# Computation and Action Under Bounded Resources

** Click here to access pdf file (319 pages).
**

** Click here to access Postscript file (319 pages).**

Also listed as *Technical Report KSL-90-76*, Computer Science Department, Stanford University, December 1990.

### Abstract:

We define and implement a model of rational action for automated
reasoning systems that makes use of flexible approximation methods and
inexpensive decision-theoretic procedures to determine how best to
solve a problem under bounded computational resources. The model
provides metareasoning techniques which enable a reasoning system to
balance the costs of increased delays with the benefits of better
results in a decision context. The decision-theoretic metareasoning
techniques presented can be applied to a variety of computational
tasks. We focus on the use of inexpensive decision procedures to
control complex decision-theoretic reasoning at the base level. The
approach extends traditional decision analyses to autoepistemic models
that represent knowledge about problem solving, in addition to
knowledge about distinctions and relationships in the world. We found
that it can be valuable to allocate a portion of costly reasoning
resources to metalevel deliberation about the best way to use
additional resources to solve a decision problem. After reviewing
principles for applying multiattribute utility theory to the control
of computational procedures, we describe how these principles can be
used to control probabilistic reasoning. In particular, we shall
examine techniques for controlling, at run time, the tradeoff between
the complexity of detailed, accurate analyses and the tractability of
less complex, yet less accurate probabilistic inference. Then we
review the architecture and functionality of a system named Protos
that embodies the principles for using complex probabilistic models to
make high-stakes decisions under time pressure. We shall study the
behavior of Protos on high-stakes decision problems in
medicine. Finally, we move beyond our focus on time constraints to
consider the constraints on decision-theoretic reasoning posed by the
cognitive limitations of people seeking insight from automated
decision systems.
** Keywords:** Bounded optimality, principles of bounded optimal systems, action under scarce resources, rationality, decision-theoretic reasoning, Bayesian networks, probabilistic inference, bounded rationality.

### Some Background

In the dissertation work, I explored foundations of flexibility of
computation, probing the multiattribute utility of partial results and
the trajectories through a multiattribute space that algorithms
generate in return for resources.

I examined a variety of algorithms from the perspective of
maximizing the expected utility of computation under resource
constraints. Here is a figure displaying data generated by
Protos/Algo as it probed the value of partial results generated by
alternative sorting algorithms. A partial sort is depicted by a set
of points in a two dimensional represenation where one axis is the key
of records and the other are the locations of the records. A diagonal
line represents a completely sorted file.

Here is another depiction of the value of partial results with
flexible computation, now exploring the traveling salesperson problem
(TSP), an NP-Hard task. We show the performance over time of a two-opt
approximation. In the context of a loss function, representing the
cost of waiting for an increasingly better tour, we compute a net
value, the curve appearing in the middle of the graph. This work was done with Adrian Klein.

The primary focus of the dissertation is the exploration of
rationality under resource constraints. The Protos system was built
to explore the control of decision-theoretic inference in
time-critical contexts. The system continues to compute an
approximation for the expected value of computation (EVC) and decides
whether to continue to compute or to act in the world. Here is some
output from Protos after the system tackled a time-pressured medical
decision. The upper left-hand corner displays the tightening of
bounds over a probability needed to solve a decision problem. The
larger graph displays several pieces of information about the state of
the problem when the system decided to act in the world rather than
continue to refine its result.

## Doctoral committee

Ron Howard, EES (Chair)

George Dantzig, OR

Ted Shortliffe, AI/Medicine and Computer Science

Patrick Suppes, Philosophy (Orals)