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:
- 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.
- 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.
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.
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