Skip to main content

Definition and complexity of some basic metareasoning problems

Publication ,  Journal Article
Conitzer, V; Sandholm, T
Published in: IJCAI International Joint Conference on Artificial Intelligence
December 1, 2003

In most real-world settings, due to limited time or other resources, an agent cannot perform all potentially useful deliberation and information gathering actions. This leads to the metareasoning problem of selecting such actions. Decision-theoretic methods for metareasoning have been studied in AI, but there are few theoretical results on the complexity of metareasoning. We derive hardness results for three settings which most real metareasoning systems would have to encompass as special cases. In the first, the agent has to decide how to allocate its deliberation time across anytime algorithms running on different problem instances. We show this to be ATP-complete. In the second, the agent has to (dynamically) allocate its deliberation or information gathering resources across multiple actions that it has to choose among. We show this to be AfP-hard even when evaluating each individual action is extremely simple. In the third, the agent has to (dynamically) choose a limited number of deliberation or information gathering actions to disambiguate the state of the world. We show that this is AfP-hard under a natural restriction, and PSPACE-hard in general.

Duke Scholars

Published In

IJCAI International Joint Conference on Artificial Intelligence

ISSN

1045-0823

Publication Date

December 1, 2003

Start / End Page

1099 / 1106
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Conitzer, V., & Sandholm, T. (2003). Definition and complexity of some basic metareasoning problems. IJCAI International Joint Conference on Artificial Intelligence, 1099–1106.
Conitzer, V., and T. Sandholm. “Definition and complexity of some basic metareasoning problems.” IJCAI International Joint Conference on Artificial Intelligence, December 1, 2003, 1099–1106.
Conitzer V, Sandholm T. Definition and complexity of some basic metareasoning problems. IJCAI International Joint Conference on Artificial Intelligence. 2003 Dec 1;1099–106.
Conitzer, V., and T. Sandholm. “Definition and complexity of some basic metareasoning problems.” IJCAI International Joint Conference on Artificial Intelligence, Dec. 2003, pp. 1099–106.
Conitzer V, Sandholm T. Definition and complexity of some basic metareasoning problems. IJCAI International Joint Conference on Artificial Intelligence. 2003 Dec 1;1099–1106.

Published In

IJCAI International Joint Conference on Artificial Intelligence

ISSN

1045-0823

Publication Date

December 1, 2003

Start / End Page

1099 / 1106