Quantum Exploration Algorithms for Multi-Armed Bandits
Keywords:Online Learning & Bandits
AbstractIdentifying 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. https://doi.org/10.1609/aaai.v35i11.17212
AAAI Technical Track on Machine Learning IV