Open Collections

A computational theory of decision networks

University of British Columbia

This thesis is about how to represent and solve decision problems in Bayesian decision the ory (e.g. Fishburn 1988). A general representation named decision networks is proposed based on influence diagrams (Howard and Matheson 1984). This new representation incorporates the idea, from Markov decision processes (e.g. Puterman 1990, Denardo 1982), 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. Both influence diagrams and finite stage Markov decision processes 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 consider ation of all the decisions. The theme of this thesis is to seek the weakest graph-theoretic condition under which decision networks are guaranteed to be 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. It is also shown that stepwise-decomposability is the weakest graphical condition that guarantees stepwise-solvability. Given a decision network, there are often nodes and arcs that can harmlessly removed. An algorithm is presented that is able to find and prune all graphically identifiable removable nodes and arcs. Finally, the relationship between stepwise-decomposable decision networks (SDDN‘s) and Markov decision process is investigated, which results in a two-stage approach for evaluating SDDN’s. This approach enables one to make use of the asymmetric nature of decision problems, facilitates parallel computation, and gives rises to an incremental way of computing the value of perfect information.

Thesis/Dissertation

application/pdf

2009-04-08

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/6932

Computer Science

University of British Columbia

UBCV

DSpace