Evaluating influence diagrams with decision circuits
This work addresses a computational bottleneck for researchers and practitioners in decision analysis and probabilistic modeling, offering an incremental improvement over prior methods.
The paper tackles the intractability of exact solutions for evaluating influence diagrams by introducing decision circuits, which exploit local structure in decision problems to improve performance, building on existing arithmetic circuit methods for Bayesian belief networks.
Although a number of related algorithms have been developed to evaluate influence diagrams, exploiting the conditional independence in the diagram, the exact solution has remained intractable for many important problems. In this paper we introduce decision circuits as a means to exploit the local structure usually found in decision problems and to improve the performance of influence diagram analysis. This work builds on the probabilistic inference algorithms using arithmetic circuits to represent Bayesian belief networks [Darwiche, 2003]. Once compiled, these arithmetic circuits efficiently evaluate probabilistic queries on the belief network, and methods have been developed to exploit both the global and local structure of the network. We show that decision circuits can be constructed in a similar fashion and promise similar benefits.