Multi-Agent RL: Cooperative and Competitive

Consider a fast bowler running in against a set batsman in a T20 death over. The bowler decides, before releasing the ball, whether to bowl a yorker (full, at the base of the stumps) or a bouncer (short, rising toward the ribs). The batsman, because a shot requires committing weight and stance before the ball arrives, simultaneously decides which delivery to prepare for. Neither sees the other's choice in advance. The bowler's payoff (control, dot balls, wickets) and the batsman's payoff (runs) are locked together ball for ball: whatever the batsman gains, the bowler loses. Try writing this as a standard Markov Decision Process, the object every earlier reinforcement learning chapter has been built on, with one agent, one reward signal, and an environment that reacts only to that agent's action. It does not fit. There are two decision-makers, each adapting to the other's history, and the "environment" each of them experiences is itself another learning agent.

Now switch scenes to a large e-commerce fulfillment center outside Bhiwandi during a festive-season surge. Forty sorting robots share a warehouse floor, and the number that matters — total packages correctly routed per hour — depends on all forty of them simultaneously, not on any single robot's individual path. If robot 14 cuts across an aisle to shave two seconds off its own route, robot 27 may lose twenty seconds rerouting around it. There is one team reward, but forty separate decision-makers producing it, and none of them can see what all the others are doing before it acts. This also breaks the single-agent MDP — not because the agents are adversaries, but because one shared reward has to be traced back to forty individually taken actions, and no single robot's local view tells it whether its own last move helped or hurt the team.

Both scenarios are instances of the same generalized object, a Markov game, and the difference between them — adversarial reward versus shared reward — is not cosmetic. It changes which algorithms even make sense to run. This chapter builds the formalism, solves the bowler-batsman duel to an exact numeric answer, and traces the architecture — centralized training, decentralized execution — that almost every deployed cooperative and competitive multi-agent system uses today.

From One Agent to a Game: The Markov Game Formalism

Recall the single-agent MDP: a tuple (S, A, P, R, gamma) — states, actions, a transition function P(s'|s,a), a reward function R(s,a,s'), and a discount factor. A Markov game (also called a stochastic game) generalizes this to n agents: the tuple is (N, S, {A_i}, P, {R_i}, gamma), where N = {1, ..., n} is the set of agents, each agent i has its own action set A_i, and the joint action a = (a_1, ..., a_n) is what actually drives the world. Crucially, both the transition function P(s' | s, a) and every agent's reward function R_i(s, a, s') depend on the entire joint action, not on agent i's action alone. Set n = 1 and this collapses exactly back to the ordinary MDP of earlier chapters — a Markov game is the strict generalization, not a different topic bolted on beside it.

The reward structure across agents is what splits the field into three regimes. If R_1 = R_2 = ... = R_n = R for every state and joint action, every agent is optimizing the same number — this is the fully cooperative case (sometimes called a Markov team problem, or a Dec-POMDP once observations are only partially shared). If n = 2 and R_1 = -R_2 always, the game is zero-sum and strictly competitive — one agent's gain is the other's exact loss. Everything in between, where rewards are neither identical nor exact opposites, is the general-sum case, and it is the least well-understood: most of the clean convergence results in this chapter apply to the cooperative and zero-sum extremes, not to general-sum games.

There is one structural fact that drives almost every design choice in this chapter: non-stationarity. Watkins and Dayan's original convergence proof for Q-learning depends on the learner facing a stationary environment — a transition and reward function that does not change while learning proceeds. In a Markov game, from agent i's point of view, "the environment" silently includes every other agent's policy. Because those policies are themselves being updated by their own learning processes during training, the effective dynamics agent i experiences keep shifting underneath it. The stationarity assumption the proof relies on is violated by construction, so nothing guarantees convergence — and in adversarial settings, two independently learning agents can cycle indefinitely, each perpetually best-responding to a version of the other that no longer exists by the time it responds.

The Cooperative Case: Crediting Forty Robots for One Number

The naive approach to the warehouse problem is independent Q-learning (IQL): give each robot its own Q-table, treat every other robot as part of the environment, and run ordinary Q-learning per robot. It sometimes works in practice, but it inherits the non-stationarity problem directly — each robot's Q-table is chasing a moving target, since the "environment" it is learning against is thirty-nine other Q-tables also being updated — and it gives no principled way to assign credit. If the team reward improves, IQL has no mechanism to say which robot's action deserves the credit; this is the classic multi-agent credit-assignment problem, sometimes nicknamed the lazy-agent problem, since an agent can free-ride on its teammates' improvements without its own policy ever learning anything useful.

Value Decomposition Networks (VDN) fix this by constraining how the joint value is built, not by centralizing decision-making. Each agent keeps its own per-agent utility function Q_i(s, o_i, a_i), but instead of training these independently, the team's joint value is forced to be their sum: Q_tot(s, a) = Q_1(s, o_1, a_1) + Q_2(s, o_2, a_2) + ... + Q_n(s, o_n, a_n). Training uses the single team TD-error computed against Q_tot, and that one error signal backpropagates into every Q_i simultaneously, so each agent's utility function is shaped by the team outcome even though the outcome is never split up by hand. The payoff of the additive constraint is a property called Individual-Global-Max (IGM): because the sum of individually maximized terms is the maximum of the sum, argmax over the full joint action space of Q_tot is exactly reproduced by each agent independently taking the argmax of its own Q_i. A concrete instance makes this exact rather than asserted. Suppose two robots each choose between two shelves, Left or Right, and after training the per-agent utilities are Q_1(Left) = 3, Q_1(Right) = 5, Q_2(Left) = 2, Q_2(Right) = 6. The four joint values are Q_tot(L,L) = 5, Q_tot(L,R) = 9, Q_tot(R,L) = 7, Q_tot(R,R) = 11, so the joint optimum is (Right, Right) at 11. Each robot acting purely on its own utility also picks Right (5 beats 3 for robot 1; 6 beats 2 for robot 2) — the decentralized choice and the centralized optimum agree exactly, with no communication between the robots at decision time.

That agreement is not free — it is bought by the additive assumption, and it breaks the moment the true team reward is not decomposable that way. Suppose the real reward table gives a large bonus only when both robots go Left at the same instant to jointly lift a heavy carton — say R(L,L) = 10, R(L,R) = 1, R(R,L) = 1, R(R,R) = 2 — with no bonus for any other combination. No choice of Q_1(a) + Q_2(b) can represent that interaction term, because the (L,L) synergy is not separable into two independent per-robot contributions; each robot maximizing its own additive share will simply never discover it. QMIX loosens VDN's constraint by replacing the plain sum with a learned mixing network subject to a weaker condition — that Q_tot is monotonically non-decreasing in each Q_i — which is strictly more expressive than addition while still preserving IGM. It still cannot represent every possible non-monotonic team reward, but it captures a meaningfully larger class of genuine teamwork than a simple sum can.

The Competitive Case: When the Environment Learns Back

In a two-player zero-sum Markov game, standard Q-learning's update rule breaks in a specific way: the usual backup Q(s,a) <- Q(s,a) + alpha[r + gamma * max_a' Q(s',a') - Q(s,a)] assumes that after reaching s', the agent gets to pick the best next action for itself. In a zero-sum game, the opponent moves too, and the opponent is actively trying to push the state toward whatever is worst for the agent. Littman's 1994 minimax-Q algorithm replaces the plain max with a maximin: rather than committing to a single best action, the agent computes a full mixed strategy (a probability distribution over its own actions) that maximizes its worst-case expected value against whichever action the opponent picks in response. This also changes the solution concept itself. Single-agent RL looks for the optimal deterministic policy; a zero-sum Markov game generally has no deterministic policy that dominates every opponent strategy, so the target becomes a Nash equilibrium — a pair of (possibly randomized) strategies such that neither player can improve by unilaterally deviating, given the other player's strategy is fixed.

The bowler-batsman duel is the smallest possible instance of exactly this object: a Markov game with a single state (so it reduces to a one-shot matrix game), two agents, two actions each, and a strictly zero-sum reward. Solving it by hand, in full, is the cleanest way to see what "compute a Nash equilibrium" actually means as arithmetic rather than as a slogan.

Worked Example: Solving the Bowler-Batsman Duel

Entries are the batsman's expected runs relative to a baseline ball; the bowler's payoff on each cell is the exact negative, since the game is zero-sum. A quick check rules out a pure-strategy answer: at every one of the four cells, at least one player can strictly improve by unilaterally switching (for instance at Bowler=Bouncer, Batsman=PrepBouncer, worth +4 to the batsman, the bowler can switch to Yorker and turn it into -3 for the batsman, i.e. +3 for the bowler) — so no single deterministic pair of choices is stable, and only a mixed strategy can be an equilibrium.

Let the bowler bowl a yorker with probability p and a bouncer with probability (1 - p). For p to be part of an equilibrium, it must leave the batsman indifferent between the two preparations — if one preparation were strictly better for the batsman, the batsman would play it with certainty, and the bowler could then exploit that certainty. Setting the batsman's expected payoff from each preparation equal:

p(2) + (1-p)(-1) = p(-3) + (1-p)(4)
3p - 1 = -7p + 4
10p = 5
p = 0.5

The bowler's equilibrium mix is an even split, 50% yorker and 50% bouncer. Now do the same from the other side: let the batsman prepare for a yorker with probability q. The bowler's mix must leave the bowler indifferent between the two deliveries, and the bowler's payoff is the negative of the batsman's:

-[q(2) + (1-q)(-3)] = -[q(-1) + (1-q)(4)]
-(5q - 3) = -(-5q + 4)
-5q + 3 = 5q - 4
7 = 10q
q = 0.7

The batsman's equilibrium mix prepares for a yorker 70% of the time and a bouncer only 30% of the time, even though the bowler's own equilibrium mix is an exact coin flip. This is the payoff of doing the algebra rather than guessing "both players should be 50-50 since the game looks symmetric": the game is not symmetric in its penalties. Misjudging a yorker costs the batsman -3, while misjudging a bouncer costs only -1, so the batsman's equilibrium response leans toward guarding the costlier mistake, even facing a perfectly even bowler. Substituting p = 0.5 back into either batsman payoff line gives the value of the game: V = 0.5(2) + 0.5(-1) = 0.5 runs to the batsman per ball. As a check from the other side, substituting q = 0.7 gives -5(0.7) + 3 = -0.5 for the bowler on the yorker row and 5(0.7) - 4 = -0.5 on the bouncer row — both equal -0.5, confirming the same game value from both directions independently.

Tracing the Solver in Code

The hand derivation above is just two linear equations in one unknown, solved twice. The same computation, done symbolically instead of by hand, is short enough to trace line by line:

import numpy as np

# rows = bowler's delivery, cols = batsman's preparation
# entries = batsman's expected payoff (bowler's payoff is the negative)
A = np.array([[ 2, -3],
              [-1,  4]], dtype=float)

# bowler's mix (p, 1-p) must make the batsman indifferent between columns:
# col0(p) = p*A[0,0] + (1-p)*A[1,0] = p*a0 + b0
# col1(p) = p*A[0,1] + (1-p)*A[1,1] = p*a1 + b1
a0, a1 = A[0,0] - A[1,0], A[0,1] - A[1,1]
b0, b1 = A[1,0], A[1,1]
p = (b1 - b0) / (a0 - a1)

# batsman's mix (q, 1-q) must make the bowler indifferent between rows:
# row0(q) = -(q*A[0,0] + (1-q)*A[0,1]) = -(q*c0 + d0)
# row1(q) = -(q*A[1,0] + (1-q)*A[1,1]) = -(q*c1 + d1)
c0, c1 = A[0,0] - A[0,1], A[1,0] - A[1,1]
d0, d1 = A[0,1], A[1,1]
q = (d1 - d0) / (c0 - c1)

V = p * A[0,0] + (1 - p) * A[1,0]   # value of the game to the batsman

print(f"bowler plays Yorker with p = {p}")
print(f"batsman prepares for Yorker with q = {q}")
print(f"value of the game (expected runs to batsman) = {V}")

Trace it: a0 = 2 - (-1) = 3, a1 = -3 - 4 = -7, b0 = -1, b1 = 4, so p = (4 - (-1)) / (3 - (-7)) = 5 / 10 = 0.5. Then c0 = 2 - (-3) = 5, c1 = -1 - 4 = -5, d0 = -3, d1 = 4, so q = (4 - (-3)) / (5 - (-5)) = 7 / 10 = 0.7. Finally V = 0.5(2) + 0.5(-1) = 0.5. The three printed lines read exactly "p = 0.5", "q = 0.7", "value of the game = 0.5" — matching the hand derivation, because the code is nothing more than the same two indifference equations with p and q factored out algebraically instead of substituted by hand.

Why Nobody Solves StarCraft Exactly: Self-Play

The bowler-batsman duel worked because it is tiny: two actions per side, one state, a 2x2 linear system solved in closed form. Minimax-Q generalizes this cleanly across an entire Markov game — at every state s, solve the same kind of matrix game (using the current Q-estimates as payoffs) as a linear program, back up the resulting value V(s), and repeat for every state during training. That is exact, and it is correct. It is also completely impractical the moment the game is real. Go has on the order of 10^170 legal positions; StarCraft II has an action space of roughly 10^26 legal actions per timestep. Solving a linear program at every one of those states, every training step, is not on the table.

The practical substitute is self-play: instead of computing the equilibrium mix directly, an agent plays repeated games against copies of itself — often a pool of past versions rather than only the current best, to avoid endlessly cycling against a single static target — and nudges its policy toward whatever wins more often. This is structurally the same update independent Q-learning performs against whatever the opponent has been doing, except the opponent is now a snapshot of the same learning process reflected back. AlphaGo and AlphaZero reached superhuman Go and chess play this way, with no human game data at all; OpenAI Five and DeepMind's AlphaStar extended the idea to Dota 2 and StarCraft II by training large populations of agents against evolving pools of their own past selves — a "league" — specifically to stop the current policy from overfitting to one static opponent and losing badly to a strategy outside that opponent's repertoire. In the two-player zero-sum case, self-play against an ever-improving pool provably drifts toward a Nash equilibrium under fairly general conditions, which is the theoretical justification for the whole approach. In general-sum games — most real cooperative-competitive mixes, such as several delivery platforms simultaneously competing for the same riders while depending on the same shared road network — no such convergence guarantee exists, and matching a good general-sum solution concept to a training algorithm remains an open research question.

Architecture: Centralized Training, Decentralized Execution

The cooperative warehouse case and the competitive duel case converge on the same practical training architecture, because both share the same deployment constraint: whatever gets learned in simulation, each agent's deployed policy can only condition on that agent's own local observation. Robot 14 does not get a live feed of every other robot's internal state before deciding its next move; the bowler does not see the batsman's chosen preparation before releasing the ball. During training, though — in simulation, or in a recorded self-play league — access is usually much richer: the full joint state, every agent's action, every agent's reward. Centralized-training-decentralized-execution (CTDE) architectures such as MADDPG and QMIX exploit exactly that asymmetry. A centralized critic that is allowed to see the whole joint state and every agent's action is used only to compute sharper gradients during training; at execution time that critic is discarded entirely, and each agent acts from a lightweight policy that has only ever consumed its own observation.

Solid arrows are the path that survives into deployment: an observation in, an action out, per agent, with no cross-talk between them. Dashed arrows exist only inside the training loop, where a simulator can hand the critic the global state and every agent's action to compute a sharper TD-error than any single agent could estimate from its own narrow view alone.

A Common Misconception

A frequent shortcut in reasoning about cooperative multi-agent RL: "if every agent gets the same shared team reward, training them is basically the same as training one giant single agent that outputs all the actions at once — there's nothing structurally new here." This is wrong, and the architecture above is the direct rebuttal. Reward alignment and information access are two separate axes, and the misconception collapses them into one. Even with a perfectly shared reward, each agent at deployment time must choose its action from only its own local observation — it is solving a decentralized partially observable Markov decision process (Dec-POMDP), not a fully observable single-agent MDP with a wide action vector. The distinction is not academic: a Dec-POMDP is NEXP-complete to solve optimally in the worst case, provably harder than a single-agent POMDP, which is only PSPACE-complete — precisely because the planner cannot coordinate the agents' information, only their reward. A single monolithic policy fed the full joint state and outputting all forty robots' actions at once would train just fine and would trivially sidestep the coordination problem, because it is not decentralized. It could never be deployed as-is on the actual warehouse floor, where no robot has real-time access to the other thirty-nine robots' sensor feeds. VDN, QMIX, and MADDPG exist precisely to capture the benefit of that centralized view during training while still producing policies that are honestly decentralized at the end — a strictly harder target than "shared reward" alone implies.

Active Recall

Attempt these before reading the answers.

1. Write down the tuple that defines a general-sum Markov game, and state precisely what breaks when you try to reuse the standard single-agent Q-learning convergence proof in this setting.
2. A different match-up produces the payoff matrix (batsman's expected runs): Yorker/PrepYorker = 1, Yorker/PrepBouncer = -2, Bouncer/PrepYorker = -4, Bouncer/PrepBouncer = 3. Find the new equilibrium probability p that the bowler bowls a yorker.
3. What specific problem does Value Decomposition Networks (VDN) solve for cooperative MARL, and what assumption limits when its decentralized policy is actually optimal?
4. Give the minimax-Q Bellman backup for V(s) in a two-player zero-sum Markov game, and explain in one sentence why it is a linear program rather than a simple max like single-agent Q-learning.
5. Why does AlphaStar's league-based self-play train against a pool of past agent versions instead of only ever playing the current-best version against itself?
6. A team of delivery drones shares one team reward, and every drone streams its full internal Q-value estimates to every other drone in real time before each of them decides its next move. Is this still meaningfully multi-agent RL? Answer using the Dec-POMDP framing.

Answers.

1. The tuple is (N, S, {A_i}, P, {R_i}, gamma), with the joint action a = (a_1, ..., a_n) driving both P(s'|s,a) and every R_i(s,a,s'). Watkins and Dayan's convergence proof for Q-learning requires the environment to be a stationary MDP — a transition and reward function that does not change while the agent learns. In a Markov game, agent i's effective environment includes every other agent's policy, and since those policies are being updated by their own learning processes during training, the dynamics agent i experiences keep shifting underneath it. The stationarity assumption the proof depends on is violated, so nothing guarantees convergence, and in adversarial settings the learners can cycle indefinitely instead of settling.

2. Let A = [[1, -2], [-4, 3]]. Using a0 = A[0,0] - A[1,0] = 1 - (-4) = 5, a1 = A[0,1] - A[1,1] = -2 - 3 = -5, b0 = A[1,0] = -4, b1 = A[1,1] = 3: p = (b1 - b0) / (a0 - a1) = (3 - (-4)) / (5 - (-5)) = 7/10 = 0.7. The bowler's equilibrium mix is 70% yorker, 30% bouncer.

3. VDN solves the multi-agent credit-assignment problem under a single shared team reward: each agent learns its own per-agent utility Q_i(s, o_i, a_i) while training end-to-end against one team TD-error, by constraining the joint value to be the plain sum Q_tot = sum of Q_i. Because the sum is additive, the joint argmax over all agents' actions equals each agent independently taking the argmax of its own Q_i — the Individual-Global-Max property — which is exactly what lets each agent act from Q_i alone at deployment. The limiting assumption is that additivity: if the true team reward has a genuine synergy that exists only when specific agents jointly pick specific actions in a way that is not a sum of independent per-agent contributions, no assignment of Q_1(a_1) + Q_2(a_2) can represent that interaction term, and independent optimization of each additive share will not discover it.

4. V(s) = max over the agent's mixed strategy pi(s) in the simplex over A, of [ min over the opponent's action o in O, of sum_a pi(a) * Q(s,a,o) ]. It is a linear program rather than a simple max_a Q(s,a) because the agent is choosing a full probability distribution over its own actions, not a single action, specifically to guard against a worst-case opponent who gets to pick the best response to that distribution — exactly the maximin computation done by hand in the bowler-batsman example, repeated at every state instead of the single implicit state of a one-shot matrix game.

5. Playing only the current-best version against itself risks a specific failure mode: the policy can drift into a narrow strategy that beats its immediate mirror image while remaining secretly vulnerable to a different strategy it has not faced in a while — one that a slightly older version of itself might still play. Keeping a diverse pool of past versions, plus dedicated exploiter agents whose sole objective is to find and punish exactly this kind of narrow overfitting, forces the current policy to stay robust against a wide range of strategies rather than one constantly co-adapting mirror of itself, closer to actually approximating a Nash equilibrium against all opponents rather than the single most recently trained one.

6. No. The reward being shared never made this a Dec-POMDP if every agent also has real-time access to every other agent's full internal state before acting — that setup is a fully centralized decision-maker wearing several drones as actuators, equivalent to one large single-agent MDP whose action space is the Cartesian product of all the drones' individual action spaces. The Dec-POMDP framing turns on execution-time information, not on the reward: it requires each agent to select its action from its own local observation history alone. Letting every agent see every other agent's full state before acting collapses the decentralization constraint that made the problem hard in the first place, and the system is back to an ordinary — if large — single-agent MDP solvable with standard single-agent methods.

Think About It

Think about this: How would you explain multi-agent rl: cooperative and competitive to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind multi-agent rl: cooperative and competitive, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.