Solving Multi-agent MDPs Optimally with Conditional Return Graphs

Joris Scharpff, Diederik M. Roijers, Frans A. Oliehoek, Matthijs T. J. Spaan, Mathijs de WeerdtUvA-DARE 2015

Abstract

In cooperative multi-agent sequential decision making under uncertainty, agents must coordinate to find an optimal joint policy that maximizes joint value. Typical solution algorithms exploit additive structure in the value function, but in the fully-observable multi-agent MDP setting (MMDP), such structure is not present. We propose a new optimal solver for Transition-Independent MMDPs (TI-MMDPs), where agents can only affect their local state, while their value may depend on the state of others. We decompose the returns into local returns per agent that we represent compactly in a conditional return graph (CRG). Using CRGs, the value of a joint policy as well as bounds on the value of partially specified joint policies can be efficiently computed. We propose CoRe, a novel branch-and-bound policy search algorithm building on CRGs. CoRe typically requires less runtime than available alternatives and is able to find solutions to problems previously considered unsolvable.

Introduction: The Curse of Dimensionality in Coordination

In cooperative multi-agent systems, agents must coordinate to maximize a shared team value. When every agent has full observability of the global state, the complexity of finding an optimal plan grows exponentially with the number of agents—a phenomenon known as the "curse of dimensionality" in Multi-agent Markov Decision Processes (MMDPs).

To address this, researchers often resort to approximations that sacrifice optimality or decentralization models that assume local-only information. While decentralization simplifies the math, it often results in significantly lower team value because agents cannot react to their teammates' actions. This paper targets Transition-Independent MMDPs (TI-MMDPs), where an agent’s actions only affect its own local state, but rewards depend on joint interactions. The goal is to find an optimal global policy without the exponential overhead.

Methodology: Factoring Returns via CRGs

The core innovation of this work is shifting the focus from factoring the complex global value function to factoring the execution returns.

Conditional Return Graphs (CRGs)

The authors represent an agent's rewards as a Directed Acyclic Graph (DAG) called a Conditional Return Graph. These graphs compactly store all possible local rewards and interactions. By using "wildcards" to group actions or state transitions that do not trigger reward interactions, the size of the graph is drastically reduced.

The CoRe Algorithm

CoRe (Conditional Return policy search) is a branch-and-bound algorithm that leverages CRGs to navigate the policy space efficiently. It uses CRGs to:

  1. Compute Bounds: Quickly estimate future rewards to prune suboptimal branches of the search tree.
  2. Detect Dynamic Decoupling: If groups of agents complete their interacting tasks, CoRe identifies them as "conditionally independent" and solves their remaining plans as smaller, independent sub-problems.
Comparison of standard policy search versus the CoRe algorithm using Conditional Return Graphs (CRGs).

Experimental Evaluation

The approach was evaluated using the Maintenance Planning Problem (MPP), a benchmark for infrastructure management.

  • mpp set: 1,200 random instances (2-4 agents) with varying horizons.
  • coordint set: 1,000 coordination-intensive instances designed to test the limits of decentralized vs. centralized planning.
  • pyra set: A "pyramid" interaction structure used to test scalability up to 10 agents.

Key Insights and Results

The Cost of Decentralization

A major finding is the quantification of value lost when using decentralized models (Dec-MDPs) instead of optimal centralized ones. In coordination-heavy tasks, decentralized policies were found to be 33% worse on average, and in extreme cases up to 75% worse, than the optimal policies found by CoRe.

The performance gap between decentralized (Dec-MDP) and optimal centralized (MMDP) policies across different problem sets.

Performance and Scalability

  • Efficiency: CoRe reduced the number of joint actions evaluated by approximately one order of magnitude compared to standard dynamic programming.
  • Speed: CoRe consistently outperformed SPUDD (a popular MDP solver). While SPUDD failed on 63.9% of certain test sets, CoRe successfully found optimal solutions.
  • Scalability: In the "pyramid" test, CoRe solved 10-agent problems with a horizon of 4, whereas previous state-of-the-art methods typically capped out at 5 agents.

Conclusion and Future Work

CoRe demonstrates that factoring returns through CRGs provides a powerful path to optimality in TI-MMDPs. While the current model assumes transition independence—fitting for resource-sharing problems but not for physically interactive environments like robot soccer—future work aims to extend CRGs to handle sparse transition dependencies. Additionally, exploring domain-specific heuristics for CRG construction could further enhance the algorithm's scalability and performance in multi-objective settings.

Summary updated

Abstract

In cooperative multi-agent sequential decision making under uncertainty, agents must coordinate in order find an optimal joint policy that maximises joint value. Typical solution algorithms exploit additive structure in the value function, but in the fully-observable multi-agent MDP setting (MMDP) such structure is not present. We propose a new optimal solver for so-called TI-MMDPs, where agents can only affect their local state, while their value may depend on the state of others. We decompose the returns into local returns per agent that we represent compactly in a conditional return graph (CRG). Using CRGs the value of a joint policy as well as bounds on the value of partially specified joint policies can be efficiently computed. We propose CoRe, a novel branch-and-bound policy search algorithm building on CRGs. CoRe typically requires less runtime than the available alternatives and is able to find solutions to problems previously considered unsolvable.
BibTeX
@inproceedings{scharpff2015solving,
  author = {Joris Scharpff and Diederik M. Roijers and Frans A. Oliehoek and Matthijs T. J. Spaan and Mathijs de Weerdt},
  title = {{Solving Multi-agent MDPs Optimally with Conditional Return Graphs}},
  booktitle = {UvA-DARE},
  year = {2015},
}
Figure