Safety
The Curious Case of Exploding DecPOMDPs: Containing the Fire through Policy Counting
arXiv:2608.17749v1 Announce Type: new Abstract: Decentralised partially observable Markov decision processes (DecPOMDPs) provide a general framework for modelling multi-agent decision making under unc
arXiv:2608.17749v1 Announce Type: new 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.
Related
- Synthesizing POMDP Policies: Sampling Meets Model-checking via Learning
- Safety-critical Control Under Partial Observability: Reach-Avoid POMDP meets Belief Space Control
- Think Fast and Far: Long-Horizon Online POMDP Planning via Rapid State Sampling
- Robustness Analysis of POMDP Policies to Observation Perturbations
Source: arXiv cs.AI | 2026-08-19