Abstract
Decentralized decision making under uncertainty has been shown to be intractable when each agent has different partial information about the domain. Thus, improving the applicability and scalability of planning algorithms is an important challenge. We present the first memory-bounded dynamic programming algorithm for finite-horizon decentralized POMDPs. A set of heuristics is used to identify relevant points of the infinitely large belief space. Using these belief points, the algorithm successively selects the best joint policies for each horizon. The algorithm is extremely efficient, having linear time and space complexity with respect to the horizon length. Experimental results show that it can handle horizons that are multiple orders of magnitude larger than what was previously possible, while achieving the same or better solution quality. These results significantly increase the applicability of decentralized decision-making techniques.
Introduction
The Decentralized Partially Observable Markov Decision Process (DEC-POMDP) is a powerful framework for multi-agent coordination under uncertainty. However, solving DEC-POMDPs is notoriously difficult—proven to be NEXP-complete. The core challenge is the "double exponential" explosion of the policy space: as agents receive observations over time, the number of possible policy trees grows at a rate of $|A|^{|O|^T}$. Traditional exact dynamic programming methods typically fail to reach horizons beyond 10 time steps due to memory exhaustion. This paper introduces Memory-Bounded Dynamic Programming (MBDP) to overcome this "horizon barrier."
Methodology: Memory-Bounded Dynamic Programming
MBDP integrates bottom-up dynamic programming with top-down heuristics to maintain a manageable set of policies. The core innovation lies in using heuristics to identify a small, fixed number of relevant belief points, which then guide the selection of the most promising policies.
The algorithm proceeds through a series of steps:
- Full Backup: For each agent, all possible one-step extensions of the current policy trees are generated.
- Heuristic Selection: A portfolio of heuristics (e.g., MDP or Infinite-Horizon) is used to sample relevant joint belief points from the infinitely large belief space.
- Policy Selection: For the identified belief points, only the top
maxTreespolicy pairs are retained, and the rest are discarded. - Pointer Mechanism: To ensure linear space complexity, the algorithm stores pointers to subtrees rather than the full tree structures. This ensures that memory usage grows linearly with the horizon $T$.
Experimental Evaluation
The algorithm was evaluated on two classic DEC-POMDP benchmarks: the Multi-Access Broadcast Channel (MABC) and the Multi-Agent Tiger Problem.
As shown in the results, MBDP successfully scales to horizons of 100,000—orders of magnitude beyond previous state-of-the-art methods like JESP or PBDP, which struggle past horizons of 3 to 8. Notably, MBDP maintains high solution quality, often matching or exceeding the values found by more computationally expensive approximate methods. For instance, in the MABC problem at horizon 100,000, the algorithm finished in under an hour, a feat previously considered impossible.
Discussion and Insights
The success of MBDP hinges on the "Relevant Belief" filter. While the total policy space is vast, only a tiny fraction of policies are relevant to the belief states agents actually encounter. By anchoring selection to heuristic-driven belief points, the search space is drastically reduced without significant loss in performance. This transforms a "provably intractable" problem into one that is computationally manageable.
However, limitations remain. The "full backup" step is still sensitive to the number of observations, which may limit applicability to problems with very large observation sets. Additionally, solution quality depends on the effectiveness of the chosen heuristic portfolio. Future work could involve more aggressive pruning or exploring even larger state and action spaces.
Conclusion
MBDP represents a significant leap in the scalability of DEC-POMDP solvers. By achieving linear time and space complexity with respect to the horizon, it effectively shatters the previous scalability limits, opening the door for decentralized planning in long-horizon, real-world applications.
Summary updated