Extended abstract: Learning search strategies

The underlying motivation for the work presented in this paper is to usefully understand what is called the value of computation (Russell & Wefald 1991). By this intuitively mean the following. Suppose we have some computational process C which, at some point, has a choice between the computations co and cl. We would like to be able to make claims of the form: co is a better choice for C than cl because the value of co is greater than that of cl. Extending this idea by calling the set of choices made by C a program, we would similarly like to be able to say that the value of the program ~r = {ci} is greater than that of ~r ’ = {e~}. This, in turn, would allow us to define the best, or bounded optimal (Russell & Subramanian 1995) program for C. Let us consider what would be required of a formalism to make these