Quantum Algorithms for Reinforcement Learning with a Generative Model

Abstract

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 $\gamma$-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy (${\pi }^{\ast }$), the optimal value function ($v^{\ast }$), and the optimal $Q$-function ($q^{\ast }$), 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 ($\epsilon$) and two main parameters of the MDP: the effective time horizon ($\frac{1}{1-\gamma }$) and the size of the action space ($A$). Moreover, we show that our quantum algorithm for computing $q^{\ast }$ is optimal by proving a matching quantum lower bound.

arXiv comment26 pages

References in corpus (9)

• Quantum reinforcement learning
• A Quantum Algorithm for Finding the Minimum
• Quantum speedup of Monte Carlo methods
• Quantum speedup for active learning agents
• Advances in Quantum Reinforcement Learning
• Variance-reduced $Q$-learning is minimax optimal
• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Efficiently Solving MDPs with Stochastic Mirror Descent
• New Results on Quantum Property Testing

Cited by in corpus (4)

• Quantum Machine Learning for Finance
• Quantum Deep Hedging
• Quantum reinforcement learning in continuous action space
• Quantum Search Approaches to Sampling-Based Motion Planning