# Quantum exploration algorithms for multi-armed bandits

arXiv: https://arxiv.org/abs/2007.07049 · HTML: https://mlsanity.com/paper/2007.07049/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2020.

## Built on by (most cited first, 22 of 22)

- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [Quantum policy gradient algorithms](https://mlsanity.com/paper/2212.09328/) (2022)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning](https://mlsanity.com/paper/2302.08617/) (2023)
- [Quantum contextual bandits and recommender systems for quantum data](https://mlsanity.com/paper/2301.13524/) (2023)
- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (2025)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Multi-Armed Bandits and Quantum Channel Oracles](https://mlsanity.com/paper/2301.08544/) (2023)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [Quantum Deep Learning Still Needs a Quantum Leap](https://mlsanity.com/paper/2511.01253/) (2025)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Quantum spatial best-arm identification via quantum walks](https://mlsanity.com/paper/2509.05890/) (2025)
- [Variational Quantum Circuits in Offline Contextual Bandit Problems](https://mlsanity.com/paper/2509.07633/) (2025)
- [Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Bandits](https://mlsanity.com/paper/2603.18431/) (2026)
- [Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization](https://mlsanity.com/paper/2607.01080/) (2026)
- [Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms](https://mlsanity.com/paper/2608.14319/) (2026)
- [Quantum Monte Carlo Tree Search with Fixed Confidence](https://mlsanity.com/paper/2609.33132/) (2026)

## Abstract (arXiv)

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 tildeObigl(√sumi=2nDelta^smash-2ibigr) quantum queries, where Deltai represents the difference between the mean reward of the best arm and the ith-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).