On the Convergence of Optimal Computing Budget Allocation Algorithms

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

View graph of relations

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publication2021 Winter Simulation Conference (WSC)
PublisherIEEE
Number of pages12
ISBN (electronic)9781665433112
ISBN (print)978-1-6654-3312-9
Publication statusPublished - Dec 2021

Publication series

NameProceedings - Winter Simulation Conference
ISSN (Print)0891-7736
ISSN (electronic)1558-4305

Conference

Title2021 Winter Simulation Conference (WSC 2021)
LocationJW Marriott Desert Ridge (Face-to-face & Virtual)
PlaceUnited States
CityPhoenix
Period13 - 15 December 2021

Abstract

This paper considers a well-known ranking and selection (RS) framework, called optimal computing budget allocation (OCBA). This framework includes a set of equations that optimally determine the number of samples allocated to each design in a finite design set. Sample allocations that satisfy these equations have been shown to be the asymptotic optimizer of the probability of correct selection (PCS) for the best design and the expected opportunity cost (EOC) if false selection occurs. In this paper, we analyze two popular OCBA algorithms and study their convergence rates, assuming known variances for samples of each design. It fills the gap of convergence analysis for algorithms that are developed based on the OCBA optimality equations. In addition, we propose modifications of the OCBA algorithms for cumulative regret, an objective commonly studied in machine learning, and derive their convergence rates. Last, the convergence behaviors of these algorithms are demonstrated using numerical examples.

Citation Format(s)

On the Convergence of Optimal Computing Budget Allocation Algorithms. / Li, Yanwen; Gao, Siyang.
2021 Winter Simulation Conference (WSC). IEEE, 2021. (Proceedings - Winter Simulation Conference).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review