# Improving the Knowledge Gradient Algorithm

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 30 references that are in the map.
- First posted on arXiv 27 Oct 2023.

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

- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Offline A/B testing for Recommender Systems](https://mlsanity.com/paper/1801.07030/) (2018)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms](https://mlsanity.com/paper/2211.14722/) (2022)
- [On the Finite-Time Performance of the Knowledge Gradient Algorithm](https://mlsanity.com/paper/2206.06847/) (2022)

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

- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [Stochastically Constrained Best Arm Identification with Thompson Sampling](https://mlsanity.com/paper/2501.03877/) (2025)

## Abstract (arXiv)

The knowledge gradient (KG) algorithm is a popular policy for the best arm identification (BAI) problem. It is built on the simple idea of always choosing the measurement that yields the greatest expected one-step improvement in the estimate of the best mean of the arms. In this research, we show that this policy has limitations, causing the algorithm not asymptotically optimal. We next provide a remedy for it, by following the manner of one-step look ahead of KG, but instead choosing the measurement that yields the greatest one-step improvement in the probability of selecting the best arm. The new policy is called improved knowledge gradient (iKG). iKG can be shown to be asymptotically optimal. In addition, we show that compared to KG, it is easier to extend iKG to variant problems of BAI, with the ε-good arm identification and feasible arm identification as two examples. The superior performances of iKG on these problems are further demonstrated using numerical examples.