# Finite-time Analysis for the Knowledge-Gradient Policy

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2016.

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

- [On the Finite-Time Performance of the Knowledge Gradient Algorithm](https://mlsanity.com/paper/2206.06847/) (2022)
- [Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identification](https://mlsanity.com/paper/2202.05193/) (2022)

## Abstract (arXiv)

We consider sequential decision problems in which we adaptively choose one of finitely many alternatives and observe a stochastic reward. We offer a new perspective of interpreting Bayesian ranking and selection problems as adaptive stochastic multi-set maximization problems and derive the first finite-time bound of the knowledge-gradient policy for adaptive submodular objective functions. In addition, we introduce the concept of prior-optimality and provide another insight into the performance of the knowledge gradient policy based on the submodular assumption on the value of information. We demonstrate submodularity for the two-alternative case and provide other conditions for more general problems, bringing out the issue and importance of submodularity in learning problems. Empirical experiments are conducted to further illustrate the finite time behavior of the knowledge gradient policy.