Dec-POMDPs and the Complexity of Decentralised Control

Two robots share one reward signal. Each sees part of the room, neither can talk to the other while acting, and both must commit to a policy before the episode starts. That setting has a name, a formal model, and a complexity result that explains why almost every practical algorithm in cooperative multi-agent RL looks the way it does: finding the optimal joint policy is harder than any problem single-agent RL asks you to solve, by a provable margin.

The model

A decentralised partially observable Markov decision process (Dec-POMDP) is the tuple \(\langle I, S, \{A_i\}, T, R, \{\Omega_i\}, O, h \rangle\): a set of \(n\) agents, a hidden global state, one action set per agent, a transition function over the joint action, a single shared reward, one observation set per agent, an observation function, and a horizon. Three features do all the work. The reward is shared, so this is a fully cooperative problem with no conflict of interest. The state is hidden, so each agent acts on a local observation history. And there is no communication channel at execution time, so each agent's policy is a map from its own observation history to an action, with no access to what anyone else saw.

The last point is the one that bites. A joint policy is a tuple of local policies, and the quality of agent 1's policy depends on which policy agent 2 happens to be running. You cannot evaluate a local policy in isolation, and you cannot decompose the search.

Why it is NEXP-complete

Bernstein, Givan, Immerman and Zilberstein proved that for even two agents, the finite-horizon Dec-POMDP (and the Dec-MDP, where the agents' observations jointly determine the state) is complete for nondeterministic exponential time (Bernstein et al., 2002, Mathematics of Operations Research 27(4), 819-840; preprint). Assuming EXP ≠ NEXP, that means worst-case superexponential time, and the paper notes the problems most likely require doubly exponential time.

Put that next to the single-agent ladder. A finite-horizon MDP is solvable in polynomial time by dynamic programming. A finite-horizon POMDP is PSPACE-complete (Papadimitriou and Tsitsiklis, 1987), which is already bad. Adding one more agent with its own private observation stream jumps two complexity classes, and the jump is not about the size of the action space. It is about the information structure: each agent conditions on a different history, so the number of candidate joint policies is doubly exponential in the horizon, and no belief state summarises it.

The distinction that matters

A Dec-POMDP is not a POMDP with a larger action space. If you hand one controller every observation and let it emit the joint action, you get a POMDP, which is PSPACE-complete, and the hard part has disappeared. What makes the decentralised problem hard is that the controllers are separate at execution time.

The consequence shows up in what each agent must reason about. In a POMDP, a belief over states is a sufficient statistic. In a Dec-POMDP it is not, because an optimal action depends on what the other agent believes, which depends on what it thinks you believe. The nested belief hierarchy is the formal statement of the problem that zero-shot coordination methods attack empirically (Oliehoek and Amato, 2016, A Concise Introduction to Decentralized POMDPs).

What the result forces

Three standard moves in the literature are direct responses to this complexity, not stylistic choices.

Centralised training with decentralised execution exploits the fact that the hardness is in execution-time information, not training-time information. A critic conditioned on the joint state and joint action faces a stationary problem; only the policies it trains are constrained to local observations. See non-stationarity in multi-agent learning.

Structural restrictions buy real complexity reductions. Transition-independent and network-distributed Dec-POMDPs, where agents' transitions are coupled only through reward or only through local neighbourhoods, drop to NP-complete in useful cases. This is why so many benchmark environments are grid worlds with local interaction.

Communication collapses the problem. With free, instantaneous, lossless broadcast, a Dec-POMDP becomes a multi-agent POMDP. Every realistic communication model sits between the two extremes, and the gap between them is exactly the cost the decentralisation imposes.

When it breaks

Approximation without guarantees. Every deep MARL algorithm in use is a heuristic for a NEXP-complete problem. Convergence claims are about the optimiser, not about finding the optimal joint policy, and a result that looks like convergence is often a local joint optimum from which no single agent can improve unilaterally.

Infinite horizon is worse. The finite-horizon result is the good news. Deciding optimal infinite-horizon policies is undecidable, which is why discounted approximations and finite rollouts are universal.

The model assumes a known environment. The complexity result is for planning with the model in hand. Learning adds the usual exploration problem on top, now with exploration that must be coordinated to be informative at all.

Shared reward hides the credit problem. A Dec-POMDP's single reward makes the objective unambiguous and the learning signal almost useless, since each agent sees the team's outcome and not its own contribution. See credit assignment across agents.