A computational theory of decision networks

This paper is about how to represent and solve decision problems in Bayesian decision theory (e.g. [6]). A general representation, called decision networks, is proposed based on influence diagrams [10]. This new representation incorporates the idea, from Markov decision processes (e.g. [5]), that a decision may be conditionally independent of certain pieces of available information. It also allows multiple cooperative agents and facilitates the exploitation of separability in the utility function. Decision networks inherit the advantages of both influence diagrams and Markov decision processes, which makes them a better representation framework for decision analysis, planning under uncertainty, and medical diagnosis and treatment. Influence diagrams are stepwise-solvable, in the sense that they can be evaluated by considering one decision at a time. However, the evaluation of a decision network requires, in general, simultaneous consideration of all the decisions. The theme of this paper is to seek the weakest condition under which decision networks are stepwise-solvable and to seek the best algorithms for evaluating stepwise-solvable decision networks. A concept of decomposability is introduced for decision networks, and it is shown that when a decision network is decomposable, a divide-and-conquer strategy can be utilized to aid its evaluation. In particular, when a decision network is stepwise-decomposable, it can be evaluated not only by considering one decision at a time, but also by considering one portion of the network at a time.