Systems with limited rationality have finite architectures, time, and knowledge. The authors contrast this approach with more classical theories of computation, which tend to ignore these restrictions. In particular, the authors seek to develop a metalevel reasoning methodology that can compute the value of a computation for solving a particular problem. Metareasoning is thinking about what to think about. This approach, combined with compilation of reasoning sequences or decisions and goal-directed search, is contrasted with the much less efficient local search methods normally used. The authors describe in some detail an experimental system they constructed, and make both theoretical and empirical comparisons with other systems.

The first chapter considers bounded rationality in the context of intelligent agents. Traditional artificial intelligence has defined practical reasoning as finding an action that will achieve a specified goal. A more flexible alternative is the decision theoretic approach of defining the “right thing to do” as the action that maximizes expected payoff. The authors argue that both approaches deal with the action finally taken rather than with the whole process of deliberating and acting. This problem is particularly acute when computing with the finite resources that, unfortunately, are all that is currently available. This book investigates architectures and algorithms particularly designed for machines with less than infinite speed and knowledge.

The second chapter deals with metareasoning architectures. An interesting aspect of bounded rationality is that computations on a decision node may often terminate with unpondered pathways. The architectures are considered by constructing a taxonomy composed of six basic kinds of knowledge, four basic execution architectures, and several kinds of compilation processes. An example of a basic kind of knowledge is condition-action rules--the basic IF-THEN production rules. Combinations of the six basic types of knowledge then lead to the four execution architectures: decision theoretic, goal-based, action-utility, and production systems. Finally, knowledge compilation is used as an optimization method for omitting intermediate computations. Two examples of knowledge compilation are explanation-based learning, which is used to compress chains of inferences about the state of the world, and macro-operator formation, which collapses inferences about the results of sequences of actions. The second chapter concludes with a comparison of three systems: TEIRESIAS, MRS, and SOAR.

Chapters 3 through 6 contain the meat of the book and are moderately heavy going. In chapter 3, the authors derive a series of formulae to turn the principles of rational metareasoning into concrete practice. Chapters 4 through 6 are devoted to applying these formulae to specific applications. In these application chapters, the initial mathematical derivations are followed by pseudo-English algorithms with detailed discussions. The examples conclude with experimental comparisons to competing algorithms. This material should provide sufficient information to allow another researcher to begin the study of rational metareasoning.

The third chapter expounds two basic principles: computations are to be treated as actions, and are therefore to be selected on the basis of their expected utilities; and the utility of a computation is derived from its expected effects. Computations are only valuable to the extent that they reveal one action to be superior to another. Sometimes the cost of delaying a decision by computing further alternatives outweighs any expected gain.

Chapter 4 applies these formulae to game playing, particularly Othello. Algorithms are developed for this game, and the results are compared to more traditional approaches such as min-max and alpha-beta. The comparisons begin with a theoretical approach but also include empirical studies. Finally, the authors discuss initial work in applying rational metareasoning to chess and backgammon. Chapter 5 addresses problem-solving search. The approach parallels that used in the previous chapter. The final application area, considered in chapter 6, is learning the value of a computation. Learning is considered an essential attribute of bounded rational agents because the designer cannot be expected to have an exact model of the environment. This chapter lacks the extensive algorithm development found in chapters 4 and5.

Chapter 7, the last chapter, briefly considers other areas in which bounded rationality might be fruitfully applied, and addresses problem solving and planning systems. An explication of Bayesian search and planning serves as a backdrop for a description of a system under development by the authors, which incorporates a Bayesian network inference engine, a graph elaboration generator, and a metalevel control algorithm. A second future application considered in some detail is real-time systems. The time constraints involved in real-time systems make them a natural match with the time costs used as part of the constraints in bounded rationality. The bulk of this discussion concerns the development of “anytime” systems--systems where the decision quality is a function of the time allocated to computation. This text assumes a strong general background in artificial intelligence research. It develops the arguments, mathematics, and algorithms for applying bounded rationality to a broad class of problems with an enthusiasm and occasional humor that are refreshing.