Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
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 Matérn kernels with smoothness parameter ν in dimension d, we establish a worst-case expected simple-regret upper bound of O(N−ν/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 Ω(N−5/2√(log N)) for both implementations under a fixed one-dimensional Matérn-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 Θ(N−ν/d) for both discrete and continuous implementations.
Related
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity
- Thompson Sampling for Learning in Zero-Sum Games
- High-Probability Regret Bounds for Feel-Good Thompson Sampling
- Posterior Tempering Explains Variance Inflation in Linear and Generalized Linear Thompson Sampling
BibTeX
@misc{wang2026convergence,
title = {{Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization}},
author = {Haowei Wang and Yilin Zheng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19925},
eprint = {2610.19925},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19925},
}
RIS
TY - UNPB
TI - Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization
AU - Haowei Wang
AU - Yilin Zheng
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19925
UR - https://arxiv.org/abs/2610.19925
AB - 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érn kernels with smoothness parameter ν in dimension d, we establish a worst-case expected simple-regret upper bound of O(N^−ν/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 Ω(N^−5/2√(log N)) for both implementations under a fixed one-dimensional Matérn-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 Θ(N^−ν/d) for both discrete and continuous implementations.
ER -