Multi-Armed Bandits and Quantum Channel Oracles

Understand

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.