Quantum Exploration Algorithms for Multi-Armed Bandits


  • Daochen Wang University of Maryland
  • Xuchen You University of Maryland
  • Tongyang Li University of Maryland Massachusetts Institute of Technology
  • Andrew M. Childs University of Maryland


Online Learning & Bandits


Identifying the best arm of a multi-armed bandit is a central problem in bandit optimization. We study a quantum computational version of this problem with coherent oracle access to states encoding the reward probabilities of each arm as quantum amplitudes. Specifically, we provide an algorithm to find the best arm with fixed confidence based on variable-time amplitude amplification and estimation. This algorithm gives a quadratic speedup compared to the best possible classical result in terms of query complexity. We also prove a matching quantum lower bound (up to poly-logarithmic factors).




How to Cite

Wang, D., You, X., Li, T., & Childs, A. M. (2021). Quantum Exploration Algorithms for Multi-Armed Bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 35(11), 10102-10110. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17212



AAAI Technical Track on Machine Learning IV