Review on ranking and selection: A new perspective

Abstract

In this paper, we briefly review the development of ranking and selection (R&S) in the past 70 years, especially the theoretical achievements and practical applications in the past 20 years. Different from the frequentist and Bayesian classifications adopted by Kim and Nelson (2006b) and Chick (2006) in their review articles, we categorize existing R&S procedures into fixed-precision and fixed-budget procedures, as in Hunter and Nelson (2017). We show that these two categories of procedures essentially differ in the underlying methodological formulations, i.e., they are built on hypothesis testing and dynamic programming, respectively. In light of this variation, we review in detail some well-known procedures in the literature and show how they fit into these two formulations. In addition, we discuss the use of R&S procedures in solving various practical problems and propose what we think are the important research questions in the field.

Graphical abstract

Keywords

ranking and selection / hypothesis testing / dynamic programming / simulation

References

[1] Andradóttir S, Kim S H (2010). Fully sequential procedures for comparing constrained systems via simulation. Naval Research Logistics, 57(5): 403–421

[2] Applegate E A, Feldman G, Hunter S R, Pasupathy R (2020). Multi-objective ranking and selection: Optimal sampling laws and tractable approximations via SCORE. Journal of Simulation, 14(1): 21–40

[3] Banerjee S (1961). On confidence interval for two-means problem based on separate estimates of variances and tabulated values of t-table. Sankhya Series A, 23(4): 359–378

[4] Batur D, Choobineh F (2012). Stochastic dominance based comparison for system selection. European Journal of Operational Research, 220(3): 661–672

[5] Batur D, Wang L, Choobineh F F (2018). Methods for systems selection based on sequential mean-variance analysis. INFORMS Journal on Computing, 30(4): 724–738

[6] Bechhofer R E (1954). A single-sample multiple decision procedure for ranking means of normal populations with known variances. Annals of Mathematical Statistics, 25(1): 16–39

[7] Bechhofer R E, Santner T J, Goldsman D M (1995). Design and Analysis of Experiments for Statistical Selection, Screening, Multiple Comparisons. Hoboken, NJ: Wiley

[8] Bellman R (1966). Dynamic programming. Science, 153(3731): 34–37

[9] Bertsekas D P (1995). Dynamic Programming and Optimal Control, vol. 1. 4th ed. Belmont, MA: Athena Scientific

[10] Boesel J, Nelson B L, Kim S H (2003). Using ranking and selection to “clean up” after simulation optimization. Operations Research, 51(5): 814–825

[11] Branke J, Chick S E, Schmidt C (2007). Selecting a selection procedure. Management Science, 53(12): 1916–1932

[12] Branke J, Zhang W (2015). A new myopic sequential sampling algorithm for multi-objective problems. In: Proceedings of the Winter Simulation Conference. IEEE, 3589–3598

[13] Branke J, Zhang W, Tao Y (2016). Multiobjective ranking and selection based on hypervolume. In: Proceedings of the Winter Simulation Conference. IEEE, 859–870

[14] Bubeck S, Cesa-Bianchi N (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv Preprint. arXiv:1204.5721

[15] Chen C H (1996). A lower bound for the correct subset-selection probability and its application to discrete-event system simulations. IEEE Transactions on Automatic Control, 41(8): 1227–1231

[16] Chen C H, Lin J, Yücesan E, Chick S E (2000). Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems, 10(3): 251–270

[17] Chen E J (2005). Using parallel and distributed computing to increase the capability of selection procedures. In: Proceedings of the Winter Simulation Conference. IEEE, 723–731

[18] Chick S E (2006). Subjective probability and Bayesian methodology. In: Henderson S G, Nelson B L, eds. Handbooks in Operations Research and Management Science: Simulation, Chapter 9. Amsterdam, Chapter 9: Elsevier, 13: 225–257

[19] Chick S E, Branke J, Schmidt C (2010). Sequential sampling to myopically maximize the expected value of information. INFORMS Journal on Computing, 22(1): 71–80

[20] Chick S E, Inoue K (2001). New two-stage and sequential procedures for selecting the best simulated system. Operations Research, 49(5): 732–743

[21] Clark G M, Yang W (1986). A bonferroni selection procedure when using common random numbers with unknown variances. In: Proceedings of the Winter Simulation Conference. IEEE, 313–315

[22] Dean J, Ghemawat S (2008). MapReduce: Simplified data processing on large clusters. Communications of the ACM, 51(1): 107–113

[23] Eckman D J, Henderson S G (2018a). Guarantees on the probability of good selection. In: Proceedings of the Winter Simulation Conference. IEEE, 351–365

[24] Eckman D J, Henderson S G (2018b). Reusing search data in ranking and selection: What could possibly go wrong? ACM Transactions on Modeling and Computer Simulation, 28(3): 1–15

[25] Eckman D J, Henderson S G (2020). Fixed-confidence, fixed-tolerance guarantees for selection-of-the-best procedures. ACM Transactions on Modeling and Computer Simulation, 31(2): 7

[26] Even-Dar E, Mannor S, Mansour Y (2002). PAC bounds for multi-armed bandit and Markov decision processes. In: COLT '02: Proceedings of the 15th Annual Conference on Computational Learning Theory. Springer-Verlag, 255–270

[27] Even-Dar E, Mannor S, Mansour Y (2006). Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(39): 1079–1105

[28] Fabian V (1974). Note on Anderson’s sequential procedures with triangular boundary. Annals of Statistics, 2(1): 170–176

[29] Fan W W, Hong L J, Nelson B L (2016). Indifference-zone-free selection of the best. Operations Research, 64(6): 1499–1514

[30] Fan W W, Hong L J, Zhang X W (2013). Robust selection of the best. In: Proceedings of the Winter Simulation Conference. IEEE, 868–876

[31] Fan W W, Hong L J, Zhang X W (2020). Distributionally robust selection of the best. Management Science, 66(1): 190–208

[32] Feldman G, Hunter S R (2018). SCORE allocations for bi-objective ranking and selection. ACM Transactions on Modeling and Computer Simulation, 28(1): 1–28

[33] Frazier P I (2014). A fully sequential elimination procedure for indifference-zone ranking and selection with tight bounds on probability of correct selection. Operations Research, 62(4): 926–942

[34] Frazier P I, Powell W B, Dayanik S (2008). A knowledge-gradient policy for sequential information collection. SIAM Journal on Control and Optimization, 47(5): 2410–2439

[35] Frazier P I, Powell W B, Dayanik S (2009). The knowledge-gradient policy for correlated normal beliefs. INFORMS Journal on Computing, 21(4): 599–613

[36] Fu M C, Henderson S G (2017). History of seeking better solutions, aka simulation optimization. In: Proceedings of the Winter Simulation Conference. IEEE, 131–157

[37] Fu M C, Hu J Q, Chen C H, Xiong X (2007). Simulation allocation for determining the best design in the presence of correlated sampling. INFORMS Journal on Computing, 19(1): 101–111

[38] Gabillon V, Ghavamzadeh M, Lazaric A (2012). Best arm identification: A unified approach to fixed budget and fixed confidence. In: Pereira F, Burges C J C, Bottou L, Weinberger K Q, eds. Advances in Neural Information Processing Systems. Minneapolis, MN: Curran Associates, Inc., 25: 3212–3220

[39] Gao F, Gao S, Xiao H, Shi Z (2019a). Advancing constrained ranking and selection with regression in partitioned domains. IEEE Transactions on Automation Science and Engineering, 16(1): 382–391

[40] Gao S, Chen W, Shi L (2017a). A new budget allocation framework for the expected opportunity cost. Operations Research, 65(3): 787–803

[41] Gao S, Du J, Chen C H (2019b). Selecting the optimal system design under covariates. In: 15th International Conference on Automation Science and Engineering (CASE). IEEE, 547–552

[42] Gao S, Xiao H, Zhou E, Chen W (2017b). Robust ranking and selection with optimal computing budget allocation. Automatica, 81: 30–36

[43] Glynn P, Juneja S (2004). A large deviations perspective on ordinal optimization. In: Proceedings of the Winter Simulation Conference. IEEE, 577–585

[44] Glynn P, Juneja S (2018). Selecting the best system and multi-armed bandits. arXiv Preprint. arXiv:1507.04564

[45] Goldsman D, Nelson B L, Banks J (1998). Comparing systems via simulation. In: Banks J, ed. Handbook of Simulation: Principles, Methodology, Advances, Applications, Practice. Hoboken, NJ: Wiley, 273–306

[46] Gropp W, Lusk E, Skjellum A (1999). Using MPI: Portable Parallel Programming with the Message-Passing Interface, vol. 1. Cambridge, MA: MIT press

[47] Gupta S (1956). On a Decision Rule for a Problem in Ranking Means. Dissertation for the Doctorol Degree. Chapel Hill, NC: University of North Carolina

[48] He D, Chick S E, Chen C H (2007). Opportunity cost and OCBA selection procedures in ordinal optimization for a fixed number of alternative systems. IEEE Transactions on Systems, Man and Cybernetics: Part C, Applications and Reviews, 37(5): 951–961

[49] He D, Lee L H, Chen C H, Fu M C, Wasserkrug S (2010). Simulation optimization using the cross-entropy method with optimal computing budget allocation. ACM Transactions on Modeling and Computer Simulation, 20(1): 1–22

[50] Healey C M, Andradóttir S, Kim S H (2014). Selection procedures for simulations with multiple constraints under independent and correlated sampling. ACM Transactions on Modeling and Computer Simulation, 24(3): 14

[51] Healey C M, Andradóttir S, Kim S H (2015). A minimal switching procedure for constrained ranking and selection under independent or common random numbers. IIE Transactions, 47(11): 1170–1184

[52] Hong L J (2006). Fully sequential indifference-zone selection procedures with variance-dependent sampling. Naval Research Logistics, 53(5): 464–476

[53] Hong L J, Luo J, Nelson B L (2015a). Chance constrained selection of the best. INFORMS Journal on Computing, 27(2): 317–334

[54] Hong L J, Nelson B L (2005). The tradeoff between sampling and switching: New sequential procedures for indifference-zone selection. IIE Transactions, 37(7): 623–634

[55] Hong L J, Nelson B L (2007a). A framework for locally convergent random-search algorithms for discrete optimization via simulation. ACM Transactions on Modeling and Computer Simulation, 17(4): 19

[56] Hong L J, Nelson B L (2007b). Selecting the best system when systems are revealed sequentially. IIE Transactions, 39(7): 723–734

[57] Hong L J, Nelson B L (2009). A brief introduction to optimization via simulation. In: Proceedings of the Winter Simulation Conference. IEEE, 75–85

[58] Hong L J, Nelson B L, Xu J (2015b). Discrete optimization via simulation. In: Fu M C, ed. Handbook of Simulation Optimization. Berlin: Springer

[59] Hu R, Ludkovski M (2017). Sequential design for ranking response surfaces. SIAM/ASA Journal on Uncertainty Quantification, 5(1): 212–239

[60] Hunter S R, Applegate E A, Arora V, Chong B, Cooper K, Rincón-Guevara O, Vivas-Valencia C (2019). An introduction to multiobjective simulation optimization. ACM Transactions on Modeling and Computer Simulation, 29(1): 1–36

[61] Hunter S R, Nelson B L (2017). Parallel ranking and selection. In: Tolk A, Fowler J, Shao G, Yücesan E, eds. Advances in Modeling and Simulation. Berlin: Springer, 249–275

[62] Hunter S R, Pasupathy R (2013). Optimal sampling laws for stochastically constrained simulation optimization on finite sets. INFORMS Journal on Computing, 25(3): 527–542

[63] Jamieson K, Malloy M, Nowak R, Bubeck S (2014). lil’UCB: An optimal exploration algorithm for multi-armed bandits. In: Conference on Learning Theory, 423–439

[64] Kamiński B, Szufel P (2018). On parallel policies for ranking and selection problems. Journal of Applied Statistics, 45(9): 1690–1713

[65] Kao S C, Lai T L (1980). Sequential selection procedures based on confidence sequences for normal populations. Communications in Statistics: Theory and Methods, 9(16): 1657–1676

[66] Kaufmann E, Kalyanakrishnan S (2013). Information complexity in bandit subset selection. Journal of Machine Learning Research, 30: 228–251

[67] Kim S H, Nelson B L (2001). A fully sequential procedure for indifference-zone selection in simulation. ACM Transactions on Modeling and Computer Simulation, 11(3): 251–273

[68] Kim S H, Nelson B L (2006a). On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Operations Research, 54(3): 475–488

[69] Kim S H, Nelson B L (2006b). Selecting the best system. In: Henderson S G, Nelson B L, eds. Handbooks in Operations Research and Management Science: Simulation. Amsterdam: Elsevier, 501–534

[70] Lee L H, Chew E P, Teng S, Goldsman D (2010). Finding the non-dominated Pareto set for multi-objective simulation models. IIE Transactions, 42(9): 656–674

[71] Lee L H, Pujowidianto N A, Li L W, Chen C H, Yap C M (2012). Approximate simulation budget allocation for selecting the best design in the presence of stochastic constraints. IEEE Transactions on Automatic Control, 57(11): 2940–2945

[72] Li X, Zhang X, Zheng Z (2018). Data-driven ranking and selection: High-dimensional covariates and general dependence. In: Proceedings of the Winter Simulation Conference. IEEE, 1933–1944

[73] Luo J, Hong L J (2011). Large-scale ranking and selection using cloud computing. In: Proceedings of the Winter Simulation Conference. IEEE, 4051–4061

[74] Luo J, Hong L J, Nelson B L, Wu Y (2015). Fully sequential procedures for large-scale ranking-and-selection problems in parallel computing environments. Operations Research, 63(5): 1177–1194

[75] Ma S (2018). Sequential Ranking and Selection Procedures and Sample Complexity. Dissertation for the Doctorol Degree. New York: Cornell University

[76] Ma S, Henderson S G (2017). An efficient fully sequential selection procedure guaranteeing probably approximately correct selection. In: Proceedings of the Winter Simulation Conference. IEEE, 2225–2236

[77] Nelson B L, Matejcik F J (1995). Using common random numbers for indifference-zone selection and multiple comparisons in simulation. Management Science, 41(12): 1935–1945

[78] Nelson B L, Swann J, Goldsman D, Song W (2001). Simple procedures for selecting the best simulated system when the number of alternatives is large. Operations Research, 49(6): 950–963

[79] Ni E C, Ciocan D F, Henderson S G, Hunter S R (2015). Comparing message passing interface and MapReduce for large-scale parallel ranking and selection. In: Proceedings of the Winter Simulation Conference. IEEE, 3858–3867

[80] Ni E C, Ciocan D F, Henderson S G, Hunter S R (2017). Efficient ranking and selection in parallel computing environments. Operations Research, 65(3): 821–836

[81] Ni E C, Hunter S R, Henderson S G (2013). Ranking and selection in a high performance computing environment. In: Proceedings of the Winter Simulation Conference. IEEE, 833–845

[82] Ni E C, Hunter S R, Henderson S G (2014). A comparison of two parallel ranking and selection procedures. In: Proceedings of the Winter Simulation Conference. IEEE, 3761–3772

[83] Pasupathy R, Hunter S R, Pujowidianto N A, Lee L H, Chen C H (2015). Stochastically constrained ranking and selection via SCORE. ACM Transactions on Modeling and Computer Simulation, 25(1): 1–26

[84] Paulson E (1949). A multiple decision procedure for certain problems in the analysis of variance. Annals of Mathematical Statistics, 20(1): 95–98

[85] Paulson E (1964). A sequential procedure for selecting the population with the largest mean from k. Annals of Mathematical Statistics, 35(1): 174–180

[86] Pearce M, Branke J (2017). Efficient expected improvement estimation for continuous multiple ranking and selection. In: Proceedings of the Winter Simulation Conference. IEEE, 2161–2172

[87] Pei L, Nelson B L, Hunter S (2018). A new framework for parallel ranking & selection using an adaptive standard. In: Proceedings of the Winter Simulation Conference. IEEE, 2201–2212

[88] Peng Y, Chong E K, Chen C H, Fu M C (2018). Ranking and selection as stochastic control. IEEE Transactions on Automatic Control, 63(8): 2359–2373

[89] Peng Y, Fu M C (2017). Myopic allocation policy with asymptotically optimal sampling rate. IEEE Transactions on Automatic Control, 62(4): 2041–2047

[90] Pichitlamken J, Nelson B L, Hong L J (2006). A sequential procedure for neighborhood selection-of-the-best in optimization via simulation. European Journal of Operational Research, 173(1): 283–298

[91] Rinott Y (1978). On two-stage selection procedures and related probability-inequalities. Communications in Statistics: Theory and Methods, 7(8): 799–811

[92] Ryzhov I O (2016). On the convergence rates of expected improvement methods. Operations Research, 64(6): 1515–1528

[93] Shen H, Hong L J, Zhang X (2017). Ranking and selection with covariates. In: Proceedings of the Winter Simulation Conference. IEEE, 169

[94] Shen H, Hong L J, Zhang X (2019). Ranking and selection with covariates for personalized decision making. arXiv Preprint. arXiv:1710.02642

[95] Song E, Nelson B L, Hong L J (2015). Input uncertainty and indifference-zone ranking & selection. In: Proceedings of the Winter Simulation Conference. IEEE, 414–424

[96] Tsai S C, Luo J, Sung C C (2017). Combined variance reduction techniques in fully sequential selection procedures. Naval Research Logistics, 64(6): 502–527

[97] Tsai S C, Nelson B L (2009). Fully sequential selection procedures with control variates. IIE Transactions, 42(1): 71–82

[98] Wald A (1945). Sequential tests of statistical hypotheses. Annals of Mathematical Statistics, 16(2): 117–186

[99] Wald A (1947). Sequential Analysis. New York: John Wiley & Sons

[100] Wang W, Wan H (2017). Sequential probability ratio test for multiple-objective ranking and selection. In: Proceedings of the Winter Simulation Conference. IEEE, 1998–2009

[101] Wilcox R R (1984). A table for Rinott’s selection procedure. Journal of Quality Technology, 16(2): 97–100

[102] Wu D, Zhou E (2019). Fixed confidence ranking and selection under input uncertainty. In: Proceedings of the Winter Simulation Conference. IEEE, 3717–3727

[103] Xie J, Frazier P, Chick S E (2016). Bayesian optimization via simulation with pairwise sampling and correlated prior beliefs. Operations Research, 64(2): 542–559

[104] Yücesan E, Luo Y C, Chen C H, Lee I (2001). Distributed web-based simulation experiments for optimization. Simulation Practice and Theory, 9(1–2): 73–90

[105] Zaharia M, Chowdhury M, Franklin M J, Shenker S, Stoica I (2010). Spark: Cluster computing with working sets. In: HotCloud'10: Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley, CA, 10

[106] Zhang S, Xu J, Lee L H, Chew E P, Wong W P, Chen C H (2017). Optimal computing budget allocation for particle swarm optimization in stochastic optimization. IEEE Transactions on Evolutionary Computation, 21(2): 206–219

[107] Zhang X, Shen H, Hong L J, Ding L (2020). Knowledge gradient for selection with covariates: Consistency and computation. arXiv Preprint. arXiv:1906.05098

[108] Zhong Y, Hong L J (2020). Knockout-tournament procedures for large-scale ranking and selection in parallel computing environments. Operations Research, to appear

[109] Zhong Y, Liu S, Luo J, Hong L J (2020). Speeding up Paulson’s procedure for large-scale problems using parallel computing. INFORMS Journal on Computing, in press, doi: 10.1287/ijoc.2020. 1054

RIGHTS & PERMISSIONS

The Author(s) 2021. This article is published with open access at link.springer.com and journal.hep.com.cn