Markov Games

One MDP with many deciders. Next state and each reward depend on the full joint action, so agents must settle on mutual best responses.

Two agents pick a joint action that moves the shared state, and Q values 4.00, 1.80, 1.80, 2.00 leave two pure Nash points

Why Does This Exist?

A single agent MDP assumes the world sits still while you learn. Transition $P(s^\prime \mid s, a)$ and reward $R(s, a)$ depend only on your action. That lets greedy value iteration work.

Teams break the assumption. With $N$ agents the next state depends on the joint vector $\mathbf{a} = (a_1, \dots, a_N)$ . From one agent view the world shifts as peers update, so old replay no longer matches current dynamics. Greedy max over your own actions is not defined, because payoff depends on simultaneous peer picks.

Markov games fix the math. Shapley named them stochastic games in 1953, Littman brought them to RL in 1994. They keep states, add joint actions, and replace solo max with equilibrium. This page covers the model and the equilibrium idea. Team training methods live in multi-agent RL. Environment types live in cooperative versus competitive environments. Solo baselines that ignore coupling live in independent Q-learning.

The one idea you need first

An MDP has states $s$ , actions $a$ , transitions $P(s^\prime \mid s, a)$ , rewards $R$ , discount $\gamma$ . Value $V(s)$ is expected discounted return from $s$ . A Markov game keeps all of that and swaps solo $a$ for joint $\mathbf{a}$ , with one reward head per agent.

Think of It Like This

Four cars at a crossing with no lights

You practice alone on a closed track. Turn right 30 degrees at 40 speed and you land in the right lane every time. The track never reacts.

Now put four cars at a crossing with no lights. Your next position depends on all four pedals at once. You go while cross traffic goes and you meet in the middle. You both stop and you wait forever. You go while they wait and all pass.

You cannot solve it by treating cars as rocks. You need a shared rule where no driver gains by swerving alone. That stalemate is the equilibrium the math below defines.

Where it stops: drivers use eyes and horns. Game agents use policies $\pi_i(a_i \mid s)$ and matrix solvers, not social cues.

How It Actually Works

A Markov game lists agents $N$ , shared states $\mathcal{S}$ , one action set per agent $\mathcal{A}_i$ , joint set $\mathcal{A} = \mathcal{A}_1 \times \dots \times \mathcal{A}_N$ , joint transitions $P(s^\prime \mid s, \mathbf{a})$ , one reward function per agent $\mathcal{R}_i(s, \mathbf{a})$ , and discount $\gamma$ in $[0, 1)$ .

Each agent holds policy $\pi_i(a_i \mid s)$ . Joint policy factorizes as product of locals under decentralized choice:

\boldsymbol{\pi}(\mathbf{a} \mid s) = \prod_{i=1}^N \pi_i(a_i \mid s)

Value for agent $i$ is expected discounted sum under the joint policy:

V_i^{\boldsymbol{\pi}}(s) = \mathbb{E}_{\boldsymbol{\pi}}\left[\sum_{t \ge 0} \gamma^t \mathcal{R}_i(s_t, \mathbf{a}_t) \mid s_0 = s\right]

Joint action value follows the team Bellman form:

Q_i^{\boldsymbol{\pi}}(s, \mathbf{a}) = \mathcal{R}_i(s, \mathbf{a}) + \gamma \sum_{s^\prime} P(s^\prime \mid s, \mathbf{a}) V_i^{\boldsymbol{\pi}}(s^\prime)

In words: immediate team reward plus discounted next state value, where next state depends on all actions at once.

Nash replaces max

Joint policy $\boldsymbol{\pi}^\ast$ is Nash when no agent gains by leaving alone. For every agent $i$ , state $s$ , and alternative $\pi_i$ :

V_i^{(\pi_i^\ast, \boldsymbol{\pi}_{-i}^\ast)}(s) \ge V_i^{(\pi_i, \boldsymbol{\pi}_{-i}^\ast)}(s)

Zero sum pairs have one value solvable by linear programming. Shared reward teams reduce to joint maximization. General sum games can hold many equilibria, and finding one is hard in general, which is why large systems use sampling and centralized critics instead of exact solves.

Worked example

Two agents share start $s_0$ and terminal goal $g$ with $V(g) = 0.00$ . Agent 1 picks $U$ or $D$ . Agent 2 picks $L$ or $R$ . Discount $\gamma = 0.90$ . Current guess $V(s_0) = 2.00$ .

Payoffs and moves:

Pair $(U, L)$ goes to $g$ with reward $4.00$ each.
Pair $(U, R)$ stays at $s_0$ with reward $0.00$ each.
Pair $(D, L)$ stays at $s_0$ with reward $0.00$ each.
Pair $(D, R)$ goes to $g$ with reward $2.00$ each.

Joint values for agent 1 by Bellman backup:

Q(U, L) = 4.00 + 0.90 \times 0.00 = 4.00

Q(U, R) = 0.00 + 0.90 \times 2.00 = 1.80

Q(D, L) = 0.00 + 0.90 \times 2.00 = 1.80

Q(D, R) = 2.00 + 0.90 \times 0.00 = 2.00

Agent 2 shares the same numbers here, so the state holds a symmetric 2 by 2 game:

$(U, L)$ pays $(4.00, 4.00)$ .
$(U, R)$ pays $(1.80, 1.80)$ .
$(D, L)$ pays $(1.80, 1.80)$ .
$(D, R)$ pays $(2.00, 2.00)$ .

Pure best responses: against $L$ , $U$ beats $D$ because $4.00$ tops $1.80$ . Against $U$ , $L$ beats $R$ for the same reason, so $(U, L)$ is Nash. Against $R$ , $D$ beats $U$ because $2.00$ tops $1.80$ . Against $D$ , $R$ beats $L$ , so $(D, R)$ is also Nash. One pays $4.00$ , the other pays $2.00$ .

Mixed mixing makes the peer indifferent. Let agent 1 play $U$ with chance $p$ . Agent 2 earns $1.80 + 2.20 p$ from $L$ and $2.00 - 0.20 p$ from $R$ . Equalize:

1.80 + 2.20 p = 2.00 - 0.20 p

2.40 \cdot p = 0.20

p = 1 / 12 \approx 0.0833

Symmetry gives $q \approx 0.0833$ for $L$ . Mixed value is $1.80 + 2.20 / 12 \approx 1.9833$ , below both pure points. Coordination on $(U, L)$ lifts state value from $2.00$ to $4.00$ . That is what the diagram draws.

Code

This snippet rebuilds the four joint values and the mixing chance with plain Python.

1def q_value(reward: float, gamma: float, v_next: float) -> float:2    return reward + gamma * v_next3
4
5qs = {6    "UL": q_value(4.0, 0.90, 0.0),7    "UR": q_value(0.0, 0.90, 2.0),8    "DL": q_value(0.0, 0.90, 2.0),9    "DR": q_value(2.0, 0.90, 0.0),10}11print([round(qs[k], 2) for k in ["UL", "UR", "DL", "DR"]])  # -> [4.0, 1.8, 1.8, 2.0]12
13p = 0.20 / 2.4014print(round(p, 4))  # -> 0.083315print(round(1.80 + 2.20 * p, 4))  # -> 1.9833

Outputs match the hand math: four joint values $[4.00, 1.80, 1.80, 2.00]$ , mixing chance $0.0833$ , mixed value $1.9833$ .

Watch Out For

Running solo Q-learning on a team game

Treating peers as fixed noise and learning $Q_i(s, a_i)$ looks simple and oscillates. Peer policies shift the effective transition $P(s^\prime \mid s, a_i)$ every epoch, so old replay misleads the update. Policies chase each other and never settle.

Model the joint action during training. Use a central critic on $(s, a_1, \dots, a_N)$ , or an explicit peer model, or an equilibrium backup for tiny matrix games. Keep solo Q only for truly fixed peers.

Assuming one equilibrium

General sum games often hold several Nash points with different payoffs, here $4.00$ versus $2.00$ versus $1.9833$ mixed. An algorithm can lock onto the safe low point while a better joint point exists.

Check which equilibrium your update found. Seed joint exploration toward the high payoff pair, log which pair the team actually plays, and do not report mixed value as if it were the coordinated value.

The Quick Version

A Markov game swaps solo action $a$ for joint vector $\mathbf{a}$ in transitions and rewards.
Solo max is invalid because payoff depends on simultaneous peer picks.
Nash means no agent gains by deviating alone while peers stay fixed.
In the worked 2 by 2 game, joint values are $4.00$ , $1.80$ , $1.80$ , $2.00$ with pure Nash at $(U, L)$ and $(D, R)$ .
Mixing chance $1/12 \approx 0.0833$ gives mixed value $1.9833$ , below coordinated play at $4.00$ .