Simulation optimization typically returns a single estimated optimal point. When decisions also depend on criteria evaluated independently of simulation, such as resource cost, the decision maker instead needs the set of designs whose expected performance lies within a tolerance of the optimum, often choosing the tolerance only after seeing the tradeoffs. We study how to identify these near-optimal regions on a continuous design space, simultaneously for all tolerances up to a prescribed maximum T, with region estimation error at most η. We show that region identification is not a by-product of optimization. Specifically, when α>ν, any procedure, even one given the optimal design in advance, needs at least Ω(η−(2+d/ν)min{1,KTd/α}) simulation evaluations, where d is the dimension, ν the smoothness, and (K,α) the covering parameters that describe the geometry of the near-optimal designs. We propose SASORI, which returns an estimated optimal point and the regions for all tolerances from the same evaluations, matching this lower bound up to logarithmic factors. SASORI also achieves the optimal tradeoff between region estimation error and cumulative regret, and reduces to a minimax-optimal simulation optimization procedure at zero tolerance. Numerical experiments illustrate the effectiveness of our proposed method.
Figures & tables
Method
ηQ(τ)
Recovery (%)
Unclassified (%)
SASORI-Opt
0.0621±0.0011
59.97±0.64
23.49±0.17
SASORI-Joint-Free
0.0671±0.0016
60.89±0.50
23.48±0.14
SASORI-Reg
0.0518±0.0007
57.25±0.55
20.58±0.17
GP-UCB
0.7024±0.0716
20.12±3.94
62.01±2.51
Sobol-GP
0.0661±0.0010
53.20±0.74
22.91±0.27
Table 1: Branin-2 algorithm-output region estimates at τ=T=0.1 (mean ± standard error).
Figure 1: Branin-2 evaluations for the three SASORI variants from one replication. Point colors indicate evaluation order. Stars and diamonds denote the true maxima and original recommendations, respectively.
Figure 2: Branin-2 algorithm regions at τ=0.1 from the same replication.
Figure 3: Branin-2 simple and cumulative regret. The middle panel uses the best evaluated point; shading indicates one standard error. Recommendation curves show SASORI.
Method
ηQ(τ)
Recovery (%)
Unclassified (%)
SASORI-Opt
0.1672±0.0023
55.59±0.44
9.11±0.05
SASORI-Joint-Free
0.1747±0.0028
55.61±0.54
9.19±0.06
SASORI-Reg
0.1206±0.0020
53.66±0.65
6.79±0.06
GP-UCB
0.665667±0.000004
12.53±1.36
81.53±0.57
Sobol-GP
0.2036±0.0044
37.75±1.14
9.60±0.12
Table 2: Hartmann-3 algorithm-output region estimates at τ=T=0.3 (mean ± standard error).
Figure 4: Hartmann-3 simple and cumulative regret. The middle panel uses the best evaluated point; shading indicates one standard error. Recommendation curves show SASORI.
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
Branin-2
Hartmann-3
Domain
[0,1]2
[0,1]3
Objective
−BBr/200
−H3/4
Largest tolerance T
0.10
0.30
Evaluation tolerances
.04,.06,.08,.10
.12,.18,.24,.30
Fixed length scale
0.32
0.23
Joint-Free region quota
591
197
Appendix
Table D.1: Settings for the two benchmarks.
Figure D.1: Branin-2 empirical region error ηQ(τ) : algorithm output (left) and GP fitted to all observations (right). Error bars show one standard error.
Method
Algorithm output: ηQ,max/T
All observations: ηQ,max/T
Opt
0.638±0.010
0.567±0.010
Joint-Free
0.688±0.017
0.435±0.006
Reg
0.528±0.007
0.514±0.008
GP-UCB
7.186±0.741
7.186±0.741
Sobol-GP
0.678±0.008
0.678±0.008
Appendix
Table D.2: Branin-2 maximum empirical region error across the four tested tolerances (mean ± standard error).
Figure D.2: Branin-2 inner recovery across tolerances: algorithm output (left) and GP fitted to all observations (right). Error bars show one standard error.
Figure D.3: Branin-2 unclassified fractions across tolerances: algorithm output (left) and GP fitted to all observations (right). Error bars show one standard error.
Figure D.4: Branin-2 algorithm regions at three additional tolerances.
Method
103rN
105rNbest
RN
Opt
1.938±0.356
3.850±0.580
152.77±2.18
Joint-Free
2.243±0.437
4.854±0.955
231.55±2.94
Reg
1.244±0.250
4.536±0.964
318.72±1.69
GP-UCB
0.356±0.081
0.146±0.048
17.37±0.46
Sobol-GP
2.124±0.431
5.107±0.835
943.34±0.11
Appendix
Table D.3: Branin-2 final regret (mean ± standard error).
Method
Minutes
Opt
47.89±0.38
Joint-Free
44.75±0.40
Reg
48.42±0.40
GP-UCB
119.01±4.29
Sobol-GP
0.24±0.01
Appendix
Table D.4: Branin-2 recorded sampling time in minutes (mean ± standard error).
Figure D.5: Hartmann-3 empirical region error ηQ(τ) : algorithm output (left) and GP fitted to all observations (right). Error bars show one standard error.
Method
Algorithm output: ηQ,max/T
All observations: ηQ,max/T
Opt
0.571±0.006
0.655±0.071
Joint-Free
0.593±0.009
0.522±0.008
Reg
0.419±0.006
0.366±0.005
GP-UCB
2.818815±0.000028
2.818815±0.000028
Sobol-GP
0.733±0.017
0.733±0.017
Appendix
Table D.5: Hartmann-3 maximum empirical region error across the four tested tolerances (mean ± standard error).
Figure D.6: Hartmann-3 inner recovery across tolerances: algorithm output (left) and GP fitted to all observations (right). Error bars show one standard error.
Figure D.7: Hartmann-3 unclassified fractions across tolerances: algorithm output (left) and GP fitted to all observations (right). Error bars show one standard error.
Method
103rN
105rNbest
RN
Opt
4.345±0.753
69.990±7.690
687.27±5.24
Joint-Free
4.591±0.951
71.250±9.490
824.05±5.83
Reg
5.038±0.916
185.300±22.500
1711.04±6.84
GP-UCB
0.500±0.104
3.048±0.844
90.72±0.65
Sobol-GP
2.685±0.477
386.300±43.800
2554.40±0.09
Appendix
Table D.6: Hartmann-3 final regret (mean ± standard error).
Method
Minutes
Opt
47.62±0.63
Joint-Free
44.33±0.60
Reg
45.82±0.57
GP-UCB
141.33±4.91
Sobol-GP
0.31±0.01
Appendix
Table D.7: Hartmann-3 recorded sampling time in minutes (mean ± standard error).
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.
Songhao Wang, Jianglin Xia, Haowei Wang +1
College of Business, Southern University of Science and Technology, Shenzhen, CHINA · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore, SINGAPORE
We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.
Michal Valko, Alexandra Carpentier, Rémi Munos
INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France · Statistical Laboratory, CMS, Wilberforce Road, CB3 0WB, University of Cambridge, United Kingdom
Simulation-driven design optimization requires active learning strategies that efficiently combine models with different computational costs and levels of fidelity. We introduce Multifidelity Cost-Aware Screening (MF-CAS), which enables the joint selection of sampling location and fidelity using a surrogate that provides decomposed uncertainty intervals rather than a complete predictive probability distribution. MF-CAS exploits the contribution of each fidelity to the high-fidelity uncertainty together with its computational cost to determine whether a candidate should first be evaluated at low fidelity or directly progressed towards high fidelity. The method is assessed on the constrained 14-dimensional hydrodynamic optimization of the DTMB 5415 hull under a deliberately limited computational budget. MF-CAS achieves an approximately 9.0% resistance reduction, compared with 6.7% for the best baseline optimisation method, demonstrating that incorporating fidelity-resolved uncertainty directly into the joint location-fidelity decision can substantially improve multifidelity active learning efficiency.
Hayriye Pehlivan Solak, Francesco Di Fiore, Jeroen Wackers +4
Brahmal Institute for Sustainable Aviation, Imperial College London, United Kingdom. · Department of Aeronautics, Imperial College London, United Kingdom. · LHEEA Lab, Centrale Nantes / CNRS UMR 6598, Nantes, France. +1