Selection of the Most Probable Best
Taeho Kim, Kyoung-Kuk Kim, Eunhye Song
Operations Research · 2025 · Volume 73 · Issue 6
Abstract
We consider an expected-value ranking and selection (R&S) problem where all k solutions’ simulation outputs depend on a common parameter whose uncertainty can be modeled by a distribution. We define the most probable best (MPB) to be the solution that has the largest probability of being optimal with respect to the distribution and design an efficient sequential sampling algorithm to learn the MPB when the parameter has a finite support. We derive the large deviations rate of the probability of falsely selecting the MPB and formulate an optimal computing budget allocation problem to find the rate-maximizing static sampling ratios. The problem is then relaxed to obtain a set of optimality conditions that are interpretable and computationally efficient to verify. We devise a series of algorithms that replace the unknown means in the optimality conditions with their estimates and prove the algorithms’ sampling ratios achieve the conditions as the simulation budget increases. Furthermore, we show that the empirical performances of the algorithms can be significantly improved by adopting the kernel ridge regression for mean estimation while achieving the same asymptotic convergence results. The algorithms are benchmarked against a state-of-the-art contextual R&S algorithm and demonstrated to have superior empirical performances. Funding: The work by K.-K. Kim was supported by the National Research Foundation of Korea [Grant NRF-2019R1A2C1003144]. E. Song’s work was supported by the National Science Foundation [Grants CMMI-2045400 and CMMI-2417616]. Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2022.0343 .
Keywords
Simulation, ranking and selection, input uncertainty, large deviations theory, optimal computing budget allocation, sequential sampling algorithm
Enable JavaScript for citation tools and additional paper interactions.