Search papers, labs, and topics across Lattice.
This paper addresses the exponential complexity of decentralized partially observable Markov decision processes (DecPOMDPs) by shifting the focus from counting agents to counting policies, which allows for a more tractable representation. The authors introduce a novel approach called policy-counted dynamic programming, which leverages this compact encoding to efficiently solve DecPOMDPs while maintaining polynomial complexity in model evaluation. The key finding is that this method significantly reduces the computational burden associated with multi-agent decision-making under uncertainty, enabling practical applications in larger agent scenarios.
Counting policies instead of agents transforms DecPOMDPs from intractable to efficiently solvable, paving the way for scalable multi-agent systems.
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.
