Abstract
We analyze the Bayesian regret of the Gaussian process posterior sampling reinforcement learning (GP-PSRL) algorithm. Posterior sampling is an effective 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 fail to achieve a tight dependence on a kernel-dependent quantity called the maximum information gain 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. To obtain tight dependence on the maximum information gain, we use the chaining method to control the regret suffered by GP-PSRL. Our main result is a Bayesian regret bound of the order $\widetilde{\mathcal{O}}(H^{3/2}\sqrt{γ_{T/H} T})$, where $H$ is the horizon, $T$ is the number of time steps and $γ_{T/H}$ is the maximum 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.
Introduction
In Reinforcement Learning (RL), agents must balance exploration and exploitation. Posterior Sampling (or Thompson Sampling) is a powerful heuristic where an agent maintains a belief about the environment, samples a model from this belief, and acts optimally according to that sample. In continuous control, Gaussian Processes (GPs) are frequently used to model these beliefs due to their uncertainty estimation capabilities.
However, existing theory for GP-based RL has faced two significant hurdles. First, most proofs assume a bounded state space, whereas real-world systems with Gaussian noise can technically reach any state in $\mathbb{R}^d$. This "unbounded state space problem" can cause the Information Gain—a key metric for learning complexity—to explode. Second, previous regret bounds were often loose, scaling poorly with the time horizon $H$ or requiring extreme smoothness in the GP kernel.
Methods: Taming the Unbounded State Space
The authors address these challenges in the GP-PSRL algorithm using two primary mathematical innovations:
1. Recursive BTIS Inequality
To handle the unbounded nature of the state space, the authors employ the Borell-Tsirelson-Ibragimov-Sudakov (BTIS) inequality. They prove that despite the theoretical possibility of infinite wandering, the probability of an agent leaving a localized region is extremely low. By applying this inequality recursively across the horizon $H$, they demonstrate that the agent effectively remains within a "ball of near-constant radius" with high probability.
2. The Chaining Method
To achieve a near-optimal regret bound, the authors use the "chaining" method (Dudley’s integral). This technique allows for controlling the maximum error of the GP model across the state space without requiring the kernel to be four-times differentiable, as required by previous literature. This expansion allows the theory to cover "rougher" kernels like Matérn 1/2.
Results and Empirical Validation
The primary theoretical contribution is a Bayesian regret bound of $\widetilde{\mathcal{O}}(H^{3/2}\sqrt{\gamma_{T/H} T})$. This result matches the best-known rates for simpler bandit problems and improves upon several existing bounds in the literature, as shown in the comparison below.
The authors validated these findings using a 2D navigation task involving a goal state and obstacles. They tested various kernels, including Squared Exponential (SE) and Matérn ($\nu = 1/2, 3/2, 5/2$). The experiments confirmed that smoother kernels (like SE) result in lower regret due to lower information gain. Furthermore, log-log plots of the experimental data aligned with the predicted $\sqrt{T}$ relationship, verifying the theoretical sublinear regret.
Conclusion
This work provides a rigorous theoretical foundation for GP-PSRL in continuous control. By proving that stability is implicit in the GP framework and providing tighter bounds, the authors bridge the gap between heuristic success and theoretical understanding. Future work may address the "Oracle Problem"—the computational difficulty of finding optimal policies in continuous spaces—and extend the theory to locally bounded kernels like the linear kernel.
Summary updated