On the Convergence of Optimal Computing Budget Allocation Algorithms

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.