Asymptotically Optimal Sampling Policy for Selecting Top-m Alternatives

References

• Bertsekas DP (2005) Dynamic programming and suboptimal control: A survey from ADP to MPC. Eur. J. Control 11(4–5):310–334.Crossref, Google Scholar
• Boyd S, Boyd SP, Vandenberghe L (2009) Convex Optimization, 7th ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bubeck S, Wang T, Viswanathan N (2013) Multiple identifications in multi-armed bandits. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. on Machine Learn. (PMLR, New York), 258–265.Google Scholar
• Cassandras CG, Lafortune S (2009) Introduction to Discrete Event Systems (Springer Science & Business Media, Boston).Google Scholar
• Chen CH, Lee LH (2011) Stochastic Simulation Optimization: An Optimal Computing Budget Allocation, vol. 1 (World Scientific, Singapore).Google Scholar
• Chen CH, He D, Fu M (2006) Efficient dynamic simulation allocation in ordinal optimization. IEEE Trans. Automated Control 51(12):2005–2009.Crossref, Google Scholar
• Chen CH, He D, Fu M, Lee LH (2008) Efficient simulation budget allocation for selecting an optimal subset. INFORMS J. Comput. 20(4):579–595.Link, Google Scholar
• Chen CH, Lin J, Yücesan E, Chick SE (2000) Simulation budget allocation for further enhancing the efficiency of ordinal optimization. J. Discrete Event Dynamic Systems 10(3):251–270.Crossref, Google Scholar
• Chen Y, Ryzhov IO (2019) Complete expected improvement converges to an optimal budget allocation. Adv. Appl. Probability 51(1):209–235.Crossref, Google Scholar
• Chen Y, Ryzhov IO (2023) Balancing optimal large deviations in sequential selection. Management Sci. 69(6):3457–3473.Google Scholar
• Chick SE, Inoue K (2001) New two-stage and sequential procedures for selecting the best simulated system. Oper. Res. 49(5):732–743.Link, Google Scholar
• Chick SE, Branke J, Schmidt C (2010) Sequential sampling to myopically maximize the expected value of information. INFORMS J. Comput. 22(1):71–80.Link, Google Scholar
• DeGroot MH (2005) Optimal Statistical Decisions, vol. 82 (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Frazier PI, Powell W, Dayanik S (2009) The knowledge-gradient policy for correlated normal beliefs. INFORMS J. Comput. 21(4):599–613.Link, Google Scholar
• Frazier PI, Powell WB, Dayanik S (2008) A knowledge-gradient policy for sequential information collection. SIAM J. Control Optim. 47(5):2410–2439.Crossref, Google Scholar
• Gabillon V, Ghavamzadeh M, Lazaric A (2012) Best arm identification: A unified approach to fixed budget and fixed confidence. Adv. Neural Inform. Processing Systems 2:3212–3220.Google Scholar
• Gao F, Gao S (2016) Optimal computing budget allocation with exponential underlying distribution. Roeder TMK, Frazier PI, Szechtman R, Zhou E, Huschka T, Chick SE, eds. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 682–689.Google Scholar
• Gao S, Chen W (2015a) Efficient subset selection for the expected opportunity cost. Automatica J. IFAC 59:19–26.Crossref, Google Scholar
• Gao S, Chen W (2015b) A note on the subset selection for simulation optimization. Yilmaz L, Chan WKV, Moon I, Roeder TMK, Macal C, Rossetti MD, eds. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 3768–3776.Google Scholar
• Gao S, Chen W (2016) A new budget allocation framework for selecting top simulated designs. IIE Trans. 48(9):855–863.Crossref, Google Scholar
• Gao S, Du J, Chen CH (2019) Selecting the optimal system design under covariates. Proc. 15th Internat. Conf. on Automation Sci. and Engrg. (IEEE, New York), 547–552.Google Scholar
• Glynn PW, Juneja S (2004) A large deviations perspective on ordinal optimization. Ingalls RG, Rossetti MD, Smith JS, Peters BA, eds. Proc. Winter Simulation Conf., vol. 1 (IEEE, Piscataway, NJ).Google Scholar
• Glynn PW, Juneja S (2011) Ordinal optimization: A nonparametric framework. Jain S, Creasey RR, Himmelspach J, White KP, Fu M, eds. Proc. 11 Winter Simulation Conf. (IEEE, Piscataway, NJ), 4057–4064.Google Scholar
• Ho YC, Sreenivas R, Vakili P (1992) Ordinal optimization of deds. Discrete Event Dynamics Systems 2(1):61–88.Crossref, Google Scholar
• Hong LJ, Fan W, Luo J (2021) Review on ranking and selection: A new perspective. Frontiers Engrg. Management 8(3):321–343.Crossref, Google Scholar
• Hunter SR, Nelson BL (2017) Parallel ranking and selection. Adv. Modeling Simulation 249–275.Crossref, Google Scholar
• Hunter SR, Pasupathy R (2013) Optimal sampling laws for stochastically constrained simulation optimization on finite sets. INFORMS J. Comput. 25(3):527–542.Link, Google Scholar
• Jeff Hong L (2006) Fully sequential indifference-zone selection procedures with variance-dependent sampling. Naval Res. Logist. 53(5):464–476.Crossref, Google Scholar
• Kaufmann E, Cappé O, Garivier A (2016) On the complexity of best arm identification in multi-armed bandit models. J. Machine Learn. Res. 17:1–42.Google Scholar
• Kim SH, Nelson BL (2001) A fully sequential procedure for indifference-zone selection in simulation. ACM Trans. Modeling Comput. Simulation 11(3):251–273.Crossref, Google Scholar
• Kim SH, Nelson BL (2006) Selecting the best system. Handbook Oper. Res. Management Sci. 13:501–534.Google Scholar
• Koenig LW, Law AM (1985) A procedure for selecting a subset of size m containing the l best of k independent normal populations, with applications to simulation. Comm. Statist. Simulation Comput. 14(3):719–734.Crossref, Google Scholar
• Peng Y, Chen CH, Chong EK, Fu MC (2018a) A review of static and dynamic optimization for ranking and selection. Rabe M, Juan AA, Mustafee N, Skoogh A, Jain S, Johansson B, eds. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 1909–1920.Google Scholar
• Peng Y, Chen CH, Fu MC, Hu JQ (2016) Dynamic sampling allocation and design selection. INFORMS J. Comput. 28(2):195–208.Link, Google Scholar
• Peng Y, Chen CH, Fu MC, Hu JQ (2018b) Gradient-based myopic allocation policy: An efficient sampling procedure in a low-confidence scenario. IEEE Trans. Automated Control 63(9):3091–3097.Crossref, Google Scholar
• Peng Y, Chong EK, Chen CH, Fu MC (2018c) Ranking and selection as stochastic control. IEEE Trans. Automated Control 63(8):2359–2373.Crossref, Google Scholar
• Pillac V, Van Hentenryck P, Even C (2016) A conflict-based path-generation heuristic for evacuation planning. Transportation Res. Part B: Methodological 83:136–150.Crossref, Google Scholar
• Rinott Y (1978) On two-stage selection procedures and related probability-inequalities. Comm. Statist. Theory Methods 7(8):799–811.Crossref, Google Scholar
• Ryzhov IO (2016) On the convergence rates of expected improvement methods. Oper. Res. 64(6):1515–1528.Link, Google Scholar
• Shin D, Broadie M, Zeevi A (2022) Practical nonparametric sampling strategies for quantile-based ordinal optimization. INFORMS J. Comput. 34(2):752–768.Link, Google Scholar
• Xiao H, Gao S, Lee LH (2017) Simulation budget allocation for simultaneously selecting the best and worst subsets. Automatica J. IFAC 84:117–127.Crossref, Google Scholar
• Xiao H, Lee LH, Ng KM (2013) Optimal computing budget allocation for complete ranking. IEEE Trans. Automated Sci. Engrg. 11(2):516–524.Crossref, Google Scholar
• You W, Qin C, Wang Z, Yang S (2022) Information-directed selection for top-two algorithms. Preprint, submitted May 24, https://arxiv.org/abs/2205.12086.Google Scholar
• Zeitouni O, Dembo A (2010) Large Deviations Techniques and Applications, vol. 38, 2nd ed. (Springer-Verlag, New York).Google Scholar
• Zhang G, Li H, Peng Y (2020) Sequential sampling for a ranking and selection problem with exponential sampling distributions. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 2984–2996.Google Scholar
• Zhang G, Chen B, Jia Q-S, Peng Y (2022) Efficient sampling policy for selecting a subset with the best. IEEE Trans. Automatic Control. 68(8):4904–4911.Google Scholar
• Zhang G, Peng Y, Zhang J, Zhou E (2021) Dynamic sampling policy for subset selection. Kim S, Feng B, Smith K, Masoud S, Zheng Z, Szabo C, Loper M, eds. Proc. Winter Simulation Conf. (IEEE, Piscataway, NJ), 1–12.Google Scholar
• Zhang G, Peng Y, Zhang J, Zhou E (2023) Asymptotically optimal sampling policy for selecting top-m alternatives. http://dx.doi.org/10.1287/ijoc.2021.0333.cd, https://github.com/INFORMSJoC/2021.0333.Google Scholar
• Zhang J, Liu Y, Zhao Y, Deng T (2020) Emergency evacuation problem for a multi-source and multi-destination transportation network: Mathematical model and case study. Ann. Oper. Res. 291:1153–1181.Google Scholar
• Zhang S, Lee LH, Chew EP, Chen CH, Jen HY (2012) An improved simulation budget allocation procedure to efficiently select the optimal subset of many alternatives. Proc. 8th Internat. Conf. on Automation Sci. and Engrg (IEEE, Piscataway, NJ), 230–236.Google Scholar
• Zhang S, Lee LH, Chew EP, Xu J, Chen CH (2015) A simulation budget allocation procedure for enhancing the efficiency of optimal subset selection. IEEE Trans. Automated Control 61(1):62–75.Crossref, Google Scholar