Quantum Bandits

Abstract

We consider the quantum version of the bandit problem known as {\em best arm identification} (BAI). We first propose a quantum modeling of the BAI problem, which assumes that both the learning agent and the environment are quantum; we then propose an algorithm based on quantum amplitude amplification to solve BAI. We formally analyze the behavior of the algorithm on all instances of the problem and we show, in particular, that it is able to get the optimal solution quadratically faster than what is known to hold in the classical case.

arXiv commentAll your comments are very welcome!

References in corpus (13)

• Quantum Machine Learning
• Quantum support vector machine for big data classification
• Quantum Amplitude Amplification and Estimation
• End-to-End Training of Deep Visuomotor Policies
• Spatial search by quantum walk
• Quantum computers can search rapidly by using almost any transformation
• Quantum machine learning: a classical perspective
• Quantum-enhanced machine learning
• Quantum reinforcement learning
• Quantum Perceptron Models
• Basic protocols in quantum reinforcement learning with superconducting circuits
• Single-photon decision maker
• The Grover search as a naturally occurring phenomenon

Cited by in corpus (7)

• Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states
• Performance analysis of a hybrid agent for quantum-accessible reinforcement learning
• Quantum contextual bandits and recommender systems for quantum data
• Quantum Algorithm for Online Convex Optimization
• Multi-Armed Bandits and Quantum Channel Oracles
• Quantum spatial best-arm identification via quantum walks
• Quantum Perceptron Revisited: Computational-Statistical Tradeoffs