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

Aug 18, 2026

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

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.

Kaifei Wang, Yinyu Ye, Han Zhong

Peking University · Stanford University · Shanghai Jiao Tong University

Multi-Armed Bandits UCB Algorithms

Ask PDF

Jul 26, 2026

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

Recent years have witnessed increasing interests in tackling heteroscedastic noise in bandits and reinforcement learning. In these works, the cumulative variance of the noise

Λ= \sum_{t=1}^T σ_t^2

, where

σ_t^2

is the variance of the noise at round

t

, is used to characterize the statistical complexity of the problem, yielding simple regret bounds of order

\tilde{\cal{O}}(d \sqrt{Λ/ T^2})

for

d

-dimensional linear bandits with heteroscedastic noise. However, with a closer look,

Λ

remains the same order even if the noise is close to zero at half of the rounds, which indicates that the

Λ

-dependence is not optimal. In this paper, we revisit the stochastic linear bandit problem with heteroscedastic noise, where the action set is prefixed throughout the learning process. We propose a novel variance-adaptive algorithm VAEE (Variance-Aware Exploration with Elimination) for large action set, which actively explores actions that maximizes the information gain among a candidate set of actions that are not eliminated. With the active-exploration strategy, we show that VAEE achieves a simple regret with a nearly harmonic-mean dependent rate. For finitely many actions, we propose a variance-aware variant of G-optimal design based exploration, which achieves a simple regret with sharper dependence on

d

. We also establish a nearly matching lower bound for the fixed action set setting indicating that harmonic-mean dependent rate is unavoidable. To the best of our knowledge, this is the first work that breaks the

\sqrtΛ

barrier for stochastic linear bandits with heteroscedastic noise.

Heyang Zhao, Tianyuan Jin, Weixin Wang +3

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

Multi-Armed Bandits

Ask PDF

May 1, 2026

Trading off rewards and errors in multi-armed bandits

In multi-armed bandits, the most-explored arms are the most informative, while reward maximization typically pulls only the best arm. We study the tradeoff between identifying arm means accurately and accumulating reward, and present an algorithm with regret guarantees that interpolates between the two objectives. We provide both upper and lower bounds and validate empirically.

Akram Erraqabi, Alessandro Lazaric, Michal Valko +2

Inria SequeL · CMU · EnLearn

Multi-Armed Bandits Exploration-Exploitation Tradeoff Best-Arm Identification Regret Minimization Bandit Learning

Ask PDF

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