mlsanityData to 14 Oct 2026

A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning

arXiv 2208.10904 ↗First posted 23 Aug 2022cs.LGcited by 31

Not on the map. Why?

Abstract (arXiv)

Thompson Sampling is one of the most effective methods for contextual bandits and has been generalized to posterior sampling for certain MDP settings. However, existing posterior sampling methods for reinforcement learning are limited by being model-based or lack worst-case theoretical guarantees beyond linear MDPs. This paper proposes a new model-free formulation of posterior sampling that applies to more general episodic reinforcement learning problems with theoretical guarantees. We introduce novel proof techniques to show that under suitable conditions, the worst-case regret of our posterior sampling method matches the best known results of optimization based methods. In the linear MDP setting with dimension, the regret of our algorithm scales linearly with the dimension as compared to a quadratic dependence of the existing posterior sampling-based exploration algorithms.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). Builds on 20 of its 35 references that are in the map. First posted on arXiv 23 Aug 2022.

Builds on

20 of 35 references.

References · 20

  1. 2016Deep Exploration via Bootstrapped DQNcited by 527
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  4. 2017Noisy Networks for Explorationcited by 266
  5. 2013Learning to Optimize Via Posterior Samplingcited by 256
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  8. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 219
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  10. 2020Neural Thompson Samplingcited by 128
  11. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  12. 2014Generalization and Exploration via Randomized Value Functionscited by 112
8 more
  1. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  2. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  3. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  4. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  5. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  6. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
  7. 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
  8. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 8; 2024: 10; 2025: 6; 2026: 4.

31 papers.

Sort:

By area:

  1. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  2. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  3. 2024A Single Goal is All You Need: Skills and Exploration Emerge from Contrastive RL without Rewards, Demonstrations, or Subgoalscited by 23
  4. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  5. 2022A Self-Play Posterior Sampling Algorithm for Zero-Sum Markov Gamescited by 16
  6. 2024Bayesian Design Principles for Offline-to-Online Reinforcement Learningcited by 14
  7. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Samplingcited by 12
  8. 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
  9. 2022Eluder-based Regret for Stochastic Contextual MDPscited by 9
  10. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  11. 2024Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theorycited by 7
  12. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
19 more
  1. 2024Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgentcited by 6
  2. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  3. 2023Bridging Imitation and Online Reinforcement Learning: An Optimistic Talecited by 5
  4. 2023Exploiting Causal Graph Priors with Posterior Sampling for Reinforcement Learningcited by 5
  5. 2023Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximationcited by 4
  6. 2024Satisficing Exploration for Deep Reinforcement Learningcited by 4
  7. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 4
  8. 2024Regret Minimization via Saddle Point Optimizationcited by 2
  9. 2025Provably Efficient and Agile Randomized Q-Learningcited by 2
  10. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 2
  11. 2026Optimism Stabilizes Thompson Sampling for Adaptive Inferencecited by 2
  12. 2023Sample-Efficient Multi-Agent RL: An Optimization Perspectivecited by 1
  13. 2025Q-learning with Posterior Samplingcited by 1
  14. 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Errorcited by 0
  15. 2025Concurrent Learning with Aggregated States via Randomized Least Squares Value Iterationcited by 0
  16. 2025When a Reinforcement Learning Agent Encounters Unknown Unknownscited by 0
  17. 2026Bayesian learning for the stochastic shortest path problemcited by 0
  18. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0
  19. 2026High-Probability Regret Bounds for Feel-Good Thompson Samplingcited by 0