Improving Multi-agent Reinforcement Learning with Stable Prefix Policy

Yue Deng, Zirui Wang, Yin Zhang, Gianmarco Parretti

Abstract

Standard exploration techniques in multi-agent reinforcement learning (MARL), such as $\epsilon$-greedy, often lead to sub-optimal local optima due to the "conservativeness trap." This paper introduces the Stable Prefix Policy (SPP), a novel plugin for value-based MARL that utilizes historical data to plan stable, high-performing initial trajectories. By following a "stable prefix" planned via a Monte-Carlo Trajectory Tree ($MCT^2$), agents can reach complex joint states before switching to exploration. Empirical evaluations on the StarCraft Multi-Agent Challenge (SMAC) show that SPP enhances convergence speed and performance across various hard and super-hard maps.

Introduction

In value-based MARL, balancing exploration and exploitation is critical. However, the common $\epsilon$-greedy method often fails in complex coordination tasks. Random exploration early in a trajectory can distort the joint value function ($Q_{tot}$), leading agents to settle for safe but sub-optimal strategies. Furthermore, consistent noise throughout an episode makes it difficult for agents to reach distant, complex goals. This paper addresses these challenges by proposing a two-phase decision-making process that prioritizes stability at the start of each episode.

Methods

The Stable Prefix Policy (SPP) operates as a modular plugin for existing MARL frameworks. It breaks decision-making into two distinct phases: the Stable Prefix and Adaptive Dropout.

Technical Architecture

Agents first follow a "template"—a sequence of state prototypes planned from successful historical trajectories. This template is greedily followed without exploration noise until the agent encounters a state that deviates significantly from the plan, triggering a "dropout" into standard $\epsilon$-greedy exploration.

Overview of the SPP architecture, showing the integration of MCT² planning and the selective assemble function.

Key components include:

  • State Clustering: K-Means clustering is used to group similar states into manageable "clusters."
  • Monte-Carlo Trajectory Tree ($MCT^2$): A tree structure where nodes represent state clusters. Using data from the replay buffer, the system employs a Predictor Upper Confidence Bound (PUCB) algorithm to identify the most promising paths.
  • Selective Assemble Function: This function reduces value function error by averaging $Q$-values from trajectories sharing the same cluster ID, accelerating the learning process.

Experimental Results

The SPP framework was evaluated on the StarCraft Multi-Agent Challenge (SMAC), focusing on hard and super-hard maps such as 6h_vs_8z and MMM2.

Visualization of agent trajectories under the Stable Prefix Policy, illustrating the coordinated paths before exploration.

Key Findings

  • Performance Gains: SPP-enhanced algorithms achieved significantly higher win rates in super-hard scenarios where standard baselines like QMIX often stalled.
  • Efficiency: The method reached high win rates within the first 2 million time steps, demonstrating much faster convergence than traditional methods.
  • Stability: In scenarios like 3s_vs_5z, SPP showed lower variance across training runs, indicating a more robust learning process.

Conclusion

SPP offers a powerful solution to the conservativeness trap in MARL by treating the replay buffer as a structural map for high-level planning rather than just a collection of samples. While its performance is sensitive to clustering quality, its modular nature allows it to be easily integrated into various existing MARL algorithms to improve coordination and long-term strategy execution.

Summary updated

BibTeX
@inproceedings{deng2024improving,
  author = {Yue Deng and Zirui Wang and Yin Zhang and Gianmarco Parretti},
  title = {{Improving Multi-agent Reinforcement Learning with Stable Prefix Policy}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=2RqsOe5HYs},
}

Loading related content...

Figure