Quantum Exploration Algorithms for Multi-Armed Bandits

Authors

  • 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

Keywords:

Online Learning & Bandits

Abstract

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).

Downloads

Published

2021-05-18

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

Issue

Section

AAAI Technical Track on Machine Learning IV