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

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

cs.LGAug 14, 2026

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

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

Organizations: The Chinese University of Hong Kong · Xidian University

Abstract

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.

Figures & tables

	Bound	MAB	Linear, general $\mathcal{A}$	Linear, finite $\mathcal{A}$
Classical	UB	$O(\sqrt{KT})$	$O(d\sqrt{T}\log T)$	$O(\sqrt{dT\log K})$
Classical	LB	$\Omega(\sqrt{KT})$	$\Omega(d\sqrt{T})$	$\Omega(\sqrt{dT})$
Quantum	UB ( Wan et al., 2023 )	$O(K\log T)$	$O(d^{2}\,\mathrm{polylog}\,T)$	$O(d^{2}\,\mathrm{polylog}\,T)$
	UB (Appendix C ) †	—	$O(d^{3/2}\operatorname{polylog}T)$	$O(d^{3/2}\operatorname{polylog}T)$
	UB (Sections 4 – 5 )	${O}(K\log(1+T/K))$	—	$O(d\log T\log(KT))\,^{\ddagger}$
	LB (Section 3 )	$\Omega(K\log(1+T/K))$	$\Omega(d\log(1+T/d))$	$\Omega(d\log(1+T/d))$

Table 1: Regret bounds for multi-armed bandits and linear bandits.

Explore similar work

May 29, 2026stat.ML

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size

B

, and during each batch the learner sends

B

requested arm pulls to an agent, who then observes the corresponding

B

rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that

Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\})

regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of

\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}})

. We develop two phased-elimination algorithms based on

G

-optimal designs and 1-bit mean estimation. The first achieves

\widetilde{O}(dB + d\sqrt{T})

regret, matching the lower bound up to logarithmic factors when

\lvert \mathcal{A} \rvert = \exp(Ω(d))

, and the second incorporates a safe-arm identification and warm-start procedure to obtain

\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert})

regret, which is near-optimal in broad scaling regimes of

(\lvert \mathcal{A} \rvert, B, d, T)

. Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as

Θ(\sqrt{T})

Ivan Lau, Daniel McMorrow, Kevin Jamieson +1

National University of Singapore · University of Washington

Multi-Armed Bandits Minimax Regret Communication Complexity Low-Bit Quantization

Ask PDF

Sep 29, 2026stat.ML

Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity

We study multi-armed bandits (MAB) with multiple optimal arms, motivated by the fact that many practical decision making problems admit multiple correct answers. For

K

-armed bandits with

A

optimal arms, we first provide a sharper analysis of previous sub-sampling algorithms (De Heide et al., 2021; Zhu and Nowak, 2020), establishing a

\tilde{O}\Big(\frac{K-A}{\sqrt{KA}}\sqrt{T} \Big)

minimax regret, where

T

is the total number of interactions and

\tilde O(\cdot)

drops all constant and logarithmic factors, improving the previous

\tilde{O}(\sqrt{KT/A})

regret. We then provide a matching lower bound up to logarithmic factors, indicating that our established rate is nearly minimax-optimal. We further show that the knowledge of

A

up to

\tilde{O}(1)

factors is necessary to achieve near-optimal regret, as near-optimal algorithms for one number of optimal arms must incur substantially larger regret than optimal regret for a smaller number. Overall, our results provide a comprehensive minimax characterization of

K

-armed bandits with

A

over the entire range of

1 \leq A \leq K-1

Kaixuan Ji, Qiwei Di, Qingyue Zhao +2

Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Multi-Armed Bandits Minimax Regret Regret Minimization

Ask PDF

May 8, 2026cs.LG

Multi-Armed Bandits With Best-Action Queries

We study \emph{multi-armed bandits} (MABs) augmented with \emph{best-action queries}, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the \emph{full-feedback} model, where the learner observes the rewards of all arms after each round. They show that, in both \emph{stochastic} and \emph{adversarial} environments,

k

best-action queries reduce the optimal

\widetilde{\mathcal{O}}(\sqrt{T})

regret to

\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T}\})

. Whether this improvement extends to the more realistic \emph{bandit-feedback} model -- where the learner observes only the reward of the played arm -- was left as an open problem. We fully resolve this question. When rewards are stochastic but correlated among arms, we show that the full-feedback result does not carry over: any algorithm must incur regret at least

Ω(\sqrt{T-k})

. This lower bound directly extends to adversarial environments. On the positive side, we show that

\widetilde{\mathcal{O}}(\min\{T/k,\sqrt{T-k}\})

regret is still achievable when rewards are stochastic and i.i.d., and establish a matching lower bound, up to logarithmic factors. Together, these results provide a complete characterization of the benefits of \emph{best-action queries} in the \emph{bandit-feedback} model.

Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1

Politecnico di Milano

Multi-Armed Bandits Adversarial Bandits

Ask PDF