Exact Unlearning in Reinforcement Learning

A new study formulates the problem of exact unlearning in reinforcement learning, proposing an algorithm that can remove a user's data upon request while leaving the model's output indistinguishable from one trained without that data [1]. The work, posted to arXiv on June 2, 2026, addresses a gap at the intersection of data privacy and sequential decision-making. While machine unlearning has been studied in supervised learning contexts, its application to reinforcement learning has remained largely unaddressed [3]. A separate line of research introduced the term "reinforcement unlearning" to describe the revocation of entire training environments, noting that reinforcement learning agents tend to memorize features of their environments, raising privacy concerns under data protection regulations [4]. The new paper instead focuses on removing individual user interactions from an online learner's history [1]. The authors define exact unlearning through the lens of Total Variation stability, a framework previously developed by Ullah et al. and Ullah and Arora [3]. For any stability parameter ρ greater than 0, they construct a ρ-TV-stable algorithm for tabular Markov decision processes that supports an exact unlearning procedure [1]. The expected computational cost of this procedure is only a ρ√ln T fraction of the cost of retraining from scratch, where T denotes the number of episodes [2]. The algorithm achieves a regret bound of O(H²√SAT + H³S²A + H²·⁵S²A/ρ), where S is the number of states, A the number of actions, and H the episode horizon [1]. The researchers also establish a lower bound of Ω(H√SAT + SAH/ρ) for the class of ρ-TV-stable RL algorithms, demonstrating that their upper bound is nearly minimax optimal [2]. To construct the algorithm, the authors extend the UCB-VI method introduced by Azar et al. in 2017. Modifications include replacing visitation statistics with binary-tree, noise-perturbed prefix sums while preserving optimism, and storing intermediate sufficient statistics so that unlearning can reuse randomness through maximal coupling [3]. The regret proof is extended to control additional variance from correlated Gaussian noise, matching UCB-VI up to logarithmic factors [3]. The broader unlearning literature has explored alternative approaches. One method, decremental reinforcement learning, involves deliberately erasing an agent's learned knowledge about a specific environment [4]. Another, environment poisoning, creates modified experience samples to induce forgetting while preserving performance in other environments [4]. A more recent framework called PURGE treats unlearning as a verifiable task within reinforcement learning, using measurable indicators of data removal to guide the forgetting process [5].