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

arXiv:2608.14319 · cs.LG, quant-ph · Submitted 2026-08-14 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Quantum Multi-Armed Bandits and Linear Bandits".

Tom: The gist The authors prove minimax lower bounds for quantum multi-armed bandits and linear bandits, resolving prior questions regarding T-independent regret and improving dimension dependence in finite-action settings.

Jane: First, who's behind it and why it matters.

Paper summary: Tom: So to recap, this paper focuses on quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB) within a model where you query each arm or action through a quantum reward oracle. The authors are challenging prior results that suggested better performance guarantees for these problems.

Jane: Specifically, they prove the first minimax lower bounds of (K (T/K)) for QMAB and (d (T/d)) for finite-action QLB. This directly addresses whether regret independent of T can ever be achieved in these settings.

Lu: The entire argument hinges on establishing a high-confidence single-arm quantum testing lower bound, which they prove using the polynomial method and a Remez-type inequality for trigonometric polynomials.

Meng: That testing lower bound is what they use to build the bandit reduction, showing that this difficulty in distinguishing means translates into a hard limit on how well you can manage regret over time T.

Lalam: Essentially, they are using the structure of quantum testing—how hard it is to tell a fixed reward mean apart from an interval of possibilities—to set a floor for the regret.

Tom: The implication is that for these specific quantum bandit setups, worst-case performance must scale logarithmically with T, which was previously questioned in earlier work by Wan et al. two thousand twenty-three <ref:2608.14319#pg1>.

Jane: It also tackles the second open question from Wan et al.: does the dimension dependence improve? They show that for general action sets, the optimal dimension dependence is still unresolved right now.

Lu: The paper provides upper bounds from previous work, like O(d squared polylog T) for general QLB, and they compare those to their new lower bounds to see where the gap lies <ref:2608.14319#pg1>.

Meng: It’s important because it clarifies where the current algorithmic performance is hitting a wall compared to the theoretical minimum required by these lower bounds.

Lalam: From a cultural perspective, this suggests that when we apply quantum techniques, we have to accept a certain level of uncertainty that scales with time unless we find entirely new ways around these quantum testing constraints.

Conclusion: Tom: The work by Maoli Liu, Zhuohua Li, and John C.S. Lui on "Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms" really crystallizes the current understanding of the limits for these problems.

Jane: It moves the conversation from just finding algorithms to rigorously defining what is achievable in terms of performance guarantees against an adversary who knows your strategy.

Lu: The core contribution is establishing those (K (T/K)) and (d (T/d)) lower bounds, which are hard limits for quantum multi-armed bandits and linear bandits respectively.

Meng: For me, the practical implication is that when we design systems using these quantum reward oracles, we should treat those logarithmic factors as a baseline requirement for our performance expectations over a long run T.

Lalam: It tells us that even with advanced quantum estimation techniques, the inherent structure of these problems imposes a necessary scaling factor related to the number of arms or actions and the total time.

Tom: So, in simple terms, they are saying that you can’t avoid these logarithmic growth rates in regret; it’s a fundamental constraint imposed by how quantum testing works.

Jane: They also show that while algorithms exist, the dimension dependence for general action sets is still an open area where better scaling might be possible down the road.

Lu: This work provides a very solid foundation, setting clear benchmarks that future research needs to beat or at least understand the landscape of.

Meng: It’s less about a single solution and more about understanding the landscape of what's fundamentally possible in this quantum domain right now.

Chinese University of Hong Kong · Xidian University

cs.LG, quant-ph

Submitted: 2026-08-14

Updated: 2026-10-08

Importance score: 88/100

The gist: The gist The authors prove minimax lower bounds for quantum multi-armed bandits and linear bandits, resolving prior questions regarding T-independent regret and improving dimension dependence in

Key concepts

Quantum Multi-Armed Bandits (QMAB): This is the problem of choosing the best action from a set of quantum choices over time. The paper focuses on proving how much regret (the difference between optimal and actual reward) must occur in this setting, establishing a fundamental lower bound on performance.
Quantum Linear Bandits (QLB): This is a variation where the reward depends linearly on the chosen action. The authors analyze finite-action versions, proving that the minimum possible regret scales with d (the number of actions) and log(T/d), setting a benchmark for performance.
Minimax Lower Bound: This is a theoretical result in decision-making that sets the absolute best possible performance guarantee achievable by any algorithm. The paper proves that no algorithm can perform better than these specific logarithmic bounds for QMAB and QLB.
Regret to Testing Reduction: The proof technique involves transforming the bandit problem into a point-versus-interval testing problem. This allows the authors to use established lower bounds from quantum testing theory to derive the required logarithmic regret bounds for the bandit scenario.

Terminology

Regret — 122× in this paper · explained in 3 episodes
Accuracy — 11× in this paper · explained in 1 episode
Quantum Monte Carlo — 4× in this paper
Minimax Regret — 2× in this paper · explained in 2 episodes
Reconstruction Error — 2× in this paper · explained in 2 episodes
Bayesian Optimization — 1× in this paper · explained in 3 episodes
Benchmark — 1× in this paper · explained in 2 episodes
Contextual Bandits — 1× in this paper · explained in 3 episodes
Core — 1× in this paper · explained in 2 episodes
Entanglement — 1× in this paper · explained in 3 episodes
Generative Model — 1× in this paper · explained in 2 episodes
Hilbert Space — 1× in this paper · explained in 2 episodes
Query Complexity — 1× in this paper · explained in 2 episodes
Regularization — 1× in this paper · explained in 3 episodes

Summary

The gist The authors prove minimax lower bounds for quantum multi-armed bandits and linear bandits, resolving prior questions regarding T-independent regret and improving dimension dependence in finite-action settings.

Lower Bounds

The paper establishes a minimax lower bound of omega(K log(T /K)) for quantum multi-armed bandits (QMAB) and omega(d log(T /d)) for finite-action quantum linear bandits (QLB). For general action sets, the optimal dimension dependence is unresolved. The upper bounds are O(d squared polylog T) from Wan et al. [23,page1] and O(d 3/2 polylog T) from a linear-kernel specialization of the analysis of Hikima et al. [24,page1]. For finite action sets with K superpolynomial in d, the nearly linear bound of LV-G-Elim carries an extra log K factor, while the QMC variant removes this dependence at the cost of a d 3/2 dimension factor. Whether the two advantages can be combined, for instance by improving the log K dependence toward the classical √log K, remains open. On the lower bound side, our construction uses only K = d actions and does not rule out a mild K dependence for larger fixed action sets, which would have to remain consistent with the QMC upper bound. Beyond these gaps, our upper bound may extend to the bounded-variance assumption via the estimator replacement sketched in Remark 19.

How it works

The paper establishes a minimax lower bound of omega(K log(T /K)) for quantum multi-armed bandits (QMAB) and omega(d log(T /d)) for finite-action quantum linear bandits (QLB) <ref:13,page14. The first result shows that worst-case regret must grow logarithmically with T, ruling out T-independent regret <ref:2,page2. This lower bound is derived from a reduction from bandit regret to a point-versus-interval testing problem, which is then lower bounded by the polynomial method and a Remez-type inequality for trigonometric polynomials <ref:10,page4. The second result establishes the finite-action QLB lower bound of omega(d log(T /d)) with only d actions <ref:13,page14.

Lower Bounds

Algorithms and Upper Bounds

The paper presents the LV-G-Elim algorithm for finite-action QLB, which achieves a regret nearly linear in d when K = poly(d) <ref:18,page20. This algorithm uses a small-support approximate G-optimal design coupled with the low-bias low-variance quantum mean estimator from Lemma 6 <ref:17,page17. The upper bound for LV-G-Elim is O(d log T log K log T δ log(dT) log log(dT)) for any confidence parameter δ <ref:20,page21. A QMC variant, QMC-G-Elim, is also presented with a high-probability regret of O(d 3/2 log T log d) <ref:23,page19.

Technical Details

The lower bounds rely on the hardness of distinguishing a fixed reward mean from an interval of alternatives using quantum testing <ref:10,page4. The proof involves showing that any quantum test distinguishing two fixed unitary oracles requires omega(log(1/δ)) queries <ref:10,page9. The bandit-to-testing reduction converts the policy's worst-case regret MT into a family of single-arm tests with error probabilities O(MT /T) <ref:12,page13.

Design and Estimation

The design phase computes a small-support design (Sl, πl, Ml) for the current active set Al using Lemma 15 <ref:15,page24. The estimation step uses LVQME to obtain estimates µbl(x), which controls bias and variance through its low-bias low-variance properties <ref:6,page7.

Improvements for AI systems

This system can achieve near-linear regret in finite-action linear bandits when action set size is polynomial in dimension, as shown by LV-G-Elim achieving regret nearly linear in d under bounded rewards when K = poly(d).
The system can utilize a quantum mean estimation technique that controls the bias and the variance using the low-bias low-variance estimator from Cornelissen and Hamoudi [2023], which allows for aggregate error control through variance rather than worst-case absolute error, removing the remaining √d factor.
The system can perform high-probability estimation of all action means simultaneously by using the LVQMEDesignEstimate, which provides an estimate with probability at least 1 − δ, µb(x) − µ(x) ⩽ ϵ for all x ∈ A, by running it independently several times and taking medians.
The system can employ a phased elimination algorithm, LV-G-Elim, which achieves a high-probability regret bound of R(T) = O d log T log K log T δ log(dT) log log(dT) when using the low-variance estimator with confidence parameter 1/T.
For general action sets, the system can achieve an upper bound of O d3⁄2 polylog T regret by running QMC-G-Elim, which trades worst-case absolute error for a dimension factor of d3⁄2 polylog T.