Exact Unlearning for Reinforcement Learning in Linear MDPs
Desk rejected at ICLR 2027, so left out of the paper lists and the map.
Abstract
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 -TV-stable RL learner and a *coupling*-based exact RL unlearner. Our -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 . At the same time, the learner is -TV-stable and has regret , retaining the optimal order in the -independent term; here is the feature dimension, is the horizon, and is the number of episodes.
- Primary area:
- learning theory