A Knowledge-Gradient Policy for Sequential Information Collection

By Peter I. Frazier, Warrren B Powell, Savas Dayanik. SIAM Journal of Control and Optimization, 2008

547 citations recorded by the source corpus.

In a sequential Bayesian ranking and selection problem with independent normal populations and common known variance, we study a previously introduced measurement policy which we refer to as the knowledge-gradient policy. This policy myopically maximizes the expected increment in the value of information in each time period, where the value is measured according to the terminal utility function. We show that 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. We show furthermore that, in some special cases, the knowledge-gradient policy is optimal regardless of the length of any given fixed total sampling horizon. We bound the knowledge-gradient policy's suboptimality in the remaining cases, and show through simulations that it performs competitively with or significantly better than other policies.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/c958734949eaeac84bb554bb542fb053ea0dd087

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistics and Probability

Citations in the corpus

Multi-Information Source Optimization (2016, methodology): “This acquisition function generalizes and parallelizes previously proposed knowledgegradient methods for single-IS Bayesian optimization [7, 8, 28, 26, 37] to MISO.”
A Tutorial on Thompson Sampling (2017, background): “The knowledge gradient [61, 62] and information-directed sampling [50] are alternative algorithms that attempt to reason more carefully about the value of information acquired by sampling an action.”
Navigating the protein fitness landscape with Gaussian processes (2012, background): “A number of algorithms attempt to deal with the exploitation – exploration dilemma (26, 27).”
Simple Bayesian Algorithms for Best Arm Identification (2016, background): “They formulate simpler problems that can be solved exactly – like a problem where only a single measurement can be gathered [Gupta and Miescke, 1996, Frazier et al., 2008, Chick et al., 2010] or a continuous-time problem with only two alternatives [Chick and Frazier, 2012] – and then extend those…”
Sequential design of computer experiments for the estimation of a probability of failure (2010, background): “When considered in terms of utility rather than cost, such strategies have also been called knowledge gradient policies by Frazier et al. (2008). Given a sequence of estimators (α̂n)n≥1, a direct application of the above principle using the quadratic loss function yields the sampling criterion Jn(x)”
Monte Carlo sampling-based methods for stochastic optimization (2014, unknown): “[77, 78], Huang et al.”
BoTorch: Programmable Bayesian Optimization in PyTorch (2019, methodology): “Popular look-ahead acquisition functions include the Knowledge Gradient (KG) (Frazier et al., 2008), Predictive Entropy Search (Henrández-Lobato et al.”
Learning to Optimize via Information-Directed Sampling (2014, methodology): “ononthequalityofthedecision madebyagreedyalgorithm,whichsimplyselectstheactionwithhighestposteriorexpectedreward. This measure was proposed by Mockus et al. [40] and studied further by Frazier et al. [23] and 3 Ryzhov et al. [48]. KG seems natural since it explicitly seeks information that improves ”
Recent Advances in Bayesian Optimization (2022, background): “An idea closely related to EI is Knowledge Gradient (KG) [74], maximizing the expected incremental value of a measurement; however, it does not depend on the optimum obtained so far.”
A Tutorial on Bayesian Optimization (2018, methodology): “(2009) for GP regression over discrete A, building on earlier work (Frazier et al., 2008) that proposed the same algorithm for Bayesian ranking and selection (Chick and Inoue, 2001) with an independent prior.”
A unified framework for stochastic optimization (2019, methodology): “Beyond the brief introducion we provided in Section 2.6 , we refer the reader to these refernces as a starting point. There is an entire literature that focuses on settings where x t is vector, and the contribution function C(S t , x t ) = c t x t , where the onstraints X t are a set of linear equat”
The Knowledge-Gradient Policy for Correlated Normal Beliefs (2009, unknown): “The independent normal means case was analyzed further by Frazier et al. (2008) and extended to the unknown variance case by Chick et al. (2007).”
An Analytics Approach to Designing Combination Chemotherapy Regimens for Cancer (2016, methodology): “Another avenue of future work is to use more sophisticated techniques such as the knowledge gradient algorithm (Frazier et al. 2008) or Q-learning (Dearden et al. 1998) when exploring the space of combination chemotherapy regimens using phase II studies.”