mlsanityData to 7 Oct 2026

Posterior sampling for reinforcement learning: worst-case regret bounds

arXiv 1705.07041 ↗First posted 19 May 2017cs.LGcited by 28

Not on the map. Why?

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.

Key facts. Cited by 28 papers in the map (data through 7 Oct 2026). First posted on arXiv 19 May 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 13; 2023: 3; 2024: 2; 2025: 1; 2026: 3.

28 papers.

Sort:

  1. 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
  2. 2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 57
  3. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  4. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  5. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  6. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  7. 2022Robustness Implies Generalization via Data-Dependent Generalization Boundscited by 23
  8. 2021Sublinear Regret for Learning POMDPscited by 19
  9. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 14
  10. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  11. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  12. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
16 more
  1. 2022Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Samplingcited by 10
  2. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 9
  3. 2021Exponential Family Model-Based Reinforcement Learning via Score Matchingcited by 5
  4. 2023Provably Efficient Reinforcement Learning via Surprise Boundcited by 4
  5. 2024Cascading Reinforcement Learningcited by 4
  6. 2022Hardness in Markov Decision Processes: Theory and Practicecited by 3
  7. 2023Efficient Online Decision Tree Learning with Active Feature Acquisitioncited by 2
  8. 2023Posterior Sampling for Competitive RL: Function Approximation and Partial Observationcited by 2
  9. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  10. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  11. 2022Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximationcited by 1
  12. 2022Rate-matching the regret lower-bound in the linear quadratic regulator with unknown dynamicscited by 0
  13. 2024Online MDP with Transition Prototypes: A Robust Adaptive Approachcited by 0
  14. 2026Case-Guided Sequential Assay Planning in Drug Discoverycited by 0
  15. 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learningcited by 0
  16. 2026Optimal Multi-Reward Reinforcement Learningcited by 0