TY - GEN
T1 - On the Convergence of Optimal Computing Budget Allocation Algorithms
AU - Li, Yanwen
AU - Gao, Siyang
PY - 2021/12
Y1 - 2021/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85123486607&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85123486607&origin=recordpage
U2 - 10.1109/WSC52266.2021.9715371
DO - 10.1109/WSC52266.2021.9715371
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 978-1-6654-3312-9
T3 - Proceedings - Winter Simulation Conference
BT - 2021 Winter Simulation Conference (WSC)
PB - IEEE
T2 - 2021 Winter Simulation Conference (WSC 2021)
Y2 - 13 December 2021 through 15 December 2021
ER -