{"id":"b250aa31-1cc5-44d5-b713-86a5ff47efd2","arxiv_id":"2608.02826","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New quantum algorithms compute near-optimal policies for finite-horizon MDPs with Õ(H^{2.5}S√A/ε) queries and for infinite-horizon discounted MDPs with Õ(Γ^{2.5}S√A/ε) queries, improving all previously known quantum upper bounds.","lead":"This paper presents quantum algorithms that compute approximately optimal policies for two standard classes of reinforcement learning problems, using fewer queries to the environment simulator than any previous quantum approach. The results move quantum reinforcement learning closer to the theoretical limits on how fast such problems can be solved.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The H^{2.5}/Γ^{2.5} results hinge on a coherent mean-estimation oracle that is asserted but not constructed; a constant mismatch with the pseudocode makes this the least secure step.","rationale":"The reader's verdict is CONDITIONAL, and I share that assessment: the paper's proof structure is credible and the imported total-variance lemmas (Fact 3 and Lemma 1) are standard, likely correct statements. However, the genuinely fragile point in both theorems is the claimed coherent implementation of quantum mean estimation as an oracle for quantum maximum finding. The proof asserts this in one sentence and then bounds the difference between real and ideal unitaries, but it never exhibits the unitary or verifies that Fact 2 can be run without adaptive measurements. Since both advertised improvements over prior work come precisely from composing variance-aware mean estimation with maximum finding, this is the step on which the central claim rests. The pseudocode/proof constant discrepancy is not fatal by itself, but it is a concrete sign that the subroutine has not been fully pinned down. I therefore keep the reader's CONDITIONAL verdict rather than moving to ACCEPT or REJECT; the natural next step is a complete circuit-level construction of the oracle and a reconciliation of the constants.","tokens_in":24450,"tokens_out":20433,"duration_ms":182113,"concrete_test":"Write out the full circuit for Fact 2 ([36, Thm 1.1]) as a unitary with a success flag, listing every call to O_u and O_p, and verify that (a) no intermediate measurement is used to choose later queries and (b) the total Q_p-query count remains O((1/θ) log(1/δ)) with success amplitude sqrt(1−δ). Then re-run the Theorem 1 induction using Algorithm 1 line 7's constants (θH^2, θ^{3/2}H) in place of Eq. (3)'s (2θH^2, sqrt(2) θ^{3/2}H); if pμ ≤ μ fails, the pseudocode must be corrected or the ε budget updated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the construction of the unitary U_s^{(h)} in the proof of Theorem 1, and its analogue U_s^{(t)} in Theorem 2. The proof says \"We claim that Fact 2 can be adapted to perform all of its steps in superposition without any need for intermediary measurements,\" but Fact 2 as stated is a probabilistic estimator that outputs a classical estimate rμ with success probability 1−δ. Nesting it inside Dürr–Høyer maximum finding requires one unitary that (i) computes both rμ and rσ, (ii) forms pμ by coherent arithmetic, and (iii) has a failure branch of amplitude sqrt(δ_a). No circuit-level construction is given. If the Kothari–O'Donnell subroutine uses adaptive measurements, deferral is not automatic and the query count to Q_p may change; the norm-distance argument between the \"real\" and \"ideal\" unitaries does not by itself establish that quantum maximum finding still succeeds, since maximum finding is itself adaptive. This step is where the sqrt(A) speedup in both main results comes from. A secondary concrete mismatch compounds the concern: Algorithm 1 line 7 states |rσ−σ| ≤ θH^2 and pμ = rμ − θ sqrt(rσ) − θ^{3/2}H, while the proof's Eq. (3) uses 2θH^2 and sqrt(2) θ^{3/2}H. With proof-level guarantees, the pseudocode's smaller shift may fail to make pμ one-sided, which would break the monotonicity argument. Both issues are likely fixable, but until the unitary is explicitly constructed, the advertised H^{2.5} and Γ^{2.5} exponents are not fully established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes two quantum algorithms for computing approximately optimal policies in tabular MDPs under a generative model. For finite-horizon MDPs, Algorithm 1 is claimed to output an ε-optimal policy with query complexity Õ(H^{2.5} S √A / ε) (Theorem 1); for infinite-horizon discounted MDPs, Algorithm 2 is claimed to output a 2ε-optimal stationary policy with query complexity Õ(Γ^{2.5} S √A / ε) (Theorem 2). The algorithms run quantum value iteration using Kothari–O'Donnell mean estimation with variance inside Dürr–Høyer maximum finding, and the analysis imports the total-variance error-accumulation bound from Sidford et al. [50] to replace the naive H or Γ accumulation by H^{3/2} or Γ^{3/2}. The proof structure is an induction with one-sided estimates pμ chosen to preserve monotonicity in the discounted case.","tokens_in":24827,"tokens_out":12064,"duration_ms":108400,"significance":"If the advertised bounds hold, they give a clear improvement over previous quantum upper bounds: the finite-horizon H^3 S√A/ε bounds of Ambainis et al. and Luo et al. become H^{2.5} S√A/ε, and the infinite-horizon Γ^3 S√A/ε branch of Wang et al. becomes Γ^{2.5} S√A/ε, while the Γ^{1.5} S A / ε and H^{2.5} S A / ε branches are subsumed or complemented. The gap to the lower bounds Ω(H^{1.5} S√A/ε) and Ω(Γ^{1.5} S√A/ε) is reduced. The derivation is essentially parameter-free in the sense that the stated complexities follow from the chosen θ = ε/(7H^{3/2}) and θ = ε/(7Γ^{3/2}), and the error-accumulation analysis is explicit and careful. The main weakness is not in the algebraic error analysis but in the asserted construction of a coherent mean-estimation oracle; until that construction is supplied, the √A speedup and the advertised exponents are not fully justified.","major_comments":[{"comment":"The construction of the oracle U_s^(h) (and its analogue U_s^(t)) is the load-bearing step of both theorems. The proof asserts that \"Fact 2 can be adapted to perform all of its steps in superposition without any need for intermediary measurements,\" but Fact 2 as stated is a bounded-error classical-output estimator. What is needed is an explicit unitary that on |a>|0> produces sqrt(1−δ_a)|pμ_{h+1}(s,a)> + sqrt(δ_a)|K_a>, with rμ, rσ and pμ computed by coherent arithmetic, and without measurements inside the branch. If the Kothari–O'Donnell subroutine uses adaptive measurements, its coherent version is not automatic and the number of queries to Q_p and Q_p† may change. The subsequent norm-distance argument between W and W̃ treats quantum maximum finding as a fixed sequence of unitaries, but Dürr–Høyer maximum finding is adaptive and may use intermediate measurements, so the spectral-norm bound alone does not directly control the failure probability unless a hybrid argument over the random oracle sequence is supplied. Since this oracle carries the √A factor in both main results, the H^{2.5} and Γ^{2.5} exponents are not fully established until this construction is provided.","section":"Sec. 3, proof of Theorem 1, Eq. (2); Sec. 4, proof of Theorem 2, Eq. (4)"},{"comment":"There is a concrete constant mismatch between the pseudocode and the proof. Algorithm 1 line 7 specifies |rσ−σ| ≤ θH² and pμ = rμ − θ√(rσ) − θ^{3/2}H, while the proof's Eq. (3) gives |rσ−σ| ≤ 2θH² and pμ = rμ − θ√(rσ) − √2 θ^{3/2}H. Algorithm 2 has the analogous mismatch with Γ. Under the proof-level bound |rσ−σ| ≤ 2θH², the smaller shift θ^{3/2}H in the pseudocode may fail to guarantee pμ ≤ μ; this one-sided property is used to conclude V_h(s) ≤ (L_{π_h}V_{h+1})(s) and hence V_h ≤ V^{π_h,H}_h, and the analogous monotonicity argument in Theorem 2. The constants in the pseudocode and the proof should be reconciled, or the proof should be adjusted to the pseudocode's stated bounds.","section":"Algorithm 1, line 7 vs. Eq. (3); Algorithm 2, line 7 vs. Eq. (5)"},{"comment":"The claimed improvement from H^3 to H^{2.5} rests on Fact 3, quoted from [50, Lemma F.4] with only a typo correction and no proof or exact quotation of the original statement. If that bound were mis-transcribed, the query complexity of both main theorems would degrade by a factor of √H or √Γ. I am not claiming that the lemma is false; however, because it is load-bearing and the paper flags a typo in the source, the proof should be reproduced or the precise lemma quoted verbatim. The analogous discounted bound (Lemma 1) is proved in the paper, but the Cauchy–Schwarz step leading to ||Σ γ√σ||_∞ ≤ Γ^{1/2} ||Σ γ²σ||_∞^{1/2} should be written out explicitly, as it is not immediate.","section":"Sec. 3, Fact 3; Sec. 4, Lemma 1"}],"minor_comments":[{"comment":"The declared output is a stationary deterministic policy π^8_{T−1}, but the return statement gives the finite sequence (π_0, ..., π_{T−1}); the relationship between the two should be clarified.","section":"Algorithm 2, Output and return statement"},{"comment":"The algorithm's input range ε ∈ (0, √Γ] differs from the theorem's ε ∈ (0, 1]; since Γ ≥ 1, these are not the same and the discrepancy should be resolved.","section":"Algorithm 2, line 1"},{"comment":"The phrase \"up to poly log log factors\" appears immediately before an expression that already contains several log factors; either the phrase is a typo or the displayed log factors should be reconciled with it.","section":"Theorem 2, query complexity statement"},{"comment":"The initialization step uses Fact 1 to find max_a r(s,a), but the reward function is known exactly; the algorithm should state whether this step is charged to the query complexity, since it appears not to require queries to Q_p.","section":"Algorithm 1, line 2"}],"recommendation":"major_revision","confidential_remarks":"This is a plausible and well-scoped algorithmic contribution for the journal. The error-accumulation analysis is careful and the claimed scalings are a genuine improvement over the previous quantum upper bounds if the coherent-oracle construction can be made rigorous. The two main obstacles—the unbuilt coherent mean-estimation oracle and the pseudocode/proof constant mismatch—are of the kind that a serious revision can address, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this paper improves the best known quantum query upper bounds for RL under a generative model to O~(H^{2.5} S sqrt(A)/epsilon) and O~(Gamma^{2.5} S sqrt(A)/epsilon). That is a real advance: it subsumes the previous finite-horizon branches and improves the infinite-horizon sqrt(A) branch by sqrt(Gamma). The gap to the lower bounds shrinks from H^2 to H and from Gamma^2 to Gamma. If the proofs hold, this is the paper to beat.\n\nWhat is genuinely new is the specific combination: variance-aware mean estimation (Kothari-O'Donnell) run inside Dürr-Høyer maximum finding, with total-variance error accumulation taken from Sidford et al. The error analysis is mostly careful: the induction is coherent, the use of Fact 3 and Lemma 1 is clearly flagged, and the author even notes the typo in the original [50, Lemma F.4]. The citation pattern is healthy; the author's own work is cited only as the prior bound being improved.\n\nThe soft spots are real but, I think, fixable. The load-bearing step is the claim that Fact 2 can be adapted to run in superposition to build the oracle O_s^{(h)}. That claim is asserted, not constructed. This is exactly where the sqrt(A) speedup comes from, so the advertised exponents rest on it. The norm-distance argument between real and ideal unitaries is okay once such a unitary exists, but existence needs a circuit-level argument, or at least a careful deferral-of-measurement argument, rather than a sentence. Second, the pseudocode and the proof disagree: Algorithm 1 line 7 writes |r_sigma - sigma| <= theta H^2 and p_mu = r_mu - theta sqrt(r_sigma) - theta^{3/2} H, while the proof's Eq. (3) uses 2 theta H^2 and sqrt(2) theta^{3/2} H. With the proof-level constants, the pseudocode's shift is too small to guarantee the one-sided error, so monotonicity can break. The same mismatch appears in Algorithm 2. This is a minor fix but needs to be made.\n\nI also note that Fact 3 and Lemma 1 are imported; if the total-variance bound were wrong or mis-transcribed, the gains would degrade by sqrt(H) or sqrt(Gamma). That is a reasonable dependency on the literature, not a flaw in itself, and the author does flag the typo in [50].\n\nAll in all, this is a serious paper for the quantum-RL theory crowd. I would send it to a competent referee. The right verdict is probably a revision: make the oracle construction explicit, reconcile the constants, and the improved bounds should stand.","headline":"Best-known upper bounds for finite- and infinite-horizon RL, but the proof leaves the coherent mean-estimation oracle at the level of an assertion and the pseudocode constants don't match the analysis.","tokens_in":25403,"tokens_out":7518,"would_cite":true,"duration_ms":70669,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","90C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Under a generative model of an MDP, quantum algorithms compute ε-optimal policies with Õ(H^{2.5}S√A/ε) queries for finite-horizon problems and Õ(Γ^{2.5}S√A/ε) for infinite-horizon discounted problems, improving all prior quantum bounds…","keywords":["reinforcement learning","Markov decision processes","generative model","quantum algorithms","value iteration","quantum mean estimation","quantum maximum finding","query complexity"],"falsifier":"Choose a small MDP with known transition probabilities, run the paper's error-accumulation inequalities (the finite-horizon bound and its discounted analogue) over all deterministic policies, and compute the ℓ∞ norm of the variance-weighted error sum. If any policy yields a value above $H^{{3/2}}$ in the finite-horizon case or above $2Γ^{2}$ in the discounted case, the bound used in Theorems 1 and 2 is false and the stated query complexity does not follow.","tokens_in":24267,"feed_emoji":"⚛️","tokens_out":9474,"duration_ms":75899,"temperature":0.7,"pith_summary":"This paper claims that, when an agent can only learn an MDP's transition probabilities by sampling from a generative model, quantum computers can compute ε-optimal policies with query complexity Õ($H^{{2.5}}$S√A/ε) for finite-horizon MDPs and Õ($Γ^{{2.5}}$S√A/ε) for infinite-horizon discounted MDPs, where H is the horizon, Γ=1/(1−γ) the effective horizon, and S and A the numbers of states and actions. These are the best known quantum upper bounds and move closer to the established quantum lower bounds of Õ($H^{{1.5}}$S√A/ε) and Õ($Γ^{{1.5}}$S√A/ε). The advance comes from nesting a variance-aware quantum mean estimator inside quantum maximum finding, so that the search over actions is quadratically faster while the accumulated error is controlled by total variance instead of a naive linear sum. A sympathetic reader should care because the generative model is the standard theoretical yardstick for reinforcement-learning sample complexity, and the result shows that the quantum advantage persists when both state and action spaces are large.","feed_headline":"Quantum RL: near-optimal policies at H^2.5√A queries","feed_subtitle":"Variance-aware mean estimation plus quantum search beats previous query bounds for finite-horizon and discounted MDPs.","key_machinery":"The load-bearing object is a coherent mean-and-variance oracle: quantum mean estimation is invoked twice, once for the next-step value function and once for its square, so that each action branch of the superposition carries both a one-sided low-biased estimate $\\hat\\mu_{h+1}(s,a)$ of the expected next value and an estimate $\\hat\\sigma_{h+1}(s,a)$ of its variance. This oracle is then handed to quantum maximum finding, which finds the best action with $O(\\sqrt A)$ oracle calls instead of $A$. The variance estimate is what allows the error to be tracked by total-variance bounds (a finite-horizon bound and a discounted analogue) asserting that the $\\ell^\\infty$-norm of the variance-weighted Bellman-error sum is $O(H^{3/2})$ or $O(\\Gamma^{3/2})$, so the algorithm can afford larger per-step errors while still finishing $\\varepsilon$-close. In the discounted case the algorithm additionally enforces monotonicity, keeping the current value function below its own Bellman iterate, which is what turns an $\\varepsilon$-close value function into an $\\varepsilon$-optimal policy.","core_discovery":"The paper's central discovery is that the total-variance technique that makes classical value iteration sample-optimal is compatible with quantum maximum finding, provided the quantum mean estimator also outputs a variance estimate in superposition. Concretely, Theorem 1 proves that Algorithm 1 returns value functions and a deterministic policy such that $V^*_h - \\varepsilon \\le V_h \\le V^{\\pi,H}_h \\le V^*_h$ for every $h \\in [H]$, with probability at least $1-\\delta$, using $O(H^{2.5}S\\sqrt{A}/\\varepsilon \\cdot \\operatorname{polylog})$ queries to the transition oracle and its inverse. Theorem 2 proves the analogous statement for infinite-horizon discounted MDPs with $\\Gamma$ replacing $H$ and an additional monotonicity step, yielding a $2\\varepsilon$-optimal stationary policy with $\\tilde{O}(\\Gamma^{2.5}S\\sqrt{A}/\\varepsilon)$ queries. The proofs induct step by step through value iteration and show that the per-step estimation error, which is proportional to the square root of the local variance, accumulates through a variance-weighted sum that is $O(H^{3/2})$ or $O(\\Gamma^{3/2})$ rather than $O(H)$ or $O(\\Gamma)$.","pith_inferences":["The paper notes that the finite-horizon construction generalises to time-dependent MDPs; if that extension is worked out in full, the same $H^{2.5}S\\sqrt{A}/\\varepsilon$ complexity should apply there with only notational changes.","The speed advantage is a query-complexity statement; a practical implementation must also account for building quantum access to the value functions and for executing quantum mean estimation without intermediate measurements, and a failure of that coherent execution would inflate the complexity by a factor of $\\sqrt{H}$ or $\\sqrt{\\Gamma}$.","One could empirically test the claims on small synthetic MDPs by instrumenting the number of oracle queries and checking that it scales as $H^{2.5}\\sqrt{A}$ rather than $H^3\\sqrt{A}$ or $H^{2.5}A$; such a benchmark would also reveal whether the constant factors hidden in the $\\tilde{O}$ notation are practical.","The combination of variance-aware estimation with quantum search may transfer to other planning and simulation problems whose sample complexity is set by total variance, such as average-reward or risk-sensitive MDPs, though the paper does not make this claim."],"forward_implications":["Finite-horizon MDPs can now be solved with $\\tilde{O}(H^{2.5}S\\sqrt{A}/\\varepsilon)$ queries, which subsumes both previous upper bounds $\\tilde{O}(H^{2.5}SA/\\varepsilon)$ and $\\tilde{O}(H^3 S\\sqrt{A}/\\varepsilon)$ since $\\sqrt{A} \\le A$.","Infinite-horizon discounted MDPs have a new upper bound $\\tilde{O}(\\Gamma^{2.5}S\\sqrt{A}/\\varepsilon)$, which combined with the earlier $\\tilde{O}(\\Gamma^{1.5}SA/\\varepsilon)$ branch gives the overall bound $\\tilde{O}(\\min\\{\\Gamma^{1.5}SA/\\varepsilon,\\ \\Gamma^{2.5}S\\sqrt{A}/\\varepsilon\\})$.","The algorithms return certified outputs with high probability: value functions within $\\varepsilon$ of optimal and policies that are $\\varepsilon$-optimal (finite horizon) or $2\\varepsilon$-optimal (discounted), including a stationary deterministic policy in the infinite-horizon case.","The remaining gap to the quantum lower bounds is a factor $H$ in the finite-horizon setting and a factor $\\Gamma$ in the discounted setting, so closing that gap would require new ideas beyond variance-aware maximum finding."],"supporting_citations":[{"why":"Supplies the sample-optimal classical framework—monotonicity, variance reduction, and the total-variance bound (Fact 3)—that the quantum algorithms quantise.","marker":"[50]"},{"why":"Supplies Fact 2, the variance-aware quantum mean estimator that is run coherently to build the mean-and-variance oracle.","marker":"[36]"},{"why":"Supplies Fact 1, quantum maximum finding, which finds the best action in O(√A) oracle calls.","marker":"[17]"},{"why":"Prior quantum upper bound for infinite-horizon discounted MDPs; Result 2 improves its Γ^3 S√A/ε branch.","marker":"[55]"},{"why":"Prior finite-horizon quantum upper bound; Result 1 subsumes its query complexity.","marker":"[4]"},{"why":"Prior finite-horizon quantum algorithm and the H^{1.5}S√A/ε lower bound that Result 1 approaches.","marker":"[39]"}],"fun_headline_variants":["Quantum RL: variance-aware estimation cuts query cost","Quantum RL: approaching lower bounds with variance-aware search","Quantum RL: H^2.5√A queries via variance-aware sampling","Improved quantum RL: near-optimal queries for MDPs","Quantum RL: variance-aware search achieves near-optimal query bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The improved exponents depend on a guarantee that small estimation errors at each step do not pile up as fast as the number of steps—they accumulate like the square root of the number of steps cubed; if that guarantee fails for quantum estimation errors, the advertised speedup shrinks by a factor of √H or √Γ.","fun_headline_variants_meta":{"raw":{"variants":["Quantum RL: variance-aware estimation cuts query cost","Quantum RL: approaching lower bounds with variance-aware search","Quantum RL: H^2.5√A queries via variance-aware sampling","Improved quantum RL: near-optimal queries for MDPs","Quantum RL: variance-aware search achieves near-optimal query bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001142,"raw_usage":{"total_tokens":4735,"prompt_tokens":937,"completion_tokens":3798,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":3714}},"tokens_in":553,"tokens_out":3798,"duration_ms":22297,"temperature":1.0,"reasoning_tokens":3714,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:58:56.740520+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose a small MDP with known transition probabilities, run the paper's error-accumulation inequalities (the finite-horizon bound and its discounted analogue) over all deterministic policies, and compute the ℓ∞ norm of the variance-weighted error sum. If any policy yields a value above $H^{{3/2}}$ in the finite-horizon case or above $2Γ^{2}$ in the discounted case, the bound used in Theorems 1 and 2 is false and the stated query complexity does not follow.","supporting_citations":[{"cited_title":"Near-optimal time and sample complexities for solving Markov decision processes with a generative model","cited_arxiv_id":null,"evidence_quote":"Supplies the sample-optimal classical framework—monotonicity, variance reduction, and the total-variance bound (Fact 3)—that the quantum algorithms quantise."},{"cited_title":"Mean estimation when you have the source code; or, quantum Monte Carlo methods","cited_arxiv_id":null,"evidence_quote":"Supplies Fact 2, the variance-aware quantum mean estimator that is run coherently to build the mean-and-variance oracle."},{"cited_title":"Quantum algorithms for reinforcement learning with a generative model","cited_arxiv_id":null,"evidence_quote":"Prior quantum upper bound for infinite-horizon discounted MDPs; Result 2 improves its Γ^3 S√A/ε branch."},{"cited_title":"A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model","cited_arxiv_id":"2507.22854","evidence_quote":"Prior finite-horizon quantum upper bound; Result 1 subsumes its query complexity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Prior finite-horizon quantum algorithm and the H^{1.5}S√A/ε lower bound that Result 1 approaches."}],"review_version":1}