Point-based Dynamic Programming for DEC-POMDPs

Daniel Szer, François CharpilletAAAI 2006

Abstract

Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs) provide a powerful framework for multi-agent coordination under uncertainty, but their NEXP-complete complexity has historically limited their application. This paper presents a novel point-based dynamic programming (PBDP) approach that shifts the focus from the entire infinite belief space to a finite set of reachable belief states. By replacing expensive linear programming bottlenecks with simpler evaluation operators, the proposed algorithms—both exact and approximate—demonstrate significant improvements in scalability and runtime over traditional dynamic programming methods.

Introduction

Planning for multiple agents in uncertain environments is a fundamental challenge in artificial intelligence. In a DEC-POMDP, agents must cooperate to achieve a common goal without full visibility of the state or perfect communication. Traditional optimal algorithms utilize Dynamic Programming (DP) to prune dominated strategies. However, these methods rely on Linear Programming (LP) to identify dominated policies across an infinite space of possible beliefs, making them computationally prohibitive and memory-intensive beyond very short horizons.

Methodology: Point-based Multi-agent DP

The authors adapt the "point-based" revolution from single-agent robotics to the multi-agent domain. The core contribution is Point-based Multi-agent DP, which consists of several key components:

  1. Multi-agent Belief States: The framework formally computes complex distributions where an agent maintains a belief about the world state and the concurrent actions of other agents.
  2. Exact Point-based DP: Rather than proving policy optimality for every possible belief, the algorithm identifies a finite set of "reachable" belief points—scenarios agents are likely to encounter—and optimizes specifically for those points.
  3. Eliminating Linear Programming: By evaluating policies at specific points, the algorithm replaces slow LP solvers with a "max" operator. If Policy A yields a higher value than Policy B at a specific point, it is retained.
  4. Approximation: To further enhance scalability, an approximate version samples prior joint policies and belief points instead of exhaustive generation.

Experimental Evaluation

The algorithms were evaluated on two benchmark DEC-POMDP problems: the Multi-access Broadcast Channel, where agents manage a shared channel without collisions, and the Multi-agent Tiger Problem, a cooperative puzzle requiring agents to open doors based on noisy observations.

Figure 2: Runtime comparison (log scale) showing the point-based approach is orders of magnitude faster than traditional DP as the horizon increases.

Key Results

The point-based approach demonstrated superior performance in both efficiency and scalability:

  • Scalability: On the Broadcast Channel problem, traditional DP failed at horizon $T=5$ due to memory constraints. In contrast, Exact PBDP solved $T=5$ efficiently, and the Approximate version scaled to $T=8$.
  • Efficiency: As shown in Figure 2, the runtime for point-based methods is significantly lower than previous DP methods, with the gap widening as the problem horizon grows.
  • Optimality: The Exact PBDP version remains optimal, while the Approximate version produces values very close to optimal solutions as shown in the performance tables.
Figure 4: Performance values for the Multi-access Broadcast Channel problem across different horizons.

Discussion and Future Work

While PBDP significantly outperforms standard DP, it does not always surpass heuristic search methods like MAA in specific problem structures like the Tiger problem. This suggests that the choice between DP and A-style search may depend on the specific characteristics of the environment. Future research directions include extending the framework to infinite-horizon problems and developing more sophisticated "active learning" strategies for belief point selection to further improve the approximate solver's performance.

Summary updated

BibTeX
@inproceedings{szer2006point,
  author = {Daniel Szer and François Charpillet},
  title = {{Point-based Dynamic Programming for DEC-POMDPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure