Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization

Shouri Hu, Haowei Wang, Zhongxiang Dai, Bryan Kian Hsiang Low, Szu Hui Ng

Abstract

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 further establish in theory a tight regret upper bound of EIC for the squared-exponential covariance kernel under mild regularity conditions, and perform experiments to illustrate the improvement of EIC over several popular BO algorithms.

Introduction

Bayesian Optimization (BO) is a powerful framework for optimizing expensive, black-box functions. Traditionally, the focus has been on simple regret—identifying the single best point after a fixed budget of evaluations. The Expected Improvement (EI) algorithm has become a standard choice due to its intuitive nature and strong empirical performance in these settings.

However, many practical applications, such as online recommendation systems or clinical trials, prioritize cumulative regret. In these contexts, every evaluation counts; a poor sample choice results in immediate loss, whether in revenue or patient outcomes. Standard EI tends to be overly aggressive for cumulative regret minimization, and its theoretical guarantees have historically lagged behind alternatives like GP-UCB or Thompson Sampling.

The Expected Improvement-Cost (EIC) Algorithm

To address these shortcomings, we propose the Expected Improvement-Cost (EIC) algorithm. The central innovation is the introduction of an evaluation cost ($L_n$), which serves as a dynamic threshold for exploration.

Decision Rule and Cost-Benefit Analysis

In each step, EIC calculates the standard EI (the potential "upside") for a point. It then compares this to the evaluation cost, which quantifies the potential "downside" or expected loss if the point is worse than the current best. A new point is only sampled if its expected gain exceeds its evaluation cost. If no point in the domain meets this criterion, the algorithm plays it safe and resamples the current best-known point to reduce noise.

Dynamic Conservatism

The evaluation cost is scaled by the remaining budget ($N-n$). Early in the run, the cost is lower, encouraging exploration. As the budget runs out, the cost rises, forcing the algorithm to become more exploitative and "conservative."

Experimental Evaluation

We evaluated EIC against several baselines, including standard EI, GP-UCB, and GP-TS, across synthetic benchmarks and real-world tasks.

Synthetic Benchmarks

The algorithm was tested on classic functions such as Ackley, Eggholder, and Hartmann-6. These functions present various challenges, including high dimensionality and numerous local optima.

Cumulative regret on the Ackley function comparing EIC, EI, and GP-UCB.

As shown in the Ackley benchmark, EIC begins to significantly outperform both GP-UCB and standard EI as the number of iterations increases, demonstrating its ability to avoid local traps and manage cumulative regret more effectively.

Real-World Application: Hyperparameter Tuning

EIC was also applied to tune a Multi-Layer Perceptron (MLP) for classification on the Breast Cancer Wisconsin dataset. In this experiment, EIC achieved the lowest cumulative regret, with performance gains becoming statistically significant after 150 iterations.

Key Insights and Theoretical Contributions

  • Accounting for Downside Risk: By comparing EI to an evaluation cost, EIC explicitly considers the potential loss of sampling a sub-optimal point, a critical factor in cumulative regret.
  • Resampling Strategy: In noisy environments, EIC’s ability to resample the incumbent provides stability, ensuring that the model's estimate of the peak is well-supported before moving on.
  • Tightened Regret Bounds: The authors proved a high-probability regret upper bound of $O(\sqrt{N \gamma_N (\log N)^{1/2}})$. This result is significantly tighter than previous EI-based bounds and places EIC on equal theoretical footing with state-of-the-art algorithms like GP-UCB.

Conclusion

EIC offers a robust and theoretically sound adaptation of Expected Improvement for cumulative regret minimization. By balancing potential gains against evaluation costs and incorporating a budget-aware resampling strategy, it achieves superior performance in noisy, high-stakes optimization environments.

Summary updated

Abstract

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 further establish in theory a tight regret upper bound of EIC for the squared-exponential covariance kernel under mild regularity conditions, and perform experiments to illustrate the improvement of EIC over several popular BO algorithms.
BibTeX
@misc{hu2022adjusted,
  author = {Shouri Hu and Haowei Wang and Zhongxiang Dai and Bryan Kian Hsiang Low and Szu Hui Ng},
  title = {{Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization}},
  year = {2022},
  eprint = {2205.04901},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.04901},
}
Figure