Multi-Agent Reinforcement Learning

Background

Multi-agent RL generalizes single-agent RL to settings where multiple agents interact, cooperate, or compete
AlphaStar (2019) and OpenAI Five (2019) demonstrated multi-agent RL at superhuman level in complex games
MARL theory is still immature: non-stationarity and credit assignment are open research problems

The Concept

Multi-agent RL involves multiple independent learning agents that share an environment. Agents may cooperate (maximizing a shared reward), compete (zero-sum games), or do both (mixed-cooperative). Each agent faces a non-stationary world because other agents are also changing their policies.

How it Links

Game theory (Nash equilibrium, mechanism design) provides the solution concepts for multi-agent settings
Connects to emergent communication, social dilemmas, and AI safety (misaligned multi-agent outcomes)
Independent Q-learning, MADDPG, and QMIX are key MARL algorithms each with different coordination assumptions

Concrete Example

Autonomous intersection management: 20 self-driving cars (agents) approach an intersection simultaneously. Each maximizes its own throughput. Through multi-agent RL, they learn to coordinate implicitly - slowing down slightly to avoid collisions - without any central controller. Emergent traffic flow patterns arise from individual policies.

Prerequisites

Foundations of RL, The Math You Need, Multilayer Perceptrons

Learning outcomes

Formalise the multi-agent problem as a Markov game (stochastic game) and distinguish cooperative, competitive, and mixed settings.
Explain why independent Q-learning fails in the multi-agent setting due to non-stationarity from the perspective of each agent.
Describe the Centralised Training with Decentralised Execution (CTDE) paradigm and explain why it resolves the non-stationarity problem during training.
Explain QMIX value decomposition and MADDPG centralised critics, and compare their assumptions.
Define a Nash equilibrium in a normal-form game and explain what it means in the context of multi-agent RL.

TL;DR

Multi-agent RL generalises single-agent RL to settings with multiple interacting agents. Independent Q-learning fails because each agent faces a non-stationary environment as others learn simultaneously. The dominant solution paradigm — Centralised Training, Decentralised Execution (CTDE) — resolves this by allowing agents to share information during training while operating independently at deployment time. QMIX and MADDPG are the canonical CTDE algorithms for cooperative and mixed settings respectively.

Intuition

In single-agent RL, the environment is stationary given a fixed policy. In multi-agent settings, each agent’s environment includes the other agents — and as they all learn simultaneously, the effective environment changes for everyone. This is the root cause of most MARL difficulties. The Centralised Training, Decentralised Execution (CTDE) paradigm resolves this asymmetry: during training, agents can share global state and each other’s observations; at execution, each agent acts only on its own local information.

Insight

The key MARL insight: training is a coordination problem; execution is a scalability problem. CTDE gets the best of both worlds — globally coordinated training with scalable independent deployment.

Markov Games (Stochastic Games)

A Markov game [7] with $N$ agents is a tuple $(\mathcal{S}, \{\mathcal{A}_i\}_{i=1}^N, P, \{R_i\}_{i=1}^N, \gamma)$ where:

$\mathcal{S}$ : shared state space.
$\mathcal{A}_i$ : action space for agent $i$ ; joint action $\mathbf{a} = (a_1, \ldots, a_N) \in \mathcal{A}_1 \times \cdots \times \mathcal{A}_N$ .
$P(s' \mid s, \mathbf{a})$ : transition probability depending on the joint action of all agents.
$R_i(s, \mathbf{a})$ : reward for agent $i$ , which may depend on all agents’ actions.
$\gamma$ : shared discount factor.

Cooperative: all agents share the same reward $R_1 = R_2 = \cdots = R_N = R$ . The goal is to maximise the team return.

Competitive (zero-sum): $\sum_i R_i(s, \mathbf{a}) = 0$ . One agent’s gain is another’s loss. Examples: chess, Go, poker.

Mixed (general-sum): agents have different reward functions that may partially overlap. Examples: trading, autonomous driving.

Why Independent Q-Learning Fails

The simplest approach: give each agent a separate Q-learning update, treating other agents as part of the environment. This is called Independent Q-Learning (IQL). The problem is fundamental: from agent $i$ ‘s perspective, the transition $P(s' \mid s, a_i)$ depends on the actions of all other agents. As other agents update their policies, this transition distribution changes — the environment is non-stationary from each agent’s perspective. Standard Q-learning convergence proofs assume a stationary environment; without this, Q-values can cycle or diverge.

Specifically, suppose two agents are learning simultaneously. Agent 1’s Bellman update targets $R_1 + \gamma \max_{a_1'} Q_1(s', a_1')$ , but the reward $R_1$ was generated under agent 2’s old policy. By the time agent 1 uses this target, agent 2 has already changed — the target is stale. In cooperative tasks, this causes coordination failures; in competitive tasks, agents oscillate without converging to an equilibrium.

Warning

The non-stationarity problem is the central obstacle in MARL. Every time agent 2 updates, the Markov assumption is violated for agent 1. IQL can work in practice for simple tasks, but it has no convergence guarantees and fails for coordination-heavy problems.

Centralised Training, Decentralised Execution (CTDE)

The CTDE paradigm [8] addresses non-stationarity during training by allowing agents to access global state (all agents’ observations and actions), then deploying agents using only their local information.

During training: agent $i$ uses a centralised critic $Q_i(s, \mathbf{a})$ conditioned on the full state $s$ and all agents’ actions $\mathbf{a}$ . This resolves non-stationarity because the centralised critic “sees” what all agents are doing.

During execution: each agent uses only its local policy $\pi_i(a_i \mid o_i)$ conditioned on its own observation $o_i$ . No communication or global information is required at deployment.

This is practically powerful because: training can be centralised on a cluster with full information sharing, while deployment can be fully decentralised (each agent runs independently, even without network connectivity).

QMIX: Monotonic Value Decomposition

QMIX [1] addresses cooperative MARL where all agents share a single team reward. The core insight: each agent $i$ maintains its own local utility function $Q_i(o_i, a_i)$ , but the joint action-value function $Q_{\text{tot}}(\mathbf{s}, \mathbf{a})$ should be consistent with decentralised execution. QMIX enforces the IGM (Individual-Global-Max) condition:

\arg\max_{\mathbf{a}} Q_{\text{tot}}(\mathbf{s}, \mathbf{a}) = \left(\arg\max_{a_1} Q_1(o_1, a_1), \ldots, \arg\max_{a_N} Q_N(o_N, a_N)\right)

If this holds, each agent can greedily maximise its own $Q_i$ and the result is globally optimal. QMIX enforces a monotonicity constraint:

\frac{\partial Q_{\text{tot}}}{\partial Q_i} \geq 0 \quad \forall i

This is implemented with a mixing network whose weights (output of a hypernetwork conditioned on global state $\mathbf{s}$ ) are constrained to be non-negative. The mixing network takes individual $Q_i$ values and combines them into $Q_{\text{tot}}$ ; the non-negativity of weights ensures monotonicity.

QMIX was evaluated on StarCraft Multi-Agent Challenge (SMAC) and became the de facto cooperative MARL baseline.

MADDPG: Centralised Critics for Mixed Environments

MADDPG [2] extends DDPG to multi-agent mixed cooperative-competitive settings. Each agent $i$ has:

A local actor $\mu_i(o_i)$ acting on its own observation.
A centralised critic $Q_i(s, a_1, \ldots, a_N)$ conditioned on all agents’ observations and actions.

The actor is trained with the deterministic policy gradient from the centralised critic:

\nabla_{\theta_i} J(\theta_i) = \mathbb{E} \left[ \nabla_{\theta_i} \mu_i(o_i) \cdot \nabla_{a_i} Q_i(s, a_1, \ldots, a_N) \big|_{a_i = \mu_i(o_i)} \right]

Because the critic sees all agents’ actions, it can correctly attribute credit even in mixed games where cooperation and competition coexist. Agents in MADDPG can also optionally model other agents’ policies (opponent modeling) for competitive settings.

Nash Equilibria in MARL

A Nash equilibrium (NE) is a joint policy $(\pi_1^*, \ldots, \pi_N^*)$ such that no agent can improve its expected return by unilaterally changing its own policy, given the others’ policies:

\forall i: \quad V_i(\pi_i^*, \pi_{-i}^*) \geq V_i(\pi_i, \pi_{-i}^*) \quad \forall \pi_i

where $\pi_{-i}^*$ denotes the joint policy of all agents other than $i$ .

In a two-player zero-sum game, the minimax theorem guarantees the existence of a unique Nash equilibrium in mixed strategies, and both players achieve their minimax values. This is the game-theoretic foundation behind AlphaZero’s self-play convergence.

In cooperative games, the Nash equilibrium typically coincides with the joint optimum. In general-sum games, multiple NE may exist and they may be inefficient (the Prisoner’s Dilemma is a classic example where the NE is globally suboptimal).

Case Studies: OpenAI Five and AlphaStar

OpenAI Five [4]: Five separate neural networks play Dota 2 using PPO. Each agent observes partial information (its own hero’s perspective). Key innovations: (1) team spirit parameter in the reward that blends individual and team reward, allowing a spectrum from fully selfish to fully cooperative; (2) self-play with league training; (3) distributed training at 180 years of game experience per day.

AlphaStar [3]: Mastered StarCraft II — a game with 1,000+ possible actions per step, long time horizons (thousands of steps), and partial observability. Used a centralised policy trained via population-based training with a league of agents. The architecture uses transformers to process multi-entity observations, a pointer network for action selection, and LSTM for temporal integration.

Both systems demonstrate that with sufficient scale and well-designed multi-agent training infrastructure, MARL can reach superhuman performance in complex partially observable games.

Emergent Communication

Cooperative MARL agents can develop emergent communication protocols when given a discrete communication channel [6]. Early work showed that agents develop grounded symbols that refer to game entities. However, emergent languages are often uninterpretable to humans, not compositional, and brittle — they only communicate what’s needed for the task, not general language.

Single-Agent vs Multi-Agent: Comparison

Dimension	Single-Agent RL	Multi-Agent RL
Environment stationarity	Stationary (given fixed policy)	Non-stationary (other agents change during training)
Credit assignment	Direct — one agent, one reward	Hard — joint rewards must be decomposed across agents
Convergence guarantees	Q-learning converges under mild conditions	IQL has no guarantees; CTDE methods have partial guarantees
Scalability	Single policy network	N policy networks; joint action space grows exponentially
Communication	Not needed	Optional; emergent or engineered protocols
Training paradigm	On-policy or off-policy	CTDE, self-play, population-based training
Equilibrium concept	Optimal policy	Nash equilibrium (may not be unique or efficient)
Hallmark algorithms	DQN, PPO, SAC	IQL (baseline), QMIX, MADDPG, MAPPO, QMix+

Real-World Applications

Multi-robot coordination: warehouse robots (Amazon Kiva) navigate without collisions; cooperative teams in search-and-rescue. CTDE methods trained in simulation, deployed individually.

Trading: market microstructure with multiple interacting strategies. Each strategy is an agent; the market price is an emergent property. Zero-sum competition with complex mixed incentives.

Ad auctions: multiple bidders (agents) compete in repeated auctions. Mechanism design intersects with MARL — the auction rules shape the equilibrium.

Multi-player games: poker, Diplomacy (Facebook CICERO), StarCraft, Dota — all require reasoning about other agents’ policies and intentions.

Tip

When to use cooperative MARL over single-agent with a team reward: when the joint action space is too large for a single policy to handle (e.g., $|\mathcal{A}|^N$ grows fast), or when agents must be deployed independently without communication.

Pop Quiz

Check yourself

Score: 0 / 5(0 answered)

1. Why does independent Q-learning (IQL) fail to converge in cooperative multi-agent settings?
2. What is the CTDE paradigm, and why does it resolve the non-stationarity problem?
3. What does QMIX's monotonicity constraint ensure?
4. In a two-player zero-sum game, what does a Nash equilibrium guarantee?
5. What distinguishes cooperative MARL from single-agent RL with a team reward?

Interview Q&A

Why does independent Q-learning fail, and what is the CTDE rationale?onsite

Independent Q-learning gives each agent its own Q-function trained on its own experience. From agent $i$ ‘s perspective, the transition function is $P(s' | s, a_i) = \sum_{\mathbf{a}_{-i}} \mu_{-i}(\mathbf{a}_{-i}) P(s' | s, a_i, \mathbf{a}_{-i})$ — this depends on the joint distribution of other agents’ policies $\mu_{-i}$ . Since other agents are updating their policies simultaneously, $\mu_{-i}$ changes each step, making the environment non-stationary. Q-learning requires a Markov, stationary environment to converge; non-stationarity breaks this.

CTDE addresses this by maintaining a centralised critic $Q_i(s, \mathbf{a})$ conditioned on the full state and all agents’ actions. During training, the centralised critic sees everything, making the effective environment stationary. The policy (actor) is still local $\pi_i(o_i)$ . At deployment, only the local policy runs, so no inter-agent communication is needed. The price paid is that training requires centralised infrastructure; the benefit is principled credit assignment and stable learning.

Define Nash equilibrium in a 2-player zero-sum game, and explain what self-play converges to.onsite

A Nash equilibrium (NE) in a two-player zero-sum game is a pair of strategies $(x^*, y^*)$ such that:

V(x^*, y) \geq V(x^*, y^*) \geq V(x, y^*)

for all strategies $x$ of player 1 and $y$ of player 2, where $V$ is the payoff to player 1 (player 2 gets $-V$ ). Neither player can improve by unilaterally deviating.

The minimax theorem guarantees a unique minimax value $v^* = \max_x \min_y V(x,y) = \min_y \max_x V(x,y)$ . Both players achieve this value at the NE.

Self-play in theory converges to the NE for two-player zero-sum games when combined with the right update rule (fictitious play, counterfactual regret minimisation, or mirror descent). In practice, deep RL self-play (AlphaGo/AlphaZero) uses iterative policy improvement with MCTS rather than directly computing the NE — this works empirically but the theoretical connection is less clean for function approximation. AlphaStar uses a population-based league specifically to avoid cycling, which can occur with naive self-play.

What makes cooperative MARL different from single-agent RL, and when would you use QMIX vs MADDPG?phone

Single-agent RL with a team reward assumes one central controller with access to all agents’ observations — it acts in a joint action space that grows exponentially with the number of agents. Cooperative MARL instead assumes decentralised execution: each agent acts independently at runtime, observing only its local information. The challenge is coordinating these independent agents to achieve team goals.

QMIX is designed for pure cooperative settings: all agents share one team reward and the goal is to maximise it jointly. QMIX’s monotonicity constraint means each agent can greedily maximise its own $Q_i$ and the result is globally optimal for the team — this is the IGM condition. QMIX cannot handle settings where agents have different reward functions.

MADDPG works for cooperative, competitive, or mixed settings because each agent has its own centralised critic $Q_i$ that can encode that agent’s individual objective. The actors are still local and deterministic. Use QMIX when you want lightweight cooperative coordination with strong theoretical guarantees; use MADDPG when agent objectives differ or when you need stochastic continuous-action policies.

References

Rashid, T., Samvelyan, M., Schroeder de Witt, C., Farquhar, G., Foerster, J. N., and Whiteson, S. (2018). QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning. ICML 2018 (arXiv preprint). arXiv:1803.11485
Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., and Mordatch, I. (2017). Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. NeurIPS 2017 (arXiv preprint). arXiv:1706.02275
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Choi, J., Powell, R., Ewalds, T., Georgiev, P., Oh, J., et al. (2019). Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350-354. doi:10.1038/s41586-019-1724-z
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., et al. (2019). Dota 2 with Large Scale Deep Reinforcement Learning. arXiv preprint. arXiv:1912.06680
Sutton, R. S., and Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. ISBN 978-0-262-03924-6
Foerster, J. N., Assael, Y. M., de Freitas, N., and Whiteson, S. (2016). Learning to Communicate with Deep Multi-Agent Reinforcement Learning. NeurIPS 2016 (arXiv preprint). arXiv:1605.06676
Shapley, L. S. (1953). Stochastic Games. Proceedings of the National Academy of Sciences 39(10), 1095-1100. doi:10.1073/pnas.39.10.1095
Oliehoek, F. A., and Amato, C. (2016). A Concise Introduction to Decentralized POMDPs. Springer. doi:10.1007/978-3-319-28929-8

Offline RL & RLHF Open Problems in AI