Probabilistic Inference Techniques for Scalable Multiagent Decision Making

Akshat Kumar, Shlomo Zilberstein, Marc ToussaintJAIR 2015 · DOI · OpenReview

TL;DR

This paper tackles the scalability problem of multiagent decision-making by reformulating Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) as inference problems in dynamic Bayesian networks (DBNs). By leveraging machine learning techniques like Expectation-Maximization (EM) and identifying a "value factorization" property, they achieve significant speedups and enable planning for systems with dozens of agents, outperforming previous methods.

What Problem Does This Paper Address?

Multiagent sequential decision-making, where multiple agents must coordinate their actions under uncertainty to achieve a common goal, is often modeled using Dec-POMDPs. These models are incredibly expressive, allowing for complex coordination scenarios. However, their computational complexity is extremely high (NEXP-Complete even for just two agents), making them intractable for real-world problems involving more than a handful of agents. This paper aims to bridge this gap by developing scalable algorithms that can handle larger multiagent systems.

Methods

The core of the paper's approach is a "planning-as-inference" paradigm. They achieve this by:

  • Reformulating Dec-POMDPs as DBN Mixtures: They transform the planning problem into an inference problem within a mixture of dynamic Bayesian networks. This allows them to leverage powerful probabilistic inference techniques.
  • Expectation-Maximization (EM) Algorithm: They apply the EM algorithm to learn the parameters of the agents' policies (represented as finite-state controllers, FSCs) by maximizing the likelihood of observed rewards. EM is an "anytime" algorithm, meaning it improves its solution iteratively.
  • Value Factorization Property: They identify a crucial property called "value factorization" that holds for many existing multiagent planning models. This property allows the overall problem to be decomposed into smaller, more manageable subproblems (value factors).
  • Decomposition of Inference: By exploiting value factorization, the computationally intensive inference required for the EM algorithm can be decomposed into independent computations for each value factor. This significantly reduces the complexity and enables scalability.
  • Message Passing: The decomposed inference is implemented using a parallel, distributed message-passing framework on a "value-factor graph," making it well-suited for large, distributed multiagent systems.

Datasets

The paper evaluates their approach on several standard multiagent planning benchmarks, including:

  • Broadcast channel
  • Recycling robots
  • Meeting on a grid
  • Multi-agent tiger
  • Box pushing
  • Mars rovers
  • Sensor network benchmarks (5P, 11H, 15-3D, 20D)

These benchmarks vary in size and complexity, with the sensor network problems being particularly challenging due to large state spaces and the need for agents to manage internal states like battery levels.

Key Insights and Ideas

  • Planning is Inference: The paper demonstrates a powerful connection between multiagent planning and machine learning inference. By framing planning as an inference problem, they unlock a wealth of efficient algorithms from the ML community.
  • Value Factorization is Key to Scalability: The identification and exploitation of the value factorization property is the central mechanism for achieving scalability. It allows the problem to be broken down into independent subproblems, avoiding exponential complexity.
  • EM's Anytime Property is Beneficial: The EM algorithm's ability to iteratively improve solutions is valuable in multiagent settings where finding an exact optimal solution is often infeasible.
  • Stochastic Controllers Outperform Deterministic Ones: The EM algorithm naturally produces stochastic controllers, which the authors argue can achieve better solution quality than deterministic controllers.

Key Results

  • Scalability: The proposed EM-based approach scales linearly with the number of edges in the agent interaction graph and can handle systems with up to 20 agents, significantly outperforming previous methods that struggled beyond 5 agents.
  • Runtime: For smaller problems, EM is competitive with or faster than state-of-the-art NLP solvers. For larger problems, it offers a substantial speedup. For instance, in the 20D sensor network benchmark, parallel EM achieved near-linear speedup.
  • Solution Quality: EM consistently achieved comparable or better solution quality than existing methods like DEC-BPI and NLP, often by a significant margin, especially in more complex scenarios. For example, in the "recycling robots" problem, EM achieved a ~20% improvement over NLP.
  • Generality: The value factorization framework is shown to be satisfied by several existing multiagent planning models (e.g., Transition-Independent Dec-MDPs, ND-POMDPs, TD-POMDPs), demonstrating the broad applicability of their approach.

Limitations and Future Work

  • Local Optima: The EM algorithm, like many optimization techniques, is not guaranteed to find the global optimum, but rather converges to a stationary point of the likelihood function. While EM's local optima are more stringent (stationary points), escaping them is an area for future work.
  • Reward Scaling: The paper notes that the scaling of rewards using Rmax and Rmin can significantly impact the policy value, which can be a drawback in certain scenarios.
  • Future Work: The authors suggest exploring:
  • Extending the approach to continuous action and state spaces.
  • Investigating strategies to escape local optima.
  • Developing methods for marginal MAP inference to provide quality guarantees.
  • Exploring the overlap with stochastic control theory for multiagent planning.

Summary updated

Abstract

Decentralized POMDPs provide an expressive framework for multiagent sequential decision making. However, the complexity of these models---NEXP-Complete even for two agents---has limited their scalability. We present a promising new class of approximation algorithms by developing novel connections between multiagent planning and machine learning. We show how the multiagent planning problem can be reformulated as inference in a mixture of dynamic Bayesian networks (DBNs). This planning-as-inference approach paves the way for the application of efficient inference techniques in DBNs to multiagent decision making. To further improve scalability, we identify certain conditions that are sufficient to extend the approach to multiagent systems with dozens of agents. Specifically, we show that the necessary inference within the expectation-maximization framework can be decomposed into processes that often involve a small subset of agents, thereby facilitating scalability. We further show that a number of existing multiagent planning models satisfy these conditions. Experiments on large planning benchmarks confirm the benefits of our approach in terms of runtime and scalability with respect to existing techniques.
BibTeX
@article{kumar2015probabilistic,
  author = {Akshat Kumar and Shlomo Zilberstein and Marc Toussaint},
  title = {{Probabilistic Inference Techniques for Scalable Multiagent Decision Making}},
  journal = {J. Artif. Intell. Res.},
  year = {2015},
  doi = {10.1613/jair.4649},
}
Figure