Solving Limited Memory Influence Diagrams
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 1064 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low treewidth and the variables take on a bounded number of states, and that they admit no provably good approximation if variables can take on an arbitrary number of states.
Cite
Text
Mauá et al. "Solving Limited Memory Influence Diagrams." Journal of Artificial Intelligence Research, 2012. doi:10.1613/JAIR.3625Markdown
[Mauá et al. "Solving Limited Memory Influence Diagrams." Journal of Artificial Intelligence Research, 2012.](https://mlanthology.org/jair/2012/maua2012jair-solving/) doi:10.1613/JAIR.3625BibTeX
@article{maua2012jair-solving,
title = {{Solving Limited Memory Influence Diagrams}},
author = {Mauá, Denis Deratani and de Campos, Cassio P. and Zaffalon, Marco},
journal = {Journal of Artificial Intelligence Research},
year = {2012},
pages = {97-140},
doi = {10.1613/JAIR.3625},
volume = {44},
url = {https://mlanthology.org/jair/2012/maua2012jair-solving/}
}