Metareasoning as a Formal Computational Problem

Vincent Conitzer

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.

Subjects: 9.2 Computational Complexity; 16. Real-Time Systems

Submitted: May 5, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.