cs.LGNov 11, 2026

Regret Bounds for Quantum Linear Bandits

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

Organizations: The Chinese University of Hong Kong · Xidian University

Abstract

We study dd-dimensional quantum linear bandits with bounded rewards, where the learner selects an action and queries its quantum reward oracle or its inverse in each round. For general action sets, existing algorithms achieve regret O(d3/2polylog⁡(T))O(d^{3/2}\operatorname{polylog}(T)) over TT rounds. Prior work established a lower bound of Ω(dlog⁡(1+T/d))Ω(d\log(1+T/d)), leaving open whether the d3/2d^{3/2} dependence in the upper bound is necessary. We resolve this question by proving a minimax lower bound of Ω(d3/2log⁡(1+T/d3/2))Ω(d^{3/2}\log(1+T/d^{3/2})). To prove this result, we construct a family of hard instances in which the reward gap of each action is proportional to its squared distance from the optimal action. We establish a posterior Fisher information bound for adaptive quantum queries with quantum memory, relating the information acquired about the optimal direction to the regret incurred. Viewing each selected action as an estimate of the optimal direction, we use a matrix Cramér--Rao argument to derive a lower bound on expected regret. When the action set is fixed and has size KK, we propose two phased elimination algorithms, Soft-G-Elim and QG-Elim. We adapt quantum phase estimation to construct SoftQME, a mean estimator with small bias and controlled tails. Soft-G-Elim estimates the mean reward of every surviving action from independent SoftQME outputs on the support of an experimental design. Controlling the bias and fluctuations of these estimates yields regret O(dlog⁡Tlog⁡(dT)log⁡(KT))O(d\log T\log(dT)\sqrt{\log(KT)}), reducing the log⁡(KT)log⁡log⁡(dT)\log(KT)\log\log(dT) factor in the previous regret bound to log⁡(KT)\sqrt{\log(KT)}. QG-Elim further reduces this factor to min⁡{log⁡(KT),d}\min\{\sqrt{\log(KT)},\sqrt d\}.

Figures & tables

Explore similar work

Aug 14, 2026

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

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 TT with regret O(Klog⁡T)O(K\log T) for QMAB with KK arms and O(d2polylog⁡T)O(d^2\operatorname{polylog} T) for dd-dimensional QLB. This leaves open the optimal dependence on KK and TT and whether the dependence on dd can be further improved. In this work, we prove the first tight minimax regret bound of Θ(Klog⁡(1+T/K))Θ(K\log(1+T/K)) for QMAB and the first lower bound of Ω(dlog⁡(1+T/d))Ω(d\log(1+T/d)) for finite-action QLB, ruling out regret independent of TT. 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 GG-optimal design through a query allocation matched to the design weights. When the action set has size poly⁡(d)\operatorname{poly}(d), its regret is nearly linear in dd and matches our lower bound up to polylogarithmic factors.
May 29, 2026

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 BB, and during each batch the learner sends BB requested arm pulls to an agent, who then observes the corresponding BB 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 Ω(Bmin⁡{d,log⁡∣A∣})Ω(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 Ω~(Bmin⁡{d,log⁡∣A∣}+dTmin⁡{d,log⁡∣A∣})\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 GG-optimal designs and 1-bit mean estimation. The first achieves O~(dB+dT)\widetilde{O}(dB + d\sqrt{T}) regret, matching the lower bound up to logarithmic factors when ∣A∣=exp⁡(Ω(d))\lvert \mathcal{A} \rvert = \exp(Ω(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain O~(Blog⁡∣A∣+d3/2B+dTlog⁡∣A∣)\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 (∣A∣,B,d,T)(\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 Θ(T)Θ(\sqrt{T}).
Oct 15, 2026

Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means

We study the problem of online learning of quantum states with logarithmic loss, which is a quantum generalization of online portfolio selection and has applications to quantum state tomography, the task of estimating an unknown quantum state from measurement outcomes. We first establish a regret lower bound, showing that the regret rates of Exponential Weights and the algorithm of Tseng et al. (2025) have optimal polynomial dependence on the dimension. Our analysis leads to two further results. First, our lower-bound proof leads to a quantum state tomography algorithm that is sample optimal up to polylogarithmic factors in the sample size. Second, we develop an algorithm for constructing confidence sequences for the mean of a matrix-valued random variable. A numerical experiment shows that the latter algorithm is competitive with existing methods.