mlsanityData to 14 Oct 2026

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

arXiv 2205.14988 ↗First posted 30 May 2022cs.LG quant-phcited by 19

Not on the map. Why?

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.

Key facts. Cited by 19 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

8 of 29 references.

References · 8

  1. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 114
  2. 2016Quantum-enhanced machine learningcited by 79
  3. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  4. 2020Quantum exploration algorithms for multi-armed banditscited by 22
  5. 2020Quantum Banditscited by 18
  6. 2017An Actor-Critic Contextual Bandit Algorithm for Personalized Mobile Health Interventionscited by 17
  7. 2015Framework for learning agents in quantum environmentscited by 9
  8. 2020Quantum Algorithm for Online Convex Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 0; 2025: 7; 2026: 4.

19 papers.

Sort:

By area:

  1. 2022A Survey on Quantum Reinforcement Learningcited by 53
  2. 2023Quantum Bayesian Optimizationcited by 12
  3. 2025A Primer on Quantum Machine Learningcited by 12
  4. 2022Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Banditscited by 11
  5. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  6. 2023Quantum Heavy-tailed Banditscited by 8
  7. 2023Quantum contextual bandits and recommender systems for quantum datacited by 4
  8. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  9. 2025Quantum Lipschitz Banditscited by 4
  10. 2023Multi-Armed Bandits and Quantum Channel Oraclescited by 3
  11. 2023Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processescited by 3
  12. 2025Quantum Non-Linear Bandit Optimizationcited by 2
7 more
  1. 2025Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexitiescited by 2
  2. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  3. 2026Quantum-Enhanced Neural Contextual Bandit Algorithmscited by 1
  4. 2025Quantum Algorithms for Projection-Free Sparse Convex Optimizationcited by 0
  5. 2026Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Banditscited by 0
  6. 2026Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimizationcited by 0
  7. 2026Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithmscited by 0