mlsanityData to 14 Oct 2026

Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

arXiv 2608.02826 ↗First posted 3 Aug 2026quant-ph cs.AI cs.LGcited by 0

On the map: Deep reinforcement learning methods → Quantum reinforcement learning

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Quantum reinforcement learning, one of 15 directions in Deep reinforcement learning methods. Builds on 17 of its 54 references that are in the map. First posted on arXiv 3 Aug 2026.

Builds on

17 of 54 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model30 Jul

Other references · 16

  1. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  2. 2016Quantum Recommendation Systemscited by 70
  3. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  4. 2018q-means: A quantum algorithm for unsupervised machine learningcited by 55
  5. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  6. 2022Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learningcited by 21
  7. 2016Reinforcement Learning Using Quantum Boltzmann Machinescited by 20
  8. 2021Quantum Sub-Gaussian Mean Estimatorcited by 15
  9. 2022Quantum policy gradient algorithmscited by 15
  10. 2017Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Timecited by 11
  11. 2021Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraintscited by 11
  12. 2018Quantum Chebyshev's Inequality and Applicationscited by 10
4 more
  1. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  2. 2013Artificial Intelligence Framework for Simulating Clinical Decision-Making: A Markov Decision Process Approachcited by 8
  3. 2022Mean estimation when you have the source code; or, quantum Monte Carlo methodscited by 6
  4. 2023Do you know what q-means?cited by 6

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory search
  2. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach
  3. 2025Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environments
  4. 2026Reinforcement learning for quantum processes with memory
  5. 2026Reinforcement Learning for Quantum Technology
  6. 2025From Classical Data to Quantum Advantage -- Quantum Policy Evaluation on Quantum Hardware
  7. 2026Towards Surrogate Based Dequantization of Quantum Reinforcement Learning
  8. 2024An Introduction to Quantum Reinforcement Learning (QRL)