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

arXiv: https://arxiv.org/abs/2206.07659 · HTML: https://mlsanity.com/paper/2206.07659/

## 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 (most cited first, 30 of 37)

- [World Models](https://mlsanity.com/paper/1803.10122/) (2018)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Deep Reinforcement Learning in a Handful of Trials using Probabilistic Dynamics Models](https://mlsanity.com/paper/1805.12114/) (2018)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Planning to Explore via Self-Supervised World Models](https://mlsanity.com/paper/2005.05960/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Contextual Markov Decision Processes](https://mlsanity.com/paper/1502.02259/) (2015)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Deep Dynamics Models for Learning Dexterous Manipulation](https://mlsanity.com/paper/1909.11652/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [On the Sample Complexity of the Linear Quadratic Regulator](https://mlsanity.com/paper/1710.01688/) (2017)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Naive Exploration is Optimal for Online LQR](https://mlsanity.com/paper/2001.09576/) (2020)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Generalization and Exploration via Randomized Value Functions](https://mlsanity.com/paper/1402.0635/) (2014)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)

## Built on by (most cited first, 30 of 32)

- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration](https://mlsanity.com/paper/2305.18258/) (2023)
- [Learning in POMDPs is Sample-Efficient with Hindsight Observability](https://mlsanity.com/paper/2301.13857/) (2023)
- [Bayesian Design Principles for Frequentist Sequential Learning](https://mlsanity.com/paper/2310.00806/) (2023)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption](https://mlsanity.com/paper/2402.08991/) (2024)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Model-Free Reinforcement Learning with the Decision-Estimation Coefficient](https://mlsanity.com/paper/2211.14250/) (2022)
- [Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.01380/) (2023)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2405.20165/) (2024)
- [LLM Routing with Dueling Feedback](https://mlsanity.com/paper/2510.00841/) (2025)
- [A General Framework for Sequential Decision-Making under Adaptivity Constraints](https://mlsanity.com/paper/2306.14468/) (2023)
- [Provably Efficient UCB-type Algorithms For Learning Predictive State Representations](https://mlsanity.com/paper/2307.00405/) (2023)
- [Bridging Imitation and Online Reinforcement Learning: An Optimistic Tale](https://mlsanity.com/paper/2303.11369/) (2023)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Satisficing Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/2407.12185/) (2024)
- [Efficient Online Learning with Offline Datasets for Infinite Horizon MDPs: A Bayesian Approach](https://mlsanity.com/paper/2310.11531/) (2023)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [Regret Minimization via Saddle Point Optimization](https://mlsanity.com/paper/2403.10379/) (2024)
- [Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits](https://mlsanity.com/paper/2511.02123/) (2025)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Theoretical Foundations and Effective Algorithms for Policy-Aware Simulator Learning](https://mlsanity.com/paper/2605.29032/) (2026)
- [Sample-Efficient Multi-Agent RL: An Optimization Perspective](https://mlsanity.com/paper/2310.06243/) (2023)
- [Optimistic Thompson Sampling for No-Regret Learning in Unknown Games](https://mlsanity.com/paper/2402.09456/) (2024)
- [Q-learning with Posterior Sampling](https://mlsanity.com/paper/2506.00917/) (2025)
- [BFTS: Thompson Sampling with Bayesian Additive Regression Trees](https://mlsanity.com/paper/2602.07767/) (2026)

## 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.