# Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 41 references that are in the map.
- First posted on arXiv 15 Mar 2022.

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

- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [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)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Adversarially Robust Optimization with Gaussian Processes](https://mlsanity.com/paper/1810.10775/) (2018)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Knowing The What But Not The Where in Bayesian Optimization](https://mlsanity.com/paper/1905.02685/) (2019)
- [Efficient Exploration of Reward Functions in Inverse Reinforcement Learning via Bayesian Optimization](https://mlsanity.com/paper/2011.08541/) (2020)
- [Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces](https://mlsanity.com/paper/2009.02539/) (2020)
- [Bayesian Optimistic Optimisation with Exponentially Decaying Regret](https://mlsanity.com/paper/2105.04332/) (2021)

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

- [Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization](https://mlsanity.com/paper/2205.04901/) (2022)
- [A Corrected Expected Improvement Acquisition Function Under Noisy Observations](https://mlsanity.com/paper/2310.05166/) (2023)
- [Regret Analysis for Randomized Gaussian Process Upper Confidence Bound](https://mlsanity.com/paper/2409.00979/) (2024)
- [Regional Expected Improvement for Efficient Trust Region Selection in High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2412.11456/) (2024)
- [On the convergence rate of noisy Bayesian Optimization with Expected Improvement](https://mlsanity.com/paper/2501.09262/) (2025)
- [High Dimensional Bayesian Optimization using Lasso Variable Selection](https://mlsanity.com/paper/2504.01743/) (2025)
- [Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2507.09828/) (2025)
- [Regret Bounds for Noise-Free Cascaded Kernelized Bandits](https://mlsanity.com/paper/2211.05430/) (2022)
- [Bayesian Optimization with Informative Covariance](https://mlsanity.com/paper/2208.02704/) (2022)
- [High-Dimensional Bayesian Optimization via Random Projection of Manifold Subspaces](https://mlsanity.com/paper/2412.16554/) (2024)
- [Simple-regret rates and minimax optimality of fixed-prior expected improvement in Mat'ern and squared-exponential RKHSs](https://mlsanity.com/paper/2607.29245/) (2026)
- [Practical Efficient Global Optimization is No-regret](https://mlsanity.com/paper/2603.25311/) (2026)
- [A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback](https://mlsanity.com/paper/2604.25025/) (2026)
- [Transferring Information Across Interventions in Causal Bayesian Optimization](https://mlsanity.com/paper/2606.01457/) (2026)
- [Principled Design of Expected Improvement for Continuous Simulation Optimization](https://mlsanity.com/paper/2610.18434/) (2026)

## Abstract (arXiv)

The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty due to its simplicity and efficiency. Despite its popularity, the theoretical aspects of this algorithm have not been properly analyzed. In particular, whether in the noisy setting, the EI strategy with a standard incumbent converges is still an open question of the Gaussian process bandit optimization problem. We aim to answer this question by proposing a variant of EI with a standard incumbent defined via the GP predictive mean. We prove that our algorithm converges, and achieves a cumulative regret bound of mathcal O(γT√T), where γT is the maximum information gain between T observations and the Gaussian process model. Based on this variant of EI, we further propose an algorithm called Improved GP-EI that converges faster than previous counterparts. In particular, our proposed variants of EI do not require the knowledge of the RKHS norm and the noise's sub-Gaussianity parameter as in previous works. Empirical validation in our paper demonstrates the effectiveness of our algorithms compared to several baselines.