mlsanityData to 7 Oct 2026

Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees

arXiv 2209.14414 ↗First posted 28 Sep 2022stat.ML cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

We consider reinforcement learning in an environment modeled by an episodic, finite, stage-dependent Markov decision process of horizon H with S states, and A actions. The performance of an agent is measured by the regret after interacting with the environment for T episodes. We propose an optimistic posterior sampling algorithm for reinforcement learning (OPSRL), a simple variant of posterior sampling that only needs a number of posterior samples logarithmic in H, S, A, and T per state-action pair. For OPSRL we guarantee a high-probability regret bound of order at most widetildeO(√H3SAT) ignoring polylog(HSAT) terms. The key novel technical ingredient is a new sharp anti-concentration inequality for linear forms which may be of independent interest. Specifically, we extend the normal approximation-based lower bound for Beta distributions by Alfers and Dinges [1984] to Dirichlet distributions. Our bound matches the lower bound of order Omega(√H3SAT), thereby answering the open problems raised by Agrawal and Jia [2017b] for the episodic setting.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 32 of its 66 references that are in the map. First posted on arXiv 28 Sep 2022.

Builds on

32 of 66 references.

References · 32

  1. 2016Deep Exploration via Bootstrapped DQNcited by 518
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  5. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 218
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  7. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  8. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  9. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  10. 2017Deep Exploration via Randomized Value Functionscited by 155
  11. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  12. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
20 more
  1. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  2. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  3. 2020Adaptive Reward-Free Explorationcited by 77
  4. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  5. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  6. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
  7. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  8. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  9. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  10. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  11. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  12. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  13. 2018Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Banditscited by 33
  14. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
  15. 2020Optimal Thompson Sampling strategies for support-aware CVaR banditscited by 26
  16. 2022From Dirichlet to Rubin: Optimistic Exploration in RL without Bonusescited by 22
  17. 2018KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpointscited by 20
  18. 2020Concentration Inequalities for Multinoulli Random Variablescited by 12
  19. 2020Towards Tractable Optimism in Model-Based Reinforcement Learningcited by 10
  20. 2021From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 0; 2025: 4; 2026: 5.

12 papers.

  1. 2023Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learningcited by 7
  2. 2023Bridging Imitation and Online Reinforcement Learning: An Optimistic Talecited by 5
  3. 2025Provably Efficient and Agile Randomized Q-Learningcited by 2
  4. 2025Q-learning with Posterior Samplingcited by 1
  5. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processescited by 1
  6. 2023Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Needcited by 0
  7. 2025Deep Actor-Critics with Tight Risk Certificatescited by 0
  8. 2026Distributional Active Inferencecited by 0
  9. 2026A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iterationcited by 0
  10. 2026Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learningcited by 0
  11. 2026Mathematical methods of reinforcement learningcited by 0
  12. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0