About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
AAAI 2021
Conference paper
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.