Generalization in Cooperative Multi-Agent Systems

Anuj Mahajan, Mikayel Samvelyan, Tarun Gupta, Benjamin Ellis, Mingfei Sun, Tim Rocktäschel, Shimon Whiteson

Abstract

Collective intelligence is a fundamental trait shared by several species of living organisms, allowing them to thrive in diverse environmental conditions. Natural systems, from ant colonies to human groups, exhibit a high degree of generalization when the abilities or the total number of agents changes—a phenomenon termed Combinatorial Generalization (CG). While recent works have shown impressive results on complex domains, they often lack performance guarantees for novel situations. In this work, we shed light on the theoretical underpinnings of CG for cooperative multi-agent systems (MAS). We study generalization bounds under a linear dependence of underlying dynamics on agent capabilities, extending Successor Features to MAS. We further generalize these results to Lipschitz and arbitrary reward dependencies. Finally, empirical analysis across various domains highlights critical desiderata for multi-agent algorithms to ensure robust CG.

Introduction: The Challenge of Combinatorial Generalization

In the natural world, collective intelligence is remarkably flexible. If a player is injured in a football match, the team adjusts roles; if an ant colony grows, workers redistribute tasks. In contrast, most Multi-Agent Reinforcement Learning (MARL) agents are brittle. Training a team of three agents and then changing one agent's "speed" stat or adding a fourth teammate often leads to system failure, requiring retraining from scratch.

This gap is a lack of Combinatorial Generalization. The challenge is three-fold:

  1. Infinite Possibilities: Agent capabilities (e.g., torque, speed) can exist on a continuous spectrum.
  2. Combinatorial Explosion: The number of possible team compositions is astronomical.
  3. The Grounding Problem: Agents must not only receive information about teammates' abilities but also understand how those abilities affect environment dynamics and team success.

Theoretical Framework

The researchers model environment dynamics (transitions and rewards) as a function of agent capability vectors. By assuming rewards and state transitions depend linearly on these capabilities, they extend the Successor Features (SF) framework—a popular single-agent transfer learning method—to the multi-agent domain.

Empirical verification of theoretical performance bounds (Theorems 1-3) in the Fruit Forage domain.

Several key theorems provide upper bounds on performance loss when transferring policies between teams, substituting agents, or changing population sizes. Recognizing real-world non-linearity, these bounds are extended to cases where rewards are Lipschitz continuous (where small capability changes lead to bounded reward changes) and cases where dynamics are only approximately linear.

Empirical Evaluation

The theories were evaluated across three distinct environments:

  1. Fruit Forage: A grid world used to verify that empirical performance gaps stay strictly within the theoretical "red zones" defined by the upper bounds.
  2. Predator-Prey: A coordination task where predators must hunt prey. Success requires the sum of predators' hit-point capabilities to exceed the prey's health.
  3. StarCraft Multi-Agent Challenge (SMAC): A modified benchmark introducing "unit swapping" (e.g., novel combinations of Marines, Marauders, and Medivacs) and "continuous capability variations" (randomized health and accuracy).
Performance comparison of MARL algorithms across various SMAC scenarios, showing mean test win rates and return gaps.

Key Results and Insights

  • Grounding is the Bottleneck: Experiments reveal that providing agents with teammate stats is insufficient. In complex tasks like StarCraft, agents often ignore this information because they haven't learned its "semantics"—how a 10% drop in a teammate's health should change their own tactical positioning.
  • Algorithm Performance: Value-based methods like QMIX and VDN generally showed better grounding of teammate capabilities than policy-gradient methods like MAPPO, leading to smaller generalization gaps in the Predator-Prey environment.
  • The "Hard" SMAC Barrier: On difficult StarCraft scenarios where certain unit types were never seen together during training, all current MARL baselines struggled, highlighting CG as a significant frontier for the field.

Limitations and Future Work

A significant limitation is the reliance on linear or near-linear dependence of dynamics on capabilities. Many real-world interactions involve non-linear "tipping points." Future research should focus on developing better grounding mechanisms (e.g., auxiliary tasks like predicting forward dynamics), learning latent embeddings of agent capabilities, and refining mathematical bounds for more complex, non-linear interactions.

Summary updated

Abstract

Collective intelligence is a fundamental trait shared by several species of living organisms. It has allowed them to thrive in the diverse environmental conditions that exist on our planet. From simple organisations in an ant colony to complex systems in human groups, collective intelligence is vital for solving complex survival tasks. As is commonly observed, such natural systems are flexible to changes in their structure. Specifically, they exhibit a high degree of generalization when the abilities or the total number of agents changes within a system. We term this phenomenon as Combinatorial Generalization (CG). CG is a highly desirable trait for autonomous systems as it can increase their utility and deployability across a wide range of applications. While recent works addressing specific aspects of CG have shown impressive results on complex domains, they provide no performance guarantees when generalizing towards novel situations. In this work, we shed light on the theoretical underpinnings of CG for cooperative multi-agent systems (MAS). Specifically, we study generalization bounds under a linear dependence of the underlying dynamics on the agent capabilities, which can be seen as a generalization of Successor Features to MAS. We then extend the results first for Lipschitz and then arbitrary dependence of rewards on team capabilities. Finally, empirical analysis on various domains using the framework of multi-agent reinforcement learning highlights important desiderata for multi-agent algorithms towards ensuring CG.
BibTeX
@misc{mahajan2022generalization,
  author = {Anuj Mahajan and Mikayel Samvelyan and Tarun Gupta and Benjamin Ellis and Mingfei Sun and Tim Rocktäschel and Shimon Whiteson},
  title = {{Generalization in Cooperative Multi-Agent Systems}},
  year = {2022},
  eprint = {2202.00104},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.00104},
}
Figure