Source-linked AI summary
Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning
Jakob Foerster, Nantas Nardelli, Gregory Farquhar, Triantafyllos Afouras, Philip H. S. Torr, Pushmeet Kohli, Shimon Whiteson
TL;DR
Deep multi-agent RL needs replay for stable, sample-efficient learning, but independent Q-learning makes replayed experience stale because other agents change their policies. The paper proposes multi-agent importance sampling and low-dimensional fingerprints to address this mismatch. On decentralised StarCraft micromanagement, the methods enable successful combination of experience replay with multiagent Q-learning.
Problem
Independent Q-learning introduces nonstationarity that makes experience replay incompatible with deep multi-agent RL, limiting the transfer of replay-based deep-learning methods to complex cooperative tasks.
Method
The paper uses multi-agent importance sampling to decay obsolete data and conditions value functions on fingerprints containing training iteration and exploration information.
Results
The methods enable successful combination of experience replay with multiagent Q-learning on a challenging decentralised StarCraft unit-micromanagement benchmark.
Takeaways & Limitations
Experience replay can be combined with multi-agent RL when obsolete data is downweighted or disambiguated by information about training state.
Takeaways & Limitations
Importance sampling can have large, unbounded variance, while truncating or adjusting weights reduces variance at the cost of bias.
Abstract
from arXiv · showhide
Many real-world problems, such as network packet routing and urban traffic control, are naturally modeled as multi-agent reinforcement learning (RL) problems. However, existing multi-agent RL methods typically scale poorly in the problem size. Therefore, a key challenge is to translate the success of deep learning on single-agent RL to the multi-agent setting. A major stumbling block is that independent Q-learning, the most popular multi-agent RL method, introduces nonstationarity that makes it incompatible with the experience replay memory on which deep Q-learning relies. This paper proposes two methods that address this problem: 1) using a multi-agent variant of importance sampling to naturally decay obsolete data and 2) conditioning each agent's value function on a fingerprint that disambiguates the age of the data sampled from the replay memory. Results on a challenging decentralised variant of StarCraft unit micromanagement confirm that these methods enable the successful combination of experience replay with multi-agent RL.
1. Introduction
Multi-agent RL captures cooperative real-world problems but faces scalability and nonstationarity challenges. This paper proposes importance sampling and fingerprints to make replay compatible with independent Q-learning, confirming success on decentralised StarCraft micromanagement.
- Cooperative multi-agent RL naturally models problems such as network packet delivery, rubbish removal, and urban traffic control.
- Centralised learning has exponentially growing joint action spaces and fails when agents receive observations that do not disambiguate the state.
- Independent Q-learning avoids centralised scalability problems but makes each agent’s environment nonstationary because other agents are learning.
- Experience replay conflicts with independent Q-learning because stored data reflects obsolete dynamics, despite replay’s stabilisation and sample-efficiency benefits.
- Importance sampling decays obsolete replay data, while a low-dimensional fingerprint disambiguates sampled experience by the other agents’ policies.
- The proposed methods successfully combine experience replay with multiagent Q-learning on decentralised StarCraft unit micromanagement.
2. Related Work
Prior multi-agent RL work largely used tabular settings, simple environments, communication, or centralised policies. The paper addresses high-dimensional decentralised tasks with partial observability, where earlier techniques had not scaled successfully.
- Earlier multi-agent RL research focused mostly on tabular settings and simple environments, commonly using independent Q-learning.
- Hyper Q-learning and related methods address nonstationarity by tracking or conditioning on teammates’ policies or behavioural traces.
- Coordination graphs and communication have been proposed to connect separate observations with global state information.
- Deep multi-agent RL work included DQN with independent Q-learning and differentiable communication architectures, often in two-player settings.
- Prioritized experience replay changes sampling using TD error but does not account for nonstationarity or multi-agent properties.
- This paper considers a decentralised task with partial observability, unlike centralised StarCraft policies that observe the full game state.
3. Background
The background develops deep Q-learning and its replay mechanism, then defines cooperative partially observable multi-agent RL and independent Q-learning. IQL scales and decentralises learning but introduces nonstationarity that conflicts with replay.
- 3.1. Single-Agent Reinforcement Learning: RL agents maximise expected discounted returns, with γ controlling the discounting of future rewards.
- 3.1. Single-Agent Reinforcement Learning: The action-value function gives expected return from a state and action, while Bellman optimality recursively relates optimal values to rewards and transitions.
- 3.1. Single-Agent Reinforcement Learning: Deep Q-learning represents Q with a neural network and trains its parameters from replay-memory batches by minimising squared TD error.
- 3.1. Single-Agent Reinforcement Learning: Replay stabilises learning, reduces overfitting to recent experiences, and improves sample efficiency; recurrent networks handle partial observability through action-observation histories.
- 3.2. Multi-Agent Reinforcement Learning: In cooperative multi-agent RL, agents share rewards while each acts from its own observation and action-observation history.
- 3.2. Multi-Agent Reinforcement Learning: Independent Q-learning gives each agent a decentralised Q-function, avoiding exponentially growing joint action spaces.
- 3.2. Multi-Agent Reinforcement Learning: IQL makes the environment nonstationary because other agents learn, and replay stores data generated by dynamics that no longer match current learning dynamics.
4. Methods
The methods address experience replay’s incompatibility with independent Q-learning by correcting obsolete data with importance sampling or disambiguating replay samples with low-dimensional fingerprints.
- Motivation: Experience replay is difficult to combine with independent Q-learning because other agents’ changing policies make the learning environment nonstationary.Prior work therefore restricted replay to short recent buffers or disabled it, reducing sample efficiency and threatening stability.
- Multi-Agent Importance Sampling: Multi-agent importance sampling records the other agents’ joint-action probability when each experience tuple is collected.The augmented replay tuple stores the state, action, reward, recorded policy probability, and next state for later correction.
- Multi-Agent Importance Sampling: At replay time, training uses an importance-weighted loss to account for policy changes between data collection and replay.The method treats replayed experience as off-environment data and applies the correction during optimization.
- Multi-Agent Importance Sampling: In partially observable settings, exact importance correction is difficult because several Bellman terms indirectly depend on other agents’ policies and are intractable.The complexity arises from correlated action-observation histories and dependencies on transition and observation functions.
- Multi-Agent Fingerprints: Importance sampling is unbiased but can have large, unbounded variance, motivating an alternative that embraces rather than corrects nonstationarity.The paper presents fingerprints as this alternative.
- Multi-Agent Fingerprints: Fingerprints condition each agent’s Q-function on replay-disambiguating information instead of the other agents’ full policy parameters.Only policy values occurring in the replay memory need to be distinguished, following a one-dimensional trajectory through policy space.
- Multi-Agent Fingerprints: The proposed fingerprint augments each agent’s observation with the exploration rate ϵ and training iteration e.Both quantities vary smoothly during training and are intended to correlate with the other agents’ policy quality.
5. Experiments
The experiments evaluate replay with fingerprints, importance sampling, or both in decentralised StarCraft micromanagement using feed-forward and recurrent models.
- Experimental Design: The experiments compare XP+FP, XP+IS, and XP+IS+FP in the decentralised StarCraft domain.Both feed-forward and recurrent models are tested to assess whether trajectory information helps distinguish experiences from different training stages.
- Environment: Each StarCraft agent controls one unit, observes a local subset of the map, and selects restricted durative actions.Available actions are move[direction], attack[enemy id], stop, and noop.
- Environment: The tasks use Terran Marines in cooperative 3-versus-3 and 5-versus-5 battles against game-controlled opponents.Agents receive damage-based rewards plus a terminal reward equal to the team’s remaining health.
- Models: The models include a feed-forward network with two fully connected hidden layers and a single-layer GRU, each using 128 neurons per hidden layer.The setup omits communicating agents and message connections.
- Training: Training anneals ϵ from 1.0 to 0.02 over 1500 episodes and runs for emax = 2500 training episodes.Episodes are added to replay during the standard training loop.
- Training: Importance weights are clipped to [0.01, 2], normalized by the number of agents, and divided by their running average.These adjustments reduce variance and maintain a constant overall learning rate.
6. Results
Across StarCraft tasks, experience replay without disambiguation performs poorly or inefficiently, while fingerprints provide the strongest improvement, especially for feed-forward models. Importance sampling offers smaller gains and can suffer high-variance weights; recurrent models already retain trajectory information that partially identifies training stage.
- Baseline performance: Without experience replay, NOXP performs poorly because agents overfit to greedy policies and bootstrap from stale or distorted values.The degradation is stronger and earlier for feed-forward models; recurrent performance simply degrades.
- Baseline performance: Naive replay lets XP outperform NOXP, but limited disambiguating information makes historical experiences inefficiently reusable.The model attempts to learn best responses to every historical policy without properly tracking the current policies of other agents.
- Importance sampling: XP+IS slightly outperforms XP with feed-forward models, but importance ratios become increasingly multimodal and high-variance as ϵ decreases.Most weights become less than or equal to approximately ϵ, so few experiences contribute strongly to learning.
- Fingerprints: XP+FP dramatically improves feed-forward performance by disambiguating training stage while preserving diverse replay experiences for generalisation.The fingerprint enables value estimates to vary with the known stage of training.
- Fingerprints: Combining importance sampling with fingerprints provides no additional benefit because both methods address nonstationarity in different ways.Figure 2 compares XP, NOXP, XP+IS, XP+FP, and their combination across RNN and feed-forward models in 3v3 and 5v5 settings.
- Recurrent models: Fingerprint inputs produce smoothly varying value estimates across training stages, while recurrent hidden states already retain trajectory-based information about training stage.Adding fingerprints makes recurrent hidden states even more informative, explaining their smaller performance gains from XP+IS and XP+FP.
7. Conclusion
The paper proposes importance sampling and fingerprints to stabilise experience replay in deep multi-agent reinforcement learning. Experiments on decentralised StarCraft micromanagement confirm that these methods enable successful combination of replay with multi-agent Q-learning.
- Conclusion: The paper proposes importance sampling that decays obsolete replay data and fingerprints that disambiguate the age of sampled data.Both methods target the incompatibility between experience replay and nonstationary multi-agent learning.
- Conclusion: Experiments on decentralised StarCraft micromanagement confirm that the proposed methods enable successful experience replay with multi-agent Q-learning.The benchmark is described as challenging and decentralised.