Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.02826

Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

Joao F. Doriguello

quant-phcs.AIcs.LGstat.MLSubmitted Aug 3, 2026• Announced Aug 5, 2026• 1 citation
arXivHTMLPDF

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.

Comments
22 pages. Comments welcome

Related papers

Quantum Algorithms for Reinforcement Learning with a Generative Model

Daochen Wang, Aarthi Sundaram, Robin Kothari +2 more

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 ($\frac{1}{1-γ}$) 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.

arXiv:2112.08451•Dec 15, 2021•20 citations

A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

Andris Ambainis, João Fernando Doriguello, Debbie Lim

Abstract We propose novel classical and quantum online algorithms for learning finite- and infinite-horizon Markov Decision Processes (MDPs). Our algorithms are based on a hybrid online-offline reinforcement learning model wherein the agent can, from time to time, freely interact with the environment in a generative sampling fashion, i.e., by having access to a ''simulator''. By employing known classical and new quantum algorithms for approximating optimal policies under a generative model within our learning algorithms, we show that it is possible to avoid several paradigms from RL like ''optimism in the face of uncertainty'' and ''posterior sampling'' and instead compute and use optimal policies directly, which yields better regret bounds compared to previous works. Our quantum algorithms obtain regret bounds which only a $\operatorname{poly}\log{T}$ dependence on the number of time steps T , thus breaking the $O(\sqrt{T})$ classical barrier. Our infinite-horizon discounted regret bound is brand new, while in the finite- and infinite-horizon undiscounted settings, our results match the time dependence of some prior quantum works, but with improved dependence on other parameters like state space size S and action space size A .

arXiv:2507.22854•Aug 14, 2026•3 citations

Quantum Algorithms for Finite-horizon Markov Decision Processes

Luo, Bin, Yu‐Wen Huang, Jonathan Allcock +3 more

In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment's dynamics (i.e., transition probabilities), we prove that our $\textbf{Quantum Value Iteration (QVI)}$ algorithm $\textbf{QVI-1}$ achieves a quadratic speedup in the size of the action space $(A)$ compared with the classical value iteration algorithm for computing the optimal policy ($π^{*}$) and the optimal V-value function ($V_{0}^{*}$). Furthermore, our algorithm $\textbf{QVI-2}$ provides an additional speedup in the size of the state space $(S)$ when obtaining near-optimal policies and V-value functions. Both $\textbf{QVI-1}$ and $\textbf{QVI-2}$ achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on $S$ and $A$. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms $\textbf{QVI-3}$ and $\textbf{QVI-4}$ achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of $A$, estimation error $(ε)$, and time horizon $(H)$. More importantly, we prove quantum lower bounds to show that $\textbf{QVI-3}$ and $\textbf{QVI-4}$ are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.

arXiv:2508.05712•Aug 7, 2025•0 citations

Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning

Simon M. Wiedemann, Daniel M. Hein, Steffen Udluft +1 more

We present a full implementation and simulation of a novel quantum reinforcement learning method. Our work is a detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement learning problems and shows that, given access to error-free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte-Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classical Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.

arXiv:2206.04741•Jun 9, 2022•26 citations

Optimal Policies for Quantum Markov Decision Processes

Mingsheng Ying, Yuan Feng, Shenggang Ying

Abstract Markov decision process (MDP) offers a general framework for modelling sequential decision making where outcomes are random. In particular, it serves as a mathematical framework for reinforcement learning. This paper introduces an extension of MDP, namely quantum MDP (qMDP), that can serve as a mathematical model of decision making about quantum systems. We develop dynamic programming algorithms for policy evaluation and finding optimal policies for qMDPs in the case of finite-horizon. The results obtained in this paper provide some useful mathematical tools for reinforcement learning techniques applied to the quantum world.

Machine Intelligence Research•Mar 19, 2021•18 citations

A New Framework for Quantum Reinforcement Learning

Alireza Tavakoli, Mohsen Heidari

Quantum reinforcement learning (QRL) has emerged as a promising approach for controlling quantum systems and accelerating learning tasks with quantum resources. However, most existing QRL formulations still retain a classical reinforcement learning interface: states and actions are often encoded in computational bases and rewards are extracted through measurements. This interface is restrictive for genuinely quantum environments: choosing a measurement can discard entanglement information, while repeated intermediate measurements collapse the evolving state and require costly re-preparation. This motivates a fully QRL framework in which the agent, environment, rewards, and return accumulation are all quantum. In this paper, we take a step toward this goal and introduce a new QRL framework in which both the policy and the environment are modeled by conditional quantum channels. We then propose a quantum policy-gradient algorithm for parameterized conditional quantum channels with a trainable control basis. We also derive finite- and infinite-horizon gradient estimators using a new parameter-shift rule. This rule is needed because policy parameters are shared across repeated interaction blocks and the infinite-horizon objective is not a finite circuit; rather than shifting every occurrence and evaluating the whole trajectory, our estimator shifts only one sampled policy block. Sampling this block from a geometric distribution yields an unbiased gradient estimator under bounded rewards. Finally, we establish convergence of the resulting stochastic gradient-ascent procedure to stationary points under standard smoothness and step-size assumptions.

arXiv:2611.14731•Nov 10, 2026•0 citations
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.
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∗v^*v∗), and the optimal QQQ-function (q∗q^*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 (11−γ\frac{1}{1-γ}1−γ1​) and the size of the action space (AAA). Moreover, we show that our quantum algorithm for computing q∗q^*q∗ is optimal by proving a matching quantum lower bound.
Abstract We propose novel classical and quantum online algorithms for learning finite- and infinite-horizon Markov Decision Processes (MDPs). Our algorithms are based on a hybrid online-offline reinforcement learning model wherein the agent can, from time to time, freely interact with the environment in a generative sampling fashion, i.e., by having access to a ''simulator''. By employing known classical and new quantum algorithms for approximating optimal policies under a generative model within our learning algorithms, we show that it is possible to avoid several paradigms from RL like ''optimism in the face of uncertainty'' and ''posterior sampling'' and instead compute and use optimal policies directly, which yields better regret bounds compared to previous works. Our quantum algorithms obtain regret bounds which only a poly⁡log⁡T\operatorname{poly}\log{T}polylogT dependence on the number of time steps T , thus breaking the O(T)O(\sqrt{T})O(T​) classical barrier. Our infinite-horizon discounted regret bound is brand new, while in the finite- and infinite-horizon undiscounted settings, our results match the time dependence of some prior quantum works, but with improved dependence on other parameters like state space size S and action space size A .
In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment's dynamics (i.e., transition probabilities), we prove that our Quantum Value Iteration (QVI)\textbf{Quantum Value Iteration (QVI)}Quantum Value Iteration (QVI) algorithm QVI-1\textbf{QVI-1}QVI-1 achieves a quadratic speedup in the size of the action space (A)(A)(A) compared with the classical value iteration algorithm for computing the optimal policy (π∗π^{*}π∗) and the optimal V-value function (V0∗V_{0}^{*}V0∗​). Furthermore, our algorithm QVI-2\textbf{QVI-2}QVI-2 provides an additional speedup in the size of the state space (S)(S)(S) when obtaining near-optimal policies and V-value functions. Both QVI-1\textbf{QVI-1}QVI-1 and QVI-2\textbf{QVI-2}QVI-2 achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on SSS and AAA. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms QVI-3\textbf{QVI-3}QVI-3 and QVI-4\textbf{QVI-4}QVI-4 achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of AAA, estimation error (ε)(ε)(ε), and time horizon (H)(H)(H). More importantly, we prove quantum lower bounds to show that QVI-3\textbf{QVI-3}QVI-3 and QVI-4\textbf{QVI-4}QVI-4 are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.
We present a full implementation and simulation of a novel quantum reinforcement learning method. Our work is a detailed and formal proof of concept for how quantum algorithms can be used to solve reinforcement learning problems and shows that, given access to error-free, efficient quantum realizations of the agent and environment, quantum methods can yield provable improvements over classical Monte-Carlo based methods in terms of sample complexity. Our approach shows in detail how to combine amplitude estimation and Grover search into a policy evaluation and improvement scheme. We first develop quantum policy evaluation (QPE) which is quadratically more efficient compared to an analogous classical Monte Carlo estimation and is based on a quantum mechanical realization of a finite Markov decision process (MDP). Building on QPE, we derive a quantum policy iteration that repeatedly improves an initial policy using Grover search until the optimum is reached. Finally, we present an implementation of our algorithm for a two-armed bandit MDP which we then simulate.
Abstract Markov decision process (MDP) offers a general framework for modelling sequential decision making where outcomes are random. In particular, it serves as a mathematical framework for reinforcement learning. This paper introduces an extension of MDP, namely quantum MDP (qMDP), that can serve as a mathematical model of decision making about quantum systems. We develop dynamic programming algorithms for policy evaluation and finding optimal policies for qMDPs in the case of finite-horizon. The results obtained in this paper provide some useful mathematical tools for reinforcement learning techniques applied to the quantum world.
Quantum reinforcement learning (QRL) has emerged as a promising approach for controlling quantum systems and accelerating learning tasks with quantum resources. However, most existing QRL formulations still retain a classical reinforcement learning interface: states and actions are often encoded in computational bases and rewards are extracted through measurements. This interface is restrictive for genuinely quantum environments: choosing a measurement can discard entanglement information, while repeated intermediate measurements collapse the evolving state and require costly re-preparation. This motivates a fully QRL framework in which the agent, environment, rewards, and return accumulation are all quantum. In this paper, we take a step toward this goal and introduce a new QRL framework in which both the policy and the environment are modeled by conditional quantum channels. We then propose a quantum policy-gradient algorithm for parameterized conditional quantum channels with a trainable control basis. We also derive finite- and infinite-horizon gradient estimators using a new parameter-shift rule. This rule is needed because policy parameters are shared across repeated interaction blocks and the infinite-horizon objective is not a finite circuit; rather than shifting every occurrence and evaluating the whole trajectory, our estimator shifts only one sampled policy block. Sampling this block from a geometric distribution yields an unbiased gradient estimator under bounded rewards. Finally, we establish convergence of the resulting stochastic gradient-ascent procedure to stationary points under standard smoothness and step-size assumptions.