On the finite-sample statistical validity of adaptive fully sequential procedures. (English) Zbl 1541.62058
Summary: We consider the simulation optimization problem of selecting the best system design from a finite set of alternatives, which is known as ranking and selection (R&S). Many fully sequential procedures have been proposed to solve the R&S problem using a static sampling rule in order to ensure a finite-sample statistical guarantee. In this paper, we develop fully sequential procedures that can incorporate various adaptive sampling rules, based on a modification of E. Paulson’s bound [Ann. Math. Stat. 35, 174–180 (1964; Zbl 0136.39404)], while still preserving the finite-sample guarantee. In particular, we propose an adaptive sampling rule that utilizes the consecutively updated sample mean and sample variance information by solving a minimization problem of the approximated total sample size. Finally, we demonstrate the efficiency of the proposed procedures with several existing procedures through extensive simulation experiments, and apply them to solve an ambulance dispatching problem.
Keywords:
simulation; ranking and selection; adaptive sampling rule; finite-sample statistical guarantee; fully sequential procedureCitations:
Zbl 0136.39404References:
| [1] | Batur, D.; Choobineh, F., A quantile-based approach to system selection, European Journal of Operational Research, 202, 3, 764-772 (2010) · Zbl 1176.90137 |
| [2] | Batur, D.; Choobineh, F. F., Selecting the best alternative based on its quantile, INFORMS Journal on Computing, 33, 2, 657-671 (2021) · Zbl 1466.90038 |
| [3] | Bazaraa, M. S.; Sherali, H. D.; Shetty, C. M., Nonlinear programming: Theory and algorithms (2013), John Wiley & Sons |
| [4] | Bechhofer, R. E., A single-sample multiple decision procedure for ranking means of normal populations with known variances, The Annals of Mathematical Statistics, 25, 1, 16-39 (1954) · Zbl 0055.13003 |
| [5] | Chen, C.-H.; He, D.; Fu, M., Efficient dynamic simulation allocation in ordinal optimization, IEEE Transactions on Automatic Control, 51, 12, 2005-2009 (2006) · Zbl 1366.90145 |
| [6] | Chen, C.-H.; Lee, L. H., Stochastic simulation optimization: An optimal computing budget allocation (2011), World Scientific Publishing |
| [7] | Chen, C.-H.; Lin, J.; Yücesan, E.; Chick, S. E., Simulation budget allocation for further enhancing the efficiency of ordinal optimization, Discrete Event Dynamic Systems, 10, 3, 251-270 (2000) · Zbl 0970.90014 |
| [8] | Chen, C.-H.; Yücesan, E., An alternative simulation budget allocation scheme for efficient simulation, International Journal of Simulation and Process Modelling, 1, 49-57 (2005) |
| [9] | Chen, Y.; Ryzhov, I. O., Complete expected improvement converges to an optimal budget allocation, Advances in Applied Probability, 51, 1, 209-235 (2019) · Zbl 1428.62038 |
| [10] | Forthcoming. |
| [11] | Chick, S. E.; Inoue, K., New two-stage and sequential procedures for selecting the best simulated system, Operations Research, 49, 5, 732-743 (2001) |
| [12] | Clark, G. M.; Yang, W.n., A Bonferroni selection procedure when using common random numbers with unknown variances, Proceedings of the 18th conference on winter simulation, 313-315 (1986) |
| [13] | Durbin, J., The first-passage density of a continuous gaussian process to a general boundary, Journal of Applied Probability, 22, 1, 99-122 (1985) · Zbl 0576.60029 |
| [14] | Fabian, V., Note on Anderson’s sequential procedures with triangular boundary, The Annals of Statistics, 2, 170-176 (1974) · Zbl 0288.62033 |
| [15] | Fan, W.; Hong, L. J.; Nelson, B. L., Indifference-zone-free selection of the best, Operations Research, 64, 6, 1499-1514 (2016) · Zbl 1406.91083 |
| [16] | Gao, S.; Chen, W.; Shi, L., A new budget allocation framework for the expected opportunity cost, Operations Research, 65, 3, 787-803 (2017) · Zbl 1407.91142 |
| [17] | Gao, S.; Xiao, H.; Zhou, E.; Chen, W., Robust ranking and selection with optimal computing budget allocation, Automatica, 81, 30-36 (2017) · Zbl 1372.93217 |
| [18] | Glynn, P.; Juneja, S., A large deviations perspective on ordinal optimization, Proceedings of the 2004 winter simulation conference, vol. 1 (2004), IEEE |
| [19] | Goodwin, T.; Xu, J.; Celik, N.; Chen, C. H., Real-time digital twin-based optimization with predictive simulation learning, Journal of Simulation, 1-18 (2022) |
| [20] | He, D.; Chick, S. E.; Chen, C. H., 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 (2007) |
| [21] | Hong, L. J., Fully sequential indifference-zone selection procedures with variance-dependent sampling, Naval Research Logistics, 53, 5, 464-476 (2006) · Zbl 1127.62066 |
| [22] | Hong, L. J.; Fan, W.; Luo, J., Review on ranking and selection: A new perspective, Frontiers of Engineering Management, 8, 3, 321-343 (2021) |
| [23] | Hunter, S. R.; Closky, B. M., Maximizing quantitative traits in the mating design problem via simulation-based Pareto estimation, IIE Transactions, 48, 6, 565-578 (2016) |
| [24] | Hunter, S. R.; Nelson, B. L., Parallel ranking and selection, Advances in modeling and simulation, 249-275 (2017), Springer |
| [25] | Jennison, C.; Johnstone, I. M.; Turnbull, B. W., Asymptotically optimal procedures for sequential adaptive selection of the best of several normal means, Technical report (1980), Department of Operations Research and Industrial Engineering, Cornell University |
| [26] | Kim, S.-H.; Nelson, B. L., A fully sequential procedure for indifference-zone selection in simulation, ACM Transactions on Modeling and Computer Simulation, 11, 251-273 (2001) · Zbl 1490.62207 |
| [27] | Lee, L. H.; Pujowidianto, N. A.; Li, L.-W.; Chen, C.-H.; Yap, C. M., Approximate simulation budget allocation for selecting the best design in the presence of stochastic constraints, IEEE Transactions on Automatic Control, 57, 11, 2940-2945 (2012) · Zbl 1369.90202 |
| [28] | Lee, M.; Park, I.; Park, D.; Park, C., Constrained ranking and selection for operations of an emergency department, International Journal of Simulation Modelling, 16, 4, 563-575 (2017) |
| [29] | Lee, M. L.; Park, C.; Park, D. U., Self-adjusting the tolerance level in a fully sequential feasibility check procedure, European Journal of Operational Research, 271, 2, 733-745 (2018) · Zbl 1403.90535 |
| [30] | Ma, S.; Henderson, S. G., An efficient fully sequential selection procedure guaranteeing probably approximately correct selection, 2017 winter simulation conference (WSC), 2225-2236 (2017), IEEE |
| [31] | Nelson, B. L.; Swann, J.; Goldsman, D.; Song, W., Simple procedures for selecting the best simulated system when the number of alternatives is large, Operations Research, 49, 950-963 (2001) |
| [32] | Ni, E. C.; Hunter, S. R.; Henderson, S. G.; Topaloglu, H., Exploring bounds on ambulance deployment policy performance, 2012 winter simulation conference, 1-12 (2012) |
| [33] | Pasupathy, R.; Hunter, S. R.; Pujowidianto, N. A.; Lee, L. H.; Chen, C. H., Stochastically constrained ranking and selection via score, ACM Transactions on Modeling and Computer Simulation (TOMACS), 25, 1, 1-26 (2014) · Zbl 1371.65059 |
| [34] | Paulson, E., A sequential procedure for selecting the population with the largest mean from \(k\) normal populations, The Annals of Mathematical Statistics, 35, 174-180 (1964) · Zbl 0136.39404 |
| [35] | Pedrielli, G.; Candan, K. S.; Chen, X.; Mathesen, L.; Inanalouganji, A.; Xu, J.; Lee, L. H., Generalized ordinal learning framework (golf) for decision making with future simulated data, Asia-Pacific Journal of Operational Research, 36, 06, 1940011 (2019) |
| [36] | Peng, Y.; Chen, C.-H.; Fu, M. C.; Hu, J.-Q.; Ryzhov, I. O., Efficient sampling allocation procedures for optimal quantile selection, INFORMS Journal on Computing, 33, 1, 230-245 (2021) · Zbl 07362313 |
| [37] | Peng, Y.; Chong, E. K.; Chen, C.-H.; Fu, M. C., Ranking and selection as stochastic control, IEEE Transactions on Automatic Control, 63, 8, 2359-2373 (2018) · Zbl 1423.93422 |
| [38] | Puyang, X.; Zhong, Y., Asymptotic efficiency analysis on the modified Paulson’s procedure with a PAC guarantee, Operations Research Letters, 49, 1, 35-39 (2021) · Zbl 1525.62013 |
| [39] | Rinott, Y., On two-stage selection procedures and related probability-inequalities, Communications in Statistics - Theory and Methods, 7, 8, 799-811 (1978) · Zbl 0392.62020 |
| [40] | Robbins, H.; Siegmund, D. O., Sequential tests involving two populations, Journal of the American Statistical Association, 69, 132-139 (1974) · Zbl 0296.62072 |
| [41] | Russo, D., Simple bayesian algorithms for best-arm identification, Operations Research, 68, 6, 1625-1647 (2020) · Zbl 1458.91111 |
| [42] | Shin, D.; Broadie, M.; Zeevi, A., Tractable sampling strategies for ordinal optimization, Operations Research, 66, 6, 1693-1712 (2018) · Zbl 1467.62041 |
| [43] | Tsai, S. C.; Chen, S. T., A simulation-based multi-objective optimization framework: A case study on inventory management, Omega, 70, 148-159 (2017) |
| [44] | Wu, R.; Liu, S.; Luo, J., Adaptive sampling rule for ranking-and-selection problem, The 13th IEEE conference on automation science and engineering (CASE), 1499-1505 (2017) |
| [45] | Wu, R.; Liu, S.; Shi, Z., Algorithm for calculating the initial sample size in a fully sequential ranking and selection procedure, Asia-Pacific Journal of Operational Research, 37, 03, 2050015 (2020) · Zbl 1460.62133 |
| [46] | Xiao, H.; Gao, S., Simulation budget allocation for selecting the top-m designs with input uncertainty, IEEE Transactions on Automatic Control, 63, 09, 3127-3134 (2018) · Zbl 1423.90127 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
