acceptodds
Under review as a conference paper at ICLR 2027

Quantum Algorithms for Risk-Sensitive Bandits: Matching Upper and Lower Bounds for Quantum CVaR Estimation

Abstract

Multi-armed bandit algorithms decide which option to try next when each choice both yields an outcome and reveals information. Standard methods rank options by average reward, but finance, medicine, and safety-critical control care about lower-tail performance, average performance in the worst fraction of cases, formalized by the conditional value-at-risk. Quantum algorithms accelerate average-reward bandits, and risk-sensitive bandit theory is well developed classically, but the intersection has been empty. We give the first quantum algorithms for risk-sensitive bandits, with matching lower bounds. Our core primitive estimates conditional value-at-risk using quadratically fewer oracle queries than the analyzed classical sampling baseline, and an amplitude-aware refinement adds a further square-root advantage in the tail level by exploiting the fact that the estimated quantity is intrinsically small deep in the tail. Building on it we obtain best-arm identification that improves quadratically in the arm gap, and regret with no polynomial gap dependence. Adversary-method lower bounds show the estimator is optimal in both parameters.

Primary area:
learning theory
Keywords:
quantum algorithms, multi-armed bandits, risk-sensitive learning, conditional value-at-risk, CVaR, quantum amplitude estimation, query complexity, lower bounds, quantum adversary method, best-arm identification, regret minimization, risk measures, learning theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_PKwjOpenReview ↗
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 ε\varepsilon-additive estimator with query complexity O~(1/(αε))\widetilde O(1/(\sqrt{\alpha}\varepsilon)), together with an Ω(1/(αε))\Omega(1/(\sqrt{\alpha}\varepsilon)) 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 O~(∑i≠i⋆1/(αΔi))\widetilde O(\sum_{i\ne i^\star}1/(\sqrt{\alpha}\Delta_i)) and high-probability, query-charged regret O~(K/α)\widetilde O(K/\sqrt{\alpha}). The best-arm identification bounds remain separated by up to a K\sqrt K factor. Here KK is the number of arms.

Critical strengths
  1. The strongest contribution is the matching dependence on α\alpha and ε\varepsilon, up to logarithmic factors. Importantly, the upper bound does not assume that the quantile is known or that the reward distribution is continuous.
  2. 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
  1. 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?
  2. 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

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 KK separate oracles under classical control, and VTAA appeared only in Section 6, which discussed why we had not obtained a H\sqrt{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:

  1. An estimator with the optimal tail dependence. Lemma 2 estimates CVaR with O~(1/(αε))\tilde O(1/(\sqrt{\alpha}\varepsilon)) queries. It rests on two observations: the shortfall amplitude at the quantile is at most α\alpha with no continuity assumption, and a certified three-way bisection keeps the quantile bracketed even when FF has an atom there. Where earlier quantum CVaR analyses expose the tail level, it enters as α−1\alpha^{-1} (new Appendix J); to our knowledge α−1/2\alpha^{-1/2}, with a matching lower bound, is new. Following Reviewer 4hW6, the algorithm is now a bisection followed by a single amplitude estimate, and its cost has one logarithmic factor instead of two.
  2. Matching lower bounds. Ω(1/(αε))\Omega(1/(\sqrt{\alpha}\varepsilon)) for estimation (Theorem 6), to our knowledge the first for scalar CVaR estimation, and Ω(H/α)\Omega(\sqrt{H/\alpha}) for best-arm identification (Theorem 7). The latter needs the adversary matrix recomputed for mass-parameterized coins; that its off-diagonal entry is linear in the gap and carries α\sqrt\alpha is what makes the bound work.
  3. Bandit algorithms whose regret has no polynomial dependence on the gaps, now also in expectation (Theorem 5).
  4. Best-arm identification at the lower-bound rate (new Theorem 9). What is new there is Lemma 8, the coherent gapped CVaR test. The α\sqrt\alpha in Theorem 9 comes from Lemma 2, not from VTAA.

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 ∣γ0⟩,∣γ1⟩|\gamma_0\rangle,|\gamma_1\rangle 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 O~(H/α)\tilde O(\sqrt{H/\alpha}) (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 6.8×10−46.8\times10^{-4}. "Exact" was therefore not accurate for that sampler.

The revised simulator enumerates all MM outcomes of amplitude estimation and samples from the full distribution, so it is exact up to floating point (largest normalization error 2.4×10−102.4\times10^{-10}). The Algorithm 1 results are unchanged: 200 of 200 runs met the guarantee, with worst error 1.4×10−3ε1.4\times10^{-3}\varepsilon and medians between 5.7×10−4ε5.7\times10^{-4}\varepsilon and 7.7×10−4ε7.7\times10^{-4}\varepsilon. 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 ε\varepsilon 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.
Reviewer_4hW6OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies lower-tail conditional value-at-risk (CVaR) estimation and risk-sensitive bandits for bounded rewards, assuming coherent quantum sampling access with inverse and controlled queries. The main result is a scalar CVaR estimator with query complexity O~(1α ε),\widetilde O\left(\frac{1}{\sqrt{\alpha}\,\varepsilon}\right), where α\alpha is the tail level and ε\varepsilon is the desired accuracy. A lower bound matches this dependence up to logarithmic factors. The guarantee holds uniformly over the reward distributions considered, including those with atoms at the quantile. The authors then use the estimator in elimination and optimism algorithms, obtaining best-arm identification complexity O~(∑i≠i⋆1/(αΔi))\widetilde O(\sum_{i\ne i^\star}1/(\sqrt{\alpha}\Delta_i)) and regret O~(K/α)\widetilde O(K/\sqrt{\alpha}) when each oracle query incurs regret. The best-arm lower bound leaves a worst-case K\sqrt K gap. The evidence is mainly theoretical; the experiments simulate the baseline estimator rather than the sharper algorithm that exploits the small amplitude of the shortfall quantity.

Critical strengths
  1. The matching dependence on α\alpha and ε\varepsilon is the main reason for my positive assessment. The result applies uniformly without a density assumption and covers atoms at the quantile, making the estimation guarantee more broadly applicable.
  2. The estimation result also yields useful guarantees for risk-sensitive bandit learning. Best-arm identification requires O~(∑i≠i⋆1/(αΔi))\widetilde O(\sum_{i\ne i^\star}1/(\sqrt{\alpha}\Delta_i)) queries, while the regret bound has no polynomial dependence on the gaps and grows only polylogarithmically with the horizon. These results show how the improved estimation rate translates into learning guarantees for a nonlinear risk objective. I find this a meaningful extension beyond the scalar estimation problem.
Critical weaknesses

I am less convinced that all of the proposed search procedure is needed. After localization, the returned point appears already close enough to a maximizer of the Rockafellar--Uryasev objective that one further shortfall estimate could replace the ternary search in Phase 2. If so, the technical contribution is somewhat more limited than the algorithm's presentation suggests, although the improved estimation rate remains valuable. The gap in arm dependence also leaves the bandit results incomplete. These points limit my assessment of the contribution, but do not undermine the scalar theorem.

Questions for authors
  1. Is Phase 2 necessary? After the BAND exit, the CDF guarantee appears to imply that r0r_0 is already near-optimal for the CVaR objective, and the atom exit similarly provides a suitable LOW endpoint. Could a single amplitude estimate at the returned endpoint replace the ternary search with the same guarantee?
  2. Equation (8) appears to omit factors in the logarithm of its terminal term. Appendix E assigns the attempted next call failure probability δs,rs+1=δ/[K(rs+1)(rs+2)]\delta_{s,r_s+1}=\delta/[K(r_s+1)(r_s+2)], which gives the factor log⁡((Bs+2Js+3)K(rs+1)(rs+2)δ).\log \left(\frac{(B_s+2J_s+3)K(r_s+1)(r_s+2)}{\delta}\right). The equation and the indices used for the terminal call should be made consistent with this calculation. This correction should leave the leading O~(K/α)\widetilde O(K/\sqrt\alpha) bound unchanged. Could the authors reconcile the terminal logarithm and search indices in Equation (8) with Appendix E's use of δs,rs+1\delta_{s,r_s+1} and accuracy εrs+1\varepsilon_{r_s+1}?
2 comments

We thank the reviewer for a precise review. Both questions identified real issues, and the first has changed the central algorithm of the paper. Changes made in response to this review are in orange in the revised PDF (Section 3.2, Algorithm 2, Appendix D, the constants of Theorems 4 and 5, and Eq. (8)); the closing of the arm-dependence gap, which other reviewers also raised, is in purple (Section 6, Appendix H).

W1 and Q1. Is Phase 2 necessary? No. The reviewer's suggestion is correct, and we have adopted it with acknowledgment in Appendix D. After Phase 1, in every exit that reaches the final step, the stopping point r0r_0 satisfies

0≤CVaRα−ϕ(r0)≤3ε8,ar0≤118α.0\le \mathrm{CVaR_\alpha}-\phi(r_0)\le \tfrac{3\varepsilon}{8},\qquad a_{r_0}\le \tfrac{11}{8}\alpha .

  • After a BAND at r0r_0, F(r0)∈[α(1−ε/4),α(1+3ε/8)]F(r_0)\in[\alpha(1-\varepsilon/4),\alpha(1+3\varepsilon/8)]. Between r0r_0 and t⋆t^\star, ϕ′=1−F/α\phi'=1-F/\alpha lies in (0,ε/4](0,\varepsilon/4] if t⋆>r0t^\star>r_0 and in [−3ε/8,0][-3\varepsilon/8,0] if t⋆≤r0t^\star\le r_0.
  • After an atom exit, r0=lr_0=l with t⋆−l≤αε/4t^\star-l\le\alpha\varepsilon/4, ϕ′≤1\phi'\le 1 and al≤F(l)<αa_l\le F(l)<\alpha. One median-amplified estimate of ar0a_{r_0} with Mf=⌈14/(αε)⌉M_f=\lceil 14/(\sqrt{\alpha}\varepsilon)\rceil has error below 0.577αε<58αε0.577\alpha\varepsilon<\tfrac58\alpha\varepsilon, so −ε<C^−CVaRα<58ε-\varepsilon<\hat C-\mathrm{CVaR_\alpha}<\tfrac58\varepsilon. The revised Lemma 2 is

Q′≤1920(B+2)ln⁡((B+2)/δ)αε,Q'\le 1920(B+2)\frac{\ln((B+2)/\delta)}{\sqrt{\alpha}\varepsilon},

which replaces the factor (2R2+1)2(2R_2+1)^2 by B+2B+2. As before, the constant is checked against exact query counts over the whole admissible domain (largest prefactor required about 1855), and the updated checker is in the supplementary material. Theorems 4 and 5 change only through Lemma 2's cost: the factor (2Ji+1)2(2J_i+1)^2 becomes Bi+2B_i+2, the logarithm's argument becomes Bi+2B_i+2 (times the same failure-allocation terms), and the constants become 122880=1920⋅64122880 = 1920\cdot 64 and 76807680. Theorem 5 also gains the expected-regret bound (Eq. (9)).

The practical effect is large:

  • exact worst-case query counts fall by 34 to 57 times at the six settings we simulated, and by about 96 times at α=0.05\alpha=0.05, ε=10−4\varepsilon=10^{-4};
  • the accuracy below which the Lemma 2 bound beats the classical bound moves from 3.6×10−63.6\times10^{-6} to 1.9×10−51.9\times10^{-5} (for α\alpha from 0.25 to 0.005) to 6.5×10−46.5\times10^{-4} to 3.8×10−33.8\times10^{-3};
  • the earlier caveat that Lemma 2 beat Lemma 1 only below α≈0.022\alpha\approx 0.022 disappears, so it is removed from Figure 2. In simulation the revised Algorithm 2 met its guarantee in all 14,400 runs on twelve distributions covering every exit, including atoms at the quantile and the lower-bound instances (worst error 0.245ε0.245\varepsilon; Figure 4(a), Table 3).

W2. The gap in arm dependence leaves the bandit results incomplete. This gap is now closed. As Reviewers 1Tea and PKwj also pointed out, our claim that coherent execution of the estimator was the obstacle was wrong. Run by deferred measurement, Algorithm 2 is a gapped CVaR test with exactly the interface that Wang et al. (2021) need for variable-time amplitude amplification (new Lemma 8). Their algorithm with this test in place of gapped amplitude estimation identifies the best arm with O~(H/α)\tilde O(\sqrt{H/\alpha}) queries (new Theorem 9), matching Theorem 7 up to polylogarithmic factors in the worst case over gap profiles. Appendix H checks each use of the subroutine in their analysis. Theorem 4 remains as the result with explicit constants and classical control over arms.

On the concern that the contribution was more limited than presented: with these changes the estimator is a certified bisection followed by one amplitude estimate, matching the lower bound in both ε\varepsilon and α\alpha, and best-arm identification is tight up to logarithmic factors in the worst case. We have also removed the statements that depended on the old Phase 2.

Q2. The terminal logarithm in Eq. (8). The reviewer is right: Appendix E was correct and the theorem statement was not. With the revised constants, the terminal term of Eq. (8) is now

7680(Bs+2)ln⁡((Bs+2)K(rs+1)(rs+2)/δ)α,\frac{7680(B_s+2)\ln\big((B_s+2)K(r_s+1)(r_s+2)/\delta\big)}{\sqrt\alpha},

where BsB_s is evaluated at εrs+1\varepsilon_{r_s+1}, the accuracy of the call that does not fit, whose failure probability is δs,rs+1=δ/(K(rs+1)(rs+2))\delta_{s,r_s+1}=\delta/(K(r_s+1)(r_s+2)). This matches the display in Appendix E term by term, and the order of growth is unaffected. Theorem 5 now also states the expected-regret bound obtained with δ=1/T\delta = 1/T (Eq. (9)).

Reviewer_1TeaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies quantum estimation and bandit learning under the lower-tail conditional value-at-risk objective, CVaRα\mathrm{CVaR}_\alpha, for reward distributions supported on [0,1][0,1]. It assumes coherent access to reward distributions through quantum indexed oracles, including inverse and controlled queries. Its estimators exploit the representation of CVaR as the maximum of a concave Rockafellar–Uryasev objective over a scalar threshold, together with the amplitude-dependent error bound of standard amplitude estimation.

Algorithm 1 approximately maximizes the objective through noisy ternary search, evaluating each probe using amplitude estimation. Algorithm 2 first uses CDF-based bisection with a tolerance band to identify a search region where shortfall amplitudes are bounded by (O(\alpha)), while approximately preserving the optimal objective value. It then performs an amplitude-aware ternary search.Theorem 6 establishes a matching lower bound: even for distributions supported on {0,1}\{0,1\}, estimating CVaR to additive error ε\varepsilon requires Ω(1/(εα))\Omega(1/(\varepsilon\sqrt{\alpha})) quantum queries in the worst case. Together, these results establish a quantum query complexity of (\widetilde{\Theta}(1/(\varepsilon\sqrt{\alpha}))) for additive error (\varepsilon) in the stated parameter regime, compared with (O(\alpha^{-1}\varepsilon^{-2})) samples for the analyzed classical estimator at fixed confidence.

Combining the estimator with successive elimination and an optimism-based scheme yields best-arm identification guarantees (Theorem 4) and high-probability regret with no polynomial gap dependence (Theorem 5), under the paper’s query-based regret convention. The identification lower bound (Theorem 7) matches the dependence on (\alpha), but leaves a gap of up to order (\sqrt K). Validation consists of theoretical proofs, query-budget comparisons, and simulations of Algorithm 1 on a uniform distribution; Algorithm 2 and the bandit algorithms are not directly evaluated experimentally.

Critical strengths
  1. The paper shows a clear connection between estimation complexity and sequential decision guarantees. The paper shows how the improved estimator changes both identification complexity and regret. The cancellation between inverse-gap estimation cost and per-query regret provides a useful explanation of the resulting gap dependence. The authors also state important limitations explicitly, including the coherent-access assumption, the query-based regret convention, the remaining multi-arm gap, and the absence of practical advantage at moderate accuracy under the reported constants. These qualifications make the theoretical results easier to interpret.

  2. The paper gives matching scalar estimation bounds with explicit tail dependence and support for atomic distributions. The matching upper and lower bounds show that the CVaR estimator achieves optimal worst-case dependence on both the tail level α\alpha and the target accuracy ε\varepsilon, up to logarithmic factors, within the stated quantum oracle model. The handling of unknown quantiles without a density assumption is consequential: a straightforward quantile-estimation argument can fail near atoms or poorly conditioned quantiles. The localization argument addresses this issue directly. This result of mathcing bounds (i.e. the combination of Lemma 2 and Theorem 6) mainly drives my decision on the rating.

Critical weaknesses
  1. The claimed explanation of the remaining best-arm identification gap is insufficiently established. Section 6 and Appendix H identify coherent implementation of the CVaR estimator as the principal unresolved obstacle. However, Algorithm 2 has a bounded query budget at any prescribed accuracy. Its measurements, comparisons, medians, and branch decisions appear amenable to coherent implementation by retaining the computation history and controlling subsequent operations. The cited framework of Wang et al. explicitly uses deferred measurement and allows workspace states accompanying the decision flag. Consequently, the presence of estimation garbage does not by itself establish that the required interface is unavailable.

  2. The numerical evidence provides limited support for the paper’s main algorithmic claims. The actual stochastic experiments test Algorithm 1 on a single uniform distribution. They do not test the amplitude-aware estimator responsible for the optimal α−1/2\alpha^{-1/2} dependence, its different localization exits, or either bandit algorithm. The uniform example is also comparatively benign: the objective has a vanishing derivative at its interior maximizer, whereas atomic distributions motivate important parts of the analysis.

  3. The regret guarantee contains unresolved bookkeeping and comparison issues. Theorem 5 provides a high-probability guarantee, while comparisons with expected-regret results require accounting for the failure event. This introduces an additional (\delta T) term; choosing (\delta) of order (1/T) preserves polylogarithmic horizon dependence. These issues appear fixable, but they weaken the precision of the theorem statement and its comparison with existing results.

  4. Minor issue. Section 9 would benefit from discussing Siam, Guan, and Liu (2025), Quantum Non-Linear Bandit Optimization. This work combines quantum mean estimation with UCB-based exploration for nonlinear bandit optimization and establishes polylogarithmic regret under its stated assumptions. A brief comparison would provide broader context for the proposed bandit algorithms and clarify the distinction between nonlinear mean-reward optimization and the CVaR objective considered here.

  5. Minor issue. The classical comparison should also discuss Agrawal, Koolen, and Juneja, Optimal Best-Arm Identification Methods for Tail-Risk Measures (NeurIPS 2021), which establishes asymptotically optimal CVaR identification results. Its asymptotic regime differs from the uniform gap-and-tail scaling emphasized here, so the relationship should be explained rather than inferred from the generic elimination baseline.

Questions for authors
  1. Please provide a parameter-explicit comparison with earlier quantum CVaR estimation methods, distinguishing assumptions about quantiles, continuity, tail probability, and oracle access.

  2. What guarantee controls the change in the complete algorithm’s output distribution caused by the tail-replacement sampler? Is there a stochastic-domination argument supporting the claimed conservativeness, or should the experiment be described as approximate? Are results available for the actual Algorithm 2, particularly on distributions with atoms and cases exercising its different localization exits?

  3. which requirement of the cited variable-time amplitude amplification framework remains unsatisfied after making Algorithm 2 coherent? Please distinguish the need for a reliable threshold flag from the stronger requirement of producing a unique clean numerical estimate. Why cannot the computation history be retained and the complete unitary inverted when needed?

3 comments

We thank the reviewer for a detailed and constructive review. W1 and W2 led to the largest changes in the revision. Changes made in response to this review are in blue in the revised PDF; those addressing points that other reviewers also raised are in purple.

W1 and Q3. The explanation of the K\sqrt{K} gap. The reviewer is right that our explanation was not established; it was in fact wrong. To answer Q3 directly: no requirement of VTAA fails, a flag is enough, and retaining the history is exactly what works.

Wang et al. (2021) use gapped amplitude estimation (their Corollary 2), which maps ∣coin p⟩∣0⟩C∣0⟩P|\mathrm{coin}\ p\rangle|0\rangle_C|0\rangle_P to ∣coin p⟩(β0∣0⟩C∣γ0⟩P+β1∣1⟩C∣γ1⟩P)|\mathrm{coin}\ p\rangle(\beta_0|0\rangle_C|\gamma_0\rangle_P+\beta_1|1\rangle_C|\gamma_1\rangle_P), with β1≤a\beta_1\le a if p≥ℓ−εp\ge \ell-\varepsilon, β0≤a\beta_0\le a if p<ℓ−2εp<\ell-2\varepsilon, and arbitrary ∣γ0⟩,∣γ1⟩|\gamma_0\rangle,|\gamma_1\rangle. Their VTAA theorem (Theorem 7) requires a variable-time algorithm in the sense of their Definition 1 and places no condition on workspace. A clean estimate is never needed.

Run without measurement, Algorithm 2 provides this interface for CVaR (new Lemma 8):

  • each amplitude estimation keeps its phase register as a quantum control (deferred measurement);
  • medians, test outcomes and the dyadic bisection endpoints are computed reversibly, and the comparisons in each test are exact integer comparisons;
  • once the bisection has ended, the remaining tests idle, so every branch makes the worst-case number of queries;
  • 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 by aa. Nothing needs to be uncomputed.

Substituting this test for GAE in the algorithm of Wang et al. gives new Theorem 9: best-arm identification with O~(H/α)\tilde O(\sqrt{H/\alpha}) queries, matching Theorem 7 up to polylogarithmic factors in the worst case over gap profiles. Appendix H checks each use of GAE in their analysis:

  • the flag bounds in their Lemmas 1 and 6, with pip_i replaced by Ci∈[0,1]C_i\in[0,1];
  • the per-arm decomposition of their Lemma 6, which needs only that each stage is controlled on the arm index;
  • the stopping times of their Lemma 2, each multiplied by α−1/2\alpha^{-1/2} up to logarithms, while the stopping probabilities are unchanged;
  • the VTAA cost, through tmax⁡t_{\max}, tavgt_{\mathrm{avg}} and psuccp_{\mathrm{succ}};
  • the artificial arm with p0=1p_0=1, replaced by a point mass at 1;
  • the analyses of Amplify, Estimate, Locate and Shrink, which use the biases only through their order, the number of arms above a threshold, and interval arithmetic, all of which hold for the CiC_i. Section 6 and Appendix H are rewritten accordingly (purple). Theorem 4 is kept because it needs no superposition over arms and has explicit constants, whereas Theorem 9 inherits unspecified polylogarithmic factors from VTAA.

W2 and Q2. Numerical evaluation and the sampler. We agree the evaluation was too narrow, and on Q2 our sampler claim was incorrect. Every outcome outside the enumerated window was a failure, so replacing it by a uniform grid outcome could only turn failures into successes, by at most the discarded mass (6.8×10−46.8\times10^{-4} per run). There was no stochastic domination in the direction we claimed. The simulator now enumerates all MM outcomes (largest normalization error 2.4×10−102.4\times10^{-10}), and the results for Algorithm 1 are unchanged: 200 runs, worst error 1.4×10−3ε1.4\times10^{-3}\varepsilon.

New experiments (Section 7, Figure 4, Appendix I, in blue), all with exact amplitude-estimation statistics (the sampler description is in purple, since Reviewer PKwj raised it too):

  • Algorithm 2 on atoms and every exit. Twelve distributions chosen to reach every exit and the delicate cases of the proof: point masses at 0 and 1, an atom straddling the quantile, a CDF equal to α\alpha on an interval, the two lower-bound instances of Theorem 6, and a two-point instance at the edge of the band at the origin. With α∈{0.2,0.05}\alpha\in\lbrace 0.2,0.05\rbrace, ε∈{0.05,0.02,0.01}\varepsilon\in\lbrace 0.05,0.02,0.01\rbrace and 200 runs per setting, all 14,400 runs were within ε\varepsilon (worst 0.245ε0.245\varepsilon), with 5,475 band exits, 6,362 atom exits and 2,563 exits at the origin (Table 3). Before replacing it (see our reply to Reviewer 4hW6), we ran the submitted two-phase Algorithm 2 on the same distributions: 1,200 runs, all within ε\varepsilon, worst 0.125ε0.125\varepsilon.
  • Algorithm 3 (best-arm identification). Four instances at α=0.05\alpha=0.05, with KK up to 20 and smallest gap down to 0.005, one of which has a mean-optimal arm that is not CVaR-optimal: 320 of 320 runs correct, using about 6% of the Theorem 4 bound, and no arm eliminated after round rˉi\bar r_i (Table 4).
  • Algorithm 4 (regret). K=4K=4 and T=5×1010T=5\times10^{10}: as the gap shrinks from 0.2 to 0.003125, the regret grows from 4.1×1064.1\times10^6 to 1.4×1071.4\times10^7, that is 3.6-fold. The classical estimator run through the same rounds grows from 9.2×1049.2\times10^4 to 9.7×1069.7\times10^6, that is 106-fold. We report the comparison as it stands. At the constants of our bounds the classical version is still cheaper at every gap and instance we simulated, and the quantum advantage shows in the growth rates: the ratio falls from 44 to 1.5 in regret as the gap shrinks, and extrapolating, the two cross near a gap of 0.002. Identification shows the same trend, with ratios from 18 on instance A to 1.5 on instance D. This is the same trade-off between constants and exponents as the estimator crossover of Figure 3(c), which moved to ε∗≈6.5×10−4\varepsilon^\ast\approx 6.5\times10^{-4} to 3.8×10−33.8\times10^{-3} after the simplification of Algorithm 2.

W3. High-probability versus expected regret. Theorem 5 now also states (Eq. (9), in blue) that with δ=1/T\delta=1/T,

E[Regret(T)]≤Bˉ(T,1/T)+1=O(Kαlog⁡Tαlog⁡(KTlog⁡Tα)),\mathbb E[\mathrm{Regret}(T)] \le \bar{\mathcal B}(T,1/T)+1 = O\Big(\tfrac{K}{\sqrt\alpha}\log\tfrac{T}{\alpha}\log\big(KT\log\tfrac{T}{\alpha}\big)\Big),

where Bˉ(T,δ)\bar{\mathcal B}(T,\delta) is the right-hand side of Eq. (8) with every round index replaced by the last round whose estimator call fits within TT queries. On the failure event, of probability at most δ\delta, the regret is at most TT because every gap is at most 1, so the δT\delta T term contributes 1 (Appendix E). This makes the comparison with the expected-regret results of Wan et al. (2023) and the Ω(Klog⁡(T/K))\Omega(K\log(T/K)) lower bound of Liu et al. (2026) direct.

W4 and W5. Related work. Both are added to Section 9 (blue). Agrawal, Koolen and Juneja (NeurIPS 2021) give δ\delta-correct best-arm identification for CVaR, VaR and mean-CVaR mixtures, including heavy-tailed arms, with sample complexity asymptotically matching the lower bound; Theorems 4 and 9 are a quantum counterpart in the bounded setting. Siam, Guan and Liu (AAAI 2026) obtain polylogarithmic regret for non-linear bandit optimization using quantum Monte Carlo mean estimation; their objective is non-linear in the action but is still a mean reward, whereas ours is a non-linear functional of the reward distribution.

Q1. Comparison with earlier quantum CVaR estimators. New Appendix J (Table 5, in blue) compares them parameter by parameter:

  • Woerner and Egger (2019): VaR by bisection over amplitude estimates of the CDF on a 2n2^n-point grid, and CVaR by amplitude estimation of the tail sum normalized by the estimated tail probability, with state-preparation access (whose inverse amplitude estimation uses). Their CVaR error is given to first order as about (VaR+CVaR)π/(MP[X≤VaR])(\mathrm{VaR}+\mathrm{CVaR})\pi/(M\mathbb{P}[X\le \mathrm{VaR}]), which is α−1\alpha^{-1} in our notation, with higher-order terms dropped, and their payoff approximation gives an O(M−2/3)O(M^{-2/3}) rate. There is no end-to-end bound and no lower bound.
  • Skarlatos and Konofaos (2025): the dd-dimensional CVaR subgradient of a linear loss (upper tail), with O((d/ε)log⁡(1/η))O((d/\varepsilon)\log(1/\eta)) queries when the VaR threshold is given, and constants depending on the tail probability, assuming a bounded density and a bounded loss gradient. A matching lower bound is stated as open.
  • Ours: the scalar CVaR value under the qsample oracle with inverse and controlled access, with no continuity or density assumption; an atom at the quantile is handled by the atom exit. Lemma 1 gives 140(2R+1)2ln⁡((2R+1)/δ)/(αε)140(2R+1)^2\ln((2R+1)/\delta)/(\alpha\varepsilon). Lemma 2 gives 1920(B+2)ln⁡((B+2)/δ)/(αε)1920(B+2)\ln((B+2)/\delta)/(\sqrt{\alpha}\varepsilon) for α≤1/4\alpha\le 1/4 and αε≤10−2\alpha\varepsilon\le10^{-2}, matched by the Ω(1/(αε))\Omega(1/(\sqrt{\alpha}\varepsilon)) of Theorem 6. The two structural differences are quantile handling and tail-level dependence. Both earlier works locate the quantile on an estimated CDF and divide by an estimated tail probability, which is where a density or grid assumption enters; the Rockafellar-Uryasev search and the certified three-way bisection need neither. Where the earlier analyses expose the tail level, it enters as an inverse tail probability, α−1\alpha^{-1} in our notation; Lemma 2 and Theorem 6 pin it at α−1/2\alpha^{-1/2}.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank all three reviewers for careful reviews. Their main technical points were correct, and acting on them has made the paper stronger. We have uploaded a revised PDF in which every change is highlighted by color (key below). The main changes are summarized here, and each reviewer's points are answered individually.

1. A simpler and cheaper amplitude-aware estimator (Reviewer 4hW6). The reviewer observed that Phase 2 of Algorithm 2 is unnecessary, and this is right. The certified bisection already stops at a point r0r_0 with 0≤CVaRα−ϕ(r0)≤3ε/80 \le \mathrm{CVaR_\alpha} - \phi(r_0) \le 3\varepsilon/8 and ar0≤118αa_{r_0} \le \tfrac{11}{8}\alpha, so a single amplitude estimate of ar0a_{r_0} finishes the job. Lemma 2 now reads Q′≤1920(B+2)ln⁡((B+2)/δ)/(αε)Q' \le 1920(B+2)\ln((B+2)/\delta)/(\sqrt{\alpha}\varepsilon), one logarithmic factor where there were two. In exact worst-case counts the estimator is 34 to 57 times cheaper at the six settings we simulated, and about 96 times cheaper at α=0.05\alpha = 0.05, ε=10−4\varepsilon = 10^{-4}. The accuracy below which the Lemma 2 bound beats the classical bound moves from 3.6×10−63.6\times10^{-6} to 1.9×10−51.9\times10^{-5} (as α\alpha goes from 0.25 to 0.005) to 6.5×10−46.5\times10^{-4} to 3.8×10−33.8\times10^{-3}. (Section 3.2, Appendix D.)

2. The K\sqrt{K} gap is closed (Reviewers 1Tea and PKwj). Both reviewers questioned our claim that coherent execution of the estimator was the obstacle to variable-time amplitude amplification (VTAA). They were right. Run by deferred measurement, Algorithm 2 is a unitary with a fixed worst-case query count whose final estimate can be thresholded into a flag qubit. The gapped amplitude estimation (GAE) interface of Wang et al. (2021, Corollary 2) allows arbitrary states beside the flag, and their VTAA theorem places no condition on workspace. New Lemma 8 constructs this coherent gapped CVaR test, and new Theorem 9 gives best-arm identification with O~(H/α)\tilde O(\sqrt{H/\alpha}) queries, matching the lower bound of Theorem 7 up to polylogarithmic factors in the worst case over gap profiles. Section 6 is rewritten, and Appendix H checks every place where the analysis of Wang et al. uses GAE. Theorem 4 is kept: it needs no superposition over arms and has explicit constants.

3. Experiments for every algorithm we can run classically (Reviewers 1Tea and PKwj). The simulator now enumerates all MM outcomes of amplitude estimation, so it is exact up to floating point. Algorithm 2 met its guarantee in all 14,400 runs on twelve distributions chosen to reach every exit (point masses, an atom straddling the quantile, a CDF flat at level α\alpha, the lower-bound instances), with worst error 0.245ε0.245\varepsilon. Algorithm 3 identified the best arm in all 320 runs on four instances (KK up to 20, smallest gap 0.005). 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, which at our constants is still cheaper at the gaps simulated. (Section 7, Figure 4, Appendix I.)

4. Further changes. Eq. (8) has the corrected terminal logarithm (4hW6). Theorem 5 now also bounds expected regret (1Tea). Related work adds Agrawal, Koolen and Juneja (2021) and Siam, Guan and Liu (2026), and new Appendix J compares quantum CVaR estimators parameter by parameter (1Tea). The incorrect statement about the earlier truncated sampler is removed (PKwj, 1Tea).

Color key. In the revised PDF, changed text is colored by the review that prompted it: blue for Reviewer 1Tea, orange for Reviewer 4hW6, and purple for points raised by more than one reviewer, which include all of Reviewer PKwj's points. Gray marks text that was only shortened, reworded or given a corrected citation, with no new content. A colored figure caption marks a new or regenerated figure, and a colored table a new table.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.