mlsanityData to 14 Oct 2026

Mathematical methods of reinforcement learning

arXiv 2607.06935 ↗First posted 8 Jul 2026math.OC cs.LG stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates for value and policy iteration, and temporal-difference schemes. We then develop the optimization perspective: stochastic approximation and martingale methods, convex duality and the role of regularization linking mirror/proximal methods. Function approximation is treated through linear and non-linear settings, covering stabilization, error decomposition, and sample-complexity via concentration inequalities for dependent data and mixing processes. We further cover off-policy evaluation/learning, constrained RL and constrained MDPs (CMDPs). Throughout we unify algorithmic templates under common operator and variational lenses, highlighting both finite-sample bounds and asymptotic results. Our presentation is intended to provide a unified mathematical entry point for researchers in probability, optimization, and statistics interested in reinforcement learning.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 64 of its 101 references that are in the map. First posted on arXiv 8 Jul 2026.

Builds on

64 of 101 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024When Do Off-Policy and On-Policy Policy Gradient Methods Align?19 Feb

Other references · 63

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  3. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  4. 2015Trust Region Policy Optimizationcited by 2,580
  5. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  6. 2016Generative Adversarial Imitation Learningcited by 1,597
  7. 2025Understanding R1-Zero-Like Training: A Critical Perspectivecited by 1,345
  8. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  9. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  10. 2018Is Q-learning Provably Efficient?cited by 487
  11. 2019Introduction to Multi-Armed Banditscited by 481
  12. 2017A Tutorial on Thompson Samplingcited by 433
38 more
  1. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  2. 2025The Landscape of Agentic Reinforcement Learning for LLMs: A Surveycited by 205
  3. 2017A unified view of entropy-regularized Markov decision processescited by 182
  4. 2025Multi-agent Architecture Search via Agentic Supernetcited by 179
  5. 2017Deep Exploration via Randomized Value Functionscited by 156
  6. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  7. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  8. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  9. 2024G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networkscited by 119
  10. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  11. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  12. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  13. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  14. 2025SPIRAL: Self-Play on Zero-Sum Games Incentivizes Reasoning via Multi-Agent Multi-Turn Reinforcement Learningcited by 100
  15. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  16. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  17. 2025MAPoRL: Multi-Agent Post-Co-Training for Collaborative Large Language Models with Reinforcement Learningcited by 86
  18. 2025Chain-of-Agents: End-to-End Agent Foundation Models via Multi-Agent Distillation and Agentic RLcited by 80
  19. 2025ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learningcited by 79
  20. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  21. 2025FlowReasoner: Reinforcing Query-Level Meta-Agentscited by 63
  22. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  23. 2025Co-Evolving LLM Coder and Unit Tester via Reinforcement Learningcited by 56
  24. 2020Efficiently Solving MDPs with Stochastic Mirror Descentcited by 53
  25. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  26. 2025LLM Collaboration With Multi-Agent Reinforcement Learningcited by 49
  27. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  28. 2025MMedAgent-RL: Optimizing Multi-Agent Collaboration for Multimodal Medical Reasoningcited by 40
  29. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 33
  30. 2021Survey on reinforcement learning for language processingcited by 31
  31. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  32. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 27
  33. 2020Kernel-Based Reinforcement Learning: A Finite-Time Analysiscited by 23
  34. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  35. 2013Improved and Generalized Upper Bounds on the Complexity of Policy Iterationcited by 21
  36. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  37. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  38. 2019A First-Order Approach To Accelerated Value Iterationcited by 17

50 most cited of 63 All 63 (JSON)

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  2. 2025Statistical and Algorithmic Foundations of Reinforcement Learning
  3. 2024A General Control-Theoretic Approach for Reinforcement Learning: Theory and Algorithms
  4. 2023Understanding Reinforcement Learning Algorithms: The Progress from Basic Q-learning to Proximal Policy Optimization
  5. 2025Control and Reinforcement Learning through the Lens of Optimization: An Algorithmic Perspective
  6. 2024A Comprehensive Survey of Reinforcement Learning: From Algorithms to Practical Challenges
  7. 2025Bellman operator convergence enhancements in reinforcement learning algorithms
  8. 2024Strongly-polynomial time and validation analysis of policy gradient methods