Solving Multistage Influence Diagrams using Branch-and-Bound Search
This addresses a computational bottleneck in decision-making under uncertainty for researchers and practitioners, though it is incremental as it builds on prior theoretical work.
The paper tackled the problem of efficiently solving multistage influence diagrams by developing a practical implementation of depth-first branch-and-bound search with effective bounds, resulting in outperforming existing methods for multiple stages.
A branch-and-bound approach to solving influ- ence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated - apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementa- tion of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.