Compact Mathematical Programs For DEC-MDPs With Structured Agent Interactions

Hala Mostafa, Victor R. LesserUAI 2011

TL;DR

This paper introduces a more efficient way to model and solve complex multi-agent decision-making problems by exploiting structured interactions. They propose a compact Mixed Integer Linear Program (MILP) formulation that significantly reduces the computational burden compared to existing methods, leading to faster solutions and better policy quality.

What Problem Does This Paper Address?

Decentralized Markov Decision Processes (DEC-MDPs) are powerful for modeling scenarios where multiple agents make decisions independently but with some interdependencies. However, finding optimal policies in these systems is computationally prohibitive due to the sheer complexity. Existing models either ignore these structured interactions, leading to inefficiencies, or use formulations that are too verbose or lack optimality guarantees. This paper focuses on a specific type of structured interaction called Event-Driven Interactions with Complex Rewards (EDI-CR), where agents are mostly independent except for a few actions that influence others' transitions or rewards. The challenge is to create a mathematical program that accurately captures EDI-CR while being computationally tractable.

Methods

The core contribution is a novel compact Mixed Integer Linear Program (MILP) formulation for EDI-CR. The key insight is that for a given agent, many different sequences of actions by other agents can have the same effect on its transitions and rewards. Instead of creating a variable for every possible combination of other agents' histories (as in general DEC-MDP MILPs), this paper proposes "binning" these histories. Histories that have the same impact are grouped into a single "bin." A single variable is then introduced for each history of an agent and each bin it influences. This significantly reduces the number of variables needed.

For the 2-agent case, they introduce a MILP formulation that uses these bins to create variables representing the joint probability of an agent taking a specific history and the other agent's history falling into a particular bin. They then derive linear constraints to enforce the identity that these bin variables should equal the product of the individual agent's history probabilities.

For the 3-or-more agent case, the problem becomes more complex. They extend the binning idea but face challenges in creating tight linear constraints that enforce the identity. They propose a set of linear constraints that provide an upper bound, acknowledging that this results in a relaxed version of the problem, which might overestimate the optimal reward but still yields a legal policy.

Datasets

The paper evaluates their approach using instances of the modified Mars rovers problem. This benchmark involves multiple rovers that need to visit sites and collect samples. The interactions arise when one rover's actions (e.g., visiting a site) can affect the probability of another rover successfully processing a dependent site or collecting complementary/redundant samples. The authors used 22 instances for the 2-agent case and 25 instances for the 3-agent case, categorized by size.

Key Insights and Ideas

  • "Binning" is the key: The most crucial insight is that many distinct histories of other agents can have identical effects on a given agent. Grouping these histories into "bins" dramatically reduces the complexity of the problem representation.
  • Structured interactions are exploitable: Unlike general DEC-MDPs, EDI-CR has a specific structure that can be leveraged for computational gains. This paper demonstrates a principled way to do so.
  • MILP offers optimality guarantees: By formulating the problem as an MILP, the authors can guarantee finding globally optimal solutions, unlike non-linear programming (NLP) approaches which can get stuck in local optima.
  • Relaxation for >2 agents is a practical trade-off: While the 2-agent formulation is exact, the 3-or-more agent formulation introduces a relaxation. This is a pragmatic choice to make the problem tractable, acknowledging that the solver might overestimate the reward but still finds a valid policy.

Key Results

  • Compactness: The proposed EDI-CR MILP formulation is significantly more compact than the general DEC-MDP MILP formulation, introducing far fewer variables. For example, in the 3-agent case, the number of variables for the EDI-CR MILP was orders of magnitude smaller than for the DEC-MDP MILP, which was often too large to even load into the solver.
  • Speed: The EDI-CR MILP formulation leads to substantially faster solution times. In the 2-agent case, it was significantly faster than both QP and DEC-MDP MILP formulations, especially for larger instances. For the 3-agent case, the MILP solver was orders of magnitude faster than the NLP solver.
  • Optimality: For the 2-agent case, the EDI-CR MILP achieved provably optimal solutions in a much higher percentage of instances (17/22) compared to the QP formulation. Even in cases where optimality wasn't verified within the timeout, the EDI-CR MILP often found better solutions.
  • Scalability: The compact formulation allows for solving larger and more complex problems that were intractable with previous methods.

Limitations and Future Work

  • Relaxation for >2 agents: The MILP for 3 or more agents is a relaxation, meaning it might overestimate the optimal reward. The authors suggest future work could focus on tightening these upper bounds to improve the correspondence between the relaxed problem and the original one.
  • Approximate Binning: The paper mentions that "approximately binning" histories (grouping similar-effect histories even if not perfectly identical) could further reduce the number of compound variables needed. This is a promising avenue for future research.
  • Unoptimized Implementation: The authors note that their current implementation is not optimized for speed, suggesting further performance improvements are possible.

Summary updated

BibTeX
@inproceedings{mostafa2011compact,
  author = {Hala Mostafa and Victor R. Lesser},
  title = {{Compact Mathematical Programs For DEC-MDPs With Structured Agent Interactions}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}
Figure