Mathematical methods of reinforcement learning
Denis Belomestny, Alexander Gasnikov, Egor Gladin, Alexey Naumov, Artemy Rubtsov, Yuri Sapronov, Daniil Tiapkin, Nikita Yudin
math.OC, cs.LG, stat.ML
Submitted: 2026-07-08
Comments: 65 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory.
Terminology
Abstract
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.
Sources
- The Landscape of Agentic Reinforcement Learning for LLMs: A Survey
- From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPs
- A unified view of entropy-regularized Markov decision processes
- Stochastic Optimization under Hidden Convexity
- Stochastic approximation with cone-contractive operators: Sharp $\ell_\infty$-bounds for $Q$-learning
- Variance-reduced $Q$-learning is minimax optimal
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
- Proximal Policy Optimization Algorithms
- Reinforcement Learning from Human Feedback: A Statistical Perspective
- When Do Off-Policy and On-Policy Policy Gradient Methods Align?
- DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models
- DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Understanding R1-Zero-Like Training: A Critical Perspective
- Multi-agent Architecture Search via Agentic Supernet
- G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks
- MAPoRL: Multi-Agent Post-Co-Training for Collaborative Large Language Models with Reinforcement Learning
- How to Train a Leader: Hierarchical Reasoning in Multi-Agent LLMs
- ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learning
- FlowReasoner: Reinforcing Query-Level Meta-Agents
- Co-Evolving LLM Coder and Unit Tester via Reinforcement Learning
Related papers
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
- Incremental Learning in Mirror Flows
- Beyond Aggregate Drift: Optimal Client-Specific Windows in Federated Learning
- Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets
- Second-Order Optimization with Asynchronous Curvature