# Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 40 references that are in the map.
- First posted on arXiv 16 Feb 2023.

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

- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Quantum-enhanced machine learning](https://mlsanity.com/paper/1610.08251/) (2016)
- [RecoGym: A Reinforcement Learning Environment for the problem of Product Recommendation in Online Advertising](https://mlsanity.com/paper/1808.00720/) (2018)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [Quantum Algorithms for Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.08451/) (2021)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Quantum exploration algorithms for multi-armed bandits](https://mlsanity.com/paper/2007.07049/) (2020)
- [Quantum Bandits](https://mlsanity.com/paper/2002.06395/) (2020)
- [Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities](https://mlsanity.com/paper/1905.12425/) (2019)
- [Quantum Sub-Gaussian Mean Estimator](https://mlsanity.com/paper/2108.12172/) (2021)

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

- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [Benchmarking Quantum Reinforcement Learning](https://mlsanity.com/paper/2501.15893/) (2025)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Lipschitz Bandits](https://mlsanity.com/paper/2504.02251/) (2025)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)
- [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)

## Abstract (arXiv)

In this paper, we investigate the problem of textitepisodic reinforcement learning with quantum oracles for state evolution. To this end, we propose an textitUpper Confidence Bound (UCB) based quantum algorithmic framework to facilitate learning of a finite-horizon MDP. Our quantum algorithm achieves an exponential improvement in regret as compared to the classical counterparts, achieving a regret of TildeO(1) as compared to TildeO(√K) footnoteTildeO(·) hides logarithmic terms., K being the number of training episodes. In order to achieve this advantage, we exploit efficient quantum mean estimation technique that provides quadratic improvement in the number of i.i.d. samples needed to estimate the mean of sub-Gaussian random variables as compared to classical mean estimation. This improvement is a key to the significant regret improvement in quantum reinforcement learning. We provide proof-of-concept experiments on various RL environments that in turn demonstrate performance gains of the proposed algorithmic framework.