Research map / Bandits and online learning / RL theory and MDPs
Regret bounds with function approximation
Prove instance-dependent and low-switching regret bounds for RL with function approximation.
79 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2017–2026) · an approach in RL theory and MDPs, keyword cluster “rl · function approximation · linear function”
State History Tried Checklist 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.
19 papers in 2023–24 and 14 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 26.0% to 23.3%.
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
- 2017 · Minimax Regret Bounds for Reinforcement Learning (ICML 2017 · 42 citations)
- 2019 · Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (ICML 2019 · 57 citations)
- 2020 · Model-Based Reinforcement Learning with Value-Targeted Regression (ICML 2020 · 63 citations)
- 2021 · Logarithmic Regret for Reinforcement Learning with Linear Function Approximation (ICML 2021 · 20 citations)
- 2022 · First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach (ICML 2022 · 3 citations)
- 2023 · Non-stationary Risk-Sensitive Reinforcement Learning: Near-Optimal Dynamic Regret, Adaptive Detection, and Separation Design (AAAI 2023 · 2 citations)
- 2024 · Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · 1 citation)
- 2025 · Optimal Regret Bounds via Low-Rank Structured Variation in Non-Stationary Reinforcement Learning (NeurIPS 2025 · 0 citations)
- 2026 · Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation (ICML 2026 · 0 citations)
Earliest papers here
- Minimax Regret Bounds for Reinforcement Learning (ICML 2017 · 42 citations)
- Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (ICML 2017 · 30 citations)
- Online Reinforcement Learning in Stochastic Games (NeurIPS 2017 · 7 citations)
What has been tried
59 papers here report 252 measured changes (a component added, removed or swapped, compared with a baseline): helped 71%, no clear effect 10%, hurt 13%, mixed 6%. Papers mostly publish changes that helped, so "helped" is over-represented.
Ablations in recent papers
| What was changed | Measured on | Result | Effect | Paper |
|---|---|---|---|---|
| Use PI instead of VI | Admission control experiments · empirical regret | No clear effect | Reinforcement Learning and Regret Bounds for Admission Control (ICML 2024 · 0 citations) | |
| Use the tighter Bernstein-Freedman bonus instead of the original Bernstein-Freedman bonus | Toy MDPs (S = 3, A = 3; H = 5, 10; K = 10^5, 10^6) · cumulative regret | 1.87 ± 0.03 | Helped | Position: Constants are Critical in Regret Bounds for Reinforcement Learning (ICML 2025) |
What reviewers will expect
Datasets and baselines named in the 9 papers of this approach from 2025–2026 that have a full-text summary. Leaving out the common ones is a frequent review question.
Baselines
- AMB · 2 of 9 papers
- UCB-Advantage · 2 of 9 papers
- Q-EarlySettled-Advantage · 2 of 9 papers
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 33 papers; from OpenAlex and the papers' affiliations).
- Google · 7 papers
- Amazon · 5 papers
- Tel Aviv University · 4 papers
- University of California, Los Angeles · 4 papers
- Peking University · 4 papers
- Tsinghua University · 3 papers
- University of Southern California · 2 papers
- Massachusetts Institute of Technology · 2 papers
- University of Washington · 2 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
- Linear function approximation in RL (64 papers)
- Stochastic shortest path (11 papers)
Elsewhere in the topic
- Average-reward and latent MDPs (57 papers)
- Non-stationary and structured MDPs (30 papers)
- Adversarial MDPs with bandit feedback (30 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).