- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies quantum algorithms for multi-armed bandits whose arms are ranked by lower-tail conditional value-at-risk (CVaR). Its main technical contribution is a distribution-uniform CVaR -additive estimator with query complexity , together with an lower bound. The estimator combines approximate quantile localization with amplitude-aware estimation of the Rockafellar–Uryasev objective, without requiring a density assumption. The scalar estimation bounds match up to logarithmic factors. The paper then uses this estimator in successive-elimination and optimistic bandit algorithms, obtaining best-arm identification complexity and high-probability, query-charged regret . The best-arm identification bounds remain separated by up to a factor. Here is the number of arms.
Critical strengths
- The strongest contribution is the matching dependence on and , up to logarithmic factors. Importantly, the upper bound does not assume that the quantile is known or that the reward distribution is continuous.
- The paper establishes that the estimator can be substituted into the bandit schemes without relying on linearity of CVaR. The resulting inverse-gap query cost produces the stated cancellation of polynomial gap dependence in query-charged regret. Although this composition is not the main technical novelty, it connects the estimation result to concrete learning guarantees rather than leaving it as an isolated subroutine.
Critical weaknesses
The technical innovation seems not enough. The algorithm heavily depends on VTAA by Ambinis 2010.
Questions for authors
- Which precise condition of the cited VTAA by Ambainis 2010 framework is not satisfied after deferring measurements, retaining the computation history, and padding each fixed-accuracy estimator call to its worst-case query budget? In particular, why is a non-adaptive estimator necessary rather than a coherent implementation of the adaptive estimator?
- What establishes that replacing the omitted measurement-distribution tail with uniformly random grid outcomes cannot increase the measured success rate? Without such an argument, can the authors quantify the resulting simulation error and revise the claim of sampling from the exact measurement distribution?
2 comments
Part II
Q1. Which VTAA condition fails after deferring measurements, retaining history and padding to the worst-case budget? Why is a non-adaptive estimator necessary? No condition fails, and a non-adaptive estimator is not necessary. We withdraw the claim, and the revision proves the opposite.
VTAA as used by Wang et al. (their Theorem 7) needs a variable-time algorithm in the sense of their Definition 1: a product of unitaries, each controlled on the earlier stop flags. Their gapped amplitude estimation (Corollary 2) leaves arbitrary states beside the flag, so garbage never has to be uncomputed. Algorithm 2 with the three modifications the reviewer lists, plus a threshold on its final estimate, has this interface (new Lemma 8):
- deferred measurement keeps each phase register as a quantum control;
- the history (medians, test outcomes, dyadic bisection endpoints) is computed reversibly and retained;
- finished branches idle, so every branch uses the worst-case query count;
- the final estimate is thresholded into the flag. Measuring the history would reproduce the classical run, so Lemma 2 bounds the amplitude on a wrong flag. Substituting this test for gapped amplitude estimation gives (Theorem 9), matching Theorem 7 up to polylogarithmic factors in the worst case over gap profiles. Section 6 is rewritten, and Appendix H checks each use of the subroutine in their analysis. Adaptivity is harmless because only the flag is used.
Q2. The sampler. Nothing established that claim, and it was wrong. Every outcome outside the enumerated window was a failure, so replacing it by a uniform grid outcome could only turn a failure into a success. The direction is the opposite of what we wrote, and the effect per amplitude-estimation run is bounded by the discarded mass, at most . "Exact" was therefore not accurate for that sampler.
The revised simulator enumerates all outcomes of amplitude estimation and samples from the full distribution, so it is exact up to floating point (largest normalization error ). The Algorithm 1 results are unchanged: 200 of 200 runs met the guarantee, with worst error and medians between and . The same exact sampler drives all new experiments, which now cover Algorithms 2, 3 and 4 (Section 7, Figure 4, Appendix I):
- Algorithm 2 was within in all 14,400 runs on twelve distributions, including atoms and point masses;
- Algorithm 3 was correct in all 320 identification runs;
- the regret of Algorithm 4 grew 3.6-fold while the gap shrank 64-fold, against 106-fold for the classical estimator run through the same rounds.
Part I
We thank the reviewer for the review. Both questions were well aimed. The first exposed an incorrect claim, and correcting it led to a new result. Both questions overlap with points from the other reviewers, so the changes that answer them are in purple in the revised PDF: Section 6 and Appendix H for Q1, and the sampler description in Section 7 and Appendix I for Q2.
W. Technical innovation and dependence on VTAA. First a factual point: no algorithm in the submitted paper uses variable-time amplitude amplification (VTAA). Algorithms 1 to 4 run with K separate oracles under classical control, and VTAA appeared only in Section 6, which discussed why we had not obtained a H rate. In the revision VTAA is used in exactly one place, the new Theorem 9, and there only as a black box through Wang et al. (2021).
The contributions are: