Multi-Armed Bandits and Quantum Channel Oracles

Abstract

Multi-armed bandits are one of the theoretical pillars of reinforcement learning. Recently, the investigation of quantum algorithms for multi-armed bandit problems was started, and it was found that a quadratic speed-up (in query complexity) is possible when the arms and the randomness of the rewards of the arms can be queried in superposition. Here we introduce further bandit models where we only have limited access to the randomness of the rewards, but we can still query the arms in superposition. We show that then the query complexity is the same as for classical algorithms. This generalizes the prior result that no speed-up is possible for unstructured search when the oracle has positive failure probability.

50 pages, accepted in Quantum

References in corpus (18)

• Quantum Machine Learning
• Quantum sensing
• Advances in Quantum Metrology
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Quantum advantage in learning from experiments
• Quantum machine learning: a classical perspective
• Quantum reinforcement learning
• Statistical distinguishability between unitary operations
• Quantum fidelity measures for mixed states
• Fundamental limits to quantum channel discrimination
• Effects of Noisy Oracle on Search Algorithm Complexity
• Ultimate limits for multiple quantum channel discrimination
• Quantum Bandits
• Quantum exploration algorithms for multi-armed bandits
• Quantum algorithms for hedging and the learning of Ising models
• Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets