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

Yilin Zheng, Haowei Wang, Wenjia Wang, Szu Hui NgarXiv 2026 · arXiv

In the world of engineering and complex systems, we often use stochastic simulations to find the "best" design—whether that’s the most efficient routing for a call center or the most stable configuration for a chemical reactor. Traditionally, simulation optimization (SO) has one goal: find the single point that maximizes performance.

But real-world decision-making is rarely that simple. The "mathematical optimum" might be prohibitively expensive to build, or it might violate a safety constraint that wasn't included in the simulation. In practice, managers don't just want the best point; they want a near-optimal region—a set of all designs that perform within a certain tolerance (say, 5%) of the best possible result.

This paper introduces a new framework and algorithm, SASORI, to identify these regions efficiently on a continuous design space.

TL;DR

The authors present SASORI, the first algorithm capable of identifying all "near-optimal" design regions across a range of tolerances simultaneously. They prove the fundamental "minimax" limit on how many simulations are required for this task and show that SASORI hits that limit while still finding the global optimum.

What Problem Does This Paper Address?

Identifying a region is fundamentally different from finding a single optimal point. If you are just looking for the peak of a mountain, you can quickly ignore the foothills. But if you need to map every part of the mountain above 10,000 feet, you have to spend a lot of time exploring the edges of that boundary.

Current methods have two major gaps:

  1. Optimization vs. Identification: Standard optimization algorithms are "greedy"—they stop exploring a design as soon as they realize it isn't the absolute best. This makes them terrible at mapping near-optimal regions.
  2. The Tolerance Catch-22: Usually, you have to pick your tolerance (e.g., "within 10 units of the best") before you start. But managers often want to see the trade-offs first. They might accept a 2% performance loss if it saves 20% in cost, but they won't know that until the simulation is done.

The authors tackle the challenge of identifying these regions for all possible tolerances simultaneously, providing a "menu" of good designs for the decision-maker.

Methods

The authors propose SASORI (Shared-confidence Adaptive Sampling for Optimization and Region Identification). Key features include:

  • Dual-Track Sampling: The algorithm runs two tracks in parallel. The Optimization Track hunts for the global maximum, while the Region Track maps the boundaries of the near-optimal sets.
  • Shared Confidence Bounds: Both tracks contribute to and draw from a single Gaussian Process (GP) metamodel. This means evaluations spent looking for the peak also help define the region, and vice versa.
  • Phased Adaptive Sampling: SASORI operates in phases. In each phase, it uses an "acquisition function" to identify points that are still "undetermined"—meaning the algorithm isn't sure yet if they are inside or outside the target region. It focuses its limited simulation budget only on these high-uncertainty areas.
  • Minimax Analysis: The authors provide a rigorous mathematical proof of the "evaluation complexity"—the minimum number of samples any algorithm needs to solve this problem.

Datasets

The algorithm was evaluated using two classic "black-box" benchmarks used in simulation optimization:

  • Branin-2: A 2D function with three global optima, used to test how well the algorithm handles multiple "good" regions.
  • Hartmann-3: A 3D function used to test performance in higher dimensions.

Key Insights and Ideas

  • Region Identification is not a by-product of optimization: The authors prove that even if you already know where the peak is, you still need a massive number of samples to define the region around it. Optimization and region learning are distinct tasks that require different sampling strategies.
  • The "Shell" Geometry: The difficulty of the problem depends on the "geometry" of the near-optimal designs. If the peak is very sharp, the region is small and easy to find. If the peak is flat or there are many local "hills," the complexity increases.
  • The Regret-Accuracy Trade-off: There is a fundamental tension between "Cumulative Regret" (how much performance you lose by testing sub-optimal designs during the search) and "Region Accuracy." SASORI allows users to tune this trade-off using a "region quota."

Key Results

  • Theoretical Optimality: SASORI matches the theoretical lower bound for sample complexity (up to logarithmic factors).
  • Superior Recovery: In experiments on the Branin-2 function, SASORI variants recovered significantly more of the "true" acceptable region (higher "inner recovery") compared to standard baselines like GP-UCB.
  • Efficiency: SASORI-Joint-Free (the balanced version) was able to map regions accurately while using only a small fraction of its budget for dedicated region learning, preserving its ability to find the global optimum quickly.

Limitations and Future Work

While SASORI is a major step forward, the authors note a few areas for improvement:

  • Parameter Knowledge: The current theory assumes we know certain "smoothness" parameters of the underlying function. In the real world, these often have to be estimated on the fly.
  • Noise Handling: The model assumes the simulation noise is the same everywhere (homoscedastic). Future versions could adapt to "heteroscedastic" noise, which is common in queueing and inventory simulations.
  • Boundary Complexity: The current analysis works best when the boundaries of the near-optimal regions are relatively "regular." Very jagged or complex boundaries might require even more sophisticated geometric analysis.

Summary updated

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 $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 $Ω\bigl(η^{-(2+d/ν)}\min\{1,KT^{d/α}\}\bigr)$ 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.
BibTeX
@misc{zheng2026simultaneous,
  author = {Yilin Zheng and Haowei Wang and Wenjia Wang and Szu Hui Ng},
  title = {{Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling}},
  year = {2026},
  eprint = {2611.13489},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13489},
}
Figure