Search papers, labs, and topics across Lattice.
This paper analyzes Gaussian Process Thompson Sampling (GP-TS) in Bayesian optimization, focusing on high-probability regret bounds. It establishes a regret lower bound showing polynomial dependence on $1/\delta$, derives an upper bound on the second moment of cumulative regret leading to improved regret bounds on $\delta$, and provides expected lenient regret upper bounds and an improved cumulative regret upper bound on the time horizon $T$. The analysis also presents relaxed conditions for achieving improved regret upper bounds on $T$.
GP Thompson Sampling's reliance on probability $\delta$ dooms it to polynomial regret, a stark contrast to GP-UCB's more favorable bounds.
We study a widely used Bayesian optimization method, Gaussian process Thompson sampling (GP-TS), under the assumption that the objective function is a sample path from a GP. Compared with the GP upper confidence bound (GP-UCB) with established high-probability and expected regret bounds, most analyses of GP-TS have been limited to expected regret. Moreover, whether the recent analyses of GP-UCB for the lenient regret and the improved cumulative regret upper bound can be applied to GP-TS remains unclear. To fill these gaps, this paper shows several regret bounds: (i) a regret lower bound for GP-TS, which implies that GP-TS suffers from a polynomial dependence on $1/\delta$ with probability $\delta$, (ii) an upper bound of the second moment of cumulative regret, which directly suggests an improved regret upper bound on $\delta$, (iii) expected lenient regret upper bounds, and (iv) an improved cumulative regret upper bound on the time horizon $T$. Along the way, we provide several useful lemmas, including a relaxation of the necessary condition from recent analysis to obtain improved regret upper bounds on $T$.
