PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2608.14319v1cs.LGquant-ph

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.

    Source: §1 · p. 2

  • 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.

    Source: §1 · p. 2, §3.1 · p. 9

  • 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.

    Source: §1.1 · p. 2, §5 · p. 23

  • 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.

    Source: §5 · p. 23

    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.

    Source: §5 · p. 23

Abstract

from arXiv · show

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.Source: §1 · p. 2, §1.1 · p. 2
  • Ω(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.Source: §1.1 · pp. 2–3
  • 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.Source: §1.1 · p. 2, §1 · p. 2

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.Source: Lower bounds · pp. 3–4
  • 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.Source: §1 · p. 2, Lower bounds · p. 4

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.Source: §2 · p. 6

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).Source: §2 · p. 6

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].Source: §2 · p. 6

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].Source: §2 · p. 7

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.Source: §2 · p. 8

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.Source: §3 · p. 8, §3.4 · p. 14

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.Source: §3.1 · p. 8

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).Source: §3.1 · p. 9

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.Source: §3.1 · p. 9, §3.2 · p. 10
  • 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.Source: §3.1 · p. 9, §3.2 · pp. 10–11

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.Source: §3.5 · pp. 14–15

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.Source: §4 · p. 15

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)).Source: §4 · p. 15, §4.2 · pp. 16–17, §4.3 · pp. 20–21

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.Source: §4.1 · p. 15

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.Source: §4.1 · p. 16
  • 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.Source: §4.1 · p. 16

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.Source: §4.3 · pp. 22–23

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.Source: §5 · p. 23
  • 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.Source: §5 · p. 23
  • LV-G-Elim achieves regret nearly linear in d when K = poly(d), improving the prior d^2 dependence.Source: §5 · p. 23
  • The logarithmic slack between the QMAB lower and upper bounds remains open, as does optimal dimension dependence for general action sets.Source: §5 · p. 23
  • 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.Source: §5 · p. 23
  • The lower-bound construction uses K = d actions and does not rule out mild K dependence for larger fixed action sets.Source: §5 · p. 23

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

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

Loading 2608.14319v1…