mlsanityData to 14 Oct 2026

Statistical and Algorithmic Foundations of Reinforcement Learning

arXiv 2507.14444 ↗First posted 19 Jul 2025stat.ML cs.AI cs.LGcited by 2

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

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.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 100 of its 158 references that are in the map. First posted on arXiv 19 Jul 2025.

Builds on

100 of 158 references.

References · 100

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 8,065
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,920
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  8. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  9. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  10. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  11. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  12. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
38 more
  1. 2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 238
  2. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  5. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  7. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  10. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  11. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  12. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 161
  13. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 158
  14. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  15. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  16. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  17. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  18. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  19. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  20. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  21. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  22. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  23. 2020Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learningcited by 96
  24. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  25. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  26. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  27. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  28. 2013Data-Driven Robust Optimizationcited by 85
  29. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 85
  30. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  31. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  32. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 83
  33. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  34. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  35. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  36. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  37. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
  38. 2017Boltzmann Exploration Done Rightcited by 69

50 most cited of 100 All 100 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimationcited by 8
  2. 2026Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalizationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Review
  2. 2024A Comprehensive Survey of Reinforcement Learning: From Algorithms to Practical Challenges
  3. 2023Understanding Reinforcement Learning Algorithms: The Progress from Basic Q-learning to Proximal Policy Optimization
  4. 2026Mathematical methods of reinforcement learning
  5. 2026Reinforcement Learning in Operational Research: A Technical Review and Practical Roadmap
  6. 2026Reinforcement Learning in the Real World: A Survey of Statistical Challenges and Future Directions
  7. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  8. 2024Introduction to Reinforcement Learning