The Complexity of Approximately Solving Influence Diagrams
This addresses the computational complexity of decision-making under uncertainty for researchers in AI and operations research, but it is incremental as it builds on known hardness results with new bounded-case insights.
The paper tackles the problem of approximately solving influence diagrams, which are hard to solve in general, and shows that when tree-width and variable cardinality are bounded, the problem admits a fully polynomial-time approximation scheme.
Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the tree-width and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.