research-article

Provably improving the optimal computing budget allocation algorithm

Authors:

Di Wu,

Enlu ZhouAuthors Info & Claims

WSC '18: Proceedings of the 2018 Winter Simulation Conference

Pages 1921 - 1932

Published: 09 December 2018 Publication History

Get Access

Abstract

We boost the performance of the Optimal Computing Budget Allocation (OCBA) algorithm, a widely used and studied algorithm for Ranking and Selection (as known as Best Arm Identification) under a fixed budget. The proposed fully sequential algorithms, OCBA+ and OCBAR, are shown to have better performance both theoretically and numerically. Surprisingly, we reveal that in a two-design setting, a constant initial sample size in a family of OCBA-type algorithms (including the original OCBA) only amounts to a sub-exponential or even polynomial convergence rate of the probability of false selection (PFS). In contrast, our algorithms are guaranteed to converge exponentially fast, as is shown by a finite-sample bound on the PFS.

References

[1]

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

Google Scholar

[2]

Chen, C.-H., D. He, and M. Fu. 2006. "Efficient Dynamic Simulation Allocation in Ordinal Optimization". IEEE Transactions on Automatic Control 51(12):2005--2009.

Crossref

Google Scholar

[3]

Chen, C.-H., and L. H. Lee. 2010. Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. 1st ed. River Edge, NJ, USA: World Scientific Publishing Co., Inc.

Digital Library

Google Scholar

[4]

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

Google Scholar

[5]

Glynn, P., and S. Juneja. 2004. "A Large Deviations Perspective on Ordinal Optimization". In Proceedings of the 2004 Winter Simulation Conference, edited by J. Smith et al., 577--585. Piscataway, New Jersey: IEEE.

Digital Library

Google Scholar

[6]

Glynn, P., and S. Juneja. 2015. "Ordinal Optimization-Empirical Large Deviations Rate Estimators, and Stochastic Multi-Armed Bandits". arXiv preprint arXiv:1507.04564.

Google Scholar

[7]

Henderson, S. G., and B. L. Nelson. 2006. Handbooks in Operations Research and Management Science: Simulation. 1st ed, Volume 13. New York, NY, USA: Elsevier.

Google Scholar

[8]

Jacobovic, R., and O. Zuk. 2017. "On the Asymptotic Efficiency of Selection Procedures for Independent Gaussian Populations". Electronic Journal of Statistics 11(2):5375--5405.

Crossref

Google Scholar

[9]

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

Google Scholar

[10]

Laurent, B., and P. Massart. 2000. "Adaptive Estimation of a Quadratic Functional by Model Selection". Annals of Statistics 28(5):1302--1338.

Crossref

Google Scholar

[11]

Lee, L. H., E. P. Chew, S. Teng, and D. Goldsman. 2004. "Optimal Computing Budget Allocation for Multi-Objective Simulation Models". In Proceedings of the 2004 Winter Simulation Conference, edited by J. Smith et al., 586--594. Piscataway, New Jersey: IEEE.

Digital Library

Google Scholar

[12]

Pasupathy, R., S. R. Hunter, N. A. Pujowidianto, L. H. Lee, and C.-H. Chen. 2015. "Stochastically Constrained Ranking and Selection via SCORE". ACM Transactions on Modeling and Computer Simulation (TOMACS) 25(1):1.

Digital Library

Google Scholar

Cited By

View all

Li YGao S(2021)On the convergence of optimal computing budget allocation algorithmsProceedings of the Winter Simulation Conference10.5555/3522802.3523026(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3523026
Zhang GPeng YZhang JZhou E(2021)Dynamic sampling policy for subset selectionProceedings of the Winter Simulation Conference10.5555/3522802.3522957(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522957

Recommendations

Provably improving the optimal computing budget allocation algorithm
WSC '18: Proceedings of the 2018 Winter Simulation Conference

We boost the performance of the Optimal Computing Budget Allocation (OCBA) algorithm, a widely used and studied algorithm for Ranking and Selection (as known as Best Arm Identification) under a fixed budget. The proposed fully sequential algorithms, ...
Optimal Resource Allocation on Grid Computing Using a Quantum Chromosomes Genetic Algorithm
DMAMH '07: Proceedings of the Second Workshop on Digital Media and its Application in Museum & Heritage

Grid computing system is different from conventional distributed computing systems by its focus on large-scale resource sharing and open architecture for services. The global grid technologies and the Globus Toolkit in particular, are evolving toward an ...
A hybrid search algorithm with optimal computing budget allocation for resource allocation problem
WSC '13: Proceedings of the 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World

In this paper, a simulation-based optimization approach, named NH_OCBA, for a typical resource allocation problem is presented. The hybrid algorithm based on neighborhood algorithm is applied to explore toward optimal direction in design space. For ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WSC '18: Proceedings of the 2018 Winter Simulation Conference

December 2018

4298 pages

ISBN:978153866570

General Chair:
Björn Johansson
Chalmers University of Technology
,
Program Chair:
Sanjay Jain
George Washington University

Publisher

IEEE Press

Publication History

Published: 09 December 2018

Check for updates

Qualifiers

Research-article

Conference

WSC '18

Sponsor:

SIGSIM

WSC '18: Winter Simulation Conference

December 9 - 12, 2018

Gothenburg, Sweden

Acceptance Rates

WSC '18 Paper Acceptance Rate 183 of 260 submissions, 70%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
31
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li YGao S(2021)On the convergence of optimal computing budget allocation algorithmsProceedings of the Winter Simulation Conference10.5555/3522802.3523026(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3523026
Zhang GPeng YZhang JZhou E(2021)Dynamic sampling policy for subset selectionProceedings of the Winter Simulation Conference10.5555/3522802.3522957(1-12)Online publication date: 13-Dec-2021
https://dl.acm.org/doi/10.5555/3522802.3522957

View Options

Login options

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

Cited By

Recommendations

Provably improving the optimal computing budget allocation algorithm

Optimal Resource Allocation on Grid Computing Using a Quantum Chromosomes Genetic Algorithm

A hybrid search algorithm with optimal computing budget allocation for resource allocation problem