# Quantum Algorithms for Reinforcement Learning with a Generative Model

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 48 references that are in the map.
- First posted on arXiv 15 Dec 2021.

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

- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Quantum-enhanced machine learning](https://mlsanity.com/paper/1610.08251/) (2016)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Quantum exploration algorithms for multi-armed bandits](https://mlsanity.com/paper/2007.07049/) (2020)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Quantum Chebyshev's Inequality and Applications](https://mlsanity.com/paper/1807.06456/) (2018)
- [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms](https://mlsanity.com/paper/1807.05209/) (2018)

## Built on by (most cited first, 24 of 24)

- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Quantum Deep Hedging](https://mlsanity.com/paper/2303.16585/) (2023)
- [Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning](https://mlsanity.com/paper/2206.04741/) (2022)
- [Quantum Reinforcement Learning via Policy Iteration](https://mlsanity.com/paper/2203.01889/) (2022)
- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [Quantum policy gradient algorithms](https://mlsanity.com/paper/2212.09328/) (2022)
- [Generative Models in Decision Making: A Survey](https://mlsanity.com/paper/2502.17100/) (2025)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Benchmarking Quantum Reinforcement Learning](https://mlsanity.com/paper/2501.15893/) (2025)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning](https://mlsanity.com/paper/2302.08617/) (2023)
- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (2025)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)
- [Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory search](https://mlsanity.com/paper/2412.18208/) (2024)
- [QSpeech: Low-Qubit Quantum Speech Application Toolkit](https://mlsanity.com/paper/2205.13221/) (2022)
- [Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environments](https://mlsanity.com/paper/2507.18606/) (2025)
- [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)
- [Scalable Quantum Reinforcement Learning on NISQ Devices with Dynamic-Circuit Qubit Reuse and Grover Optimization](https://mlsanity.com/paper/2509.16002/) (2025)
- [Unclonability and Quantum Cryptanalysis: From Foundations to Applications](https://mlsanity.com/paper/2210.17545/) (2022)
- [From Classical Data to Quantum Advantage -- Quantum Policy Evaluation on Quantum Hardware](https://mlsanity.com/paper/2509.07614/) (2025)
- [Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model](https://mlsanity.com/paper/2608.02826/) (2026)
- [Quantum Monte Carlo Tree Search with Fixed Confidence](https://mlsanity.com/paper/2609.33132/) (2026)

## Abstract (arXiv)

Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a γ-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy (π^*), the optimal value function (v^*), and the optimal Q-function (q^*), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy (ε) and two main parameters of the MDP: the effective time horizon (frac11-γ) and the size of the action space (A). Moreover, we show that our quantum algorithm for computing q^* is optimal by proving a matching quantum lower bound.