Quantum exploration algorithms for multi-armed 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 show that we can find the best arm with fixed confidence using $\tilde{O}\left(\sqrt{{\sum }_{i=2}^n{\Delta }_i^{-2}}\right)$ quantum queries, where ${\Delta }_i$ represents the difference between the mean reward of the best arm and the $i^{\text{th}}$-best arm. This algorithm, based on variable-time amplitude amplification and estimation, gives a quadratic speedup compared to the best possible classical result. We also prove a matching quantum lower bound (up to poly-logarithmic factors).

18 pages, 1 figure. To appear in the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)

References in corpus (7)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum-enhanced machine learning
• q-means: A quantum algorithm for unsupervised machine learning
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Sublinear quantum algorithms for training linear and kernel-based classifiers
• A new quantum lower bound method, with an application to strong direct product theorem for quantum search
• Quantum Boosting

Cited by in corpus (4)

• Quantum Logic Gate Synthesis as a Markov Decision Process
• Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states
• Quantum spatial best-arm identification via quantum walks
• Multi-Armed Bandits and Quantum Channel Oracles