IDEI Distinguished Research Seminar Series

Large-scale ranking-and-selection (R&S), which aims to select the best alternative with the largest mean performance from a finite set of alternatives, has emerged as an important research topic in simulation optimization. An ideal large-scale R&S procedure should be rate optimal, i.e., the total sample size required to deliver an asymptotically non-zero probability of correct selection (PCS) grows linearly in the number of alternatives. We discover that the naïve greedy procedure that keeps sampling the alternative with the largest running sample mean performs surprisingly well and appears rate optimal in solving large-scale R&S problems. We develop a boundary-crossing perspective and prove that the greedy procedure is indeed rate optimal, and we further show that the obtained PCS lower bound is tight asymptotically for the slippage configuration with a common variance. To develop a practically competitive procedure that harnesses the rate optimality of the greedy procedure, we propose the explore-first greedy (EFG) procedure that adds an exploration phase to the greedy procedure. We show that the new procedure is simple, rate optimal and consistent. The numerical study demonstrates that the EFG procedure performs well compared to the existing carefully designed rate-optimal R&S procedures.

This is a joint work with Zaile Li (Fudan University) and Weiwei Fan (Tongji University).