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

arXiv:2507.22854v3 Announce Type: replace-cross 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$.

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$.

31 pages. v3: main text completely restructured and simplified, results for compact spaces have been dropped (to be included elsewhere), fixed a bug on optimal policies for finite-horizon MDPs which weakened a bit one result, expanded the new RL model by including a tunable budget parameter, new results on infinite-horizon discounted MDPs, improved regrets overall

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC); Quantum Physics (quant-ph); Machine Learning (stat.ML)

arXiv:2507.22854 [cs.LG]

(or arXiv:2507.22854v3 [cs.LG] for this version)

From: Joao F. Doriguello [view email] [v1] Wed, 30 Jul 2025 17:24:23 UTC (65 KB) [v2] Mon, 11 Aug 2025 03:00:03 UTC (66 KB) [v3] Thu, 16 Jul 2026 17:57:33 UTC (76 KB)

analiza aiqbench

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

Subiecte conexe