pith. sign in

arxiv: 2606.04182 · v1 · pith:CDP452J7new · submitted 2026-06-02 · 💻 cs.LG · cs.AI· stat.ML

Exact Unlearning in Reinforcement Learning

Thanh Nguyen-Tang , Raman Arora This is my paper

Pith reviewed 2026-06-28 10:43 UTC · model grok-4.3

classification 💻 cs.LG cs.AIstat.ML
keywords exact unlearningreinforcement learningtabular MDPstotal variation stabilityregret boundsdata deletion
0
0 comments X

The pith

There exists an RL algorithm for tabular MDPs that supports exact unlearning of any user's data at only a ρ√(ln T) fraction of the cost of retraining from scratch while keeping near-optimal regret.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper formulates exact unlearning in reinforcement learning as the requirement that after deleting a user's data the learner's output must be indistinguishable from the output that would have been produced if that user had never interacted. It proves that for any positive ρ one can build a ρ-TV-stable RL algorithm whose expected unlearning cost is only that small fraction of full retraining cost. For finite tabular MDPs the construction achieves a concrete regret bound of order H²√(SAT) plus lower-order terms divided by ρ, and a matching lower bound shows the construction is nearly minimax optimal.

Core claim

For any ρ > 0 there exists a ρ-TV-stable reinforcement learning algorithm that supports an exact unlearning procedure whose expected computational cost is only a ρ √(ln T) fraction of the cost of retraining from scratch; for tabular MDPs this algorithm attains regret O(H² √(SAT) + H³ S² A + H^{2.5} S² A / ρ) and the matching lower bound Ω(H √(SAT) + SAH / ρ) establishes near-optimality.

What carries the argument

A ρ-TV-stable RL algorithm for tabular MDPs that maintains a stability property allowing an exact unlearning procedure whose cost scales with ρ √(ln T).

If this is right

  • Exact unlearning becomes computationally practical for any ρ without sacrificing the core learning performance up to the lower-order additive terms.
  • The lower bound establishes that some dependence on 1/ρ in the regret is unavoidable for any algorithm supporting this form of exact unlearning.
  • The same stability-plus-unlearning framework applies uniformly to every deletion request rather than requiring a separate retraining run each time.
  • Regret remains controlled by the usual √(SAT) term plus an additive penalty linear in 1/ρ, so choosing larger ρ trades stability for better regret.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same stability idea might be combined with function approximation to handle large or continuous state spaces, though the current analysis is limited to tabular MDPs.
  • If the unlearning cost scaling holds in practice it would allow modular deletion in deployed RL systems such as recommendation or robotics without periodic full retraining.
  • The lower-bound construction suggests that any future unlearning method in RL must pay either in regret or in stability parameter ρ.

Load-bearing premise

The environment must be a finite tabular MDP in which ρ-TV-stability can be maintained without destroying the stated regret bound.

What would settle it

An explicit tabular MDP and value of ρ for which every ρ-TV-stable algorithm either exceeds the stated regret or requires unlearning cost larger than ρ √(ln T) times retraining cost.

Figures

Figures reproduced from arXiv: 2606.04182 by Raman Arora, Thanh Nguyen-Tang.

Figure 1
Figure 1. Figure 1: Hard MDPs. Proof of Theorem D.4. To prove the hardness result, consider the following class of MDPs in [PITH_FULL_IMAGE:figures/full_fig_p023_1.png] view at source ↗
read the original abstract

We formulate the problem of \emph{exact unlearning} in reinforcement learning, where the goal is to design an efficient framework that enables the removal of any user's data upon deletion request, i.e., the online learner's output after unlearning is \emph{indistinguishable} from what would have been produced had the deleted user never interacted with the learner. For any $\rho >0$, we show that there exists a reinforcement learning (RL) algorithm that is $\rho$-TV-stable and supports an exact unlearning procedure whose expected computational cost is only a $\rho \sqrt{\ln T}$ fraction of the computational cost of retraining from scratch. We construct such a $\rho$-TV-stable RL algorithm for tabular Markov decision processes (MDPs), which achieves a regret bound of $\mathcal{O}(H^2 \sqrt{SAT} + H^3 S^2 A + {H^{2.5} S^2 A}/{\rho})$, where $S, A, H$, and $T$ denote the number of states, the number of actions, the episode horizon, and the number of episodes, respectively. We also establish a lower bound of $\Omega(H\sqrt{\!SAT}\! +\! {SAH}/{\rho})$ for $\rho$-TV-stable RL algorithms, showing that our algorithm is nearly minimax optimal.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper formulates exact unlearning in RL, requiring that after deleting a user's data the learner's output is indistinguishable from the output that would have been produced had the user never interacted. It claims that for any ρ > 0 there exists a ρ-TV-stable RL algorithm whose exact unlearning procedure has expected computational cost only a ρ √(ln T) fraction of retraining from scratch. For finite tabular MDPs it constructs such an algorithm achieving regret O(H² √(SAT) + H³ S² A + H^{2.5} S² A / ρ) and proves a matching lower bound Ω(H √(SAT) + SAH / ρ) establishing near-optimality.

Significance. If the stated construction and bounds hold, the result is significant: it supplies the first rigorous framework for exact unlearning in RL together with both computational-efficiency and regret guarantees in the tabular setting. The explicit lower bound that matches the upper bound up to lower-order terms is a clear strength, as is the parameter-free dependence on ρ in the unlearning-cost fraction.

major comments (2)
  1. [algorithm construction and regret analysis (presumably §3–4)] The central existence claim rests on the construction of a single algorithm that is simultaneously ρ-TV-stable and achieves the stated regret for every ρ > 0. The manuscript must therefore verify, in the section presenting the algorithm and its analysis, that the mechanism used to enforce the total-variation stability parameter ρ does not inflate the regret beyond the explicit H^{2.5} S² A / ρ term already present in the bound.
  2. [lower-bound section] The lower-bound argument (presumably §5) is stated only for ρ-TV-stable algorithms on finite tabular MDPs. The manuscript should clarify whether the Ω(SAH / ρ) term continues to hold if the stability property is relaxed or if the MDP is permitted to be infinite; otherwise the near-optimality statement is limited to the tabular case already assumed for the upper bound.
minor comments (2)
  1. [abstract] The abstract and introduction should define the symbols S, A, H, T at first use rather than deferring the definitions to the regret statement.
  2. [preliminaries] Notation for total-variation stability (ρ-TV-stable) should be introduced with a formal definition before it is used in the main theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for their detailed feedback, which has helped us identify areas for improvement in the presentation of our results. Below we provide point-by-point responses to the major comments.

read point-by-point responses

  1. Referee: [algorithm construction and regret analysis (presumably §3–4)] The central existence claim rests on the construction of a single algorithm that is simultaneously ρ-TV-stable and achieves the stated regret for every ρ > 0. The manuscript must therefore verify, in the section presenting the algorithm and its analysis, that the mechanism used to enforce the total-variation stability parameter ρ does not inflate the regret beyond the explicit H^{2.5} S² A / ρ term already present in the bound.

    Authors: Thank you for highlighting this important aspect of the analysis. Our algorithm construction in Sections 3 and 4 is parameterized by ρ, and the regret bound is derived to include the additional term H^{2.5} S² A / ρ precisely to account for the cost of enforcing ρ-TV-stability. The analysis shows that the stability mechanism contributes exactly this term without further inflation. To make this verification more explicit, we will add a dedicated paragraph in Section 3 clarifying how the stability enforcement integrates into the regret analysis without exceeding the stated bound. revision: yes

  2. Referee: [lower-bound section] The lower-bound argument (presumably §5) is stated only for ρ-TV-stable algorithms on finite tabular MDPs. The manuscript should clarify whether the Ω(SAH / ρ) term continues to hold if the stability property is relaxed or if the MDP is permitted to be infinite; otherwise the near-optimality statement is limited to the tabular case already assumed for the upper bound.

    Authors: We agree that clarification is needed here. The lower bound of Ω(H √(SAT) + SAH / ρ) is established specifically for ρ-TV-stable algorithms operating on finite tabular MDPs, which aligns with the setting of our upper bound construction. We do not assert that this lower bound holds under relaxed stability notions or for infinite MDPs. The near-optimality claim is therefore with respect to the tabular MDP setting. We will revise the manuscript to explicitly state this scope in Section 5 and in the abstract/introduction as appropriate. revision: yes

Circularity Check

0 steps flagged

No significant circularity; theoretical construction is self-contained

full rationale

The paper presents an explicit algorithmic construction for a ρ-TV-stable RL procedure on finite tabular MDPs together with a matching lower bound derived from the same stability definition. Both the regret upper bound O(H²√(SAT) + H³S²A + H^{2.5}S²A/ρ) and the unlearning-cost claim are obtained directly from the stability parameter ρ and the tabular MDP structure; neither quantity is defined in terms of the other nor obtained by fitting to the same data. No self-citation is invoked as a load-bearing uniqueness theorem, and the derivation does not rename a known empirical pattern or smuggle an ansatz. The finite-MDP assumption is stated up front and is required for both bounds, but this is an explicit modeling choice rather than a definitional reduction. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The central claims rest on the tabular MDP assumption and the new stability definition; no additional free parameters beyond the user-chosen ρ are introduced.

free parameters (1)
  • ρ
    User-specified stability parameter that trades off unlearning cost against regret; appears in both upper and lower bounds.
axioms (1)
  • domain assumption The environment is a finite-horizon tabular MDP with S states, A actions and horizon H.
    Required for both the algorithm construction and the lower-bound argument; stated when the regret bounds are given.
invented entities (1)
  • ρ-TV-stable RL algorithm no independent evidence
    purpose: Algorithm class that enables efficient exact unlearning while controlling regret.
    New stability notion introduced to support the unlearning guarantee.

pith-pipeline@v0.9.1-grok · 5770 in / 1381 out tokens · 27500 ms · 2026-06-28T10:43:56.154291+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 3 linked inside Pith

  1. [1]

    Advances in neural information processing systems , volume=

    Making ai forget you: Data deletion in machine learning , author=. Advances in neural information processing systems , volume=

  2. [2]

    International Conference on Machine Learning , pages=

    From adaptive query release to machine unlearning , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    2023

  3. [3]

    Algorithmic Learning Theory , pages=

    Descent-to-delete: Gradient-based methods for machine unlearning , author=. Algorithmic Learning Theory , pages=. 2021 , organization=

    2021

  4. [4]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Differentially private regret minimization in episodic markov decision processes , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  5. [5]

    Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=

    Differentially private reinforcement learning with linear function approximation , author=. Proceedings of the ACM on Measurement and Analysis of Computing Systems , volume=. 2022 , publisher=

    2022

  6. [6]

    2021 IEEE symposium on security and privacy (SP) , pages=

    Machine unlearning , author=. 2021 IEEE symposium on security and privacy (SP) , pages=. 2021 , organization=

    2021

  7. [7]

    Advances in Neural Information Processing Systems , volume=

    Replicable reinforcement learning , author=. Advances in Neural Information Processing Systems , volume=

  8. [8]

    Privacy in Statistics and Machine Learning Spring 2021 Lecture 7: The Binary Tree Mechanism , author=

    2021

  9. [9]

    Advances in Neural Information Processing Systems , volume=

    (Nearly) optimal algorithms for private online learning in full-information and bandit settings , author=. Advances in Neural Information Processing Systems , volume=

  10. [10]

    Conference on Learning Theory , pages=

    Machine unlearning via algorithmic stability , author=. Conference on Learning Theory , pages=. 2021 , organization=

    2021

  11. [11]

    International Conference on Machine Learning , pages=

    The price of differential privacy under continual observation , author=. International Conference on Machine Learning , pages=. 2023 , organization=

    2023

  12. [12]

    International Conference on Machine Learning , pages=

    Practical and private (deep) learning without sampling or shuffling , author=. International Conference on Machine Learning , pages=. 2021 , organization=

    2021

  13. [13]

    ACM Transactions on Information and System Security (TISSEC) , volume=

    Private and continual release of statistics , author=. ACM Transactions on Information and System Security (TISSEC) , volume=. 2011 , publisher=

    2011

  14. [14]

    arXiv preprint arXiv:1711.03908 , year=

    Finite sample differentially private confidence intervals , author=. arXiv preprint arXiv:1711.03908 , year=

    Pith/arXiv arXiv

  15. [15]

    Advances in Neural Information Processing Systems , volume=

    Differentially private contextual linear bandits , author=. Advances in Neural Information Processing Systems , volume=

  16. [16]

    2025 , eprint=

    Online Learning and Unlearning , author=. 2025 , eprint=

    2025

  17. [17]

    arXiv preprint arXiv:2502.17779 , year=

    Simulating Time With Square-Root Space , author=. arXiv preprint arXiv:2502.17779 , year=

    arXiv

  18. [18]

    Bonta, Rob , journal=

  19. [19]

    Proceedings of the 22nd ACM SIGSAC conference on computer and communications security , pages=

    Model inversion attacks that exploit confidence information and basic countermeasures , author=. Proceedings of the 22nd ACM SIGSAC conference on computer and communications security , pages=

  20. [20]

    Journal of machine Learning research , volume=

    An MDP-based recommender system , author=. Journal of machine Learning research , volume=

  21. [21]

    2017 IEEE symposium on security and privacy (SP) , pages=

    Membership inference attacks against machine learning models , author=. 2017 IEEE symposium on security and privacy (SP) , pages=. 2017 , organization=

    2017

  22. [22]

    ACM Computing Surveys , year=

    Machine Unlearning: A Survey , author=. ACM Computing Surveys , year=

  23. [23]

    International conference on machine learning , pages=

    Minimax regret bounds for reinforcement learning , author=. International conference on machine learning , pages=. 2017 , organization=

    2017

  24. [24]

    Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006

    Calibrating noise to sensitivity in private data analysis , author=. Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3 , pages=. 2006 , organization=

    2006

  25. [25]

    arXiv preprint arXiv:2312.15910 , year=

    Reinforcement unlearning , author=. arXiv preprint arXiv:2312.15910 , year=

    arXiv

  26. [26]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    Differential privacy under continual observation , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  27. [27]

    International Conference on Machine Learning , pages=

    The price of differential privacy for online learning , author=. International Conference on Machine Learning , pages=. 2017 , organization=

    2017

  28. [28]

    arXiv preprint arXiv:2502.17323 , year=

    When to Forget? Complexity Trade-offs in Machine Unlearning , author=. arXiv preprint arXiv:2502.17323 , year=

    arXiv

  29. [29]

    arXiv preprint arXiv:2412.09119 , year=

    The Utility and Complexity of In-and Out-of-Distribution Machine Unlearning , author=. arXiv preprint arXiv:2412.09119 , year=

    Pith/arXiv arXiv

  30. [30]

    arXiv preprint arXiv:2306.02216 , year=

    Forgettable Federated Linear Learning with Certified Data Unlearning , author=. arXiv preprint arXiv:2306.02216 , year=

    Pith/arXiv arXiv

  31. [31]

    arXiv preprint arXiv:2310.02238 , year=

    Who's harry potter? approximate unlearning in llms , author=. arXiv preprint arXiv:2310.02238 , year=

    arXiv

  32. [32]

    Proceedings of IEEE 36th annual foundations of computer science , pages=

    Gambling in a rigged casino: The adversarial multi-armed bandit problem , author=. Proceedings of IEEE 36th annual foundations of computer science , pages=. 1995 , organization=

    1995

  33. [33]

    Advances in Neural Information Processing Systems , volume=

    Remember what you want to forget: Algorithms for machine unlearning , author=. Advances in Neural Information Processing Systems , volume=

  34. [34]

    arXiv preprint arXiv:1911.03030 , year=

    Certified data removal from machine learning models , author=. arXiv preprint arXiv:1911.03030 , year=

    arXiv 1911

  35. [35]

    Advances in neural information processing systems , volume=

    Near-optimal regret bounds for reinforcement learning , author=. Advances in neural information processing systems , volume=

  36. [36]

    IEEE Transactions on Emerging Topics in Computational Intelligence , year=

    Machine unlearning: Solutions and challenges , author=. IEEE Transactions on Emerging Topics in Computational Intelligence , year=

  37. [37]

    Mironov, Ilya , booktitle=. R. 2017 , organization=

    2017

  38. [38]

    International Conference on Machine Learning , pages=

    Private reinforcement learning with pac and regret guarantees , author=. International Conference on Machine Learning , pages=. 2020 , organization=

    2020

  39. [39]

    2015 IEEE symposium on security and privacy , pages=

    Towards making systems forget with machine unlearning , author=. 2015 IEEE symposium on security and privacy , pages=. 2015 , organization=

    2015

  40. [40]

    Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

    Private matchings and allocations , author=. Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages=

  41. [41]

    International Conference on Artificial Intelligence and Statistics , pages=

    Near-optimal differentially private reinforcement learning , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2023 , organization=

    2023

  42. [42]

    arXiv preprint arXiv:2503.14347 , year=

    A New Proof of Sub-Gaussian Norm Concentration Inequality , author=. arXiv preprint arXiv:2503.14347 , year=

    arXiv