Quantum exploration algorithms for multi-armed bandits
arXiv:2007.07049 · doi:10.1609/aaai.v35i11.17212
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 quantum queries, where represents the difference between the mean reward of the best arm and the -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).
arXiv comment18 pages, 1 figure. To appear in the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)
References in corpus (21)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum support vector machine for big data classification
- Quantum Amplitude Amplification and Estimation
- Quantum principal component analysis
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum algorithms for supervised and unsupervised machine learning
- Quantum-enhanced machine learning
- A Quantum Algorithm for Finding the Minimum
- Quantum speedup of Monte Carlo methods
- Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
- Contextual Bandit Algorithms with Supervised Learning Guarantees
- q-means: A quantum algorithm for unsupervised machine learning
- Advances in Quantum Reinforcement Learning
- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
- Lower Bounds on Quantum Query Complexity
- A Survey of Quantum Learning Theory
- Sublinear quantum algorithms for training linear and kernel-based classifiers
- Towards Instance Optimal Bounds for Best Arm Identification
- A new quantum lower bound method, with an application to strong direct product theorem for quantum search
- Quantum Boosting