Abstract
In multi-agent reinforcement learning (MARL), the epsilon-greedy method plays an important role in balancing exploration and exploitation during the decision-making process in value-based algorithms. However, the epsilon-greedy exploration process will introduce conservativeness when calculating the expected state value when the agents are more in need of exploitation during the approximate policy convergence, which may result in a suboptimal policy convergence. Besides, eliminating the epsilon-greedy algorithm leaves no exploration and may lead to unacceptable local optimal policies. To address this dilemma, we use the previously collected trajectories to construct a Monte-Carlo Trajectory Tree, so that an existing optimal template, a sequence of state prototypes, can be planned out. The agents start by following the planned template and act according to the policy without exploration, Stable Prefix Policy. The agents will adaptively dropout and begin to explore by following the epsilon-greedy method when the policy still needs exploration. We scale our approach to various value-based MARL methods and empirically verify our method in a cooperative MARL task, SMAC benchmarks. Experimental results demonstrate that our method achieves not only better performance but also faster convergence speed than baseline algorithms within early time steps.
Introduction
Value-based multi-agent reinforcement learning (MARL) typically relies on the $\epsilon$-greedy method to balance exploration and exploitation. While effective in single-agent settings, this approach introduces significant noise in multi-agent environments. When one agent explores randomly, it can negatively impact the expected value calculations for the entire team, often leading to safe but suboptimal "local optima."
Furthermore, random exploration at every step makes reaching distant, complex goals statistically improbable. The authors argue that agents require a "stable" start to their episodes to reach the frontiers of known successful strategies before initiating experimentation.
The Stable Prefix Policy (SPP) Framework
To address these challenges, the researchers introduced the Stable Prefix Policy (SPP), a "plug-in" architecture designed to stabilize early-episode decision-making. The framework consists of several key components:
- Monte-Carlo Trajectory Tree (MCT$^2$): Historical data from the replay buffer is used to build a tree where nodes represent clusters of similar states (grouped via K-Means). This preserves the structural essence of successful past runs.
- Trajectory Planning: Using a variant of the Upper Confidence Bound (PUCB) algorithm, agents plan an "optimal template"—a sequence of state prototypes representing a successful path.
- The Stable Prefix: At the start of a rollout, agents follow this template greedily without random noise.
- Adaptive Dropout: If the environment's state deviates from the template or the template concludes, agents "dropout" and switch to standard $\epsilon$-greedy exploration.
- Selective Assemble Function: During training, target $Q$-values are assembled from similar trajectory segments across the batch, reducing error propagation in value decomposition.
Experimental Evaluation
The method was evaluated on the StarCraft Multi-Agent Challenge (SMAC), testing on maps ranging from "Hard" (e.g., 1c3s5z, 5m_vs_6m) to "Super-Hard" (e.g., 3s5z_vs_3s6z, 6h_vs_8z).
Key findings include:
- Superior Performance and Convergence: SPP-enhanced algorithms (like QMIX+SPP) consistently outperformed vanilla counterparts and baselines like MAPPO. Convergence was significantly faster, often reaching high win rates within the first 2 million time steps.
- Handling Complexity: The gains were most pronounced in "Super-Hard" tasks where standard baselines often failed to achieve any significant win rate.
- Stability: SPP reduced training variance, providing smoother learning curves compared to the erratic behavior of standard exploration.
Discussion and Future Work
While SPP significantly improves MARL performance, it remains dependent on the presence of some successful trajectories in the replay buffer to initialize the MCT$^2$. If the task is so difficult that agents never succeed initially, the tree may lack useful prefixes. Future research could explore "re-entry" strategies for agents that have deviated from a template, or move toward more prescriptive exploration methods in the later stages of trajectories.
Summary updated