Abstract
Quantum computers can offer dramatic improvements over classical devices fordata analysis tasks such as prediction and classification. However, less isknown about the advantages that quantum computers may bring in the setting ofreinforcement learning, where learning is achieved via interaction with a taskenvironment. Here, we consider a special case of reinforcement learning, wherethe task environment allows quantum access. In addition, we impose certain"naturalness" conditions on the task environment, which rule out the kinds oforacle problems that are studied in quantum query complexity (and for whichquantum speedups are well-known). Within this framework of quantum-accessiblereinforcement learning environments, we demonstrate that quantum agents canachieve exponential improvements in learning efficiency, surpassing previousresults that showed only quadratic improvements. A key step in the proof is toconstruct task environments that encode well-known oracle problems, such asSimon's problem and Recursive Fourier Sampling, while satisfying the above"naturalness" conditions for reinforcement learning. Our results suggest thatquantum agents may perform well in certain game-playing scenarios, where thegame has recursive structure, and the agent can learn by playing againstitself.