Solving limited memory influence diagrams

DOI10.1613/JAIR.3625MaRDI QIDQ2905380zbMATH OpenOpenAlexFDO

Authors D. D. Maua, C. P. De Campos, M. Zaffalon

Publication date 27 August 2012

Published in The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.1754

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Abstract: We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and $10^{64}$ solutions. We show that the problem is NP-hard even if the underlying graph structure of the problem has small treewidth and the variables take on a bounded number of states, but that a fully polynomial time approximation scheme exists for these cases. Moreover, we show that the bound on the number of states is a necessary condition for any efficient approximation scheme.

Recommendations

• Fast local search methods for solving limited memory influence diagrams
• On the complexity of solving polytree-shaped limited memory influence diagrams with binary variables
• Speeding up k-neighborhood local search in limited memory influence diagrams
• Representing and solving decision problems with limited information
• Influence diagrams with memory states: representation and algorithms

Cited in

(22)

• Solving linear-quadratic conditional Gaussian influence diagrams
• An axiomatic framework for influence diagram computation with partially ordered preferences
• Information enhancement -- a tool for approximate representation of optimal strategies from influence diagrams
• Solving trajectory optimization problems by influence diagrams
• A forward-backward Monte Carlo method for solving influence diagrams
• scientific article; zbMATH DE number 1670617 (Why is no real title available?)
• Exploiting model equivalences for solving interactive dynamic influence diagrams
• Speeding up k-neighborhood local search in limited memory influence diagrams
• Influence diagrams with memory states: representation and algorithms
• Representing and solving decision problems with limited information
• Multistage Monte Carlo method for solving influence diagrams using local computation
• An efficient exhaustive anytime sampling algorithm for influence diagrams
• Decomposition of influence diagrams
• On the complexity of solving polytree-shaped limited memory influence diagrams with binary variables
• scientific article; zbMATH DE number 7592245 (Why is no real title available?)
• Strategy Graphs for Influence Diagrams
• On Imperfect Recall in Multi-Agent Influence Diagrams
• Solving decision problems with endogenous uncertainty and conditional information revelation using influence diagrams
• Risk-averse decision strategies for influence diagrams using rooted junction trees
• Equivalences between maximum a posteriori inference in Bayesian networks and maximum expected utility computation in influence diagrams
• Fast local search methods for solving limited memory influence diagrams
• A comparison of two approaches for solving unconstrained influence diagrams

This page was built for publication: Solving limited memory influence diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2905380)