TY - JOUR T1 - Advances in Quantum Reinforcement Learning JF - IEEE SMC, Banff, AB Y1 - 2017 A1 - Vedran Dunjko A1 - J. M. Taylor A1 - Hans J. Briegel AB -

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.

U4 - 282-287 UR - https://arxiv.org/abs/1811.08676 U5 - https://doi.org/10.1109/SMC.2017.8122616 ER - TY - JOUR T1 - Exponential improvements for quantum-accessible reinforcement learning Y1 - 2017 A1 - Vedran Dunjko A1 - Yi-Kai Liu A1 - Xingyao Wu A1 - J. M. Taylor AB -

Quantum 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

UR - https://arxiv.org/abs/1710.11160 ER - TY - JOUR T1 - Super-polynomial and exponential improvements for quantum-enhanced reinforcement learning Y1 - 2017 A1 - Vedran Dunjko A1 - Yi-Kai Liu A1 - Xingyao Wu A1 - J. M. Taylor AB -

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.

UR - https://arxiv.org/abs/1710.11160 ER - TY - JOUR T1 - Framework for learning agents in quantum environments Y1 - 2015 A1 - Vedran Dunjko A1 - J. M. Taylor A1 - Hans J. Briegel AB - In 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. UR - http://arxiv.org/abs/1507.08482v1 ER -