# Posterior Sampling Reinforcement Learning with Gaussian Processes for Continuous Control: Sublinear Regret Bounds for Unbounded State Spaces

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

## Key facts

- Cited by 2 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 26 of its 53 references that are in the map.
- First posted on arXiv 9 Mar 2026.

## 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, 26 of 26)

- [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)
- [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)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Information Theoretic Regret Bounds for Online Nonlinear Control](https://mlsanity.com/paper/2006.12466/) (2020)
- [Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning](https://mlsanity.com/paper/2006.08684/) (2020)
- [Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning](https://mlsanity.com/paper/2110.00871/) (2021)
- [On Adaptive Linear-Quadratic Regulators](https://mlsanity.com/paper/1806.10749/) (2018)
- [Model-based Reinforcement Learning for Continuous Control with Posterior Sampling](https://mlsanity.com/paper/2012.09613/) (2020)
- [Tight Regret Bounds for Bayesian Optimization in One Dimension](https://mlsanity.com/paper/1805.11792/) (2018)
- [Kernelized Reinforcement Learning with Order Optimal Regret Bounds](https://mlsanity.com/paper/2306.07745/) (2023)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Thompson Sampling for Linear-Quadratic Control Problems](https://mlsanity.com/paper/1703.08972/) (2017)
- [Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification](https://mlsanity.com/paper/2002.09954/) (2020)
- [Multiscale Gaussian Process Level Set Estimation](https://mlsanity.com/paper/1902.09682/) (2019)
- [A Short Note on the Relationship of Information Gain and Eluder Dimension](https://mlsanity.com/paper/2107.02377/) (2021)
- [Optimistic Information Directed Sampling](https://mlsanity.com/paper/2402.15411/) (2024)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/2510.20725/) (2025)
- [Efficient Model-Based Reinforcement Learning Through Optimistic Thompson Sampling](https://mlsanity.com/paper/2410.04988/) (2024)
- [Optimization for Gaussian Processes via Chaining](https://mlsanity.com/paper/1510.05576/) (2015)
- [Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chaining](https://mlsanity.com/paper/1602.04976/) (2016)
- [Sparse Optimistic Information Directed Sampling](https://mlsanity.com/paper/2510.24234/) (2025)

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

- [Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization](https://mlsanity.com/paper/2606.00956/) (2026)
- [Minimax-Optimality of Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2609.33246/) (2026)

## Abstract (arXiv)

We analyze the Bayesian regret of the Gaussian process posterior sampling reinforcement learning (GP-PSRL) algorithm. Posterior sampling is a heuristic for decision-making under uncertainty that has been used to develop successful algorithms for a variety of continuous control problems. However, theoretical work on GP-PSRL is limited. All known regret bounds either have a sub-optimal growth rate, require strong smoothness assumptions, or fail to properly account for the fact that the set of possible system states is unbounded. Through a recursive application of the Borell-Tsirelson-Ibragimov-Sudakov inequality, we show that, with high probability, the states actually visited by the algorithm are contained within a ball of near-constant radius. We then use the chaining method to control the regret suffered by GP-PSRL under weak smoothness conditions. Our main result is a Bayesian regret bound of the order widetildeO(H√γTT), where H is the horizon, T is the number of time steps and γT is the expected information gain. With this result, we resolve the limitations with prior theoretical work on PSRL, and provide the theoretical foundation and tools for analyzing PSRL in complex settings.