VAST: Value Function Factorization with Variable Agent Sub-Teams

Thomy Phan, Fabian Ritz, Lenz Belzner, Philipp Altmann, Thomas Gabor, Claudia Linnhoff-PopienNeurIPS 2021 · OpenReview

In the world of Multi-Agent Reinforcement Learning (MARL), getting a group of agents to work together toward a single global goal is notoriously difficult. How do you tell which agent's specific action led to a victory? This is known as the "credit assignment" problem. While Value Function Factorization (VFF) has been the go-to solution, it often hits a wall when the number of agents grows beyond a handful.

A team of researchers recently presented VAST (Value Function Factorization with Variable Agent Sub-Teams), offering a clever hierarchical workaround to this scaling bottleneck.

TL;DR

VAST introduces a hierarchical approach to value function factorization by grouping agents into dynamic, task-oriented sub-teams. By factorizing a global reward into sub-team values first, VAST alleviates the performance bottleneck of standard "flat" factorization methods, allowing cooperative AI to scale to dozens or even hundreds of agents.

What Problem Does This Paper Address?

Most state-of-the-art cooperative MARL algorithms use Value Function Factorization (VFF). The idea is simple: take a single global reward and "factorize" it into individual agent contributions. Popular methods like QMIX or QTRAN use a centralized "mixing network" to accomplish this.

However, these methods are usually tested on fewer than 10 agents. As the number of agents ($N$) increases, the mixing network becomes a performance bottleneck. It struggles to process the massive input space and provide a clear, informative training signal to every individual agent. In large-scale systems—like fleet management or industrial robotics—standard VFF often fails to learn anything useful at all.

Methods

The core innovation of VAST is moving from a "flat" hierarchy to a two-level structure:

Comparison of flat value function factorization versus VAST's hierarchical sub-team approach.
  1. Sub-Team Level: Agents are partitioned into $K$ sub-teams. The value of a sub-team is calculated as the simple linear sum of its members' individual values. This keeps the lower level simple and hyperparameter-free.
  2. Global Level: The global value function is then factorized from these $K$ sub-team values using a more complex operator (like QMIX or QTRAN).

Because $K$ (the number of sub-teams) is much smaller than $N$ (the total number of agents), the complex mixing network at the top level has a much more focused and compact input representation.

Dynamic Assignments: Crucially, these sub-teams aren't necessarily fixed. The authors propose several assignment strategies:

  • Random/Fixed: Simple baselines.
  • Spatial: Grouping agents based on their physical proximity in a grid-world.
  • Meta-Gradient ($\mathcal{X}_{MetaGrad}$): The most advanced version, where a separate meta-policy learns how to group agents to maximize the global return. This allows the system to adapt its organizational structure on the fly.

Datasets

The researchers evaluated VAST across three distinct domains designed to test scalability:

  • Warehouse[N]: A grid-world where $N$ robots must pick up and deliver orders while avoiding collisions. Tested up to $N=16$.
  • Battle[N]: A combat scenario where an army of $N$ agents fights an opponent army. This tests coordination under pressure. Tested up to $N=80$.
  • GaussianSqueeze[N]: A large-scale resource allocation problem. This is a "stress test" for coordination, scaled up to a massive $N=800$ agents.

Key Insights and Ideas

  • Hierarchy as a Bottleneck Breaker: The "aha moment" is realizing that the complexity of the factorization operator is the limiting factor. By introducing an intermediate linear layer (sub-teams), you effectively "compress" the problem for the non-linear mixer.
  • Emergent Roles: In the Battle domain, the learned meta-gradient strategy actually discovered meaningful tactical groupings.
Emergent tactical sub-teams in the Battle domain, showing fleeing and offensive behaviors.

As seen above, it created "fleeing" sub-teams to preserve health and "offensive" sub-teams to engage the enemy, switching between these structures as the battle progressed.

  • Decentralized Execution: Despite the centralized training hierarchy, VAST maintains "decentralizability." Once trained, each agent can still act based solely on its local observations.

Key Results

  • Superior Scalability: In the 80-agent Battle scenario and the 16-agent Warehouse task, standard VFF methods (QMIX, QTRAN) performed poorly or failed to improve. VAST variants significantly outperformed them, maintaining steady learning progress.
  • Efficiency in Extremes: In the GaussianSqueeze domain with 800 agents, VAST variants clearly outperformed all baselines, including Independent Learning (IL), which usually scales well but lacks coordination.
  • The Power of Adaptation: The Meta-Gradient approach ($\mathcal{X}_{MetaGrad}$) generally yielded the best performance, proving that learning how to organize the team is just as important as learning how to act.

Limitations and Future Work

  • Linear Constraints: Currently, sub-team values are just linear sums of member values. While this is efficient, the authors acknowledge that non-linear sub-team approximations (using Transformers or RNNs) might be necessary for even more complex environments.
  • Hyperparameter Tuning: The "sub-team ratio" ($\eta$)—which determines how many sub-teams to create—is currently a manual setting. The authors suggest that a self-tuning mechanism for this ratio would be a valuable future addition.
  • Computational Overhead: Learning sub-team assignments via meta-gradients adds a computational cost that scales linearly with the number of agents.

VAST represents a significant step toward making cooperative reinforcement learning practical for the "Many-Agent" era, moving beyond toy problems toward the scale of real-world infrastructure.

Summary updated

Abstract

Value function factorization (VFF) is a popular approach to cooperative multi-agent reinforcement learning in order to learn local value functions from global rewards. However, state-of-the-art VFF is limited to a handful of agents in most domains. We hypothesize that this is due to the flat factorization scheme, where the VFF operator becomes a performance bottleneck with an increasing number of agents. Therefore, we propose VFF with variable agent sub-teams (VAST). VAST approximates a factorization for sub-teams which can be defined in an arbitrary way and vary over time, e.g., to adapt to different situations. The sub-team values are then linearly decomposed for all sub-team members. Thus, VAST can learn on a more focused and compact input representation of the original VFF operator. We evaluate VAST in three multi-agent domains and show that VAST can significantly outperform state-of-the-art VFF, when the number of agents is sufficiently large.
BibTeX
@inproceedings{phan2021vast,
  author = {Thomy Phan and Fabian Ritz and Lenz Belzner and Philipp Altmann and Thomas Gabor and Claudia Linnhoff-Popien},
  title = {{VAST: Value Function Factorization with Variable Agent Sub-Teams}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Xa7UZR13zf},
}
Figure