Non-Stationary Bandit

The fundamental property distinguishing non-stationary bandits: the expected reward for a given action changes over time. Unlike stationary problems where the optimal arm is fixed, here the underlying probability distribution drifts. This requires the algorithm to treat recent observations as more informative than older ones, effectively implementing a forgetting mechanism to track the moving target.

To adapt to drift, algorithms employ explicit mechanisms to weight recent data more heavily:

• Sliding Windows: Only consider the last W observations, discarding older data entirely.
• Exponential Discounting: Apply a decay factor γ (gamma) where the weight of an observation halves after a fixed number of steps.
• Weighted Least Squares: In contextual settings like Discounted LinUCB, the linear model is fit by minimizing a weighted sum of squared errors, prioritizing recent context-reward pairs.

Non-stationarity manifests in two primary patterns:

• Gradual Drift: The reward distribution changes slowly and continuously, like evolving user tastes over weeks. Discounted methods excel here.
• Abrupt Switches: A sudden, discontinuous jump in rewards, such as a product going out of stock or a viral trend emerging. This often requires change-point detection algorithms that actively monitor for statistical breaks and reset the model's memory when a shift is detected, discarding all pre-change data.

A formal extension where the state of each arm evolves independently according to a Markov process, even when not selected. This models scenarios like user patience decaying over time or inventory depleting. The optimal policy must consider not just the immediate reward but how the underlying state of all arms is changing. Solving restless bandits is PSPACE-hard, making heuristic index policies like the Whittle index a common practical approximation.

Performance is measured by dynamic regret, which compares the algorithm's cumulative reward against a powerful oracle that can switch its chosen arm a limited number of times. This is a harder benchmark than static regret. Algorithms are often characterized by their regret bound as a function of T (time horizon) and S (number of environmental switches), with optimal algorithms achieving sublinear regret that scales with the total variation of the reward sequence.

In production systems, non-stationarity is managed through online model retraining pipelines. A common pattern is the champion-challenger setup where a stable model serves traffic while a frequently retrained challenger is evaluated. Key metrics include model freshness—the time since the last update. For highly dynamic environments like flash sales or breaking news, freshness measured in minutes is critical to prevent serving stale, irrelevant recommendations.

A critical metric quantifying how recently a deployed bandit model has been updated to reflect the latest user behavior. In non-stationary environments, stale models suffer from concept drift, where the learned policy no longer matches the current reward distribution. Maintaining freshness requires a continuous training pipeline that ingests streaming data and updates model parameters without full retraining. Techniques include online gradient descent and exponential decay weighting of historical observations.

The gradual or abrupt change in the statistical properties of input features over time, distinct from reward drift. For example, a user's contextual feature vector may shift due to seasonality, a new device, or changing economic conditions. A static model will misinterpret these shifted contexts, leading to poor action selection. Detection requires monitoring the population stability index (PSI) or using adaptive windowing (ADWIN) to trigger model retraining when drift exceeds a threshold.

A machine learning paradigm where the model updates incrementally as each new data point arrives, rather than training on a static batch. This is the natural fit for non-stationary bandits, as it allows the policy to track a moving target. Algorithms like Online Gradient Descent or Follow-the-Regularized-Leader (FTRL) update weights with each new reward signal, ensuring the model continuously adapts without the computational cost of periodic full retraining.

The optimization objective that measures the difference between the cumulative reward of a theoretical optimal policy and the reward accumulated by the learning algorithm. In a non-stationary setting, the definition shifts to dynamic regret, which compares against a sequence of changing optimal actions rather than a single fixed best arm. Minimizing dynamic regret requires algorithms that can forget stale information quickly, often using a sliding window or discount factor on historical rewards.

The fundamental dilemma amplified in non-stationary environments. An agent must continuously explore to detect shifts in reward distributions, even if it has already identified a seemingly optimal action. A purely exploitative policy will miss a new, better arm that emerges over time. Strategies like Thompson Sampling naturally maintain exploration through posterior uncertainty, while epsilon-greedy requires a persistent exploration rate to avoid stagnation in a changing world.

A safe deployment pattern for non-stationary environments where a proven champion model serves the majority of live traffic while one or more challenger models receive a small fraction. This allows continuous, real-world evaluation of new algorithms against a shifting baseline. If a challenger demonstrates superior dynamic regret, it is promoted. This framework mitigates the risk of deploying an untested adaptive model that might react poorly to a sudden distribution shift.