# Why is Posterior Sampling Better than Optimism for Reinforcement Learning?

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

## Key facts

- Cited by 117 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2016.

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

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [COMBO: Conservative Offline Model-Based Policy Optimization](https://mlsanity.com/paper/2102.08363/) (2021)
- [Exploration in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2205.00824/) (2022)
- [POEM: Out-of-Distribution Detection with Posterior Sampling](https://mlsanity.com/paper/2206.13687/) (2022)
- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Shaking the foundations: delusions in sequence models for interaction and control](https://mlsanity.com/paper/2110.10819/) (2021)
- [Reinforcement Learning, Bit by Bit](https://mlsanity.com/paper/2103.04047/) (2021)
- [Bayesian decision-making under misspecified priors with applications to meta-learning](https://mlsanity.com/paper/2107.01509/) (2021)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Principled Exploration via Optimistic Bootstrapping and Backward Induction](https://mlsanity.com/paper/2105.06022/) (2021)
- [Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learning](https://mlsanity.com/paper/2206.02072/) (2022)
- [Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environments](https://mlsanity.com/paper/2301.13446/) (2023)
- [Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning](https://mlsanity.com/paper/2111.00633/) (2021)
- [Toward Efficient Exploration by Large Language Model Agents](https://mlsanity.com/paper/2504.20997/) (2025)
- [Online Learning for Stochastic Shortest Path Model via Posterior Sampling](https://mlsanity.com/paper/2106.05335/) (2021)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Adaptive Transmission Scheduling in Wireless Networks for Asynchronous Federated Learning](https://mlsanity.com/paper/2103.01422/) (2021)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Model-Based Uncertainty in Value Functions](https://mlsanity.com/paper/2302.12526/) (2023)
- [Expert-Supervised Reinforcement Learning for Offline Policy Learning and Evaluation](https://mlsanity.com/paper/2006.13189/) (2020)
- [No-Regret Reinforcement Learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2102.12769/) (2021)
- [Latent Plan Transformer for Trajectory Abstraction: Planning as Latent Space Inference](https://mlsanity.com/paper/2402.04647/) (2024)
- [Bayesian Design Principles for Offline-to-Online Reinforcement Learning](https://mlsanity.com/paper/2405.20984/) (2024)
- [Unsupervised Behavior Extraction via Random Intent Priors](https://mlsanity.com/paper/2310.18687/) (2023)
- [Can a Bayesian Oracle Prevent Harm from an Agent?](https://mlsanity.com/paper/2408.05284/) (2024)

## Abstract (arXiv)

Computational results demonstrate that posterior sampling for reinforcement learning (PSRL) dramatically outperforms algorithms driven by optimism, such as UCRL2. We provide insight into the extent of this performance boost and the phenomenon that drives it. We leverage this insight to establish an tildeO(H√SAT) Bayesian expected regret bound for PSRL in finite-horizon episodic Markov decision processes, where H is the horizon, S is the number of states, A is the number of actions and T is the time elapsed. This improves upon the best previous bound of tildeO(H S √AT) for any reinforcement learning algorithm.