Interaction Structure and Dimensionality Reduction in Decentralized MDPs

Abstract

Decentralized Markov Decision Processes are a power-ful general model of decentralized, cooperative multi-agent problem solving. The high complexity of the general prob-lem 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 inter-actions 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 prob-lem rewritten to take advantage of the reduction.