This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Frazier, P. Articles by Dayanik, S. Search for Related Content

The Knowledge-Gradient Policy for Correlated Normal Beliefs

Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
Department of Operations Research and Financial Engineering, Princeton University, Princeton, New Jersey 08544
pfrazier{at}princeton.edu
powell{at}princeton.edu
sdayanik{at}princeton.edu

We consider a Bayesian ranking and selection problem with independent normal rewards and a correlated multivariate normal belief on the mean values of these rewards. Because this formulation of the ranking and selection problem models dependence between alternatives' mean values, algorithms may use this dependence to perform efficiently even when the number of alternatives is very large. We propose a fully sequential sampling policy called the knowledge-gradient policy, which is provably optimal in some special cases and has bounded suboptimality in all others. We then demonstrate how this policy may be applied to efficiently maximize a continuous function on a continuous domain while constrained to a fixed number of noisy measurements.

Key words: simulation; design of experiments; decision analysis; sequential; statistics; Bayesian
History: received January 2008; revised October 2008; accepted November 2008.