FM3Q: Factorized Multi-Agent MiniMax Q-Learning for Two-Team Zero-Sum Markov Game

Guangzheng Hu, Yuanheng Zhu, Haoran Li, Dongbin Zhao

TL;DR

FM3Q is a novel reinforcement learning framework that efficiently solves two-team zero-sum games by factorizing a complex joint minimax Q-function into manageable individual agent contributions. By bridging the gap between cooperative value decomposition and competitive game theory, it enables decentralized execution while significantly outperforming state-of-the-art population-based methods in both learning speed and strategic stability.

What Problem Does This Paper Address?

Many competitive scenarios—from team sports like soccer to tactical combat in video games—are modeled as two-team zero-sum Markov games (2t0sMGs). These games are notoriously difficult to solve because they require balancing two conflicting dynamics: intra-team cooperation (working with allies) and inter-team competition (defeating opponents).

Existing approaches often fall into two traps:

  1. The "Super-Agent" Trap: Treating an entire team as a single agent. This leads to a "combinatorial explosion" where the number of possible joint actions becomes too massive to compute.
  2. The "Independent Learner" Trap: Letting agents learn on their own. This often fails because it ignores "credit assignment"—the ability to determine which specific agent's action actually contributed to the team's success or failure.

The authors aim to create a method that is computationally efficient, supports decentralized decision-making, and handles credit assignment effectively.

Methods

The core of the paper is the Individual-Global-MiniMax (IGMM) principle. This is an extension of the "Individual-Global-Max" (IGM) principle used in cooperative multi-agent learning (like the popular QMIX algorithm).

The IGMM principle ensures that the optimal joint minimax action for the whole team is consistent with the individual greedy actions of each team member. To implement this, the authors developed FM3Q:

  • Factorized Q-Learning: It breaks down the global team Q-value into individual Q-values for each agent.
  • Monotonic Mixing with Negation: It uses a neural "mixing network" to combine these individual values. Crucially, it includes a negation module for the opponent team. This allows the network to represent the zero-sum relationship: what is good for the "Protagonists" is exactly as bad for the "Antagonists."
  • Centralized Training, Decentralized Execution (CTDE): Agents are trained together using global information but can act independently during a game using only their local observations.
The FM3Q architecture: individual Q-networks feed into a mixing network, with a negation module for the antagonist team to enforce the zero-sum property.

Datasets

The researchers evaluated FM3Q on three distinct multi-agent benchmarks:

  1. Wimblepong 2v2: A modified version of the classic Pong where two agents on each side must coordinate to control a single paddle.
  2. MPE 3v3 (Multi-agent Particle Environment): A physics-based world where teams of three compete to reach and hold a target area.
  3. RoboMaster 2v2: A high-fidelity simulation of robot combat, requiring agents to manage movement, health points, and ammunition while coordinating attacks.
Visualizations of the three experimental environments used to test FM3Q: Wimblepong, MPE, and RoboMaster.

Key Insights and Ideas

  • Factorization is Competitive: The biggest "aha" moment is that value decomposition—previously thought to be a tool for cooperation—can be mathematically adapted for adversarial games. By enforcing monotonicity, the model naturally learns to assign credit to the right agents.
  • The "Memory" Advantage: Unlike many population-based methods (like PSRO) that periodically discard old data, FM3Q thrives on a large replay buffer. The authors found that keeping a "full" history of past interactions prevents the agents from "forgetting" how to counter older strategies, leading to much more stable and less exploitable policies.
  • Efficiency over Complexity: By avoiding the need to solve complex linear programs for every state (a common requirement in Nash Q-learning), FM3Q scales much better as the number of agents increases.

Key Results

FM3Q demonstrated clear superiority over established baselines like Self-Play (SP), PSRO, and NXDO:

  • Faster Convergence: In Wimblepong, FM3Q reached a 0.5 winning rate in fewer than 2,000 episodes, whereas competitors required at least 4,000 to 6,000 episodes to reach the same level.
  • Higher Peak Performance: In the RoboMaster environment, FM3Q achieved a winning rate of approximately 0.7, significantly higher than the next best baseline (NXDO at ~0.55).
  • Lower Exploitability: Using the NashConv metric (which measures how far a strategy is from an un-beatable Nash Equilibrium), FM3Q consistently showed a downward trend toward zero, outperforming all other tested algorithms.
Performance comparison showing FM3Q's faster learning and higher final rewards/winning rates compared to other popular MARL methods.

Limitations and Future Work

While powerful, the authors note a few areas for improvement:

  • Deterministic Policies: FM3Q currently learns deterministic policies. However, some games (like Rock-Paper-Scissors) require stochastic (randomized) strategies to reach a true Nash Equilibrium. Future versions might incorporate stochastic policy methods.
  • Hardware Costs: To achieve its best performance, FM3Q requires storing and training on a massive amount of historical data, which can be memory-intensive for very large-scale games.
  • Data Filtering: The authors suggest that "quality filtering" of the data in the replay buffer could further improve training efficiency by removing low-quality or redundant samples.

Summary updated

Abstract

Many real-world applications involve some agents that fall into two teams, with payoffs that are equal within the same team but of opposite sign across the opponent team. The so-called two-team zero-sum Markov games (2t0sMGs) can be resolved with reinforcement learning in recent years. However, existing methods are thus inefficient in light of insufficient consideration of intra-team credit assignment, data utilization, and computational intractability. In this paper, we propose the individual-global-minimax (IGMM) principle to ensure the coherence between two-team minimax behaviors and the individual greedy behaviors through Q functions in 2t0sMGs. Based on it, we present a novel multi-agent reinforcement learning framework, Factorized Multi-Agent MiniMax Q-Learning (FM3Q), which can factorize the joint minimax Q function into individual ones and iteratively solve for the IGMM-satisfied minimax Q functions for 2t0sMGs. Moreover, an online learning algorithm with neural networks is proposed to implement FM3Q and obtain the deterministic and decentralized minimax policies for two-team players. A theoretical analysis is provided to prove the convergence of FM3Q. Empirically, we use three environments to evaluate the learning efficiency and final performance of FM3Q and show its superiority on 2t0sMGs.
BibTeX
@article{hu2024fm,
  author = {Guangzheng Hu and Yuanheng Zhu and Haoran Li and Dongbin Zhao},
  title = {{FM3Q: Factorized Multi-Agent MiniMax Q-Learning for Two-Team Zero-Sum Markov Game}},
  journal = {IEEE Trans. Emerg. Top. Comput. Intell.},
  year = {2024},
  url = {https://openreview.net/forum?id=ABEphz0nKh},
}

Loading related content...

Figure