Adaptive Memory for Online Reinforcement Learning under Sparse Model Changes

Sreejeet Maity, Sukanya Modak, Leonardo F. TosoarXiv 2026 · arXiv

TL;DR

This paper introduces an adaptive history selection algorithm for reinforcement learning in environments that undergo sparse changes over time. By selectively reusing past observations for individual reward and transition entries only when they remain consistent with current data, the method achieves significantly lower policy loss than standard approaches while maintaining a compact memory footprint of only $O(1/\epsilon)$ deployment summaries.

What Problem Does This Paper Address?

In many real-world reinforcement learning (RL) scenarios, the environment is non-stationary. For example, a delivery robot might find a familiar route blocked, or a retailer might see a sudden shift in customer demand. Standard RL agents face a dilemma when these changes occur:

  1. Restarting: If the agent throws away all past data and learns from scratch, it is safe from "stale" information but extremely inefficient, as it ignores parts of the environment that haven't changed.
  2. Full History: If the agent pools all past data, it benefits from more samples but risks biased estimates because it's using data from before a change occurred.

The authors identify a middle ground: sparse changes. Often, even if the optimal policy changes, only a small fraction ($\epsilon$) of the underlying reward entries or transition probabilities actually move. The challenge is adaptively deciding which specific pieces of history are still valid without knowing exactly where or when the changes happened.

Methods

The authors propose Algorithm 1: Adaptive History Model Learning. Its key innovation is treating the history of every state-action pair $(s, a)$ independently.

  • Component-Level Granularity: Instead of one global "memory window," the agent maintains separate histories for every single reward entry and transition row.
  • Consistency Checks: For each $(s, a)$, the agent starts with the current deployment's data and looks backward through past deployments. It constructs confidence intervals (for rewards) and confidence sets (for transitions). It keeps adding older data as long as there exists a single value that fits within the intersection of all confidence sets in that window. If the intersection becomes empty, it indicates a likely model change, and the agent stops looking further back.
  • Deployment Summaries: To keep memory usage low, the agent doesn't store every individual observation. Instead, it stores "summaries"—visit counts, reward sums, and successor state counts—for a fixed number of recent deployments ($B$).
  • Policy Computation: Before each new observation, the agent fits an MDP using these adaptively selected histories and computes an optimal policy by solving the Bellman optimality equation.
Visualizing sparse changes in reward (R) and transition (P) matrices across deployments.

Datasets

The researchers evaluated their approach using a synthetic MDP environment designed to simulate sparse non-stationarity:

  • Environment: An MDP with 50 states and 4 actions.
  • Dynamics: Reward and transition changes were restricted to specific 20% subsets of the state-action space. At each deployment boundary, a fraction $\epsilon$ of these entries were resampled.
  • Baselines: They compared their method against Restart (using only current data), Full History (using all data), and Shared History (using a single history window for the entire model).

Key Insights and Ideas

  • The Power of "Local" Forgetting: The "aha" moment is that you don't need to forget everything just because something changed. By tracking history at the $(s, a)$ level, the agent can keep using high-quality, high-volume data for the 99% of the model that remains static.
  • Intersection as a Change Detector: Using the intersection of confidence intervals is a clever, parameter-free way to detect changes. It naturally balances the "bias-variance tradeoff": more data reduces variance, but if that data is from a different distribution (bias), the intersection will eventually vanish.
  • Theoretical Efficiency: The authors prove that the agent only needs to store $O(1/\epsilon)$ deployment summaries to achieve near-optimal long-run performance. This makes the algorithm highly scalable for long-term deployments.

Key Results

The paper provides both strong theoretical guarantees and empirical evidence:

  • Theoretical Bound: They prove a long-run average policy loss of at most $\widetilde{O}(\sqrt{\epsilon/H})$, where $\epsilon$ is the change fraction and $H$ is the deployment length. This shows the error scales gracefully with the rate of environmental change.
  • Empirical Performance: In simulations, the proposed method consistently achieved the lowest average policy loss.
  • Quantifiable Gains: For a change rate of $\epsilon = 0.005$, the proposed method reduced average policy loss by 65.2% compared to the "Shared History" baseline over the final 40 deployments. Unlike the "Full History" approach, which actually gets worse over time as it accumulates more stale data, the proposed method's error continues to decline.
Comparison of the proposed method against baselines. The proposed method (purple) maintains the lowest policy loss as deployments (K) increase.

Limitations and Future Work

  • Known Boundaries: The current theory assumes the agent knows exactly when a "deployment" ends and a potential change occurs. In many real-world settings, changes are continuous or boundaries are unknown.
  • Sampling Model: The analysis assumes an independent sampling model (where state-action pairs are drawn from a fixed distribution). Extending this to "active" RL, where the agent's own policy determines which data it collects, is a significant next step.
  • Scalability to Deep RL: While the summary statistics approach is efficient for tabular MDPs, adapting these "consistency checks" to high-dimensional spaces using neural network function approximators remains an open challenge.

Summary updated

Abstract

We study the discounted reinforcement learning (RL) problem in a setting where the underlying environment changes between deployments. Each deployment provides $H$ observations from a fixed MDP. The reward function and transition kernel are fixed within each deployment. Across deployments, at most an $ε>0$ fraction of the reward and transition kernel entries may change. In this setting, learning each model to deploy from scratch may discard useful observations from past deployments, whereas pooling all past observations can bias the estimates of entries that have already changed. We then propose an algorithm that for each state and action pair, selects how much history to reuse to estimate the reward and probabilities of the next state. We start with observations from the current deployment and add earlier deployment observations one at a time, the most recent first. After each addition, we check whether a single average reward agrees with the estimates from all histories considered until that point. We apply the same check to the distribution of next states. For each estimate, we leverage the last history that passes these aforementioned checks. The optimal control policy is then computed on top of the fitted MDP. We characterize the average gap between the optimal return and the return of the learner's policies over a finite number of deployments. We demonstrate that when $0< |S|ε\leq 2$, with $|S|$ being the cardinality of the state space, our algorithm needs only the observations from the most recent $O(1/ε)$ deployments, and achieves a long-run average gap of at most $\widetilde{O}(\sqrt{ε/H})$.
BibTeX
@misc{maity2026adaptive,
  author = {Sreejeet Maity and Sukanya Modak and Leonardo F. Toso},
  title = {{Adaptive Memory for Online Reinforcement Learning under Sparse Model Changes}},
  year = {2026},
  eprint = {2611.21879},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21879},
}
Figure