# Sequential Additivity in Distributionally Robust Ranking and Selection

arXiv: https://arxiv.org/abs/2509.06147 · HTML: https://mlsanity.com/paper/2509.06147/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 7 Sep 2025.

## Builds on (most cited first, 8 of 8)

- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Review on Ranking and Selection: A New Perspective](https://mlsanity.com/paper/2008.00249/) (2020)
- [Ranking and Selection as Stochastic Control](https://mlsanity.com/paper/1710.02619/) (2017)
- [Analyzing and provably improving fixed budget ranking and selection algorithms](https://mlsanity.com/paper/1811.12183/) (2018)
- [Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms](https://mlsanity.com/paper/2211.14722/) (2022)
- [A Nonparametric Bayesian Framework for Uncertainty Quantification in Stochastic Simulation](https://mlsanity.com/paper/1910.03766/) (2019)
- [Optimal Computing Budget Allocation for Data-driven Ranking and Selection](https://mlsanity.com/paper/2209.11809/) (2022)
- [Optimizing Input Data Collection for Ranking and Selection](https://mlsanity.com/paper/2502.16659/) (2025)

## Abstract (arXiv)

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.