Exact Unlearning for Reinforcement Learning in Linear MDPs

We develop a provably efficient learning–unlearning framework for episodic reinforcement learning in linear Markov decision processes. Our framework consists of a pair of a $\rho$-TV-stable RL learner and a *coupling*-based exact RL unlearner. Our $\rho$-TV-stable learner releases weighted Gram matrices through a binary tree and releases three value-dependent Bellman vectors only at policy switching. Upon a replacement request, the unlearner constructs an approximately maximal coupling between the randomized output of the learner and its counterfactual output had the replaced data not been present to the learner to begin with. We show that we achieve an efficient exact unlearner, whose retraining probability scales only with $\mathcal{O}(\rho )$. At the same time, the learner is $\rho$-TV-stable and has regret $\tilde{\mathcal{O}}(d{H}^{3/2}\sqrt{K}+d^2{H}^3\sqrt{K/\rho }+d^9{H}^8/\rho )$, retaining the optimal order in the $\rho$-independent term; here $d$ is the feature dimension, $H$ is the horizon, and $K$ is the number of episodes.