Weighted Linear Bandits for Non-Stationary Environments

Yoan Russac, Claire Vernade, Olivier Cappé

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^{2/3} B_T^{1/3} T^{2/3}$, where $B_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.

Introduction

In dynamic fields such as online recommendation and digital advertising, the underlying data distributions are rarely static. User preferences drift over time, and external events can cause abrupt shifts in content relevance. Standard stochastic linear bandit models, which assume a stationary environment, often fail to adapt to these changes. This paper introduces D-LinUCB, an algorithm designed to handle non-stationarity by employing a discounted least-squares approach to prioritize recent observations over obsolete history.

The Non-Stationary Linear Bandit Problem

The authors address the Stochastic Linear Bandit problem where the hidden preference vector $\theta_t$ evolves over time. In this setting, an agent selects an action $a_t$ from a set of context vectors and receives a reward $r_t = \langle a_t, \theta_t \rangle + \eta_t$. The goal is to minimize dynamic regret against a sequence of optimal actions.

Existing approaches typically rely on sliding windows or change-point detection. Sliding windows require significant memory to store past interactions, while change-point detection algorithms often struggle with slow, continuous drifts that do not trigger a discrete "reset" of the model.

The D-LinUCB Algorithm

The core innovation is the Discounted Linear Upper Confidence Bound (D-LinUCB) algorithm. Instead of a hard window cutoff, D-LinUCB utilizes Weighted Least Squares with an exponential discount factor $\gamma \in (0, 1)$. This allows the model to smoothly "forget" older data, which acts as noise or "poison" in a changing environment.

The D-LinUCB algorithm effectively tracks the true parameter $\theta$ as it rotates continuously (slow drift) in a 2D environment.

Key technical features include:

  • Recursive Implementation: The discounted estimator can be updated incrementally, requiring only the current state to be stored rather than the full history.
  • Novel Concentration Inequalities: The authors developed a new maximal deviation inequality for sequential weighted least-squares to construct a confidence ellipsoid that contains the moving parameter with high probability.
  • Scale Invariance: The regularization parameter is designed to ensure stability regardless of the weight scaling.

Theoretical and Empirical Results

The performance of D-LinUCB is analyzed using a "variation budget" $B_T = \sum_{t=1}^{T-1} \|\theta_{t+1} - \theta_t\|_2$. The authors prove that D-LinUCB achieves a dynamic regret of $\tilde{O}(d^{2/3} B_T^{1/3} T^{2/3})$, matching the theoretical lower bound for this problem class.

Empirical evaluations were conducted on synthetic environments and real-world Criteo display advertising data. In scenarios with abrupt changes, D-LinUCB demonstrated significantly faster recovery than stationary baselines.

Regret comparison in an environment with abrupt changes. D-LinUCB and SW-LinUCB significantly outperform the stationary LinUCB, which fails to adapt after the environment shifts.

Key Insights

  • Robustness to Drift: D-LinUCB tracks moving targets smoothly, whereas change-point detection methods (like dLinUCB) may fail to trigger during gradual shifts.
  • Efficiency: D-LinUCB matches the performance of Sliding Window (SW-LinUCB) methods while offering superior memory efficiency due to its recursive nature.
  • Adaptability: On the Criteo dataset, D-LinUCB quickly reconciled new data after a simulated "preference flip," while standard LinUCB remained biased by its now-obsolete history.

Conclusion

D-LinUCB provides a theoretically optimal and computationally efficient solution for linear bandits in non-stationary worlds. While the optimal discount factor $\gamma$ currently depends on the variation budget $B_T$, future work aims to develop parameter-free versions of the algorithm that can adapt the discount factor automatically.

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^{2/3} B\_T^{1/3}T^{2/3}, where B\_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