# Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

arXiv: https://arxiv.org/abs/2608.02826 · HTML: https://mlsanity.com/paper/2608.02826/

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

## Placed in

- Deep reinforcement learning methods / [Quantum reinforcement learning](https://mlsanity.com/deeprl/quantum-reinforcement-learning/)

## Builds on (most cited first, 17 of 17)

- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning](https://mlsanity.com/paper/2206.04741/) (2022)
- [Reinforcement Learning Using Quantum Boltzmann Machines](https://mlsanity.com/paper/1612.05695/) (2016)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Quantum policy gradient algorithms](https://mlsanity.com/paper/2212.09328/) (2022)
- [Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time](https://mlsanity.com/paper/1704.01869/) (2017)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Chebyshev's Inequality and Applications](https://mlsanity.com/paper/1807.06456/) (2018)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Artificial Intelligence Framework for Simulating Clinical Decision-Making: A Markov Decision Process Approach](https://mlsanity.com/paper/1301.2158/) (2013)
- [Mean estimation when you have the source code; or, quantum Monte Carlo methods](https://mlsanity.com/paper/2208.07544/) (2022)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)

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