mlsanityData to 7 Oct 2026

Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning

arXiv 2310.20007 ↗First posted 30 Oct 2023stat.ML cs.AI cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

In this paper, we prove the first Bayesian regret bounds for Thompson Sampling in reinforcement learning in a multitude of settings. We simplify the learning problem using a discrete set of surrogate environments, and present a refined analysis of the information ratio using posterior consistency. This leads to an upper bound of order widetildeO(H√dl1T) in the time inhomogeneous reinforcement learning problem where H is the episode length and dl1 is the Kolmogorov l1-dimension of the space of environments. We then find concrete bounds of dl1 in a variety of settings, such as tabular, linear and finite mixtures, and discuss how how our results are either the first of their kind or improve the state-of-the-art.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 36 of its 44 references that are in the map. First posted on arXiv 30 Oct 2023.

Builds on

36 of 44 references.

References · 36

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  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. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  8. 2014An Information-Theoretic Analysis of Thompson Samplingcited by 178
  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. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
24 more
  1. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
  2. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  3. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  4. 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
  5. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  6. 2019An Information-Theoretic Approach to Minimax Regret in Partial Monitoringcited by 41
  7. 2020Mirror Descent and the Information Ratiocited by 39
  8. 2018An Information-Theoretic Analysis for Thompson Sampling with Many Actionscited by 35
  9. 2020Asymptotically Optimal Information-Directed Samplingcited by 33
  10. 2019On Online Learning in Kernelized Markov Decision Processescited by 32
  11. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 30
  12. 2017Information Directed Sampling for Stochastic Bandits with Graph Feedbackcited by 24
  13. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  14. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  15. 2020Model-based Reinforcement Learning for Continuous Control with Posterior Samplingcited by 21
  16. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  17. 2022Deciding What to Model: Value-Equivalent Sampling for Reinforcement Learningcited by 19
  18. 2019First-Order Bayesian Regret Analysis of Thompson Samplingcited by 17
  19. 2022Contextual Information-Directed Samplingcited by 16
  20. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  21. 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15
  22. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  23. 2023Toward Large Kernel Modelscited by 12
  24. 2022Posterior Coreset Construction with Kernelized Stein Discrepancy for Model-Based Reinforcement Learningcited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 2; 2026: 1.

7 papers.

  1. 2025Sample-Efficient Reinforcement Learning from Human Feedback via Information-Directed Samplingcited by 4
  2. 2024Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learningcited by 2
  3. 2025Provably Efficient and Agile Randomized Q-Learningcited by 2
  4. 2024Learning with Posterior Sampling for Revenue Management under Time-varying Demandcited by 1
  5. 2024Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regretcited by 1
  6. 2024Thompson Sampling for Infinite-Horizon Discounted Decision Processescited by 0
  7. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0