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

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

## Key facts

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

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes](https://mlsanity.com/paper/2309.01922/) (2023)
- [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 Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learning](https://mlsanity.com/paper/2206.04741/) (2022)
- [Concave Utility Reinforcement Learning with Zero-Constraint Violations](https://mlsanity.com/paper/2109.05439/) (2021)
- [Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets](https://mlsanity.com/paper/2205.14988/) (2022)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Reinforcement Learning for Joint Optimization of Multiple Rewards](https://mlsanity.com/paper/1909.02940/) (2019)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)
- [Quantum policy gradient algorithms](https://mlsanity.com/paper/2212.09328/) (2022)
- [Quantum speedups for stochastic optimization](https://mlsanity.com/paper/2308.01582/) (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 Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling](https://mlsanity.com/paper/2301.03763/) (2023)
- [Decision Making in Monopoly using a Hybrid Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2103.00683/) (2021)
- [Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning](https://mlsanity.com/paper/2302.08617/) (2023)

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

- [Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach](https://mlsanity.com/paper/2501.16243/) (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)
- [Quantum entanglement provides a competitive advantage in adversarial games](https://mlsanity.com/paper/2603.10289/) (2026)

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