mlsanityData to 14 Oct 2026

A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model

arXiv 2507.22854 ↗First posted 30 Jul 2025cs.LG cs.AI math.OCcited by 1

On the map: Deep reinforcement learning methods → Quantum reinforcement learning

Abstract (arXiv)

We propose novel classical and quantum online algorithms for learning finite- and infinite-horizon Markov Decision Processes (MDPs). Our algorithms are based on a hybrid online-offline reinforcement learning model wherein the agent can, from time to time, freely interact with the environment in a generative sampling fashion, i.e., by having access to a "simulator". By employing known classical and new quantum algorithms for approximating optimal policies under a generative model within our learning algorithms, we show that it is possible to avoid several paradigms from RL like "optimism in the face of uncertainty" and "posterior sampling" and instead compute and use optimal policies directly, which yields better regret bounds compared to previous works. Our quantum algorithms obtain regret bounds which only a operatornamepolylogT dependence on the number of time steps T, thus breaking the O(√T) classical barrier. Our infinite-horizon discounted regret bound is brand new, while in the finite- and infinite-horizon undiscounted settings, our results match the time dependence of some prior quantum works, but with improved dependence on other parameters like state space size S and action space size A.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in Quantum reinforcement learning, one of 15 directions in Deep reinforcement learning methods. Builds on 54 of its 122 references that are in the map. First posted on arXiv 30 Jul 2025.

Builds on

54 of 122 references.

References · 54

  1. 2015Trust Region Policy Optimizationcited by 2,580
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  7. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  8. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  9. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  10. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  11. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  12. 2016Quantum Recommendation Systemscited by 70
38 more
  1. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  2. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  3. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  4. 2018q-means: A quantum algorithm for unsupervised machine learningcited by 55
  5. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
  6. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  7. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  8. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  9. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  10. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  11. 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
  12. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  13. 2018Online Learning of Quantum Statescited by 37
  14. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  15. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  16. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  17. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
  18. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  19. 2021Quantum Algorithms for Reinforcement Learning with a Generative Modelcited by 24
  20. 2022Quantum Policy Iteration via Amplitude Estimation and Grover Search -- Towards Quantum Advantage for Reinforcement Learningcited by 21
  21. 2018Regret Bounds for Reinforcement Learning via Markov Chain Concentrationcited by 19
  22. 2020Regret Bounds for Discounted MDPscited by 19
  23. 2022Quantum Reinforcement Learning via Policy Iterationcited by 19
  24. 2022Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regretscited by 19
  25. 2020Improved Analysis of UCRL2 with Empirical Bernstein Inequalitycited by 18
  26. 2013Online Regret Bounds for Undiscounted Continuous Reinforcement Learningcited by 17
  27. 2021Near-Optimal Quantum Algorithms for Multivariate Mean Estimationcited by 16
  28. 2021Quantum Sub-Gaussian Mean Estimatorcited by 15
  29. 2022Quantum policy gradient algorithmscited by 15
  30. 2023Optimal Sample Complexity for Average Reward Markov Decision Processescited by 15
  31. 2023Quantum Bayesian Optimizationcited by 12
  32. 2017Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Timecited by 11
  33. 2021Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraintscited by 11
  34. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  35. 2024Optimistic Q-learning for average reward and episodic reinforcement learningcited by 9
  36. 2013Artificial Intelligence Framework for Simulating Clinical Decision-Making: A Markov Decision Process Approachcited by 8
  37. 2022Mean estimation when you have the source code; or, quantum Monte Carlo methodscited by 6
  38. 2023Quantum Computing Provides Exponential Regret Improvement in Episodic Reinforcement Learningcited by 6

50 most cited of 54 All 54 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Improved Quantum Algorithms for Reinforcement Learning Under a Generative Modelcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Quantum framework for Reinforcement Learning: Integrating Markov decision process, quantum arithmetic, and trajectory search
  2. 2025Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environments
  3. 2026Reinforcement learning for quantum processes with memory
  4. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  5. 2026Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains
  6. 2025Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach
  7. 2024Model-based Offline Quantum Reinforcement Learning
  8. 2026QnRL: Quantum-Native Reinforcement Learning