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, yielding better regret bounds compared to previous works.
Our quantum algorithms obtain regret bounds which only have 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$.
Blogger's Review: This paper showcases the significance of generative models in reinforcement learning by combining classical and quantum algorithms. The breakthrough in regret bounds achieved by quantum algorithms not only has theoretical implications but also opens new avenues for practical applications in the field.