Introduction
Planning for multiple agents in uncertain, decentralized environments is a core challenge in artificial intelligence, applicable to domains ranging from robot swarms to space exploration. These problems are typically modeled as Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs).
The general version of this problem is notoriously difficult—specifically, NEXP-complete, meaning it is exponentially harder than already-difficult NP-complete problems. To make these problems computationally tractable, researchers often look for "special cases" or restricted models where agents act somewhat independently. For instance, previous work found a computational "sweet spot": if agents have their own separate transitions and observations and only share a joint reward, the problem's complexity drops to NP-complete.
This paper investigates a critical question: How much independence is actually required to keep the complexity low? By examining several intuitive sub-classes of decentralized control, the authors demonstrate that the previously discovered complexity reduction is incredibly fragile. Nearly any other combination of independence immediately pushes the complexity back up to the NEXP-complete computational wall.
Methodology: Complexity via Reduction
The paper employs theoretical complexity analysis rather than empirical datasets. To prove that a specific sub-class of problems is NEXP-complete, the authors use a mathematical technique called reduction.
They rely on a well-known NEXP-complete benchmark called the TILING problem. The objective of this problem is to decide if a grid can be completely filled with a given set of tiles such that adjacent tiles follow strict compatibility rules.
The authors show how to "translate" any instance of the TILING problem into the specific decentralized planning models they are studying (specifically "Factored" Dec-MDPs, where the global state is broken down into local components for each agent). If an algorithm could solve the planning problem, it could also solve the TILING problem. Therefore, the planning problem must be at least as computationally hard as TILING.
Key Insights
- The Fragility of Efficiency: The primary insight is that the jump from NEXP to NP is not a sliding scale; it is a cliff. Unless a model possesses both transition and observation independence, the problem remains at maximum difficulty.
- Independent Rewards Are Insufficient: Even if agents have completely independent reward functions (i.e., they do not care what the other agent earns), if their actions affect each other's physical state or observations, the problem remains NEXP-complete.
- The Power of "Events": The authors analyzed "event-driven" models where agents are mostly independent except for a few specific interactions (e.g., Agent A cannot finish a task until Agent B triggers an "event"). They found that even a small number of these dependencies—scaling linearly relative to the state space—is enough to make the problem NEXP-complete.
- Action Constraints Dictate Complexity: In models where agents only interact by restricting which actions are available to one another (state-dependent action sets), the complexity remains NEXP-complete. This is a surprising result because the agents' internal dynamics and rewards are otherwise entirely decoupled.
Formal Results
The paper establishes several new NEXP-completeness results for specialized Dec-MDP models:
- Reward-Independent Models: Factored Dec-MDPs with independent rewards but dependent transitions or observations are NEXP-complete.
- Event-Driven Models: Models with local full observability and independent rewards, but with event-based transition dependencies, are NEXP-complete.
- State-Dependent Action Models: Models where agents are independent in transitions and rewards but share a global state that dictates available actions are NEXP-complete.
- The Logarithmic Exception: The authors identified one narrow window of computational relief. If the number of event-based dependencies is very small—specifically logarithmic relative to the size of the state space—the problem becomes solvable in NP time.
Limitations and Future Directions
It is important to note that these results describe worst-case complexity. While these problems are theoretically intractable in the general case, specific real-world instances might still be solvable using clever heuristics or approximate methods.
Because exact solutions are prohibitively difficult to find for almost all interesting cases, the authors suggest these theoretical boundaries should drive the community toward developing better approximation tools, rather than continuing to search for "easy" exact sub-classes. Finally, a vital open problem highlighted by the authors is defining and analyzing the average-case difficulty, which currently remains ill-defined in the field of decentralized planning.
Summary updated