Multi-agent reinforcement learning
Single-agent RL assumes one decision-maker in a world that holds still while it learns. The moment a second learner shares that world, the ground moves: each agent's policy update silently rewrites every other agent's environment. The Markov guarantees you leaned on in lesson 16 quietly stop holding. This lesson is about what breaks, why, and the narrow set of cases where the cure is worth its price.
Where the agents actually are in a recsys / ads stack
"Multi-agent" sounds abstract until you name the agents in a system you already know. Three concrete groupings recur, and an interviewer wants you to reach for them immediately:
- The ranking cascade as cooperating agents. Retrieval, pre-rank, rank, re-rank each make a decision that constrains the next stage's action set. They share one long-term objective (session value, revenue) but optimize different local proxies. A retrieval recall change moves the distribution the ranker sees — that is one agent shifting another's environment, inside your own pipeline.
- Advertisers / bidders as competing agents. In the ad auction, every advertiser running auto-bidding is a learning agent adjusting bids to hit a target (ROAS, CPA, budget pacing). When one raises bids, it raises clearing prices for everyone — directly altering the rewards and dynamics every other bidder faces. The auction is a multi-agent game, and "everyone optimizes simultaneously" is exactly what naive single-bidder analysis ignores.
- Channels / slots / objectives on one surface. Feed vs ads vs stories vs notifications competing for a finite attention budget on one page; or several objectives (engagement, monetization, creator growth) each with a controller nudging exposure. Coordinating these is a cooperative MARL problem dressed as a constrained-allocation problem.
Why independent learners fail
The tempting first move: give each agent its own DQN or PPO, let each treat everyone else as part of "the environment," and train them all at once. This is independent learning (e.g. IQL — independent Q-learning), and it fails for two compounding reasons.
1 · Non-stationarity
From agent i's view, the effective transition is P(s′ | s, aᵢ, a₋ᵢ) — it depends on every other agent's action a₋ᵢ. While the others are also learning, a₋ᵢ's distribution keeps changing, so the environment agent i sees is non-stationary. The Bellman target it bootstraps toward is computed against opponents that no longer exist by the time the update lands. Convergence guarantees evaporate; experience replay makes it worse, because replayed transitions were generated by stale opponent policies that misrepresent the current game.
2 · Multi-agent credit assignment
If the agents share a team reward, each one faces a harder version of the credit problem from lesson 16: not just "which of my past actions earned this reward?" but "of the joint reward we all just received, how much was me?" A lazy agent can free-ride on a good teammate and still see high reward — the gradient cannot tell them apart. Independent learners have no mechanism to disentangle individual contribution from the team outcome.
The dominant fix: centralized training, decentralized execution
CTDE is the paradigm that organizes nearly all practical cooperative MARL. The idea is a clean asymmetry between train time and serve time:
- At training you have a god's-eye view — the logs contain every agent's observation and action. So you let a centralized critic condition on the joint state and joint action (x, a_1, …, a_N).
- At execution each agent acts from only its local observation o_i via its own actor π_i(a_i | o_i) — no need to see anyone else at serving time, which is what makes it deployable.
Why does this resolve non-stationarity? Because the critic — the thing that defines the learning target — conditions on a₋ᵢ explicitly. Once the other agents' actions are inputs to the value function rather than hidden noise folded into the environment, the target is again a well-defined, stationary function of its inputs. The environment stops looking non-stationary to the critic precisely because the moving part (everyone else's actions) is now observed, not marginalized away.
| Independent learners (IQL / per-agent PPO) | CTDE (MADDPG / QMIX) | |
|---|---|---|
| What the critic sees | own obs + action only | joint state + all agents' actions |
| Environment from each agent's view | non-stationary — others' policies drift | stationary to the critic — others' actions are inputs |
| Credit assignment | none — team reward is opaque | value decomposition / per-agent advantage |
| Convergence | oscillates / diverges in practice | far more stable empirically |
| Serving cost | local — cheap | local — cheap (critic is train-only) |
| Needs all logs at train time? | no | yes — the price of admission |
MADDPG — a centralized critic per agent
MADDPG (multi-agent DDPG) is CTDE applied to continuous or mixed action spaces. Each agent i keeps its own deterministic actor μ_i(o_i) and its own centralized critic Q_i(x, a_1, …, a_N) that scores the joint action. The critic's Bellman target uses every agent's next action from their target actors:
The actor update is the deterministic policy gradient, but pushed through the joint critic — agent i improves its own action while holding the others' actions fixed at their observed values:
The single load-bearing idea: because Q_i takes a₋ᵢ as an argument, it is a stationary function even while the other policies change — the gradient agent i follows is computed against the others' actual current actions, not against a stale average baked into the environment. Crucially MADDPG allows a different reward r_i per agent, so it handles cooperative, competitive, and mixed games — making it the natural fit for the auction setting where each advertiser has its own objective.
QMIX and value decomposition — the cooperative case
When the agents are purely cooperative and share one team reward (the ranking-cascade case), you do not need a critic per agent — you need to factorize a single joint value into per-agent pieces so each agent can act greedily on its own and still be globally optimal. Two designs, increasing in expressiveness:
- VDN (value decomposition networks) — assume the joint action-value is just the sum of per-agent utilities: Q_tot = Σ_i Q_i(o_i, a_i). Simple, but the additivity is a strong, often-violated assumption.
- QMIX — generalize the sum to a learned monotonic mixing network: Q_tot = f(Q_1, …, Q_N; s) with the constraint ∂Q_tot / ∂Q_i ≥ 0 for all i (enforced via non-negative mixing weights produced by a hypernetwork from the global state).
Why the monotonicity constraint is the whole trick: if Q_tot is monotonically increasing in each Q_i, then maximizing Q_tot jointly is the same as each agent independently maximizing its own Q_i —
This is the IGM (Individual-Global-Max) property: decentralized argmax equals centralized argmax. So you train the mixer centrally (it sees the global state), but at execution each agent just takes argmax a_i Q_i from its local network — no mixer needed at serve time. VDN is the special case where the mixer is a fixed sum; QMIX buys richer (but still IGM-preserving) credit assignment at the cost of being unable to represent games where coordination requires non-monotonic interactions.
| VDN | QMIX | MADDPG | |
|---|---|---|---|
| Game type | cooperative (shared reward) | cooperative (shared reward) | coop / competitive / mixed |
| Joint value form | Σ_i Q_i | monotonic mix f(Q_i; s) | per-agent Q_i(x, a_1…a_N) |
| Action space | discrete | discrete | continuous / mixed |
| Per-agent reward? | no | no | yes |
| Key constraint | additivity | monotonicity (IGM) | none — but N critics to train |
| Recsys fit | weak baseline | cooperating ranking stages | competing bidders / advertisers |
Cooperative, competitive, mixed — and what "optimal" even means
The single most important framing question in any multi-agent problem: what is the relationship between the agents' rewards?
| Game | Reward structure | Solution concept | Recsys/ads example |
|---|---|---|---|
| Cooperative | shared team reward | social optimum (maximize the sum) | ranking cascade optimizing session value |
| Competitive (zero-sum) | one's gain = another's loss | minimax / Nash equilibrium | two advertisers fighting for one slot |
| Mixed (general-sum) | partly aligned, partly opposed | Nash equilibrium (often ≠ social optimum) | auto-bidders: share the marketplace, compete for impressions |
The crucial gap is between two notions of "good." A Nash equilibrium is a profile where no single agent can improve by unilaterally deviating — it is stable, the place selfish learners settle. A social optimum maximizes the sum of rewards — what a benevolent central planner would pick. In general-sum games these are different points, and the equilibrium can be strictly worse for everyone. The size of that gap is the cost of decentralized selfishness.
Interactive · two auto-bidders and the commons
Two auto-bidders share one marketplace. Each picks an output/intensity q (how hard it pushes into the auction). The marketplace value per unit falls as total pressure rises: p = a − (q_A + q_B), and each pays a marginal cost c, so each agent's payoff is π = q · (a − q_A − q_B − c). Under independent (Nash), each best-responds to maximize its own payoff; under coordinated, they jointly restrain output to maximize total payoff. This is a Cournot duopoly — the textbook tragedy of the commons. Toggle the mode and watch the efficiency gap open and close.
The honest verdict — when MARL earns its complexity
Time for intellectual honesty, because an interviewer is testing whether you can resist a shiny tool. Full MARL in production recsys is mostly research, rarely shipped. The reasons are concrete: it inherits every hardship of single-agent RL (off-policy bias, reward design, the impossibility of free online exploration on real users — all from lesson 16) and adds non-stationarity, joint credit assignment, and the data plumbing to log every agent's observations and actions together. The complexity-to-payoff ratio is brutal.
The pragmatic moves that beat naive MARL in almost every real system:
- Collapse to one agent with one global reward. The ranking cascade is "multi-agent" only if you insist on it. Define a single session/revenue objective and train the whole pipeline (or each stage) against that shared reward — a cooperative problem with a shared reward is often best solved by simply not pretending the stages are independent agents at all.
- Use mechanism design, not MARL, for competition. You do not train advertisers' bidders for them. You design the auction (incentive-compatible formats, reserves, pacing controllers from lesson 10) so that each advertiser's selfish optimum is also good for the marketplace. Shape the game; do not try to centrally control independent players you do not own.
- Reserve genuine MARL for the narrow cases where agents truly have private observations they cannot share at serve time, the coupling is strong, and a shared-reward single-agent reduction provably loses value — e.g. coordinating heterogeneous controllers (engagement vs monetization vs creator-growth) that must act on distinct local signals, or simulating a marketplace to stress-test a mechanism before launch.
Interview prompts you should be ready for
- "Single-agent RL was working. Why does adding more learning agents break it?" (Non-stationarity: from any one agent's view the transition is P(s′|s,aᵢ,a₋ᵢ) and a₋ᵢ keeps changing as the others learn, so the environment is a moving target — Bellman convergence and replay both assume stationarity and break. Plus multi-agent credit assignment: a shared reward cannot tell who actually earned it.)
- "What is CTDE and why does it specifically fix non-stationarity?" (Centralized training, decentralized execution: a centralized critic conditions on the joint state and all agents' actions during training; actors run on local observations at serving. It fixes non-stationarity because once a₋ᵢ are explicit inputs to the value function, the target is a stationary function of its inputs rather than noise folded into a drifting environment.)
- "Contrast MADDPG with QMIX — when would you pick each?" (MADDPG: per-agent actor + per-agent centralized critic Qᵢ(x,a₁…a_N), allows distinct rewards rᵢ, handles competitive/mixed games and continuous actions — fits competing advertisers. QMIX: cooperative shared-reward only, factorizes one joint Q into per-agent Qs via a monotonic mixing network — fits cooperating ranking stages with discrete actions.)
- "Why does QMIX impose a monotonicity constraint, and how does it differ from VDN?" (Monotonicity ∂Q_tot/∂Qᵢ ≥ 0 guarantees the IGM property: decentralized per-agent argmax equals the centralized joint argmax, so agents can act greedily on local Qs at serve time. VDN is the special case where the mixer is a plain sum Σ Qᵢ; QMIX learns a state-conditioned monotonic mixer, strictly more expressive while preserving IGM.)
- "Every advertiser turns on an aggressive auto-bidder. What happens to the marketplace?" (Tragedy of the commons: each rational bid increase raises clearing prices for all, so the system settles at a high-bid Nash equilibrium where every advertiser's surplus is lower than at the modest social optimum, yet no one can unilaterally back off. The cure is mechanism design — reserves, IC formats, pacing — to align equilibrium with social optimum, not central control of bidders you don't own.)
- "Nash equilibrium vs social optimum — why does the distinction matter here?" (Nash = no agent gains by unilateral deviation; it's where selfish learners settle. Social optimum = maximizes the sum of rewards. In general-sum games they diverge and the equilibrium can be worse for everyone. The gap is the cost of decentralized selfishness, and closing it via mechanism design is often the real lever — not a fancier learning algorithm.)
- "Would you actually deploy MARL in a recommender? Defend your answer." (Usually no. It inherits all of single-agent RL's pain — off-policy bias, reward design, no free online exploration — and adds non-stationarity, joint credit assignment, and heavy logging. First try the reduction: one shared global reward + a single/cooperative agent, or solve competition with auction mechanism design. Reserve true MARL for strong coupling with genuinely private serve-time observations, or for offline marketplace stress-testing.)