Gaussian Process Upper Confidence Bound Achieves Nearly Optimal Regret in Noise-Free Gaussian Process Bandits
Organizations: LY Corporation, Tokyo, Japan
Abstract
We study the noise-free Gaussian Process (GP) bandits problem, in which the learner seeks to minimize regret through noise-free observations of the black-box objective function lying on the known reproducing kernel Hilbert space (RKHS). Gaussian process upper confidence bound (GP-UCB) is the well-known GP-bandits algorithm whose query points are adaptively chosen based on the GP-based upper confidence bound score. Although several existing works have reported the practical success of GP-UCB, the current theoretical results indicate its suboptimal performance. However, GP-UCB tends to perform well empirically compared with other nearly optimal noise-free algorithms that rely on a non-adaptive sampling scheme of query points. This paper resolves this gap between theoretical and empirical performance by showing the nearly optimal regret upper bound of noise-free GP-UCB. Specifically, our analysis shows the first constant cumulative regret in the noise-free settings for the squared exponential kernel and Matérn kernel with some degree of smoothness.
Figures & tables
| Algorithm | Regret (SE) | Regret (Matérn) | Type | ||
|---|---|---|---|---|---|
| GP-UCB | D | ||||
| ( Lyu et al., 2019 ) | |||||
| ( Kim and Sanz-Alonso, 2024 ) | |||||
| Explore-then-Commit | N/A | P | |||
| ( Vakili, 2022 ) | |||||
| Algorithm | Regret (SE) | Regret (Matérn) | Type |
|---|---|---|---|
| GP-EI | N/A | D | |
| ( Bull, 2011 ) | |||
| GP-EI with -Greedy | N/A | P | |
| ( Bull, 2011 ) | |||
| GP-UCB | D | ||
| ( Lyu et al., 2019 ) |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.