Weighted Linear Bandits for Non-Stationary Environments

Yoan Russac, Claire Vernade, Olivier Cappé

This paper presents a robust approach to one of the most persistent challenges in online machine learning: maintaining model accuracy when the underlying environment is constantly changing.

The Challenge of Non-Stationarity

In the standard "stochastic linear bandit" setting, an agent chooses actions (represented by context vectors) to maximize rewards, assuming the relationship between context and reward—defined by a parameter vector $\theta$—is fixed.

However, in real-world applications like web recommendations, user preferences are rarely static. A news article that was popular yesterday might be irrelevant today. Most existing algorithms either assume the world is stationary or rely on "sliding windows" that require storing a massive history of past interactions. Others use change-point detection, which works for sudden shocks but often fails to track "slowly-varying" environments where preferences drift gradually over time.

D-LinUCB: Discounted Linear Upper Confidence Bound

To address this, the authors introduce D-LinUCB, an adaptive linear bandit algorithm that uses exponential discounting to smoothly "forget" obsolete data. The core idea is to use Weighted Least Squares (WLS) where older observations are given exponentially less weight.

Key technical components include:

  • Exponential Discounting: Weights are defined as $w_s = \gamma^{-s}$, where $\gamma \in (0, 1)$ is the discount factor. This allows the model to prioritize recent data without a hard cutoff.
  • Novel Deviation Inequalities: The authors provide a new mathematical proof for the concentration of weighted least-squares estimators. This extends existing bounds to cases where the weights and actions depend on past outcomes.
  • Recursive Implementation: Unlike sliding-window methods, D-LinUCB can be updated at each step using only the current observation and the previous state of the model, making it highly memory-efficient for real-time systems.
  • Dynamic Regret Analysis: The paper analyzes performance using a "variation budget" ($B_T$), which quantifies how much the underlying parameter $\theta$ changes over time. D-LinUCB achieves an optimal dynamic regret bound of $O(d^{2/3} B_T^{1/3} T^{2/3})$, matching known lower bounds for this problem class.

Experimental Validation

The researchers evaluated D-LinUCB using both synthetic simulations and real-world data.

Synthetic 2D Environments

The algorithm was tested against two distinct types of non-stationarity:

  1. Abrupt Changes: The parameter $\theta$ jumps between four distinct points in the unit ball.
  2. Slow Variations: The parameter $\theta$ rotates continuously along a unit circle.
Performance of D-LinUCB in abrupt (left) and slowly varying (right) environments.

As shown in the synthetic experiments, D-LinUCB remains robust to different types of non-stationarity. In the "slowly-varying" test, D-LinUCB significantly outperformed algorithms based on change-point detection (like dLinUCB), which struggled to identify the gradual drift and suffered from high regret.

Real-World Data: Criteo Live Traffic

The authors also tested a high-dimensional dataset ($d=50$) containing 30 days of user interactions with web banners. They simulated non-stationarity by artificially "flipping" 60% of the model's coordinates at a specific time step. D-LinUCB and its sliding-window counterpart (SW-LinUCB) adapted to the coordinate flip much faster than the standard LinUCB.

Key Insights and Trade-offs

  • The "Forgetful" Advantage: By smoothly discounting the past, D-LinUCB handles various non-stationarities without needing to explicitly "detect" a change.
  • Unified Theory: The use of the variation budget $B_T$ allows the authors to provide a single theoretical guarantee that covers both "switching" environments (sudden jumps) and "drifting" environments (gradual change).
  • The "No Free Lunch" Trade-off: During long stationary periods, adaptive algorithms like D-LinUCB perform slightly worse than standard LinUCB because they ignore older, still-valid data. However, they recover significantly faster once a change occurs.

Limitations and Future Work

The primary limitation of D-LinUCB is hyperparameter sensitivity. The optimal discount factor $\gamma$ depends on the variation budget $B_T$ and the time horizon $T$, which are rarely known in advance. Tuning $\gamma$ without this knowledge remains an open research challenge. Future directions include exploring "horizon-independent" tuning methods that could allow the algorithm to adapt its discount rate automatically based on the observed rate of change in the environment.

Summary updated

Abstract

We consider a stochastic linear bandit model in which the available actions correspond to arbitrary context vectors whose associated rewards follow a non-stationary linear regression model. In this setting, the unknown regression parameter is allowed to vary in time. To address this problem, we propose D-LinUCB, a novel optimistic algorithm based on discounted linear regression, where exponential weights are used to smoothly forget the past. This involves studying the deviations of the sequential weighted least-squares estimator under generic assumptions. As a by-product, we obtain novel deviation results that can be used beyond non-stationary environments. We provide theoretical guarantees on the behavior of D-LinUCB in both slowly-varying and abruptly-changing environments. We obtain an upper bound on the dynamic regret that is of order d B<em>T^{1/3}T^{2/3}, where B</em>T is a measure of non-stationarity (d and T being, respectively, dimension and horizon). This rate is known to be optimal. We also illustrate the empirical performance of D-LinUCB and compare it with recently proposed alternatives in simulated environments.
BibTeX
@inproceedings{russac2019weighted,
  author = {Yoan Russac and Claire Vernade and Olivier Cappé},
  title = {{Weighted Linear Bandits for Non-Stationary Environments}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=vGZ4zdR54m},
}
Figure