Abstract
Non-stationary parametric bandits have attracted much attention recently. There are three principled ways to deal with non-stationarity, including sliding-window, weighted, and restart strategies. As many non-stationary environments exhibit gradual drifting patterns, the weighted strategy is commonly adopted in real-world applications. However, previous theoretical studies show that its analysis is more involved and the algorithms are either computationally less efficient or statistically suboptimal. This paper revisits the weighted strategy for non-stationary parametric bandits. In linear bandits (LB), we discover that this undesirable feature is due to an inadequate regret analysis, which results in an overly complex algorithm design. We propose a refined analysis framework, which simplifies the derivation and importantly produces a simpler weight-based algorithm that is as efficient as window/restart-based algorithms while retaining the same regret as previous studies. Furthermore, our new framework can be used to improve regret bounds of other parametric bandits, including Generalized Linear Bandits (GLB) and Self-Concordant Bandits (SCB).
Introduction
In many real-world applications, such as recommendation systems and online advertising, the environment is inherently non-stationary. User preferences and item popularity drift over time, meaning the optimal action at one moment may become suboptimal the next. To handle this, researchers typically employ one of three strategies: sliding-window (using only recent data), restart (periodically resetting the model), or weighted (exponentially discounting older data).
While the weighted strategy is often preferred in practice for its smooth adaptation to gradual changes, its theoretical foundation has historically been problematic. Previous analyses led to algorithms that were either computationally burdensome—requiring the maintenance of multiple covariance matrices—or statistically suboptimal. This paper identifies the root cause as an "unnatural" proof technique that attempted to force weighted strategies into a sliding-window analytical framework, creating a mismatch in how parameter drift (bias) and stochastic noise (variance) were measured.
A Refined Analysis Framework
The core contribution of this work is a refined analysis framework that utilizes a consistent "local norm" to bound both bias and variance. By using the same matrix-weighted norm for both components, the mathematical derivation is significantly simplified. This theoretical breakthrough allows for the design of leaner, more efficient algorithms:
- LB-WeightUCB: A simplified algorithm for Linear Bandits that maintains only a single covariance matrix, unlike the complex multi-matrix requirements of predecessors like D-LinUCB.
- GLB-WeightUCB: Extends the framework to Generalized Linear Bandits (e.g., logistic regression), utilizing a simplified projection step previously thought to be incompatible with drifting environments.
- SCB-WeightUCB: Provides the first weighted algorithm capable of handling the "drifting" setting for the broad class of Self-Concordant Bandits.
Key Results and Theoretical Improvements
The proposed framework yields substantial improvements in dynamic regret bounds across several bandit models. For Generalized Linear Bandits, the regret bound is improved from $\tilde{O}(d^{9/10} P_T^{1/5} T^{4/5})$ to $\tilde{O}(d^{3/4} P_T^{1/4} T^{3/4})$, where $d$ is the dimension and $P_T$ represents the total variation (path length) of the parameters. This effectively closes the gap between linear and non-linear models in non-stationary settings.
Empirical Performance
Experiments on synthetic datasets, such as a 2D feature space where the optimal parameter rotates over time, demonstrate the practical advantages of the weighted approach. In environments with gradual drift, LB-WeightUCB consistently outperforms restart-based and window-based baselines in terms of cumulative regret.
Furthermore, the computational efficiency gains are significant. By reducing the complexity of the covariance updates, LB-WeightUCB is approximately 1.5x faster than D-LinUCB (4.09s vs 6.21s in benchmark tests) while maintaining superior regret performance.
Conclusion and Future Work
This research resolves long-standing inefficiencies in weighted bandit strategies by providing a more natural analytical framework. While the current algorithms require prior knowledge of the path length $P_T$ to set the optimal discount factor $\gamma$, future work will focus on developing fully adaptive weighting schemes. Additionally, exploring more refined metrics beyond path length could help distinguish between smooth gradual drifts and sudden structural shocks in the environment.
Summary updated