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

Heyang Zhao; Tianyuan Jin; Weixin Wang; Vincent Y. F. Tan; Pan Xu; Quanquan Gu

cs.LGJul 26, 2026

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

Authors: Heyang Zhao, Tianyuan Jin, Weixin Wang, Vincent Y. F. Tan, Pan Xu, Quanquan Gu

Organizations: 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 · Department of Computer Science, Duke University · Department of Electrical and Computer Engineering, Duke University

Abstract

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 \emph{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 \texttt{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 \texttt{VAEE} achieves a \emph{simple regret} with a nearly \emph{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 \emph{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.

Explore similar work

May 11, 2026cs.LG

Learning to Sparsify Stochastic Linear Bandits

This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a

\tilde{\mathcal{O}}(d\sqrt{T})

regret, where

d

is the dimension of the action vector and

T

is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a

\tilde{\mathcal{O}}(d \sqrt{T})

α

-regret; for general compact sets lacking strong convexity, we establish a

\tilde{\mathcal{O}}(d T^{2/3})

α

-regret, where

α

pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments including an application to recommendation system.

Zhengmiao Wang, Ming Chi, Zhi-Wei Liu +2

Generalized Linear Bandit O(T^Β)$ Simultaneous Regret Sparsity Sparse Rewards

Ask PDF

Feb 11, 2026cs.LG

A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

We consider the problem of heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions, which subsumes heteroskedastic linear bandits and logistic/Poisson bandits, in the presence of adversarial corruptions. We propose HCW-GLB-OMD, which consists of two components: an online mirror descent (OMD)-based estimator and Hessian-based confidence weights to achieve corruption robustness. This is computationally efficient in that it only requires

{O}(1)

space and time complexity per iteration. Under the self-concordance assumption on the link function, we show a regret bound of

\tilde{O}\left( d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d (g_{\max} + κ) C \right)

, where

\dotμ_{t,\star}

is the slope of

μ

around the optimal arm at time

t

g(τ_t)

's are potentially exogenously time-varying dispersions (e.g.,

g(τ_t) = σ_t^2

for heteroskedastic linear bandits,

g(τ_t) = 1

for Bernoulli and Poisson),

g_{\max} = \max_{t \in [T]} g(τ_t)

is the maximum dispersion, and

C \geq 0

is the total corruption budget of the adversary. We complement this with a lower bound of

\tildeΩ(d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d C)

, unifying previous problem-specific lower bounds. Thus, our algorithm achieves, up to a

κ

-factor in the corruption term, instance-wise minimax optimality simultaneously across various instances of heteroskedastic GLBs with adversarial corruptions.

Sanghwa Kim, Junghyun Lee, Se-Young Yun

Mirror Descent Adversarial Corruption Adaptive Adversary

Ask PDF

Sep 14, 2026cs.LG

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let

d

be the dimension,

K

be the menu size, and

T

the time horizon. For

2\le K\le d

, we prove an upper bound

\widetilde O(K^{1/4}\sqrt{dT})

. When

T\ge d^2

, we further prove a lower bound

Ω(K^{1/4}\sqrt{dT})

. Thus, for

T\ge d^2

and

2\le K\le d

, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on

K

is optimal. Compared with the previous

\widetilde O(\sqrt{dKT})

bound, our upper bound improves the dependence on

K

by a factor of

K^{1/4}

. For

K\ge d

, we prove an upper bound

\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)

and a lower bound

Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)

. Here,

\widetilde O_{d,T}

omits logarithmic factors only in

d

and

T

. In particular, for polynomially large

K\ge d

, the upper and lower bounds both scale as

d^{3/4}\sqrt T

up to logarithmic factors, improving the standard

\widetilde O(d\sqrt T)

rate by a factor of

d^{1/4}

. As

K

grows further, the regret smoothly recovers the

d\sqrt T

scale once

\log K

reaches order

d

Tianyuan Jin

Topic pending

Ask PDF