Search papers, labs, and topics across Lattice.
This paper provides a frequentist regret analysis of Gaussian Process Thompson Sampling (GP-TS) for continuous action spaces, avoiding discretization by using fractional Gaussian process posteriors. They interpret variance inflation in GP-TS as Thompson Sampling with a fractional posterior, deriving a kernel-agnostic regret bound based on information gain and posterior contraction rates. The analysis yields specific regret bounds for squared exponential, Matérn, and rational quadratic kernels, demonstrating a unified, discretization-free regret framework for GP-TS.
Ditch the discretization: this work provides a unified, discretization-free regret analysis for Gaussian Process Thompson Sampling that works across various kernel classes.
We study Gaussian Process Thompson Sampling (GP-TS) for sequential decision-making over compact, continuous action spaces and provide a frequentist regret analysis based on fractional Gaussian process posteriors, without relying on domain discretization as in prior work. We show that the variance inflation commonly assumed in existing analyses of GP-TS can be interpreted as Thompson Sampling with respect to a fractional posterior with tempering parameter $α\in (0,1)$. We derive a kernel-agnostic regret bound expressed in terms of the information gain parameter $γ_t$ and the posterior contraction rate $ε_t$, and identify conditions on the Gaussian process prior under which $ε_t$ can be controlled. As special cases of our general bound, we recover regret of order $\tilde{\mathcal{O}}(T^{\frac{1}{2}})$ for the squared exponential kernel, $\tilde{\mathcal{O}}(T^{\frac{2ν+3d}{2(2ν+d)}} )$ for the Matérn-$ν$ kernel, and a bound of order $\tilde{\mathcal{O}}(T^{\frac{2ν+3d}{2(2ν+d)}})$ for the rational quadratic kernel. Overall, our analysis provides a unified and discretization-free regret framework for GP-TS that applies broadly across kernel classes.
