Quantum Best Arm Identification with Quantum Oracles
Xuchuang Wang, Yu-Zhen Janice Chen, Matheus Guedes de Andrade, Jonathan Allcock, Mohammad Hajiesmaili, John C.S. Lui, Don Towsley
Abstract
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.
BibTeX
@article{Wang_Chen_Guedes de Andrade_Allcock_Hajiesmaili_Lui_Towsley_2025, title={Quantum Best Arm Identification with Quantum Oracles}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/35432}, DOI={10.1609/aaai.v39i20.35432}, abstractNote={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.}, number={20}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Wang, Xuchuang and Chen, Yu-Zhen Janice and Guedes de Andrade, Matheus and Allcock, Jonathan and Hajiesmaili, Mohammad and Lui, John C.S. and Towsley, Don}, year={2025}, month={Apr.}, pages={21321-21329} }