An efficient sampling algorithm for influence diagrams

Authors:

Daniel Garcia-Sanchez and Marek J. Druzdzel
Decision Systems Laboratory
School of Information Sciences
and Intelligent Systems Program
University of Pittsburgh
135 North Bellefield Avenue
Pittsburgh, PA 15260, U.S.A.
e-mail: marek@sis.pitt.edu

Abstract:

We describe an efficient sampling algorithm for solving influence diagrams that achieves its efficiency by reusing samples for each of the decision strategies. Our algorithm is exhaustive in the sense of computing the expected utility of each of the possible decision strategies. We show how by a parallel evaluation of all strategies we not only save a significant amount of computation but also produce better quality anytime behavior.