Search papers, labs, and topics across Lattice.
This paper analyzes the Bayesian regret of Gaussian Process Posterior Sampling Reinforcement Learning (GP-PSRL) for continuous control problems with unbounded state spaces. It addresses limitations in prior theoretical work by demonstrating that the states visited by the algorithm are contained within a ball of near-constant radius and using the chaining method to achieve tight dependence on the maximum information gain. The main result is a Bayesian regret bound of $\widetilde{\mathcal{O}}(H^{3/2}\sqrt{γ_{T/H} T})$, providing a theoretical foundation for analyzing PSRL in complex settings.
GP-PSRL can achieve sublinear regret bounds in continuous control even with unbounded state spaces, resolving prior theoretical limitations and opening the door to more complex RL settings.
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.
