mlsanityData to 7 Oct 2026

Quantum Algorithms for Reinforcement Learning with a Generative Model

arXiv 2112.08451 ↗First posted 15 Dec 2021quant-ph cs.LGcited by 24

Not on the map. Why?

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.

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

Builds on

11 of 48 references.

References · 11

  1. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  2. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  3. 2016Quantum-enhanced machine learningcited by 79
  4. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  5. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  6. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 52
  7. 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
  8. 2020Quantum exploration algorithms for multi-armed banditscited by 22
  9. 2021Quantum Sub-Gaussian Mean Estimatorcited by 15
  10. 2018Quantum Chebyshev's Inequality and Applicationscited by 10
  11. 2018Quantum Speedups for Exponential-Time Dynamic Programming Algorithmscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 6; 2024: 1; 2025: 8; 2026: 2.

24 papers.

Sort:

  1. 2022A Survey on Quantum Reinforcement Learningcited by 50
  2. 2023Quantum Deep Hedgingcited by 22
  3. 2022Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learningcited by 21
  4. 2022Quantum Reinforcement Learning via Policy Iterationcited by 19
  5. 2022Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regretscited by 19
  6. 2022Quantum policy gradient algorithmscited by 15
  7. 2025Generative Models in Decision Making: A Surveycited by 14
  8. 2023Quantum Bayesian Optimizationcited by 12
  9. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  10. 2025Benchmarking Quantum Reinforcement Learningcited by 9
  11. 2023Quantum Heavy-tailed Banditscited by 7
  12. 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6
12 more
  1. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  2. 2025Quantum Lipschitz Banditscited by 4
  3. 2023Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processescited by 3
  4. 2024Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory searchcited by 3
  5. 2022QSpeech: Low-Qubit Quantum Speech Application Toolkitcited by 1
  6. 2025Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environmentscited by 1
  7. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  8. 2025Scalable Quantum Reinforcement Learning on NISQ Devices with Dynamic-Circuit Qubit Reuse and Grover Optimizationcited by 1
  9. 2022Unclonability and Quantum Cryptanalysis: From Foundations to Applicationscited by 0
  10. 2025From Classical Data to Quantum Advantage -- Quantum Policy Evaluation on Quantum Hardwarecited by 0
  11. 2026Improved Quantum Algorithms for Reinforcement Learning Under a Generative Modelcited by 0
  12. 2026Quantum Monte Carlo Tree Search with Fixed Confidencecited by 0