# Posterior sampling for reinforcement learning: worst-case regret bounds

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2017.

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

- [Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity](https://mlsanity.com/paper/2210.09579/) (2022)
- [Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domain](https://mlsanity.com/paper/2109.06668/) (2021)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)
- [Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexity](https://mlsanity.com/paper/2206.07659/) (2022)
- [Principled Exploration via Optimistic Bootstrapping and Backward Induction](https://mlsanity.com/paper/2105.06022/) (2021)
- [Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality](https://mlsanity.com/paper/2202.06450/) (2022)
- [Robustness Implies Generalization via Data-Dependent Generalization Bounds](https://mlsanity.com/paper/2206.13497/) (2022)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [Near-Optimal Randomized Exploration for Tabular Markov Decision Processes](https://mlsanity.com/paper/2102.09703/) (2021)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)
- [Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2212.13540/) (2022)
- [Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees](https://mlsanity.com/paper/2209.14414/) (2022)
- [On learning Whittle index policy for restless bandits with scalable regret](https://mlsanity.com/paper/2202.03463/) (2022)
- [Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling](https://mlsanity.com/paper/2203.08248/) (2022)
- [Exponential Family Model-Based Reinforcement Learning via Score Matching](https://mlsanity.com/paper/2112.14195/) (2021)
- [Provably Efficient Reinforcement Learning via Surprise Bound](https://mlsanity.com/paper/2302.11634/) (2023)
- [Cascading Reinforcement Learning](https://mlsanity.com/paper/2401.08961/) (2024)
- [Hardness in Markov Decision Processes: Theory and Practice](https://mlsanity.com/paper/2210.13075/) (2022)
- [Posterior Sampling for Competitive RL: Function Approximation and Partial Observation](https://mlsanity.com/paper/2310.19861/) (2023)
- [Efficient Online Decision Tree Learning with Active Feature Acquisition](https://mlsanity.com/paper/2305.02093/) (2023)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?](https://mlsanity.com/paper/2106.08771/) (2021)
- [Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation](https://mlsanity.com/paper/2202.13863/) (2022)
- [Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamics](https://mlsanity.com/paper/2202.05799/) (2022)
- [Online MDP with Transition Prototypes: A Robust Adaptive Approach](https://mlsanity.com/paper/2412.14075/) (2024)
- [Case-Guided Sequential Assay Planning in Drug Discovery](https://mlsanity.com/paper/2601.14710/) (2026)
- [Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning](https://mlsanity.com/paper/2605.15692/) (2026)
- [Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2608.07725/) (2026)
- [Optimal Multi-Reward Reinforcement Learning](https://mlsanity.com/paper/2609.36486/) (2026)

## Abstract (arXiv)

We present an algorithm based on posterior sampling (aka Thompson sampling) that achieves near-optimal worst-case regret bounds when the underlying Markov Decision Process (MDP) is communicating with a finite, though unknown, diameter. Our main result is a high probability regret upper bound of tildeO(DS√AT) for any communicating MDP with S states, A actions and diameter D. Here, regret compares the total reward achieved by the algorithm to the total expected reward of an optimal infinite-horizon undiscounted average reward policy, in time horizon T. This result closely matches the known lower bound of Omega(√DSAT). Our techniques involve proving some novel results about the anti-concentration of Dirichlet distribution, which may be of independent interest.