Improving the Knowledge Gradient Algorithm
Yang Le Gao Siyang Ho Chin Pang
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 $\epsilon$-good arm identification and
feasible arm identification as two examples. The superior performances of iKG
on these problems are further demonstrated using numerical examples.