IEDA Seminar - The (Surprising) Rate Optimality of Greedy Algorithms for Large-Scale Ranking and Selection
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 and multi-armed bandit. An ideal large-scale R&S algorithm 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 algorithm 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 algorithm 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 algorithm that harnesses the rate optimality of the greedy algorithm, we propose the explore-first greedy (EFG) algorithm that adds an exploration phase to the greedy algorithm. We show that the new algorithm is simple, rate optimal and consistent. The numerical study demonstrates that the EFG algorithm performs well compared to the existing algorithms.
Jeff Hong received his bachelor’s and Ph.D. degrees from Tsinghua University and Northwestern University, respectively. He is currently with Fudan University, holding the positions of Fudan Distinguished Professor, Hongyi Chair Professor, Chair of Department of Management Science in School of Management, and Associate Dean of School of Data Science. He was Chair Professor of Management Sciences at City University of Hong Kong, and Professor of Industrial Engineering and Logistics Management at the Hong Kong University of Science and Technology. Prof. Hong’s research interests include stochastic simulation, stochastic optimization, risk management and supply chain management. He is currently the Simulation Area Editor of Operations Research, an Associate Editor of Management Science and ACM Transactions on Modeling and Computer Simulation, and he was the President of INFORMS Simulation Society from 2020 to 2022.