Efficient Planning for Factored Infinite-Horizon DEC-POMDPs

Joni Pajarinen, Jaakko PeltonenIJCAI 2011 · OpenReview

Abstract

Decentralized partially observable Markov decision processes (DEC-POMDPs) are used to plan policies for multiple agents that must maximize a joint reward function but do not communicate with each other. The agents act under uncertainty about each other and the environment. This planning task arises in optimization of wireless networks, and other scenarios where communication between agents is restricted by costs or physical limits. DEC-POMDPs are a promising solution, but optimizing policies quickly becomes computationally intractable when problem size grows. Factored DEC-POMDPs allow large problems to be described in compact form, but have the same worst case complexity as non-factored DEC-POMDPs. We propose an efficient optimization algorithm for large factored infinite-horizon DEC-POMDPs. We formulate expectation-maximization based optimization into a new form, where complexity can be kept tractable by factored approximations. Our method performs well, and it can solve problems with more agents and larger state spaces than state of the art DEC-POMDP methods. We give results for factored infinite-horizon DEC-POMDP problems with up to 10 agents.

Introduction

Planning for multiple agents that share a joint goal but cannot communicate is one of the most challenging problems in multi-agent systems. These scenarios are formally modeled as Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs). They are critical for applications like autonomous robotics and wireless network optimization, where agents must make local decisions under uncertainty while accounting for the potential actions of others.

Mathematically, DEC-POMDPs are NEXP-complete, meaning the computational effort required to find an optimal policy grows exponentially with the number of agents and state variables. While "factored" models can represent large problems compactly by breaking the environment into interacting components, dependencies between variables typically "bleed" into each other over time. This phenomenon, known as the "curse of history," eventually makes factored problems as difficult as non-factored ones. Consequently, current state-of-the-art methods often fail when problems exceed a handful of agents.

Methodology: Factored EM with Forward Projections

The authors propose a novel Expectation-Maximization (EM) based approach specifically designed for factored infinite-horizon DEC-POMDPs. Their method introduces three key innovations to maintain tractability:

  1. Forward-Only Projection: Standard EM algorithms require both forward (alpha) and backward (beta) "messages" to update policies. The authors mathematically transform the update rules to require only forward projections. This transformation is crucial because it allows for efficient approximation techniques that would otherwise be impossible with backward messages.
  2. Factored Approximations (Boyen-Koller style): To prevent the state space representation from exploding, the algorithm maintains the probability distribution in a factored form during forward projection. They evaluate two clustering strategies: Fully Factored (treating every variable as independent) and Overlapping Clusters (grouping variables that directly influence each other).
  3. Stochastic Finite State Controllers (FSCs): Instead of calculating a policy for every possible history of observations, agent policies are represented as small, memory-efficient state machines.
Factored Dynamic Bayesian Network (DBN) representation for a two-device wireless network problem.

By forcing a factored structure at every time step, the algorithm achieves polynomial complexity relative to the number of state variables and agents, a significant departure from the exponential complexity of standard methods.

Experimental Setup

The algorithm was evaluated on two complex multi-agent benchmarks:

  • Factored Fire Fighting: $N$ robotic agents coordinate to extinguish fires in $N+1$ houses. The state space grows to $3^{N+1}$.
  • Wireless Network (Inline Aloha): $N$ devices manage packet buffers and transmit over a shared channel. The state space grows to $4^N 2^N$.

Configurations ranging from 2 to 10 agents were tested, comparing the proposed "Our1" and "Our2" methods against "Flat EM" and non-linear programming (NLP) baselines.

Results and Discussion

The most significant result is the algorithm's scalability. While standard "Flat EM" and NLP methods ran out of memory or failed to converge once the agent count reached 4 or 5, the proposed factored EM method successfully solved 10-agent problems.

Performance comparison (Negative Average Discounted Reward) across different agent counts for Fire Fighting and Wireless Network benchmarks.

Key insights from the results include:

  • Efficiency vs. Accuracy: On smaller problems where exact solutions were possible, the factored approximations performed comparably to exact methods, suggesting that the loss in accuracy from forcing factorization is minimal compared to the massive gain in scalability.
  • Local Interactions: The method excels in problems where interactions are local (e.g., wireless nodes only interfering with neighbors). In these cases, the "cliques" in the underlying Bayesian network remain small, keeping the computation tractable.

Conclusion

This work demonstrates that by maintaining a factored representation of the belief state during policy optimization, it is possible to solve DEC-POMDPs with significantly more agents than previously possible. While the method lacks formal optimality guarantees due to the nature of the approximations, it consistently converges to high-quality, stable solutions in practice. Future work will focus on establishing formal optimality bounds for these types of factored approximations to better understand the theoretical trade-offs between accuracy and scalability.

Summary updated

Abstract

Decentralized partially observable Markov decision processes (DEC-POMDPs) are used to plan policies for multiple agents that must maximize a joint reward function but do not communicate with each other. The agents act under uncertainty about each other and the environment. This planning task arises in optimization of wireless networks, and other scenarios where communication between agents is restricted by costs or physical limits. DEC-POMDPs are a promising solution, but optimizing policies quickly becomes computationally intractable when problem size grows. Factored DEC-POMDPs allow large problems to be described in compact form, but have the same worst case complexity as non-factored DEC-POMDPs. We propose an efficient optimization algorithm for large factored infinite-horizon DEC-POMDPs. We formulate expectation-maximization based optimization into a new form, where complexity can be kept tractable by factored approximations. Our method performs well, and it can solve problems with more agents and larger state spaces than state of the art DEC-POMDP methods. We give results for factored infinite-horizon DEC-POMDP problems with up to 10 agents.
BibTeX
@inproceedings{pajarinen2011efficient,
  author = {Joni Pajarinen and Jaakko Peltonen},
  title = {{Efficient Planning for Factored Infinite-Horizon DEC-POMDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=SkbV7QMdWr},
}
Figure