mlsanityData to 14 Oct 2026

No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes

arXiv 2510.20725 ↗First posted 23 Oct 2025cs.LGcited by 4

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Thompson sampling (TS) is a powerful and widely used strategy for sequential decision-making, with applications ranging from Bayesian optimization to reinforcement learning (RL). Despite its success, the theoretical foundations of TS remain limited, particularly in settings with complex temporal structure such as RL. We address this gap by establishing no-regret guarantees for TS using models with Gaussian marginal distributions. Specifically, we consider TS in episodic RL with joint Gaussian process (GP) priors over rewards and transitions. We prove a regret bound of mathcaltildeO(√KHGamma(KH)) over K episodes of horizon H, where Gamma(·) captures the complexity of the GP model. Our analysis addresses several challenges, including the non-Gaussian nature of value functions and the recursive structure of Bellman updates, and extends classical tools such as the elliptical potential lemma to multi-output settings. This work advances the understanding of TS in RL and highlights how structural assumptions and model uncertainty shape its performance in finite-horizon Markov Decision Processes.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 34 of its 57 references that are in the map. First posted on arXiv 23 Oct 2025.

Builds on

34 of 57 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm30 Oct
  2. 2024Efficient Model-Based Reinforcement Learning Through Optimistic Thompson Sampling7 Oct
  3. 2024NeoRL: Efficient Exploration for Nonepisodic RL3 Jun

Other references · 31

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 609
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2017A Tutorial on Thompson Samplingcited by 433
  7. 2017On Kernelized Multi-armed Banditscited by 352
  8. 2013Learning to Optimize Via Posterior Samplingcited by 256
  9. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  10. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  11. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  12. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
19 more
  1. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  2. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  3. 2020Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planningcited by 86
  4. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  5. 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
  6. 2020Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 48
  7. 2013Thompson Sampling for 1-Dimensional Exponential Family Banditscited by 42
  8. 2014Near-optimal Reinforcement Learning in Factored MDPscited by 41
  9. 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
  10. 2019On Online Learning in Kernelized Markov Decision Processescited by 35
  11. 2022A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learningcited by 31
  12. 2023On the Sublinear Regret of GP-UCBcited by 26
  13. 2020The Elliptical Potential Lemma Revisitedcited by 23
  14. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  15. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  16. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  17. 2020Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsificationcited by 13
  18. 2022Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Timescited by 13
  19. 2018Efficient Model-Free Reinforcement Learning Using Gaussian Processcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026On Regret Bounds of Thompson Sampling for Bayesian Optimizationcited by 3
  2. 2026Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spacescited by 2
  3. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0
  4. 2026Equilibrium Learning in Unbounded Stochastic Games with Gaussian Transitionscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Thompson Sampling for Infinite-Horizon Discounted Decision Processes
  2. 2026Nonparametric Bayesian Optimization for General Rewards
  3. 2024More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling
  4. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
  5. 2024Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis
  6. 2025Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown
  7. 2023Thompson Sampling for Linear Bandit Problems with Normal-Gamma Priors
  8. 2025Q-learning with Posterior Sampling