# Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 72 references that are in the map.
- First posted on arXiv 10 May 2022.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Constrained Bayesian Optimization with Noisy Experiments](https://mlsanity.com/paper/1706.07094/) (2017)
- [Bayesian optimization for materials design](https://mlsanity.com/paper/1506.01349/) (2015)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [The Parallel Knowledge Gradient Method for Batch Bayesian Optimization](https://mlsanity.com/paper/1606.04414/) (2016)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Parallel Bayesian Global Optimization of Expensive Functions](https://mlsanity.com/paper/1602.05149/) (2016)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Regret bounds for meta Bayesian optimization with an unknown Gaussian process prior](https://mlsanity.com/paper/1811.09558/) (2018)
- [Decentralized High-Dimensional Bayesian Optimization with Factor Graphs](https://mlsanity.com/paper/1711.07033/) (2017)
- [Private Outsourced Bayesian Optimization](https://mlsanity.com/paper/2010.12799/) (2020)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Regret Bounds for Gaussian-Process Optimization in Large Domains](https://mlsanity.com/paper/2104.14113/) (2021)

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

- [On the convergence rate of noisy Bayesian Optimization with Expected Improvement](https://mlsanity.com/paper/2501.09262/) (2025)
- [Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2507.09828/) (2025)
- [Cost-aware Stopping for Bayesian Optimization](https://mlsanity.com/paper/2507.12453/) (2025)
- [An Adaptive Dimension Reduction Estimation Method for High-dimensional Bayesian Optimization](https://mlsanity.com/paper/2403.05425/) (2024)
- [Practical Efficient Global Optimization is No-regret](https://mlsanity.com/paper/2603.25311/) (2026)
- [Principled Design of Expected Improvement for Continuous Simulation Optimization](https://mlsanity.com/paper/2610.18434/) (2026)

## Abstract (arXiv)

The expected improvement (EI) is one of the most popular acquisition functions for Bayesian optimization (BO) and has demonstrated good empirical performances in many applications for the minimization of simple regret. However, under the evaluation metric of cumulative regret, the performance of EI may not be competitive, and its existing theoretical regret upper bound still has room for improvement. To adapt the EI for better performance under cumulative regret, we introduce a novel quantity called the evaluation cost which is compared against the acquisition function, and with this, develop the expected improvement-cost (EIC) algorithm. In each iteration of EIC, a new point with the largest acquisition function value is sampled, only if that value exceeds its evaluation cost. If none meets this criteria, the current best point is resampled. This evaluation cost quantifies the potential downside of sampling a point, which is important under the cumulative regret metric as the objective function value in every iteration affects the performance measure. We establish in theory a high-probability regret upper bound of EIC based on the maximum information gain, which is tighter than the bound of existing EI-based algorithms. It is also comparable to the regret bound of other popular BO algorithms such as Thompson sampling (GP-TS) and upper confidence bound (GP-UCB). We further perform experiments to illustrate the improvement of EIC over several popular BO algorithms.