Rational Partial Evaluation of Decision Trees

Michael P. Frank

Introduction

Expert decision-making systems often evaluate decision trees to determine what action has the best expected utility. But sometimes the decision tree implied by the system's model of the domain is intractably large; not only too large to store explicitly, but also too large to evaluate in a reasonable time. System designers typically avoid such difficulties by simplifying the model of the domain so that it will not produce large decision trees, or by abandoning decision trees when they are too large and using some other method to come to a decision.

An alternative, explored in this research, is to partially evaluate the decision tree, using estimates for the utilities of non-leaf nodes. This is analogous to the standard computer game-playing (CGP) technique of partially evaluating the typical intractably-large game trees.

The problem now (as in game tree search) becomes two: estimating utilities of non-leaf nodes, and exploring those parts of the tree that are expected to contribute the most to the quality of the overall decision.

In CGP, the problem of tree-search can be partially handled using cheap and provably-correct algorithms such as Alpha-Beta and Scout. Recently, researchers have gone further with methods that use information about the degree of uncertainty of utility estimates to select those search actions that will most improve the quality of the overall decision. These methods have met with some success. Especially appropriate are the decision-theoretic metareasoning techniques of Russell and Wefald, which search those parts of the tree expected to contribute the most to the utility of the final decision.

Can this sort of decision-theoretic metareasoning be profitably used to control the partial evaluation of large decision trees? That is the primary question that this research will explore.

Citation information

M. Frank, ``Rational Partial Evaluation of Decision Trees.'' Master's thesis proposal, approved March 1993. http://www.ai.mit.edu/~mpf/papers/Frank/Frank93.html. 
@UNPUBLISHED{Frank-93,
	AUTHOR = {Michael P. Frank},
	TITLE = {Rational Partial Evaluation of Decision Trees},
	NOTE = {master's thesis proposal},
	MONTH = mar,
	YEAR = {1993}
	url = {http://www.ai.mit.edu/~mpf/papers/Frank/Frank93.html},
}

Full paper in HTML and DVI format (25K).