Metareasoning as a formal computational problem


Journal Article

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.

Duke Authors

Cited Authors

  • Conitzer, V

Published Date

  • December 1, 2008

Published In

  • Aaai Workshop Technical Report

Volume / Issue

  • WS-08-07 /

Start / End Page

  • 29 - 33

Citation Source

  • Scopus