Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of designing Expected Improvement (EI) algorithms for continuous simulation optimization with unknown heteroscedastic noise by systematically optimizing three key design choices: incumbent definition, replication level, and terminal recommendation. By deriving a finite-sample confidence bound for stochastic kriging (SK) predictors with estimated noise, the authors establish a high-probability upper bound on simple regret. Minimizing this bound leads to novel, theoretically grounded rules for these design choices, including a $Θ(\log T)$ replication strategy, providing the first simple-regret guarantee for EI-type methods learning unknown variances.
A theoretically grounded EI algorithm for continuous simulation optimization achieves simple-regret guarantees by learning unknown heteroscedastic noise and optimizing incumbent/recommendation strategies based on regret bounds.
Expected improvement (EI) based on stochastic kriging (SK) surrogate is widely used in continuous simulation optimization, but unknown heteroscedastic noise on simulation output makes three basic design choices consequential: the incumbent used to define improvement, the replication level at each sampled point, and the terminal 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 with unknown and estimated noise levels as a foundation for the three design choices. We then analyze general posterior-quantile families for both the incumbent and the terminal recommendation. For the incumbent, minimizing the regret bound selects a lower quantile coefficient that matches the coefficient in the SK predictor confidence bound. For the terminal recommendation, minimizing the same bound instead selects the sampled point with the best upper posterior quantile under the same coefficient. These opposite quantile choices reflect the different roles of search and implementation in simulation optimization. Intermediate simulations are exploratory with an optimistic incumbent, while the terminal recommendation is implemented in the real system and is therefore relatively conservative about the remaining posterior uncertainty. Under mild conditions satisfied by common kernels, minimizing a tractable kernel-specific bound yields $Θ(\log T)$ replications. To our knowledge, this is the first simple-regret guarantee for a continuous-domain EI-type simulation optimization method that learns unknown heteroscedastic variances through replications.