Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
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(Klog T) for QMAB with K arms and O(d2polylog 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 Θ(Klog(1+T/K)) for QMAB and the first lower bound of Ω(dlog(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 poly(d), its regret is nearly linear in d and matches our lower bound up to polylogarithmic factors.
Related
- Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
- Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
- Tight bounds for hybrid quantum-classical query algorithms
- Quantum Algorithms for Molecular Response Functions: Resolvent Kernels, Time-Domain Sampling, Query Lower Bounds with Matched Single-Point Calibers, and a Six-Route Comparison
- Quantum algorithms for optimal control: large-scale finite-horizon linear-quadratic regulation
BibTeX
@misc{liu2026quantum,
title = {{Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms}},
author = {Maoli Liu and Zhuohua Li and John C. S. Lui},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.14319},
eprint = {2608.14319},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.14319},
}
RIS
TY - UNPB
TI - Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
AU - Maoli Liu
AU - Zhuohua Li
AU - John C. S. Lui
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2608.14319
UR - https://arxiv.org/abs/2608.14319
AB - 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(Klog T) for QMAB with K arms and O(d^2polylog 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 Θ(Klog(1+T/K)) for QMAB and the first lower bound of Ω(dlog(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 poly(d), its regret is nearly linear in d and matches our lower bound up to polylogarithmic factors.
ER -