Open Collections

Flexible policy construction by information refinement

University of British Columbia

Decision making under uncertainty addresses the problem of deciding which actions to take in the world, when there is uncertainty about the state of the world, and uncertainty as to the outcome of these actions. A rational approach to making good choices is the principle of maximum expected utility: the decision maker should act so as to maximize the expected benefits of the possible outcomes. The "textbook" approaches to decision analysis typically make the assumption that the computational costs involved are negligible. This assumption is not always appropriate. When computational costs cannot be ignored, a decision maker must be able to choose a trade-off between computational costs and object value. This thesis proposes an approach to decision making called information refinement. It is an iterative, heuristic process which a decision maker can use to build a policy. We present three algorithms which use information refinement to construct policies for decision problems expressed as influence diagrams. The algorithms are intended for situations in which computational costs are not negligible, and are designed to give the decision maker control of the trade-off involved in the decision making process. The first algorithm is an anytime algorithm for single stage decision problems. It constructs a policy by increasing the use of information available to the decision maker. The second algorithm applies the single stage algorithm to multistage decision problems using a fixed allocation of computational resources. The third algorithm is an anytime algorithm for multi-stage decision problems. We show empirically that these algorithms are able to make decisions with high expected value with small computational costs. We provide empirically evidence for our claims, by applying our algorithms to a large number of large decision problems.

Thesis/Dissertation

application/pdf

2009-06-19

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/9484

Computer Science

University of British Columbia

UBCV

DSpace