Technical Summary: Mathematical Methods of Reinforcement Learning

Problem Statement

Reinforcement learning (RL) has emerged as a primary framework for sequential decision-making under uncertainty, bridging optimal stochastic control, Markov decision processes (MDPs), and statistical decision theory. While classical MDP theory assumes a fully known environment model, RL addresses scenarios where dynamics are initially unknown, requiring the agent to learn through interaction. This learning requirement shifts the performance criteria from likelihood-based risk functions to regret, quantifying the performance loss of a learning policy relative to an optimal one.

The paper addresses the need for a unified mathematical foundation for modern RL algorithms. It seeks to organize the diverse tools from probability, optimization, and operator theory that underpin the design and analysis of RL, covering various time-horizon formulations (finite, discounted, and average reward) and settings (tabular vs. function approximation, model-based vs. model-free).

Methodology and Structure

The survey organizes the mathematical structures of RL into several interconnected domains:

1. Operator-Theoretic Foundations (Dynamic Programming)

The paper establishes the Bellman principle as the core analytical tool, expressing optimal value functions through recursive fixed-point relations.

• Contraction Mappings: It emphasizes that Bellman operators (both consistency and optimality operators) are $\gamma$-contractions in the $\ell_\infty$-norm. This property, via Banach's fixed-point theorem, guarantees the existence and uniqueness of value functions and the convergence of iterative methods like Value Iteration (VI) and Policy Iteration (PI).
• Linear Programming: The optimization over policies is shown to admit an equivalent convex reformulation via linear programming (LP). The dual of the LP corresponds to value functions, while the primal corresponds to occupancy measures. This reveals the hidden convexity of MDPs, particularly when regularized with entropy, transforming the non-convex policy search into a convex optimization over occupancy measures.
• Accelerated Methods: The paper discusses accelerated schemes for solving MDPs (e.g., Accelerated Value Computation) by drawing analogies between the Bellman operator and the gradient of smooth, strongly convex objectives, though it notes the non-differentiability of the optimality operator presents challenges.

2. Generative Model Setting and Sample Complexity

Transitioning to settings where the transition kernel is unknown but accessible via a generative model (oracle), the paper analyzes sample complexity—the number of queries required to find an $\epsilon$-optimal policy.

• Model-Based vs. Model-Free: It contrasts model-based approaches (estimating the transition kernel first, then planning) with model-free approaches (directly learning value functions or policies).
• Lower Bounds: The survey presents "hard instances" (bandit-like MDPs) to derive minimax lower bounds on sample complexity.
  • Discounted MDPs: The lower bound scales as $\tilde{\Omega}\left(\frac{SA}{(1-\gamma)^3 \epsilon^2}\right)$.
  • Average Reward MDPs: The bound depends on the mixing time $t_{mix}$, scaling as $\tilde{\Omega}\left(\frac{SA \cdot t_{mix}}{\epsilon^2}\right)$.
  • Finite-Horizon MDPs: The bound scales as $\tilde{\Omega}\left(\frac{SA H^3}{\epsilon^2}\right)$.
• Algorithms: It reviews algorithms achieving these bounds, including Empirical QVI, Q-learning (and its variance-reduced and averaged variants), and Stochastic Mirror Descent applied to the saddle-point formulation of the LP.

3. Policy Evaluation and Function Approximation

The paper details Temporal Difference (TD) learning, framing it within the Linear Stochastic Approximation (LSA) framework.

• Convergence: It analyzes the convergence of TD(0) under both i.i.d. and Markovian noise, relying on martingale concentration inequalities.
• Off-Policy Stability: It addresses the divergence issues of TD in off-policy settings (e.g., the Baird counterexample) and introduces stable alternatives like GTD2 and TDC, which optimize the Mean Squared Bellman Projection Error (MSBPE).
• Continuous Spaces: For continuous state spaces, the survey covers Fitted Value Iteration (FVI), Kernel-UCBVI (using kernel smoothing for Lipschitz MDPs), and Least-Squares Value Iteration (LSVI) for linear MDPs, providing regret bounds dependent on the covering dimension of the state-action space.

4. Exploration and Randomized Algorithms

The survey explores the trade-off between exploration and exploitation.

• Optimism: It details Optimism in the Face of Uncertainty (OFU) via Upper Confidence Bound (UCB) methods (e.g., UCRL, UCBVI) which add exploration bonuses to rewards or Q-values.
• Randomization: It presents Posterior Sampling for RL (PSRL) and Randomized Least-Squares Value Iteration (RLSVI), where exploration is driven by sampling from a posterior distribution or perturbing value estimates with noise, rather than explicit confidence bounds.

5. Policy Gradient and Modern Applications

The final sections cover Policy Gradient (PG) methods, which optimize parameterized policies directly.

• Gradient Estimators: It covers the REINFORCE estimator, Actor-Critic methods (using TD residuals for low-variance advantage estimation), and Generalized Advantage Estimation (GAE).
• Trust Regions: It discusses Trust Region Policy Optimization (TRPO) and Proximal Policy Optimization (PPO), which constrain policy updates via KL-divergence or clipping to ensure stability.
• Preference Optimization: The paper introduces Direct Preference Optimization (DPO) and Group Relative Policy Optimization (GRPO) as efficient alternatives to PPO, particularly in the context of aligning Large Language Models (LLMs) with human preferences without explicit reward modeling.

Key Contributions and Results

• Unified Framework: The paper provides a cohesive mathematical entry point, unifying algorithmic templates under common operator and variational lenses.
• Convergence Guarantees: It consolidates finite-sample bounds and asymptotic results for value iteration, policy iteration, Q-learning, and stochastic approximation methods, explicitly linking them to contraction properties and martingale theory.
• Sample Complexity Characterization: It clarifies the dependence of sample complexity on the effective horizon ($1/(1-\gamma)$), mixing time, and horizon length $H$, demonstrating the minimax optimality of various algorithms in different settings.
• Hidden Convexity: It highlights the convex reformulation of MDPs via occupancy measures, linking RL to convex optimization and mirror descent.
• Application to NLP: The survey explicitly connects these mathematical foundations to Reinforcement Learning from Human Feedback (RLHF), detailing how PPO, GRPO, and DPO are used to align LLMs with human preferences and safety constraints.

Significance

The paper claims significance as a unified mathematical entry point for researchers in probability, optimization, and statistics interested in reinforcement learning. By tracing the interplay between dynamic programming, stochastic approximation, concentration methods, and function approximation theory, it aims to demystify the theoretical underpinnings of modern RL algorithms. It emphasizes that while RL problems are often non-convex in the policy space, they admit convex reformulations and can be analyzed through the rigorous lens of operator theory and stochastic processes. The survey serves to bridge the gap between classical control theory and modern data-driven learning, particularly in the context of large-scale applications like LLM alignment.