# Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

arXiv: https://arxiv.org/abs/2610.19925 · HTML: https://mlsanity.com/paper/2610.19925/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 14 references that are in the map.
- First posted on arXiv 14 Oct 2026.

## Builds on (most cited first, 7 of 7)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variance](https://mlsanity.com/paper/2502.06363/) (2025)
- [Frequentist Regret Analysis of Gaussian Process Thompson Sampling via Fractional Posteriors](https://mlsanity.com/paper/2602.14472/) (2026)
- [Simple-regret rates and minimax optimality of fixed-prior expected improvement in Mat'ern and squared-exponential RKHSs](https://mlsanity.com/paper/2607.29245/) (2026)
- [Improved Regret Analysis for Parallel Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2608.16492/) (2026)

## Abstract (arXiv)

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.