# On Improved Regret Bounds In Bayesian Optimization with Gaussian Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 23 references that are in the map.
- First posted on arXiv 25 Dec 2024.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control](https://mlsanity.com/paper/1906.01376/) (2019)
- [Scalable Thompson Sampling using Sparse Gaussian Process Models](https://mlsanity.com/paper/2006.05356/) (2020)
- [On the Suboptimality of GP-UCB under Polynomial Effective Optimism](https://mlsanity.com/paper/2312.01386/) (2023)
- [Gaussian Process Optimization with Adaptive Sketching: Scalable and No Regret](https://mlsanity.com/paper/1903.05594/) (2019)

## Built on by (most cited first, 1 of 1)

- [Reinforcement Learning Using known Invariances](https://mlsanity.com/paper/2511.03473/) (2025)

## Abstract (arXiv)

Bayesian optimization (BO) with Gaussian process (GP) surrogate models is a powerful black-box optimization method. Acquisition functions are a critical part of a BO algorithm as they determine how the new samples are selected. Some of the most widely used acquisition functions include upper confidence bound (UCB) and Thompson sampling (TS). The convergence analysis of BO algorithms has focused on the cumulative regret under both the Bayesian and frequentist settings for the objective. In this paper, we establish new pointwise bounds on the prediction error of GP under the frequentist setting with Gaussian noise. Consequently, we prove improved convergence rates of cumulative regret bound for both GP-UCB and GP-TS. Of note, the new prediction error bound under Gaussian noise can be applied to general BO algorithms and convergence analysis, e.g., the asymptotic convergence of expected improvement (EI) with noise.