Decision theory made tractable: The value of deliberation, with applications to Markov decision process planning

This dissertation addresses the construction of an operational definition of rationality in the face of computational constraints. Rational decision problem classes are often NP hard, almost certainly eliminating the possibility of any agent ever exhibiting behavior that fully meets the decision-theoretic characterization of rationality.;The most promising approaches extant in the artificial intelligence literature, bounded optimality and metalevel control of computational expenditures, do provide insight into possible agent architectures capable of exhibiting many interesting behaviors that have parallels in human problem-solving. They do not, however, resolve the fundamental difficulty of how rationality can be redefined so as to take into account the costs of its own application. This work argues that the role of rationality is in the evaluation of the agent from an external perspective, rather than in the generation of decisions by the agent, providing a new conception of the role of background or situation in decision making. It clarifies what rational metalevel controllers can accomplish and how they should be designed.;Rational metalevel control allows for problem-solving strategies to be much more responsive to a variety of resource constraints and environmental factors. This work presents metalevel architectures for problem domains modellable as Markov decision processes. They are demonstrated to exhibit the desired responsiveness on some simple examples such as mazes. They cope well with time pressure and random environmental variations. They exhibit behaviors that take account of their previous planning efforts, such as sticking to known solutions when thinking is expensive. These features offer new hope for scaling algorithmic stochastic planning to large domains.;Also discussed are methods of abstracting a decision model by coarse graining its state space, and the loss to decision model quality incurred by such an approximation. This work concludes with a discussion of issues that arise when abstract actions are characterized as plans to plan.