Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

arXiv:2610.19925v1 Announce Type: cross Abstract: 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 Matern kernels with smoothness parameter nu in dimension d, we establish a worst-case expected simple-regret upper bound of O(N^{-nu/d}sqrt{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}sqrt{log N}) for both implementations under a fixed one-dimensional Matern-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.

Source: arXiv cs.LG | 2026-10-15