Monte-Carlo Expectation Maximization for Dec-POMDPs

IJCAI 2013

TL;DR

This paper introduces a novel model-free approach, Monte-Carlo Expectation Maximization (MCEM), for solving decentralized partially observable Markov decision processes (DEC-POMDPs). It addresses the limitations of existing methods that require complete model knowledge and struggle with scalability, demonstrating effective policy learning for problems with thousands of agents.

What Problem Does This Paper Address?

Decentralized Partially Observable Markov Decision Processes (DEC-POMDPs) are a powerful framework for modeling multi-agent coordination and decision-making under uncertainty. However, solving them optimally or even approximately is notoriously difficult. Existing state-of-the-art solvers often suffer from two major drawbacks:

  1. Complete Model Knowledge Requirement: They demand full knowledge of the system's dynamics, including transition probabilities, observation functions, and reward functions. This is often impractical in real-world scenarios where these models are complex and hard to obtain.
  2. Scalability Issues: The computational complexity of DEC-POMDPs grows exponentially with the number of agents and the problem horizon. This makes existing methods infeasible for large-scale multi-agent systems.

The paper aims to overcome these limitations by developing a model-free algorithm that can learn effective policies for DEC-POMDPs, even in domains with a vast number of agents.

Methods

The core contribution of this paper is the development of a Monte-Carlo Expectation Maximization (MCEM) algorithm for infinite-horizon DEC-POMDPs. This approach builds upon recent work that reformulates planning as a likelihood maximization problem, solvable by Expectation-Maximization (EM).

Here's a breakdown of their method:

  • Model-Free Approach: Unlike traditional methods, MCEM does not require prior knowledge of the DEC-POMDP model. Instead, it learns policies by interacting with the environment (or a simulator) and collecting trajectory samples.
  • Expectation-Maximization (EM) Framework: The algorithm uses the EM framework to iteratively refine policy parameters. The EM algorithm consists of two steps:
  • E-step (Expectation): This step estimates the expected value of the objective function given the current policy. In the MCEM variant, this expectation is approximated using Monte Carlo sampling of trajectories.
  • M-step (Maximization): This step updates the policy parameters to maximize the expected objective function estimated in the E-step.
  • Efficient Sampling Techniques: A naive application of MCEM to DEC-POMDPs is inefficient due to the enormous joint policy space. The authors introduce several improvements to the sampling process:
  • Importance Sampling: To reduce the cost of sampling, importance weights are used to correct for differences between the sampling distribution and the target distribution. This allows for more efficient use of collected samples.
  • Policy Exploration: To ensure adequate exploration of the policy space, they employ an ε-greedy strategy and a UCB-style heuristic for selecting controller nodes. This helps prevent the algorithm from getting stuck in suboptimal local optima.
  • Parallelization: The algorithm is designed to be parallelized using the MapReduce framework, enabling it to scale to very large problems by distributing the sampling and computation across multiple machines.

Datasets

The paper evaluates their algorithm on:

  • Common DEC-POMDP Benchmarks: Six standard benchmark problems are used to assess solution quality and runtime. These include: Broadcast Channel, Multi-Agent Tiger, Recycling Robots, Meeting on a Grid, Box Pushing, and Mars Rovers.
  • Traffic Control Domain: A large-scale traffic control problem is introduced and used to test the scalability of the algorithm. This domain features up to 2500 agents and is described as intractable for existing DEC-POMDP solvers.

Key Insights and Ideas

  • Bridging Model-Based and Model-Free: The paper successfully adapts the powerful EM framework, traditionally used in model-based settings, to a model-free context for DEC-POMDPs. This opens up new possibilities for applying these methods to real-world problems where models are unavailable.
  • Scalability through Sampling and Parallelism: The core innovation lies in making MCEM practical for large multi-agent systems. The combination of importance sampling, policy exploration, and MapReduce parallelization is crucial for achieving scalability.
  • Importance of Efficient Exploration: The paper highlights that simply sampling randomly is insufficient for complex DEC-POMDPs. Targeted exploration strategies are essential for finding good policies in vast policy spaces.
  • DEC-POMDPs as a Foundation for Complex Coordination: The success on the traffic control domain, with thousands of agents, demonstrates the potential of DEC-POMDPs and this new algorithm for tackling highly complex coordination tasks.

Key Results

  • Competitive Solution Quality: The MCEM algorithm achieves solution quality comparable to, and in some cases better than, the state-of-the-art model-based EM approach on common DEC-POMDP benchmarks.
  • Significant Scalability: The algorithm demonstrates remarkable scalability, successfully solving the traffic control problem with up to 2500 agents, which is considered intractable for existing methods.
  • Efficiency Gains: The importance sampling techniques significantly improve the efficiency of the MCEM algorithm compared to a naive sampling approach.
  • Runtime Performance: While model-based EM can be faster on very small problems, the runtime of MCEM grows more moderately with problem size, especially when considering the complexity of state spaces. The parallelization further enhances its practical applicability for large-scale problems.

Limitations and Future Work

  • Local Optima: Like standard EM algorithms, MCEM converges to local optima. The authors address this by restarting the algorithm multiple times with different initial policies.
  • Sample Size and Iterations: The paper suggests that the sample size and number of iterations can be adjusted based on the problem and convergence criteria, drawing on existing literature for guidance.
  • Future Work: The authors plan to extend their work to domains with continuous state and action spaces. They also aim to test the algorithm on more complex real-world applications like robot soccer and rescue scenarios, where fully functional simulators are available. This work is seen as a foundation for applying DEC-POMDP techniques to such challenging domains.

Summary updated

BibTeX
@inproceedings{2013monte,
  title = {{Monte-Carlo Expectation Maximization for Dec-POMDPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2013},
}
Figure