Synthesis of strategies in influence diagrams

Influence diagrams (IDs) are a powerful tool for representing and solving decision problems un- der uncertainty. The objective of evaluating an ID is to compute the expected utility and an opti- mal strategy, which consists of a policy for each decision. Every policy is usually represented as a table containing a column for each decision sce- nario, i.e., for each configuration of the variables on which it depends. The no-forgetting assump- tion, which implies that the decision maker al- ways remembers all past observations and de- cisions, makes the policies grow exponentially with the number of variables in the ID. For hu- man experts it is very difficult to understand the strategy contained in huge policy tables, not only for their size, but also because the vast major- ity of columns correspond to suboptimal or im- possible scenarios and are hence irrelevant. This makes it difficult to extract the rules of action, to debug the model, and to convince the experts that the recommendations of the ID are reasonable. In this paper, we propose a method that presents the strategy in the form of a compact tree. It has been implemented in OpenMarkov, an open- source software tool for probabilistic graphical models. This facility was essential when eval- uating an influence diagram for the mediastinal staging of non-small cell lung cancer; the op- timal strategy, whose biggest policy table con- tained more than 15,000 columns, was synthe- sized into a tree of only 5 leaves.