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.
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.
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