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

CardsList
  1. Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms

    Aug 14, 2026Maoli Liu, Zhuohua Li, John C. S. LuiMulti-Armed BanditsInformation-Theoretic Lower Bounds

  2. Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

    May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed BanditsBatched Bandits

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

    Oct 15, 2026Yen-Huan Li, Wei-Fu TsengQuantum State TomographyInformation-Theoretic Lower Bounds