Sample Complexity in Reinforcement Learning Reading List

Curated by Mouhssine Rifaki | Stanford Electrical Engineering | Last updated August 2026

Foundational and modern results on how many samples an RL agent needs to learn a good policy.

Sample Complexity in Reinforcement Learning: 10 key papers

1. Minimax Regret Bounds for Reinforcement Learning
   Azar et al. arXiv 2017.
2. Near-optimal Regret Bounds for Reinforcement Learning
   Jaksch et al. Journal of Machine Learning Research 2010.
3. Model-based Reinforcement Learning and the Eluder Dimension
   Osband and Van Roy. arXiv 2014.
4. On the Sample Complexity of Reinforcement Learning with a Generative Model
   Azar et al. arXiv 2012.
5. Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
   Jin et al. arXiv 2021.
6. Bilinear Classes: A Structural Framework for Provable Generalization in RL
   Du et al. arXiv 2021.
7. Is Pessimism Provably Efficient for Offline RL?
   Jin et al. arXiv 2020.
8. Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model
   Li et al. arXiv 2020.
9. Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
   Li et al. arXiv 2022.
10. The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model
    Shi et al. arXiv 2023.

Related reading lists

• Linear MDPs & Linear Function Approximation
• Model-Based Reinforcement Learning
• Optimal Control & LQR/LQG
• World Models and Model-Based RL
• Off-Policy Evaluation & Offline Evaluation
• Robust & Risk-Sensitive RL
• Distributional Reinforcement Learning
• Offline Reinforcement Learning