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

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

## Key facts

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

## Builds on (most cited first, 30 of 32)

- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Randomized Prior Functions for Deep Reinforcement Learning](https://mlsanity.com/paper/1806.03335/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [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)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies](https://mlsanity.com/paper/1905.11527/) (2019)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Optimal Thompson Sampling strategies for support-aware CVaR bandits](https://mlsanity.com/paper/2012.05754/) (2020)
- [From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses](https://mlsanity.com/paper/2205.07704/) (2022)
- [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018)
- [Concentration Inequalities for Multinoulli Random Variables](https://mlsanity.com/paper/2001.11595/) (2020)

## Built on by (most cited first, 12 of 12)

- [Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning](https://mlsanity.com/paper/2310.20007/) (2023)
- [Bridging Imitation and Online Reinforcement Learning: An Optimistic Tale](https://mlsanity.com/paper/2303.11369/) (2023)
- [Provably Efficient and Agile Randomized Q-Learning](https://mlsanity.com/paper/2506.24005/) (2025)
- [Q-learning with Posterior Sampling](https://mlsanity.com/paper/2506.00917/) (2025)
- [Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes](https://mlsanity.com/paper/2512.14617/) (2025)
- [Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need](https://mlsanity.com/paper/2309.15737/) (2023)
- [Deep Actor-Critics with Tight Risk Certificates](https://mlsanity.com/paper/2505.19682/) (2025)
- [Distributional Active Inference](https://mlsanity.com/paper/2601.20985/) (2026)
- [Fitted Q-Iteration with Continuous Actions and Adaptive Data: Smoothed Coverage and Minimax Rates](https://mlsanity.com/paper/2605.05791/) (2026)
- [Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning](https://mlsanity.com/paper/2606.20107/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)
- [Minimax-Optimality of Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2609.33246/) (2026)

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