Sequential Additivity in Distributionally Robust Ranking and Selection

Abstract:Ranking and selection (R&S) seeks to identify the alternative with the best mean performance from a finite collection of simulated alternatives. Its practical value depends on accurate simulation input modeling, which is often hindered by input uncertainty arising from limited data. Distributionally robust R&S (DRR&S) addresses this challenge by considering several plausible input distributions and selecting the alternative with the best worst-case mean performance, resulting in a multiplicative number of scenarios. Existing static and oracle analyses suggest that efficient sampling should instead be additive, concentrating on only a small number of critical scenarios. We introduce sequential additivity, which characterizes how this structure emerges from adaptive sequential procedures. We first establish an algorithm-independent sampling lower bound: any consistent DRR&S procedure must sample at least this additive number of scenarios infinitely often. We then study a simplified additive allocation (AA) procedure abstracted from practical sequential designs. Using boundary-crossing arguments, we derive a finite-budget upper bound on its probability of incorrect selection and show that this probability decays exponentially as the budget grows. Moreover, AA attains the necessary sampling lower bound exactly, showing that additivity can be achieved in the strongest possible sense. Surprisingly, the scenarios sampled infinitely often need not be the true worst-case scenarios, showing that worst-case scenario identification may not be necessary for sufficient exploration in DRR&S. To generalize these insights, we introduce a general additive allocation (GAA) framework that incorporates sampling rules from traditional R&S in a modular fashion. Under suitable exploration conditions, GAA procedures retain the key properties of AA.

Machine Learning (stat.ML); Machine Learning (cs.LG); Methodology (stat.ME)

arXiv:2509.06147 [stat.ML]

(or arXiv:2509.06147v2 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2509.06147 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.