# Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Quantum reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 27 Jan 2025.

## Placed in

- Deep reinforcement learning methods / [Quantum reinforcement learning](https://mlsanity.com/deeprl/quantum-reinforcement-learning/)

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

- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [DeepPool: Distributed Model-free Algorithm for Ride-sharing using Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03882/) (2019)
- [Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm with General Parameterization for Infinite Horizon Discounted Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11677/) (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)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm](https://mlsanity.com/paper/2206.05850/) (2022)
- [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)
- [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)
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024)
- [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)
- [Reinforced Sequential Decision-Making for Sepsis Treatment: The POSNEGDM Framework with Mortality Classifier and Transformer](https://mlsanity.com/paper/2403.07309/) (2024)
- [Quantum Speedups in Regret Analysis of Infinite Horizon Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2310.11684/) (2023)

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

- [Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning](https://mlsanity.com/paper/2502.16816/) (2025)
- [Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environments](https://mlsanity.com/paper/2507.18606/) (2025)
- [Mitigating Bias in Low-SNR Financial Reinforcement Learning via Quantum Representations](https://mlsanity.com/paper/2606.10448/) (2026)
- [Qubit-Efficient Quantum Search for Hyperdimensional Decomposition via Logarithmic Encoding](https://mlsanity.com/paper/2607.11936/) (2026)

## Abstract (arXiv)

We address the problem of quantum reinforcement learning (QRL) under model-free settings with quantum oracle access to the Markov Decision Process (MDP). This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classical Natural Policy Gradient (NPG) estimators with a deterministic gradient estimation approach, enabling seamless integration into quantum systems. While this modification introduces a bounded bias in the estimator, the bias decays exponentially with increasing truncation levels. This paper demonstrates that the proposed QNPG algorithm achieves a sample complexity of tildeO(ε-1.5) for queries to the quantum oracle, significantly improving the classical lower bound of tildeO(ε-2) for queries to the MDP.