Multi-Agent RL: Learning in Competitive & Cooperative Environments

At 9 PM on an IPL final night in Bengaluru, a Swiggy delivery rider and a Zomato delivery rider are both deciding whether to reposition toward Koramangala, where a cluster of restaurants is about to get slammed with orders. Neither rider knows what the other will do. If both converge on Koramangala, they split a fixed pool of nearby orders and each gets a modest cut. If one goes and the other stays put, the one who moved captures a disproportionate share of that evening's demand. This is not a single-agent routing problem — the "environment" each rider's app is optimizing against includes another intelligent, learning decision-maker whose choices directly change the reward the first one receives. That is the entire subject of this chapter: what happens to reinforcement learning once the environment contains more than one learner.

Every RL chapter before this one has quietly assumed a single agent acting inside a Markov Decision Process: a tuple (S, A, P, R, γ) where the transition function P(s′ | s, a) and reward function R(s, a) depend only on the agent's own action. The moment a second decision-maker enters the picture whose actions also affect the state and the reward, that assumption breaks, and with it break the convergence guarantees that make Q-learning and its relatives work. Multi-agent reinforcement learning (MARL) is the study of what replaces those guarantees.

From MDP to Stochastic Game

The correct formalism for N simultaneously-acting, simultaneously-learning agents is a stochastic game (also called a Markov game), a direct generalization of the MDP: (N, S, A₁,…,A_N, P, R₁,…,R_N, γ). At each timestep, every agent i observes state s (or, more realistically, a local observation oᵢ derived from s) and independently chooses an action aᵢ ∈ Aᵢ. The environment consumes the joint action a = (a₁, …, a_N), transitions according to P(s′ | s, a), and hands each agent its own reward rᵢ = Rᵢ(s, a, s′). When N = 1 this collapses exactly to the ordinary MDP you already know. The two new objects are the extra agents and the fact that each one can have its own, possibly conflicting, reward function.

That last clause is what defines the three regimes named in this chapter's title:

• Fully cooperative: R₁ = R₂ = … = R_N. Every agent is optimizing the same team scalar. Example: every rider on the Swiggy platform sharing a team objective of "total on-time deliveries across the locality this hour."
• Fully competitive (zero-sum): Σᵢ Rᵢ = 0 at every timestep. One agent's gain is exactly another's loss. Example: the Swiggy rider and Zomato rider splitting a fixed pool of Koramangala orders — what one platform captures, the other forfeits.
• Mixed / general-sum: neither constraint holds. Example: two riders on the same platform, both wanting the locality to perform well (cooperative pull, since it feeds a shared incentive pool) but also each chasing an individual "top rider of the week" bonus (competitive pull). Most real multi-agent systems — including this one — are general-sum.

Why independent Q-learning quietly stops working

The tempting shortcut is to give each agent its own Q-table and run ordinary Q-learning independently, treating every other agent as just more environment. This is called Independent Q-Learning (IQL), and it is a completely reasonable first thing to try — CBSE-level Q-learning generalizes to it with zero code changes. It also has no convergence guarantee, and here is precisely why.

Q-learning's convergence proof (the one that guarantees your Q-values converge to Q* under the usual step-size and exploration conditions) requires the environment to be a stationary MDP: P(s′ | s, a) and R(s, a) must not change while you are learning. In IQL, agent 1's effective transition and reward functions are P(s′ | s, a₁, π₂(s)) and R₁(s, a₁, π₂(s)) — they depend on agent 2's policy π₂. But agent 2 is also learning, so π₂ is changing every episode. From agent 1's point of view, the ground is moving under its own value estimates while it tries to estimate them. This is called non-stationarity, and it is the single defining difficulty of MARL that has no counterpart in single-agent RL. Two independently-converging Q-learners can chase each other's changing policies indefinitely, cycling rather than settling — this is a real, observed failure mode in zero-sum matrix games with best-response-style learners, not a hypothetical concern.

Worked example 1 — solving a zero-sum "Fare Race" and why pure strategies fail

Take the IPL-night repositioning decision and turn it into a payoff matrix. Each rider chooses K (reposition to Koramangala) or S (stay in current zone). Because the two platforms are drawing from roughly the same fixed order pool that evening, treat the payoff to Agent 1 (Zomato) as the negative of the payoff to Agent 2 (Swiggy) — a zero-sum game. Agent 1's payoff, in extra orders captured over baseline:

                 Agent 2: K      Agent 2: S
Agent 1: K          2               6
Agent 1: S          4              -3

A student's first instinct is to look for the one best action — that is exactly the misconception to correct here. In a zero-sum game there is generally no deterministic action that is safe against a rational opponent, because your opponent will simply best-respond to whatever fixed action you commit to. Check whether this game has a pure-strategy equilibrium (a "saddle point") using the maximin/minimax test: Agent 1's maximin is the best of the worst-case rows — row K guarantees at least min(2, 6) = 2, row S guarantees at least min(4, −3) = −3, so Agent 1's maximin value is 2. Agent 2 (trying to minimize Agent 1's payoff) has a minimax of the best of the worst-case columns — column K exposes at most max(2, 4) = 4, column S exposes at most max(6, −3) = 6, so Agent 2's minimax value is 4. Since maximin (2) ≠ minimax (4), there is no saddle point: whatever pure action Agent 1 commits to, Agent 2 has a profitable deterministic counter, and vice versa. A stable solution can only exist if both agents randomize.

This is solved with the indifference principle: at a mixed-strategy Nash equilibrium, each agent's mixing probability must make the other agent exactly indifferent between their own pure actions (otherwise that agent would deviate to the strictly better pure action). Let Agent 1 play K with probability p. For Agent 2 to be indifferent between K and S:

E[payoff | Agent 2 = K] = 2p + 4(1-p) = 4 - 2p
E[payoff | Agent 2 = S] = 6p - 3(1-p) = -3 + 9p

Set equal:  4 - 2p = -3 + 9p  →  7 = 11p  →  p = 7/11 ≈ 0.636

Symmetrically, let Agent 2 play K with probability q. For Agent 1 to be indifferent between K and S:

E[payoff | Agent 1 = K] = 2q + 6(1-q) = 6 - 4q
E[payoff | Agent 1 = S] = 4q - 3(1-q) = -3 + 7q

Set equal:  6 - 4q = -3 + 7q  →  9 = 11q  →  q = 9/11 ≈ 0.818

Substituting back gives the value of the game: 4 − 2(7/11) = 30/11 ≈ 2.727 (equivalently −3 + 9(7/11) gives the same number, and both q-side expressions also reduce to 30/11 — the four cross-checks agreeing is what confirms the arithmetic). Agent 1 is favored by this particular matrix and captures about 2.73 extra order-units per round at equilibrium, but only if it randomizes K roughly 64% of the time — never deterministically.

This little program checks the equilibrium numerically rather than trusting the hand algebra:

def agent1_expected_payoff(p, q, payoff):
    """p = P(agent1 plays K), q = P(agent2 plays K).
    payoff[a1][a2] is agent1's payoff for joint action (a1, a2),
    with actions ordered as [K, S]."""
    K, S = 0, 1
    return (p * q * payoff[K][K] + p * (1 - q) * payoff[K][S] +
            (1 - p) * q * payoff[S][K] + (1 - p) * (1 - q) * payoff[S][S])

payoff = [[2, 6], [4, -3]]
p, q = 7 / 11, 9 / 11
print(round(agent1_expected_payoff(p, q, payoff), 3))

Tracing it: p*q*2 = (7/11)(9/11)(2) = 126/121, p*(1-q)*6 = (7/11)(2/11)(6) = 84/121, (1-p)*q*4 = (4/11)(9/11)(4) = 144/121, (1-p)*(1-q)*(-3) = (4/11)(2/11)(−3) = −24/121. Summing: (126 + 84 + 144 − 24)/121 = 330/121 = 30/11. The function returns 2.727, matching the hand derivation exactly.

This algebra is not a side quest — it is the algorithm. Minimax-Q (Littman, 1994), the foundational zero-sum MARL algorithm, replaces the single-agent Q-learning update target max_a Q(s′,a) with a minimax value computed the same way: V(s′) = max_{π∈Δ(A)} min_{o∈O} Σ_a π(a) Q(s′,a,o) — literally "find the mixed strategy π that maximizes your guaranteed payoff against a worst-case opponent action o." For a 2×2 game that reduces exactly to the indifference-principle computation above; for larger action sets it is solved with linear programming. The Q-update itself keeps the familiar shape, Q(s,a,o) ← (1−α)Q(s,a,o) + α[r + γV(s′)], but the bootstrap target now comes from a game solved at every state, not a simple max.

Worked example 2 — cooperative coverage and the limits of value decomposition

Now switch regimes: two riders on the same platform, sharing one team reward, must silently coordinate on which of two zones — North or South — each patrols, with no communication channel. The true joint-reward table (both zones covered is best; both riders in the same zone wastes capacity):

                North         South
North         4 (redundant)   10 (full coverage)
South        10 (full coverage)  4 (redundant)

This is a coordination game: (North, South) and (South, North) are both optimal, but a naive independent learner has no way to know which one the other rider will settle into, and — thanks to the same non-stationarity from before — the two can oscillate between miscoordinated joint actions while each is still adapting to the other's shifting policy.

The standard fix for the cooperative case is CTDE — Centralized Training, Decentralized Execution: during training (in simulation, with full information available), a central process can see everything and shape each agent's policy; at deployment, each rider's app only ever sees its own local state, exactly as it must in the real world. Value Decomposition Networks (VDN), one of the earliest CTDE cooperative algorithms, approximates the joint action-value as a simple sum of per-agent utilities: Q_tot(s, a₁, a₂) ≈ Q₁(a₁) + Q₂(a₂). Each agent can then act on its own Qᵢ alone at execution time, no communication needed, while training pushes Q_tot toward the true team return.

Can this additive form even represent the coverage table above? Set up the four constraints directly from the table:

q1(N) + q2(S) = 10
q1(S) + q2(N) = 10
q1(N) + q2(N) = 4
q1(S) + q2(S) = 4

From the third equation, q1(N) = 4 − q2(N); substituting into the first gives 4 − q2(N) = 10 − q2(S), i.e. q2(S) − q2(N) = 6. From the fourth equation, q1(S) = 4 − q2(S); substituting into the second gives 4 − q2(S) = 10 − q2(N), i.e. q2(N) − q2(S) = 6. These two derived equations require q2(S) − q2(N) to equal both 6 and −6 simultaneously — a contradiction, so no additive decomposition exists that reproduces this reward table exactly. (Solving the four equations as a linear system numerically confirms this: the coefficient matrix is singular, rank 3 against 4 unknowns, and the right-hand side is inconsistent with the null space — there is no solution, not even an approximate one that hits all four values.) The underlying reason is structural: VDN's sum can only represent reward surfaces that are monotonically separable, and this reward is a genuine XOR-style anti-coordination pattern — it rewards agents for choosing different actions, which no sum of independent per-agent terms can encode. QMIX improves on this by replacing the plain sum with a learned, non-linear mixing network — but constrained so that ∂Q_tot/∂Qᵢ ≥ 0 for every agent (monotonicity), which is what preserves the ability to still act by greedily maximizing each local Qᵢ at execution time. That monotonicity constraint is exactly what still trips on a purely anti-coordinating structure like this one; representing it exactly generally needs either an unconstrained centralized critic used only for training gradients (as in MADDPG) or an explicit communication channel between agents at execution time — the two escapes from the "decentralized execution" restriction.

The training-time / execution-time split

The diagram below is the mechanism that both worked examples ultimately point to for cooperative MARL: policies that only ever see local information at runtime, trained against a critic that is allowed to see everything but is thrown away once training ends.

Active recall

Attempt these before reading the answers.

1. In the Fare Race payoff matrix [[2, 6], [4, −3]], why is there no deterministic action Agent 1 can safely commit to?
2. Suppose the Fare Race matrix changes so that payoff[K][K] becomes 0 instead of 2 (matrix [[0, 6], [4, −3]]). Recompute Agent 1's equilibrium probability of playing K.
3. Why does Independent Q-Learning lack the convergence guarantee that single-agent Q-learning has, even though both use the identical update rule?
4. In the North/South coverage game, show why no additive decomposition Q_tot(a₁,a₂) = q1(a₁) + q2(a₂) can exactly reproduce the true reward table.
5. Classify each as cooperative, zero-sum/competitive, or general-sum, and justify in one line: (a) all riders on one platform sharing a locality efficiency bonus; (b) a Swiggy rider and a Zomato rider splitting a fixed evening order pool; (c) two riders on the same platform who share a team bonus but also compete for an individual "rider of the week" award.
6. Why is the centralized critic in CTDE discarded at deployment instead of being shipped as part of the live app?

Answers

1. Because the game has no pure-strategy saddle point: Agent 1's maximin (best of the worst-case rows) is min(2,6)=2 vs min(4,−3)=−3, so maximin = 2; Agent 2's minimax (best of the worst-case columns) is max(2,4)=4 vs max(6,−3)=6, so minimax = 4. Since 2 ≠ 4, whatever pure action Agent 1 fixes, Agent 2 has a strictly better deterministic response, so only a randomized (mixed) strategy can be stable.
2. Using the indifference principle on the new matrix: E[Agent2=K] = 0p + 4(1−p) = 4 − 4p; E[Agent2=S] = 6p − 3(1−p) = −3 + 9p. Setting equal: 4 − 4p = −3 + 9p → 7 = 13p → p = 7/13 ≈ 0.538.
3. Q-learning's convergence proof requires a stationary MDP — fixed P(s′|s,a) and R(s,a) throughout learning. In IQL, agent 1's effective transition and reward depend on agent 2's policy, which is also changing during training. The environment agent 1 is trying to learn is non-stationary from its own point of view, so the stationarity precondition of the proof is violated and no fixed point is guaranteed — the two learners can chase each other's shifting policies indefinitely.
4. The table requires q1(N)+q2(S)=10, q1(S)+q2(N)=10, q1(N)+q2(N)=4, q1(S)+q2(S)=4. Subtracting the third from the first gives q2(S) − q2(N) = 6; subtracting the fourth from the second gives q2(N) − q2(S) = 6. Both cannot hold simultaneously (that would require 6 = −6), so the system is inconsistent and no additive q1, q2 exist that reproduce the table exactly — the reward is anti-coordinating (XOR-shaped) and not additively separable.
5. (a) Cooperative — every rider shares exactly the same locality bonus, R₁=R₂=…. (b) Zero-sum/competitive — the order pool is fixed, so one platform's captured order is the other's lost order, Σ Rᵢ = 0. (c) General-sum — the team bonus term is shared (cooperative pull) but the individual weekly-award term is exclusive (competitive pull); neither the equal-reward nor the zero-sum constraint holds cleanly.
6. Because at deployment each agent only has access to its own local observation in real time — a rider's app cannot see every other rider's live position and the platform's full order queue with zero latency, and shipping that would require infeasible real-time communication bandwidth. The critic's job (using the global state and joint action) is only to produce a better training signal for shaping each agent's local policy; once that shaping is done, the policy itself needs only oᵢ to act, so the critic is dropped.

Think About It

Think about this: How would you explain multi-agent rl: learning in competitive & cooperative environments 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.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where multi-agent rl: learning in competitive & cooperative environments is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting multi-agent rl: learning in competitive & cooperative environments to at least 3 other topics you have studied.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind multi-agent rl: learning in competitive & cooperative environments, 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.