Revisiting Weighted Strategy for Non-stationary Parametric Bandits

Jing Wang, Peng Zhao, Zhi-Hua Zhou

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). For example, we develop a simple weighted GLB algorithm with an $\widetilde{O}(k_\mu^{\frac{5}{4}} c_\mu^{-\frac{3}{4}} d^{\frac{3}{4}} P_T^{\frac{1}{4}}T^{\frac{3}{4}})$ regret, improving the $\widetilde{O}(k_\mu^{2} c_\mu^{-1}d^{\frac{9}{10}} P_T^{\frac{1}{5}}T^{\frac{4}{5}})$ bound in prior work.

Introduction

In modern recommendation systems and dynamic pricing environments, the assumption of a static environment rarely holds. User preferences and market conditions drift over time, necessitating algorithms that can adapt to non-stationarity. This is formally modeled as a non-stationary parametric bandit problem.

Researchers generally employ three strategies to handle this drift: sliding-window methods (using only recent data), restart strategies (periodically resetting the model), and weighted strategies (discounting older data using a factor $\gamma \in (0, 1)$). While weighted strategies are often preferred in practice for their ability to handle gradual drift smoothly, they have historically suffered from a theoretical "cleanup" problem. Previous analyses were often complex, leading to algorithms that were either computationally burdensome or statistically suboptimal compared to their windowed or restart-based counterparts.

The Challenge: The "Two-Norm" Complexity

The primary hurdle in previous weighted strategy analyses (such as the D-LinUCB algorithm) was an "unnatural" approach to bounding estimation errors. To control the bias introduced by parameter drift and the variance caused by noise, researchers were forced to maintain two distinct covariance matrices. This dual-matrix requirement not only increased the computational overhead but also led to a mismatch in mathematical norms, resulting in suboptimal regret bounds.

A Refined Analysis Framework

This research, presented at AISTATS 2023, introduces a refined analysis framework that unifies the treatment of bias and variance. The authors demonstrate that it is possible to use the same local norm for both components of the estimation error.

Simplified Algorithm Design

By unifying these norms, the authors propose LB-WeightUCB, a simplified algorithm for linear bandits. Unlike previous iterations, LB-WeightUCB requires maintaining only a single covariance matrix. This reduction in complexity makes the weighted strategy as computationally efficient as sliding-window or restart-based algorithms, achieving a 1.5x speedup over the previous state-of-the-art (D-LinUCB) in empirical tests.

Extensions to GLB and SCB

The framework's utility extends beyond linear models to Generalized Linear Bandits (GLB) and Self-Concordant Bandits (SCB), where rewards are non-linear functions of features. Previous weighted GLB algorithms required complex projection operations to maintain theoretical guarantees. This new framework allows for a standard, simple projection, significantly lowering the barrier to implementation for non-linear reward models.

Theoretical and Empirical Results

The refined analysis yields significant improvements in theoretical regret bounds, particularly in how they scale with the dimension ($d$) and the time horizon ($T$):

  • Drifting Linear Bandits: The regret bound was improved from $\tilde{O}(d^{7/8} P_T^{1/4} T^{3/4})$ to $\tilde{O}(d^{3/4} P_T^{1/4} T^{3/4})$.
  • Drifting GLB: The framework achieved a major jump 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})$, finally bringing the performance of weighted GLB in line with the linear case.

Empirically, the authors tested these algorithms in synthetic environments where parameters ($\theta_t$) rotated over time. The weighted strategy consistently outperformed restart-based methods in these "slowly-evolving" environments, confirming that gradual discounting is superior to abrupt resets when drift is continuous.

Discussion and Limitations

While this work provides a significant theoretical advancement, it highlights a persistent challenge in non-stationary bandits: the requirement of prior knowledge. The optimal discount factor $\gamma$ depends on the path length ($P_T$), which measures the total drift of the parameters. While meta-algorithms like "Bandits-over-Bandits" (BOB) can be used to estimate this, achieving optimal regret without any prior knowledge remains an open challenge.

Furthermore, the authors suggest that future research should explore more refined metrics for non-stationarity. The current "path length" metric may be too coarse to distinguish between a few abrupt changes and a continuous, smooth drift, suggesting that Sobolev or Holder classes might provide more nuanced insights into algorithm performance.

Summary updated

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). For example, we develop a simple weighted GLB algorithm with an $\widetilde{O}(k_\mu^{\frac{5}{4}} c_\mu^{-\frac{3}{4}} d^{\frac{3}{4}} P_T^{\frac{1}{4}}T^{\frac{3}{4}})$ regret, improving the $\widetilde{O}(k_\mu^{2} c_\mu^{-1}d^{\frac{9}{10}} P_T^{\frac{1}{5}}T^{\frac{4}{5}})$ bound in prior work, where $k_\mu$ and $c_\mu$ characterize the reward model's nonlinearity, $P_T$ measures the non-stationarity, $d$ and $T$ denote the dimension and time horizon.
BibTeX
@inproceedings{wang2023revisiting,
  author = {Jing Wang and Peng Zhao and Zhi-Hua Zhou},
  title = {{Revisiting Weighted Strategy for Non-stationary Parametric Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=pN667qrPJn},
}
Figure