01776nas a2200145 4500008004100000245004700041210004700088260000900135300001200144520137700156100001901533700001901552700002201571856003701593 2017 eng d00aAdvances in Quantum Reinforcement Learning0 aAdvances in Quantum Reinforcement Learning c2017 a282-2873 a
In recent times, there has been much interest in quantum enhancements of machine learning, specifically in the context of data mining and analysis. Reinforcement learning, an interactive form of learning, is, in turn, vital in artificial intelligence-type applications. Also in this case, quantum mechanics was shown to be useful, in certain instances. Here, we elucidate these results, and show that quantum enhancements can be achieved in a new setting: the setting of learning models which learn how to improve themselves -- that is, those that meta-learn. While not all learning models meta-learn, all non-trivial models have the potential of being "lifted", enhanced, to meta-learning models. Our results show that also such models can be quantum-enhanced to make even better learners. In parallel, we address one of the bottlenecks of current quantum reinforcement learning approaches: the need for so-called oracularized variants of task environments. Here we elaborate on a method which realizes these variants, with minimal changes in the setting, and with no corruption of the operative specification of the environments. This result may be important in near-term experimental demonstrations of quantum reinforcement learning.
1 aDunjko, Vedran1 aTaylor, J., M.1 aBriegel, Hans, J. uhttps://arxiv.org/abs/1811.0867601775nas a2200133 4500008004100000245007500041210006900116520134900185100001901534700001601553700001601569700001901585856003701604 2017 eng d00aExponential improvements for quantum-accessible reinforcement learning0 aExponential improvements for quantumaccessible reinforcement lea3 aQuantum computers can offer dramatic improvements over classical devices for data analysis tasks such as prediction and classification. However, less is known about the advantages that quantum computers may bring in the setting of reinforcement learning, where learning is achieved via interaction with a task environment. Here, we consider a special case of reinforcement learning, where the task environment allows quantum access. In addition, we impose certain "naturalness" conditions on the task environment, which rule out the kinds of oracle problems that are studied in quantum query complexity (and for which quantum speedups are well-known). Within this framework of quantum-accessible reinforcement learning environments, we demonstrate that quantum agents can achieve exponential improvements in learning efficiency, surpassing previous results that showed only quadratic improvements. A key step in the proof is to construct task environments that encode well-known oracle problems, such as Simon's problem and Recursive Fourier Sampling, while satisfying the above "naturalness" conditions for reinforcement learning. Our results suggest that quantum agents may perform well in certain game-playing scenarios, where the game has recursive structure, and the agent can learn by playing against itself
1 aDunjko, Vedran1 aLiu, Yi-Kai1 aWu, Xingyao1 aTaylor, J., M. uhttps://arxiv.org/abs/1710.1116001811nas a2200145 4500008004100000245009400041210006900135260001500204520133900219100001901558700001601577700001601593700001901609856003701628 2017 eng d00aSuper-polynomial and exponential improvements for quantum-enhanced reinforcement learning0 aSuperpolynomial and exponential improvements for quantumenhanced c2017/12/123 aRecent 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.
1 aDunjko, Vedran1 aLiu, Yi-Kai1 aWu, Xingyao1 aTaylor, J., M. uhttps://arxiv.org/abs/1710.1116001280nas a2200133 4500008004100000245005800041210005800099260001500157520087600172100001901048700001901067700002201086856003801108 2015 eng d00aFramework for learning agents in quantum environments0 aFramework for learning agents in quantum environments c2015/07/303 aIn this paper we provide a broad framework for describing learning agents in general quantum environments. We analyze the types of classically specified environments which allow for quantum enhancements in learning, by contrasting environments to quantum oracles. We show that whether or not quantum improvements are at all possible depends on the internal structure of the quantum environment. If the environments are constructed and the internal structure is appropriately chosen, or if the agent has limited capacities to influence the internal states of the environment, we show that improvements in learning times are possible in a broad range of scenarios. Such scenarios we call luck-favoring settings. The case of constructed environments is particularly relevant for the class of model-based learning agents, where our results imply a near-generic improvement. 1 aDunjko, Vedran1 aTaylor, J., M.1 aBriegel, Hans, J. uhttp://arxiv.org/abs/1507.08482v1