A New Bounding Scheme for Influence Diagrams

Authors

  • Radu Marinescu IBM Research Europe
  • Junkyu Lee University of California Irvine
  • Rina Dechter University of California Irvine

DOI:

https://doi.org/10.1609/aaai.v35i13.17443

Keywords:

Graphical Models, Sequential Decision Making

Abstract

Influence diagrams provide a modeling and inference framework for sequential decision problems, representing the probabilistic knowledge by a Bayesian network and the preferences of an agent by utility functions over the random variables and decision variables. Computing the maximum expected utility (MEU) and the optimizing policy is exponential in the constrained induced width and therefore is notoriously difficult for larger models. In this paper, we develop a new bounding scheme for MEU that applies partitioning based approximations on top of the decomposition scheme called a multi-operator cluster DAG for influence diagrams that is more sensitive to the underlying structure of the model than the classical join-tree decomposition of influence diagrams. Our bounding scheme utilizes a cost-shifting mechanism to tighten the bound further. We demonstrate the effectiveness of the proposed scheme on various hard benchmarks.

Downloads

Published

2021-05-18

How to Cite

Marinescu, R., Lee, J., & Dechter, R. (2021). A New Bounding Scheme for Influence Diagrams. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 12158-12165. https://doi.org/10.1609/aaai.v35i13.17443

Issue

Section

AAAI Technical Track on Reasoning under Uncertainty