# Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 29 references that are in the map.
- First posted on arXiv 30 May 2022.

## Builds on (most cited first, 8 of 8)

- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Quantum-enhanced machine learning](https://mlsanity.com/paper/1610.08251/) (2016)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Quantum exploration algorithms for multi-armed bandits](https://mlsanity.com/paper/2007.07049/) (2020)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [An Actor-Critic Contextual Bandit Algorithm for Personalized Mobile Health Interventions](https://mlsanity.com/paper/1706.09090/) (2017)
- [Framework for learning agents in quantum environments](https://mlsanity.com/paper/1507.08482/) (2015)
- [Quantum Algorithm for Online Convex Optimization](https://mlsanity.com/paper/2007.15046/) (2020)

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

- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits](https://mlsanity.com/paper/2209.12897/) (2022)
- [Quantum Heavy-tailed Bandits](https://mlsanity.com/paper/2301.09680/) (2023)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (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 Non-Linear Bandit Optimization](https://mlsanity.com/paper/2503.03023/) (2025)
- [Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexities](https://mlsanity.com/paper/2507.04438/) (2025)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Bandits roaming Hilbert space](https://mlsanity.com/paper/2509.24569/) (2025)
- [Quantum-Enhanced Neural Contextual Bandit Algorithms](https://mlsanity.com/paper/2601.02870/) (2026)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (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)

## Abstract (arXiv)

Multi-arm bandit (MAB) and stochastic linear bandit (SLB) are important models in reinforcement learning, and it is well-known that classical algorithms for bandits with time horizon T suffer Omega(√T) regret. In this paper, we study MAB and SLB with quantum reward oracles and propose quantum algorithms for both models with O(mboxpoly(log T)) regrets, exponentially improving the dependence in terms of T. To the best of our knowledge, this is the first provable quantum speedup for regrets of bandit problems and in general exploitation in reinforcement learning. Compared to previous literature on quantum exploration algorithms for MAB and reinforcement learning, our quantum input model is simpler and only assumes quantum oracles for each individual arm.