Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Bandits

Zhuoyue Chen; Kechao Cai

cs.LGMar 19, 2026

Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Bandits

Authors: Zhuoyue Chen, Kechao Cai

Organizations: School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen, China

Abstract

Quantum multi-armed bandits (MAB) and stochastic linear bandits (SLB) have recently attracted significant attention, as their quantum counterparts can achieve quadratic speedups over classical MAB and SLB. However, most existing quantum MAB algorithms assume ideal quantum Monte Carlo (QMC) procedures on noise-free circuits, overlooking the impact of noise in current noisy intermediate-scale quantum (NISQ) devices. In this paper, we study a noise-robust QMC algorithm that improves estimation accuracy when querying quantum reward oracles. Building on this estimator, we propose noise-robust QMAB and QSLB algorithms that enhance performance in noisy environments while preserving the advantage over classical methods. Experiments show that our noise-robust approach improves QMAB estimation accuracy and reduces regret under several quantum noise models.

Figures & tables

Panel of Figure 1 — Fig. 1: Regret comparison results in noiseless settings: (a) and (b) compare QUCB and UCB under two reward gap settings, and (c) compares QLinUCB and LinUCB.

Panel of Figure 2 — Fig. 2: Cumulative regret of QUCB variants under four noise settings: exponential decoherence, readout, depolarizing, and amplitude damping.

Panel of Figure 3 — Fig. 3: Cumulative regret of QLinUCB variants under four noise settings: exponential decoherence, readout, depolarizing, and amplitude damping.

Robust Multi-Armed Bandits

Robust multi-armed bandits develop strategies that limit regret when rewards are heavy-tailed, corrupted, adversarial, or changing over time.

See all 20 papers

Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
Aug 14, 2026Maoli Liu, Zhuohua Li, John C. S. LuiMulti-Armed Bandits Information-Theoretic Lower Bounds
The Chinese University of Hong Kong · Xidian University
Replay-buffer engineering for noise-aware quantum circuit optimization
Apr 23, 2026Akash Kundu, Sebastian FeldQuantum Architecture Search Reinforcement Learning
Delft University of Technology, Delft, The Netherlands · Quantum Computing Division, QuTech, The Netherlands
Stochastic Multi-Armed Bandits with Limited Control Variates
Mar 2, 2026Arun Verma, Manjesh Kumar Hanawal, Arun RajkumarMulti-Armed Bandits UCB Algorithms
Singapore-MIT Alliance for Research and Technology Centre · Department of IEOR, Indian Institute of Technology Bombay · Department of DSAI, Indian Institute of Technology Madras

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

Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

Maoli Liu, Zhuohua Li, John C. S. Lui

The Chinese University of Hong Kong · Xidian University

Multi-Armed Bandits Information-Theoretic Lower Bounds

Open paper AskPDF arXiv

We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB), where the learner queries each arm or action through a quantum reward oracle or its inverse. Prior work gives algorithms over horizon

T

with regret

O(K\log T)

for QMAB with

K

arms and

O(d^2\operatorname{polylog} T)

for

d

-dimensional QLB. This leaves open the optimal dependence on

K

and

T

and whether the dependence on

d

can be further improved. In this work, we prove the first tight minimax regret bound of

Θ(K\log(1+T/K))

for QMAB and the first lower bound of

Ω(d\log(1+T/d))

for finite-action QLB, ruling out regret independent of

T

. Our lower bounds rely on a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. The matching QMAB upper bound is obtained using a tail bound for the Quantum Monte Carlo (QMC) estimator. For finite-action QLB, we propose a phased elimination algorithm that combines a low-bias low-variance quantum mean estimator with a small-support

G

-optimal design through a query allocation matched to the design weights. When the action set has size

\operatorname{poly}(d)

, its regret is nearly linear in

d

and matches our lower bound up to polylogarithmic factors.

Abstract

Robust Multi-Armed Bandits

Explore similar work

Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

Replay-buffer engineering for noise-aware quantum circuit optimization

Stochastic Multi-Armed Bandits with Limited Control Variates