Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

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 approximating 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 query complexities improve on previous works, thus approaching already established quantum lower bounds.