TY - JOUR AU - Wang, Daochen AU - You, Xuchen AU - Li, Tongyang AU - Childs, Andrew M. PY - 2021/05/18 Y2 - 2024/03/29 TI - Quantum Exploration Algorithms for Multi-Armed Bandits JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 35 IS - 11 SE - AAAI Technical Track on Machine Learning IV DO - 10.1609/aaai.v35i11.17212 UR - https://ojs.aaai.org/index.php/AAAI/article/view/17212 SP - 10102-10110 AB - 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). ER -