research-article

An efficient fully sequential selection procedure guaranteeing probably approximately correct selection

Authors:

Shane G. HendersonAuthors Info & Claims

WSC '17: Proceedings of the 2017 Winter Simulation Conference

Article No.: 177, Pages 1 - 12

Published: 03 December 2017 Publication History

Abstract

Ranking and Selection (R&S) procedures are designed for selecting the best among a finite set of systems using stochastic simulation, guaranteeing the quality of the final selection. Instead of assuming a known lower bound on the difference between the best and others, we consider the probably approximately correct (PAC) selection formulation, which ensures a high quality solution with high probability for all configurations. In this paper, we present a new fully sequential selection procedure, called the Envelope Procedure (EP), which accommodates a variety of sampling rules that, together with a carefully defined termination condition, ensures a PAC selection. A particular sampling rule that achieves good efficiency is proposed. We compare the efficiency of the EP with some existing procedures in numerical experiments, and the results show that the EP saves considerable computational effort in many problem configurations.

References

[1]

Bechhofer, R. E. 1954. "A single-sample multiple decision procedure for ranking means of normal populations with known variances". The Annals of Mathematical Statistics:16--39.

[2]

Branke, J., S. E. Chick, and C. Schmidt. 2007. "Selecting a selection procedure". Management Science 53 (12): 1916--1932.

Digital Library

[3]

Chen, C.-H., S. E. Chick, L. H. Lee, and N. A. Pujowidianto. 2015. "Ranking and selection: efficient simulation budget allocation". In Handbook of Simulation Optimization, 45--80. Springer.

[4]

Chen, C.-h., and L. H. Lee. 2011. Stochastic simulation optimization: an optimal computing budget allocation, Volume 1. World scientific.

Digital Library

[5]

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

Digital Library

[6]

Chick, S. E., and K. Inoue. 2001a. "New procedures to select the best simulated system using common random numbers". Management Science 47 (8): 1133--1149.

Digital Library

[7]

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

Digital Library

[8]

Even-Dar, E., S. Mannor, and Y. Mansour. 2002. "PAC bounds for multi-armed bandit and Markov decision processes". In International Conference on Computational Learning Theory, 255--270. Springer.

Digital Library

[9]

Feller, W. 1968. An introduction to probability theory and its applications: volume I, Volume 3. John Wiley & Sons New York.

[10]

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.

Digital Library

[11]

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

[12]

Jamieson, K., M. Malloy, R. Nowak, and S. Bubeck. 2014. "lilucb: An optimal exploration algorithm for multi-armed bandits". In Conference on Learning Theory, 423--439.

[13]

Jamieson, K., and R. Nowak. 2014. "Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting". In Information Sciences and Systems (CISS), 2014 48th Annual Conference on, 1--6. IEEE.

[14]

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

Digital Library

[15]

Lee, S., and B. L. Nelson. "Bootstrap ranking & selection revisited". In Proceedings of the 2014 Winter Simulation Conference, edited by A. Tolk, S. Y. Diallo, I. O. Ryzhov, L. Yilmaz, S. Buckley, and J. A. Miller, 3857--3868. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers, Inc.

Digital Library

[16]

Lee, S., and B. L. Nelson. 2015. "Computational improvements in bootstrap ranking & selection procedures via multiple comparison with the best". In Proceedings of the 2015 Winter Simulation Conference, edited by L. Yilmaz, W. K. V. Chan, I. Moon, T. M. K. Roeder, C. Macal, and M. D. Rossetti, 3758--3767. Piscataway, New Jersey: Institute of Electrical and Electronics Engineers, Inc.

Digital Library

[17]

Nelson, B. L., and S. Banerjee. 2001. "Selecting a good system: Procedures and inference". IIE Transactions 33 (3): 149--166.

[18]

Ni, E. C., D. F. Ciocan, S. G. Henderson, and S. R. Hunter. 2017. "Efficient ranking and selection in parallel computing environments". Operations Research. To appear. arXiv preprint arXiv:1506.04986.

Digital Library

[19]

Paulson, E. 1964. "A sequential procedure for selecting the population with the largest mean from k normal populations". The Annals of Mathematical Statistics:174--180.

[20]

Rinott, Y. 1978. "On two-stage selection procedures and related probability-inequalities". Communications in Statistics-Theory and methods 7 (8): 799--811.

[21]

Shaked, M., and G. Shanthikumar. 2007. Stochastic orders. Springer Science & Business Media.

Cited By

Zhong YHong LJohansson BJain S(2018)Fully sequential ranking and selection procedures with PAC guaranteeProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320745(1898-1908)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320745
Eckman DHenderson SJohansson BJain S(2018)Guarantees on the probability of good selectionProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320567(351-365)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320567

Recommendations

A Fully Sequential Elimination Procedure for Indifference-Zone Ranking and Selection with Tight Bounds on Probability of Correct Selection

We consider the indifference-zone IZ formulation of the ranking and selection problem with independent normal samples. In this problem, we must use stochastic simulation to select the best among several noisy simulated systems, with a statistical ...
A Fully Sequential Elimination Procedure for Indifference-Zone Ranking and Selection with Tight Bounds on Probability of Correct Selection

<P>We consider the indifference-zone (IZ) formulation of the ranking and selection problem with independent normal samples. In this problem, we must use stochastic simulation to select the best among several noisy simulated systems, with a statistical ...
A Fully Sequential Elimination Procedure for Indifference-Zone Ranking and Selection with Tight Bounds on Probability of Correct Selection

We consider the indifference-zone IZ formulation of the ranking and selection problem with independent normal samples. In this problem, we must use stochastic simulation to select the best among several noisy simulated systems, with a statistical ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WSC '17: Proceedings of the 2017 Winter Simulation Conference

December 2017

4389 pages

ISBN:9781538634271

Sponsors

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

IEEE Press

Publication History

Published: 03 December 2017

Check for updates

Qualifiers

Research-article

Conference

WSC '17

Sponsor:

SIGSIM

WSC '17: Winter Simulation Conference

December 3 - 6, 2017

Nevada, Las Vegas

Acceptance Rates

Overall Acceptance Rate 3,413 of 5,075 submissions, 67%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
24
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhong YHong LJohansson BJain S(2018)Fully sequential ranking and selection procedures with PAC guaranteeProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320745(1898-1908)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320745
Eckman DHenderson SJohansson BJain S(2018)Guarantees on the probability of good selectionProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320567(351-365)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320567

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten