- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies stochastic multi-armed and linear bandits with coherent quantum access to each arm's reward distribution. Actions are selected classically, and both forward and inverse reward-oracle calls count toward the horizon and incur the selected action's regret. Under , where , the paper proves a multi-armed regret bound of with a lower bound matching the leading polynomial dependence. For linear bandits, it improves the leading dimension dependence to for finite action sets and for compact action sets. The compact case requires additional design and optimization oracles.
The algorithms use phased elimination with existing quantum mean estimators. The improvements come from allocating a shared query budget across active arms and, in the linear case, using experimental designs to estimate rewards more efficiently. The lower bounds reduce learning to distinguishing distributions that differ on rare outcomes, while allowing the learner to stop querying adaptively. The paper also considers central-moment assumptions. The results are supported mainly by proofs, with synthetic experiments that emulate the estimators.
Critical strengths
- The multi-armed upper and lower bounds match in their leading polynomial dependence on the number of arms and the horizon. This gives a sharper characterization than the previous guarantees and is the strongest reason for my positive assessment. The lower bound also allows adaptive query allocation and stopping, which is important for the stated optimality claim.
- The linear-bandit results make useful use of the action geometry. Allocating queries according to an experimental design and controlling the resulting estimation errors leads to a concrete improvement in dimension dependence. The paper therefore contributes more than an application of a faster scalar estimator to an existing bandit algorithm.
Critical weaknesses
I do not see a weakness that warrants rejection. My main reservation is that the linear-bandit bounds still leave gaps in dimension dependence, especially for compact action sets. The lower-bound construction based on informative rays does not fully capture the difficulty introduced by the geometry of the action set.
The technical novelty is also somewhat limited: the scalar estimators, elimination approach, and experimental-design tools are established, with the new work mainly in how queries are allocated and how the errors are analyzed. The experiments emulate the estimators and illustrate the consequences of the query bounds; they do not validate a quantum implementation. These limitations keep me from giving a stronger recommendation, but they do not undermine the main results.
Questions for authors
None essential to my recommendation. The remaining dimension gaps are a natural direction for future work, but I do not think they need to be resolved for this paper to be accepted.
We thank the reviewer for the careful summary and positive assessment. Three changes address the stated reservations.
Dimension gaps and the ray construction. The new Remark 4.2 in the main text states the gaps and their sources: d(1−α)/(2(1+α)) for finite sets, which vanishes at α=1 for poly(d) actions, and d for compact sets. For compact sets, the concurrent work of Liu et al. (2026b, arXiv:2611.15237) proves a matching Ω(d3/2) lower bound for bounded rewards, so our compact-action bound is optimal in d at α=1 and the gap remains only for α<1. The new Proposition C.8 shows that a hypercube instance, the type that separates linear from multi-armed bandits classically (Tajdini et al. 2025), yields only the d-armed rate under the stopped-query hybrid argument, because the hybrid bound is linear in the per-query perturbation whereas the classical KL divergence is quadratic. This explains why the ray construction does not capture the geometry and why a different construction, such as the spherical cap of Liu et al. (2026b), is needed.
Technical novelty. A new "Positioning" paragraph in Section 1, together with Remark 4.4, states which components are inherited and which are new.
We also position our bounds against the bounded-reward results at α=1 (Table 1), which our algorithms recover as a special case.
Experiments. Section 5 now states that the experiments compare certified query-complexity rates under emulated estimators and make no claim about a hardware implementation.