How to cite

@misc{mit-multiagent-learning-lecture-S6,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Supplementary reading S6: Markov (aka stochastic) games},
  booktitle = {MIT Topics in Multiagent Learning Lecture Notes},
  note = {MIT 6.7980, Fall 2026},
  year = {2026},
  url = {https://www.mit.edu/~6.7980/stochastic_games.html}
}

Supplementary reading S6

Markov (aka stochastic) games

Instructor

Prof. Constantinos Daskalakis (costis@mit.edu)

Edition

Fall 2026

In this lecture, we turn our attention to Markov games, also known as stochastic games. These are an expressive family of games which has become especially popular recently as a mathematical model underlying multi-agent reinforcement learning. Markov games capture strategic interactions that take place over a number of rounds or perhaps an infinite number of rounds, in some environment whose state is influenced by the actions taken by players, and which in turn influences the players’ rewards.

S6.1 The model

The model of Markov games was introduced in the seminal work of Shapley [Sha53[Sha53] Shapley, L. S. (1953). Stochastic games. Proceedings of the National Academy of Sciences, 39(10), 1095–1100.] as a generalization of Markov decision process from the single-agent to the multi-agent setting. In this model, the agents interact with each other and with the environment, and the environment is affected by the joint actions of the agents. In this lecture, we will draw a distinction between infinite-horizon games, and finite-horizon games (also known as episodic). We start with the former. While the definition is a mouthful, the model is very natural in its examination.

Definition S6.1 (Infinite-horizon stochastic game) .

An $$m$$ -player, infinite-horizon, finite state and action stochastic game, also called Markov game, is a tuple $G = (S , A , \mathbb{P} , r , \gamma , \boldsymbol{\mu })$ where

$$S$$ is a finite set of states that the environment can be in;
$A = A_{1} \times A_{2} \times \dots \times A_{m}$ is the set of action profiles, where $A_{i}$ are the actions available to player $$i$$ ;
$\mathbb{P} (s' \hspace{0.22em} | \hspace{0.22em} s , a)$ , for $s , s' \in S$ and $a \in A$ are the transition probabilities of the environment; in particular, $\mathbb{P} (s' \hspace{0.22em} | \hspace{0.22em} s , a)$ is the probability that the state of the environment becomes $$s'$$ if action profile $a \in A$ is taken by the players in some state $$s$$ ;
$r = (r_{1} , \dots , r_{m})$ is a tuple of reward functions, where $r_{i} (s , a)$ specifies the immediate reward received by player $$i$$ when the action profile $a \in A$ is taken by the players in some state $$s$$ ;
$\gamma \in [0 , 1)$ is the discount factor; and
$\boldsymbol{\mu } \in \Delta ( S )$ is the initialization distribution, sampling the state $s^{( 0 )}$ of the environment at the beginning of the interaction.

Given an infinite state-action sequence $(s^{( t )} , a^{( t )})_{t = 0}^{∞}$ , each player derives a discounted utility of

\displaystyle u_{i} \left(\left(s^{\left( t \right)} , a^{\left( t \right)}\right)_{t}\right) \coloneqq \sum_{t \ge 0} \gamma^{t} ⋅ r_{i} \left(s^{\left( t \right)} , a^{\left( t \right)}\right) .

We will use the convention that $\gamma^{0} = 1$ , when $\gamma = 0$ .

As the name suggests, an infinite-horizon stochastic game is played over an infinite number of steps, and there is discounting of future rewards. The goal of each player is to maximize their discounted utility. If the interaction takes place over a finite number of steps, we have a finite-horizon stochastic game, as defined next.

Definition S6.2 (Finite-Horizon Stochastic Game) .

A finite-horizon stochastic game is defined in terms of the same primitives used to defined an infinite-horizon stochastic game, together with an additional parameter

H \in \mathbb{N}

, called the horizon, which indicates that the interaction takes place over

\(H\)

steps, indexed

t = 0 , \dots , H - 1

. Because of the finiteness of the number of steps, the discount factor can now take any value in

\([ 0 , 1 ]\)

, i.e. the value of

\gamma = 1

is acceptable since the discounted utility is a finite sum and therefore cannot diverge. If

\gamma = 1

, we say that there is no discounting of future rewards.

S6.2 Strategies and Nash Equilibrium

In general, when we think about strategies, a.k.a. policies, for players in a stochastic game, we may allow for the possibility that the actions taken at some state $$s$$ at some time $$t$$ may depend on the entire trajectory $( s^{( τ )} , a^{( τ )} )_{τ < t}$ so far. In other words, when left unqualified, the term policy allows for history-dependence and we think of it as a mapping

\displaystyle π_{i} : S \times \left(S \times A\right)^{∗} \to \Delta \left(A_{i}\right) ,

where the asterisk denotes a tuple of arbitrary length representing the history of play up to any point.

When further restrictions are imposed on how the policy can depend on the history, we arrive at two important distinctions.

Definition S6.3 (Markovian policy) .

A policy is history-independent, or Markovian, if it only depends on the current state and time. This means that given any two histories of the same length ending in the same current state, the action distribution is the same. In particular, the policy is a function

\displaystyle π_{i} : S \times \mathbb{N} \to \Delta \left(A_{i}\right) .

Definition S6.4 (Stationary and Markovian policy) .

A policy is stationary and Markovian if it only depends on the current state. In particular, the policy is just a function of the current state

\displaystyle π_{i} : S \to \Delta \left(A_{i}\right) .

Given a collection of policies $π_{1} , \dots , π_{m}$ for the players of a stochastic game, the expected utility of each player is naturally defined as follows:

\displaystyle u_{i} \left( π_{1} , \dots , π_{m} \right) = \mathop{\mathbb{E}}\limits_{\substack{s_{0} \sim \boldsymbol{\mu } ;\\ \forall t > 0 : s^{\left( t \right)} \sim \mathbb{P} \left(⋅ | \hspace{0.22em} s^{\left( t - 1 \right)} , a^{\left( t - 1 \right)}\right)\\ \forall t \ge 0 , i : \hspace{0.22em} a_{i}^{\left( t \right)} \sim π_{i} \left(s^{\left( t \right)} , \left( s^{\left( τ \right)} , a^{\left( τ \right)} \right)_{τ < t}\right)}} \left[\sum_{t \ge 0} \gamma^{t} r_{i} \left( s^{\left( t \right)} , a^{\left( t \right)} \right)\right] .

For the finite-horizon version, truncate the sum at $$t=H-1$$ and restrict the trajectory to those $$H$$ stages.

In particular, $u_{i} ( π_{1} , \dots , π_{m} )$ is the expected discounted utility of player $$i$$ under the random trajectory which starts at $s^{( 0 )} \sim \boldsymbol{\mu }$ and is sampled by having each player sampling an action from their policy at each state, and having the environment transition according to its dynamics. In terms of these utilities, Nash equilibrium is defined in the natural way as follows. Notice that this definition generalizes the concept of Nash equilibrium in normal-form games.

Definition S6.5 (Nash equilibrium) .

A collection of policies $π = ( π_{1} , \dots , π_{m} )$ is a Nash equilibrium of a stochastic game iff for all players $$i$$ , for all policies $π' : S \times (S \times A)^{∗} \to \Delta (A_{i})$ it holds that

\displaystyle u_{i} \left( π_{i} \hspace{0.22em} ; \hspace{0.22em} π_{- i} \right) \ge u_{i} \left( π_{i}' \hspace{0.22em} ; \hspace{0.22em} π_{- i} \right) .

If all strategies $π_{1} , \dots , π_{m}$ are Markovian, the Nash equilibrium is called Nash equilibrium in Markovian strategies. Similarly, if all strategies $π_{1} , \dots , π_{m}$ are stationary and Markovian, the Nash equilibrium is called Nash equilibrium in stationary and Markovian strategies.

S6.3 Nash Equilibrium Existence

S6.3.1 The finite-horizon case

If we are content with non-Markovian strategies, a finite-horizon stochastic game can just be “unrolled” and converted into a perfect-recall extensive-form game (Section L7.1), whose Nash equilibrium strategies can be converted to a Nash equilibrium of the stochastic game. In general, this Nash equilibrium will not be in Markovian strategies. However, finite-horizon stochastic games do have Nash equilibria in Markovian strategies, as can be seen by a backward induction argument.

Theorem S6.6 .

Every finite-horizon stochastic game with a finite number of states, actions, and players, has a Nash equilibrium in Markovian strategies. More formally, in the setting of Definition S6.2, there exists a collection of policies $π_{1} , \dots , π_{m}$ where $π_{i} : S \times \{0 , \dots , H - 1\} \to \Delta (A_{i})$ such that

\displaystyle u_{i} \left(π_{i} , π_{- i}\right) \ge u_{i} \left(π_{i}' , π_{- i}\right) \qquad \forall i , π_{i}' ,

where $π_{i}'$ is any, not necessarily Markovian, policy for player $$i$$ .

Proof Sketch.

The idea is to solve the game backwards, starting at the end of the horizon and proceeding backwards, down to the first step of the interaction, inductively picking Nash equilibrium strategies for hypothetical games that would start at all possible interaction steps $$t$$ and all possible states $$s$$ . To compute these Nash equilibrium strategies inductively, we need, for all $$t$$ and all $$s$$ , to find Nash equilibrium strategies for a game whose payoff, $U_{i , t , s} ( a )$ , for each player $$i$$ , is the immediate reward $r_{i} ( s , a )$ plus the continuation value expected for this player under the inductively computed strategies and the transitions of the environment.

Below is a Nash equilibrium computation algorithm, whose correctness establishes the existence of Nash equilibrium in Markov policies.

Initialization ( $$t = H$$ ):
1. $V_{i , H} ( s ) = 0$ , for all $$i , s$$ ; in particular, the expected continuation value for each player $$i$$ at each state $$s$$ at time $$t = H$$ is $$0$$ , as the game has ended at $$t = H$$ .
Inductive Step (from $$t = H - 1$$ down to $$t = 0$$ ):
1. Assume already computed expected continuation values $V_{i , t + 1} : S \to \mathbb{R}$ for each player $$i$$ .
2. For each state $$s$$ :
  1. define a game wherein player $$i$$ ‘s utility is
    $\displaystyle U_{i , t , s} \left( a \right) = r_{i} \left( s , a \right) + \gamma \mathop{\mathbb{E}}\limits_{s' \sim \mathbb{P} \left( ⋅ | s , a \right)} \left[ V_{i , t + 1} \left( s' \right) \right] ;$
  2. pick an arbitrary Nash equilibrium $π ( ⋅ | s , t ) \in \Delta ( A )$ of the normal-form game with the above utility functions;
  3. set $V_{i , t} ( s ) = \mathop{\mathbb{E}}\limits_{a \sim π ( ⋅ | s , t )} [ U_{i , t , s} ( a ) ] .$

To argue the correctness of the above algorithm, one proceeds as follows. Suppose that $π ( ⋅ | s , t ) = ( π_{1} ( ⋅ | s , t ) , \dots , π_{m} ( ⋅ | s , t ) )$ are the Nash equilibrium strategies picked in Step 2.2.2 of the algorithm for all $$s , t$$ . For each player $$i$$ , define a Markovian policy $π_{i} : S \times \{0 , \dots , H - 1\} \to \Delta (A_{i})$ as follows:

\displaystyle π_{i} \left( s , t \right) \left( ⋅ \right) \coloneqq π_{i} \left( ⋅ | s , t \right) .

We claim that the collection of policies $( π_{1} , \dots , π_{m} )$ is a Nash equilibrium of the game in Markovian policies. The Markovianity of the policies is clear from the definition of this policies in a backwards induction manner.

So all we need to prove is that $π_{i}$ is a best-response to $π_{- i}$ . This can be shown inductively. The base case is arguing that, for each $$s$$ , the distribution $π_{i} ( s , H - 1 )$ is optimal for player $$i$$ to use, if he finds himself at state $$s$$ at time $$H - 1$$ , given the policies of the other players. This follows immediately by the Nash equilibrium conditions satisfied by $$π ( \cdot | s , H - 1 )$$ . The inductive hypothesis is that policy

\displaystyle π_{i}^{\ge t + 1} \coloneqq \left( π_{i} \left( s , τ \right) \left( ⋅ \right) \right)_{s \in S , τ \ge t + 1} ,

is optimal for player $$i$$ to continue the game with against the policies of the other players if the player finds himself at some state $$s$$ at time $$t + 1$$ . The induction step is showing that under the induction hypothesis, $π_{i}^{\ge t}$ is optimal for continuing the game with against the policies of the other players if the player finds himself at some state $$s$$ at time $$t$$ . To show the inductive step we will use the definition of the game in Step 2.2.1 of the algorithm and the Nash equilibrium properties of the strategies picked in Step 2.2.2. We leave the complete details to the reader. □

Finally, we remark that in finite-horizon games, there typically do not exist Nash equilibria in stationary and Markovian policies, because the best response of a player to the policies of the other players, even if all other players use stationary and Markovian policies, typically depends on the number of interaction steps that remain. In infinite-horizon games, however, equilibria in stationary and Markovian policies do exist, as we show in the next section.

S6.3.2 The infinite-horizon case

Theorem S6.7 ([Tak64[Tak64] Takahashi, M. (1964). Equilibrium points of stochastic non-cooperative $$n$$ -person games. Journal of Science of the Hiroshima University, Series AI (Mathematics), 28(1), 95–99.][Fin64[Fin64] Fink, A. M. (1964). Equilibrium in a stochastic $$n$$ -person game. Journal of Science of the Hiroshima University, Series Ai (Mathematics), 28(1), 89–93.]) .

Every infinite-horizon stochastic game with a finite number of states, actions, and players, has a Nash equilibrium in stationary, Markovian strategies. In particular, in the setting of Definition S6.1, there exists a collection of policies $π_{1} , \dots , π_{m}$ where $π_{i} : S \to \Delta (A_{i})$ such that

\displaystyle u_{i} \left(π_{i} , π_{- i}\right) \ge u_{i} \left(π_{i}' , π_{- i}\right) \qquad \forall i , π_{i}' ,

where $π_{i}'$ is any, not necessarily stationary and Markovian, policy for player $$i$$ .

Proof.

Given a stationary Markov policy profile $π = (π_{1} , \dots , π_{m})$ and a player $i \in [ m ]$ , we introduce the following notation:

$v_{i}^{π} ( s )$ , for $s \in S$ , is the infinite discounted utility of player $$i$$ if the game started at state $$s$$ and all players used policies $π_{1} , \dots , π_{m}$ . In symbols,
$\displaystyle \forall s : v_{i}^{π} \left( s \right) = \underbrace{\sum_{a} r_{i} \left( s , a \right) π \left( a | s \right)}_{≕ r_{i}^{π} \left( s \right)} + \gamma \sum_{s'} v_{i}^{π} \left( s' \right) \underbrace{\sum_{a} π \left( a | s \right) \mathbb{P} \left( s' | s , a \right)}_{≕ \Gamma^{π} \left( s , s' \right)}$ (1)
Notice that 1 is a linear system of equations in the variables $( v_{i}^{π} ( s ) )_{s}$ , which we can rewrite more compactly as
$\displaystyle \left(I - \gamma \Gamma^{π}\right) \boldsymbol{v}_{i}^{π} = \boldsymbol{r}_{i}^{π} .$
We now argue that the matrix $I - \gamma \Gamma^{π}$ is invertible. To see this, note that the matrix $\Gamma^{π}$ is a row-stochastic matrix:
$\displaystyle \sum_{s'} \Gamma^{π} \left(s , s'\right) = \sum_{s'} \sum_{a} π \left(a | s\right) \mathbb{P} \left(s' | s , a\right) = \sum_{a} π \left(a | s\right) \left(\sum_{s'} \mathbb{P} \left(s' | s , a\right)\right) = \sum_{a} π \left(a | s\right) = 1 .$
Since $\gamma < 1$ by Definition S6.1, we have that $I - \gamma \Gamma^{π}$ is strictly diagonally dominant, which implies that $I - \gamma \Gamma^{π}$ cannot be singular. Therefore, the system of equations has a unique solution, which corresponds to
$\displaystyle \boldsymbol{v}_{i}^{π} = \left(I - \gamma \Gamma^{π}\right)^{- 1} \boldsymbol{r}_{i}^{π} .$
Furthermore, the value vectors $\boldsymbol{v}_{i}^{π}$ are continuous in the policies $$π$$ , because the inverse matrix of the non-singular matrix $I - \gamma \Gamma^{π}$ is continuous in the values of the entries, and these are continuous in $$π$$ .
$q_{i}^{π} (s , a_{i})$ , for $s \in S$ and $a_{i} \in A_{i}$ , is the infinite discounted utility of player $$i$$ if the game started at state $$s$$ , and players used policies $π_{1} , \dots , π_{m}$ , with the only exception that the very first action of player $$i$$ is set to $a_{i}$ . In symbols,
$\displaystyle q_{i}^{π} \left(s , a_{i}\right) = \sum_{a_{- i}} r_{i} \left(s , a\right) ⋅ π_{- i} \left(a_{- i} | s\right) + \gamma \sum_{s'} v_{i}^{π} \left( s' \right) \sum_{a_{- i}} π_{- i} \left(a_{- i} | s\right) ⋅ \mathbb{P} \left(s' | s , a\right) .$
Like before, the function $q_{i}^{π}$ is continuous in the policies $$π$$ , since everything on the right-hand side is continuous, including the $\boldsymbol{v}_{i}^{π}$ as discussed above. Furthermore,
$\displaystyle v_{i}^{π} \left( s \right) = \sum_{a_{i}} π_{i} \left(a_{i} | s\right) ⋅ q_{i}^{π} \left(s , a_{i}\right) .$ (2)

We now define a Nash-type function $\phi$ , analogous to the Nash improvement function for normal-form games (Definition L1.6), mapping policy profiles to improved policy profiles as follows:

\displaystyle \forall i , s , a_{i} : \qquad π_{i}' \left(a_{i} | s\right) ← \frac{π_{i} \left(a_{i} | s\right) + \left[q_{i}^{π} \left(s , a_{i}\right) - v_{i}^{π} \left( s \right)\right]^{+}}{1 + \sum_{a_{i}'} \left[q_{i}^{π} \left(s , a_{i}'\right) - v_{i}^{π} \left( s \right)\right]^{+}} .

(3)

This mapping is continuous over the convex compact set of all stationary Markov policy profiles. Hence, by Brouwer’s fixed-point theorem, there exists a fixed point $π^{∗} = \phi (π^{∗})$ .

To complete the proof, we need to argue that the fixed point $π^{∗}$ is a Nash equilibrium, that is, for all $$i$$ , $π_{i}^{∗}$ is a best response to $π_{- i}^{∗}$ , even if the best response is computed with respect to arbitrary policies $π_{i}' : S \times ( S \times A )^{∗} \to \Delta ( A_{i} )$ .

Pick an arbitrary player $$i$$ and state $$s$$ . Using the utility-improvement argument from the Nash existence proof (Theorem L1.8), we infer that

\displaystyle \forall a_{i} \in A_{i} , \qquad v_{i}^{π^{∗}} \left( s \right) \ge q_{i}^{π^{∗}} \left(s , a_{i}\right) .

(4)

Indeed, all that is needed to repeat the argument from Nash’s proof is the linearity $v_{i}^{π} ( s ) = \sum_{a_{i}} π_{i} (a_{i} | s) ⋅ q_{i}^{π} (s , a_{i})$ and form of 3.

With this in hand, let us now show that $π_{i}^{∗}$ is a best response to $π_{- i}^{∗}$ for player $$i$$ . From the point of view of player $$i$$ , computing a best response to $π_{- i}^{∗}$ amounts to solving a Markov decision process (MDP) with states $$S$$ and actions $A_{i}$ and rewards, transitions given by

\displaystyle \tilde{r} \left(s , a_{i}\right)

\displaystyle \coloneqq \sum_{a_{- i}} r_{i} \left(s , a\right) ⋅ π_{- i}^{∗} \left(a_{- i} | s\right) ,

\displaystyle \tilde{\mathbb{P}} \left(s' | s , a_{i}\right)

\displaystyle \coloneqq \sum_{a_{- i}} \mathbb{P} \left(s' | s , a\right) ⋅ π_{- i}^{∗} \left(a_{- i} | s\right) .

Notice that the $$V$$ -value function induced by policy $π_{i}^{∗}$ in this MDP, denoted $\tilde{V}^{π_{i}^{∗}} ( s )$ , coincides with $v_{i}^{π^{∗}} ( s ) ,$ as defined above in the stochastic game, i.e.

\displaystyle \tilde{V}^{π_{i}^{∗}} \left( s \right) ≡ v_{i}^{π^{∗}} \left( s \right) , \forall s .

Moreover, 2 and 4 together imply that

\displaystyle \forall s \in S , \qquad \tilde{V}^{π_{i}^{∗}} \left( s \right) = \operatorname*{max}_{a_{i}} \left\{\tilde{r} \left(s , a_{i}\right) + \gamma \sum_{s'} \tilde{V}^{π_{i}^{∗}} \left( s' \right) \tilde{\mathbb{P}} \left(s' | s , a_{i}\right)\right\} .

The previous condition is the Bellman equation for the MDP. From the theory of MDPs, we conclude that $π_{i}^{∗}$ is an optimal policy in the MDP, even among history-dependent policies. Therefore $π_{i}^{∗}$ is a best response to $π_{- i}^{∗}$ , even among history-dependent policies. □

S6.3.3 Shapley’s theorem for two-player zero-sum Markov games

In this section, we turn our attention to two-player zero-sum stochastic games. These are games where the interests of the two players are strictly opposed, i.e., $r_{1} ( s , a ) = - r_{2} ( s , a )$ for all states $$s$$ and action profiles $$a$$ . We typically denote $r ( s , a ) \coloneqq r_{1} ( s , a )$ as the reward for Player 1 (the maximizer) and the cost for Player 2 (the minimizer).

For the remainder of this section, we will focus specifically on the more interesting case of infinite-horizon games. As we discussed in the previous section, finite-horizon games generally do not admit Nash equilibria in stationary Markovian strategies (strategies that depend only on the state, not the time step). In contrast, infinite-horizon games do admit stationary equilibria.

Shapley [Sha53] established a sharp existence result for this setting, showing that these games have a unique value. While we have already established that Nash equilibria exist in general-sum Markov games (using Brouwer’s fixed-point theorem), the zero-sum setting admits a “simpler” reason for existence. This simplicity translates into better computational guarantees. The existence of equilibrium here is guaranteed not merely by the existence of a fixed point of a continuous map (as in Brouwer), but specifically by the existence of a fixed point of a contraction map.

S6.3.3.1 Contraction Mappings and Banach’s Theorem

In the general-sum case, Brouwer’s theorem guarantees a fixed point exists but provides no recipe for finding it. In contrast, a contraction mapping guarantees that simply iterating the function will converge to the unique fixed point.

Definition S6.8 (Contraction Mapping) .

Let $$( X , d )$$ be a complete metric space. A function $T : X \to X$ is called a $\lambda$ -contraction if there exists a constant $\lambda \in [ 0 , 1 )$ such that for all $u , v \in X$ :

\displaystyle d \left( T \left( u \right) , T \left( v \right) \right) \le \lambda ⋅ d \left( u , v \right) .

The mathematical engine behind Shapley’s result is the following fundamental theorem from analysis.

Theorem S6.9 (Banach Fixed-Point Theorem) .

Let $$( X , d )$$ be a non-empty complete metric space and $T : X \to X$ be a $\lambda$ -contraction. Then:

$$T$$ admits a unique fixed point $x^{∗} \in X$ (i.e., $T ( x^{∗} ) = x^{∗}$ ).
For any initial guess $x^{( 0 )} \in X$ , the sequence defined by $x^{( t + 1 )} = T ( x^{( t )} )$ converges to $x^{∗}$ .

Proof Sketch.

The reason contraction maps have fixed points is intuitive: applying the map strictly shrinks the distance between points. Consider the distance between two successive iterates:

\displaystyle d \left( x^{\left( t + 1 \right)} , x^{\left( t \right)} \right) = d \left( T \left( x^{\left( t \right)} \right) , T \left( x^{\left( t - 1 \right)} \right) \right) \le \lambda ⋅ d \left( x^{\left( t \right)} , x^{\left( t - 1 \right)} \right) .

By induction, the steps become exponentially smaller: $d ( x^{( t + 1 )} , x^{( t )} ) \le \lambda^{t} d ( x^{( 1 )} , x^{( 0 )} ) .$ For $$k>t$$ , the triangle inequality bounds $d(x^{(k)},x^{(t)})$ by $\lambda^{t} \frac{d(x^{(1)},x^{(0)})}{1-\lambda}$ . Completeness gives a limit $x^{∗}$ . Continuity of $$T$$ implies $T(x^{∗})=x^{∗}$ . If $y^{∗}$ were another fixed point, contraction would give $d(x^{∗},y^{∗}) \le \lambda d(x^{∗},y^{∗})$ , forcing equality of the points. □

S6.3.3.2 Shapley’s Operator

Shapley used this machinery to prove that zero-sum stochastic games have a value. He constructed a contraction mapping over the space of value functions (not strategies). Let $\boldsymbol{V} \in \mathbb{R}^{|S|}$ be a vector representing the value of the game to Player 1 at each state. We use the infinity norm $\Vert \boldsymbol{V}\Vert_{∞} = \operatorname*{max}_{s} |V(s)|$ .

We define the Shapley Operator (or Bellman Operator) $\mathcal{T} : \mathbb{R}^{|S|} \to \mathbb{R}^{|S|}$ as follows. For a given estimate of future values $\boldsymbol{V}$ , we construct a “local” matrix game at each state $$s$$ where the payoff for joint action $$a$$ is the immediate reward plus the discounted future value:

\displaystyle Q_{s , \boldsymbol{V}} \left( a \right) \coloneqq r \left( s , a \right) + \gamma \sum_{s'} \mathbb{P} \left( s' | s , a \right) V \left( s' \right) .

The operator updates the value of state $$s$$ to be the minimax value (Section L3.1.1) of this local game:

\displaystyle \left( \mathcal{T} \boldsymbol{V} \right) \left( s \right) \coloneqq \operatorname*{max}_{\boldsymbol{π}_{1} \in \Delta \left( A_{1} \right)} \operatorname*{min}_{\boldsymbol{π}_{2} \in \Delta \left( A_{2} \right)} \mathop{\mathbb{E}}\limits_{a \sim \left( \boldsymbol{π}_{1} , \boldsymbol{π}_{2} \right)} \left[ Q_{s , \boldsymbol{V}} \left( a \right) \right] .

Theorem S6.10 (Shapley’s Minimax Theorem) .

The operator

\mathcal{T}

is a contraction mapping with modulus

\gamma

. That is,

\Vert \mathcal{T} \boldsymbol{U} - \mathcal{T} \boldsymbol{V}\Vert_{∞} \le \gamma \Vert \boldsymbol{U} - \boldsymbol{V}\Vert_{∞}

. Consequently, there exists a unique value vector

\boldsymbol{V}^{∗}

such that

\mathcal{T} \boldsymbol{V}^{∗} = \boldsymbol{V}^{∗}

. This

\boldsymbol{V}^{∗}

is the value of the stochastic game.

Proof Sketch.

The proof relies on the fact that the value of a zero-sum matrix game is non-expansive with respect to its payoffs (if payoffs change by $\delta$ , the value changes by at most $\delta$ ). Here, if future values $\boldsymbol{U}$ and $\boldsymbol{V}$ differ by $\epsilon$ , the payoffs in the local matrix games differ by at most $\gamma \epsilon$ . Thus, the values of these local games differ by at most $\gamma \epsilon$ .

At the fixed point, choose a saddle pair in each local matrix game. Fixing either player’s policy gives the other player a discounted MDP. Its optimal Bellman operator fixes $\boldsymbol{V}^{∗}$ because the chosen local strategies are a saddle pair. Uniqueness of the MDP value therefore shows that these stationary policies secure $\boldsymbol{V}^{∗}$ against arbitrary history-dependent opponents. This proves the value and equilibrium assertions, as well as the contraction claim. □

S6.3.3.3 Computation: value iteration and a stopping certificate

Value iteration starts from $\boldsymbol{V}_{0}=0$ and computes $\boldsymbol{V}_{t+1}=\mathcal{T}\boldsymbol{V}_{t}$ . Each step solves one matrix game per state. To extract policies with a specified equilibrium error, we need to relate the Bellman residual to deviation gains.

Theorem S6.11 (Residual certificate for an approximate equilibrium) .

Let $\boldsymbol{V}$ be any value vector and choose a saddle pair $π=(π_{1},π_{2})$ in every local matrix game $Q_{s,\boldsymbol{V}}$ . Set

\displaystyle ρ=\left\Vert \mathcal{T}\boldsymbol{V}-\boldsymbol{V}\right\Vert_{∞}.

The resulting stationary profile is a

2 \frac{ρ}{1-\gamma}

-Nash equilibrium from every initial state, for the unnormalized discounted utilities used in this lecture.

Proof.

Let $\mathcal{T}_{π}$ be the affine Bellman operator obtained by fixing both policies. Let $\mathcal{T}_{1}$ be the maximizing player’s best-response operator with $π_{2}$ fixed, and $\mathcal{T}_{2}$ the minimizing player’s best-response operator with $π_{1}$ fixed. The local saddle conditions give

\displaystyle \mathcal{T}_{π} \boldsymbol{V} = \mathcal{T}_{1} \boldsymbol{V} = \mathcal{T}_{2} \boldsymbol{V} = \mathcal{T}\boldsymbol{V}.

All three operators are $\gamma$ -contractions. For any contraction $$F$$ with fixed point $\boldsymbol{w}$ ,

\displaystyle \left\Vert \boldsymbol{w}-\boldsymbol{V}\right\Vert_{∞} \le \gamma \left\Vert \boldsymbol{w}-\boldsymbol{V}\right\Vert_{∞} + \left\Vert F \boldsymbol{V}-\boldsymbol{V}\right\Vert_{∞}.

Thus its fixed point lies within

\frac{ρ}{1-\gamma}

\boldsymbol{V}

. Applied to the three operators, this bounds the profile value and both best-response values. Their pairwise differences are at most

2 \frac{ρ}{1-\gamma}

, which bounds either player’s unilateral gain. Discounted MDP optimality includes history-dependent deviations. □

A concrete algorithm is therefore:

Set $\boldsymbol{V}=0$ .
For each state, solve $Q_{s,\boldsymbol{V}}$ , retaining its value $$W(s)$$ and saddle strategies $π_{1}(s),π_{2}(s)$ .
If $\Vert \boldsymbol{W}-\boldsymbol{V}\Vert_{∞} \le \frac{\epsilon (1-\gamma )}{2}$ , return the retained policies.
Otherwise set $\boldsymbol{V}=\boldsymbol{W}$ and repeat.

The returned policies are those computed from the same $\boldsymbol{V}$ whose residual was tested. The proof also handles $\gamma =0$ without dividing by $\gamma$ . If the stage games are solved numerically, their optimization errors must be included in the residual and best-response bounds; the displayed certificate assumes exact local solutions.

S6.3.3.4 Discount dependence and computational complexity

Suppose $|r(s,a)| \le R$ and $0<\gamma <1$ . Contraction implies

\displaystyle \left\Vert \boldsymbol{V}_{t+1}-\boldsymbol{V}_{t}\right\Vert_{∞} \le \gamma^{t} \left\Vert \boldsymbol{V}_{1}-\boldsymbol{V}_{0}\right\Vert_{∞} \le \gamma^{t} R.

Consequently the stopping criterion is met once $\gamma^{t} R \le \frac{\epsilon (1-\gamma )}{2}$ . For fixed $$R>0$$ , the number of iterations is bounded by

\displaystyle 1 + O\left(\frac{1}{1-\gamma} \operatorname{log} \operatorname*{max}\left\{1, \frac{2R}{\epsilon \left(1-\gamma \right)}\right\}\right).

Each iteration solves $$|S|$$ matrix games. This is an arithmetic/optimization bound; bit complexity also accounts for rational input lengths and the precision of the local solves. If $1-\gamma$ is exponentially small in its binary encoding length, this iteration bound is not polynomial in the input length.

Changing the discount factor changes the problem, and cannot in general remove this dependence. For example, a one-state game with reward $$1$$ at every step has value $\frac{1}{1-\gamma}$ . Replacing $\gamma =0.9999$ by $1-\epsilon$ with $\epsilon =0.01$ changes the value from $$10,000$$ to $$100$$ . There is no $O(\epsilon )$ approximation of these unnormalized values. Such a substitution also needs a separate policy-transfer argument before it can certify an equilibrium of the original game.

The computational comparisons should therefore be made with their models specified:

A rational two-player zero-sum normal-form game can be solved exactly by linear programming in polynomial bit complexity.
For finite discounted two-player zero-sum Markov games, the value-iteration guarantee above depends on $\frac{1}{1-\gamma}$ as well as the requested accuracy. Banach’s theorem supplies this quantitative convergence argument, not a discount-independent polynomial bound.
General-sum two-player normal-form Nash computation is PPAD-complete [CDT09[CDT09] Chen, X., Deng, X., & Teng, S.-H. (2009). Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3), 1–57.]. For more players, exact algebraic solutions and approximate equilibria must be distinguished [EY10[EY10] Etessami, K., & Yannakakis, M. (2010). On the Complexity of Nash Equilibria and Other Fixed Points. SIAM Journal on Computing, 39(6), 2531–2597. link].

Simple stochastic games, studied by Condon [Con92[Con92] Condon, A. (1992). The Complexity of Stochastic Games. Information and Computation, 96(2), 203–224. link], form a different model: a turn-based reachability game with maximizing, minimizing, and random vertices. The decision problem belongs to NP intersect coNP. This result is not a claim about strongly polynomial algorithms for arbitrary simultaneous-move discounted Markov games. Here, “polynomial time” counts the binary encoding of numerical data, whereas “strongly polynomial” imposes a stricter arithmetic-operation requirement.

S6.4 Bibliography for this lecture

[Sha53]	Shapley, L. S. (1953). Stochastic games. Proceedings of the National Academy of Sciences, 39(10), 1095–1100.
[Tak64]	Takahashi, M. (1964). Equilibrium points of stochastic non-cooperative $$n$$ -person games. Journal of Science of the Hiroshima University, Series AI (Mathematics), 28(1), 95–99.
[Fin64]	Fink, A. M. (1964). Equilibrium in a stochastic $$n$$ -person game. Journal of Science of the Hiroshima University, Series Ai (Mathematics), 28(1), 89–93.
[CDT09]	Chen, X., Deng, X., & Teng, S.-H. (2009). Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3), 1–57.
[EY10]	Etessami, K., & Yannakakis, M. (2010). On the Complexity of Nash Equilibria and Other Fixed Points. SIAM Journal on Computing, 39(6), 2531–2597. `https://doi.org/10.1137/080720826`
[Con92]	Condon, A. (1992). The Complexity of Stochastic Games. Information and Computation, 96(2), 203–224. `https://doi.org/10.1016/0890-5401(92)90048-K`