Data Deletion Can Help in Adaptive RL

Param Budhraja, Aditya Gangrade, Alex Olshevsky, Venkatesh SaligramaarXiv 2026 · arXiv

TL;DR

In adaptive reinforcement learning, training a context estimator on all historical data can backfire due to distribution shifts caused by evolving policies. This paper introduces a counterintuitive yet highly effective fix: randomly deleting a fraction of the training buffer after each round, which implicitly decays stale data while preserving crucial diversity.

What Problem Does This Paper Address?

Reinforcement learning (RL) agents often struggle to generalize when deployed in real-world environments where physical properties—like gravity, friction, or mass—fluctuate over time. To tackle this, researchers use the Contextual Markov Decision Process (cMDP) framework. The standard approach splits the problem into two parts:

  1. A universal policy that learns the optimal actions given the true environment context.
  2. A context estimator that predicts this hidden context at test time based on the agent's recent state-action history.

The catch lies in how these components are trained. Training happens in multiple alternating rounds: the estimator learns from past trajectories, and the policy uses the updated estimator to collect new data. Because early policies are clumsy, the data they collect looks vastly different from what a mature policy encounters. This creates a severe distribution mismatch, causing the context estimator to perform poorly at deployment.

Methods

The authors propose a remarkably simple trick: Random Data Deletion.

Instead of accumulating all trajectories in a massive replay buffer, they delete a randomly chosen fraction ($1-\alpha$) of the buffer after each training round. Because older data must survive multiple rounds of deletion, its presence decays exponentially. This automatically prioritizes recent, high-quality data without requiring complex tracking of sample age or quality.

To understand why this works, the authors also analyze a simplified, idealized setting: regularized empirical risk minimization (ERM) with a mismatch between training and test distributions. They mathematically prove that under mild conditions, removing a uniformly random training point strictly decreases the expected test loss. For ridge regression, they show this benefit is most pronounced when the signal-to-noise ratio (SNR) is low and regularization is moderate.

Datasets

The method was evaluated across several standard simulation environments where context parameters were systematically varied:

  • Gym Suite (Classical Control & Box2D): Pendulum (varying gravity and length), LunarLander (varying gravity), Acrobot (varying link mass and length), and Mountain Car (varying gravity and force).
  • Brax Locomotives: Ant and Halfcheetah (varying friction and mass).
  • Supervised Learning Benchmarks: MNIST and CIFAR were also utilized to validate the theoretical insights by intentionally introducing out-of-distribution classes during training.

Key Insights and Ideas

  • The Stale Data Dilemma: Keeping all historical data introduces out-of-distribution noise from early, poorly performing policies. However, completely wiping out old data (termed "stale deletion") destroys data diversity, which is vital for robust estimation.
  • Implicit Exponential Decay: Random deletion strikes a perfect balance. It doesn't explicitly identify which samples are stale; instead, probability naturally filters out older samples over time while preserving a diverse, randomized subset of historical trajectories.
  • Levelling the Playing Field for Small Models: Large models often have the capacity to absorb distribution mismatches, but smaller models easily overfit to bad historical data. Random deletion acts as a powerful regularizer for these compact architectures.

Key Results

  • Shrinking the Robustness Gap: Implementing random data deletion reduced the robustness gap (the performance distance to an oracle policy with perfect context knowledge) by 30% for MLPs and 6% on average for recurrent networks (LSTMs and GRUs).
  • Doing More with Less: Remarkably, a narrow MLP with 5× fewer parameters trained with random deletion outperformed a wide MLP trained on the full dataset.
  • Supervised Validation: In the MNIST and CIFAR image classification experiments, excluding just 5% of the data consistently boosted test accuracy under distribution shifts across various regularization settings.

Limitations and Future Work

While empirically powerful, the paper's theoretical framework has limitations. The mathematical proof relies on a strong convexity assumption, which is rarely satisfied by deep neural networks in practice. Furthermore, the theory only models the deletion of a single random data point, whereas practical RL implementations delete 10% to 50% of the buffer at a time.

Bridging this gap by developing a non-convex theory that accounts for fractional data deletion remains an open and promising direction for future research.

Summary updated

Abstract

Deploying reinforcement learning policies in the real world requires adapting to time-varying environments. We study this problem in the contextual Markov Decision Process (cMDP) framework, where a family of environments is indexed by a low-dimensional context unknown at test time. The standard approach decomposes the problem: train a so-called "universal policy" which assumes knowledge of the true context, then pair it with a context estimator which approximates context using the observed trajectory. We identify a simple, counterintuitive trick that substantially improves the estimator: randomly delete a fraction of the training buffer after each round. This works because data is collected across multiple rounds using progressively better policies, and older trajectories come from a different distribution than what the estimator will face at deployment time; random deletion creates an implicit exponential decay on older data while preserving diversity without requiring any explicit identification of which samples are stale. This reduces robustness gap by 30% for MLPs and by 6% on average for recurrent networks. Strikingly, it allows a narrow MLP with 5x fewer parameters to outperform a wide MLP trained without deletion. To understand when and why deletion helps, we analyze regularized empirical risk minimization with a mismatch between the train distribution and the distribution at deployment; in this idealized setting, we prove that removing a single uniformly random training point decreases expected test loss in expectation under mild conditions. For ridge regression we make this quantitative: deletion helps when the regularization coefficient is moderate and the signal-to-noise ratio (SNR) is sufficiently low, and, crucially, this SNR threshold gives a direct measure of how large the distribution mismatch between training and deployment must be for deletion to be beneficial.
BibTeX
@misc{budhraja2026data,
  author = {Param Budhraja and Aditya Gangrade and Alex Olshevsky and Venkatesh Saligrama},
  title = {{Data Deletion Can Help in Adaptive RL}},
  year = {2026},
  eprint = {2605.00298},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.00298},
}
Figure