mlsanityData to 7 Oct 2026

Quantum exploration algorithms for multi-armed bandits

arXiv 2007.07049 ↗First posted 14 Jul 2020quant-ph cs.DS cs.LGcited by 22

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 7; 2024: 0; 2025: 7; 2026: 4.

22 papers.

Sort:

  1. 2022A Survey on Quantum Reinforcement Learningcited by 50
  2. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  3. 2022Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regretscited by 19
  4. 2022Quantum policy gradient algorithmscited by 15
  5. 2023Quantum Bayesian Optimizationcited by 12
  6. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  7. 2023Quantum Heavy-tailed Banditscited by 7
  8. 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6
  9. 2023Quantum contextual bandits and recommender systems for quantum datacited by 4
  10. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  11. 2025Quantum Lipschitz Banditscited by 4
  12. 2023Multi-Armed Bandits and Quantum Channel Oraclescited by 3
10 more
  1. 2023Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processescited by 3
  2. 2025Quantum Algorithms for Bandits with Knapsacks with Improved Regret and Time Complexitiescited by 2
  3. 2025Quantum Deep Learning Still Needs a Quantum Leapcited by 1
  4. 2025Quantum Algorithms for Projection-Free Sparse Convex Optimizationcited by 0
  5. 2025Quantum spatial best-arm identification via quantum walkscited by 0
  6. 2025Variational Quantum Circuits in Offline Contextual Bandit Problemscited by 0
  7. 2026Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Banditscited by 0
  8. 2026Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimizationcited by 0
  9. 2026Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithmscited by 0
  10. 2026Quantum Monte Carlo Tree Search with Fixed Confidencecited by 0