Quantum Exploration Algorithms for Multi-Armed Bandits

Daochen Wang; Xuchen You; Tongyang Li; Andrew M. Childs

AAAI 2021technical33 citations

Quantum Exploration Algorithms for Multi-Armed Bandits

Daochen Wang, Xuchen You, Tongyang Li, Andrew M. Childs

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

BibTeX

@inproceedings{aaai2021_quantumexplorati,
  title = {Quantum Exploration Algorithms for Multi-Armed Bandits},
  author = {Daochen Wang and Xuchen You and Tongyang Li and Andrew M. Childs},
  booktitle = {AAAI 2021},
  year = {2021}
}