Source-linked AI summary
Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
Maoli Liu, Zhuohua Li, John C. S. Lui
TL;DR
Quantum bandit theory lacked minimax evidence on whether logarithmic horizon dependence is unavoidable and whether finite-action linear-bandit dimension dependence could improve. The paper proves matching-scale lower bounds through interval testing and develops design-based elimination, obtaining nearly linear dimension dependence for polynomial-size action sets. Remaining gaps include logarithmic slack for QMAB and unresolved optimal dependence for general or very large action sets.
Problem
Prior quantum algorithms achieve O(K log T) QMAB regret and O(d^2 polylog T) QLB regret, leaving the necessity of horizon logarithms and the finite-action dimension dependence open.
Method
The paper combines a polynomial-method quantum testing lower bound for interval alternatives with bandit reductions and a design-based elimination algorithm using low-bias low-variance estimation.
Results
Ω(K log(T/K)) and Ω(d log(T/d)) lower bounds are proved, while LV-G-Elim achieves nearly linear regret in d when K = poly(d), improving the prior d^2 dependence.
Takeaways & Limitations
Worst-case quantum bandit regret must grow logarithmically with T, and finite-action QLB admits substantially better dimension dependence than the prior general-action guarantee.
Takeaways & Limitations
The logarithmic slack for QMAB, optimal dimension dependence for general action sets, and the combination of LV-G-Elim’s advantages for superpolynomial K remain open.
Abstract
from arXiv · showhide
We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB) in the model of Wan et al. [2023], 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(K\log T)$ for QMAB with $K$ arms and $O(d^2\operatorname{polylog} T)$ for $d$-dimensional QLB. This leaves open whether the $K\log T$ scale is unavoidable and whether the $d^2$ dependence can be improved. We prove the first minimax lower bounds of $Ω(K\log(T/K))$ for QMAB and $Ω(d\log(T/d))$ for finite-action QLB, resolving the question raised by Wan et al. [2023] of whether regret independent of $T$ is achievable. At the heart of our argument is a high-confidence single-arm quantum testing lower bound for distinguishing a fixed reward mean from an interval of alternatives, proved by the polynomial method and a Remez-type inequality for trigonometric polynomials. A bandit-to-testing reduction then lifts it to the QMAB lower bound, while a linear embedding gives the finite-action QLB lower bound. Complementing the lower bounds, we give a design-based elimination algorithm for finite-action QLB. When the action set has size $\operatorname{poly}(d)$, its regret is linear in $d$, improving the prior $d^2$ dependence and matching our lower bound up to polylogarithmic factors. The algorithm couples a low-bias low-variance quantum mean estimator with a small-support $G$-optimal design through a query allocation matched to the design weights. The design-based elimination reduces the dimension dependence from $d^2$ to $d^{3/2}$ when using Quantum Monte Carlo estimates. The low-variance estimator then makes reconstruction error aggregate through variance rather than worst-case absolute error, removing the remaining $\sqrt d$ factor.
1 Introduction
The paper establishes logarithmic-in-horizon quantum regret lower bounds and improves finite-action quantum linear-bandit dimension dependence using testing reductions and design-based elimination.
- Our Results: Ω(K log(T/K)) is a minimax lower bound for quantum multi-armed bandits, nearly matching the prior O(K log T) upper bound.This rules out regret independent of T.
- Our Results: Ω(d log(T/d)) holds for finite-action quantum linear bandits with only d actions.The lower bound uses a linear realization of the hard multi-armed-bandit instances.
- Our Results: O(d log(KT) · polylog(d, T)) is achieved by LV-G-Elim for finite-action quantum linear bandits.When K = poly(d), this is nearly linear in d and improves the prior d^2 dependence.
- Technical Overview: The lower bounds reduce regret minimization to high-confidence testing of a fixed mean against an interval of alternatives.The testing lower bound uses the polynomial method and a Remez-type inequality for trigonometric polynomials.
- Technical Overview: A small-support approximate G-optimal design and query allocation matched to design weights underpin the improved upper bound.Quantum mean estimation changes support size from an additive overhead to a leading regret term.
2 Preliminaries
The preliminaries define the quantum reward-oracle interaction for multi-armed and linear bandits and introduce the mean-estimation primitives used by the algorithms.
- Quantum Bandit Model: A quantum reward oracle encodes an action’s reward distribution, and the learner may apply the oracle or its inverse at most once per round.Arbitrary distribution-independent unitaries and measurements are allowed between rounds.
- Quantum Multi-Armed Bandits: QMAB regret sums the gaps between the selected arms and an optimal arm over the horizon.The gap is defined as Δ_i = μ(i⋆) − μ(i).
- Quantum Linear Bandits: QLB uses a known action set A ⊆ R^d and unknown parameter θ, with mean reward μ(x) = x⊤θ.The model assumes bounded action and parameter norms and means in [0, 1].
- Quantum Mean Estimation: QMC estimates reward means with high-probability accuracy, while LVQME controls estimator bias and variance.LVQME’s analysis uses bias and variance guarantees rather than requiring estimates to remain in [0, 1].
- Oracle Access: The model does not provide controlled black-box access to unknown reward oracles, but the presented estimators do not require it.The lower bounds allow controlled queries and therefore remain valid for the restricted model.
3 Lower Bounds
The lower-bound proof reduces quantum bandit regret to high-confidence point-versus-interval testing, then uses polynomial arguments and embeddings to obtain logarithmic minimax regret lower bounds.
- QMAB lower bound: The proof establishes a QMAB minimax lower bound of Ω(K log(T/K)) for canonical Bernoulli-oracle instances.Theorem 8 applies for K ≥ 2 and T ≥ CK.
- Hard instances: The hard family uses a baseline arm with mean 1/2, candidate arms with mean 5/12, and alternatives elevating one candidate into [7/12, 2/3].The optimal arm changes between the baseline and each alternative, while all relevant gaps remain at least 1/12.
- Bandit-to-testing reduction: Low regret converts each candidate arm into a test distinguishing its baseline mean from an interval of elevated means.Selecting an arm more than T/2 times determines the test outcome; a wrong decision implies Ω(T) regret and yields error probability O(M_T/T).
- Single-arm testing: A fixed-query quantum test has acceptance probability represented by a trigonometric polynomial whose degree is O(q).The parameterization p = sin^2 θ enables a Remez-type inequality to relate uniform smallness on an interval to polynomial degree.
- Single-arm testing: The Remez-type argument forces Ω(log(1/δ)) queries for point-versus-interval testing with both error probabilities at most δ.A truncation argument extends the fixed-query bound to tests with random expected query counts.
- Finite-action QLB: Embedding the hard QMAB family into a finite action set of d linear-bandit actions yields an Ω(d log(T/d)) finite-action QLB lower bound.The construction uses K = d actions and preserves the induced action-mean pattern and oracle-query behavior.
4 Finite-Action Quantum Linear Bandits
Finite-action quantum linear bandits admit a design-based elimination algorithm that nearly matches the dimension dependence of the lower bound when K = poly(d). Its gains come from small-support G-optimal designs and low-bias, low-variance quantum estimation.
- Results: Ω(d log(T/d)) is the finite-action quantum linear bandit lower bound, while LV-G-Elim achieves nearly linear dependence on d when K = poly(d).The algorithm matches the lower bound up to polylogarithmic factors and improves the prior d^2 dependence.
- Low-variance elimination: LV-G-Elim uses query allocations matched to design weights and low-bias, low-variance estimation so reconstruction errors aggregate through variance rather than worst-case absolute error.The resulting expected regret bound is O(d log T log(KT) log(dT) log log(dT)).
- Motivation: Quantum mean estimation makes support size a leading regret term because each support action requires a separate estimator call with a minimum query cost.This differs from the classical ϵ^-2 accounting, where support size contributes only a lower-order rounding overhead.
- Design: Small-support approximate G-optimal designs use O(r) support points and have G-value O(r), where r is the active set's span dimension.The support size keeps queried actions proportional to the dimension while controlling extrapolation error.
- Design: The design expresses every active action's mean as a weighted combination of support means, with G-value controlling the resulting error amplification.Prediction weights are induced by the design information matrix and support distribution.
- Quantum estimation: QMC-based design estimation has total query complexity O(r^3/2 ϵ^-1 log(r/δ)) and yields a d^3/2 regret dependence.The d^3/2 factor arises from worst-case absolute-error propagation through prediction weights.
5 Conclusion
The paper establishes the first regret lower bounds for quantum bandits and presents LV-G-Elim as a nearly linear-dimensional algorithm for polynomial-size finite action sets, while identifying remaining gaps.
- 5 Conclusion: Ω(K log(T/K)) and Ω(d log(T/d)) are the first regret lower bounds for quantum multi-armed and linear bandits, respectively.The linear-bandit lower bound uses only d actions.
- 5 Conclusion: The Ω(K log(T/K)) lower bound nearly matches Wan et al.’s O(K log T) upper bound and rules out T-independent regret.
- 5 Conclusion: LV-G-Elim achieves regret nearly linear in d when K = poly(d), improving the prior d^2 dependence.
- 5 Conclusion: The logarithmic slack between the QMAB lower and upper bounds remains open, as does optimal dimension dependence for general action sets.
- 5 Conclusion: For superpolynomial K, LV-G-Elim has an extra log K factor, while its QMC variant removes that dependence at the cost of a d^3/2 dimension factor.
- 5 Conclusion: The lower-bound construction uses K = d actions and does not rule out mild K dependence for larger fixed action sets.
A Small-Support Approximate G-Optimal Designs
This appendix constructs a small-support approximate G-optimal design by reducing the problem to effective dimension, solving a continuous relaxation, and rounding it to a sparse discrete design.
- A Small-Support Approximate G-Optimal Designs: A distribution with bounded G-value exists by the Kiefer–Wolfowitz equivalence theorem, and scaling it gives a feasible mass-m continuous design.
- A Small-Support Approximate G-Optimal Designs: The construction first restricts the action set to its span and maps it into R^r using an orthonormal basis.The transformed set spans R^r, enabling full-rank design construction.
- A Small-Support Approximate G-Optimal Designs: Entropic mirror descent computes a fractional design of total mass m with G-value at most 3r/m.
- A Small-Support Approximate G-Optimal Designs: The multiplicity reduction and rounding theorem convert the fractional design into a discrete design with support at most m, while preserving positive definiteness and a constant-factor G-bound.
- A Small-Support Approximate G-Optimal Designs: The resulting prediction weights satisfy x^T M^+ x ≤ C_G r for actions in the span.
- A Small-Support Approximate G-Optimal Designs: The continuous optimization and rounding procedure runs in polynomial time, with rounding time eO(|X| r^3).
B An O(d3/2 polylog T) Bound for General Action Sets
Specializing Hikima et al.’s analysis to the linear kernel yields an O(d^3/2 polylog T) regret bound for general action sets, driven by tighter confidence widths and determinant-controlled stage counts.
- B An O(d3/2 polylog T) Bound for General Action Sets: O(d^3/2 polylog T) regret follows for general, possibly infinite, action sets under the stated bounded linear-bandit assumptions.
- B An O(d3/2 polylog T) Bound for General Action Sets: The algorithm uses weighted ridge regression and stage-wise action blocks with QMC estimates obtained from the selected action’s oracle and inverse.
- B An O(d3/2 polylog T) Bound for General Action Sets: The confidence bound uses width 1 + √s instead of Wan et al.’s 1 + √d s, producing the improvement from d^2 to d^3/2.
- B An O(d3/2 polylog T) Bound for General Action Sets: With probability at least 1 − δ, the prediction error at every stage and action is bounded by β_s ||x||_{V_s^-1}, where β_s = 1 + √s.
- B An O(d3/2 polylog T) Bound for General Action Sets: At most m* = ⌈d log_2(1 + T^2/d)⌉ stages are completed, with at most m* + 1 initiated before the horizon ends.
- B An O(d3/2 polylog T) Bound for General Action Sets: The stage-count bound follows because each completed stage doubles det(V_s), while the horizon limits the cumulative stage lengths.