A Distribution-Free Sequential Selection Strategy: Data-Driven Optimal Allocation via Balancing Empirical Large Deviations

References

• Agrawal S, Goyal N (2012) Analysis of Thompson sampling for the multi-armed bandit problem. Mannor S, Srebro N, Williamson RC, eds. Proc. 25th Annual Conf. Learn. Theory (PMLR, New York), 39:1–39:26.Google Scholar
• Ajami S, Ketabi S, Yarmohammadian MH, Bagherian H (2012) Wait time in emergency department (ed) processes. Medical Arch. 66(1):53–57.Crossref, Google Scholar
• Akcay A, Corlu CG (2017) Simulation of inventory systems with unknown input models: A data-driven approach. Internat. J. Production. Res. 55(19):5826–5840.Crossref, Google Scholar
• Avci H, Nelson BL, Wächter A (2023) Getting to “rate-optimal” in ranking & selection. Preprint, submitted February 4, https://arxiv.org/abs/2302.02254.Google Scholar
• Bechhofer R (1954) A single-sample multiple decision procedure for ranking means of normal populations with known variances. Ann. Math. Statist. 25(1):16–39.Crossref, Google Scholar
• Blanchet J, Liu J, Zwart B (2008) Large deviations perspective on ordinal optimization of heavy-tailed systems. Mason SJ, Hill RR, Moench L, Rose O, eds. Proc. Winter Simulation Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 489–494.Google Scholar
• Bunge M (1963) A general black box theory. Philosophical Sci. 30(4):346–358.Crossref, Google Scholar
• Chen Y (2023) Data-driven optimal allocation for ranking and selection under unknown sampling distributions. Corlu CG, Hunter SR, Lam H, Onggo BS, Shortle J, Biller B, eds. Proc. Winter Simulation Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 3382–3387.Google Scholar
• Chen Y (2026) A distribution-free sequential selection strategy: Data-driven optimal allocation via balancing empirical large deviations. https://doi.org/10.1287/ijoc.2024.0895.cd, https://github.com/INFORMSJoC/2024.0895.Google Scholar
• Chen CH, Lee LH (2010) Stochastic Simulation Optimization: An Optimal Computing Budget Allocation (World Scientific, Singapore).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.Link, Google Scholar
• Chen Y, Zhang Q, Li M, Cai W (2022) Sequential selection for accelerated life testing via approximate bayesian inference. Naval Res. Logist. 69(2):336–351.Crossref, 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
• Du J, Gao S, Chen CH (2024) A contextual ranking and selection method for personalized medicine. Manufacturing Service Oper. Management 26(1):167–181.Link, Google Scholar
• Duffy KR, Williamson BD (2015) Estimating large deviation rate functions. Preprint, submitted November 7, https://arxiv.org/abs/1511.02295.Google Scholar
• Eckman DJ, Henderson SG (2022) Posterior-based stopping rules for bayesian ranking-and-selection procedures. INFORMS J. Comput. 34(3):1711–1728.Link, Google Scholar
• Eckman DJ, Plumlee M, Nelson BL (2020) Revisiting subset selection. Bae KH, Feng B, Kim S, Lazarova-Molnar S, Zheng Z, Roeder T, Thiesing R, eds. Proc. Winter Simulation Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 2972–2983.Crossref, Google Scholar
• Elsayed EA (2012) Reliability Engineering (Wiley Series in Systems Engineering and Management) (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Fan W, Hong LJ, Zhang X (2020) Distributionally robust selection of the best. Management Sci. 66(1):190–208.Link, Google Scholar
• Feller W (1968) An extention of the law of the iterated logarithm to variables without variance. J. Math. Mechanics 18(4):343–355.Google Scholar
• Feuerverger A (1989) On the empirical saddlepoint approximation. Biometrika 76(3):457–464.Crossref, 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. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 682–689. Google Scholar
• Garivier A, Kaufmann E (2016) Optimal best arm identification with fixed confidence. Feldman V, Rakhlin A, Shamir O, eds. Proc. Conf. Learn. Theory (PMLR, New York), 998–1027.Google Scholar
• Glynn PW, Juneja S (2004) A large deviations perspective on ordinal optimization. Ingalls R, Rossetti MD, Smith JS, Peters BA, eds. Proc. Winter Simulation Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 577–585.Crossref, Google Scholar
• Glynn P, Juneja S (2018) Selecting the best system and multi-armed bandits. Preprint, submitted September 10, https://arxiv.org/abs/1507.04564.Google Scholar
• Gumbel EJ (1941) The return period of flood flows. Ann. Math. Statist. 12(2):163–190.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, McClosky B (2016) Maximizing quantitative traits in the mating design problem via simulation-based Pareto estimation. IIE Trans. 48(6):565–578.Crossref, Google Scholar
• Jones D, Schonlau M, Welch W (1998) Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4):455–492.Crossref, Google Scholar
• Kim SH, Nelson BL (2001) A fully sequential procedure for indifference-zone selection in simulation. ACM Trans. Modeling Comput. Simulations 11(3):251–273.Crossref, Google Scholar
• Kim S, Nelson B (2006) On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Oper. Res. 54(3):475–488.Link, Google Scholar
• Kim T, Kim K, Song E (2024) Selection of the most probable best. Oper. Res. 73(6):3199–3218.Link, Google Scholar
• Law AM, Kelton WD (2000) Simulation Modeling and Analysis, 3rd ed. (McGraw-Hill, New York).Google Scholar
• Li J, Liu W, Pedrielli G, Lee LH, Chew EP (2018) Optimal computing budget allocation to select the nondominated systems—A large deviations perspective. IEEE Trans. Automated Control 63(9):2913–2927.Crossref, Google Scholar
• Norden J, O’Kelly M, Sinha A (2019) Efficient black-box assessment of autonomous vehicle safety. Preprint, submitted December 8, https://arxiv.org/abs/1912.03618.Google Scholar
• Pasupathy R, Hunter SR, Pujowidianto NA, Lee LH, Chen CH (2014) Stochastically constrained ranking and selection via SCORE. ACM Trans. Modeling Comput. Simulations 25(1):1:1–1:26.Google Scholar
• Peng Y, Chong EK, Chen CH, Fu MC (2018) Ranking and selection as stochastic control. IEEE Trans. Automated Control 63(8):2359–2373.Crossref, Google Scholar
• Qin C, Klabjan D, Russo D (2017) Improving the expected improvement algorithm. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 30 (Curran Associates, Red Hook, New York), 5381–5391.Google Scholar
• Rohwer CM, Angeletti F, Touchette H (2015) Convergence of large-deviation estimators. Phys. Rev. E 92(5):052104.Crossref, Google Scholar
• Russo D (2020) Simple bayesian algorithms for best-arm identification. Oper. Res. 68(6):1625–1647.Link, Google Scholar
• Russo D, Van Roy B (2014) Learning to optimize via posterior sampling. Math. Oper. Res. 39(4):1221–1243.Link, Google Scholar
• Ryzhov IO (2018) The local time method for targeting and selection. Oper. Res. 66(5):1406–1422.Link, Google Scholar
• Shen H, Hong LJ, Zhang X (2021) Ranking and selection with covariates for personalized decision making. INFORMS J. Comput. 33(4):1500–1519.Abstract, Google Scholar
• Shi X, Peng Y, Tuffin B (2024) Finite budget allocation improvement in ranking and selection. Lam H, Azar E, Batur D, Gao S, Xie W, Hunter SR, Rossetti MD, eds. Proc. Winter Simulation Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 477–488.Google Scholar
• Shin D, Broadie M, Zeevi A (2018) Tractable sampling strategies for ordinal optimization. Oper. Res. 66(6):1693–1712.Link, Google Scholar
• Sikorski K (1982) Bisection is optimal. Numerische Math. (Heidelberg) 40(1):111–117.Crossref, Google Scholar
• Song E, Nelson BL (2019) Input–output uncertainty comparisons for discrete optimization via simulation. Oper. Res. 67(2):562–576.Abstract, Google Scholar
• Touchette H (2009) The large deviation approach to statistical mechanics. Phys. Rep. 478(1):1–69.Crossref, Google Scholar
• Wang Y, Zhou E (2025) Optimal computing budget allocation for data-driven ranking and selection. INFORMS J. Optim. 7(1):1–19.Link, Google Scholar
• Xiao H, Gao F, Lee LH (2020) Optimal computing budget allocation for complete ranking with input uncertainty. IISE Trans. 52(5):489–499.Crossref, Google Scholar
• Xu J, Nelson BL, Hong LJ (2010) Industrial strength COMPASS: A comprehensive algorithm and software for optimization via simulation. ACM Trans. Modeling Comput. Simulations 20(1):1–29.Crossref, Google Scholar