# On the Finite-Time Performance of the Knowledge Gradient Algorithm

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 14 Jun 2022.

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

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [The Parallel Knowledge Gradient Method for Batch Bayesian Optimization](https://mlsanity.com/paper/1606.04414/) (2016)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Bayesian Optimization of Risk Measures](https://mlsanity.com/paper/2007.05554/) (2020)
- [Knowledge Gradient for Selection with Covariates: Consistency and Computation](https://mlsanity.com/paper/1906.05098/) (2019)
- [Finite-time Analysis for the Knowledge-Gradient Policy](https://mlsanity.com/paper/1606.04624/) (2016)

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

- [Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms](https://mlsanity.com/paper/2211.14722/) (2022)
- [Improving the Knowledge Gradient Algorithm](https://mlsanity.com/paper/2310.17901/) (2023)
- [Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization](https://mlsanity.com/paper/2606.00956/) (2026)

## Abstract (arXiv)

The knowledge gradient (KG) algorithm is a popular and effective algorithm for the best arm identification (BAI) problem. Due to the complex calculation of KG, theoretical analysis of this algorithm is difficult, and existing results are mostly about the asymptotic performance of it, e.g., consistency, asymptotic sample allocation, etc. In this research, we present new theoretical results about the finite-time performance of the KG algorithm. Under independent and normally distributed rewards, we derive bounds for the sample allocation of the algorithm. With these bounds, existing asymptotic results become simple corollaries. Furthermore, we derive upper and lower bounds for the probability of error and simple regret of the algorithm, and show the performance of the algorithm for the multi-armed bandit (MAB) problem. These developments not only extend the existing analysis of the KG algorithm, but can also be used to analyze other improvement-based algorithms. Last, we use numerical experiments to compare the bounds we derive and the performance of the KG algorithm.