Visual walkthrough — Multi-agent reinforcement learning
We will use only these ideas, and we define each one when it first appears: a state, an action, a transition probability, and an expectation (weighted average).
Step 1 — One agent, one frozen world
WHAT: We draw a single agent standing in a state, picks an action, and lands somewhere.
WHY: This is the world an ordinary Markov Decision Process describes — and the world Q-Learning was proven to solve. We must see it clearly before we break it.
PICTURE: The red circle is our agent. Two arrows leave state under action : one to (thick, likely), one to (thin, unlikely). The two probabilities on the arrows sum to .
Step 2 — A second learner walks in
WHAT: The same starting state , but now where we land depends on both players' moves at once.
WHY: This is the leap from an MDP to a Stochastic (Markov) Game — the framework in the parent note. Real systems (traffic, auctions, games) work this way: outcomes are joint.
PICTURE: From , four arrows fan out — one for each combination . The red arrows are the two futures for my chosen ; they differ only because of what the other agent did.
Step 3 — What a policy is, and why it makes things move
WHAT: We attach numbers to the other agent's choices: maybe today they play Up with probability , Down with .
WHY: Because I don't observe before I act, from my seat the other agent is a dice-roller. To predict my own future I must average over their dice.
PICTURE: A little bar chart hovers over agent : two bars, heights and . The red bar () is the move they favour today — remember it, it will move in Step 6.
Step 4 — Folding the other agent into "the environment"
WHAT: We collapse the four-arrow fan of Step 2 back into a two-arrow picture — but the arrow thicknesses are now blends, weighted by .
WHY: This gives me an effective transition that depends only on my action — exactly the single-agent shape Q-Learning expects. The tilde means "effective / as I experience it."
PICTURE: On the left, the four true arrows (from Step 2). On the right, two red "blended" arrows: each is the -weighted sum of the branches that share my action. The bar chart from Step 3 is the mixing recipe.
Step 5 — Looks stationary… so far
WHAT: Freeze the opponent's policy . Then is a fixed table of numbers — a perfectly ordinary MDP for me.
WHY: This is the seductive case. If opponents never learned, Q-Learning would work fine and Independent Q-Learning would be correct. We show this honestly so the failure in Step 6 is undeniable.
PICTURE: A snapshot labelled : the blended red arrows have definite thicknesses. A tag reads "stationary — proof holds." This is a still frame of a film about to start moving.
Recall Why does Q-Learning need stationarity at all?
Its convergence proof relies on visiting each pair and averaging a fixed target. If the target's underlying rule keeps shifting, the average chases a moving quantity and never settles. ::: A fixed gives fixed targets; a drifting does not.
Step 6 — The opponent learns → the ground moves (the punchline)
WHAT: Let time pass. The opponent, also a learner, updates its policy: the red bar that was on Up slides down to ; Down rises to . Plug the new into Step 4's formula.
WHY: is built out of . Change and changes with it — without any change in the true rule and without me doing anything different. My world morphed while I stood still.
PICTURE: Two panels side by side. Left = time (red bar tall on Up, blended arrows one way). Right = time (red bar tall on Down, blended arrows visibly different thicknesses). Same , same me — different world.
Step 7 — The cure: put back on the table (CTDE)
WHAT: During training, a centralized critic reads both actions. During execution, each agent still acts alone using only its local view — this is Centralized Training, Decentralized Execution.
WHY: As a function of the critic is stationary: change the opponent's behaviour and you simply land on a different input row of the same fixed function — the function itself never gets a time-stamp. That is the whole trick behind MADDPG, COMA, QMIX.
PICTURE: A box labelled with two input wires ( in red, in black) instead of one. A tag: "input changes, function stays fixed → stationary target."
The one-picture summary
The whole arc on one canvas: a single agent (stationary, provable) → add an opponent (joint action) → average the opponent away to fake a single-agent view () → the opponent learns, so that average silently drifts (non-stationarity, the disease) → stop averaging, feed the joint action in explicitly (CTDE, the cure).
Recall Feynman retelling — the walkthrough in plain words
Picture yourself learning a video game where the world reacts only to your buttons. That's the easy world (Step 1), and there's even a math proof you can master it. Now a friend joins, and the game reacts to both your buttons pressed together (Step 2). You can't see their button before you press yours, so from your seat they're rolling dice (Step 3). To keep pretending you're playing solo, you average over their dice — and get a made-up "solo world" (Step 4). If your friend never improved, this trick would work perfectly (Step 5). But your friend is also learning — and every time their dice-habits change, your made-up world quietly changes too, even though the real game and your own play never changed (Step 6). That silent shifting is non-stationarity, and it's why "just learn alone" fails. The cure: while practicing, let a coach who can see both players' buttons judge your moves — now nothing is hidden in an average, so the judgment is rock-steady. During the real match, you still play alone (Step 7). That coach-sees-everything, players-act-alone idea is CTDE.