In classical machine learning and optimization, we usually assume the world is static. We seek a single "optimal" model or action that performs well on average. But in real-world applications—like dynamic pricing, high-frequency trading, or robotic control—the "ground truth" is a moving target. A pricing strategy that worked yesterday might fail today because of a shift in consumer behavior; a robot’s optimal path might change as its joints wear down.
The challenge of non-stationary optimization is learning to track these shifts in real-time. The goal is no longer to minimize standard regret (performance against the best fixed action), but rather dynamic regret: the gap between our performance and a "dynamic oracle" that always picks the best action for the current moment.
The Variation Budget Dilemma
The fundamental difficulty in non-stationary environments is balancing memory and adaptation. If an algorithm remembers too much history, it becomes sluggish and fails to react to changes. If it forgets too quickly, it becomes hypersensitive to noise.
As Yonatan Gur, assaf zeevi, and Omar Besbes established in Non-stationary Stochastic Optimization, the optimal way to tune this balance depends on the variation budget ($V_T$)—the total amount the environment changes over time. If you know $V_T$ in advance, you can mathematically derive the perfect "forgetting rate."
However, in practice, the variation budget is almost never known. This creates a "catch-22": to optimize effectively, you need to know how much the world will change, but you can only see how much it has changed by attempting to optimize. Much of the recent research focuses on breaking this dependency to create parameter-free algorithms that adapt to unknown volatility.
Forgetting via Windows and Restarts
To handle non-stationarity, an agent must eventually "forget" old data. Two primary mechanisms dominate the literature:
- Sliding Windows: Algorithms like Sliding-Window Thompson Sampling (SW-TS), analyzed by Francesco Trovò and Marcello Restelli in Sliding-Window Thompson Sampling for Non-Stationary Settings, maintain a fixed-length buffer of recent observations. This ensures the model is always trained on "fresh" data, though choosing the window size remains a challenge when the drift rate is unknown.
- Periodic Restarts: Instead of a sliding window, algorithms like RestartQ-UCB—introduced by Weichao Mao and Kaiqing Zhang in Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs—periodically wipe their memory and start over. This is particularly effective in Reinforcement Learning (RL), where old transition data can actively mislead an agent if the environment's physics have shifted.
Meta-Learning for Unknown Volatility
Since we don't know the variation budget, how do we choose the right restart interval or window size? A powerful solution is to use meta-algorithms.
In Adaptive Online Learning in Dynamic Environments, Lijun Zhang and Zhi-Hua Zhou proposed Ader. Instead of running one optimizer, Ader runs a suite of "expert" optimizers, each tuned to a different possible variation budget. A higher-level meta-algorithm then aggregates their advice, favoring the experts that are currently performing best.
This hierarchical approach allows the system to "learn the learning rate." If the environment suddenly becomes more volatile, the meta-algorithm shifts weight to the experts that forget more quickly. This strategy has been extended to complex settings like Online Convex Optimisation, where Stephen Pasteris and Mark Herbster developed the RESET algorithm to achieve optimal switching regret across all possible segmentations simultaneously.
The Cost of Change
The theoretical price of non-stationarity is steep. In a stationary multi-armed bandit problem, the regret typically grows at a rate of $\sqrt{T}$. However, when rewards are non-stationary, Yonatan Gur and colleagues proved in Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewards that the optimal regret scales as $T^{2/3}$.
This $T^{2/3}$ rate represents a fundamental limit: in a shifting world, you must spend a larger fraction of your time exploring just to keep up with the changes. Recent work by Xi Chen and Yining Wang in Non-stationary Stochastic Optimization under $L_{p,q}$-Variation Measures further refines this by showing how the "curse of dimensionality" interacts with these temporal shifts, revealing that tracking a moving target becomes exponentially harder as the number of features increases.
Beyond Simple Drift
While much of the field focuses on gradual drift, researchers are also exploring structured non-stationarity:
- Sparse Changes: In Higher-criticism for sparse multi-stream change-point detection, Tingnan Gong and Alon Kipnis look at "needle in a haystack" scenarios where only a few data streams out of thousands change at once.
- Safe Adaptation: Honghao Wei and Ness Shroff have developed model-free RL algorithms for Non-stationary CMDPs that guarantee zero safety constraint violations even as the environment's rules change.
By moving away from the assumption of a static world and developing algorithms that can estimate their own "variation budget," this research direction is bridging the gap between theoretical optimization and the messy, ever-changing reality of autonomous systems.