Stochastic Multi-Armed Bandits with Limited Control Variates

Arun Verma; Manjesh Kumar Hanawal; Arun Rajkumar

cs.LGMar 2, 2026

Stochastic Multi-Armed Bandits with Limited Control Variates

Authors: Arun Verma, Manjesh Kumar Hanawal, Arun Rajkumar

Organizations: Singapore-MIT Alliance for Research and Technology Centre · Department of IEOR, Indian Institute of Technology Bombay · Department of DSAI, Indian Institute of Technology Madras

Abstract

Motivated by wireless networks where interference or channel state estimates provide partial insight into throughput, we study a variant of the classical stochastic multi-armed bandit problem in which the learner has limited access to auxiliary information. Recent work has shown that such auxiliary information, when available as control variates, can be used to get tighter confidence bounds, leading to lower regret. However, existing works assume that control variates are available in every round, which may not be realistic in several real-life scenarios. To address this, we propose UCB-LCV, an upper confidence bound (UCB) based algorithm that effectively combines the estimators obtained from rewards and control variates. When there is no control variate, UCB-LCV leads to a novel algorithm that we call UCB-NORMAL, outperforming its existing algorithms for the standard MAB setting with normally distributed rewards. Finally, we discuss variants of the proposed UCB-LCV that apply to general distributions and experimentally demonstrate that UCB-LCV outperforms existing bandit algorithms.

Figures & tables

Fig. 1: Variation in $\frac{\mathcal{V}_{T,N_{i}(T)}^{(2)}}{\mathcal{V}_{T,T}^{(2)}}$ with $S_{i}(T)$ .

Fig. 2: $\mathcal{V}_{T,T}^{(\alpha)}$ vs. $\log(T)$ .

Panel of Figure 3 — Fig. 3: Regret comparison of UCB-LCV with existing bandit algorithms (Fig. 3a and Fig. 3b ). Regret of UCB-LCV vs. the availability of control variate (Fig. 3c ). Regret of UCB-LCV vs. erroneous mean of control variate (Fig. 3d ). Since the confidence intervals are very small compared to the scale of the y-axis, they are not observable in the plots.

Panel of Figure 4 — Fig. 4: Regret comparison of different variants of UCB-LCV that are based on Jackknifing, Splitting, and Batching methods for MAB-LCV problems with arms having a non-Gaussian distribution of reward and associated CVs. In these experiments, UCB-LCV assumes a Gaussian distribution irrespective of the underlying true distribution.

Explore similar work

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
Replicable Bandits with UCB based Exploration
Apr 21, 2026Rohan Deb, Udaya Ghai, Karan Singh +1Multi-Armed Bandits Contextual Bandits
University of Illinois Urbana-Champaign · Amazon · Carnegie Mellon University
Truly Adapting to Adversarial Constraints in Constrained MABs
Feb 16, 2026Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni +2Constrained Optimization Adversarial Bandits
Politecnico di Milano

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

Explore similar work

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

Replicable Bandits with UCB based Exploration

Truly Adapting to Adversarial Constraints in Constrained MABs