# Principled Design of Expected Improvement for Continuous Simulation Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 13 Oct 2026.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [The Parallel Knowledge Gradient Method for Batch Bayesian Optimization](https://mlsanity.com/paper/1606.04414/) (2016)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Parallel Bayesian Global Optimization of Expensive Functions](https://mlsanity.com/paper/1602.05149/) (2016)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2008.08757/) (2020)
- [Replication or exploration? Sequential design for stochastic simulation experiments](https://mlsanity.com/paper/1710.03206/) (2017)
- [Simulation optimization: A review of algorithms and applications](https://mlsanity.com/paper/1706.08591/) (2017)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)
- [Bayesian Optimization Allowing for Common Random Numbers](https://mlsanity.com/paper/1910.09259/) (2019)
- [Batch Bayesian Optimization for Replicable Experimental Design](https://mlsanity.com/paper/2311.01195/) (2023)
- [Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization](https://mlsanity.com/paper/2205.04901/) (2022)
- [Combined Global and Local Search for Optimization with Gaussian Process Models](https://mlsanity.com/paper/2107.03217/) (2021)
- [Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2507.09828/) (2025)

## Abstract (arXiv)

Expected improvement based on stochastic kriging (SK) surrogate is widely used in continuous simulation optimization, but unknown heteroscedastic noise makes three basic design choices consequential: the incumbent to define improvement, replication allocation, and final recommendation. Existing methods typically either assume the noise levels are known or choose these components separately through heuristic rules or empirical calibration. We instead derive a high-probability upper bound on the simple regret and systematically choose the three components within general rule classes to tighten this bound. We first establish a finite-sample confidence bound for the SK predictor as a foundation for the three design choices. Within general posterior-quantile rule classes, tightening the regret certificate selects a lower-quantile incumbent and an upper-quantile recommendation among sampled designs. The opposing quantiles reflect the different roles of exploratory experiments and the final implemented decision. Under mild conditions satisfied by common kernels, minimizing a tractable kernel-specific bound yields a logarithmic replication order. Based on these design choices, the resulting simple regret matches the existing results under known homoscedastic noise up to logarithmic factors. To our knowledge, this is the first simple-regret guarantee of this form for a continuous-domain EI-type simulation optimization method that learns unknown heteroscedastic variances through replications.