Papers › The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection
The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection
Zaile Li, Weiwei Fan, L. Jeff Hong
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 towards the large-scale R&S problem which involves a large number of alternatives. Ideal large-scale R&S procedures should be sample optimal, i.e., the total sample size required to deliver an asymptotically non-zero probability of correct selection (PCS) grows at the minimal order (linear order) in the number of alternatives, k. Surprisingly, we discover that the na\"ive 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections