Multi-agent reinforcement learning: Exercises

Parent: Multi-agent reinforcement learning. This page is a self-test ladder. Each problem is graded by cognitive level: L1 Recognition (can you name it?) → L2 Application (can you plug in?) → L3 Analysis (can you break it apart?) → L4 Synthesis (can you combine ideas?) → L5 Mastery (can you invent/prove?).

Every solution is hidden inside a collapsible callout — try first, then reveal. After each level there is a [!mistake] callout showing the trap most people fall into there.

Before we start, one reminder of notation so nothing here is used before it is defined:

Level 1 — Recognition

Recall Solution L1.1

The generalization is the Stochastic (Markov) Game: $⟨ N, S, {A^{i}}, P, {r^{i}}, γ ⟩$ . The ingredient whose meaning changes most is the transition $P$ : it now depends on the joint action $a$ , not a single action. Rewards $r^{i}$ also become per-agent. When $N = 1$ it collapses back to an MDP.

Recall Solution L1.2

(a) Fully cooperative — shared reward, $r^{1} = r^{2}$ .
(b) Fully competitive / zero-sum — $r^{1} = - r^{2}$ .
(c) Mixed / general-sum — each driver is self-interested yet crashes hurt everyone.

Recall Solution L1.3

It is replaced by a Nash Equilibrium: a joint policy where no agent gains by unilaterally deviating. We can't "just maximize reward" because there is no single reward — each agent has its own $V^{i}$ , and they may conflict. See Game Theory & Nash Equilibrium.

Level 2 — Application

Recall Solution L2.1

Your expected payoff for each pure move (Rock beats Scissors, loses to Paper): $E [Rock] = p_{S} - p_{P}, E [Paper] = p_{R} - p_{S}, E [Scissors] = p_{P} - p_{R} .$ At a mixed NE you must be indifferent between your moves (else you'd shift all weight to the best one). Set them equal: $p_{S} - p_{P} = p_{R} - p_{S} = p_{P} - p_{R} .$ With $p_{R} + p_{P} + p_{S} = 1$ the unique solution is $p_{R} = p_{P} = p_{S} = \frac{1}{3}$ . By symmetry both players play $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ and the game value = 0 (fair game). See figure below.

Figure — Multi-agent reinforcement learning

Recall Solution L2.2

Start from the single-agent Deterministic Policy Gradient and apply the chain rule through the critic: $\nabla_{θ_{i}} J^{i} = E [how my action moves with my params \nabla_{θ_{i}} μ^{i} (o^{i}) how team value moves with my action \nabla_{a^{i}} Q_{ϕ}^{i} (s, a)_{a^{i} = μ^{i} (o^{i})}] .$ Because $Q^{i}$ takes all actions as explicit inputs, its target is stationary — no hidden moving parts. See Policy Gradient Methods and Actor-Critic Methods.

Recall Solution L2.3

$\tilde{P}^{1} (s^{'} ∣ s, a^{1}) = \sum_{a^{2}} π^{2} (a^{2} ∣ s) P (s^{'} ∣ s, a^{1}, a^{2}) .$ It is weighted by $π^{2}$ . As agent 2 learns, $π^{2}$ changes, so $\tilde{P}^{1}$ changes over time — the Markov property is violated for agent 1. This is exactly why Q-Learning's convergence proof breaks in MARL.

Level 3 — Analysis

Recall Solution L3.1

Say early on agent 2 mostly picked action A. Agent 1's buffer fills with transitions where "picking A → reward $+ 1$ ", so agent 1 learns "A is good." Now agent 2 shifts to B. The pair that pays off is now $(B, B)$ , but agent 1's buffer still says "A good" — that data was generated under an old $π^{2}$ and is now stale/wrong. Agent 1 chases a target that no longer exists. Fix: a centralized critic $Q (s, a^{1}, a^{2})$ conditions on both actions, so each transition is correctly explained and never becomes stale.

Recall Solution L3.2

Let each agent pick $a^{i ⋆} = ar g max_{a^{i}} Q^{i}$ . Take any joint action $a$ . Change agents one at a time toward their local maximiser. Each such change raises (or keeps equal) that agent's $Q^{i}$ , and since $Q_{t o t}$ is non-decreasing in every $Q^{i}$ , each change cannot lower $Q_{t o t}$ . After all $N$ swaps we reach $a^{⋆} = (a^{1 ⋆}, \dots, a^{N ⋆})$ with $Q_{t o t} (a^{⋆}) \geq Q_{t o t} (a)$ . Hence $a^{⋆}$ is the global argmax. ∎ This is what lets decentralized greedy action selection match centralized greedy.

Recall Solution L3.3

Local maximisers: $a^{1 ⋆} = 1, a^{2 ⋆} = 1$ (value $1$ beats $- 2$ ). So IGM demands the joint argmax be $(1, 1)$ . (a) Sum: values over $(a^{1}, a^{2})$ are $(0, 0) \to - 4, (0, 1) \to - 1, (1, 0) \to - 1, (1, 1) \to 2$ . Max at $(1, 1)$ ✔ — IGM holds. (b) Product: $(0, 0) \to 4, (0, 1) \to - 2, (1, 0) \to - 2, (1, 1) \to 1$ . Max at $(0, 0) \neq = (1, 1)$ ✘ — IGM violated. Cause: the product is not monotone when a $Q^{i} < 0$ (two negatives multiply to a large positive). That is exactly why QMIX forces non-negative mixing weights.

Level 4 — Synthesis

Recall Solution L4.1

Recipe (CTDE + factorization):

Centralized training: use a joint critic $Q_{t o t} (s, a)$ so the target is stationary (all actions are explicit inputs). Kills non-stationarity.
Monotonic mixing (QMIX): enforce $\partial Q_{t o t} / \partial Q^{i} \geq 0$ so IGM holds and greedy decentralized action = centralized action.
Decentralized execution: each agent acts with $π^{i} (a^{i} ∣ o^{i})$ using only local observation — deployable without a coach.
Replay hygiene: because the joint critic sees $a$ , stored transitions are no longer stale (contrast L3.1). Each step directly targets a failure mode we diagnosed above. See Self-Play for the competitive analogue.

Recall Solution L4.2

Let the row player play $H$ with probability $p$ , column player play $H$ with probability $q$ . Column player's indifference (make row's payoff independent of column's move) forces the row mix so that column is indifferent; by symmetry each plays $p = q = \frac{1}{2}$ . Check row payoff at $q = \frac{1}{2}$ : $E = p (q \cdot 1 + (1 - q) (- 1)) + (1 - p) (q (- 1) + (1 - q) 1) = p (0) + (1 - p) (0) = 0$ . NE: $(\frac{1}{2}, \frac{1}{2})$ for both; value = 0.

Level 5 — Mastery

Recall Solution L5.1

Pure NE = joint actions where neither can improve alone.

$(A, A)$ : payoff $(1, 1)$ . If either deviates to B alone → mismatch → $0 < 1$ . NE.
$(B, B)$ : payoff $(2, 2)$ . Deviating alone → $0 < 2$ . NE.
$(A, B), (B, A)$ : payoff $0$ ; deviating to match gives $> 0$ . Not NE. So there are two pure NE. $(A, A)$ is a NE yet Pareto-dominated by $(B, B)$ . Lesson: NE only guarantees no unilateral improvement, not global optimality — agents can get stuck in a worse equilibrium. This is why coordination (and Self-Play / communication) matters.

Recall Solution L5.2

Use $f (Q^{1}, Q^{2}) = 2 Q^{1} + 3 Q^{2} + 5$ . Partials $= 2 \geq 0$ and $= 3 \geq 0$ → monotone, and it's not a plain sum. Evaluate on the L3.3 grid ( $Q^{1}, Q^{2} \in {- 2, 1}$ ):

$(0, 0) \to 2 (- 2) + 3 (- 2) + 5 = - 5$
$(0, 1) \to 2 (- 2) + 3 (1) + 5 = 4$
$(1, 0) \to 2 (1) + 3 (- 2) + 5 = 1$
$(1, 1) \to 2 (1) + 3 (1) + 5 = 10$ Max at $(1, 1)$ = the per-agent argmaxes → IGM holds ✔. Any positive weights work; monotonicity is what matters, not the exact numbers.

Recall Solution L5.3

A pure profile is one deterministic move each, e.g. (Rock, Rock) → tie, payoff $0$ . But the column player can switch to Paper and get $+ 1 > 0$ — a profitable unilateral deviation. Every pure profile has such a beating response (each move is beaten by exactly one other). Since some player can always deviate profitably, no pure NE exists. The best-response cycle Rock→Paper→Scissors→Rock never settles, so equilibrium must be mixed — recovering the $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$ answer of L2.1.