The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection

Zaile Li (), Weiwei Fan () and L. Jeff Hong ()
Additional contact information
Zaile Li: Department of Management Science, School of Management, Fudan University, Shanghai 200433, China
Weiwei Fan: Advanced Institute of Business, School of Economics and Management, Tongji University, Shanghai 200092, China
L. Jeff Hong: Department of Management Science, School of Management, Fudan University, Shanghai 200433, China; and School of Data Science, Fudan University, Shanghai 200433, China

Management Science, 2025, vol. 71, issue 2, 1238-1259

Abstract: Ranking and selection (R&S) aims to select the best alternative with the largest mean performance from a finite set of alternatives. Recently, considerable attention has turned toward the large-scale R&S problem which involves a large number of alternatives. Ideal large-scale R&S procedures should be sample optimal; that is, the total sample size required to deliver an asymptotically nonzero probability of correct selection (PCS) grows at the minimal order (linear order) in the number of alternatives, k . Surprisingly, we discover that the naïve greedy procedure, which keeps sampling the alternative with the largest running average, performs strikingly well and appears sample optimal. To understand this discovery, we develop a new boundary-crossing perspective and prove that the greedy procedure is sample optimal for the scenarios where the best mean maintains at least a positive constant away from all other means as k increases. We further show that the derived PCS lower bound is asymptotically tight for the slippage configuration of means with a common variance. For other scenarios, we consider the probability of good selection and find that the result depends on the growth behavior of the number of good alternatives: if it remains bounded as k increases, the sample optimality still holds; otherwise, the result may change. Moreover, we propose the explore-first greedy procedures by adding an exploration phase to the greedy procedure. The procedures are proven to be sample optimal and consistent under the same assumptions. Last, we numerically investigate the performance of our greedy procedures in solving large-scale R&S problems.

Keywords: ranking and selection; sample optimality; greedy; boundary-crossing (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2023.00694 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:71:y:2025:i:2:p:1238-1259

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().