Submodel Decomposition Bounds for Influence Diagrams

Authors

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

DOI:

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

Keywords:

Graphical Models, Sequential Decision Making, Planning under Uncertainty, Planning with Markov Models (MDPs, POMDPs)

Abstract

Influence diagrams (IDs) are graphical models for representing and reasoning with sequential decision-making problems under uncertainty. Limited memory influence diagrams (LIMIDs) model a decision-maker (DM) who forgets the history in the course of making a sequence of decisions. The standard inference task in IDs and LIMIDs is to compute the maximum expected utility (MEU), which is one of the most challenging tasks in graphical models. We present a model decomposition framework in both IDs and LIMIDs, which we call submodel decomposition that generates a tree of single-stage decision problems through a tree clustering scheme. We also develop a valuation algebra over the submodels that leads to a hierarchical message passing algorithm that propagates conditional expected utility functions over a submodel-tree as external messages. We show that the overall complexity is bounded by the maximum tree-width over the submodels, common in graphical model algorithms. Finally, we present a new method for computing upper bounds over a submodel-tree by first exponentiating the utility functions yielding a standard probabilistic graphical model as an upper bound and then applying standard variational upper bounds for the marginal MAP inference, yielding tighter upper bounds compared with state-of-the-art bounding schemes for the MEU task.

Downloads

Published

2021-05-18

How to Cite

Lee, J., Marinescu, R., & Dechter, R. (2021). Submodel Decomposition Bounds for Influence Diagrams. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 12147-12157. https://doi.org/10.1609/aaai.v35i13.17442

Issue

Section

AAAI Technical Track on Reasoning under Uncertainty