Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

Xiaojin Zhang

cs.LGOct 19, 2026

Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

Authors: Xiaojin Zhang

Organizations: School of Computer Science and Technology, Huazhong University of Science and Technology, China

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.

Figures & tables

Envelope budget	Width choice	Additional cost
$Q\leq B^{2}\sqrt{AT}$	$w=B$	$O(B\sqrt{AT})$
$B^{2}\sqrt{AT}<Q<\sqrt{ABT}$	$w=(Q^{2}/(ABT))^{1/3}$	$O((AQBT)^{1/3})$
$Q\geq\sqrt{ABT}$	Ordinary restarts	$O((AQBT)^{1/3})$

Table 1: The width choice for

0<B<1

. The last column bounds the additional monitoring and clipping-bias terms;

A+\sqrt{AQ}

and

(AQBT)^{1/3}

are accounted for separately. No clipping is needed in the last row.

Source	Rate	Scope and attribution
[ WHL16 ] , Theorem 3.1	$(A^{2}W_{T}V_{0}T)^{1/3}+\sqrt{AV_{0}T}$	Supplied full-vector variance and initial-inclusive variation; prior result.
[ Ito21b ] , Theorem 3, plus restarting	$A+\sqrt{AQ}+(AQBT)^{1/3}+\sqrt{ABT}$	Supplied $Q,B$ ; direct reduction in Proposition 6.2 .
Theorem 4.1	$A+\sqrt{AQ}+(AQBT)^{1/3}+\sqrt{AT}\min\{B,\sqrt{B}\}$	Supplied $Q,B$ ; matching lower bound up to logs. The noisy refinement is for $B<1$ .

Table 2: Closest finite-arm guarantees. Upper rates suppress logarithms and the trivial horizon cap. All rows compare to the best mean arm at each round; the supplied information and budget conventions differ.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Source and version	Relevant statement	Relation to the present bounds
[ WHL16 ] , NeurIPS 2016	Equation (1), Theorems 3.1 and 4.3; original supplement	Variance–variation dynamic regret and noise-free monitoring are prior themes. Full-vector variance and initial-inclusive variation differ from $Q,B$ .
[ Ito21b ] , COLT 2021	Theorem 3, Eq. (6), and its explicit proof	The arbitrary-reference static algorithm is prior work; ordinary restarting is its direct consequence. Our added steps are calibration and clipping-bias accounting.
[ KA16 ] , NeurIPS 2016 supplement	Theorem A.1 and Appendix D	Prior-free variation tracking and a noiseless construction already exist; the deterministic problem itself is not a new formulation.
[ GM08 , GM11 ] ; [ LS20 ]	Preprint Theorem 13, Remark 15; textbook Theorem 31.2	The inverse stationary/change-regret obstruction is classical. Our matching frontier is restricted to the disclosed deterministic family.
[ WXC+25 ] , AISTATS 2025	Theorems 4.1, 5.2; Corollary 5.4; Remark 5.6	Variance-sensitive linear results include a finite-arm comparison; the stated theorem is not the same all-budget finite-arm formula.
[ QW26 ] , arXiv v2, 17 February 2026	Theorem 4	Simultaneous static/dynamic bounds use a supplied switch limit and allow a stationary $\sqrt{AT}$ scale. This differs from our small-stationary-regret constraint.

Appendix

Table 3: Models and guarantees in closely related work.

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 348 papers

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits
Aug 18, 2026Kaifei Wang, Yinyu Ye, Han ZhongMulti-Armed Bandits UCB Algorithms
Peking University · Stanford University · Shanghai Jiao Tong University
Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
Jul 26, 2026Heyang Zhao, Tianyuan Jin, Weixin Wang +3Multi-Armed Bandits
Department of Computer Science, University of California, Los Angeles · Department of Electrical and Computer Engineering, National University of Singapore · Department of Biostatistics & Bioinformatics, Duke University +2
Trading off rewards and errors in multi-armed bandits
May 1, 2026Akram Erraqabi, Alessandro Lazaric, Michal Valko +2Multi-Armed Bandits Exploration-Exploitation Tradeoff
Inria SequeL · CMU · EnLearn

Aug 18, 2026J/K move · Enter open · S save

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

Kaifei Wang, Yinyu Ye, Han Zhong

Peking University · Stanford University · Shanghai Jiao Tong University

Multi-Armed Bandits UCB Algorithms

Open paper AskPDF arXiv

Multi-armed bandit algorithms are evaluated by regret, yet comparable regret can coexist with different allocations across independent runs. We study the trade-off between worst-case regret

\mathcal{R}_{K,T}

and instability

\mathcal S_{K,T}

, defined as the largest standard deviation of a terminal pull count, for

K

arms and

T

rounds. We prove the finite-time lower bound

\mathcal R_{K,T}\mathcal S_{K,T}\ge C T^{3/2}

, where

C

is independent of

K

and

T

, under a finite-time regret condition and without the regularity assumptions imposed in the prior asymptotic analysis. We also introduce Stabilized Lower-Envelope UCB (\textup{SLE-UCB}), a new tunable algorithm combining a running lower-envelope index with a decreasing pull-count stabilizer. \textup{SLE-UCB} satisfies

\mathcal R_{K,T}\mathcal S_{K,T}=O(T^{3/2}\log K)

, with an implicit constant independent of

K

and

T

, matching the lower bound exactly in

T

and within a logarithmic factor in

K

. To prove the instability bound, we develop a new offline top-prefix representation that removes path dependence from online decisions. Together with single-reward perturbations and the Efron--Stein inequality, this representation controls pull-count variance. Thus, regret and instability depend reciprocally on

K

, while their product has no polynomial dependence on

K

. These results resolve the open question raised in the literature concerning the sharp arm-dependent regret--instability frontier.

Abstract

Multi-Armed Bandits

Explore similar work

Toward the Optimal Regret-Instability Trade-off in Multi-Armed Bandits

Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set

Trading off rewards and errors in multi-armed bandits