Submodel Decomposition Bounds for Influence Diagrams

Abstract

An influence diagram represents a sequential decision-making problem under uncertainty. The standard inference task in influence diagrams is to compute the maximum expected utility, which is the most challenging task in graphical models. In this paper, we present a submodel decomposition scheme that identifies a tree of single-stage decision problems, called submodels, by exploiting relevance relationships and characterize its inference complexity by the maximum tree-width of individual submodels. We subsequently design an upper bounding scheme over a submodel tree by applying variational upper bounds for marginal MAP inference on each submodel. The scheme is implemented by a hierarchical message passing algorithm that propagates upper bounds of conditional expected utility values over the submodel tree. We demonstrate that the proposed approach provides tighter upper bounds compared with state-of-the-art bounding schemes on several benchmarks.