Multiscale Non-stationary Stochastic Bandits

Qin Ding, Cho-Jui Hsieh, James SharpnackarXiv 2020 · arXiv

Introduction

Standard contextual bandit algorithms, such as LinUCB, operate under the assumption of a stationary environment where the relationship between contexts and rewards remains constant over time. However, real-world applications—ranging from news recommendations to online advertising—frequently encounter non-stationary dynamics. User preferences shift, seasonal trends emerge, and external events alter the underlying reward distributions. Failing to adapt to these changes leads to suboptimal performance and "linear regret," where the algorithm fails to converge on the optimal policy.

Problem Statement: The Challenge of Non-Stationarity

Existing approaches to non-stationary bandits generally fall into two categories: passive adaptation and active detection. Passive methods, like sliding windows (SW-LinUCB) or discounted rewards (D-LinUCB), often require prior knowledge of the environment's total variation—a parameter rarely known in practice. Active detection methods attempt to identify "changepoints" but frequently struggle with "faint" changes. If a reward shift is subtle, an algorithm might stop sampling an arm before the change is detected, missing the opportunity to re-engage when that arm becomes optimal again.

Proposed Method: Multiscale-LinUCB

This paper introduces Multiscale-LinUCB, an algorithm designed to actively detect and adapt to non-stationary environments without requiring oracle knowledge of the number of changepoints.

Multiscale Changepoint Detection

The core innovation is a multiscale detection mechanism. Rather than monitoring a single fixed window, the algorithm evaluates potential changes across multiple time scales simultaneously. It employs Ordinary Least Squares (OLS) to estimate reward parameters over various intervals and utilizes a specific test statistic to identify significant deviations.

Multiscale changepoint detection mechanism illustrating the evaluation of parameters across different time intervals.

Randomized Exploration and Parameter Resets

To address the "faint change" trap, Multiscale-LinUCB incorporates a randomized exploration strategy. A small fraction of rounds (approximately $\sqrt{\log T / T}$) is dedicated to pulling arms purely for monitoring purposes, ensuring that even under-sampled arms are checked for shifts. When a change is statistically confirmed, the algorithm resets the memory for that specific arm, allowing it to learn the new parameters from scratch.

Experimental Evaluation

The authors evaluated Multiscale-LinUCB across several synthetic scenarios, including abrupt large changes, high-dimensional settings ($p=50$), and environments with random changepoints to test robustness against model mismatch.

Results and Discussion

The theoretical analysis demonstrates that Multiscale-LinUCB achieves a regret bound of $\tilde{O}(D\sqrt{S_{max}})$, where $S_{max}$ is the length of the longest stationary period. This matches the theoretical lower bounds for this class of problems.

Empirically, Multiscale-LinUCB consistently outperforms baseline algorithms. As shown in the regret curves, the proposed method adapts more rapidly to changes than D-LinUCB or SW-LinUCB.

Cumulative regret comparison showing Multiscale-LinUCB achieving significantly lower regret than standard and non-stationary baselines.

A key insight is the algorithm's independence from the total variation parameter $D$. While competitors often require $D$ as a hyperparameter to function optimally, Multiscale-LinUCB achieves near-optimal performance using only a detection threshold constant. Furthermore, the multiscale approach proves robust in high-dimensional settings, where competitors often experience significant regret spikes following changepoints.

Conclusion

Multiscale-LinUCB represents a significant advancement in non-stationary bandit literature. By combining multiscale detection with strategic exploration, it effectively balances sensitivity to subtle changes with robustness against false alarms. Future work includes optimizing the computational overhead of the OLS-based detection and validating the approach on large-scale real-world datasets.

Summary updated

Abstract

Classic contextual bandit algorithms for linear models, such as LinUCB, assume that the reward distribution for an arm is modeled by a stationary linear regression. When the linear regression model is non-stationary over time, the regret of LinUCB can scale linearly with time. In this paper, we propose a novel multiscale changepoint detection method for the non-stationary linear bandit problems, called Multiscale-LinUCB, which actively adapts to the changing environment. We also provide theoretical analysis of regret bound for Multiscale-LinUCB algorithm. Experimental results show that our proposed Multiscale-LinUCB algorithm outperforms other state-of-the-art algorithms in non-stationary contextual environments.
BibTeX
@misc{ding2020multiscale,
  author = {Qin Ding and Cho-Jui Hsieh and James Sharpnack},
  title = {{Multiscale Non-stationary Stochastic Bandits}},
  year = {2020},
  eprint = {2002.05289},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2002.05289},
}
Figure