Pith. sign in

REVIEW 3 major objections 4 minor 59 references

Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2608.02826 v1 pith:RW7LLCLW submitted 2026-08-03 quant-ph cs.AIcs.LGstat.ML

Joao F. Doriguello This is my paper · ORCID
classification quant-phcs.AIcs.LGstat.ML MSC 68Q1290C40
keywords reinforcementlearningMarkovdecisionprocessesgenerativemodelquantumalgorithmsvalueiterationmeanestimationmaximumfindingquerycomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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)$.

Load-bearing premise

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 √Γ.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Sec. 3, proof of Theorem 1, Eq. (2); Sec. 4, proof of Theorem 2, Eq. (4)] 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.
  2. [Algorithm 1, line 7 vs. Eq. (3); Algorithm 2, line 7 vs. Eq. (5)] 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.
  3. [Sec. 3, Fact 3; Sec. 4, Lemma 1] 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.
minor comments (4)
  1. [Algorithm 2, Output and return statement] 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.
  2. [Algorithm 2, line 1] 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.
  3. [Theorem 2, query complexity statement] 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.
  4. [Algorithm 1, line 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new query-complexity upper bounds are derived from external lemmas (Fact 1, Fact 2, Fact 3) and a self-contained discounted total-variance bound (Lemma 1), so the central claims are not assumed as inputs.

full rationale

The derivation chain for both theorems is parameter-free and self-contained apart from standard external subroutines. Theorem 1 combines Fact 1 (Dürr–Høyer maximum finding, ref. [17]), Fact 2 (Kothari–O'Donnell mean estimation with variance, ref. [36]), and Fact 3 (Sidford et al. total-variance bound, ref. [50]); Theorem 2 uses the same ingredients plus Lemma 1, whose proof is given in the paper. The only self-citation to the author's earlier work, ref. [4] (Ambainis–Doriguello–Lim), is used to state the previous upper bound that the new results improve and to describe the prior algorithm; it is not used to justify the new construction or to forbid alternatives. No parameter is fitted to data and then called a prediction; the advertised accuracies and query counts follow from the stated error bounds in Equation (3)/Equation (5), the one-sided shift pµ, and the total-variance lemmas. The fragile step — the claim that Fact 2 can be run coherently without intermediate measurements — is an unproved technical assertion and the pseudocode/proof constant mismatch is a correctness concern, but neither makes the result equal to its inputs by construction. Because the proof does not define any quantity in terms of the target theorem and the main imported lemmas are from non-self references, there is no circularity; score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No data are fitted. The central claim is a query-complexity upper bound over a fixed oracle model; the only 'parameters' are analysis constants chosen to satisfy error budgets. The main auxiliary assumptions are external theorems (quantum max finding, quantum mean estimation with variance, the Sidford et al. total-variance lemma) and the model-level assumption of a quantum-accessible environment.

assumptions (6)
  • domain assumption A quantum-accessible environment oracle Q_p and its inverse are available for the transition kernel p, and the reward function is known.
    Section 1.1.2 defines Q_p; all query complexities count queries to Q_p and Q_p†. If only a classical simulator is available, the ability to build Q_p with the same efficiency is assumed.
  • standard math Quantum maximum finding (Fact 1, Dürr-Høyer) finds the maximum of a set with O(√S log(1/δ)) queries.
    External theorem, used in Algorithm 1 step 2, Algorithm 2 step 2, and in each iteration of both algorithms.
  • standard math Quantum mean estimation with variance (Fact 2, Kothari-O'Donnell 2023) provides |μ̂-μ| ≤ √σ ε with O(1/ε log(1/δ)) queries.
    External theorem; the entire algorithm nests this subroutine inside quantum maximum finding.
  • ad hoc to paper Fact 2 can be executed coherently in superposition without intermediate measurements, over a superposition of actions a.
    Assumed in the proof of Theorem 1 ('We claim that Fact 2 can be adapted...') and used to construct the oracle for quantum maximum finding; no circuit-level derivation is given.
  • domain assumption The total-variance lemma (Fact 3, Sidford et al. [50, Lemma F.4]) bounds the accumulated variance-weighted error by H^{3/2}.
    Imported from the classical MDP literature and not re-proved; the paper only notes a typo in the original statement. The H^{2.5} claim depends on it.
  • standard math Bellman operators are monotone and contractive or nonexpansive, and value iteration converges to the optimal value function.
    Standard MDP theory, Section 2.2, used throughout the correctness proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model." pith.science (2026). https://pith.science/paper/RW7LLCLW

@misc{pith2026260802826,
  author       = {Pith},
  title        = {Pith review of: Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RW7LLCLW}},
  note         = {Machine review of arXiv:2608.02826}
}
read the original abstract

Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard approach to study such interaction is through Markov Decision Processes (MDPs) and the task of choosing an optimal policy --- a function that tells the agent which action to take. In this work, we study two types of MDPs --- finite-horizon and infinite-horizon discounted --- and propose new quantum algorithms for computing approximate optimal policies. Our quantum algorithms are based on a new combination of standard value iteration and quantum subroutines like quantum mean estimation and quantum maximum finding, overall enhanced with techniques from sample-optimal classical algorithms. Our resulting query complexities improve upon previous works, thus approaching already established quantum lower bounds.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 55 canonical work pages

  1. [50]

    Near-optimal time and sample complexities for solving Markov decision processes with a generative model

    Aaron Sidford, Mengdi Wang, Xian Wu, Lin Yang, and Yinyu Ye. Near-optimal time and sample complexities for solving Markov decision processes with a generative model. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors,Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. 2, 3...

    work page 2018

  2. [1]

    Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I

    Rajeev Acharya, Dmitry A. Abanin, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Ander- sen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourass...

    work page 2025

  3. [2]

    An introduction to quantum machine learning: from quantum logic to quantum deep learning.Quantum Machine Intelligence, 3(2):28, Nov 2021

    Leonardo Alchieri, Davide Badalotti, Pietro Bonardi, and Simone Bianco. An introduction to quantum machine learning: from quantum logic to quantum deep learning.Quantum Machine Intelligence, 3(2):28, Nov 2021. 1

    work page 2021

  4. [3]

    Doriguello, Alessandro Luongo, and Miklos Santha

    Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, and Miklos Santha. Constant-depth circuits for Boolean functions and quantum memory devices using multi- qubit gates.Quantum, 8:1530, November 2024. 6

    work page 2024

  5. [4]

    A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

    Andris Ambainis, Joao F Doriguello, and Debbie Lim. A bit of freedom goes a long way: Classical and quantum algorithms for reinforcement learning under a generative model. arXiv preprint arXiv:2507.22854, 2025. 1, 4, 5, 8, 9

    work page Pith review arXiv 2025

  6. [5]

    Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Bur- kett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, ...

    work page 2019

  7. [6]

    Optimal control of Markov processes with incomplete state information I.Journal of mathematical analysis and applications, 10:174–205, 1965

    Karl Johan ˚Astr¨ om. Optimal control of Markov processes with incomplete state information I.Journal of mathematical analysis and applications, 10:174–205, 1965. 1

    work page 1965

  8. [7]

    Springer Science & Business Media, 2011

    Nicole B¨ auerle and Ulrich Rieder.Markov decision processes with applications to finance. Springer Science & Business Media, 2011. 1

    work page 2011

Show all 59 references
  1. [8]

    Artificial intelligence framework for simulating clinical decision-making: A Markov decision process approach.Artificial intelligence in medicine, 57(1):9–19, 2013

    Casey C Bennett and Kris Hauser. Artificial intelligence framework for simulating clinical decision-making: A Markov decision process approach.Artificial intelligence in medicine, 57(1):9–19, 2013. 1

    2013

  2. [9]

    Athena scientific, 2012

    Dimitri Bertsekas.Dynamic programming and optimal control: Volume I, volume 4. Athena scientific, 2012. 1

    2012

  3. [10]

    Athena Scientific, 2022

    Dimitri Bertsekas.Abstract dynamic programming. Athena Scientific, 2022. 1, 3

    2022

  4. [11]

    Quantum machine learning.Nature, 549(7671):195–202, Sep 2017

    Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning.Nature, 549(7671):195–202, Sep 2017. 1

    2017

  5. [12]

    Distributed autonomous virtual resource management in datacenters using finite-Markov decision process

    Liuhua Chen, Haiying Shen, and Karan Sapra. Distributed autonomous virtual resource management in datacenters using finite-Markov decision process. InProceedings of the ACM Symposium on Cloud Computing, pages 1–13, 2014. 1

    2014

  6. [13]

    Quantum algorithms and lower bounds for linear regres- sion with norm constraints.arXiv preprint arXiv:2110.13086, 2021

    Yanlin Chen and Ronald de Wolf. Quantum algorithms and lower bounds for linear regres- sion with norm constraints.arXiv preprint arXiv:2110.13086, 2021. 11

    2021 arXiv

  7. [14]

    Oberoi, and Pooya Ron- agh

    Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, and Pooya Ron- agh. Reinforcement learning using quantum boltzmann machines.Quantum Info. Comput., 18(1–2):51–74, February 2018. 1 18

    2018

  8. [15]

    Quantum reinforcement learning.IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38(5):1207–1220, 2008

    Daoyi Dong, Chunlin Chen, Hanxiong Li, and Tzyh-Jong Tarn. Quantum reinforcement learning.IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 38(5):1207–1220, 2008. 1

    2008

  9. [16]

    Do you know what q-means?arXiv preprint arXiv:2308.09701, 2023

    Jo˜ ao F Doriguello, Alessandro Luongo, and Ewin Tang. Do you know what q-means?arXiv preprint arXiv:2308.09701, 2023. 1

    2023 arXiv

  10. [17]

    A quantum algorithm for finding the minimum.arXiv preprint quant-ph/9607014, 1996

    Christoph D¨ urr and Peter Høyer. A quantum algorithm for finding the minimum.arXiv preprint quant-ph/9607014, 1996. 4, 6

    1996 arXiv

  11. [18]

    Springer Science & Business Media, 2012

    Eugene A Feinberg and Adam Shwartz.Handbook of Markov decision processes: methods and applications, volume 40. Springer Science & Business Media, 2012. 1

    2012

  12. [19]

    Mohammad Gheshlaghi Azar, R´ emi Munos, and Hilbert J. Kappen. Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.Machine Learning, 91(3):325–349, Jun 2013. 2, 5

    2013

  13. [20]

    Architectures for a quantum random access memory.Phys

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for a quantum random access memory.Phys. Rev. A, 78:052310, Nov 2008. 6

    2008

  14. [21]

    Quantum random access memory

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100:160501, Apr 2008. 6

    2008

  15. [22]

    A fast quantum mechanical algorithm for database search

    Lov K Grover. A fast quantum mechanical algorithm for database search. InProceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996. 1

    1996

  16. [23]

    Theses, Universit´ e Paris Cit´ e, July 2021

    Yassine Hamoudi.Quantum Algorithms for the Monte Carlo Method. Theses, Universit´ e Paris Cit´ e, July 2021. 4

    2021

  17. [24]

    Quantum Sub-Gaussian Mean Estimator

    Yassine Hamoudi. Quantum Sub-Gaussian Mean Estimator. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors,29th Annual European Symposium on Algorithms (ESA 2021), volume 204 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:17, Dagstuhl, Germany...

    2021

  18. [25]

    Quantum Chebyshev’s Inequality and Applica- tions

    Yassine Hamoudi and Fr´ ed´ eric Magniez. Quantum Chebyshev’s Inequality and Applica- tions. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors,46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 13...

    2019

  19. [26]

    Harrow, Avinatan Hassidim, and Seth Lloyd

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations.Phys. Rev. Lett., 103:150502, Oct 2009. 1

    2009

  20. [27]

    Springer Science & Business Media, 2007

    Qiying Hu and Wuyi Yue.Markov decision processes with their applications, volume 14. Springer Science & Business Media, 2007. 1

    2007

  21. [28]

    Samuel Jaques and Arthur G. Rattew. QRAM: A Survey and Critique.Quantum, 9:1922, December 2025. 6

    1922

  22. [29]

    Quantum Policy Gra- dient Algorithms

    Sofiene Jerbi, Arjan Cornelissen, Maris Ozols, and Vedran Dunjko. Quantum Policy Gra- dient Algorithms. In Omar Fawzi and Michael Walter, editors,18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), vol- ume 266 ofLeibniz Internation...

    2023

  23. [30]

    Uni- versity of London, University College London (United Kingdom), 2003

    Sham Machandranath Kakade.On the sample complexity of reinforcement learning. Uni- versity of London, University College London (United Kingdom), 2003. 2

    2003

  24. [31]

    Michael Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for near-optimal planning in large Markov decision processes.Machine Learning, 49(2):193– 208, Nov 2002. 2

    2002

  25. [32]

    Finite-sample convergence rates for Q-learning and indirect algorithms.Advances in neural information processing systems, 11, 1998

    Michael Kearns and Satinder Singh. Finite-sample convergence rates for Q-learning and indirect algorithms.Advances in neural information processing systems, 11, 1998. 2

    1998

  26. [33]

    Finite-sample convergence rates for Q-learning and indirect algorithms

    Michael Kearns and Satinder Singh. Finite-sample convergence rates for Q-learning and indirect algorithms. In M. Kearns, S. Solla, and D. Cohn, editors,Advances in Neural Information Processing Systems, volume 11. MIT Press, 1998. 2

    1998

  27. [34]

    q-means: A quantum algorithm for unsupervised machine learning

    Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash. q-means: A quantum algorithm for unsupervised machine learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch´ e-Buc, E. Fox, and R. Garnett, editors,Advances in Neural In- formation Processing...

    2019

  28. [35]

    Quantum Recommendation Systems

    Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In Chris- tos H. Papadimitriou, editor,8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, Dagstu...

    2017

  29. [36]

    Mean estimation when you have the source code; or, quantum Monte Carlo methods

    Robin Kothari and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1186–1215, 2023. 4, 5, 6, 9, 13

    2023

  30. [37]

    Breaking the sample size barrier in model-based reinforcement learning with a generative model

    Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors,Advances in Neural Information Processing Syst...

    2020

  31. [38]

    Quantum algorithms for supervised and unsupervised machine learning.arXiv preprint arXiv:1307.0411, 2013

    Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning.arXiv preprint arXiv:1307.0411, 2013. 1

    2013 arXiv

  32. [39]

    Bin Luo, Yuwen Huang, Jonathan Allcock, Xiaojun Lin, Shengyu Zhang, and John C.S. Lui. Quantum algorithms for finite-horizon Markov decision processes. InForty-second International Conference on Machine Learning, 2025. 4, 5, 8, 9

    2025

  33. [40]

    Quantum speedup of Monte Carlo methods.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015

    Ashley Montanaro. Quantum speedup of Monte Carlo methods.Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015. 4

    2015

  34. [41]

    Springer Nature, 2022

    Mausam Natarajan and Andrey Kolobov.Planning with Markov decision processes: An AI perspective. Springer Nature, 2022. 1

    2022

  35. [42]

    Cambridge university press, 2010

    Michael A Nielsen and Isaac L Chuang.Quantum computation and quantum information. Cambridge university press, 2010. 1, 4, 6

    2010

  36. [43]

    John Wiley & Sons, 2007

    Warren B Powell.Approximate Dynamic Programming: Solving the curses of dimension- ality, volume 703. John Wiley & Sons, 2007. 1

    2007

  37. [44]

    John Wiley & Sons, 2014

    Martin L Puterman.Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. 1, 2, 3, 4, 8, 12 20

    2014

  38. [45]

    Quantum support vector machine for big data classification.Phys

    Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification.Phys. Rev. Lett., 113:130503, Sep 2014. 1

    2014

  39. [46]

    Saggio, B

    V. Saggio, B. E. Asenbeck, A. Hamann, T. Str¨ omberg, P. Schiansky, V. Dunjko, N. Friis, N. C. Harris, M. Hochberg, D. Englund, S. W¨ olk, H. J. Briegel, and P. Walther. Exper- imental quantum speed-up in reinforcement learning agents.Nature, 591(7849):229–233, Mar 2021. 1

    2021

  40. [47]

    Markov models in health care.Einstein (S˜ ao Paulo), 8:376–379, 2010

    Renato Cesar Sato and D´ esir´ ee Moraes Zouain. Markov models in health care.Einstein (S˜ ao Paulo), 8:376–379, 2010. 1

    2010

  41. [48]

    An introduction to quantum machine learning.Contemporary Physics, 56(2):172–185, 2015

    Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning.Contemporary Physics, 56(2):172–185, 2015. 1

    2015

  42. [49]

    P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134,

  43. [51]

    Variance reduced value iteration and faster algorithms for solving Markov decision processes

    Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye. Variance reduced value iteration and faster algorithms for solving Markov decision processes. InProceedings of the Twenty- Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, page 770–787, USA, 2018. Society for ...

    2018

  44. [52]

    Markov decision processes for screening and treat- ment of chronic diseases.Markov Decision Processes in Practice, pages 189–222, 2017

    Lauren N Steimle and Brian T Denton. Markov decision processes for screening and treat- ment of chronic diseases.Markov Decision Processes in Practice, pages 189–222, 2017. 1

    2017

  45. [53]

    MIT press Cambridge, 1998

    Richard S Sutton and Andrew G Barto.Reinforcement learning: An introduction. MIT press Cambridge, 1998. 1

    1998

  46. [54]

    Synthesis Lectures on Artificial Intelligence and Machine Learning

    Csaba Szepesv´ ari.Algorithms for Reinforcement Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning. Springer Cham, 2010. 1

    2010

  47. [55]

    Quantum algorithms for reinforcement learning with a generative model

    Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, and Martin Roetteler. Quantum algorithms for reinforcement learning with a generative model. InInternational Conference on Machine Learning, pages 10916–10926. PMLR, 2021. 3, 4, 5, 13

    2021

  48. [56]

    Randomized linear programming solves the discounted Markov de- cision problem in nearly-linear (sometimes sublinear) running time.arXiv preprint arXiv:1704.01869, 2017

    Mengdi Wang. Randomized linear programming solves the discounted Markov de- cision problem in nearly-linear (sometimes sublinear) running time.arXiv preprint arXiv:1704.01869, 2017. 2

    2017 arXiv

  49. [57]

    Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum algorithms for nearest- neighbor methods for supervised and unsupervised learning.Quantum Info. Comput., 15(3–4):316–356, March 2015. 1

    2015

  50. [58]

    Simon Wiedemann, Daniel Hein, Steffen Udluft, and Christian B. Mendl. Quantum policy iteration via amplitude estimation and Grover search – towards quantum advantage for reinforcement learning.Transactions on Machine Learning Research, 2023. 3 21

    2023

  51. [59]

    Provably efficient exploration in quantum reinforcement learning with logarithmic worst-case regret

    Han Zhong, Jiachen Hu, Yecheng Xue, Tongyang Li, and Liwei Wang. Provably efficient exploration in quantum reinforcement learning with logarithmic worst-case regret. InPro- ceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org,

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.