Multi-Agent Reinforcement Learning (MARL)
Advanced material
A specialized extension of single-agent RL. It assumes familiarity with policy gradients, actor-critic methods, and the basics of game theory. Read Policy Gradient & Actor-Critic first.
Single-agent RL assumes one agent in a stationary environment. Multi-Agent RL studies settings where multiple agents learn simultaneously — autonomous vehicles negotiating an intersection, bots in a strategy game, market-making agents, or robot swarms. The presence of other learning agents breaks the core assumptions of single-agent RL.
The Markov game (stochastic game)
MARL generalizes the MDP to a Markov game with agents:
- Each agent has its own action set and reward function
- The transition depends on the joint action of all agents
- Each agent learns a policy to maximize its own expected return
Three regimes
| Regime | Reward structure | Example |
|---|---|---|
| Cooperative | All agents share one reward | Robot team assembling a product |
| Competitive | Zero-sum: | Two-player Go, poker |
| Mixed | General-sum, partial alignment | Autonomous driving (avoid collisions but reach own goal) |
The non-stationarity problem
This is the central challenge of MARL. From any single agent's perspective, the environment includes the other agents' policies. As those agents learn and change their policies, the effective transition and reward dynamics change over time — the environment is non-stationary.
This breaks the Markov assumption that single-agent RL relies on:
- Q-learning convergence guarantees no longer hold (the optimal Q-function is a moving target)
- Experience replay becomes problematic — old transitions were generated by outdated opponent policies, so replaying them teaches the agent to respond to behavior that no longer occurs
Solution concepts: beyond "optimal"
In single-agent RL the goal is the optimal policy. With multiple agents, "optimal" is ill-defined — your best policy depends on what others do. MARL borrows equilibrium concepts from game theory:
- Nash Equilibrium: a joint policy where no agent can improve by unilaterally changing its own policy
- Correlated Equilibrium: agents coordinate through a shared signal
- Minimax / maximin: for zero-sum games, play the policy that maximizes worst-case return
Centralized Training, Decentralized Execution (CTDE)
The dominant modern paradigm. During training, a central critic has access to the global state and all agents' actions; during execution, each agent acts using only its own local observations.
This resolves non-stationarity during training (the centralized critic sees everyone's actions, so the environment looks stationary to it) while keeping execution decentralized (practical for deployment).
| Algorithm | Idea |
|---|---|
| MADDPG | Multi-agent DDPG: each agent has a decentralized actor and a centralized critic that takes all agents' observations and actions |
| QMIX | Cooperative value factorization: a mixing network combines per-agent Q-values into a joint Q-value, constrained to be monotonic so decentralized argmax matches centralized argmax |
| MAPPO | Multi-agent PPO with a centralized value function; surprisingly strong on cooperative benchmarks |
| Self-play | For competitive games, the agent trains against copies of itself (AlphaGo, AlphaStar, OpenAI Five) |
Emergent phenomena
MARL produces behaviors that don't arise in single-agent settings:
- Communication: agents can learn to emit signals that coordinate behavior, even when communication isn't explicitly rewarded
- Specialization / role assignment: in cooperative teams, agents differentiate into complementary roles
- Arms races: in competitive settings, agents iteratively discover and counter each other's strategies (OpenAI's hide-and-seek showed tool use emerging from competitive pressure)
Credit assignment
In cooperative MARL with a shared reward, a hard question is: which agent's action caused the team reward? Counterfactual multi-agent (COMA) policy gradients address this by computing a counterfactual baseline — comparing the actual reward to what would have happened if a single agent had acted differently, holding others fixed.
When to use MARL
- The problem genuinely involves multiple decision-makers with their own objectives
- Centralized control is infeasible (communication limits, scale, privacy)
- You need robustness to adaptive opponents (self-play produces strong, general strategies)
Related concepts
- Policy Gradient & Actor-Critic: the single-agent actor-critic that CTDE algorithms (MADDPG, MAPPO) extend
- Markov Decision Processes: the single-agent MDP that Markov games generalize