mlsanityData to 7 Oct 2026

Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes

arXiv 2310.11684 ↗First posted 18 Oct 2023cs.LG cs.AI quant-phcited by 3

Not on the map. Why?

Abstract (arXiv)

This paper investigates the potential of quantum acceleration in addressing infinite horizon Markov Decision Processes (MDPs) to enhance average reward outcomes. We introduce an innovative quantum framework for the agent's engagement with an unknown MDP, extending the conventional interaction paradigm. Our approach involves the design of an optimism-driven tabular Reinforcement Learning algorithm that harnesses quantum signals acquired by the agent through efficient quantum mean estimation techniques. Through thorough theoretical analysis, we demonstrate that the quantum advantage in mean estimation leads to exponential advancements in regret guarantees for infinite horizon Reinforcement Learning. Specifically, the proposed Quantum algorithm achieves a regret bound of tildeO(1), a significant improvement over the tildeO(√T) bound exhibited by classical counterparts.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 23 of its 54 references that are in the map. First posted on arXiv 18 Oct 2023.

Builds on

23 of 54 references.

References · 23

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  3. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
  4. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  5. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  6. 2019DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learningcited by 54
  7. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  8. 2020Quantum exploration algorithms for multi-armed banditscited by 22
  9. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  10. 2022Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learningcited by 21
  11. 2022Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regretscited by 19
  12. 2020Quantum Banditscited by 18
11 more
  1. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  2. 2021Near-Optimal Quantum Algorithms for Multivariate Mean Estimationcited by 16
  3. 2019Reinforcement Learning for Joint Optimization of Multiple Rewardscited by 15
  4. 2021Quantum Sub-Gaussian Mean Estimatorcited by 15
  5. 2022Quantum policy gradient algorithmscited by 15
  6. 2023Quantum speedups for stochastic optimizationcited by 12
  7. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  8. 2023Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Samplingcited by 7
  9. 2023Quantum Heavy-tailed Banditscited by 7
  10. 2021Decision Making in Monopoly using a Hybrid Deep Reinforcement Learning Approachcited by 6
  11. 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approachcited by 4
  2. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  3. 2026Quantum entanglement provides a competitive advantage in adversarial gamescited by 0