|Publications & Technical Reports
Submodel Decomposition Bounds for Influence DiagramsJunkyu Lee, Radu Marinescu, and Rina Dechter.
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. It presents a tree clustering scheme that identifies a tree of single-stage decision problems. We develop a valuation algebra over the submodels leading to a hierarchical message passing algorithm that propagates conditional expected utility functions over the submodel-tree as external messages while it uses internal message passing to generate those submodel external messages. The scheme’s complexity is bounded by the maximum tree-width over the submodels, as is common in graphical model algorithms. Finally, we present a new method for computing upper bounds over a submodel-tree, by first exponen- tiating 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 bounds to the MEU that are tighter compared with state-of-the-art bounding schemes.