Interaction Structure and Dimensionality Reduction in Decentralized MDPs

Martin Allen, Marek Petrik, Shlomo Zilberstein

Decentralized Markov Decision Processes are a powerful general model of decentralized, cooperative multi-agent problem solving. The high complexity of the general problem leads to a focus on restricted models. While worst-case hardness of such reduced problems is often better, less is known about the actual difficulty of given instances. We show tight connections between the structure of agent interactions and the essential dimensionality of various problems. Bounds are placed on problem difficulty, given restrictions on the type and number of interactions between agents. These bounds arise from a bilinear programming formulation of the problem; from such a formulation, a more compact reduced form can be automatically generated, and the original problem rewritten to take advantage of the reduction.

Subjects: 7.1 Multi-Agent Systems; 1.11 Planning

Submitted: Apr 15, 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.