Multi-Agent Reinforcement Learning
When Agents Share a World
Classic reinforcement learning has a single agent learning to act in a fixed environment. Multi-agent RL (MARL) drops that assumption: several agents learn simultaneously inside the same shared environment, and each agent's rewards depend not only on its own actions but on what every other agent does. Trading bots in a market, cars merging at an intersection, players in a video game, and bidders in an auction are all multi-agent systems.
This sounds like a small change, but it breaks one of the deepest assumptions in RL and forces us to borrow ideas from game theory. The single most important thing to understand about MARL is the problem of non-stationarity.
Intuition: in single-agent RL you are learning to play against a fixed opponent (the environment). In MARL, your "opponent" is itself learning and changing while you learn. You are aiming at a moving target that moves because you moved.
The Core Difficulty: Non-Stationarity
Single-agent RL relies on the Markov property: the environment's transition and reward distributions depend only on the current state and the agent's action, and they do not change over time. This stationarity is what makes value functions well-defined and what guarantees that algorithms like Q-learning converge.
From the point of view of a single agent in a multi-agent system, the other agents are part of the environment. But those agents are learning, so their policies keep changing. That means the effective transition and reward dynamics that agent i experiences change over time — the environment is non-stationary. The Markov assumption breaks for any single agent considered in isolation.
Formally, agent i's transition dynamics depend on the joint action of all agents:
P(s' | s, a₁, a₂, ..., aₙ)
If agent i marginalizes out the others to reason about its own "P(s' | s, aᵢ)", that marginal depends on the others' policies π₋ᵢ. As π₋ᵢ changes during training, agent i's world changes underneath it. A target that was optimal yesterday may be wrong today.
Practical consequences: naïvely running independent Q-learners (one per agent, each treating the others as part of the environment) often fails to converge or oscillates, because each learner's "ground truth" keeps shifting. Replay buffers become stale, because old experience was generated against opponents that no longer exist. Much of MARL research is about taming this moving target.
Cooperative, Competitive, and Mixed
How agents' rewards relate to each other determines the entire character of the problem. We classify MARL settings along this axis.
| Setting | Reward structure | Goal | Examples |
|---|---|---|---|
| Cooperative | Shared / common reward; agents succeed or fail together. | Maximize team return. | Robot swarms, traffic-light coordination, team sports bots. |
| Competitive (zero-sum) | One agent's gain is exactly another's loss; rewards sum to zero. | Beat the opponent. | Chess, Go, poker (heads-up), pursuit-evasion. |
| Mixed (general-sum) | Partly aligned, partly conflicting; rewards need not sum to a constant. | Balance self-interest and cooperation. | Markets, autonomous driving, the Prisoner's Dilemma. |
Zero-sum vs general-sum: in a zero-sum game total reward is constant, so there is no possibility of mutual gain — minimax reasoning applies. In a general-sum game the totals can differ across outcomes, so agents may both do better by cooperating or both worse by competing. Most real-world multi-agent problems are general-sum and mixed: the interesting and hard case.
Interactive Demo: Strategic Interaction
The iterated Prisoner's Dilemma is the canonical mixed-motive game. Two agents each choose to Cooperate (C) or Defect (D). The payoff matrix below uses the standard ordering T > R > P > S, which is what makes the dilemma sharp: defecting is the dominant move in any single round (D beats C whatever the opponent does), so the one-shot Nash equilibrium is mutual defection (1,1) — even though mutual cooperation (3,3) would leave both better off.
| Agent B | ||
|---|---|---|
| Cooperate | Defect | |
| Agent A Cooperate | A: 3B: 3 | A: 0B: 5 |
| Agent A Defect | A: 5B: 0 | A: 1B: 1 |
Each cell shows (A's payoff, B's payoff). T=5 > R=3 > P=1 > S=0.
The twist is iteration. When the same agents meet over and over, the shadow of future rounds can make cooperation rational. Strategies like Tit-for-Tat punish defection just enough to deter it, sustaining the (3,3) outcome. Experiment below.
Iterated Prisoner's Dilemma Tournament
Two agents repeatedly play the Prisoner's Dilemma. Pick a strategy for each, set the number of rounds, and watch how the cumulative scores diverge. Try Tit-for-Tat vs Always Defect, then Tit-for-Tat vs Tit-for-Tat, then Always Defect vs Always Defect.
Moves per round (C = cooperate, D = defect):
| A | C | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D |
| B | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D | D |
The Game-Theory Link
Because outcomes depend on every agent's choice, MARL inherits the language of game theory. The central solution concept is the Nash equilibrium: a joint policy where no single agent can improve its own expected return by unilaterally changing its policy, holding the others' policies fixed. It is the multi-agent analogue of "optimal" — but, crucially, it is about mutual best response, not a single global maximum.
Nash equilibrium
In the one-shot Prisoner's Dilemma, (Defect, Defect) is the unique Nash equilibrium: given that the other defects, your best reply is to defect too. Notably the equilibrium (1,1) is worse for both than (3,3) — equilibria need not be efficient.
Iterated game & folk theorem
Repeat the game and cooperation can become an equilibrium. If players value the future enough, strategies that reward cooperation and punish defection (like Tit-for-Tat) make sustained cooperation a stable outcome. This is why the demo's line chart matters.
The reward structure dictates which equilibria are even possible. In a zero-sum game, a Nash equilibrium coincides with a minimax solution and is essentially unique in value. In a general-sum game there can be many equilibria, some good for everyone and some bad — and finding or selecting among them is itself hard.
Centralized Training, Decentralized Execution (CTDE)
A dominant paradigm for taming non-stationarity in cooperative MARL is centralized training with decentralized execution. The idea: during training, allow a learning component to see global information — all agents' observations and actions — so it can reason about the joint dynamics. During execution, each agent acts using only its own local observation, so the learned policies are deployable in the real, decentralized world.
Centralizing the critic during training is what addresses non-stationarity: a critic conditioned on every agent's action sees a stationary target even though each agent's individual view is non-stationary.
MADDPG
Multi-Agent DDPG gives each agent its own actor (local observation in) and a centralized critic that takes the actions of all agents. Each critic therefore faces stationary dynamics — the others' actions are explicit inputs rather than hidden, shifting environment. At test time only the local actors run.
QMIX
For cooperative teams with a shared reward, QMIX learns a per-agent Q value and a monotonic mixing network that combines them into a joint Q. Monotonicity guarantees that the action maximizing each agent's local Q also maximizes the joint Q, so agents can act greedily and independently yet stay coordinated.
Credit assignment across agents: when a team shares one reward, how do we tell which agent's action actually helped? This multi-agent credit assignment problem is central to cooperative MARL. Methods like QMIX's mixing network, or counterfactual baselines (e.g. COMA, which asks "how much better did the team do because this agent acted this way rather than a default?"), exist precisely to distribute shared credit fairly.
Self-Play and Emergent Behavior
In competitive settings, a powerful trick is self-play: an agent trains by playing against copies (often past versions) of itself. As the agent improves, so does its opponent, creating an automatic curriculum that ratchets skill upward without any external teacher. AlphaZero mastered chess, shogi, and Go this way, starting from random play and learning purely through self-play plus search — reaching superhuman strength with no human game data.
Why self-play helps with non-stationarity: the opponent is non-stationary by design, but it improves with the learner and at a matched pace, keeping the game perpetually at the edge of the agent's ability. In symmetric zero-sum games, a self-play fixed point corresponds to a Nash-equilibrium (minimax) strategy.
When many agents learn together, behaviors no one explicitly programmed can emerge. Agents discover coordination (e.g. dividing up roles or territory) and even communication — in cooperative tasks with a learnable signaling channel, agents can invent their own protocols to share information. In OpenAI's hide-and-seek work, agents progressively discovered tool use and counter-strategies in an open-ended arms race. Such emergence is one of the most striking properties of multi-agent learning.
Common Pitfalls
- Independent learners ignoring non-stationarity: training each agent with vanilla single-agent RL and pretending the others are a fixed environment can diverge or cycle.
- Stale replay buffers: off-policy experience generated against earlier opponent policies can mislead, because those opponents no longer exist.
- Credit assignment: with a shared team reward, a lazy agent can free-ride on good teammates unless credit is properly decomposed.
- Equilibrium ≠ good outcome: as the Prisoner's Dilemma shows, the Nash equilibrium can be worse for everyone than a cooperative outcome.
- Non-transitive cycles: in competitive games, strategy A may beat B, B beat C, and C beat A (rock-paper-scissors), so "getting better" is not a simple ladder — self-play can chase its own tail without diverse opponents.
Key Takeaways
- MARL = multiple agents learning at the same time in one shared environment, where each agent's reward depends on the others' actions.
- The defining difficulty is non-stationarity: because the other agents are also learning, any single agent's effective environment keeps changing, breaking the Markov assumption it would normally rely on.
- Settings are cooperative (shared reward), competitive (zero-sum, one's gain is another's loss), or mixed/general-sum (the hard, realistic case).
- MARL borrows from game theory: the Nash equilibrium is mutual best response, and it need not be efficient — the Prisoner's Dilemma's equilibrium (defect, defect) is worse for both than cooperation.
- Iteration can rescue cooperation: strategies like Tit-for-Tat sustain the (3,3) outcome by punishing defection, while Always-Defect exploits cooperators but tanks against itself.
- CTDE (MADDPG, QMIX) tames non-stationarity by giving the critic global information at training time while keeping execution decentralized; it also tackles multi-agent credit assignment.
- Self-play (AlphaZero) creates an automatic curriculum and can yield emergent coordination and communication.