Frequentist Regret Analysis of Gaussian Process Thompson Sampling via Fractional Posteriors

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 α ∈ (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 tildeO(T^frac12) for the squared exponential kernel, tildeO(T^frac2nu+3d2(2nu+d) ) for the Mat'ern-nu kernel, and a bound of order tildeO(T^frac2nu+3d2(2nu+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.