When a reinforcement learning agent (a system that learns to act by trial and error) faces an environment that changes over time, it has to forget outdated experience. Current methods forget globally. Provably efficient algorithms keep a sliding window over recent episodes or restart the policy on a schedule. Practical deep methods reweight the entire replay buffer, the memory of past transitions, once a change is detected. Both throw away good data along with bad. Many real changes are local: one corridor gets blocked, one room becomes slippery, one actuator wears out. A lookup-table agent could handle this cheaply, because each state's statistics live in their own entry and can be reset alone. Neural networks lose that isolation, since every update touches every state. This is the root of the function approximation gap in this setting.
We propose to restore isolation in the bookkeeping, not in the value function. The agent learns a coarse discrete code for its states. It uses that code only to keep per-region transition statistics and to run a statistical change test in each region. When a region's dynamics change, the agent drops just that region's stale transitions from replay and pushes fresh updates backward to the regions that lead into it. A neural network still does all value learning and generalization. In two sentences: deep agents forget too much because they cannot tell where the world changed, so we give them a cheap discrete map for detecting and forgetting change locally. Our hypothesis is that this cuts the post-change data cost from roughly the size of the replay buffer to roughly the size of the changed region, and that it works with sparse rewards because detection uses dynamics, not rewards.
Core Claim
The claim is narrow and testable. When environment change is spatially localized, per-region change detection and forgetting should recover faster than global windows, global restarts, or global reprioritization. It should do so without losing performance in unchanged regions. When change is global, as with a uniform mass or friction shift, the method should roughly match the best global method, not beat it. That second prediction is a built-in falsification check. If our method wins equally on global drift, the gain comes from something other than locality, and the story is wrong.
Four lines of prior work motivate and constrain this.
The theory papers supply the motivation by showing that forgetting is the price of tracking:
- Non-stationary Reinforcement Learning under General Function Approximation bounds dynamic regret for its SW-OPEA algorithm using a global sliding window tuned to a known variation budget. Its optimism step is intractable for neural networks.
- Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs (PROPO) uses periodic full restarts in linear kernel MDPs.
- Dynamic Regret of Adversarial Linear Mixture MDPs softens restarts with a fixed-share rule. It handles unknown change through an ensemble of learners.
All three forget uniformly across the state space. We do not try to inherit their guarantees for neural networks. Instead we ask what a per-region window buys in the tabular case, where the analysis is tractable.
The closest empirical work is Sample Efficient Experience Replay in Non-stationary Environments (DEER). It shows that standard prioritized replay confuses learning progress with environment change, and it fixes this with a change-aware priority. However, DEER detects change from a divergence test on reward sequences, which is blind when rewards are sparse. Its response is also a global two-phase priority schedule.
Our method borrows its mechanism from Efficient ModelBased Deep Reinforcement Learning with Variational State Tabulation (VaST). VaST compresses pixels into 8–32 bit discrete codes and runs table-based prioritized sweeping, which adapted to a new teleporter shortcut after one forced run. VaST's transition counts are cumulative, though, so it never forgets. Our expectation is that it handles added shortcuts well and removed paths poorly, because stale counts for a blocked corridor keep dominating. We reuse VaST's discrete code but put it to a different job: change detection and replay invalidation, with values left to a standard deep learner.
Finally, Balancing Plasticity and Stability with Fast and Slow Successor Features constrains the design. It shows that weight resets and plasticity injection collapse under gradual drift, while protecting learned representations prevents collapse. That result rules out any design that answers detection by resetting network weights. Our response to a detected change touches data, never parameters.
Research Program
The agent has three parts.
The first is an encoder that maps observations to a discrete code, trained on a reconstruction-style objective as in VaST and updated slowly so that code identities stay stable over time. Each code value defines a cell.
The second is a per-cell, per-action statistics store. For pixel mazes it holds counts over next-cell codes. For continuous control it holds residuals of a small learned dynamics model, pooled within the cell. In each cell we compare recent transitions against older ones with a two-window likelihood-ratio test. The detection threshold grows as the cell's sample count shrinks, so that ordinary randomness in the transitions does not trigger alarms. This targets the open problem, noted for surprise-based detectors, of mistaking noise for structural change.
The third part is the response to a detection. Pre-change transitions originating in the flagged cell are removed from the replay buffer and that cell's statistics restart. Post-change transitions from the cell, and from its predecessor cells in the empirical transition graph, receive raised replay priority, in the spirit of prioritized sweeping. The value learner is an ordinary off-policy deep agent: DQN-style for VizDoom and Miniworld, TD3 for MuJoCo. It trains with Adam and uses no architectural changes. This avoids the SGD-only restriction of synaptic consolidation.
The analytical part is modest and stated as a conjecture to be proved. In a tabular episodic MDP with variation budget decomposed across states, per-state sliding windows should give a dynamic regret whose variation-dependent term involves only the variation and visitation of the changed states. Global windows instead pay for the total variation spread over all states. We will try to prove this by adapting the standard sliding-window argument state by state. We will then measure empirically how coding error, meaning cells that merge truly different states, erodes the advantage.
Baselines
Naive reference. The same deep learner with a large uniform replay buffer and no change handling. It shows how much stale data actually hurts in each environment.
Tuned sliding window. A first-in, first-out replay buffer whose window length is chosen by grid search with the true change schedule known. This gives the global-forgetting baseline an advantage it would not have in deployment. It is the practical analogue of the global windows in SW-OPEA and PROPO.
Prioritized experience replay. Standard replay prioritized by temporal-difference error.
DEER. The strongest existing empirical competitor and the method closest to ours. Since the file lists no code resource, we reimplement it from the paper. On Ant, HalfCheetah, Hopper and InvertedDoublePendulum with shifts applied halfway through training, it reports an average improvement of 11.54% over existing replay methods, rising to 22.53% under the extreme 200% shift. We first reproduce its protocol and check that our reimplementation recovers a margin of that order over prioritized replay before using it anywhere else.
Unmodified VaST. Included for the maze tasks. The paper reports that it learned to use a new teleporter shortcut in about 160 episodes after one forced run, where other baselines largely failed.
Fast-and-slow successor features. The SF + SC agent, included for the drift tasks.
All methods share:
- the same network sizes and environment step budgets,
- an equal hyperparameter search budget,
- ten seeds per condition,
- one environment change schedule, unknown to every method except the oracle-tuned window.
Beating DEER means faster recovery and higher return after the change on local-change tasks, with intervals that do not overlap across seeds, and no loss on DEER's own global-shift protocol.
Three ablations isolate the key ingredients:
- Global response. Our detector is kept, but any detection triggers global forgetting. This tests whether locality is what matters.
- No pooling. Per-transition model-error weighting replaces the cell-pooled test. This tests whether the discrete partition earns its place.
- Reward-based detection. DEER's reward-divergence detector replaces our dynamics test. This tests the sparse-reward claim.
Why not just…?
Why not just use a short sliding-window buffer? A window short enough to purge stale data from the changed region also purges valid data from every unchanged region. Its right length depends on a variation budget that is unknown in practice, as Feng et al. note. We give the window its best length using the true change schedule. If even that oracle-tuned window matches us on local-change tasks, locality buys nothing and we would report that outcome.
Why not just use DEER? DEER already separates environment change from learning progress, and on dense-reward, globally shifted MuJoCo it may well be as good as anything we build. We expect parity there. However, its detector reads reward sequences, which stay at zero in sparse-reward mazes. Its response is also global. The sparse-reward maze tasks and the reward-detector ablation decide this question directly.
Why not just weight each replayed transition by a world model's prediction error, with no discrete cells? This is the most serious threat. It is simpler and needs no encoder. Its weakness is that a single transition's error cannot distinguish randomness from change, and in stochastic environments, such as slippery rooms, it should both falsely discard good data and react late. The no-pooling ablation tests exactly this. If it matches the full method, we drop the cells and publish the simpler method.
Why not just reset weights or inject plasticity when change is detected? Chua et al. report that plasticity-based variants often collapsed entirely under severe mass drift on Humanoid. Nikishin et al. show that plasticity injection does not help when the bottleneck is elsewhere, as on Assault. We include plasticity injection, triggered by our detector, as a further comparison in the drift tasks.
Proposed Experiments
VizDoom mazes. Starting from VaST's H-maze, we run three changes: the original teleporter added after 400,000 steps, a corridor blocked at the same point, and a flipped goal reward. The blocked corridor is the decisive case. Stale data actively misleads there, and we predict both VaST and the large-buffer baseline recover slowly from it.
3D Miniworld slippery four rooms. We let slippage drift in one room only and, separately, in all four. The single-room versus all-room contrast tests the locality prediction directly.
MuJoCo Gymnasium. We use DEER's global 50% and 200% parameter shifts as the negative control where we expect no gain. We add two local variants: friction changes on a terrain patch, and a sparse-goal Hopper.
We measure four things:
- Recovery time: episodes until return reaches 90% of a post-change reference agent trained on the new environment alone.
- Area under the return curve after the change.
- Retention: return on probe episodes that start in unchanged regions.
- Detector false alarms: rate on matched stationary runs with stochastic transitions.
The proposal stands or falls on four checks. Local-change recovery must clearly beat both the oracle-tuned window and DEER. Global-shift results must show parity with DEER, not a win, consistent with the locality explanation. The global-response ablation must lose most of the advantage on local tasks. Retention in unchanged regions must stay at its pre-change level. If the global-shift parity check fails in our favor, or the no-pooling ablation matches the full method, the locality story is wrong or the cells are unnecessary.
References
- Non-stationary Reinforcement Learning under General Function Approximation
- Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
- Dynamic Regret of Adversarial Linear Mixture MDPs
- Sample Efficient Experience Replay in Non-stationary Environments
- Efficient ModelBased Deep Reinforcement Learning with Variational State Tabulation
- Balancing Plasticity and Stability with Fast and Slow Successor Features
- Deep Reinforcement Learning with Plasticity Injection