Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget N. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Mat'ern kernels with smoothness parameter nu in dimension d, we establish a worst-case expected simple-regret upper bound of O(N-nu/d√log N) for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of Omega(N-5/2√log N) for both implementations under a fixed one-dimensional Mat'ern-5/2 kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate Theta(N-nu/d) for both discrete and continuous implementations.