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

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

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

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [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)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (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)
- [Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning](https://mlsanity.com/paper/2006.08684/) (2020)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2007.11849/) (2020)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [On Online Learning in Kernelized Markov Decision Processes](https://mlsanity.com/paper/1911.01871/) (2019)
- [A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning](https://mlsanity.com/paper/2208.10904/) (2022)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [The Elliptical Potential Lemma Revisited](https://mlsanity.com/paper/2010.10182/) (2020)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation](https://mlsanity.com/paper/2102.07301/) (2021)
- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)
- [Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification](https://mlsanity.com/paper/2002.09954/) (2020)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)

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

- [On Regret Bounds of Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2603.09276/) (2026)
- [Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces](https://mlsanity.com/paper/2603.08287/) (2026)
- [Minimax-Optimality of Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2609.33246/) (2026)
- [Equilibrium Learning in Unbounded Stochastic Games with Gaussian Transitions](https://mlsanity.com/paper/2610.16149/) (2026)

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