Quantum Best Arm Identification with Quantum Oracles

Best arm identification (BAI) is a key problem in stochastic multi-armed bandits, where K arms each has an associated reward distribution, and the objective is to minimize the number of queries needed to identify the best arm with high confidence. In this paper, we explore BAI using quantum oracles. For the case where each query probes only one arm (m=1), we devise a quantum algorithm with a query complexity upper bound of O((K/Delta)log(1/delta)), where delta is the confidence parameter and Delta is the reward gap between best and second best arms. This improves on the classical bound by a factor of 1/Delta. For the general case where a single query can probe m arms (1<= m<= K) simultaneously, we propose an algorithm with an upper bound of O((K/(Delta x sqrt(m))) log(1/delta)), improving by a factor of sqrt(m) compared to the m=1 case. We also provide query complexity lower bounds for both scenarios, which match the upper bounds up to logarithmic factors, and validate our theoretical results with Qiskit-based simulations.

Authors

• Xuchuang Wang University of Massachusetts Amherst
• Yu-Zhen Janice Chen University of Massachusetts, Amherst, MA
• Matheus Guedes de Andrade University of Massachusetts, Amherst, MA
• Jonathan Allcock Tencent Quantum Lab
• Mohammad Hajiesmaili University of Massachusetts Amherst
• John C.S. Lui Department of Computer Science and Engineering, The Chinese University of Hong Kong
• Don Towsley

Keywords

No keywords are indexed for this paper.