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:2507.22854

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

Published Aug 14, 2026• 0 citations
arXivHTMLPDF

Abstract

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 .

DOI
10.21203/rs.3.rs-10385616/v1

Related papers

Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

Joao F. Doriguello

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.

quant-pharXiv:2608.02826•Aug 5, 2026•0 citations

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•14 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 Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes

Bhargav Ganguly, Xu, Yang, Aggarwal, Vaneet

This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conventional interaction paradigm. Our approach involves the design of an optimism-driven tabular Reinforcement Learning algorithm that harnesses quantum signals acquired by the agent through efficient quantum mean estimation techniques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning. Specifically, the proposed Quantum algorithm achieves a regret bound of $\tilde{\mathcal{O}}(1)$, a significant improvement over the $\tilde{\mathcal{O}}(\sqrt{T})$ bound exhibited by classical counterparts.

arXiv:2310.11684•Oct 18, 2023•1 citation

Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret

Han Zhong, Jiachen Hu, Yecheng Xue +2 more

While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design provably efficient quantum RL algorithms that can address the exploration-exploitation trade-off. To this end, we propose a novel UCRL-style algorithm that takes advantage of quantum computing for tabular Markov decision processes (MDPs) with $S$ states, $A$ actions, and horizon $H$, and establish an $\mathcal{O}(\mathrm{poly}(S, A, H, \log T))$ worst-case regret for it, where $T$ is the number of episodes. Furthermore, we extend our results to quantum RL with linear function approximation, which is capable of handling problems with large state spaces. Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with $d$-dimensional linear representation and prove that it enjoys $\mathcal{O}(\mathrm{poly}(d, H, \log T))$ regret. Our algorithms are variants of UCRL/UCRL-VTR algorithms in classical RL, which also leverage a novel combination of lazy updating mechanisms and quantum estimation subroutines. This is the key to breaking the $Ω(\sqrt{T})$-regret barrier in classical RL. To the best of our knowledge, this is the first work studying the online exploration in quantum RL with provable logarithmic worst-case regret.

arXiv:2302.10796•Feb 21, 2023•1 citation

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•15 citations
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 .
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.
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.
This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conventional interaction paradigm. Our approach involves the design of an optimism-driven tabular Reinforcement Learning algorithm that harnesses quantum signals acquired by the agent through efficient quantum mean estimation techniques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning. Specifically, the proposed Quantum algorithm achieves a regret bound of O~(1)\tilde{\mathcal{O}}(1)O~(1), a significant improvement over the O~(T)\tilde{\mathcal{O}}(\sqrt{T})O~(T​) bound exhibited by classical counterparts.
While quantum reinforcement learning (RL) has attracted a surge of attention recently, its theoretical understanding is limited. In particular, it remains elusive how to design provably efficient quantum RL algorithms that can address the exploration-exploitation trade-off. To this end, we propose a novel UCRL-style algorithm that takes advantage of quantum computing for tabular Markov decision processes (MDPs) with SSS states, AAA actions, and horizon HHH, and establish an O(poly(S,A,H,log⁡T))\mathcal{O}(\mathrm{poly}(S, A, H, \log T))O(poly(S,A,H,logT)) worst-case regret for it, where TTT is the number of episodes. Furthermore, we extend our results to quantum RL with linear function approximation, which is capable of handling problems with large state spaces. Specifically, we develop a quantum algorithm based on value target regression (VTR) for linear mixture MDPs with ddd-dimensional linear representation and prove that it enjoys O(poly(d,H,log⁡T))\mathcal{O}(\mathrm{poly}(d, H, \log T))O(poly(d,H,logT)) regret. Our algorithms are variants of UCRL/UCRL-VTR algorithms in classical RL, which also leverage a novel combination of lazy updating mechanisms and quantum estimation subroutines. This is the key to breaking the Ω(T)Ω(\sqrt{T})Ω(T​)-regret barrier in classical RL. To the best of our knowledge, this is the first work studying the online exploration in quantum RL with provable logarithmic worst-case regret.
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.