PaperlayerView exact revision on arXiv

Source-linked AI summary

Counterfactual Multi-Agent Policy Gradients

Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, Shimon Whiteson

arXiv:1705.08926v3cs.AIcs.MA

TL;DR

Cooperative multi-agent RL needs efficient decentralised policy learning despite large joint action spaces, partial observability, and credit-assignment challenges. COMA combines a centralised critic with decentralised actors and a counterfactual baseline, achieving significantly better performance than other multi-agent actor-critic methods and competitiveness with centralised controllers on decentralised StarCraft micromanagement. The paper also identifies scalability of centralised critics and multi-agent exploration as future challenges.

  • Problem

    Cooperative multi-agent RL needs methods that efficiently learn decentralised policies despite large joint action spaces, partial observability, and difficult multi-agent credit assignment.

  • Method

    COMA uses a centralised critic with decentralised actors and an agent-specific counterfactual baseline that marginalises one action while holding other agents’ actions fixed.

  • Results

    COMA significantly improves final performance and training speed over other multi-agent actor-critic methods and remains competitive with state-of-the-art centralised controllers in decentralised StarCraft micromanagement.

  • Takeaways & Limitations

    COMA provides a centralised-training, decentralised-execution approach that addresses multi-agent credit assignment without extra simulations or default-action assumptions.

  • Takeaways & Limitations

    The paper identifies multi-agent exploration as the scalability bottleneck and defers further investigation of factored COMA critics; future work targets scenarios with many agents.

Abstract

from arXiv · show

Cooperative multi-agent systems can be naturally used to model many real world problems, such as network packet routing and the coordination of autonomous vehicles. There is a great need for new reinforcement learning methods that can efficiently learn decentralised policies for such systems. To this end, we propose a new multi-agent actor-critic method called counterfactual multi-agent (COMA) policy gradients. COMA uses a centralised critic to estimate the Q-function and decentralised actors to optimise the agents' policies. In addition, to address the challenges of multi-agent credit assignment, it uses a counterfactual baseline that marginalises out a single agent's action, while keeping the other agents' actions fixed. COMA also uses a critic representation that allows the counterfactual baseline to be computed efficiently in a single forward pass. We evaluate COMA in the testbed of StarCraft unit micromanagement, using a decentralised variant with significant partial observability. COMA significantly improves average performance over other multi-agent actor-critic methods in this setting, and the best performing agents are competitive with state-of-the-art centralised controllers that get access to the full state.

1 Introduction

Cooperative multi-agent RL must learn decentralised policies despite exponentially growing joint action spaces, partial observability, communication constraints, and difficult credit assignment. COMA addresses these challenges with centralised training, decentralised execution, and counterfactual policy gradients, and performs strongly in decentralised StarCraft micromanagement.

  • Joint action spaces grow exponentially with agent count, causing single-agent RL methods to fare poorly on cooperative multi-agent tasks.
  • Decentralised policies are needed when agents must act from local action-observation histories under partial observability or communication constraints.
  • Centralised training can exploit extra state information and communication, but how best to use that opportunity remains open.
  • Global rewards make it difficult for individual agents to infer their contributions, substantially impeding learning in challenging cooperative tasks.
  • COMA combines a centralised critic during learning with decentralised actors during execution.
  • Its counterfactual baseline marginalises one agent’s action while holding other agents’ actions fixed, providing agent-specific credit assignment without extra simulations or default-action assumptions.
  • COMA significantly improves performance over other multi-agent actor-critic methods and ablations, while its best agents are competitive with centralised full-state controllers.

2 Related Work

Prior deep multi-agent RL work includes independent value-based methods, learned communication, centralised-training actor-critic approaches, and centralised StarCraft controllers. COMA differs by combining centralised learning with decentralised policies while directly addressing multi-agent credit assignment.

  • Earlier multi-agent RL was often restricted to tabular methods and simple environments, while later deep methods scaled to high-dimensional inputs and action spaces.
  • Communication-focused methods commonly pass gradients between agents or share parameters during centralised training.
  • Some related methods do not use extra state information during learning or address multi-agent credit assignment.
  • Gupta et al. use centralised training with decentralised execution, but their actors and critic rely on local observations and actions and use hand-crafted local rewards.
  • Most prior StarCraft micromanagement work uses centralised controllers with full-state access and control of all units.
  • Foerster et al. use decentralised policies but focus on stabilising DQN experience replay rather than fully exploiting centralised training.
  • Lowe et al. concurrently use centralised critics but do not address multi-agent credit assignment and target competitive continuous-action environments.

3 Background

The paper formulates cooperative multi-agent RL as a stochastic game with partially observable decentralised policies and centralised training. It reviews policy gradients and actor-critic baselines, then uses TD(λ)-trained critics as the learning foundation.

  • A cooperative stochastic game contains agents, states, joint actions, transitions, shared rewards, observations, and a discount factor.
  • Under partial observability, each agent conditions its stochastic policy on its own action-observation history.
  • The joint policy induces value and action-value functions, with the advantage defined as Qπ(st, ut) − Vπ(st).
  • The setting permits centralised training with additional state information but requires decentralised execution from local histories.
  • Policy-gradient methods optimise expected discounted reward by ascending gradients estimated from policy log-probabilities and returns.
  • Actor-critic methods replace returns with critic-based quantities such as Q(st, ut) − b(st), using baselines to reduce variance.
  • The paper trains critics on-policy with a deep-neural-network variant of TD(λ), using mixtures of n-step returns and bootstrapped target-network values.

4 Methods

COMA extends multi-agent actor-critic learning with centralized training, decentralized execution, and counterfactual credit assignment. Its centralized critic conditions on global information while efficiently evaluating agent-specific counterfactual baselines.

  • Independent actor-critic agents learn from local histories, making coordinated strategies and individual contributions to team rewards difficult to estimate.
  • COMA uses a centralized critic during learning while each decentralized actor conditions only on its own action-observation history during execution.
  • The counterfactual baseline marginalizes one agent’s action while fixing the other agents’ actions, producing a separate advantage for each agent.
  • COMA computes counterfactual baselines from the centralized critic rather than requiring extra simulations, reward models, or user-designed default actions.
  • The critic outputs Q-values for each agent’s actions with other agents’ actions as inputs, reducing outputs from the joint action space to |U| per agent.
  • COMA focuses on discrete actions, while continuous-action extensions can estimate the counterfactual expectation with Monte Carlo samples or suitable analytic forms.

5 Experimental Setup

The experiments evaluate COMA in a challenging, decentralised StarCraft micromanagement setting with limited fields of view, shared rewards, and ablations of its critic design.

  • StarCraft Micromanagement: The benchmark replaces StarCraft units with decentralised controllers across 3m, 5m, 5w, and 2d 3z scenarios against the StarCraft AI.The task concerns low-level unit positioning and attack commands.
  • StarCraft Micromanagement: Agents choose discrete move, attack, stop, and noop actions, with attack actions using built-in pathfinding to move into range.Attack-move macro-actions make control easier, so the benchmark restricts this capability.
  • Decentralised Benchmark: A restricted firing-range field of view introduces partial observability, invalid attack commands, and a larger effective action space.These conditions increase exploration and coordination difficulty.
  • Reward Function: The shared reward combines damage inflicted, half the damage taken, opponent kills, and a winning-game bonus based on remaining team health.The approach does not require estimating local rewards.
  • State Representations: Actors use local observations while critics receive global state information; the centralised critic combines global state with the evaluated agent’s local observation.Local observations are drawn from circular fields of view, whereas the global representation covers all units.
  • Ablations: The study also examines critic architectures factored at the agent level, finding exploration—not critic centralisation—to be the scalability bottleneck.Further investigation of factored COMA critics is deferred.
  • Ablations: The experiments ablate critic centralisation, learning Q instead of V, and replacing COMA’s counterfactual baseline with V.The central-QV comparison uses Q − V for advantage estimation, while all critics use TD(λ).

6 Results

COMA outperforms multi-agent actor-critic baselines across the evaluated StarCraft scenarios and remains competitive with centralised controllers despite decentralised policies and local observations.

  • Evaluation protocol: 35 independent trials evaluated average win rates every 100 training episodes across 200 evaluation episodes per method.The plots report averages across episodes and trials with one standard deviation.
  • Comparison with IAC: COMA is superior to the IAC baselines in all scenarios.IAC eventually learns reasonable policies in 5m but requires substantially more episodes.
  • Comparison with central-QV: COMA strictly dominates central-QV in both training speed and final performance across all settings.The results identify the counterfactual baseline as crucial when using a central Q-critic for decentralised policy training.
  • Comparison with central-V: COMA outperforms central-V in final performance and typically reaches good policies faster and more consistently.The paper attributes the faster learning to COMA’s shaped training signal and the stability to its gradient tending to zero as policies become greedy.
  • Comparison with centralised controllers: COMA’s best agents achieve performance comparable to the best published win rates in most settings despite decentralised policies and local fields of view.The comparison uses centralised controllers with full field of view and attack-move macro-actions.

7 Conclusions & Future Work

The paper concludes that COMA improves decentralised multi-agent reinforcement learning and remains competitive with centralised controllers. Future work targets larger-agent settings and more sample-efficient variants for applications such as self-driving cars.

  • Conclusion: COMA uses a centralised critic to estimate a counterfactual advantage for decentralised policies in multi-agent reinforcement learning.
  • Conclusion: COMA significantly improves final performance and training speed over other multi-agent actor-critic methods in a decentralised StarCraft benchmark.
  • Conclusion: COMA remains competitive with state-of-the-art centralised controllers under best-performance reporting.
  • Future Work: Future work will address scenarios with many agents and develop more sample-efficient variants for real-world applications such as self-driving cars.

Errata

The paper’s revised version corrects a proof issue caused by an omitted joint-history dependence in the critic and updates the associated equation and figure.

  • Errata: An earlier version contained an error in the proof of Lemma 1 because the critic depended on state s but not joint history τ.The revised version updates Equation 4 and Figure 1 to add this dependence and revises the proof.
  • Errata: The revised proof explicitly shows how existing policy-gradient results apply to the modified history-based setting.It cites Sutton et al. (1999) instead of Konda and Tsitsiklis (2000), whose irreducibility condition does not hold for history-based state representations.

A Proof of Lemma 1

The proof shows that COMA’s counterfactual baseline leaves the expected policy gradient unchanged, allowing standard policy-gradient convergence reasoning under stated assumptions.

  • Gradient definition: The COMA gradient is expressed using actor-policy parameters and the counterfactual baseline b(s, τ, u−a).
  • Proof structure: The expected contribution of the baseline is analyzed before evaluating the remaining policy-gradient term.
  • Baseline property: Because the per-agent baseline is independent of agent a’s action u_a, it may reduce variance without changing the expected gradient.
  • Policy factorization: Writing the joint policy as a product of independent actors enables rewriting the gradient in multi-agent form.
  • MDP correspondence: The multi-agent stochastic game can be reinterpreted as a single-agent policy in a corresponding MDP with state space S × T and action space U.
  • Assumptions: Convergence to a local maximum of expected return relies on bounded rewards, differentiable policies, unbiased critic targets, critic convergence, and compatible critic representation.
  • Assumptions: Decomposing a single-agent joint-action learner into independent actors does not affect convergence provided the parameterisation remains differentiable.

B Training Details and Hyperparameters

Training uses batched parallel processing with a three-step cycle: data collection, critic updates, and actor updates. The implementation uses target networks and RMSprop optimization with fixed hyperparameters.

  • 30 episodes are collected per batch, with each agent, episode, and timestep occupying one batch entry for parallel processing.
  • Each training cycle collects data, trains the critic from episode ends backward, and then trains the recurrent actor across all timesteps.
  • Target critics update every 150 steps for feed-forward centralised critics and every 50 steps for recurrent IAC critics.
  • Both actor and critic networks use RMSprop with learning rate 0.0005 and alpha 0.99, without weight decay, while gamma is 0.99 for all maps.

C Algorithm

Algorithm 1 processes agents in parallel through a batched recurrent computation. It collects episode transitions, unrolls the RNN, and computes TD(λ) targets.

  • Algorithm 1 loops over agents until termination or the time horizon while collecting rewards, next states, and episode data.
  • Episodes are collated into a single batch so that subsequent processing covers all agents in parallel.
  • The algorithm batch-unrolls the RNN using states, actions, and rewards, then calculates TD(λ) targets y^a.
Loading 1705.08926v3…