🤖 AI

The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting

This paper addresses the exponential complexity of Decentralised Partially Observable Markov Decision Processes (DecPOMDPs) by shifting from agent counting to policy counting, thereby enabling tractable solutions through a novel policy-counted dynamic programming approach that leverages symmetry for compact representation.

Original authors: Nazlı Nur Karabulut, tanya Braun

Published 2026-08-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Nazlı Nur Karabulut, tanya Braun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast, chaotic landscape of modern computing, there exists a fundamental challenge: how to coordinate the actions of many independent thinkers when none of them can see the whole picture. Imagine a swarm of drones trying to rescue survivors in a smoke-filled building, or a fleet of autonomous vehicles navigating a city grid during a storm. Each unit must make decisions based on limited, local information, yet their collective success depends on how well they work together. Scientists model these scenarios using a framework called decentralized partially observable decision processes. In this model, a group of agents operates in an uncertain world, each seeing only a fragment of reality and acting to maximize a shared goal. The difficulty arises when the number of agents grows. As more units are added to the system, the number of possible ways they can coordinate their actions does not just grow; it explodes. This exponential growth creates a wall of complexity that makes finding the best strategy impossible for even the most powerful computers, effectively freezing the system in a state of indecision.

For years, researchers have tried to break through this wall by looking for patterns. If the agents are identical—meaning they have the same capabilities and face the same rules—scientists realized they could group them together. Instead of tracking every single agent individually, they could simply count how many agents were doing one thing versus another. This approach, known as "lifting," treats the group as a collection of counts rather than a list of individuals. It successfully simplified the description of the environment and the cost of checking if a plan would work. However, a curious and frustrating problem remained. While the description of the world became manageable, the space of possible strategies for the agents to follow still exploded. It was as if the map of the territory had shrunk to a manageable size, but the number of possible routes across that territory had grown so large that no one could ever find the best path. The strategy space, the set of all possible ways the agents could decide to act, remained too vast to navigate.

In a new study, researchers Nazlı Nur Karabulut and Tanya Braun from the University of Münster have turned this problem on its head. They realized that the explosion was not inevitable; it was a result of how the strategies themselves were being counted. In previous attempts, the method of counting agents was applied to the environment, but the strategies were still treated as unique combinations of individual choices. The authors proposed a shift in perspective: instead of just counting the agents, they began counting the strategies. They developed a new way to define these decision processes where the agents are still grouped by their similarities, but the possible plans they can follow are also grouped and counted. By treating a strategy not as a unique script for every single agent, but as a distribution of how many agents follow a few representative plans, they transformed the problem.

The result is a system where the complexity of finding the best solution no longer depends on the total number of agents in a way that causes an explosion. The researchers demonstrated that by using this "policy-counted" approach, the number of possible strategies grows at a manageable, polynomial rate, even as the number of agents increases. They proved mathematically that this new method is equivalent to the old, more complex way of thinking, meaning it finds the exact same best solution. Furthermore, they created a new algorithm, a step-by-step procedure for finding this best solution, that works efficiently within this new, simplified framework. This means that for systems with many identical agents, such as large swarms of robots or fleets of sensors, it is now possible to calculate the optimal way for them to coordinate, a task that was previously considered computationally impossible. The fire of exponential complexity has been contained, not by fighting it with more power, but by changing the lens through which the problem is viewed.

Technical Summary: The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting

Problem Statement

Decentralised partially observable Markov decision processes (DecPOMDPs) provide a framework for cooperative multi-agent decision-making under uncertainty. However, solving DecPOMDPs is notoriously difficult due to the exponential growth of the policy space relative to the number of agents ( $N$ ).

Recent work on "lifting" has attempted to mitigate this by exploiting symmetries among agents. By partitioning agents into sets of indistinguishable agents, researchers have successfully reduced the complexity of the model (transition, reward, and sensor functions) and the evaluation cost from exponential to polynomial in $N$ . This is achieved by using Counting Random Variables (CRVs) to represent actions and observations as histograms (e.g., counting how many agents perform action $a$ rather than tracking which specific agent performs it).

However, a critical limitation remains in the existing formulation of "counting DecPOMDPs" (as defined by Braun et al. [1]): while the model complexity is reduced, the policy space itself still explodes exponentially with $N$ . The previous approach applied counting to the actions and observations used to build policies, but the resulting policy space size still depended on $N$ in the exponent. This paper identifies this "exploding DecPOMDP" phenomenon as a barrier to tractability, even when the underlying model is compact.

Methodology

The authors propose a fundamental shift in the counting strategy: instead of counting agents' actions and observations to build policies, they propose counting policies themselves.

1. Policy-Counted DecPOMDPs

The paper introduces a new definition of DecPOMDPs, termed policy-counted DecPOMDPs. The core distinction lies in how the action and observation sets are defined:

Previous Approach (Counting Actions/Observations): The action and observation sets were replaced by CRVs (histograms of actions/observations). This reduced model complexity but left the policy space exponential.
New Approach (Counting Policies): The action and observation sets remain as "plain variables" (representative actions/observations for a partition). However, the policies available to agents within a partition are treated as a set of representative policies ( $\Pi_k$ $Π_{k}$ ).
- Since agents in a partition are indistinguishable (sharing the same action/observation spaces and symmetric transition/reward functions), they share the same local policy space.
- Instead of tracking individual agent policies, the system tracks a histogram of policies. A "counted partition policy" is defined as a histogram $h^\Pi_k = \{(\pi_j, m_j)\}$ , where $m_j$ is the number of agents in partition $k$ following representative policy $\pi_j$ .
- The joint policy space is thus the set of all valid histograms of policy counts across all partitions.

2. Updated Utility Calculation

The paper redefines the Maximum Expected Utility (MEU) calculation to operate over these counted policies.

The utility function $U^{\bar{M}}(h^\Pi)$ is computed recursively over the horizon $\tau$ .
Crucially, the summation over observations is transformed into a summation over counted observations. Given a joint counted policy, agents are grouped by the representative policy they follow. Within these groups, observations are aggregated into histograms.
The calculation utilizes multinomial coefficients ( $Mul(h^{o,\Pi})$ ) to account for the number of ground permutations encoded by the histograms, ensuring the utility matches that of the ground DecPOMDP.
Theorem 4 establishes that the MEU of the ground DecPOMDP is equal to the MEU of the policy-counted DecPOMDP.

3. Policy-Counted Dynamic Programming

To solve these problems efficiently, the authors extend the standard Multi-Agent Dynamic Programming (MA-DP) operator:

Exhaustive Backup: Instead of generating policies for individual agents, the operator generates depth- $t$ representative policies for each partition based on depth- $(t-1)$ representative policies.
Value Computation: Value vectors are computed for representative policies using the counted joint action and observation histograms derived from the representative policies (Eq. 13).
Pruning: Weakly dominated representative policies are pruned based on their value relative to other representative policies across all possible counted policies of other partitions (Eq. 14).

Key Contributions

The paper makes three primary contributions:

A New Definition: It defines policy-counted DecPOMDPs, a formalism that shifts the counting focus from agents' actions/observations to the agents' policies. This prevents the explosion of the policy space.
Tractability Analysis: It provides an analysis showing that for a fixed number of partitions ( $K$ ), fixed action/observation spaces, and fixed horizon ( $\tau$ ), both the model complexity and the policy space size depend polynomially on the number of agents ( $N$ ). This contrasts with previous counting methods where the policy space remained exponential.
Solution Algorithm: It presents a policy-counted dynamic programming operator that solves policy-counted DecPOMDPs efficiently. The authors prove that this operator is equivalent to standard dynamic programming on the ground model (Theorem 6) and that its runtime is polynomial in $N$ (Theorem 7).

Results

Complexity Reduction: The paper demonstrates that by counting policies rather than actions/observations, the dependency on $N$ in the policy space size is removed from the exponent. The size of the joint counted policy space and the cost of evaluating a joint policy are shown to be polynomial in $N$ (Corollary 2).
Equivalence: Theoretical proofs confirm that the policy-counted formulation is equivalent to the ground DecPOMDP in terms of Maximum Expected Utility (Theorem 4) and that the proposed dynamic programming operator yields correct results equivalent to standard DP (Theorem 6).
Runtime: The policy-counted dynamic programming algorithm runs in time polynomial in the number of agents, assuming the number of partitions and the horizon are fixed and small relative to $N$ .

Significance

The paper addresses a specific "curious case" where previous attempts to simplify DecPOMDPs via symmetry (lifting) failed to achieve full tractability because the policy space remained intractable. By redirecting the counting mechanism from the inputs (actions/observations) to the outputs (policies), the authors successfully "contain the fire" of exponential complexity.

The significance lies in providing a dedicated solution method that renders DecPOMDPs tractable in the number of agents under the assumption of indistinguishable partitions. This allows for the computation of optimal joint policies in large-scale agent systems where the number of agents is large, provided the agents can be grouped into a small number of symmetric partitions. The work extends the applicability of lifting techniques from merely reducing model evaluation costs to enabling the actual solution of the decision-making problem for large $N$ .