stat.MLNov 10, 2026

Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling

Authors: Yilin Zheng, Haowei Wang, Wenjia Wang, Szu Hui Ng

Organizations: National University of Singapore, Singapore

Abstract

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 TT, 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/α})Ω\bigl(η^{-(2+d/ν)}\min\{1,KT^{d/α}\}\bigr) simulation evaluations, where dd is the dimension, νν the smoothness, and (K,α)(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

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Principled Design of Expected Improvement for Continuous Simulation Optimization

    Oct 13, 2026Songhao Wang, Jianglin Xia, Haowei Wang +1Stochastic OptimizationStochastic Optimization Convergence

  2. Stochastic simultaneous optimistic optimization

    Apr 27, 2026Michal Valko, Alexandra Carpentier, Rémi MunosStochastic OptimizationMulti-Armed Bandits

  3. Robust Active Learning for More Efficient and Reliable Paths to Optimal Design

    Oct 28, 2026Hayriye Pehlivan Solak, Francesco Di Fiore, Jeroen Wackers +4Active LearningMulti-Fidelity Optimization