Computer Science – Artificial Intelligence
Scientific paper
2003-07-07
In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003
Computer Science
Artificial Intelligence
Scientific paper
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 $\mathcal{NP}$-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 $\mathcal{NP}$-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 $\mathcal{NP}$-hard under a natural restriction, and $\mathcal{PSPACE}$-hard in general.
Conitzer Vincent
Sandholm Tuomas
No associations
LandOfFree
Definition and Complexity of Some Basic Metareasoning Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Definition and Complexity of Some Basic Metareasoning Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Definition and Complexity of Some Basic Metareasoning Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-10286