{"id":"e384935e-2561-4232-a840-079cad088bf7","arxiv_id":"2501.16243","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A quantum natural policy gradient algorithm with deterministic truncated estimators achieves tilde O(epsilon^{-1.5}) sample complexity for infinite-horizon model-free RL, improving on the classical tilde O(epsilon^{-2}) rate.","lead":"This paper designs a quantum version of a standard reinforcement-learning update rule, natural policy gradient, that uses coherent quantum sampling instead of random sampling. It claims a sample-efficiency improvement, roughly a square-root reduction in queries to the environment, for infinite-horizon decision problems with parameterized policies.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The stated quantum oracle model has no reward oracle, yet U_g in Eq. (17) requires r(s,a) (Eq. 14); without one, Algorithm 1 cannot compute gradient estimates, so Theorem 3's \\tilde{O}(ε^{-1.5}) guarantee is not implementable as stated.","rationale":"After reviewing the full text, I find the reader's weakest_assumption to be the correct load-bearing concern. The central claim of Theorem 3 is a sample-complexity guarantee for Algorithm 1 under the oracle model of Section 2.3. Lemma 4 and Appendix A.2 describe how to construct U_g, but this construction relies on the fact that r(s,a) can be computed classically (A.2 point 2). The oracles defined in (4)-(6) provide no reward information; they are purely transition, initial-state, and policy oracles. Therefore the gradient estimator of Eq. (14) cannot be evaluated in superposition, so QVarianceReduce (18) has no valid input. This is not a mere notation issue: the sample complexity 'queries to the quantum oracle' in Theorem 3 counts queries to U_P/Π/U_ρ, not to any reward mechanism, so the theorem is asserting a rate for an algorithm that cannot be implemented for an unknown-reward MDP. A clean remedy is to add a quantum reward oracle and count its queries; this is standard in quantum RL (e.g., Jerbi et al. 2023) and would make the comparison to the classical lower bound fair. The other defects—the missing S_N register in A.1, the (1−γ)^{-2} mismatch in the Lemma 5 proof, and the α condition in Lemma 6—are real but local: they are typos or easy fixes that do not change the ε-scaling of the argument. The reward-oracle gap is the single condition that must be settled before the central claim is meaningful. Since this matches the reader's CONDITIONAL verdict, no adjustment is needed.","tokens_in":23408,"tokens_out":22056,"duration_ms":193930,"concrete_test":"Add to Section 2.3 a quantum reward oracle O_r: |s,a⟩|0⟩ → |s,a⟩|r(s,a)⟩, let U_g query O_r, and re-derive the query complexity of Theorem 3 counting O_r queries. If the total remains \\tilde{O}(ε^{-1.5}), the central claim survives under the amended oracle model; if O_r queries add a factor that cannot be absorbed, the speedup fails. Separately, attempt to build U_g for a 2-state MDP with unknown reward using only U_P, U_ρ, Π; any impossibility demonstrates the stated algorithm is not implementable in the current model.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.3 defines quantum access to the MDP via only the transition oracle U_P (Eq. 4), the initial-state oracle U_ρ (Eq. 5), and the policy oracle Π (Eq. 6). No reward oracle is defined. However, the gradient estimator \\hat{g}_ρ in Eq. (14) contains the factor γ^n r(s_n, a_n), and the construction of U_g in Eq. (17) / Appendix A.2 requires evaluating r(s,a) in superposition for every trajectory. Appendix A.2 asserts r(·,·) is 'classically computable' but this is an unstated modeling assumption: it requires the learner to know the reward function analytically, which is not implied by access to U_P, U_ρ, Π and is stronger than the oracle access normally assumed in model-free RL. If r is unknown to the learner, there is no way to build U_g, and Algorithm 1 cannot form \\tilde{g}_h. This also makes the comparison with the classical \\tilde{Ω}(ε^{-2}) MDP-query lower bound unfair: the quantum algorithm would be using analytic knowledge of r, which the classical lower bound does not grant. The other issues found by the reader (the missing S_N register in Appendix A.1, the inconsistent bound in the proof of Lemma 5, and the α condition in Lemma 6) are technical fixable defects; the reward-oracle gap is a modeling premise that must be amended before the central claim can be stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a Quantum Natural Policy Gradient (QNPG) algorithm for infinite-horizon discounted Markov decision processes with general policy parameterization. It replaces classical stochastic NPG estimators with deterministic truncated estimators \\hat g_ρ(τ_N|θ) and \\hat F_ρ(τ_N|θ), evaluates them coherently on superpositions of length-N trajectories, and feeds them to a quantum variance-reduction subroutine (QVarianceReduce). The main result, Theorem 3, claims that under Assumptions 1–3 and with H = O(log(1/ε)), N = O(log(1/ε)), K = O(1/ε), σ_g^2 = O(ε), and σ_F^2 = O((1−γ)^4 ε), Algorithm 1 guarantees J*_ρ − (1/K)Σ_k E[J_ρ(θ_k)] ≤ √ε_bias + ε with \\tilde O(ε^{−1.5}) sample complexity and O(ε^{−1}) iteration complexity, improving on the classical \\tilde Ω(ε^{−2}) lower bound.","tokens_in":23626,"tokens_out":8719,"duration_ms":85267,"significance":"If the theorem holds as stated, this is a significant result: it would be the first quantum speedup for model-free infinite-horizon policy gradient optimization with general policy parameterization. The paper's main analytical contribution is a bias–variance decomposition for deterministic truncated trajectory estimators, and the proof structure is largely explicit in the appendices. The paper correctly builds on external quantum mean estimation results (Cornelissen et al. 2022; Sidford and Zhang 2024) and shows a leading-order rate that is internally consistent. However, the implementation gap concerning the reward oracle and a register-counting defect in the trajectory oracle construction must be resolved before the central claim can be accepted at face value.","major_comments":[{"comment":"The oracle model defines only the transition oracle U_P, the initial-state oracle U_ρ, and the policy oracle Π; no quantum reward oracle is defined or assumed. Yet the estimator \\hat g_ρ(τ_N|θ) in Eq. (14) requires r(s_n,a_n), and the construction of U_g in Eq. (17) and Appendix A.2 explicitly relies on r(·,·) being classically computable and evaluates it in superposition. If the reward is not available to the learner, Algorithm 1 cannot form \\tilde g_h, and Theorem 3's \\tilde O(ε^{−1.5}) guarantee is not implementable as stated. This also creates an asymmetry with the classical \\tilde Ω(ε^{−2}) MDP-query lower bound, which does not grant analytic knowledge of the reward. The authors need to add a quantum reward oracle to the model and count its queries, or state and defend a different modeling assumption; the rate claim cannot be evaluated until this is resolved.","section":"Section 2.3 and Appendix A.2, Eqs. (4)–(6), (14), (17)"},{"comment":"The construction of U_P(τ_N) allocates N state registers S_0, …, S_{N−1}, but at step t = N−1 the transition oracle U_P writes a superposition over s_N into register S_N, which has not been allocated. The final amplitude includes P(s_N|s_{N−1},a_{N−1}) without a corresponding register, so the unitary is ill-defined as written. Adding an (N+1)-th state register fixes the construction and preserves the O(N) query count, but as written Lemma 4 is not established for the stated registers.","section":"Appendix A.1, Eq. (7)"},{"comment":"The proof of Lemma 5 derives ||E[\\tilde F_h] − F_ρ(θ)||^2 ≤ G^4 γ^{2N}/(1−γ)^2, whereas the lemma statement (33) gives G^4 γ^{2N}. These cannot both be correct: since δ_F = G^2 γ^N from Theorem 1, the squared bias bound should be G^4 γ^{2N}. The proof needs correction, and the constants flowing from this bound into Lemma 6 should be rechecked.","section":"Appendix D, Eq. (58)"},{"comment":"Lemma 6 states the condition α ≤ μ_F/(56G^4), while the proof requires α ≤ μ_F/[4(6σ_F^2 + 6δ_F^2 + 2G^4)]. For the parameter choices in Theorem 3, σ_F^2 and δ_F^2 tend to 0 as ε tends to 0, so the stated condition is sufficient for the asymptotic rate, but the mismatch between the lemma statement and the proof should be cleaned up and the exact dependency on σ_F, σ_g should be made explicit.","section":"Lemma 6 and Theorem 3"}],"minor_comments":[{"comment":"The definition of ω*_θ writes arg max over L^ν_{π_θ^ρ}(ω, θ), but Eq. (12) defines L as a minimization objective; this should be arg min.","section":"Eq. (24)"},{"comment":"The notation ∇_ω \\tilde L(ω, τ_N) retains an explicit dependence on τ_N, but the quantities \\tilde F_h and \\tilde g_h are already Monte-Carlo estimates over trajectories; using τ_N here is confusing.","section":"Algorithm 1, line 7"},{"comment":"The variance bound Var(\\hat g_ρ) ≤ dG^2/(1−γ)^4 is conservative: the pointwise norm bound ||\\hat g_ρ|| ≤ G/(1−γ)^2 already gives a d-independent bound. Since the d factor enters the final complexity through Lemma 1, the authors should state which variance convention is used and confirm the dimension dependence is intentional.","section":"Theorem 1, Eq. (30)"},{"comment":"The statement that this is the first quantum model-free RL algorithm with theoretical guarantees is too strong given existing quantum policy gradient and tabular QRL results; it should be qualified to general-parameterization infinite-horizon policy gradient methods.","section":"Section 1.1"}],"recommendation":"major_revision","confidential_remarks":"The reward-oracle gap is the main obstacle to accepting the central claim. If the authors add a quantum reward oracle to the model, count its queries, and fix the register and Lemma 5 proof defects, the \\tilde O(ε^{−1.5}) rate may be recoverable. The comparison to the classical lower bound should also be stated carefully once reward access is specified, since the classical lower bound does not grant analytic reward knowledge."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. First, if the main theorem holds, it is a genuine milestone: the first quantum sample-complexity speedup for general-parameterization, model-free, infinite-horizon policy gradient RL, with the oracle complexity dropping from tilde O(eps^-2) to tilde O(eps^-1.5). Second, the paper as written has a modeling gap that must be fixed before that claim is fully implementable: the quantum oracle model in Section 2.3 defines only transition, initial-state, and policy oracles, but the gradient estimator in Eq. (14) uses r(s,a), and building U_g in Eq. (17) requires evaluating the reward in superposition. Appendix A.2 just asserts r is classically computable. That is a real unstated assumption, and it makes the comparison with the classical MDP-query lower bound unfair as stated. The fix is straightforward: add a reward oracle U_r to the model and count its queries. Then the speedup claim is clean. What is genuinely new: the deterministic fixed-truncation NPG estimator, the exponential-bias analysis (Theorem 1 and Lemma 5), and the coherent construction of the Fisher and gradient oracles. The outer-loop analysis is standard classical NPG from Mondal and Aggarwal, and the inner-loop speedup is imported from Sidford-Zhang quantum variance reduction, but the truncation bias analysis is the real technical work and it mostly holds together. The proof structure is careful and the rate bookkeeping in Theorem 3 is internally consistent at leading order. The soft spots are proportionate and fixable. The missing S_N register in Appendix A.1 is a typo-level bug. The Lemma 5 proof has a bound that differs from the lemma statement by a (1-gamma)^-2 factor. Lemma 6's statement uses alpha <= mu_F/(56 G^4) while the proof uses a different condition. And the novelty claim should be sharpened against Jerbi et al. 2023, whose title overlaps substantially. None of these destroy the central idea, but all need to be addressed before the result is accepted as stated. This paper is for the quantum RL theory community and anyone tracking the boundary between quantum and classical optimization speedups. It deserves a serious referee. I would send it to peer review with a request for revision addressing the oracle model and the technical details above. My take is the result is likely true in essence; the current write-up is not yet the definitive version.","headline":"Serious, plausible result with a fixable oracle-model gap: the stated quantum access model has no reward oracle, but the gradient estimator needs reward values.","tokens_in":704,"tokens_out":960,"would_cite":false,"duration_ms":34332,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","90C40","68T05","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a quantum natural policy gradient algorithm with deterministic truncated estimators and quantum mean estimation achieves $\\tilde{\\mathcal{O}}(\\epsilon^{-1.5})$ sample complexity for model-free infinite-horizon…","keywords":["quantum reinforcement learning","natural policy gradient","quantum mean estimation","sample complexity","Markov decision process","model-free","quantum oracle","policy gradient"],"falsifier":"Check whether a reward unitary is available: Section 2.3 defines only $U_P$, $U_\\rho$, and $\\Pi$, while Eq. (14) requires $r(s_n,a_n)$ and Appendix A.2 assumes it is classically computable. If the reward is accessible only through a black-box oracle, then $U_g$ in Eq. (17) cannot be built from the stated oracles, and Theorem 3's query count omits the reward-query cost; alternatively, simulate Theorem 1's bias bounds (26)-(29) on a small MDP and test whether the truncation bias decays as $O(\\gamma^N)$.","tokens_in":23091,"feed_emoji":"⚛️","tokens_out":11429,"duration_ms":102002,"temperature":0.7,"pith_summary":"The paper claims that quantum access to an MDP's transition and initial-state distributions can accelerate model-free policy gradient reinforcement learning below the classical sample-complexity floor. It introduces the Quantum Natural Policy Gradient (QNPG) algorithm, which replaces random geometric-length trajectory sampling with fixed-length truncated trajectories that can be generated coherently in superposition. Truncation introduces exponentially decaying bias, but quantum mean estimation reduces the variance of the resulting gradient and Fisher information estimates fast enough to yield $\\tilde{\\mathcal{O}}(\\epsilon^{-1.5})$ oracle queries for an $\\epsilon$-optimal policy. If the theorem holds, this is the first quantum speedup for general-parameterization model-free infinite-horizon RL, with the caveat that the algorithm assumes rewards are classically computable from state-action pairs.","feed_headline":"Quantum policy gradient beats the classical sample floor","feed_subtitle":"Quantum mean estimation inside natural policy gradient breaks the classical sample-complexity bound for model-free RL.","key_machinery":"The load-bearing machinery is a coherent quantum embedding of the truncated NPG estimator: a unitary $U_P(\\tau_N)$ prepares a superposition over all length-$N$ trajectories using the initial-state oracle and $O(N)$ calls to the transition and policy oracles, then unitaries $U_F$ and $U_g$ append the Fisher matrix estimate and gradient estimate in superposition. These are combined with QVarianceReduce, a quantum mean-estimation-based variance reduction routine that converts an estimator with variance $L^2$ into one with variance $\\hat{\\sigma}^2$ using $\\tilde{O}(L\\sqrt{d}/\\hat{\\sigma})$ queries. The deterministic truncation in Eqs. (14)-(15) is what makes the whole pipeline implementable in superposition; the resulting bias decays as $O(\\gamma^N)$, which the analysis absorbs by choosing $N=O(\\log(1/\\epsilon))$.","core_discovery":"The central claim is Theorem 3: under Lipschitz and smooth score functions, a bounded compatible function approximation error $\\epsilon_{\\mathrm{bias}}$, and Fisher non-degeneracy, Algorithm 1 with $H=O(\\log(1/\\epsilon))$, $N=O(\\log(1/\\epsilon))$, $K=O(1/\\epsilon)$, $\\hat{\\sigma}_g^2=O(\\epsilon)$, and $\\hat{\\sigma}_F^2=O((1-\\gamma)^4\\epsilon)$ guarantees $J^*_\\rho - (1/K)\\sum_{k=0}^{K-1} E[J_\\rho(\\theta_k)] \\le \\sqrt{\\epsilon_{\\mathrm{bias}}} + \\epsilon$ using $\\tilde{\\mathcal{O}}(\\epsilon^{-1.5})$ quantum oracle queries and $\\tilde{\\mathcal{O}}(\\epsilon^{-1})$ iterations. The speedup comes from replacing classical geometric-length trajectory sampling with deterministic length-$N$ truncation and feeding the resulting estimators into quantum mean estimation, which reduces variance quadratically faster than classical averaging. The authors state this is the first demonstration of a quantum speedup for parameterized model-free infinite-horizon MDPs.","pith_inferences":["In my reading, the reward-access assumption is the soft point: the oracle model in Section 2.3 defines only transition and initial-state oracles, yet Eq. (14) evaluates $r(s_n,a_n)$, and Appendix A.2 fills the gap by assuming rewards, score functions, and discounting are classically computable in superposition. If a future model-free setting hides rewards behind a quantum oracle, each $U_g$ call m","The speedup is a polynomial $\\epsilon^{1/2}$ factor, not exponential; because the outer loop remains classical, further improvement would require a different outer-loop mechanism such as quantum cutting-plane methods, which the paper argues cannot be directly adapted to non-convex RL.","A practical extension is to tune $N$ against the actual bias: the analysis guarantees $N=O(\\log(1/\\epsilon))$, but constants hidden in the $\\tilde{O}$ bounds are not quantified, so an implementation would need to check where truncation bias becomes negligible for a given $\\gamma$.","The same deterministic-estimator-plus-quantum-mean-estimation pattern could be tried for actor-critic or Q-learning updates, but each variant would need its own error decomposition and oracle construction, so it remains an open extension."],"forward_implications":["Model-free policy gradient RL with general policy parameterization can be solved with $\\tilde{\\mathcal{O}}(\\epsilon^{-1.5})$ quantum oracle queries, improving on the classical $\\tilde{\\mathcal{O}}(\\epsilon^{-2})$ lower bound for MDP queries.","The outer loop still needs $\\tilde{\\mathcal{O}}(\\epsilon^{-1})$ iterations; the speedup lives entirely in the inner-loop estimation, making QNPG a hybrid classical-outer, quantum-inner algorithm.","A trajectory length of only $N=O(\\log(1/\\epsilon))$ is sufficient, because the truncation bias decays exponentially in $N$ with rate $\\gamma$.","Under softmax parameterization, where $\\epsilon_{\\mathrm{bias}} = 0$, the guarantee becomes a clean $\\epsilon$-optimal value gap; under expressive neural parameterization the gap inherits the compatible approximation error $\\epsilon_{\\mathrm{bias}}$.","The query count is measured in calls to $U_\\rho$, $U_P$, and $\\Pi$, and Lemma 4 accounts for the $O(N)$ transitions and policy applications inside each superposition sample."],"supporting_citations":[{"why":"Supplies Lemma 1, the near-optimal quantum multivariate mean estimation procedure whose quadratic speedup drives QVarianceReduce.","marker":"(Cornelissen et al., 2022)"},{"why":"Supplies the QVarianceReduce algorithm and the quantum stochastic optimization results that give the inner-loop speedup.","marker":"(Sidford & Zhang, 2024)"},{"why":"Supplies the classical NPG sample-complexity lower bound and the outer-loop error decomposition used in Lemma 3.","marker":"(Mondal & Aggarwal, 2024a)"},{"why":"Supplies the global convergence theory for NPG and the compatible function approximation error $\\epsilon_{\\mathrm{bias}}$ behind Assumption 2.","marker":"(Agarwal et al., 2021)"},{"why":"Supplies the unbiased geometric-length estimators and variance-reduced PG/NPG analysis that QNPG replaces and compares against.","marker":"(Liu et al., 2020)"},{"why":"Supplies the infinite-horizon policy gradient estimator used as the unbiased reference in the truncation-bias proof of Theorem 1.","marker":"(Baxter & Bartlett, 2001)"},{"why":"Supplies the natural actor-critic and compatible-function-approximation quadratic program that defines the inner-loop $\\omega$ update.","marker":"(Peters & Schaal, 2008)"},{"why":"Supplies the quantum-evaluatable policy unitary construction and prior quantum policy gradient framework that the trajectory unitaries build on.","marker":"(Jerbi et al., 2023)"}],"fun_headline_variants":["Quantum NPG cuts sample calls below classical limit","QNPG: first quantum speedup for model-free RL","Quantum natural gradient hits epsilon^-1.5 sample complexity","Truncation trick brings quantum speedup to policy gradients","Quantum mean estimation speeds up policy gradient sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee assumes the reward of any state-action pair is known classically to the learner, so it can be encoded coherently into the gradient and Fisher estimators; the quantum model stated in the paper alone, with only transition and initial-state oracles, does not provide reward access.","fun_headline_variants_meta":{"raw":{"variants":["Quantum NPG cuts sample calls below classical limit","QNPG: first quantum speedup for model-free RL","Quantum natural gradient hits epsilon^-1.5 sample complexity","Truncation trick brings quantum speedup to policy gradients","Quantum mean estimation speeds up policy gradient sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000726,"raw_usage":{"total_tokens":3235,"prompt_tokens":905,"completion_tokens":2330,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":2253}},"tokens_in":521,"tokens_out":2330,"duration_ms":17805,"temperature":1.0,"reasoning_tokens":2253,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T13:37:33.545276+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check whether a reward unitary is available: Section 2.3 defines only $U_P$, $U_\\rho$, and $\\Pi$, while Eq. (14) requires $r(s_n,a_n)$ and Appendix A.2 assumes it is classically computable. If the reward is accessible only through a black-box oracle, then $U_g$ in Eq. (17) cannot be built from the stated oracles, and Theorem 3's query count omits the reward-query cost; alternatively, simulate Theorem 1's bias bounds (26)-(29) on a small MDP and test whether the truncation bias decays as $O(\\gamma^N)$.","supporting_citations":[{"cited_title":"Near-optimal quantum algorithms for multivariate mean estimation","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 1, the near-optimal quantum multivariate mean estimation procedure whose quadratic speedup drives QVarianceReduce."},{"cited_title":"and Zhang, C","cited_arxiv_id":null,"evidence_quote":"Supplies the QVarianceReduce algorithm and the quantum stochastic optimization results that give the inner-loop speedup."},{"cited_title":"An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods","cited_arxiv_id":null,"evidence_quote":"Supplies the unbiased geometric-length estimators and variance-reduced PG/NPG analysis that QNPG replaces and compares against."},{"cited_title":"and Bartlett, P","cited_arxiv_id":null,"evidence_quote":"Supplies the infinite-horizon policy gradient estimator used as the unbiased reference in the truncation-bias proof of Theorem 1."},{"cited_title":"and Schaal, S","cited_arxiv_id":null,"evidence_quote":"Supplies the natural actor-critic and compatible-function-approximation quadratic program that defines the inner-loop $\\omega$ update."},{"cited_title":"Quantum policy gradient algorithms","cited_arxiv_id":null,"evidence_quote":"Supplies the quantum-evaluatable policy unitary construction and prior quantum policy gradient framework that the trajectory unitaries build on."}],"review_version":1}