mlsanityData to 7 Oct 2026

Why is Posterior Sampling Better than Optimism for Reinforcement Learning?

arXiv 1607.00215 ↗First posted 1 Jul 2016stat.ML cs.AI cs.LGcited by 116

Not on the map. Why?

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.

Key facts. Cited by 116 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Jul 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 3; 2021: 23; 2022: 19; 2023: 20; 2024: 21; 2025: 17; 2026: 13.

116 papers.

Sort:

By area:

  1. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  2. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  3. 2021COMBO: Conservative Offline Model-Based Policy Optimizationcited by 365
  4. 2022Exploration in Deep Reinforcement Learning: A Surveycited by 158
  5. 2022POEM: Out-of-Distribution Detection with Posterior Samplingcited by 108
  6. 2021A Survey of Exploration Methods in Reinforcement Learningcited by 68
  7. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  8. 2021Shaking the foundations: delusions in sequence models for interaction and controlcited by 61
  9. 2021Reinforcement Learning, Bit by Bitcited by 59
  10. 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
  11. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  12. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
38 more
  1. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  2. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  3. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 23
  4. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  5. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  6. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  7. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  8. 2021Adaptive Transmission Scheduling in Wireless Networks for Asynchronous Federated Learningcited by 15
  9. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  10. 2023Model-Based Uncertainty in Value Functionscited by 15
  11. 2025Toward Efficient Exploration by Large Language Model Agentscited by 15
  12. 2020Expert-Supervised Reinforcement Learning for Offline Policy Learning and Evaluationcited by 14
  13. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  14. 2024Latent Plan Transformer for Trajectory Abstraction: Planning as Latent Space Inferencecited by 14
  15. 2024Bayesian Design Principles for Offline-to-Online Reinforcement Learningcited by 14
  16. 2021No-Regret Reinforcement Learning with Heavy-Tailed Rewardscited by 13
  17. 2023Unsupervised Behavior Extraction via Random Intent Priorscited by 13
  18. 2021On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Controlcited by 12
  19. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  20. 2024Can a Bayesian Oracle Prevent Harm from an Agent?cited by 12
  21. 2025Know When to Explore: Difficulty-Aware Certainty as a Guide for LLM Reinforcement Learningcited by 12
  22. 2023Probabilistic Inference in Reinforcement Learning Done Rightcited by 11
  23. 2023Social Contract AI: Aligning AI Assistants with Implicit Group Normscited by 9
  24. 2021Continuous Control With Ensemble Deep Deterministic Policy Gradientscited by 8
  25. 2023Shattering the Agent-Environment Interface for Fine-Tuning Inclusive Language Modelscited by 8
  26. 2021Online Learning of Energy Consumption for Navigation of Electric Vehiclescited by 7
  27. 2022Posterior Coreset Construction with Kernelized Stein Discrepancy for Model-Based Reinforcement Learningcited by 7
  28. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  29. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  30. 2024Function-space Parameterization of Neural Networks for Sequential Learningcited by 7
  31. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
  32. 2021Variational Bayesian Optimistic Samplingcited by 6
  33. 2022On Rate-Distortion Theory in Capacity-Limited Cognition & Reinforcement Learningcited by 6
  34. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  35. 2024Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgentcited by 6
  36. 2024Beyond Optimism: Exploration With Partially Observable Rewardscited by 6
  37. 2025LLM Routing with Dueling Feedbackcited by 6
  38. 2021State-Aware Variational Thompson Sampling for Deep Q-Networkscited by 5

50 most cited of 116 All 116 (JSON)