Statistical and Algorithmic Foundations of Reinforcement Learning

2025/07/19 by Chi, Yuejie, Chen, Yuxin, Wei, Yuting · 1 citation
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2507.14444

Abstract

As a paradigm for sequential decision making in unknown environments, reinforcement learning (RL) has received a flurry of attention in recent years. However, the explosion of model complexity in emerging applications and the presence of nonconvexity exacerbate the challenge of achieving efficient RL in sample-starved situations, where data collection is expensive, time-consuming, or even high-stakes (e.g., in clinical trials, autonomous systems, and online advertising). How to understand and enhance the sample and computational efficacies of RL algorithms is thus of great interest. In this tutorial, we aim to introduce several important algorithmic and theoretical developments in RL, highlighting the connections between new ideas and classical topics. Employing Markov Decision Processes as the central mathematical model, we cover several distinctive RL scenarios (i.e., RL with a simulator, online RL, offline RL, robust RL, and RL with human feedback), and present several mainstream RL approaches (i.e., model-based approach, value-based approach, and policy optimization). Our discussions gravitate around the issues of sample complexity, computational efficiency, as well as algorithm-dependent and information-theoretic lower bounds from a non-asymptotic viewpoint.

Citations

• Actor-Critics Can Achieve Optimal Sample Efficiency
• A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms
• Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning
• Statistical Inference for Policy Evaluation with Temporal Difference Learning
• The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis
• The Sample-Communication Complexity Trade-off in Federated Q-Learning
• Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
• Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF
• Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty
• Federated Offline Reinforcement Learning: Collaborative Single-Policy Coverage Suffices
• On the Foundation of Distributionally Robust Reinforcement Learning
• Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning
• Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
• Settling the Sample Complexity of Online Reinforcement Learning
• Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlation
• Direct Preference Optimization: Your Language Model is Secretly a Reward Model
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model
• Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time
• The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond
• Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning
• Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning
• Policy learning "without" overlap: Pessimism and generalized empirical Bernstein's inequality
• Leveraging Offline Data in Online Reinforcement Learning
• Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient
• The Role of Coverage in Online Reinforcement Learning
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games
• Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyond
• Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model
• Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity
• Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies
• The Efficacy of Pessimism in Asynchronous Q-Learning
• Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism
• Training language models to follow instructions with human feedback
• Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity
• On the Convergence Rates of Policy Gradient Methods
• The Statistical Complexity of Interactive Decision Making
• Sample Complexity of Robust Reinforcement Learning with a Generative Model
• Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning
• Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning
• Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence
• On the Linear convergence of Natural Policy Gradient Algorithm
• Nearly Horizon-Free Offline Reinforcement Learning
• Bilinear Classes: A Structural Framework for Provable Generalization in RL
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes
• Is Pessimism Provably Efficient for Offline RL?
• Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon
• Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality
• On Linear Convergence of Policy Gradient Methods for Finite MDPs
• Bandit Algorithms
• Learning and Planning in Average-Reward Markov Decision Processes
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Task-agnostic Exploration in Reinforcement Learning
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample\n Complexity
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Tightening Exploration in Upper Confidence Reinforcement Learning
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis
• Reward-Free Exploration for Reinforcement Learning
• Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
• Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning
• Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs
• 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
• Global Optimality Guarantees For Policy Gradient Methods
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Learning Models with Uniform Performance via Distributionally Robust Optimization
• Is Q-learning Provably Efficient?
• A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• Boltzmann Exploration Done Right
• Minimax Regret Bounds for Reinforcement Learning
• Quantifying Distributional Model Risk via Optimal Transport
• Data-Driven Robust Optimization
• Data-driven robust optimization
• Robust Markov Decision Processes
• Distributionally Robust Markov Decision Processes
• Robust Dynamic Programming
• Quantal Response Equilibria for Normal Form Games
• RANK ANALYSIS OF INCOMPLETE BLOCK DESIGNS
• A Stochastic Approximation Method
• Reinforcement Learning: An Introduction

Cited by

• Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimation

Related

• Human-Inspired Framework to Accelerate Reinforcement Learning
• Understanding Reinforcement Learning Algorithms: The Progress from Basic Q-learning to Proximal Policy Optimization
• A Comprehensive Survey of Reinforcement Learning: From Algorithms to Practical Challenges
• Introduction to Reinforcement Learning
• Reinforcement Learning: An Overview