cs.AIAug 18, 2026

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

Authors: Nazlı Nur Karabulut, Tanya Braun

Organizations: Computer Science Department, University of Münster, Münster, Germany

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: Policies at level t=1t=1 available to agents with actions a,ba,b and observations x,yx,y
Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

 MMMˉc\bar{M}_{c}Mˉ\bar{M}
ss222222
aa33(N+3−13−1)=(N+22)\binom{N+3-1}{3-1}=\binom{N+2}{2}33
a\boldsymbol{a}3N3^{N}(N+22)K\binom{N+2}{2}^{K}(N+22)K\binom{N+2}{2}^{K}
oo22(N+2−12−1)=(N+11)\binom{N+2-1}{2-1}=\binom{N+1}{1}22
o\boldsymbol{o}2N2^{N}(N+11)K\binom{N+1}{1}^{K}(N+11)K\binom{N+1}{1}^{K}
pp32τ−12−13^{\frac{2^{\tau}-1}{2-1}}(N+22)(N+11)τ−1(N+11)−1\binom{N+2}{2}^{\frac{\binom{N+1}{1}^{\tau}-1}{\binom{N+1}{1}-1}}(N+32τ2−1−132τ2−1−1)\begin{pmatrix}{N+3^{\frac{2^{\tau}}{2-1}}-1}\\ {3^{\frac{2^{\tau}}{2-1}}-1}\end{pmatrix}
Appendix
Table 2
More in this topic

Partially Observable Markov Decision Processes

Partially Observable Markov Decision Processes study sequential decisions when agents must act from incomplete, noisy observations of hidden states.

See all 88 papers

Explore similar work

CardsList

  1. Risk-seeking conservative policy iteration with agent-state based policies for Dec-POMDPs with guaranteed convergence

    Apr 10, 2026Amit Sinha, Matthieu Geist, Aditya MahajanPartially Observable Markov Decision ProcessesPolicy Iteration

    Department of Electrical and Computer Engineering, McGill University, Montreal, Quebec · Earth Species Project

  2. Multi-Environment POMDPs with Finite-Horizon Objectives

    May 8, 2026Léonard Brice, Filip Cano, Krishnendu Chatterjee +2Belief-Space PlanningMarkov Models

    Institute of Science and Technology Austria

  3. On the Complexity Gap Between POMDPs and Multi-Environment POMDPs

    Oct 10, 2026Eline M. Bovy, Caleb Probine, Marnix Suilen +2Robust Partially Observable Markov Decision ProcessesPartially Observable Markov Decision Processes

    Radboud University Nijmegen, The Netherlands · The University of Texas at Austin Austin, USA · University of Antwerp Antwerp, Belgium +1