Simultaneous Near-Optimal Region Identification: A New Paradigm for Simulation Optimization and the SASORI Algorithm

Introduction: From Single-Point Optimum to Region-Based Decision-Making

In simulation optimization, traditional methods typically aim to return an estimated optimal point. However, real-world decision-making often depends not only on simulation performance but also on independently evaluated metrics such as resource cost. What decision-makers truly need is the set of designs whose expected performance falls within a certain tolerance of the optimum—the near-optimal region—and this tolerance is often determined only after observing the trade-offs.

A recent paper from rss, "Simultaneous Near-Optimal Region Identification in Continuous Simulation Optimization: Minimax Complexity and Adaptive Sampling," explores how to simultaneously identify near-optimal regions for all tolerances (up to a given upper limit T) in a continuous design space, while guaranteeing that the region estimation error does not exceed η. The study reveals that region identification is not a byproduct of the optimization process, and proposes an efficient algorithm called SASORI.

Core Problem and Theoretical Lower Bound

The paper points out that when α > ν, even if the optimal design is known in advance, any algorithm that simultaneously identifies near-optimal regions for all tolerances requires a minimum number of simulation evaluations with the following lower bound: Ω(η^{-(2+d/ν)} min{1, KT^{d/α}}). Here d is the dimension of the design space, ν is a smoothness parameter, and (K, α) are covering parameters that describe the geometry of the near-optimal region.

This lower bound shows that the complexity of region identification is fundamentally different from that of optimization itself: it requires more evaluations to cover the entire region, rather than merely locating a single point. This result theoretically clarifies the difficulty of the region identification problem and provides a benchmark for algorithm design.

Minimax complexity is a theoretical framework for measuring an algorithm's performance in the worst case. In simulation optimization, minimax complexity refers to the worst-case lower bound on sample complexity for a given problem class (e.g., a set of functions satisfying certain smoothness and region geometry conditions), and the existence of an algorithm that achieves this lower bound (up to constant or logarithmic factors). An algorithm whose sample complexity is of the same order as the lower bound is called minimax optimal. This concept helps researchers determine whether there is room for improvement in an algorithm and provides a fair comparison benchmark across different algorithms.

Covering parameters (K, α) characterize the geometric complexity of the near-optimal region. Intuitively, the near-optimal region may be an irregular continuous set, and the covering number measures the minimum number of balls of radius ε needed to cover this region. The parameter α controls how fast the covering number grows as ε decreases; a larger α indicates a "more regular" and easier-to-cover region; K is the proportionality constant of the covering number. The term T^{d/α} in the theoretical lower bound reflects the interaction between the tolerance upper limit T and the region geometry: when α is small (the region is more complex), more samples are needed to identify the region for all tolerances.

The SASORI Algorithm: Simultaneous Estimation and Adaptive Sampling

To address the above challenges, the authors propose the SASORI (Simultaneous Adaptive Sampling for Optimal Region Identification) algorithm. SASORI uses the same set of simulation evaluations to simultaneously return an estimated optimal point and the near-optimal regions for all tolerances. Theoretical analysis shows that SASORI's sample complexity matches the lower bound up to logarithmic factors, and is therefore minimax optimal.

Furthermore, SASORI achieves an optimal trade-off between region estimation error and cumulative regret. When the tolerance is zero, SASORI reduces to a minimax-optimal simulation optimization procedure, demonstrating its generality.

Cumulative regret is a core metric in online learning and sequential decision-making, defined as the sum of performance gaps between the design chosen by the algorithm at each step and the current optimal design. In simulation optimization, if the algorithm continuously recommends designs during exploration, regret measures the average performance loss of these recommendations relative to the true optimum. Through adaptive sampling, SASORI controls regret while estimating the near-optimal region: it does not excessively sacrifice approximation to the optimum in order to cover the entire region, thereby balancing region identification accuracy and optimization performance. Theoretical results show that SASORI's regret and region estimation error simultaneously achieve optimal rates.

Numerical Experiments and Results

The paper validates the effectiveness of SASORI through numerical experiments. Experiments show that SASORI can accurately identify near-optimal regions and is more sample-efficient than naive methods. Although the abstract does not provide specific numerical values, the authors emphasize that the method performs well on practical problems.

Conclusion and Implications

This study lays a theoretical foundation for the region identification problem in simulation optimization and provides a practical algorithm, SASORI. For scenarios requiring multi-criteria decision-making, simultaneously identifying near-optimal regions can help decision-makers more flexibly weigh design choices under different tolerances. In the future, the method is expected to be extended to more complex constraints and higher-dimensional problems.

One-line Summary

The paper proposes the SASORI algorithm, which simultaneously identifies near-optimal regions for all tolerances in continuous simulation optimization, achieving minimax-optimal complexity.

Paragraph Summary

This paper studies the near-optimal region identification problem in continuous design space simulation optimization, requiring simultaneous identification of near-optimal regions for all tolerances (up to T) while guaranteeing that the region estimation error does not exceed η. The authors first derive a theoretical lower bound on sample complexity, showing that region identification requires more evaluations than single-point optimization. They then propose the SASORI algorithm, which uses the same set of simulation evaluations to simultaneously return an estimated optimal point and the near-optimal regions for all tolerances; its sample complexity matches the lower bound up to logarithmic factors, achieving minimax optimality. SASORI also achieves an optimal trade-off between region estimation error and cumulative regret, and reduces to a minimax-optimal simulation optimization method when the tolerance is zero. Numerical experiments validate its effectiveness and sample efficiency.