# RL theory and sample complexity

Area: [Deep reinforcement learning methods](https://mlsanity.com/deeprl/index.md). HTML: https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/

## Key facts

- RL theory and sample complexity: 1,380 papers on arXiv since 2024 (data through 14 Oct 2026).
- 17 of its 1,380 mapped papers (1%) cite “The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise” (2024, arXiv 2401.07844).
- 13 of its 1,380 mapped papers (1%) cite “Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning” (2024, arXiv 2403.00514).
- 43 new papers 30 Sep–14 Oct.

## Most cited here

- [The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2401.07844/) (2024), cited by 17 papers here
- [Overestimation, Overfitting, and Plasticity in Actor-Critic: the Bitter Lesson of Reinforcement Learning](https://mlsanity.com/paper/2403.00514/) (2024), cited by 13 papers here
- [Elementary Analysis of Policy Gradient Methods](https://mlsanity.com/paper/2404.03372/) (2024), cited by 12 papers here
- [Truly No-Regret Learning in Constrained MDPs](https://mlsanity.com/paper/2402.15776/) (2024), cited by 11 papers here
- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024), cited by 10 papers here
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024), cited by 10 papers here
- [Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation](https://mlsanity.com/paper/2406.01762/) (2024), cited by 10 papers here
- [Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set](https://mlsanity.com/paper/2501.19254/) (2025), cited by 10 papers here
- [Sample-Efficient Constrained Reinforcement Learning with General Parameterization](https://mlsanity.com/paper/2405.10624/) (2024), cited by 9 papers here
- [Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2411.13711/) (2024), cited by 9 papers here

## New (30 Sep–14 Oct)

- [Average-Reward Policy Identification from a Single Continuing Trajectory](https://mlsanity.com/paper/2610.20486/) (2026-10-14)
- [Non-asymptotic Convergence of Average-reward Q-learning with Options](https://mlsanity.com/paper/2610.20347/) (2026-10-14)
- [On the Convergence of Semi-Gradient TD: A Mean Field Perspective](https://mlsanity.com/paper/2610.20014/) (2026-10-14)
- [What Information Buys in Active Inference](https://mlsanity.com/paper/2610.19046/) (2026-10-13)
- [Fast Rates for Offline Q-Learning with KL Regularization](https://mlsanity.com/paper/2610.18839/) (2026-10-13)
- [Stein Variational Distributional Reinforcement Learning: Score-Guided Particles for Multivariate Return Distributions](https://mlsanity.com/paper/2610.17925/) (2026-10-13)
- [Density-Matrix Reinforcement Learning](https://mlsanity.com/paper/2610.17214/) (2026-10-12)
- [Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning](https://mlsanity.com/paper/2610.15871/) (2026-10-11)
- [Mixing Regularization for Average-Reward Q-Learning and Q-Planning](https://mlsanity.com/paper/2610.14988/) (2026-10-10)
- [Hitting-Time Bounds for Asynchronous Q-Learning](https://mlsanity.com/paper/2610.13901/) (2026-10-09)
- [Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking](https://mlsanity.com/paper/2610.13871/) (2026-10-09)
- [Variance-Reduced Policy Gradient is Nearly Minimax-Optimal](https://mlsanity.com/paper/2610.13692/) (2026-10-09)
- [Structure-Aware Numerical Stabilization for Half-Precision Proximal Policy Optimization](https://mlsanity.com/paper/2610.13306/) (2026-10-09)
- [Toward Optimal Regret in Adversarial MDPs with Stochastic Hard Constraints](https://mlsanity.com/paper/2610.12153/) (2026-10-08)
- [Randomized Transport Maps for Model-Free Policy-Gradient Mean-Field Control](https://mlsanity.com/paper/2610.11619/) (2026-10-08)
- [Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach](https://mlsanity.com/paper/2610.10326/) (2026-10-07)
- [A Closed-Loop Non-Asymptotic Convergence Analysis of PPO with Learned Critics and Clipping](https://mlsanity.com/paper/2610.10273/) (2026-10-07)
- [Boundary-aware Reinforcement Learning for Hypercube State Spaces via Deterministic Policy Gradient](https://mlsanity.com/paper/2610.09712/) (2026-10-07)
- [Convex-Concave Reinforcement Learning](https://mlsanity.com/paper/2610.09108/) (2026-10-06)
- [Reinforcement Learning with Segment Reward Feedback under Linear Function Approximation](https://mlsanity.com/paper/2610.08271/) (2026-10-06)
- [Adapting to Changes in Agent Behavior via Finite-Depth Policy Sensitivity](https://mlsanity.com/paper/2610.07475/) (2026-10-05)
- [Optimal Control with Learned Critics under Unmodeled State Dependencies](https://mlsanity.com/paper/2610.05359/) (2026-10-04)
- [Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2610.06931/) (2026-10-03)
- [Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning](https://mlsanity.com/paper/2610.04752/) (2026-10-03)
- [Exact Fast Batch Simulation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2610.04746/) (2026-10-03)
- [Policy as Data: Replay-Based Policy Dual Averaging via Advantage Regression](https://mlsanity.com/paper/2610.04638/) (2026-10-03)
- [A Geometric Perspective on Reward Function Updates in Inverse Reinforcement Learning](https://mlsanity.com/paper/2610.14041/) (2026-10-02)
- [Memory-State Critic for Asymmetric Actor-Critic with Application to Vision-Based Pursuit-Evasion](https://mlsanity.com/paper/2610.03830/) (2026-10-02)
- [Single or Multiple Policies for Phase-Structured Reinforcement Learning?](https://mlsanity.com/paper/2610.03475/) (2026-10-02)
- [Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds](https://mlsanity.com/paper/2610.03165/) (2026-10-02)