



01811nas a2200145   4500008004100000245009400041210006900135260001500204520133900219100001901558700001601577700001601593700001901609856003701628       2017                        eng d00aSuper-polynomial and exponential improvements for quantum-enhanced reinforcement learning0 aSuperpolynomial and exponential improvements for quantumenhanced  c2017/12/123 a<p>Recent work on quantum machine learning has demonstrated that quantum computers can offer dramatic improvements over classical devices for data mining, prediction and classification. However, less is known about the advantages using quantum computers may bring in the more general setting of reinforcement learning, where learning is achieved via interaction with a task environment that provides occasional rewards. Reinforcement learning can incorporate data-analysis-oriented learning settings as special cases, but also includes more complex situations where, e.g., reinforcing feedback is delayed. In a few recent works, Grover-type amplification has been utilized to construct quantum agents that achieve up-to-quadratic improvements in learning efficiency. These encouraging results have left open the key question of whether super-polynomial improvements in learning times are possible for genuine reinforcement learning problems, that is problems that go beyond the other more restricted learning paradigms. In this work, we provide a family of such genuine reinforcement learning tasks. We construct quantum-enhanced learners which learn super-polynomially, and even exponentially faster than any classical reinforcement learning model, and we discuss the potential impact our results may have on future technologies.</p>1 aDunjko, Vedran1 aLiu, Yi-Kai1 aWu, Xingyao1 aTaylor, J., M.  uhttps://arxiv.org/abs/1710.11160