PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Nazlı Nur Karabulut, tanya Braun

arXiv:2608.17749v1cs.AI

TL;DR

DecPOMDPs face an exponentially growing policy space as the number of agents increases, even when counting reduces model and evaluation costs. This paper counts policies within partitions and introduces policy-counted dynamic programming, yielding solutions equivalent to ground solutions in polynomial rather than exponential time in the number of agents under fixed-parameter assumptions.

  • Problem

    DecPOMDPs remain difficult because potential policies grow exponentially with agent numbers, despite counting approaches reducing model size and evaluation cost.

  • Method

    The paper represents partitioned agents by counts of representative policies and introduces dynamic programming that updates values and prunes policies at the partition level.

  • Results

    Policy-counted dynamic programming produces a solution equivalent to the ground solution in time polynomial in N rather than exponential in N when other parameters are fixed.

  • Takeaways & Limitations

    Policy-counted DecPOMDPs provide tractability in agent numbers under fixed partitions, horizon, and representative action and observation spaces.

  • Takeaways & Limitations

    The benefit arises only when N is sufficiently large relative to K; otherwise policy-counting overhead is excessive, and a remaining exponent may still be large.

Abstract

from arXiv · show

Decentralised partially observable Markov decision processes (DecPOMDPs) provide a general framework for modelling multi-agent decision making under uncertainty. However, DecPOMDPs are known to suffer from exponential complexity in the number of agents. One way to combat this intractability in agent numbers is to look at partitions of agents that exhibit a form of symmetry among agents, allowing for a compact encoding by counting. However, a challenge arises as the policy space explodes, even though the model complexity and evaluation cost reduce to a polynomial dependence. In this paper, we redirect our focus from counting agents to counting policies, which actually enables tractability in agent numbers for so called policy-counted DecPOMDPs. Further, we present policy-counted dynamic programming using the compact representation to solve policy-counted DecPOMDPs efficiently.

1 Introduction

DecPOMDPs formalize cooperative multi-agent decision making under uncertainty, but their policy spaces grow exponentially with agent numbers. This work addresses that explosion by counting policies within symmetric agent partitions and developing policy-counted dynamic programming.

  • DecPOMDPs compute joint policies for cooperative agents to maximize a joint utility in stationary environments described by probabilistic transition models.
  • The number of potential policies escalates exponentially with the number of agents, making multi-agent decision making notoriously difficult.
  • Lifting exploits agent symmetries by partitioning agents, yielding a more compact and tractable problem formulation with fewer partitions than agents.
  • The paper defines counting DecPOMDPs that count policies to prevent policy-space explosion, updates utility calculation, and introduces counting dynamic programming.

2 Preliminaries

This section defines a ground DecPOMDP as a tuple of agents, states, actions, transitions, rewards, observations, sensing, and horizon, with agents cooperating under partial information. It also outlines dynamic programming, which constructs deeper policy trees, evaluates them with value vectors, and prunes weakly dominated policies.

  • DecPOMDP definition: A ground DecPOMDP M is defined as the tuple (I, S, A, T, R, O, Ω, τ).I contains N agents; S is the state variable; A contains local action variables; T is the transition function; R is the reward function; O contains local observation variables; Ω is the sensor function; and τ is the horizon.
  • DecPOMDP definition: The DecPOMDP problem seeks a joint policy maximizing expected utility over horizon τ.Individual policies map local observation histories to actions, and a joint policy is the tuple π = (π1, ..., πn).
  • DecPOMDP definition: Agents share a joint reward and maximize total expected utility, while each acts using local information without observing the full state or others’ observations.Agents remain coupled through the joint state and shared reward despite making decisions individually.
  • Dynamic programming: Dynamic programming builds increasingly deep individual-agent policy trees from subtrees and eliminates weakly dominated policies at each depth.Its operator performs an exhaustive backup, calculates policy value vectors, and then prunes dominated policies using a linear programme.
  • Dynamic programming: During evaluation, each policy’s value vector represents its value for every state and combination of the other agents’ policies.Pruning removes a policy when another policy has at least as high a value throughout the relevant state-policy space.

3 A Case of Exploding DecPOMDPs

Indistinguishability lets DecPOMDPs replace agent-level mappings with action and observation histograms, reducing model representation and evaluation costs to polynomial dependence on agent number. However, counting DecPOMDPs still has a policy space exponential in agent number, motivating policy counting instead.

  • Histogram-based representation: Indistinguishable agents can be represented by histograms that replace all permutations of actions or observations with one mapping from counts to outcomes.For 12 agents with action counts, one histogram replaces 495 individual action mappings.
  • Histogram-based representation: Symmetric transition, reward, and sensor functions make swapping actions or observations within a partition outcome-preserving.The symmetry assumptions extend from pairs of agents to arbitrary permutations within each partition.
  • Counting DecPOMDP formulation: Counting DecPOMDPs are equivalent by construction to DecPOMDPs satisfying the symmetry assumptions, replacing permutation-based mappings with histogram mappings and vice versa.The equivalence is established by construction in Appendix B.1.
  • Complexity: Polynomial dependence on N follows for counting DecPOMDP model representation and evaluation cost when the number of partitions K is much smaller than N.CRV ranges are bounded by N^a and N^o; compared with the ground case, K replaces N in the exponent.
  • Complexity: The policy space of a counting DecPOMDP nevertheless depends exponentially on N because N appears in both the base and exponent of its size expression.Replacing observation and action ranges with histogram counts reduces model complexity but does not prevent policy-space explosion.

4 Containing the Fire by Counting Policies

Policy-counted DecPOMDPs encode symmetric agents’ behavior by counting representative policies within partitions, preserving equivalence with the ground model while making model and evaluation complexity polynomial in agent number. This yields tractability in the number of agents under fixed partitions, action and observation spaces, and horizon.

  • Policy-counted model: The policy-counted DecPOMDP uses plain action and observation variables with counted transition, reward, and sensor inputs to represent partition symmetry compactly.This counted encoding operates over histograms instead of enumerating individual agents.
  • Policy counting: Agents with identical action and observation spaces share representative policies that can be counted within each partition.The resulting counted partition policy is a histogram whose entries give the numbers of agents following each representative policy.
  • Equivalence: A ground DecPOMDP satisfying Eqs. (5) and (7) is equivalent to its policy-counted version, with identical maximum expected utility.Theorem 4 states MEU(M) = MEU( M̄ ).
  • Complexity: For fixed K, representative action and observation spaces, and horizon τ, model complexity, joint counted-policy evaluation cost, and policy-space size depend polynomially on N.Histograms allow calculations leading to the same result to be performed only once.
  • Complexity: The policy-counted DecPOMDP is tractable in the number of agents, with N no longer appearing in the exponent and larger instances enabled especially when K is small.This reduction follows from polynomial dependence of the counted observation and policy spaces on N.

5 Policy-Counted Dynamic Programming

Policy-counted dynamic programming performs exhaustive backup, value computation, and pruning at the partition level, while remaining equivalent to standard dynamic programming on the ground DecPOMDP. Under fixed partitions, representative action and observation spaces, and horizon, its runtime is polynomial in the number of agents.

  • 5 Policy-Counted Dynamic Programming: The operator applies exhaustive backup, value computation, and pruning to representative policies at the partition level using counted equations.During backup, it builds depth-t representative policies from depth-(t −1) policies for each partition.
  • 5 Policy-Counted Dynamic Programming: Pruning removes a representative policy only when another policy has equal or higher value for every state and counted policy configuration of the other partitions.The pruning condition is solvable by a linear programme.
  • 5 Policy-Counted Dynamic Programming: Policy-counted dynamic programming is equivalent to standard dynamic programming on the corresponding ground DecPOMDP.Correctness follows directly from this equivalence and the correctness of standard dynamic programming.
  • 5 Policy-Counted Dynamic Programming: For fixed K, representative action and observation spaces, and horizon τ, policy-counted dynamic programming has runtime polynomial in the number of agents N.The polynomial-runtime analysis covers backup, value calculation, and pruning.
  • 5 Policy-Counted Dynamic Programming: With all other parameters fixed, the compact encoding generates a solution equivalent to the ground solution in time polynomial in N instead of exponential in N.The DecTiger example illustrates similarities and differences among ground, counting, and policy-counted DecPOMDPs.

6 Conclusion

The paper introduces policy-counted DecPOMDPs, which use representative policies and agent-policy counts to reduce complexity from exponential to polynomial in agent numbers under fixed parameters. It also presents policy-counted dynamic programming and identifies policy encodings, lifting, and approximations as directions for further scalability.

  • Conclusion: Policy-counted DecPOMDPs reduce complexity from exponential to polynomial in the number of agents under structural assumptions and fixed other parameters.They exploit partitioned agent sets and representative policies to count how many agents follow each policy, compacting the model and reducing computational cost and policy space.
  • Conclusion: Policy-counted dynamic programming updates policies and values while pruning policies directly at the partition level.This approach supports tractability in agent numbers when the number of partitions, horizon, and representative action and observation spaces are fixed.
  • Conclusion: Future work targets policy encodings, lifting to large state spaces, and approximations because histograms are rarely needed in count steps of 1.These directions aim to provide additional complexity reductions and improve scalability.

(Supplementary Material) … B.1 Equivalence between a Ground DecPOMDP and a Counting DecPOMDP

The supplementary material gives linear programmes for pruning in ground and policy-counted DecPOMDP dynamic programming, then proves equivalence between ground and counting DecPOMDPs under Eqs. (5) and (7).

  • A Linear Programmes: The pruning step in dynamic programming is expressed through linear programmes that repeat the main paper’s pruning condition.This material introduces the programmes used during pruning.
  • A.1 Ground DecPOMDP: In a ground DecPOMDP, a policy πt_i,j is pruned when the stated condition holds, equivalently when the linear programme yields d < 0.The ground-policy programme is presented as the test for pruning πt_i,j.
  • A.2 Policy-Counted DecPOMDP: In a policy-counted DecPOMDP, a policy πt_k,l is pruned under an analogous condition that can still be solved using a linear programme.The corresponding programme is given for the policy-counted representation.
  • B.1 Equivalence between a Ground DecPOMDP and a Counting DecPOMDP: The supplementary material states Theorem 1: a ground DecPOMDP M satisfying Eqs. (5) and (7) is equivalent to a counting DecPOMDP ¯ Mc.The theorem establishes the claimed equivalence under the paper’s structural conditions.
  • B.1 Equivalence between a Ground DecPOMDP and a Counting DecPOMDP: The conversion to a counting DecPOMDP groups agents into partitions sharing action and observation spaces, as guaranteed by Eq. (5).For each partition Ik, the construction introduces CRVs #Ik[Ak] and #Ik[Ok] for actions and observations.
  • B.1 Equivalence between a Ground DecPOMDP and a Counting DecPOMDP: The reverse conversion unions the partitions into the agent set and reconstructs action, observation, transition, reward, and sensor functions using mappings over permutations consistent with the counts.This replacement makes the reconstructed functions fulfill Eq. (7).

B.2 Full Proof for Theorem 2

Theorem 2 states that any ground DecPOMDP satisfying Eqs. (5) and (7) is equivalent to a counting DecPOMDP. The proof establishes this by grouping agents with shared spaces and symmetric behaviour, then expanding counted functions back into ground representations.

  • Theorem 2: Theorem 2 states that a ground DecPOMDP satisfying Eqs. (5) and (7) is equivalent to a counting DecPOMDP.This is the theorem’s stated equivalence result.
  • Proof: Agents with identical action and observation spaces and symmetric behaviour are grouped into partitions represented by shared action and observation variables.For each partition, the construction stores Ak = Ai = Aj and Ok = Oi = Oj.
  • Proof: The reverse construction expands each counted random variable into ground variables and maps inputs to outcomes according to their histogram representation.Replacing CRV #Ik[Vk] with Vk,1, . . . , Vk,nk yields a ground model satisfying Eq. (7).

B.3 Full Proof of Theorem 3 · B.4 Full Proof of Theorem 4

Theorem 3 establishes that, with fixed partitions, action and observation spaces, and horizon, counting DecPOMDP model complexity is polynomial in N. Theorem 4 establishes equal maximum expected utility between a ground DecPOMDP and its corresponding policy-counted model.

  • B.3 Full Proof of Theorem 3: For fixed K, action and observation spaces, and horizon τ, the counting DecPOMDP model complexity is polynomial in N.This is the statement of Theorem 3.
  • B.3 Full Proof of Theorem 3: The histogram space of a counting random variable for partition I_k depends on the partition size n_k and the number m of possible values.The proof begins by bounding the histogram space for each partition.
  • B.3 Full Proof of Theorem 3: Because K is fixed and K ≪N, each partition size n_k is at most N and has the same order of magnitude as N.This assumption transfers the polynomial dependence from partition sizes to the total number of agents.
  • B.3 Full Proof of Theorem 3: O(s2N Ka), O(sN Ka), and O(sN Ko) bound the sizes of T̄, R̄, and Ω̄, respectively.Here s = |ran(S̄)|, a = max_k |ran(A_k)|, and o = max_k |ran(O_k)|.
  • B.4 Full Proof of Theorem 4: MEU(M) = MEU(M̄) for a ground DecPOMDP M satisfying Eqs. (5) and (7).This is the statement of Theorem 4: both models have the same maximum expected utility.
  • B.4 Full Proof of Theorem 4: The proof converts each ground joint policy π into a joint counted policy histogram h_Π that counts representative-policy assignments within every partition.The value-equivalence argument starts from a ground policy, its corresponding policy histogram, and an empty joint counted observation.

B.5 Full Proof of Theorem 5 · B.6 Full Proof of Theorem 6

Theorem 5 proves that, with fixed partitions, action and observation spaces, and horizon, both joint counted-policy evaluation cost and policy-space size are polynomial in agent number. Theorem 6 proves that policy-counted dynamic programming is equivalent to standard dynamic programming on the corresponding ground DecPOMDP.

  • B.5 Full Proof of Theorem 5: Theorem 5 establishes polynomial dependence on agent number for evaluating a joint counted policy and for the overall joint counted policy space.The result assumes fixed K, action and observation spaces, and horizon τ.
  • B.5 Full Proof of Theorem 5: Joint counted observations are organized by partitions, representative policies, and representative observation histories.The proof analyzes Eq. (10) using a state sum of size s = |ran(S)| and defines a = maxk |ran(Ak)| and o = maxk |ran(Ok)|.
  • B.5 Full Proof of Theorem 5: Each representative history distributes up to nk ≤N agents across o possible observations, yielding a histogram count for each partition.The number of agents following a particular history is bounded by N while K ≪N.
  • B.5 Full Proof of Theorem 5: The joint counted observation space is the cross product of K partitions, p representative policies, and h representative histories, denoted HKph, and is capped polynomially in N.The proof then uses this bound to show that the joint counted policy space is also polynomial in N.
  • B.6 Full Proof of Theorem 6: Exhaustive backup can use one representative policy per partition because all agents in partition Ik have identical policies under Eq. (5).This reduces backup construction to representative policies while preserving the partition structure.
  • B.6 Full Proof of Theorem 6: Value computation can be performed on counted partition policies because MEU(¯ M) = MEU(M), and utility rewriting gives equal values for agents within each partition.The proof identifies value computation as a rewriting of utility computation.
  • B.6 Full Proof of Theorem 6: Pruning needs to check each representative policy only once per partition because Eq. (4) is identical for all agents in Ik, completing the equivalence proof.The equivalence of exhaustive backup, value computation, and pruning establishes an equivalent overall procedure.

B.7 Full Proof of Theorem 7 · C DecTiger Example

For fixed partitions, action and observation spaces, and horizon, policy-counted dynamic programming runs polynomially in the number of agents. The proof establishes this by analyzing exhaustive backup, value calculation, and pruning, while the DecTiger example introduces model definitions and compares model and worst-case policy-space sizes.

  • B.7 Full Proof of Theorem 7: Theorem 7 states that policy-counted dynamic programming has runtime polynomial in the number of agents N under fixed K, action and observation spaces, and horizon τ.These conditions are explicitly fixed in the theorem statement.
  • B.7 Full Proof of Theorem 7: Exhaustive backup has polynomial dependence on N because the counted policy representation bounds the relevant histogram space polynomially.The proof uses a = maxk |ran(Ak)| and o = maxk |ran(Ok)| and states the histogram-space bound is polynomial in N.
  • B.7 Full Proof of Theorem 7: Since exhaustive backup, value calculation, and pruning each depend polynomially on N, the overall dynamic-programming runtime is polynomial in N.This is the proof’s final aggregation of the three operator steps.
  • B.7 Full Proof of Theorem 7: Value calculation remains polynomial in N because the sum over joint counted observations depends polynomially on N.The proof contrasts this with the recursive calculation of U hΠ.
  • B.7 Full Proof of Theorem 7: Pruning is polynomial in N because its linear programme has numbers of variables and constraints that depend polynomially on the counted policy space HΠ.Linear programmes can be solved in time polynomial in their numbers of variables and constraints.
  • C DecTiger Example: The DecTiger example presents model definitions, model and worst-case policy-space sizes, and differences arising when applying the dynamic-programming operator.The supplied passage identifies these as the example section’s contents.

C.1 Model Definition … Level t = 1

The paper instantiates DecTiger as a two-agent model with a single counting-symmetry partition, then compares ground, counting, and policy-counted representations and dynamic-programming operations across levels t = 0 and t = 1. The level-t = 1 example shows policy counting is advantageous primarily when agent numbers outweigh representative policy complexity.

  • C.1 Model Definition: DecTiger has two agents, states {tl, tr}, three actions {li, ol, or}, and two observations {hl, hr}.Both agents share the same action and observation sets.
  • C.1 Model Definition: The model exhibits counting symmetry and is rewritten as a counting model with K = 1 partition indexed by c.The single partition contains agent1 and agent2.
  • C.2 Model and Policy Space Sizes: The model-and-policy-size analysis compares ground, counting, and policy-counted models using agent, partition, horizon, state, action, observation, policy, and function-range parameters.These parameters define the sizes of local, partition, joint, and representative policy spaces and of transition, reward, and sensor functions.
  • C.3 Dynamic Programming: Dynamic programming compares backup, value calculation, and pruning for the ground, counting, and policy-counted DecTiger versions at levels t = 0 and t = 1.The comparison is organized around the three dynamic-programming steps.
  • Level t = 0: At level t = 0, the ground operator builds six policies overall, while the counting operator builds six single-node policies for its one partition.The ground version builds three policies for each of two agents; the counting version uses six action histograms.
  • Level t = 1: At level t = 1, the ground operator builds 27 policies per agent, the counting operator builds 216 policies, and the policy-counted operator evaluates 378 counted policies.The policy-counted version checks 27 representative policies against each counted policy of the remaining partition during pruning.
  • Level t = 1: Policy counting pays off only when the number of agents is large or outweighs the number of representative policies.The example states that agents should be at least an order larger than the available representative actions and observations.
Loading 2608.17749v1…