In classical online learning and reinforcement learning, memory is an unalloyed asset. The more data an agent collects, the more accurately it can estimate reward distributions, map transition dynamics, and converge on optimal policies.
But this assumption relies on a critical premise: stationarity. When the underlying environment changes over time—whether due to shifting user preferences in a recommendation engine, changing channel conditions in wireless communications, or evolving market trends—historical data transforms from an asset into a liability. As Huozhi Zhou et al. observe in Nonstationary Reinforcement Learning with Linear Function Approximation, a complete memory of past experiences biases models with obsolete information, severely hindering their ability to track a moving target.
To counter this, a powerful and surprisingly simple strategy has emerged across multi-armed bandits, Bayesian optimization, and reinforcement learning: periodic restarts. By systematically wiping the algorithm's internal state and clearing its memory at scheduled intervals, researchers can force models to prioritize recent data and rapidly adapt to environmental shifts.
The Core Intuition: Managing the Information Decay
To understand why discarding perfectly valid historical data works, we must look at the fundamental trade-off between statistical variance and tracking bias in non-stationary environments.
Imagine an agent trying to estimate the reward of a specific action. In a stationary world, the variance of the estimate decreases monotonically as the number of observations $N$ grows:
$$\text{Variance} \propto \frac{1}{N}$$
However, if the true reward distribution drifts over time, older observations reflect a past reality. If the agent includes these stale data points in its average, it introduces a systematic tracking bias. The value of information decays over time.
Periodic restarting resolves this tension by partitioning a long, non-stationary decision-making horizon into a sequence of discrete, shorter epochs. Within each epoch, the environment is treated as quasi-stationary. The algorithm accumulates data to drive down variance. At the boundary of the next epoch, the algorithm executes a hard reset, wiping its history clean. This mechanism instantly drops the tracking bias back to zero, allowing the model to re-learn the optimal parameters for the current state of the world.
Stationary Learning: [------------------- Accumulate Data ------------------->] (Low Variance)
Non-Stationary Drift: [--- Stale Data ---][--- Stale Data ---][-- Current --] (High Bias)
Periodic Restarts: [-- Epoch 1 --] ↺ [-- Epoch 2 --] ↺ [-- Epoch 3 --] (Balanced)
(Reset Bias) (Reset Bias) (Reset Bias)
As Peng Zhao et al. demonstrate in A Simple Approach for Non-stationary Linear Bandits, this simple epoch-based resetting is sufficient to achieve minimax optimal dynamic regret. It matches the theoretical performance of far more complex sliding-window or weighted-penalty mechanisms while significantly reducing computational and memory overhead.
Optimizing the Restart Schedule
The critical engineering challenge in periodic restarting is determining when to restart. If you restart too frequently, the agent never collects enough data within an epoch to overcome variance and learn a good policy. If you restart too infrequently, the agent spends too much time acting on obsolete information.
The optimal restart frequency is typically derived by bounding the environment's non-stationarity using a variation budget (often denoted as $\Lambda$ or $V$), which quantifies how much the underlying rewards or transition dynamics can change over a time horizon $T$.
- Known Variation Budgets: In their foundational work, Yonatan Gur et al. proved in Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards that if the total variation budget is known beforehand, the optimal batch size can be mathematically tuned to balance adaptation speed and learning stability, yielding a near-optimal regret scaling of $T^{2/3}$.
- Dynamic and Variational Bounds: When the environment changes continuously but unpredictably, the restart frequency must adapt. In Variational Regret Bounds for Reinforcement Learning, Ronald Ortner et al. proposed an algorithm that mathematically optimizes the frequency of memory clears based on the total variation across the time horizon, ensuring the agent remains responsive without sacrificing stability.
Generalization Across Domains
The periodic restart strategy has proven remarkably versatile, serving as a core mechanism across diverse algorithmic frameworks:
Bayesian Optimization
In high-dimensional optimization problems where the objective function moves over time, standard Gaussian Processes (GPs) become overly confident in past evaluations. To solve this, Xingyu Zhou et al. introduced R-GP-UCB in No-Regret Algorithms for Time-Varying Bayesian Optimization. By discarding all historical observations periodically, they prevent outdated data from biasing the GP's upper confidence bounds, allowing the algorithm to successfully track moving global optima.
Reinforcement Learning and Policy Optimization
In reinforcement learning, non-stationarity can cause an agent to permanently lock into a suboptimal policy that was only relevant during early episodes. In Dynamic Regret of Policy Optimization in Non-Stationary Environments, Yingjie Fei et al. introduced algorithms that clear policy estimates at fixed intervals. This ensures that the policy optimization process remains sensitive to recent environmental changes rather than being anchored to historical reward structures. This mechanism has been successfully extended to complex settings like Constrained Markov Decision Processes (CMDPs) by Yuhao Ding et al. in Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints, ensuring safe exploration even when objectives and safety constraints drift simultaneously.
Multi-Agent Systems and Graph Neural Networks
The strategy also scales to multi-agent and structural learning problems. For instance, Haozhe Jiang et al. developed a black-box framework in A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning that uses periodic restarts to ensure competing or collaborating agents regularly discard outdated policies and re-converge to the most recent equilibrium. Even during the training of Graph Neural Networks (GNNs), where node embeddings continuously evolve, Qingru Zhang et al. show in A Biased Graph Neural Network Sampler with Near-Optimal Regret that periodically reinitializing bandit-based neighbor samplers prevents the model from relying on obsolete data representations.
Refinements: History Pruning and Variance Awareness
While a complete, brute-force reset is highly effective, it can sometimes be too blunt an instrument. Recent innovations have focused on making the restarting process smoother and more data-dependent.
History Pruning
In online optimization algorithms like Follow the Regularized Leader (FTRL), a massive accumulation of past gradients creates immense inertia, making the algorithm sluggish. To fix this, Naram Mhaisen et al. introduced a "history pruning" mechanism in On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning. Instead of resetting the entire model, they selectively prune past gradients to synchronize the algorithm's internal historical state with its actual decision iterates, maintaining agility without losing optimization stability.
Variance-Aware Restarts
Environments do not just experience shifts in their average rewards; their underlying noise levels can fluctuate too. In Variance-Dependent Regret Bounds for Nonstationary Linear Bandits, Zhiyong Wang et al. designed restart strategies that leverage real-time variance information. By incorporating variance estimates into the restart trigger, their algorithms achieve significantly tighter performance guarantees by adapting the epoch lengths to both structural shifts and noise fluctuations.
Trade-offs and Limitations
Despite its theoretical elegance and strong performance, periodic restarting has distinct trade-offs:
- Loss of Recurring Knowledge: Because a standard restart completely wipes the agent's memory, it cannot exploit cyclic or recurring patterns. As Chen-Yu Wei et al. point out in Efficient Contextual Bandits in Non-stationary Worlds, discarding all historical data upon detecting a shift prevents the system from reusing previously learned policies that might become relevant again later.
- Discontinuous Policy Shifts: Resetting an algorithm at fixed epoch boundaries can cause sudden, discontinuous jumps in behavior or policy strategies (Goran Radanovic et al., Learning to Collaborate in Markov Decision Processes). In human-AI collaboration or physical control systems, these abrupt shifts can be jarring or destabilizing.
- Rigid vs. Adaptive Triggers: Fixed-length intervals can be highly inefficient if environmental shifts occur at irregular or unpredictable rates. To address this, authors like Xingyu Zhou et al. in Interference Constrained Beam Alignment for Time-Varying Channels via Kernelized Bandits emphasize the ongoing need for adaptive restart mechanisms that trigger based on real-time statistical change detection rather than rigid temporal schedules.
Ultimately, periodic restarting works because it embraces a fundamental truth of changing environments: sometimes, the fastest way to move forward is to forget where you have been.
Key Foundational Work
Time-Varying Gaussian Process Bandit Optimization (2016) — contributed 2 concept elements to this direction.
Stochastic Multi-Armed-Bandit Problem with Non-stationary Rewards (2014) — contributed 2 concept elements to this direction.
Tracking the Best Expert in Non-stationary Stochastic Environments (2016) — contributed 1 concept elements to this direction.