Abstract
Recent work on quantum machine learning has demonstrated that quantumcomputers can offer dramatic improvements over classical devices for datamining, prediction and classification. However, less is known about theadvantages using quantum computers may bring in the more general setting ofreinforcement learning, where learning is achieved via interaction with a taskenvironment that provides occasional rewards. Reinforcement learning canincorporate data-analysis-oriented learning settings as special cases, but alsoincludes more complex situations where, e.g., reinforcing feedback is delayed.In a few recent works, Grover-type amplification has been utilized to constructquantum agents that achieve up-to-quadratic improvements in learningefficiency. These encouraging results have left open the key question ofwhether super-polynomial improvements in learning times are possible forgenuine reinforcement learning problems, that is problems that go beyond theother more restricted learning paradigms. In this work, we provide a family ofsuch genuine reinforcement learning tasks. We construct quantum-enhancedlearners which learn super-polynomially, and even exponentially faster than anyclassical reinforcement learning model, and we discuss the potential impact ourresults may have on future technologies.