Information collection on a graph

Ilya O. Ryzhov, Warren Buckler Powell

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)188-201
Number of pages14
JournalOperations Research
Issue number1
StatePublished - Jan 2011

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research


  • Bayesian learning
  • Knowledge gradient
  • Optimal learning
  • Ranking and selection
  • Stochastic shortest paths


Dive into the research topics of 'Information collection on a graph'. Together they form a unique fingerprint.

Cite this