Multi-agent reinforcement learning: Worked examples

The scenario matrix

Before solving, let us lay out every cell a MARL problem can land in. Each worked example below is tagged with the cell(s) it fills.

Cell	Reward regime	What is being asked	Degenerate / edge feature
A	Competitive (zero-sum)	Find the mixed Nash equilibrium	No pure best response exists
B	Cooperative	Find the joint optimum & check IGM	Miscoordination penalty
C	Mixed / general-sum	Find a pure Nash (maybe more than one)	Multiple equilibria
D	Any	Show independent Q-learning gives a stale target	Replay buffer holds old opponent data
E	Cooperative	Test whether a mixer satisfies IGM	Non-monotone mixer breaks it
F	Any (CTDE)	Compute a centralized-critic policy gradient	Numeric chain-rule
G	Competitive	Limiting case: $N = 1$ collapses to an MDP	Degenerate agent count
H	Mixed	Real-world word problem (traffic / auction)	Self-interest vs shared good

Eight cells, eight (plus a bonus) worked examples. Let us fill them all.

Cell A — Competitive: mixed Nash of a zero-sum game

Worked example A. Rock–Paper–Scissors Nash

Two agents play Rock–Paper–Scissors. Win $= + 1$ , lose $= - 1$ , tie $= 0$ , and $r^{1} = - r^{2}$ (zero-sum). Find each agent's Nash-equilibrium policy and the game value.

Forecast: Guess — is there any single "best move"? What probability should you put on each of Rock, Paper, Scissors?

Write the payoff of each pure move against the opponent's mix. Let the opponent play Rock/Paper/Scissors with probabilities $(p_{R}, p_{P}, p_{S})$ . Your expected payoff for playing Rock is $u (Rock) = you beat Scissors p_{S} - Paper beats you p_{P} + tie 0 \cdot p_{R} = p_{S} - p_{P} .$ Similarly $u (Paper) = p_{R} - p_{S}$ and $u (Scissors) = p_{P} - p_{R}$ . Why this step? A Nash equilibrium is a fixed point of best responses; to find it we must know what each pure action earns against the opponent's strategy.
Impose the indifference condition. In a mixed equilibrium you randomize only over moves that are equally good — otherwise you'd shift all weight to the best one. So set $u (Rock) = u (Paper) = u (Scissors) .$ Why this step? If any move paid more, playing it with certainty would be a profitable unilateral deviation — contradicting Nash's "no one can improve alone."
Solve. $p_{S} - p_{P} = p_{R} - p_{S} = p_{P} - p_{R}$ together with $p_{R} + p_{P} + p_{S} = 1$ forces $p_{R} = p_{P} = p_{S} = \frac{1}{3}$ . Why this step? Symmetry: subtracting the equalities gives $p_{R} = p_{P} = p_{S}$ ; the probabilities summing to 1 fixes the value.
Game value. With uniform play each payoff is $\frac{1}{3} - \frac{1}{3} = 0$ , so the value of the game is $0$ .

Verify: If you deviate to pure Rock while the opponent stays uniform, your payoff is $u (Rock) = \frac{1}{3} - \frac{1}{3} = 0$ — no improvement. Deviation is never profitable ⇒ it is a Nash equilibrium. See Game Theory & Nash Equilibrium.

Cell B — Cooperative: joint optimum with a miscoordination trap

Worked example B. Coordination game team reward

Two teammates each pick action ${X, Y}$ . Shared reward (fully cooperative, $r^{1} = r^{2}$ ):

	opp $X$	opp $Y$
$X$	$+ 10$	$0$
$Y$	$0$	$+ 5$

Find the joint action that maximizes team return, and check the per-agent argmaxes agree with it (IGM).

Forecast: Two "match" cells pay off (both-X and both-Y). Which does a coordinated team pick — and can a greedy agent that only sees its own value get there?

Enumerate the joint value. The four joint actions give $r (X, X) = 10, r (X, Y) = 0, r (Y, X) = 0, r (Y, Y) = 5$ . Why this step? In the cooperative regime there is one number to maximize — the shared reward over the joint action — so we simply list them.
Joint argmax. $max = 10$ at $(X, X)$ . Why this step? The team optimum is defined as $ar g max_{a} Q_{t o t}$ ; it is $(X, X)$ .
Suppose a monotone mixer $Q_{t o t} = Q^{1} + Q^{2}$ with per-agent values learned so that each agent's $Q^{i} (X) > Q^{i} (Y)$ . Then each agent greedily picks $X$ , giving joint $(X, X)$ — the same cell. Why this step? This is the Individual-Global-Max (IGM) test: does per-agent greedy selection reproduce the global argmax? With a sum-mixer it does (the argmax of a separable sum is the tuple of argmaxes).

Verify: $(X, X) = 10 > (Y, Y) = 5$ , and both agents independently prefer $X$ . Decentralized greedy = centralized greedy ✔ — exactly the guarantee QMIX buys us. (Contrast: if the payoffs were $(Y, Y) = 12$ but each agent's marginal signal still pointed at $X$ , a naive learner could get stuck at $10$ — the classic "relative overgeneralization" trap.)

Cell C — Mixed / general-sum: multiple pure Nash

Worked example C. The "Bach or Stravinsky" game (two equilibria)

Two friends want to attend a concert together but prefer different composers. General-sum payoffs $(r^{1}, r^{2})$ :

	opp Bach	opp Strav
Bach	$(2, 1)$	$(0, 0)$
Strav	$(0, 0)$	$(1, 2)$

Find all pure Nash equilibria.

Forecast: They both want to be together — how many stable agreements exist, and is either "fairer"?

Best response of agent 1 to each choice of agent 2. If agent 2 plays Bach, agent 1 gets $2$ (Bach) vs $0$ (Strav) ⇒ best response Bach. If agent 2 plays Strav, agent 1 gets $0$ vs $1$ ⇒ best response Strav. Why this step? A Nash equilibrium is a cell where both rows are mutual best responses; we compute each agent's best response first.
Best response of agent 2 symmetrically. If agent 1 plays Bach, agent 2 prefers Bach ( $1 > 0$ ); if agent 1 plays Strav, agent 2 prefers Strav ( $2 > 0$ ). Why this step? Same fixed-point logic from agent 2's side.
Intersect. Both play Bach → mutual best response ✔. Both play Strav → mutual best response ✔. Mixed cells $(B a c h, S t r a v)$ and $(S t r a v, B a c h)$ pay $(0, 0)$ — either agent gains by switching, so not equilibria. Why this step? Nash = every unilateral deviation is non-improving; only the two "matched" cells survive.

Verify: At $(B a c h, B a c h)$ , agent 1 deviating to Strav drops $2 \to 0$ and agent 2 drops $1 \to 0$ — no one improves ⇒ Nash. Likewise $(S t r a v, S t r a v)$ . Two pure Nash equilibria exist — a hallmark of general-sum games and why "the optimal policy" is not unique in MARL.

Cell D — Non-stationarity: the stale replay-buffer target

Worked example D. Why Independent Q-Learning stores a wrong target

Coordination game from Cell B: reward $+ 10$ only if both pick $X$ (else $0$ ). Agent 1 runs Independent Q-Learning with a replay buffer. Learning rate $α = 0.5$ , $γ = 0.9$ , one-step (terminal, so no bootstrap). At time $t_{0}$ Agent 2 always played $X$ ; Agent 1's buffer stored the transition $(s, a^{1} = X, r = 10)$ and learned $Q^{1} (X) = 10$ . Now Agent 2 has switched to $Y$ . What does the real environment now return for $a^{1} = X$ , and how stale is the buffered target?

Forecast: Agent 1 still "believes" X pays 10. Agent 2 changed. What reward does X actually give now, and by how much is the belief wrong?

Compute the true current reward for $a^{1} = X$ . With Agent 2 now on $Y$ , the realized cell is $(X, Y) \Rightarrow r = 0$ . Why this step? The reward depends on the joint action $a = (a^{1}, a^{2})$ ; changing $a^{2}$ silently changes Agent 1's payoff — this is non-stationarity.
The buffered TD target. Agent 1's stored sample says target $= 10$ . Its Q-update toward that stale sample: $Q_{new}^{1} (X) = Q^{1} (X) + α (stale r 10 - Q^{1} (X)) = 10 + 0.5 (10 - 10) = 10.$ Why this step? The replay buffer feeds old opponent-generated data; the update reinforces a value the environment no longer produces.
The correct update would use the fresh reward $0$ : $Q_{correct}^{1} (X) = 10 + 0.5 (0 - 10) = 5.$ Why this step? Contrasting stale vs fresh isolates the error the buffer injects.
Staleness error $= 10 - 5 = 5$ : half the value is wrong on a single step.

Verify: Stale update leaves $Q^{1} (X) = 10$ ; a joint-action critic $Q (s, a^{1}, a^{2})$ would store $Q (s, X, Y) = 0$ and $Q (s, X, X) = 10$ separately, so no reward is ever mis-attributed — the CTDE fix. Numbers check: $10 + 0.5 (10 - 10) = 10$ and $10 + 0.5 (0 - 10) = 5$ .

Cell E — Value factorization: does the mixer satisfy IGM?

Worked example E. Monotone vs non-monotone mixer

Two agents, each with per-agent values $Q^{1} \in {Q^{1} (a) = 3, Q^{1} (b) = 1}$ and $Q^{2} \in {Q^{2} (a) = - 2, Q^{2} (b) = 4}$ . Test IGM for (i) the additive mixer $Q_{t o t} = Q^{1} + Q^{2}$ and (ii) the product mixer $Q_{t o t} = Q^{1} \cdot Q^{2}$ .

Forecast: Each agent greedily picks its own best action. For which mixer does that reproduce the true joint argmax — and why can a product go wrong when a value is negative?

Per-agent greedy actions. $ar g max Q^{1} = a$ (since $3 > 1$ ); $ar g max Q^{2} = b$ (since $4 > - 2$ ). So decentralized greedy picks the joint action $(a, b)$ . Why this step? During execution each agent acts on its own $Q^{i}$ — this is what IGM must be consistent with.
Additive mixer, all four joint values. $Q^{1} + Q^{2} : (a, a) = 1, (a, b) = 7, (b, a) = - 1, (b, b) = 5.$ Joint argmax $= (a, b) = 7$ , matches the per-agent greedy $(a, b)$ . IGM ✔. Why this step? A sum of monotone terms is monotone, so $\partial Q_{t o t} / \partial Q^{i} \geq 0$ and IGM holds.
Product mixer, all four joint values. $Q^{1} \cdot Q^{2} : (a, a) = - 6, (a, b) = 12, (b, a) = - 2, (b, b) = 4.$ Here the joint argmax is still $(a, b) = 12$ — but watch: $\partial (Q^{1} Q^{2}) / \partial Q^{1} = Q^{2} = - 2 < 0$ at the $a$ -column. Monotonicity is violated even though the argmax happened to survive. Why this step? IGM requires $\partial Q_{t o t} / \partial Q^{i} \geq 0$ everywhere; a negative operand makes the product decrease when a $Q^{i}$ increases, so with different numbers the argmax can flip.

Verify: Additive argmax $(a, b) = 7$ equals per-agent greedy ✔. For the product, the slope $\partial / \partial Q^{1} = Q^{2} = - 2 < 0$ confirms non-monotonicity — precisely why QMIX forces the mixing weights to be non-negative. See Actor-Critic Methods for how the critic supplies these $Q^{i}$ .

Cell F — CTDE: numeric centralized-critic policy gradient

Worked example F. MADDPG chain-rule by hand

Agent $i$ 's deterministic policy is $μ_{θ}^{i} (o^{i}) = θ \cdot o^{i}$ with $θ = 2$ , local observation $o^{i} = 3$ , so the action is $a^{i} = μ^{i} = 6$ . The joint-action critic near this point behaves like $Q_{ϕ}^{i} (s, a^{i}, a^{- i}) = - \frac{1}{2} (a^{i} - 4)^{2} + (terms in a^{- i})$ . Compute the policy-gradient contribution $\nabla_{θ} J^{i}$ .

Forecast: The critic peaks at $a^{i} = 4$ but we are pushing $a^{i} = 6$ . Which direction should $θ$ move — up or down?

Gradient of the action w.r.t. params. $\nabla_{θ} μ^{i} = \frac{\partial ( θ o ^{i} )}{\partial θ} = o^{i} = 3.$ Why this step? The MADDPG gradient factor $\nabla_{θ} μ^{i}$ answers "how does my action move when I nudge my parameter?" — from Policy Gradient Methods.
Gradient of the critic w.r.t. my action, evaluated at $a^{i} = μ^{i} = 6$ . $\nabla_{a^{i}} Q^{i} = \frac{\partial}{\partial a ^{i}} [- \frac{1}{2} (a^{i} - 4)^{2}] = - (a^{i} - 4)_{a^{i} = 6} = - 2.$ Why this step? This factor asks "how does the joint value change with my action?" Because $Q^{i}$ takes the whole joint action as input, this evaluation is stationary — the CTDE guarantee.
Chain them (MADDPG gradient). $\nabla_{θ} J^{i} = \nabla_{θ} μ^{i} \cdot \nabla_{a^{i}} Q^{i} = 3 \cdot (- 2) = - 6.$ Why this step? The chain rule links "params→action" and "action→value" exactly as in the parent note's MADDPG formula.

Verify: Gradient $= - 6 < 0$ , so gradient ascent $θ \leftarrow θ + η \nabla_{θ} J^{i}$ decreases $θ$ , shrinking $a^{i}$ from $6$ toward the critic's peak at $4$ — the correct direction. Sign sanity ✔.

Cell G — Degenerate limit: $N = 1$ collapses to an MDP

Worked example G. One agent = plain RL

Take the stochastic game $⟨ N, S, {A^{i}}, P, {r^{i}}, γ ⟩$ and set $N = 1$ . Show the Nash condition becomes ordinary optimality, and evaluate a tiny numeric case: single agent, single state, actions ${a, b}$ with $r (a) = 3, r (b) = 7$ , $γ = 0$ .

Forecast: With nobody else in the world, what does "no agent can improve unilaterally" reduce to?

The "everyone else" set is empty. With $N = 1$ , $π^{- i}$ is vacuous, so the Nash inequality $V_{π^{i}, π^{- i *}}^{i} \leq V_{π^{i *}, π^{- i *}}^{i}$ becomes $V_{π} \leq V_{π^{*}}$ for all $π$ . Why this step? Non-stationarity comes only from opponents; remove them and the effective transition $\tilde{P}^{i}$ is just $P$ — stationary.
This is exactly the MDP optimality condition: $π^{*}$ maximizes $V$ . So MARL ⟶ Markov Decision Process when $N = 1$ , as the parent note states. Why this step? Confirms the framework is a proper generalization, not a different object.
Numeric. With $γ = 0$ the value equals the immediate reward. $V (a) = 3, V (b) = 7$ , so $V^{*} = max (3, 7) = 7$ with $π^{*} = b$ . Why this step? Concreteness — a limiting sanity check with real numbers.

Verify: $max (3, 7) = 7$ , achieved by action $b$ ; no other action improves ✔. Single-agent Nash = MDP optimum.

Cell H — Real-world mixed word problem (traffic)

Worked example H. Two drivers at a merge

Two self-driving cars approach a one-lane merge. Each picks ${Go, Yield}$ . Payoffs (time saved, general-sum, $(r^{1}, r^{2})$ ):

	opp Go	opp Yield
Go	$(- 10, - 10)$	$(3, 1)$
Yield	$(1, 3)$	$(- 1, - 1)$

( $(- 10, - 10)$ = collision; $(- 1, - 1)$ = both waste time hesitating.) Find the pure Nash equilibria and explain the social tension.

Forecast: Both crashing is worst, both yielding is silly. How many stable outcomes exist, and do the cars "agree" on which one?

Best responses of car 1. vs Go: $- 10$ (Go) vs $1$ (Yield) ⇒ Yield. vs Yield: $3$ (Go) vs $- 1$ (Yield) ⇒ Go. Why this step? Identify mutual-best-response cells — the definition of Nash.
Best responses of car 2 (symmetric): vs Go ⇒ Yield; vs Yield ⇒ Go. Why this step? Same logic from the second agent.
Intersect. $(G o, Y i e l d)$ : car 1 Go is best vs Yield, car 2 Yield is best vs Go ✔ Nash. $(Y i e l d, G o)$ : symmetric ✔ Nash. $(G o, G o)$ and $(Y i e l d, Y i e l d)$ are not mutual best responses. Why this step? Two pure equilibria — the "who goes first" ambiguity that a coordination signal (traffic light / CTDE communication) must break.

Verify: At $(G o, Y i e l d) = (3, 1)$ , car 1 deviating Go→Yield drops $3 \to - 1$ , car 2 deviating Yield→Go drops $1 \to - 10$ — neither improves ⇒ Nash. Two equilibria ${(G o, Y i e l d), (Y i e l d, G o)}$ ; the tension is that each car prefers a different one (each wants to be the "Go"), so training must inject a tie-breaker — a real reason Self-Play and CTDE communication matter.

Wrap-up: the scenario map

Recall Which cell matches "two friends want to meet but disagree where"?

General-sum with multiple pure Nash — Cell C (Bach-or-Stravinsky) / Cell H (traffic merge).

Recall Why does the additive mixer

$Q^{1} + Q^{2}$ guarantee IGM but $Q^{1} \cdot Q^{2}$ may not? A sum is always monotone in each part ( $\partial / \partial Q^{i} = 1 \geq 0$ ); a product's slope is the other value, which can be negative — Cell E.

Active-recall flashcards

What is the mixed Nash of Rock–Paper–Scissors and its game value?

Uniform

(1/3, 1/3, 1/3)

for both players; value

= 0

In Cell D, after the opponent switches

X \to Y

, what is the true reward for

a^{1} = X

and the correct updated

Q^{1} (X)

True reward

= 0

; correct

Q^{1} (X) = 5

(stale buffer wrongly keeps

10

Why does QMIX force non-negative mixing weights?

To keep

\partial Q_{t o t} / \partial Q^{i} \geq 0

(monotonicity), which guarantees IGM; a product/negative-weight mixer can break it (Cell E).

For the MADDPG numeric example, what is

\nabla_{θ} J^{i}

and which way does

θ

move?

\nabla_{θ} J^{i} = 3 \cdot (- 2) = - 6

; gradient ascent decreases

θ

, pushing

a^{i}

from

6

toward the critic peak

4

How many pure Nash equilibria does the traffic-merge game have?

Two —

(G o, Y i e l d)

and

(Y i e l d, G o)