Simulation optimization under input uncertainty: Formulations, algorithms, and insights

Abstract

Simulation optimization is concerned with identifying the best design for large, complex and stochastic physical systems via computer simulation models. In building a stochastic simulation model, one often needs to specify a set of distributions, known as "input distributions". However, since these distributions are usually estimated using finite real-world data, the simulation output is subject to the so-called "input uncertainty". Existing studies indicate that ignoring input uncertainty can cause a higher risk of selecting an inferior design in simulation optimization. This thesis is therefore devoted to addressing input uncertainty in the context of simulation optimization by proposing new formulations, devising new algorithms, and developing insights for improving existing algorithms. In Chapter 2, we study a simulation optimization problem with a general design space. The scenario of interest is when a set of fixed input data is given and no additional data is available. To hedge against the risk of input uncertainty, we propose a Bayesian Risk Optimization (BRO) framework that (i) models input uncertainty using posterior distributions; (ii) incorporate a decision maker's risk preference via risk measures such as value-at-risk (VaR) and conditional value-at-risk (CVaR). We establish the asymptotic properties of BRO, and reveal that BRO essentially seeks a balance between predicted average performance and the uncertainty in a design's actual performance. Chapter 3 considers optimizing over a finite design space, a problem known as Ranking and Selection (R&S) in statistics literature, or Best-Arm Identification in Multi-Armed Bandits literature. We look closely into the classical fixed budget R&S without input uncertainty, which will be a fundamental building block of Chapter 4 for studying R&S under input uncertainty. Specifically, we investigate the performance of a widely used algorithm called Optimal Computing Budget Allocation (OCBA). Our analysis leads to a surprising insight: the popular implementation of OCBA suffers from a slow convergence rate. We then propose a modification to boost its performance, where the improvement is shown by a theoretical bound and numerical results. In addition, we explicitly characterize the convergence rate of several simplified algorithms, showcasing some interesting findings as well as useful techniques for convergence analysis. In Chapter 4, we study R&S under input uncertainty where additional data can be acquired to reduce input uncertainty. To the best of our knowledge, this setting has rarely been studied in existing literature. Two classical formulations of R&S, i.e., fixed confidence and fixed budget, are extended to our new settings. New algorithms are developed to (i) achieve a statistical selection guarantee when new data arrive sequentially; (ii) efficiently allocate a finite budget between data collection and simulation experimentation. Theoretical guarantees are provided for our algorithms, and numerical results demonstrate their effectiveness.