Information Collection on a Graph

• 成果类型: Article
• 署名作者: Ryzhov, Ilya O.; Powell, Warren B.
• 署名单位: Princeton University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1100.0873
• 发表日期: 2011
• 页码: 188-201
• 关键词: shortest paths; selection; networks

摘要

We derive a knowledge gradient policy for an optimal learning problem on a graph, in which we use sequential measurements to refine Bayesian estimates of individual edge values in order to learn about the best path. This problem differs from traditional ranking and selection in that the implementation decision (the path we choose) is distinct from the measurement decision (the edge we measure). Our decision rule is easy to compute and performs competitively against other learning policies, including a Monte Carlo adaptation of the knowledge gradient policy for ranking and selection.