mlsanityData to 14 Oct 2026

Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity

arXiv 2206.07659 ↗First posted 15 Jun 2022cs.LG cs.AI stat.MLcited by 32

Not on the map. Why?

Abstract (arXiv)

We propose a general framework to design posterior sampling methods for model-based RL. We show that the proposed algorithms can be analyzed by reducing regret to Hellinger distance in conditional probability estimation. We further show that optimistic posterior sampling can control this Hellinger distance, when we measure model error via data likelihood. This technique allows us to design and analyze unified posterior sampling algorithms with state-of-the-art sample complexity guarantees for many model-based RL settings. We illustrate our general result in many special cases, demonstrating the versatility of our framework.

Key facts. Cited by 32 papers in the map (data through 14 Oct 2026). Builds on 37 of its 58 references that are in the map. First posted on arXiv 15 Jun 2022.

Builds on

37 of 58 references.

References · 37

  1. 2018World Modelscited by 1,513
  2. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  3. 2018Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Modelscited by 774
  4. 2016Deep Exploration via Bootstrapped DQNcited by 527
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  7. 2017A Tutorial on Thompson Samplingcited by 433
  8. 2020Planning to Explore via Self-Supervised World Modelscited by 368
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  10. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  11. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  12. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
25 more
  1. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  2. 2015Contextual Markov Decision Processescited by 220
  3. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  4. 2019Deep Dynamics Models for Learning Dexterous Manipulationcited by 206
  5. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  6. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  7. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  9. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  10. 2017On the Sample Complexity of the Linear Quadratic Regulatorcited by 159
  11. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  12. 2020Naive Exploration is Optimal for Online LQRcited by 116
  13. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  14. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  15. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  16. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  17. 2019Online Control with Adversarial Disturbancescited by 92
  18. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  19. 2020Active Learning for Nonlinear System Identification with Guaranteescited by 80
  20. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  21. 2017Ensemble Samplingcited by 62
  22. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  23. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  24. 2020Learning the Linear Quadratic Regulator from Nonlinear Observationscited by 21
  25. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 14; 2024: 9; 2025: 3; 2026: 4.

32 papers.

Sort:

By area:

  1. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  2. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 27
  3. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  4. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  5. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 18
  6. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 18
  7. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  8. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  9. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12
  10. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  11. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  12. 2024Optimistic Information Directed Samplingcited by 7
20 more
  1. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  2. 2025LLM Routing with Dueling Feedbackcited by 7
  3. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  4. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  5. 2023Bridging Imitation and Online Reinforcement Learning: An Optimistic Talecited by 5
  6. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 4
  7. 2024Satisficing Exploration for Deep Reinforcement Learningcited by 4
  8. 2023Efficient Online Learning with Offline Datasets for Infinite Horizon MDPs: A Bayesian Approachcited by 3
  9. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 3
  10. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  11. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  12. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 2
  13. 2026Optimism Stabilizes Thompson Sampling for Adaptive Inferencecited by 2
  14. 2026Theoretical Foundations and Effective Algorithms for Policy-Aware Simulator Learningcited by 2
  15. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  16. 2024Optimistic Thompson Sampling for No-Regret Learning in Unknown Gamescited by 1
  17. 2025Q-learning with Posterior Samplingcited by 1
  18. 2026BFTS: Thompson Sampling with Bayesian Additive Regression Treescited by 1
  19. 2023Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processescited by 0
  20. 2026High-Probability Regret Bounds for Feel-Good Thompson Samplingcited by 0