How to cite

@misc{mit-multiagent-learning-lecture-S5,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Supplementary reading S5: 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 S5

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.

S5.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 S5.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 , \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
$\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 S5.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.

S5.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 S5.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, the policy is the same. In particular, the policy is a function

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

Definition S5.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_{s_{0} \sim \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] .

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 \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 S5.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.

S5.3 Nash Equilibrium Existence

S5.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, 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 S5.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 S5.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.

S5.3.2 The infinite-horizon case

Theorem S5.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 S5.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 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) v_{i}^{π} = 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 S5.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 v_{i}^{π} = \left(I - \gamma \Gamma^{π}\right)^{- 1} r_{i}^{π} .$

Furthermore, the values $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 $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$ , similar to what we used in Lecture 2, 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 same logic in the Nash equilibrium existence proof in Lecture 2, 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.

S5.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.

S5.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 S5.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 S5.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 )} ) .$ The sequence is therefore Cauchy and must converge to a unique limit.

S5.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 $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 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 $$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 , 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 of this local game:

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

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

The operator

\mathcal{T}

is a contraction mapping with modulus

\gamma

. That is,

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

. Consequently, there exists a unique value vector

V^{∗}

such that

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

. This

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

\(U\)

and

\(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

S5.3.3.3 Computation: Value Iteration

The constructive nature of the Banach Fixed-Point Theorem yields a natural algorithm for computing the Nash equilibrium, known as Value Iteration. Conceptually, this algorithm is “decentralized.” We do not need to solve one giant optimization problem for the whole game. Instead, in each round, we update the value of every state by solving a local normal-form game based on the values from the previous round.

Initialization: Set $V^{( 0 )} ( s ) = 0$ for all $s \in S$ .
Iterative Step: For $t = 0 , 1 , 2 , \dots$ :
1. For each state $s \in S$ , construct the matrix game $M_{s}$ with payoffs:
  
  $\displaystyle A_{i j} = r \left( s , a_{i} , a_{j} \right) + \gamma \sum_{s'} \mathbb{P} \left( s' | s , a_{i} , a_{j} \right) V^{\left( t \right)} \left( s' \right) .$
2. Compute the value $v_{s}$ of the matrix game $M_{s}$ (this can be done efficiently using Linear Programming).
3. Update the estimate: $V^{( t + 1 )} ( s ) ← v_{s}$ .
Termination: Stop when $\Vert V^{( t + 1 )} - V^{( t )}\Vert_{∞} \le \epsilon \frac{1 - \gamma}{2 \gamma}$ .

Once the value function $V^{∗}$ (or a sufficient approximation) is computed, the stationary Nash equilibrium strategy for each player at state $$s$$ is simply the optimal (minimax) strategy in the local matrix game defined by payoffs $Q_{s , V^{∗}}$ .

Note that the convergence rate of the algorithm above depends heavily on the contraction modulus $\gamma$ . Specifically, the number of iterations required to reach precision $\epsilon$ scales with $\frac{1}{1 - \gamma}$ . This raises a difficulty if the discount factor is extremely close to $$1$$ (the “high-precision” regime), or if we are investigating the undiscounted setting where $\gamma \to 1$ . In such cases, the term $\frac{1}{1 - \gamma}$ blows up, potentially rendering the basic algorithm inefficient.

However, if our goal is merely to find an $\epsilon$ -approximate Nash equilibrium, we can circumvent this issue by artificially contracting the map. Even if the true game has $\gamma ≈ 1$ , we can substitute it with a surrogate game having a discount factor $\tilde{\gamma} = 1 - \epsilon$ . It can be shown that the value of this surrogate game differs from the true value by at most $O ( \epsilon )$ . Crucially, running Value Iteration on this surrogate game requires a number of iterations proportional to $\frac{1}{1 - \tilde{\gamma}} = \frac{1}{\epsilon}$ . This standard trick effectively converts the dependence on the discount factor into a polynomial dependence on $1 / \epsilon$ .

S5.3.3.4 The Complexity Landscape

We can now place the difficulty of solving two-player zero-sum Markov games in a rigorous context. By analyzing how the computational cost scales with the precision $\epsilon$ , we observe a striking hierarchy that mirrors the mathematical tools used to prove existence:

Two-player Zero-sum Normal-form Games ( $\mathrm{\boldsymbol{\operatorname{log} ( 1 / \epsilon )}}$ ): These are the “easiest” case. Existence is guaranteed by Linear Programming Duality. Consequently, we can use linear programming algorithms (like Interior Point methods) to find $\epsilon$ -approximate equilibria in time proportional to $\operatorname{log} ( 1 / \epsilon )$ .
Two-player Zero-sum Markov Games ( $\mathrm{\boldsymbol{\mathord{\operatorname{poly}} ( 1 / \epsilon )}}$ ): This setting occupies the middle ground. Existence is guaranteed by Banach’s Fixed Point Theorem (Contraction Mappings). As discussed above, even in the worst case where $\gamma \to 1$ , we can use the artificial contraction trick to find $\epsilon$ -approximate equilibria in time proportional to $\mathord{\operatorname{poly}} ( 1 / \epsilon )$ .
General-sum Normal-form Games ( $\mathrm{\boldsymbol{\operatorname{exp} ( 1 / \epsilon )}}$ ): These are the “hardest” case. Existence is guaranteed only by Brouwer’s Fixed Point Theorem (Topology), which provides no constructive recipe. Computing a Nash equilibrium is PPAD-complete. The best known algorithms run in time ( $n^{O ( \operatorname{log} n / \epsilon^{2} )}$ ), quasi-polynomial in the number of actions and exponential in $1 / \epsilon$ .

This spectrum ( $\operatorname{log} ( 1 / \epsilon )$ vs. $\mathord{\operatorname{poly}} ( 1 / \epsilon )$ vs. $\operatorname{exp} ( 1 / \epsilon )$ ) highlights the unique position of Markov games. While the $\mathord{\operatorname{poly}} ( 1 / \epsilon )$ result ensures tractability, a major open problem is whether two-player zero-sum Markov games can be pushed into the “logarithmic” category. Specifically, can they be solved in strongly polynomial time (time independent of the transitions and discount factor)? This is known as the Simplest Stochastic Games Conjecture and it is one of the major open questions in algorithmic game theory.

S5.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.