MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent Reinforcement Learning

Kefan Su, Siyuan Zhou, Chuang Gan, Xiangjun Wang, Zongqing Lu

TL;DR

MA2QL is a minimalist, theoretically grounded approach to decentralized multi-agent reinforcement learning (MARL) that solves the non-stationarity problem by having agents take turns updating their policies. By simply swapping two lines of code in standard Independent Q-Learning (IQL), the authors provide a method that consistently outperforms IQL and converges to a Nash equilibrium across a wide variety of complex cooperative tasks.

What Problem Does This Paper Address?

In cooperative MARL, agents must learn to work together to achieve a common goal. While Centralized Training with Decentralized Execution (CTDE) is popular, it requires a central entity to gather all agents' information during training. Fully decentralized learning, where agents learn using only local information, is more robust and scalable but faces a major hurdle: non-stationarity.

From the perspective of a single agent, the environment is constantly changing because other agents are also learning and updating their policies simultaneously. This breaks the Markov property that standard reinforcement learning relies on, often leading to unstable training and a failure to converge to a useful joint policy. The baseline approach, Independent Q-Learning (IQL), ignores this problem entirely, treating other agents as part of the static environment, which often results in poor performance in complex coordination tasks.

Methods

The authors propose Multi-Agent Alternate Q-Learning (MA2QL). The core idea is elegantly simple: to make the environment stationary for one agent, you must fix the policies of all other agents.

Instead of all agents updating their Q-functions at every step, agents take turns. While Agent A updates its policy, Agents B and C keep theirs fixed. Once Agent A reaches a certain level of convergence, it stops updating, and Agent B takes its turn.

The "Two-Line Swap": Comparing the loops of IQL and MA2QL.

As shown in the figure above, the implementation requires a "minimalist" change to IQL—essentially just reordering the interaction and update loops.

The authors provide a theoretical foundation for this approach, proving that if each agent achieves $\varepsilon$-convergence during its turn, the joint policy is guaranteed to converge to a Nash equilibrium. This process is illustrated as an iteration over different Markov Decision Processes (MDPs), as each agent's turn effectively defines a new stationary environment based on the fixed policies of the others.

Figure 1: Illustration of multi-agent alternate policy iteration (upper panel) and multi-agent alternate Q-iteration (lower panel) of three agents. As essentially the MDP differs at different turns of each agent, policy iteration/Q-iteration of each agent iterates over different MDPs.

Datasets

The researchers evaluated MA2QL across four distinct environments to test its versatility:

  1. Didactic Game: A custom-generated cooperative stochastic game with 30 states and 3 agents, used to verify basic convergence properties.
  2. Multi-Agent Particle Environments (MPE): Tasks like "simple spread," "line control," and "circle control" using sparse rewards to increase difficulty.
  3. Multi-Agent MuJoCo: Complex robotic control tasks (e.g., HalfCheetah, Hopper, Walker2d) adapted for multi-agent coordination in continuous action spaces.
  4. StarCraft Multi-Agent Challenge (SMAC): A popular benchmark for MARL, testing the algorithm on maps of varying difficulty (3s_vs_4z, 5m_vs_6m, and the "corridor" map).

Key Insights and Ideas

  • Stationarity via Alternation: The most fundamental way to fix a moving target is to stop it from moving. By alternating updates, MA2QL transforms a non-stationary multi-agent problem into a sequence of stationary single-agent problems.
  • Replay Buffer Stability: In deep RL, MA2QL benefits from a more stable replay buffer. Because only one agent changes at a time, the data stored in the buffer has less variance in the joint policy, leading to more reliable target values during training.
  • Minimalist but Effective: The fact that a two-line code change can significantly outperform complex CTDE-based methods suggests that decentralized learning has been underexplored and that simple coordination mechanisms can be highly powerful.
  • Scalability: The method scales well to many agents. The authors successfully demonstrated MA2QL on a 17-agent Humanoid task in MuJoCo, where IQL struggled to maintain stability.

Key Results

MA2QL consistently outperformed IQL across all benchmarks:

  • Speed and Optimality: In the didactic game, MA2QL converged in fewer than 100 steps, whereas IQL took roughly 2000 steps and reached a lower final reward.
  • Continuous Control: In Multi-Agent MuJoCo, MA2QL showed dramatic improvements. For instance, in the 3x1 Hopper task, MA2QL reached high episode rewards while IQL failed to learn effective coordination entirely.
  • Robustness: MA2QL proved robust to different update orders (e.g., fixed vs. random) and various hyperparameters like learning rates and batch sizes.
Learning curves on the didactic game comparing MA2QL to IQL and the global optimum.

As seen in Figure 2(b) above, MA2QL (red line) tracks the optimal solution (dashed green) much more closely and rapidly than IQL (blue line).

Limitations and Future Work

  • Nash vs. Global Optimum: While the authors prove convergence to a Nash equilibrium, they acknowledge that in cooperative games, there may be many Nash equilibria, and MA2QL is not guaranteed to find the globally optimal one.
  • Update Scheduling: The requirement for a pre-defined update schedule might be a hurdle in some ad-hoc decentralized scenarios where agents cannot easily coordinate their "turns."
  • Deep RL Theory Gap: The convergence proof is strictly for the tabular case. While empirical results in deep RL are strong, the interaction between alternate updates and deep neural networks (especially with shared replay buffers) warrants further theoretical study.
  • Extension to Actor-Critic: The authors suggest that the "alternate update" principle could be applied to other algorithms like PPO, which they briefly demonstrated with a "MA2PPO" variant that also outperformed its independent counterpart.

Summary updated

Abstract

Decentralized learning has shown great promise for cooperative multi-agent reinforcement learning (MARL). However, non-stationarity remains a significant challenge in fully decentralized learning. In the paper, we tackle the non-stationarity problem in the simplest and fundamental way and propose multi-agent alternate Q-learning (MA2QL), where agents take turns updating their Q-functions by Q-learning. MA2QL is a minimalist approach to fully decentralized cooperative MARL but is theoretically grounded. We prove that when each agent guarantees $\varepsilon$-convergence at each turn, their joint policy converges to a Nash equilibrium. In practice, MA2QL only requires minimal changes to independent Q-learning (IQL). We empirically evaluate MA2QL on a variety of cooperative multi-agent tasks. Results show MA2QL consistently outperforms IQL, which verifies the effectiveness of MA2QL, despite such minimal changes.
BibTeX
@misc{su2022ma,
  author = {Kefan Su and Siyuan Zhou and Chuang Gan and Xiangjun Wang and Zongqing Lu},
  title = {{MA2QL: A Minimalist Approach to Fully Decentralized Multi-Agent Reinforcement Learning}},
  year = {2022},
  eprint = {2209.08244},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.08244},
}
Figure