Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

2026/08/03 by Joao F. Doriguello
Physics and Astronomy · Computer Science · Mathematics · #quant-ph #cs.AI #cs.LG #stat.ML

paper · pdf

22 pages. Comments welcome

arxiv created 2026/08/03 · arxiv updated 2026/08/05

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.

Citations

• Quantum Algorithms for Finite-horizon Markov Decision Processes
• A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
• Do you know what q-means?
• QRAM: A Survey and Critique
• Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret
• Mean estimation when you have the source code; or, quantum Monte Carlo methods
• Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning
• Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• Quantum Recommendation Systems
• Quantum speedup of Monte Carlo methods
• An introduction to quantum machine learning
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum algorithm for solving linear systems of equations
• Quantum Reinforcement Learning
• Architectures for a quantum random access memory
• Quantum random access memory
• A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes
• A Quantum Algorithm for Finding the Minimum
• A fast quantum mechanical algorithm for database search
• A fast quantum mechanical algorithm for database search
• Algorithms for quantum computation: discrete logarithms and factoring
• Reinforcement Learning: An Introduction