Quantum algorithms for reinforcement learning with a generative model

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^*\)), 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 (\(\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^*\) is optimal by proving a matching quantum lower bound.