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

arXiv: https://arxiv.org/abs/2608.17749 · HTML: https://mlsanity.com/paper/2608.17749/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 18 Aug 2026.

## Builds on (most cited first, 6 of 6)

- [Tractability through Exchangeability: A New Perspective on Efficient Probabilistic Inference](https://mlsanity.com/paper/1401.1247/) (2014)
- [Lifted Variable Elimination: Decoupling the Operators from the Constraint Language](https://mlsanity.com/paper/1402.0565/) (2014)
- [Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information](https://mlsanity.com/paper/1606.06888/) (2016)
- [Compact Representation of Value Function in Partially Observable Stochastic Games](https://mlsanity.com/paper/1903.05511/) (2019)
- [Approximate Dec-POMDP Solving Using Multi-Agent A*](https://mlsanity.com/paper/2405.05662/) (2024)
- [Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions](https://mlsanity.com/paper/2505.22147/) (2025)

## Abstract (arXiv)

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.