Adaptive Learning of Decision-Theoretic Search Control Knowledge

Abstract

An important feature of autonomous agents with bounded rationality, especially in a context of time pressure, is the ability to exercise rational control over their own reasoning processes. In previous work (Russell and Wefald, 1988, 1989; Wefald and Russell, 1989a, 1989b), we have shown how it is possible to control heuristic search in many domains by explicitly estimating the expected value of possible computations. The expected value calculation employs stored numerical estimates of the probability distribution of the error in the heuristic evaluation function for various classes of situations, which can often be learned empirically at design time by random sampling of the state space. However, in some domains, such as robot navigation on Mars, such sampling may be expensive, even at design time. Moreover, because the use of decision-theoretic control leads to an improvement in system performance, this very change in behavior can make the error distributions incorrect, because they no longer model the behavior of the improved system. A solution to both concerns is to learn the error distributions incrementally, based on the system's own problem-solving experience. As the system gradually adapts its problem-solving behavior to take account of the new knowledge, which is then updated to reflect the new behavior, a classical feedback loop comes into play. Such an agent should be able to adaptively converge on a state in which it would have correct knowledge about its own problem-solving behavior, thus allowing it to exercise rational control over its problem-solving searches. The learning obtained in this way is very inexpensive and simple to implement.