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.
展开▼
