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
Authors
- Jonathan Allcock (ORCID: https://orcid.org/0000-0003-3545-0565)
- Yu-Zhen Janice Chen (ORCID: https://orcid.org/0000-0002-1420-9214)
- Don Towsley (ORCID: https://orcid.org/0000-0002-7808-7375)
- Mohammad Hajiesmaili (ORCID: https://orcid.org/0000-0001-9278-2254)
- John C. S. Lui (ORCID: https://orcid.org/0000-0001-7466-0384)
- Xuchuang Wang (ORCID: https://orcid.org/0009-0006-8043-8521)
- Matheus Guedes de Andrade (ORCID: https://orcid.org/0000-0002-9968-0194)
Institutions
- Chinese University of Hong Kong (HK)
- Tencent (China) (CN)
- University of Massachusetts Amherst (US)
Publication Details
- Journal
- Proceedings of the AAAI Conference on Artificial Intelligence
- Published
- 2025-04-11
- DOI
- https://doi.org/10.1609/aaai.v39i20.35432
- Citations
- 2
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 1.77
Funders
- National Science Foundation
- U.S. Department of Energy