Research map / Bandits and online learning
RL theory and MDPs: research map
275 papers on RL theory and MDPs in Bandits and online learning, from ICML, NeurIPS, ICLR, CVPR, AAAI, ICCV and ECCV, and the journals TPAMI, IJCV and JMLR (2016–2026), grouped into 2 clusters and 6 approaches. The busiest year so far is 2021.
What it is
The mathematics of reinforcement learning: how many interactions an agent needs to learn a near-optimal policy in a Markov decision process, with or without function approximation, and how to handle changing or adversarial environments.
Terms you will see on this page:
- MDP
- Markov decision process, the standard model of sequential decisions with states, actions and rewards.
- Function approximation
- representing values or policies with a parametric model instead of a table.
- Regret bound
- a guarantee on how much reward is lost while learning.
Start reading with the most cited papers here:
- Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (NeurIPS 2017 · 138 citations)
- Model-Based Reinforcement Learning with Value-Targeted Regression (ICML 2020 · 63 citations)
Within Bandits and online learning, its share shrank from 13.1% in 2023–24 to 10.1% in 2025–26 (73 → 60 papers at ICML, NeurIPS, ICLR, CVPR and AAAI, the venues with data for all four years).
Explore RL theory and MDPs in the interactive map
Working on something in this topic? Describe your idea in scime atlas to see which approach it falls under, the closest papers by meaning and how crowded the spot has become.
What changed recently
Approaches whose share of the topic moved most between 2023–24 and 2025–26 (ICML, NeurIPS, ICLR, CVPR and AAAI):
- Adversarial MDPs with bandit feedback rising: 10% → 18% of the topic (7 → 11 papers)
- Linear function approximation in RL rising: 26% → 28% of the topic (19 → 17 papers)
- Average-reward and latent MDPs falling: 26% → 20% of the topic (19 → 12 papers)
- Regret bounds with function approximation falling: 26% → 23% of the topic (19 → 14 papers)
Papers from 2025–2026 that are already cited most:
- Online MDP with Prototypes Information: A Robust Adaptive Approach (AAAI 2025 · 1 citations)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · 0 citations)
Approaches and key papers
RL with function approximation · 156 papers
Keywords: rl, function approximation, linear function
Approaches in this cluster:
- Regret bounds with function approximation (80 papers)
Prove instance-dependent and low-switching regret bounds for RL with function approximation. - Linear function approximation in RL (65 papers)
Establish efficient optimistic algorithms for RL with linear and generalized linear features. - Stochastic shortest path (11 papers)
Derive minimax-optimal regret for stochastic shortest path problems.
Most cited and most cited since 2024:
- Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (NeurIPS 2017 · 138 citations)
- Model-Based Reinforcement Learning with Value-Targeted Regression (ICML 2020 · 63 citations)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · 1 citations)
- Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret (ICML 2024 · 1 citations)
Markov decision processes · 119 papers
Keywords: markov decision, decision processes, processes mdps
Approaches in this cluster:
- Average-reward and latent MDPs (57 papers)
Derive regret guarantees for constrained, average-reward, factored, and latent MDPs. - Non-stationary and structured MDPs (32 papers)
Learn unknown, non-stationary, or structured MDPs with provable efficiency. - Adversarial MDPs with bandit feedback (30 papers)
Achieve near-optimal regret in adversarial and delayed-feedback MDPs.
Most cited and most cited since 2024:
- Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes (NeurIPS 2018 · 58 citations)
- Learning Unknown Markov Decision Processes: A Thompson Sampling Approach (NeurIPS 2017 · 54 citations)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · 2 citations)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · 2 citations)
