mlsanityData to 14 Oct 2026

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

arXiv 2603.08287 ↗First posted 9 Mar 2026stat.ML cs.LGcited by 2

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

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.

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.

Builds on

26 of 53 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes23 Oct
  2. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm30 Oct
  3. 2024Efficient Model-Based Reinforcement Learning Through Optimistic Thompson Sampling7 Oct

Other references · 23

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2013Learning to Optimize Via Posterior Samplingcited by 256
  3. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  5. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  6. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  7. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  8. 2020Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planningcited by 86
  9. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  10. 2018On Adaptive Linear-Quadratic Regulatorscited by 21
  11. 2020Model-based Reinforcement Learning for Continuous Control with Posterior Samplingcited by 21
  12. 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
11 more
  1. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  2. 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
  3. 2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 16
  4. 2017Thompson Sampling for Linear-Quadratic Control Problemscited by 14
  5. 2020Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsificationcited by 13
  6. 2019Multiscale Gaussian Process Level Set Estimationcited by 10
  7. 2021A Short Note on the Relationship of Information Gain and Eluder Dimensioncited by 7
  8. 2024Optimistic Information Directed Samplingcited by 7
  9. 2015Optimization for Gaussian Processes via Chainingcited by 2
  10. 2016Stochastic Process Bandits: Upper Confidence Bounds Algorithms via Generic Chainingcited by 2
  11. 2025Sparse Optimistic Information Directed Samplingcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Towards Regret Guarantees for One-Step Lookahead Bayesian Optimizationcited by 0
  2. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
  2. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation
  3. 2024Thompson Sampling for Infinite-Horizon Discounted Decision Processes
  4. 2025Q-learning with Posterior Sampling
  5. 2024Sublinear Regret for a Class of Continuous-Time Linear-Quadratic Reinforcement Learning Problems
  6. 2026Nonparametric Bayesian Optimization for General Rewards
  7. 2024No-Regret Reinforcement Learning in Smooth MDPs
  8. 2024Horizon-Free Regret for Linear Markov Decision Processes