New regret bounds improve tracking in changing multi-armed bandits
Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs
Machine Learning
Summary
When trying to choose the best option in a changing environment, low randomness in rewards helps but doesn't solve the problem of keeping track of changes. The authors analyze how two key limitations—how much rewards can vary and how much they can change over time—together affect how well algorithms can learn. They find new formulas that describe the best possible trade-offs between exploration and adaptation under these constraints, including what happens when changes are very small. They also identify unavoidable costs when adjusting strategies to stay competitive over time.
What this means in practice
- •For online recommender systems teams: Use new regret bounds to better tune algorithms adapting to item popularity shifts with varying reward uncertainty and change rates.
- •For real-time financial trading teams: Incorporate variance-aware adaptation costs to improve switching strategies in markets with changing volatility and underlying asset returns.
Authors
Xiaojin Zhang
Abstract
Low reward variance reduces estimation cost, but does not eliminate monitoring of arms that may improve while unobserved. We refine the variance--variation tradeoff and characterize how both costs depend on supplied variance and variation budgets in bounded, non-stationary multi-armed bandits. Let $A$ be the number of arms, $T$ the horizon, $B$ a bound on consecutive mean variation excluding the initial vector, and $Q$ a bound on the sum of the largest per-round reward variances. For every admissible pair $Q,B$, the minimax expected dynamic regret is, within a single logarithmic factor, \[ \min\{T,\;A+\sqrt{AQ}+(AQBT)^{1/3} +\sqrt{AT}\min\{B,\sqrt B\}\}. \] The deterministic boundary $Q=0$ is characterized without logarithms. For small positive budgets, a safe calibration phase identifies a common interval containing all future means of surviving arms. Clipping observations to a wider interval reduces the cost of restarting a prior hybrid static-regret algorithm; an original-mean analytical reference controls its residuals without charging the variation of clipped means. Balancing clipping bias and monitoring closes the small-budget noisy regime. Fixed oblivious constructions give the matching lower bound. We also quantify adaptation costs: on a disclosed deterministic one-improvement family, a stationary-regret budget has a matching worst-case change-regret frontier, including a finite improvement pulse. This implies an $Ω((T/A)^{1/4})$ loss when one policy competes with all supplied-budget deterministic oracle rates. The budget-free low-noise scheduling problem remains separate.