Metareasoning as a formal computational problem
Metareasoning research often lays out high-level principles, which are then applied in the context of larger systems. While this approach has proven quite successful, it sometimes obscures how metareasoning can be seen as a crisp computational problem in its own right. This alternative view allows us to apply tools from the theory of algorithms and computational complexity to metareasoning. In this paper, we consider some known results on how variants of the metareasoning problem can be precisely formalized as computational problems, and shown to be computationally hard to solve to optimality. We discuss a variety of techniques for addressing these hardness results. Copyright © 2008, Association for the Advancement of Artificial Intelligence.
