# Regret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimization

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

## Key facts

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

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [SMAC3: A Versatile Bayesian Optimization Package for Hyperparameter Optimization](https://mlsanity.com/paper/2109.09831/) (2021)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [On the Sublinear Regret of GP-UCB](https://mlsanity.com/paper/2307.07539/) (2023)
- [Optimization, fast and slow: optimally switching between local and Bayesian optimization](https://mlsanity.com/paper/1805.08610/) (2018)
- [Automatic Termination for Hyperparameter Optimization](https://mlsanity.com/paper/2104.08166/) (2021)
- [Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization](https://mlsanity.com/paper/2506.01393/) (2025)
- [Stopping Bayesian Optimization with Probabilistic Regret Bounds](https://mlsanity.com/paper/2402.16811/) (2024)
- [Stopping criteria for boosting automatic experimental design using real-time fMRI with Bayesian optimization](https://mlsanity.com/paper/1511.07827/) (2015)
- [Cost-aware Stopping for Bayesian Optimization](https://mlsanity.com/paper/2507.12453/) (2025)

## Abstract (arXiv)

Bayesian optimization (BO) is a widely used iterative black-box optimization method that utilizes Gaussian process (GP) surrogate models. In practice, BO is typically terminated after a fixed evaluation budget is exhausted, which can incur unnecessary cost and provides no optimality guarantee on solution quality. Recent research in developing a practical stopping criterion has made empirical progress, yet a theoretically sound stopping criterion remains a work in progress. In this work, we present provably tighter instantaneous regret bounds for GP upper confidence bound (GP-UCB) at any given iteration. Then, we propose stopping criteria for GP-UCB based on this tighter bound that ensures an ε-optimal solution with high probability 1-δ upon termination. Numerical experiments are performed to validate and demonstrate the effectiveness and efficiency of our stopping criteria.