Influence Diagrams (IDs) and Partially Observable Markov Decision Processes (POMDPs) are two pillars of decision-making under uncertainty. While IDs excel at representing complex dependencies in structured problems, POMDPs offer powerful algorithms for sequential decision-making. This paper bridges these frameworks by applying POMDP-style "incremental pruning" to ID evaluation, achieving significant scalability gains.
The History-Based Bottleneck
Traditional ID solvers rely on history-based strategies. To solve an ID, one typically finds a mapping from every possible sequence of observations and actions to an optimal next step. However, as the number of stages grows, the number of possible histories explodes exponentially. This "state-space explosion" has historically limited the scalability of IDs in complex, multi-stage scenarios.
Methodology: Belief-Based Evaluation
The proposed approach shifts the paradigm from history to belief states. In POMDPs, a belief state—a probability distribution over hidden variables—serves as a sufficient statistic for the history. The authors introduce new reduction rules for decision and observation nodes that treat unobserved chance nodes as hidden states.
Key methodological innovations include:
- Incremental Pruning: Borrowed from the POMDP community, this technique uses linear programming to discard "dominated" strategies that would never be optimal under any possible belief.
- Strategy Nodes: Instead of exhaustive tables, the algorithm maintains value functions as piecewise-linear and concave (PWLC) functions over the space of possible beliefs.
- Flexible Node Removal: By delaying the removal of unobserved variables, the solver can prune the search space more effectively than traditional ID methods.
Experimental Results
The authors evaluated their algorithm on several benchmarks, most notably the Maze Navigation problem. This problem is notoriously difficult for traditional ID solvers due to its 10 stages and 16 possible observations per stage, resulting in $64^{10}$ possible histories. While traditional methods fail under this complexity, the new belief-based algorithm solved it in less than a minute, producing a compact strategy graph with only 123 action nodes.
In the Mildew Treatment case, the algorithm demonstrated that even when history-based methods are feasible, the belief-based approach provides more compact and interpretable solutions for human experts.
Conclusion and Future Work
By treating IDs through the lens of POMDPs, the authors have developed a robust generalization of existing techniques that is proven to work for any "regular and no-forgetting" ID. While the current implementation relies on heuristics for node removal ordering, future work aims to automate these heuristics to further improve performance on industrial-scale decision problems.
Summary updated