Fixed-Confidence, Fixed-Tolerance Guarantees for Ranking-and-Selection Procedures

• Published in: ACM transactions on modeling and computer simulation 2021-04, Vol.31 (2), p.1-33
• Main Authors: Eckman, David J., Henderson, Shane G.
• Format: Article
• Language: English
• ISSN: 1049-3301; 1558-1195
• DOI: 10.1145/3432754

Ever since the conception of the statistical ranking-and-selection (R8S) problem, a predominant approach has been the indifference-zone (IZ) formulation. Under the IZ formulation, R8S procedures are designed to provide a guarantee on the probability of correct selection (PCS) whenever the performance of the best system exceeds that of the second-best system by a specified amount. We discuss the shortcomings of this guarantee and argue that providing a guarantee on the probability of good selection (PGS)—selecting a system whose performance is within a specified tolerance of the best—is a more justifiable goal. Unfortunately, this form of fixed-confidence, fixed-tolerance guarantee has received far less attention within the simulation community. We present an overview of the PGS guarantee with the aim of reorienting the simulation community toward this goal. We examine numerous techniques for proving the PGS guarantee, including sufficient conditions under which selection and subset-selection procedures that deliver the IZ-inspired PCS guarantee also deliver the PGS guarantee.