Regret Bounds for Quantum Linear Bandits

Maoli Liu, Zhuohua Li, John C. S. LuiarXiv 2026 · arXiv

This paper, "Regret Bounds for Quantum Linear Bandits," provides a significant theoretical leap in our understanding of how quantum computers can—and cannot—speed up sequential decision-making. By establishing a new minimax lower bound and proposing optimized algorithms, the authors resolve a long-standing question about the fundamental limits of quantum learning in high-dimensional spaces.

TL;DR

The authors prove that for general action sets, quantum linear bandits fundamentally require a $d^{3/2}$ dependence on dimensionality in their regret bounds, matching existing upper bounds and resolving a gap in prior theory. They also introduce two new algorithms, Soft-G-Elim and QG-Elim, which achieve tighter regret bounds for finite action sets by utilizing a novel, low-bias quantum mean estimator.

What Problem Does This Paper Address?

In a stochastic linear bandit problem, a learner repeatedly chooses an action $x$ from a set $\mathcal{A} \subset \mathbb{R}^d$ and receives a reward. The goal is to maximize the cumulative reward (or minimize "regret") without knowing the underlying parameter $\theta$ that determines the reward mean ($x^\top\theta$).

Quantum linear bandits extend this by allowing the learner to query a "quantum reward oracle." Classically, estimating a mean to accuracy $\epsilon$ requires $O(1/\epsilon^2)$ samples. Quantumly, this can be done in $O(1/\epsilon)$ queries—a quadratic speedup.

However, a mystery remained:

  1. For general action sets: Existing quantum algorithms showed a regret of $O(d^{3/2})$, but the known lower bound was only $\Omega(d)$. Was the $d^{3/2}$ factor an algorithmic inefficiency or a fundamental physical limit?
  2. For finite action sets: While bounds were known, they contained complex logarithmic factors involving the number of actions ($K$) and the time horizon ($T$). Can these be tightened?

Methods

The paper attacks these problems from two sides:

1. Proving the Lower Bound

To prove that $d^{3/2}$ is necessary, the authors constructed "hard instances" using a spherical cap as the action set. They developed a posterior Fisher information bound specifically for adaptive quantum queries with quantum memory. By treating each selected action as an estimate of the optimal direction, they used a matrix Cramér–Rao argument to show that any learner must incur a certain amount of regret to gain enough information to find the optimal action.

2. Designing New Algorithms

The authors introduced SoftQME, a quantum mean estimator that provides small bias and "controlled tails" (similar to sub-Gaussian behavior) within a deterministic query budget. They then built two algorithms around it:

  • Soft-G-Elim: Uses SoftQME alongside a G-optimal experimental design to estimate rewards for all surviving actions in phases.
  • QG-Elim: An adaptive algorithm that chooses between the Soft-G-Elim approach and a Quantum Monte Carlo (QMC) approach, picking whichever has a smaller query budget for the current phase.

Datasets

Not discussed in the paper. As a theoretical work in computational learning theory, the paper focuses on mathematical proofs and algorithmic analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Dimensionality Tax: The jump from a linear dependence on $d$ (classical) to $d^{3/2}$ (quantum) in the lower bound is the "aha moment." It reveals that while quantum queries provide a speedup in time ($T$), the geometry of high-dimensional space imposes a steeper cost when using quantum states to probe multiple directions simultaneously.
  • Tail Control is Crucial: Standard quantum mean estimation can suffer from "heavy tails" or significant bias. The creation of SoftQME is a key technical contribution that allows the authors to apply concentration inequalities (like Hoeffding's) more effectively in the bandit setting.
  • Information vs. Regret: The paper successfully formalizes the trade-off between the information a quantum state can retain about the optimal parameter $\theta$ and the regret incurred by the actions taken to acquire that state.

Key Results

The paper's primary contributions are summarized in the comparison table below:

Table 1: Regret bounds for quantum linear bandits with bounded rewards.
  • General Action Sets: The authors established a minimax lower bound of $\Omega(d^{3/2} \log(1 + T/d^{3/2}))$. This matches the best-known upper bounds in terms of $d$, proving they are optimal.
  • Finite Action Sets: QG-Elim achieves an expected regret of $O(d \log T \log(dT) \min\{\sqrt{\log(KT)}, \sqrt{d}\})$. This significantly reduces the logarithmic overhead compared to previous state-of-the-art results.

Limitations and Future Work

  • Logarithmic Gaps: While the polynomial dependence on $d$ is now settled for general sets, there remains a small gap in the logarithmic factors between the upper and lower bounds.
  • K-Dependence in Lower Bounds: The current lower bound construction uses only $d$ actions. A more complex construction that explicitly incorporates $K$ (the size of the action set) would be needed to prove if the $\sqrt{\log(KT)}$ factor in the new algorithms is truly optimal.
  • Algorithmic Extensions: The authors suggest that the properties of SoftQME (small bias and controlled tails) could be useful in other bandit settings, such as kernelized or contextual bandits, where quantum speedups are sought.

Summary updated

Abstract

We study $d$-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(d^{3/2}\operatorname{polylog}(T))$ over $T$ rounds. Prior work established a lower bound of $Ω(d\log(1+T/d))$, leaving open whether the $d^{3/2}$ dependence in the upper bound is necessary. We resolve this question by proving a minimax lower bound of $Ω(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 $K$, 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(d\log T\log(dT)\sqrt{\log(KT)})$, reducing the $\log(KT)\log\log(dT)$ factor in the previous regret bound to $\sqrt{\log(KT)}$. QG-Elim further reduces this factor to $\min\{\sqrt{\log(KT)},\sqrt d\}$.
BibTeX
@misc{liu2026regret,
  author = {Maoli Liu and Zhuohua Li and John C. S. Lui},
  title = {{Regret Bounds for Quantum Linear Bandits}},
  year = {2026},
  eprint = {2611.15237},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.15237},
}
Figure