A Knowledge Gradient Policy for Sequential Information Collection
by
Peter I. Frazier
Princeton University
Coauthors: Warren B. Powell (Princeton University) Savas Dayanik (Princeton University)

We propose a new algorithm for sequential sampling to determine the best of a discrete set of options with a finite number of observations. The procedure, called the knowledge gradient policy, balances the value of reducing the variance of our estimate of each option against the relative value of each option. The knowledge gradient policy is optimal both when the horizon is a single time period, and in the limit as the horizon extends to infinity. Furthermore, in some special cases, the knowledge gradient policy is optimal regardless of horizon length. We compare the knowledge gradient to other algorithms that have been proposed for collecting information.

Date received: February 18, 2007