Sequential Problems

Chapter 1: Markov Games

A Markov game (Shapley, 1953) for n agents is a tuple (I, S, A₁, …, A_n, T, R₁, …, R_n, γ):

At each step: agents observe state s, simultaneously choose actions a_i ~ π_i(s), world transitions to s' ~ T(·|s,a), each agent receives reward R_i(s,a,s'). Repeat. Each agent seeks to maximize their own expected discounted sum ∑_t γ^t R_i,t.

Chapter 2: Response Models (Sequential)

In sequential settings, a response model is no longer just a distribution over actions — it's a model of the opponent's policy π_j : S → Δ(A_j). If I know your policy, I can solve my own MDP optimally.

The simplest model: assume opponents play a fixed stationary policy (same distribution over actions at each state, regardless of history). With this assumption, the Markov game from agent i's perspective reduces to an MDP with modified transition:

This averaged transition treats other agents as part of the stochastic environment. Agent i can then run any standard RL algorithm against this effective MDP.

Chapter 3: Nash Equilibrium for Markov Games

A joint policy π* = (π₁*, …, π_n*) is a Nash equilibrium for a Markov game if, at every state s, no agent can improve their value by unilaterally changing their policy, given that all other agents play π_−i*:

The Nash Q-function for agent i is the expected discounted reward from taking action a_i in state s, given the joint Nash policy thereafter:

And the Nash value is: V_i^Nash(s) = NashVal_i(Q₁^Nash(s,·), …, Q_n^Nash(s,·)) — the value agent i gets in the Nash equilibrium of the stage game at s.

Chapter 4: Nash Q-Learning

Minimax/Nash value iteration requires knowing T and R. In practice, we often don't. Nash Q-learning (Hu & Wellman, 2003) extends Q-learning to Markov games by replacing the max operator with a Nash equilibrium solver.

Each agent i maintains a Q-table Q_i(s, a) indexed by state and joint action. After experiencing a transition (s, a, r_i, s'), agent i updates:

where NashVal_i(s') is computed by solving the Nash equilibrium of the stage game at s' with payoff matrices Q_i(s', ·) for each agent i. The Nash solution gives both the equilibrium strategy π*(s') and the equilibrium values.

python
import numpy as np

class NashQLearner:
    def __init__(self, n_agents, n_states, n_actions, alpha=0.1, gamma=0.95):
        self.n = n_agents; self.alpha = alpha; self.gamma = gamma
        # Q[i][s, a1, a2, ...] — joint action Q-table for agent i
        shape = [n_states] + [n_actions]*n_agents
        self.Q = [np.zeros(shape) for _ in range(n_agents)]

    def update(self, s, joint_a, rewards, sp):
        nash_vals = self.nash_values(sp)  # solve stage game at sp
        for i in range(self.n):
            old = self.Q[i][s][tuple(joint_a)]
            target = rewards[i] + self.gamma * nash_vals[i]
            self.Q[i][s][tuple(joint_a)] = (1-self.alpha)*old + self.alpha*target

    def nash_values(self, s):
        # For 2-agent zero-sum: minimax LP. For general-sum: Nash solver.
        # Here: simplified for 2-agent 2-action zero-sum case
        U1 = self.Q[0][s]  # 2x2 payoff matrix for agent 1
        U2 = self.Q[1][s]
        pi1, pi2 = solve_nash_2x2(U1, U2)
        v1 = (pi1 @ U1 @ pi2)
        v2 = (pi1 @ U2 @ pi2)
        return [v1, v2]

Chapter 5: Fictitious Play for Markov Games

Fictitious play for Markov games extends the normal form algorithm from Ch 24 to sequential settings. Each agent maintains empirical counts of the opponents' actions at each state, best-responds to the historical frequency, and updates its own Q-function accordingly.

The state-indexed version: agent i maintains counts C_j(s, a_j) for each opponent j — how many times j played a_j at state s. The empirical frequency is π_j^emp(a_j|s) = C_j(s,a_j) / ∑_a C_j(s,a). Agent i best-responds to this empirical policy by solving an MDP with modified transitions.

Chapter 6: Gradient Ascent for Markov Games

Gradient ascent from Ch 24 extends directly to Markov games. Each agent maintains a parametric policy π_i(a|s; θ_i) and updates the parameters by ascending the gradient of their expected value:

For tabular policies (π_i(a|s) directly as parameters), the gradient at each state reduces to the policy gradient theorem: the gradient is proportional to the advantage A_i(s, a_i) = Q_i(s, a_i, π_−i) − V_i(s). This is the same as REINFORCE from Ch 11, but with multi-agent Q-values.

python
import numpy as np

def multiagent_gradient_ascent(game, pi_init, alpha=0.01, T=1000):
    """Simultaneous gradient ascent for tabular Markov game.
    game: MarkovGame object with Q-evaluation method.
    pi_init: list of (nS x nA) strategy matrices."""
    policies = [p.copy() for p in pi_init]
    history = []

    for t in range(T):
        # Evaluate all agents' Q-functions under current joint policy
        Q_vals = game.evaluate(policies)  # list of (nS x nA_i) arrays

        # Compute advantage: A_i(s, a_i) = Q_i(s, a_i) - V_i(s)
        for i in range(game.n_agents):
            V_i = (policies[i] * Q_vals[i]).sum(axis=1, keepdims=True)
            A_i = Q_vals[i] - V_i  # advantage: (nS x nA_i)

            # Gradient ascent on log-policy parameters
            policies[i] = policies[i] + alpha * A_i
            policies[i] = np.maximum(policies[i], 1e-10)
            policies[i] /= policies[i].sum(axis=1, keepdims=True)  # renorm

        history.append([p.copy() for p in policies])
    return history

Chapter 7: SHOWCASE — Multi-Agent Grid Game

A 4×4 grid world. Agent 1 (teal) starts top-left, Agent 2 (orange) starts top-right. There is one coin (yellow star) in the grid. The agent who reaches it first gets +10; the other gets 0. Colliding costs both −2.

Chapter 8: Convergence Analysis

None of the three algorithms (Nash Q-learning, fictitious play, gradient ascent) have universal convergence guarantees for general Markov games. Understanding when and why they converge — and when they don't — is crucial for applying them.

Chapter 9: Connections & Beyond

Markov games are the right model when agents can observe the full state. In practice, this assumption often fails: robots don't have omniscient sensors, financial agents don't see each other's order books, teammates can't observe each other's locations. Chapter 26 extends to partial observability.

"Reinforcement learning in multi-agent environments is fundamentally a game. The environment is non-stationary not because the world changes, but because other agents learn and adapt."
— Paraphrase, Shoham, Powers & Grenager, "If multi-agent learning is the answer, what is the question?" (2007)