Multi-Agent RL: Markov Games and Centralized Training

Every method up to here assumed the agent was alone. The environment had fixed dynamics: take an action, the world responds according to $p(s^{\prime }\mid s,a)$, and that transition kernel never changes. That assumption is what lets the Bellman equation have a fixed point and lets Q-learning converge. It is also false the moment a second learning agent shares the world. A market has many traders, a road has many drivers, a game of Go has an opponent — and each of them is also adapting. When the others change their behavior, they change the dynamics you face. The fixed environment that grounds single-agent MDPs dissolves.

This is a different problem, with its own mathematical object (the Markov game), its own central pathology (non-stationarity), and its own dominant algorithmic paradigm (centralized training, decentralized execution). This lesson builds all three. A companion lesson then turns to the setting where multi-agent RL has produced its strongest results — self-play, the engine behind AlphaGo, OpenAI Five, and AlphaStar — and the equilibrium concepts that define what solved means.

The setting: Markov games

The single-agent MDP is a tuple $(\mathcal{S},\mathcal{A},p,r,\gamma )$. The multi-agent generalization keeps the state and the discount but gives every agent its own action set and its own reward. It is called a Markov game (or stochastic game), introduced by Shapley in 1953, decades before MDPs were standard.¹

Two features of that definition carry all the weight. First, the transition depends on the joint action $\mathbf{a}$, not on any single agent's action: where the world goes next is determined by what everyone does together. Second, each agent has a separate reward $r_i$, and those rewards need not agree. The relationship between the rewards is what carves the field into three regimes.

In a cooperative game every agent receives the same reward, $r_1=\cdots =r_N$, and the team succeeds or fails together — a fleet of warehouse robots, players on one side of a match. In a competitive (two-agent, zero-sum) game the rewards cancel, $r_1=-r_2$, so one agent's gain is the other's loss — chess, Go, a pursuit. Most real settings are mixed: partly aligned, partly opposed, like traders who all want liquidity but each want the better price, or autonomous cars that share the goal of avoiding collisions but compete for the merge. The single-agent MDP is the degenerate case $N=1$.

A worked matrix game: coordination and its traps

Even the simplest one-state Markov game exposes the difficulties. Consider the stag hunt, a two-player cooperative-leaning game where each player chooses to hunt Stag ($S$) or Hare ($H$). A stag needs both hunters; a hare can be caught alone. The payoff table (identical rewards, a cooperative game) is

Hunt stag together and both get $4$ — the best outcome. But if one hunts stag and the other defects to hare, the stag hunter gets $0$ (the stag escapes) while the defector still bags a hare for $3$. There are two pure Nash equilibria here: $(S,S)$ with payoff $4$ each, and $(H,H)$ with payoff $3$ each. Both are self-consistent — at $(H,H)$, unilaterally switching to stag drops you from $3$ to $0$, so no one deviates — yet one is strictly better for everyone. This is the crux of multi-agent learning that single-agent RL never faces: even with identical rewards and full cooperation, independent learners can converge to the safe, worse equilibrium $(H,H)$, because reaching the good one requires the risky belief that your partner will also pick stag. The problem is not conflicting incentives; it is coordinated equilibrium selection, and no single agent controls it.

Non-stationarity: the moving target

Here is the difficulty that everything downstream is built to address. From the vantage point of one agent, the others are part of the environment. Their policies determine how the world responds to that agent's actions. But the others are learning, so their policies keep changing — which means the environment that agent $i$ faces keeps changing underneath it. The transition and reward that agent $i$ effectively experiences, marginalizing out the others' actions,

depend on the other agents' policies ${\pi }_j$ through the product ${\prod }_{j\ne i}{\pi }_j$. When those policies change, $p_i$ changes. The environment is non-stationary from any single agent's local view, and non-stationarity breaks the guarantee that props up every single-agent method: the Markov property no longer holds for agent $i$ in isolation, because the best prediction of the future now depends on the hidden, drifting policies of the others, not on the state alone.²

The figure shows the pathology. Agent 1 is fitting a value function to its environment. But that environment is defined partly by agent 2's policy, and while agent 1 climbs toward the optimum, agent 2 shifts the optimum by learning. Agent 1 is aiming at a target that its opponent's learning keeps relocating.

Non-stationarity is why you cannot simply run single-agent RL per agent and expect the guarantees to survive. A replay buffer, the device that makes DQN and DDPG sample-efficient, becomes actively harmful: a transition stored when the other agents behaved one way no longer reflects how they behave now, so it teaches the agent about a world that no longer exists. Every design decision below is, at bottom, a way to cope with this one fact.

The naive baselines

Before the modern paradigm, two obvious approaches bracket the design space. Both fail in instructive, opposite ways.

Independent learning

The simplest thing to do is ignore the problem: give each agent its own single-agent algorithm — its own Q-network, its own DDPG — and let it treat every other agent as part of the environment. This is independent Q-learning (IQL) or, with policy gradients, independent learners.³ Each agent $i$ learns $Q_i(s,a_i)$ as if it were alone.

The appeal is that it is trivial to implement and, empirically, it often works — enough that it remains a standard baseline. The problem is that it comes with no convergence guarantee. Each agent's environment is non-stationary (the section above), so the Bellman target each agent regresses toward is a moving one; nothing forces the coupled learning to settle, and it can oscillate or diverge. Independent learning is the ignore it strategy: frequently fine, never provably fine.

Centralized control

The opposite extreme takes the non-stationarity away by refusing to have multiple agents at all. Treat the whole system as one agent whose action is the joint action $\mathbf{a}=(a_1,\dots ,a_N)$, and learn a single policy over that joint action space. Now the environment is a genuine MDP again — there is only one learner, so nothing is non-stationary — and every single-agent guarantee returns.

The catch is the size of the joint action space. If each of $N$ agents has $|\mathcal{A}|$ actions, the joint space has $|\mathcal{A}{|}^N$ — it grows exponentially in the number of agents. A team of ten agents with ten actions each has $10^{10}$ joint actions to evaluate per state. Worse, centralized control assumes a central controller with access to every agent's observations at execution time, which many settings forbid: a robot swarm acts on local sensors, a player sees only its own screen.

Independent learning scales but does not converge; centralized control converges but does not scale. The dominant modern paradigm is a hybrid that takes the good half of each.

Centralized training, decentralized execution

The two hard constraints apply at different times. During training — offline, in simulation, on your own hardware — you can afford a global view: you control the whole simulator and can hand any component all the agents' observations and actions. During execution — when the trained agents act in the real deployment — each agent may only see its own local observation, and must act on that alone. So separate the two phases. Use the global view where it is free (training) and demand only local information where it is required (execution). This is centralized training with decentralized execution (CTDE), the paradigm that organizes almost all of modern deep multi-agent RL.⁴

The centralized critic is what defeats non-stationarity. A critic that sees every agent's action $Q_i(\mathbf{x},a_1,\dots ,a_N)$ faces a stationary learning target: if you know what all agents did, the environment's response is fixed, so the moving-target problem disappears from the critic's point of view. The actors stay decentralized because they need to run without the others' information at test time. Training gets the global view; execution gets the local constraint.

MADDPG

The canonical CTDE algorithm is multi-agent DDPG (MADDPG), from Lowe et al. (2017).² It takes the DDPG actor-critic and gives each agent a centralized critic. Agent $i$ has a decentralized deterministic actor ${\mu }_i(o_i)$ that sees only its own observation, and a centralized critic $Q_i(\mathbf{x},a_1,\dots ,a_N)$ that sees the global state and all agents' actions.

The training rules are DDPG's, lifted to the joint view. The critic for agent $i$ regresses toward a bootstrapped target computed from the target actors of all agents, so the value is conditioned on everyone's next action:

Each actor is improved by the deterministic policy gradient through its own centralized critic — the critic that already accounts for the others' actions — while every other agent's action is held fixed at what the buffer recorded:

Because the critic conditions on the joint action, its target is stationary even though each actor is changing — that is precisely how CTDE removes non-stationarity. The single change from DDPG is the critic's input: local $Q(s,a)$ becomes joint $Q_i(\mathbf{x},a_1,\dots ,a_N)$.

MADDPG works across all three regimes — cooperative, competitive, and mixed — because each agent keeps its own reward $r_i$ and its own critic; nothing assumes the agents agree. In the paper's environments (a set of particle worlds with predators, prey, and communication) it learns coordinated and competitive behaviors that independent learners cannot.

Value factorization for cooperation

When the game is purely cooperative — all agents share one team reward — a different and cheaper idea applies. The team wants to learn one joint value $Q_{\text{tot}}(\mathbf{x},\mathbf{a})$, but that object is exponential in $N$ (the centralized-control problem again), and at execution time each agent must still pick its action from its own local value. The fix is to factorize the joint value into per-agent pieces and require the factorization to be consistent with greedy local action selection.

Value Decomposition Networks (VDN) take the simplest factorization: the joint value is the sum of per-agent utilities.⁵

The point of the sum is a property called decentralizability: the joint action that maximizes the sum is the one each agent gets by maximizing its own $Q_i$ locally, $\arg {\max }_{\mathbf{a}}{Q}_{\text{tot}}=(\arg {\max }_{a_1}{Q}_1,\dots ,\arg {\max }_{a_N}{Q}_N)$. So the team can be trained centrally on $Q_{\text{tot}}$ (regressing it toward the shared Bellman target) yet executed decentrally, each agent taking $\arg {\max }_{a_i}{Q}_i$ from its own local observation. The sum is a strong assumption, though: it forces each agent's contribution to be independent of the others.

QMIX relaxes the sum to any monotonic combination.⁶ It keeps the property that lets local greedy action selection agree with the global argmax while allowing far richer joint values. The requirement is that $Q_{\text{tot}}$ be monotonically increasing in each agent's $Q_i$:

Monotonicity is exactly enough to guarantee $\arg {\max }_{\mathbf{a}}{Q}_{\text{tot}}=(\arg {\max }_{a_i}{Q}_i{)}_i$ — if raising any agent's local value can never lower the team value, then everyone maximizing locally maximizes the team. QMIX realizes this with a mixing network that combines the per-agent $Q_i$ into $Q_{\text{tot}}$ using weights produced by a hypernetwork from the global state, with the weights constrained non-negative to enforce monotonicity. VDN is the special case where the mixer is a plain sum.

A worked factorization. Take two agents each with actions $\{0,1\}$ and a true joint value that rewards matching: $Q_{\text{tot}}(0,0)=Q_{\text{tot}}(1,1)=2$, $Q_{\text{tot}}(0,1)=Q_{\text{tot}}(1,0)=0$. Can VDN's sum $Q_1(a_1)+Q_2(a_2)$ represent this? It would need $Q_1(0)+Q_2(0)=2$ and $Q_1(1)+Q_2(1)=2$ but $Q_1(0)+Q_2(1)=0$ and $Q_1(1)+Q_2(0)=0$. Adding the first two gives $4$; adding the last two gives $0$; but both sums equal $Q_1(0)+Q_1(1)+Q_2(0)+Q_2(1)$, a contradiction ($4\ne 0$). So VDN cannot represent this coordination payoff — the sum forces each agent's contribution to be independent of the other's, exactly the wrong assumption when the reward depends on agreement. QMIX's monotonic mixer, whose weights come from the global state, can (the state-conditioned mixing breaks the additivity). This is the representational limit VDN pays for its simplicity, and why QMIX dominates it on coordination-heavy benchmarks.

But QMIX has its own limit, and it recurs. Monotonicity forbids representing any payoff where an agent's best action depends on what the others do in a non-monotone way — the classic failure is relative overgeneralization, where the safe action looks best on average across the partner's choices even though a coordinated risky action is globally optimal, and QMIX's monotonic mixer collapses onto the safe action. This is the QMIX-level echo of the stag hunt: the factorization structure can bias learning toward the risk-dominant equilibrium.

The trade is scope for cost. MADDPG handles competitive and mixed games at the price of a full joint-action critic per agent; VDN and QMIX handle only cooperative games but factor the joint value into cheap per-agent pieces, so they scale to more agents and are the standard choice for cooperative benchmarks like the StarCraft multi-agent challenge.

Counterfactual credit assignment (COMA)

Value factorization answers how do we get decentralized greedy actions from a joint value? A different question, just as central to cooperation, is the multi-agent credit-assignment problem: when the whole team shares one reward and the team does well, which agent's action deserves the credit? An agent that did nothing useful still sees the high team reward and reinforces its idle behavior.

COMA (Counterfactual Multi-Agent policy gradients, Foerster et al. 2018) solves this with a counterfactual baseline.⁷ It keeps a centralized critic $Q(\mathbf{x},\mathbf{a})$ and, for each agent $i$, computes how much better the action $a_i$ agent $i$ actually took was than the average over all the actions it could have taken, holding every other agent's action fixed. The counterfactual advantage is

The subtracted term marginalizes out agent $i$'s own action while freezing the others', so it isolates $i$'s individual contribution from the team's shared outcome. Because the critic is centralized (it sees $\mathbf{x}$ and all actions), this counterfactual is cheap to compute — one forward pass per alternative action — and it removes the confound that makes shared-reward policy gradients so noisy. COMA is the credit-assignment counterpart to QMIX's action-selection factorization: both are CTDE, but one factors the value and the other factors the blame.

Where this leaves us

Multi-agent RL is a genuinely different problem, and the pieces now assembled say why. The Markov game generalizes the MDP by giving every agent its own actions and reward; non-stationarity is its central pathology, because each agent's environment includes the others, who are themselves learning, so the ground never stops moving; and the naive baselines — independent learners and a single joint learner — fail on exactly that, one by ignoring the non-stationarity and the other by drowning in the exponential joint action space.

The dominant fix is centralized training with decentralized execution: let a critic see everything during training so it faces a stationary target, but keep each agent's executed policy dependent only on its own local observation. MADDPG, VDN, and QMIX are three points on that design — a centralized critic per agent, and two ways of factoring a joint value so decentralized greedy actions still maximize it.

CTDE handles cooperation and mixed settings. The purely competitive case has its own engine — an agent that generates its own curriculum by playing against copies of itself — which produced the landmark game-playing systems, and raises the question of what solved even means once there is an opponent. Self-play, those systems, and the equilibrium solution concepts continue in Multi-Agent RL: Self-Play and Solution Concepts.