Research map / Reinforcement learning / MDPs and planning
Offline RL sample complexity
Prove near-optimal offline RL guarantees with pessimism and variance reduction.
86 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in MDPs and planning, keyword cluster “sample complexity · function approximation · epsilon”
State History Tried Preprints Who Export
Where it stands
Not enough benchmark data Fewer than four papers report the same benchmark, so there is no record to follow.
29 papers in 2023–24 and 26 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic held steady, from 14.3% to 14.9%.
How this is decided
A benchmark is tracked when at least four papers of this approach report their own method on the same dataset and metric in at least two different years. Its record is the best number reported up to 2024 compared with the best reported in 2025–26: still improving means at least 1% better, flat means at most 0.2% better with at least two papers from 2025–26 trying. Numbers on a different scale from the rest (a fraction among percentages) and far outliers are left out. Results come from different papers with different setups, so they are signals, not head-to-head comparisons. The share of papers is counted at ICML, NeurIPS, ICLR, CVPR and AAAI.
How it got here
Most cited paper of each year
- 2016 · Compressed Conditional Mean Embeddings for Model-Based Reinforcement Learning (AAAI 2016 · 18 citations)
- 2018 · Scalable Bilinear Pi Learning Using State and Action Features (ICML 2018 · 28 citations)
- 2019 · Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling (NeurIPS 2019 · 67 citations)
- 2020 · Efficiently Solving MDPs with Stochastic Mirror Descent (ICML 2020 · 17 citations)
- 2021 · Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (NeurIPS 2021 · 18 citations)
- 2022 · Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approach (AAAI 2022 · 23 citations)
- 2023 · Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes (ICML 2023 · 4 citations)
- 2024 · A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs (ICML 2024 · 1 citation)
- 2025 · Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization (ICML 2025 · 2 citations)
- 2026 · Fast Non-Episodic Finite-Horizon RL with K-Step Lookahead Thresholding (ICML 2026 · 0 citations)
Earliest papers here
- Compressed Conditional Mean Embeddings for Model-Based Reinforcement Learning (AAAI 2016 · 18 citations)
- Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis (AAAI 2016 · 17 citations)
- Incremental Stochastic Factorization for Online Reinforcement Learning (AAAI 2016 · 10 citations)
What has been tried
61 papers here report 292 measured changes (a component added, removed or swapped, compared with a baseline): helped 68%, no clear effect 9%, hurt 15%, mixed 7%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use full factorization (K_ω = 4) rather than partial or no factorization | Imperfectly factorizable synthetic MDPs · convergence speed and asymptotic error | Mixed | Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization (ICML 2025 · 2 citations) | |
| remove deviation-control clipping of Q | Tabular infinite-horizon average-reward MDPs · deviation between value-function sequences | m_t - m (t + 1) | No clear effect | A Computationally Efficient Algorithm for Infinite-Horizon Average-Reward Linear MDPs (ICML 2025 · 0 citations) |
| Remove the pure exploration phase | Non-star-convex linear MDP · value-function covering number | at least as large as the number of states | Hurt | Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces (ICML 2025 · 0 citations) |
| Use η_k = β_k = k^{-2/3} instead of the other tested schedules | Random MDP simulations · convergence rate | Helped | On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · 0 citations) | |
| add a target network to over-parameterized TD | Baird's counterexample · value prediction error | Helped | Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation (ICML 2024 · 0 citations) |
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 55 papers; from OpenAlex and the papers' affiliations).
- Google DeepMind · 5 papers
- Google · 4 papers
- University of Wisconsin - Madison · 4 papers
- University of Alberta · 4 papers
- Indian Institute of Technology · 4 papers
- Purdue University · 4 papers
- Tsinghua University · 3 papers
- Hong Kong University of Science and Technology · 3 papers
- Peking University · 3 papers
- University of California, Los Angeles · 3 papers
Use it
Download BibTeX of 40 key papersOpen the topic in the interactive map
Get alerts. Describe your idea in scime atlas and save it (free scime account): you get a weekly email when new preprints land close to it.
Related approaches
Same keyword cluster
- Function approximation in RL theory (93 papers)
- Policy optimization theory (61 papers)
- Rich-observation exploration (53 papers)
Elsewhere in the topic
- Average-reward and regularized MDPs (135 papers)
- POMDPs and confounded RL (99 papers)
- Robust MDP policy gradient (87 papers)
- POMDP policy optimization (68 papers)
Benchmark numbers, ablations and baseline numbers are extracted by AI from each paper's full text and can be wrong; the paper is the authority. Data: results index of 2026-11-02, citation counts from OpenAlex (2026-10-09).