Quantum bandits
- PDF / 579,132 Bytes
- 7 Pages / 595.224 x 790.955 pts Page_size
- 82 Downloads / 156 Views
RESEARCH ARTICLE
Quantum bandits Balthazar Casale´ 1 · Giuseppe Di Molfetta1,2
· Hachem Kadri1 · Liva Ralaivola3
Received: 18 February 2020 / Accepted: 2 July 2020 © Springer Nature Switzerland AG 2020
Abstract We consider the quantum version of the bandit problem known as best arm identification (BAI). We first propose a quantum modeling of the BAI problem, which assumes that both the learning agent and the environment are quantum; we then propose an algorithm based on quantum amplitude amplification to solve BAI. We formally analyze the behavior of the algorithm on all instances of the problem and we show, in particular, that it is able to get the optimal solution quadratically faster than what is known to hold in the classical case. Keywords Bandits · Best arm identification · Quantum amplitude amplification
1 Introduction Many decision-making problems involve learning by interacting with the environment and observing what rewards result from these interactions. In the field of machine learning, this line of research falls into what is referred as reinforcement learning (RL), and algorithms to train artificial agents that interact with an environment have been studied extensively (Sutton and Barto 2018; Kaelbling et al. 1996; Bertsekas and Tsitsiklis 1996). We are here interested in the best arm identification (BAI) problem from the family of bandit problems, which pertains the set of RL problems where the interactions with the environment give rise to immediate rewards and where long-term planning is unnecessary (see the survey of Lattimore and Szepesv´ari 2020). Balthazar Casal´e
[email protected] Giuseppe Di Molfetta [email protected] Hachem Kadri [email protected] Liva Ralaivola [email protected] 1
Aix-Marseille Universit´e, CNRS, LIS, Marseille, France
2
Quantum Computing Center, Keio University, 3-14-1 Hiyoshi, Kohoku, Yokohama 223-8522, Japan
3
Criteo AI Lab, Criteo, Paris, France
More precisely, we are interested in a quantum version of the BAI problem, for which we design a quantum algorithm capable to solve it. Quantum machine learning is a research field at the interface of quantum computing and machine learning where the goal is to use quantum computing paradigms and technologies to improve the speed and performance of learning algorithms (Wittek 2014; Biamonte et al. 2017; Ciliberto et al. 2018; Schuld and Petruccione 2018). A fundamental concept in quantum computing is quantum superposition, which is the means by which quantum algorithm like that of Grover (1996)—one of the most popular quantum algorithms—succeeds in solving the problem of finding one√item from an unstructured database of N items in time O( N ), so beating the classical O(N) time requirement. Recent works have investigated the use of Grover’s quantum search algorithm to enhance machine learning and have proved its ability of providing non-trivial improvements not only in the computational complexity but also in the statistical performance of these models (A¨ımeur et al. 2013; Wittek 2
Data Loading...
