Exact Unlearning in Reinforcement Learning
2026-06-02 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors study how to efficiently remove a specific user's data from a reinforcement learning system so that the updated system looks like the user was never there. They propose an algorithm that balances stability and computational cost, making the unlearning process much faster than retraining from scratch. Their method works for environments modeled by Markov decision processes and comes with performance guarantees close to the best possible. They also prove mathematical limits showing their approach is nearly optimal.
Reinforcement LearningExact UnlearningMarkov Decision ProcessTotal Variation StabilityRegret BoundAlgorithmic StabilityComputational CostMinimax OptimalityEpisodesState-Action Space
Authors
Thanh Nguyen-Tang, Raman Arora
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 $ρ>0$, we show that there exists a reinforcement learning (RL) algorithm that is $ρ$-TV-stable and supports an exact unlearning procedure whose expected computational cost is only a $ρ\sqrt{\ln T}$ fraction of the computational cost of retraining from scratch. We construct such a $ρ$-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}/ρ)$, 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 $Ω(H\sqrt{\!SAT}\! +\! {SAH}/ρ)$ for $ρ$-TV-stable RL algorithms, showing that our algorithm is nearly minimax optimal.