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

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 $\widetilde{\mathcal{O}}(H\sqrt{\gamma_TT})$, where $H$ is the horizon, $T$ is the number of time steps and $\gamma_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.

Posterior sampling for reinforcement learning (PSRL) is a heuristic method for sequential decision making in which an agent maintains uncertainty about how the world works and chooses actions randomly in proportion to the probability that each action is optimal. Gaussian processes (GPs) are a tractable yet flexible way to represent this uncertainty. We noticed that the existing theory cannot always explain why PSRL with GPs works well, so we wanted to see if we could fix this. We used tools from probability theory to show that the algorithm is unlikely to wander too far from its starting point. This helped us to give a more accurate mathematical description of how quickly the algorithm can learn to make good decisions, which is also a bit more broadly applicable. Our work strengthens the theoretical foundation for a practically successful family of decision-making algorithms, helping to bridge the gap between what works empirically and what we can formally prove.