Research map / Bandits and online learning / RL theory and MDPs
Non-stationary and structured MDPs
Learn unknown, non-stationary, or structured MDPs with provable efficiency.
30 accepted papers at ICML, NeurIPS, ICLR, CVPR and AAAI (2016–2026) · an approach in RL theory and MDPs, keyword cluster “markov decision · decision processes · processes mdps”
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.
8 papers in 2023–24 and 5 in 2025–26 (at ICML, NeurIPS, ICLR, CVPR and AAAI); its share of the topic shrank, from 11.0% to 8.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
- 2016 · Bounded Optimal Exploration in MDP (AAAI 2016 · 10 citations)
- 2017 · Learning Unknown Markov Decision Processes: A Thompson Sampling Approach (NeurIPS 2017 · 54 citations)
- 2018 · Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes (NeurIPS 2018 · 58 citations)
- 2020 · Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (ICML 2020 · 29 citations)
- 2021 · Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping (ICML 2021 · 23 citations)
- 2022 · Reinforcement Learning Augmented Asymptotically Optimal Index Policy for Finite-Horizon Restless Bandits (AAAI 2022 · 12 citations)
- 2023 · Reinforcement Learning with History Dependent Dynamic Contexts (ICML 2023 · 0 citations)
- 2024 · Online Markov Decision Processes Configuration with Continuous Decision Space (AAAI 2024 · 2 citations)
- 2025 · Online MDP with Prototypes Information: A Robust Adaptive Approach (AAAI 2025 · 1 citation)
- 2026 · Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation? (ICLR 2026 · 0 citations)
Earliest papers here
- Bounded Optimal Exploration in MDP (AAAI 2016 · 10 citations)
- Learning Unknown Markov Decision Processes: A Thompson Sampling Approach (NeurIPS 2017 · 54 citations)
- Fast-Tracking Stationary MOMDPs for Adaptive Management Problems (AAAI 2017 · 10 citations)
What has been tried
26 papers here report 121 measured changes (a component added, removed or swapped, compared with a baseline): helped 76%, no clear effect 8%, hurt 14%, mixed 2%. Papers mostly publish changes that helped, so "helped" is over-represented.
Recent preprints
Loading recent arXiv preprints…
Who publishes on it
Institutions on the most papers of this approach since 2023 (of 13 papers; from OpenAlex and the papers' affiliations).
- Politecnico di Milano · 2 papers
- Google · 2 papers
- Polytechnic Institute of Milan · 2 papers
Use it
Download BibTeX of 27 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
- Average-reward and latent MDPs (57 papers)
- Adversarial MDPs with bandit feedback (30 papers)
Elsewhere in the topic
- Regret bounds with function approximation (79 papers)
- Linear function approximation in RL (64 papers)
- Stochastic shortest path (11 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).