A Distribution-Free Sequential Selection Strategy: Data-Driven Optimal Allocation via Balancing Empirical Large Deviations

The ranking and selection problem is a classic mathematical framework about identifying the best alternative from multiple alternatives through sampling them. However, the uncertainty about sampling distributions in the ranking and selection problem has been relatively overlooked, and related research is just starting to gain momentum recently. We propose a data-driven nonparametric tuning-free sequential budget allocation strategy under unknown light-tailed sampling distributions, which is theoretically proved to asymptotically achieve the exact large deviation–based optimal allocation as the sampling budget grows to infinity. Especially, we propose a new point estimation procedure for estimating the optimal large deviation rates in ranking and selection and theoretically demonstrate its validity.

History: Accepted by Bruno Tuffin, Area Editor for Simulation.

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0895) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0895). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.