Mathematical methods of reinforcement learning

2026/01/01 by Denis Vital'evich Belomestny, Denis Belomestny, Alexander Vladimirovich Gasnikov +10
Computer Science · #Adaptive Dynamic Programming Control #Bellman equation #Convex analysis #Convex function #Markov chain #Markov decision process #Markov process #Operator (biology) #Q-learning #Reinforcement Learning in Robotics #Reinforcement learning #Stochastic Gradient Optimization Techniques #Variational inequality

paper · doi:10.4213/rm10328

crossref issued 2026/01/01 · crossref published 2026/01/01 · crossref published-print 2026/01/01 · openalex publication_date 2026/01/01 · crossref published-online 2026/07/31 · crossref created 2026/07/31 · crossref deposited 2026/07/31 · crossref indexed 2026/07/31 · openalex created_date 2026/08/01 · openalex updated_date 2026/08/02

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 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. 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 who are interested in RL. Bibliography: 122 titles.

Citations

• The Landscape of Agentic Reinforcement Learning for LLMs: A Survey
• Wisdom of the Crowd: Reinforcement Learning from Coevolutionary Collective Feedback
• Gaussian Approximation for Two-Timescale Linear Stochastic Approximation
• LLM Collaboration With Multi-Agent Reinforcement Learning
• Chain-of-Agents: End-to-End Agent Foundation Models via Multi-Agent Distillation and Agentic RL
• How to Train a Leader: Hierarchical Reasoning in Multi-Agent LLMs
• SPIRAL: Self-Play on Zero-Sum Games Incentivizes Reasoning via Multi-Agent Multi-Turn Reinforcement Learning
• Co-Evolving LLM Coder and Unit Tester via Reinforcement Learning
• MMedAgent-RL: Optimizing Multi-Agent Collaboration for Multimodal Medical Reasoning
• Statistical inference for Linear Stochastic Approximation with Markovian Noise
• FlowReasoner: Reinforcing Query-Level Meta-Agents
• Understanding R1-Zero-Like Training: A Critical Perspective
• Deep Belief Markov Models for POMDP Inference
• ReMA: Learning to Meta-think for LLMs with Multi-Agent Reinforcement Learning
• MAPoRL: Multi-Agent Post-Co-Training for Collaborative Large Language Models with Reinforcement Learning
• Multi-agent Architecture Search via Agentic Supernet
• G-Designer: Architecting Multi-agent Communication Topologies via Graph Neural Networks
• When Do Off-Policy and On-Policy Policy Gradient Methods Align?
• BioXP-0.5B: Explainable Medical-AI via RL-GRPO
• Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
• Optimal Sample Complexity for Average Reward Markov Decision Processes
• Direct Preference Optimization: Your Language Model is Secretly a Reward Model
• Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization
• Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation
• From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses
• A Statistical Analysis of Polyak-Ruppert Averaged Q-learning
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
• From Convex Optimization to MDPs: A Review of First-Order, Second-Order and Quasi-Newton Methods for MDPs
• Near-Optimal Randomized Exploration for Tabular Markov Decision Processes
• Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes
• Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration
• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
• Efficiently Solving MDPs with Stochastic Mirror Descent
• Bandit Algorithms
• Variational Policy Gradient Method for Reinforcement Learning with General Utilities
• A Unifying View of Optimism in Episodic Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Variance-reduced Q-learning is minimax optimal
• Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• A First-Order Approach To Accelerated Value Iteration
• Introduction to Multi-Armed Bandits
• Is Q-learning Provably Efficient?
• Proximal Policy Optimization Algorithms
• A Tutorial on Thompson Sampling
• A unified view of entropy-regularized Markov decision processes
• Deep Exploration via Randomized Value Functions
• Minimax Regret Bounds for Reinforcement Learning
• Generative Adversarial Imitation Learning
• Asynchronous Methods for Deep Reinforcement Learning
• Trust Region Policy Optimization
• Generalization and Exploration via Randomized Value Functions
• (More) Efficient Reinforcement Learning via Posterior Sampling
• Improved and Generalized Upper Bounds on the Complexity of Policy Iteration
• Further Optimal Regret Bounds for Thompson Sampling
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• Asymptotically efficient adaptive allocation rules
• A Markovian Decision Process
• Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons
• Some methods of speeding up the convergence of iteration methods
• Some aspects of the sequential design of experiments
• Human-level control through deep reinforcement learning
• Learning to predict by the methods of temporal differences
• A Brief Survey of Deep Reinforcement Learning