Memory-Bounded Dynamic Programming for DEC-POMDPs

Sven Seuken, Shlomo ZilbersteinIJCAI 2007 · OpenReview

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.

Conceptual overview of MBDP combining top-down heuristics with bottom-up dynamic programming.

The algorithm proceeds through a series of steps:

  1. Full Backup: For each agent, all possible one-step extensions of the current policy trees are generated.
  2. 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.
  3. Policy Selection: For the identified belief points, only the top maxTrees policy pairs are retained, and the rest are discarded.
  4. 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.

Comparison of MBDP against optimal and other approximate algorithms across various horizons.

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

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.
BibTeX
@inproceedings{seuken2007memory,
  author = {Sven Seuken and Shlomo Zilberstein},
  title = {{Memory-Bounded Dynamic Programming for DEC-POMDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=SkE2V7zdbH},
}
Figure