# Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms

arXiv: https://arxiv.org/abs/2211.14722 · HTML: https://mlsanity.com/paper/2211.14722/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 53 references that are in the map.
- First posted on arXiv 27 Nov 2022.

## Builds on (most cited first, 5 of 5)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [On the Finite-Time Performance of the Knowledge Gradient Algorithm](https://mlsanity.com/paper/2206.06847/) (2022)
- [An Optimal Computing Budget Allocation Tree Policy for Monte Carlo Tree Search](https://mlsanity.com/paper/2009.12407/) (2020)

## Built on by (most cited first, 5 of 5)

- [Improving the Knowledge Gradient Algorithm](https://mlsanity.com/paper/2310.17901/) (2023)
- [Series Expansion of Probability of Correct Selection for Improved Finite Budget Allocation in Ranking and Selection](https://mlsanity.com/paper/2411.10695/) (2024)
- [New Additive OCBA Procedures for Robust Ranking and Selection](https://mlsanity.com/paper/2412.06020/) (2024)
- [Stochastically Constrained Best Arm Identification with Thompson Sampling](https://mlsanity.com/paper/2501.03877/) (2025)
- [Sequential Additivity in Distributionally Robust Ranking and Selection](https://mlsanity.com/paper/2509.06147/) (2025)

## Abstract (arXiv)

Ordinal optimization (OO) is a widely-studied technique for optimizing discrete-event dynamic systems (DEDS). It evaluates the performance of the system designs in a finite set by sampling and aims to correctly make ordinal comparison of the designs. A well-known method in OO is the optimal computing budget allocation (OCBA). It builds the optimality conditions for the number of samples allocated to each design, and the sample allocation that satisfies the optimality conditions is shown to asymptotically maximize the probability of correct selection for the best design. In this paper, we investigate two popular OCBA algorithms. With known variances for samples of each design, we characterize their convergence rates with respect to different performance measures. We first demonstrate that the two OCBA algorithms achieve the optimal convergence rate under measures of probability of correct selection and expected opportunity cost. It fills the void of convergence analysis for OCBA algorithms. Next, we extend our analysis to the measure of cumulative regret, a main measure studied in the field of machine learning. We show that with minor modification, the two OCBA algorithms can reach the optimal convergence rate under cumulative regret. It indicates the potential of broader use of algorithms designed based on the OCBA optimality conditions.