We consider a two-player zero-sum discounted Markov game defined by a tuple \((\mathcal {S}, \mathcal {A}, \mathcal {B}, \sigma , p, \gamma )\) , where: 1) \(\mathcal {S}\)  is a finite state space; 2) \(\mathcal {A}\)  and \(\mathcal {B}\)  are finite action spaces for Player 1 and Player 2 respectively; 3) \(\sigma \)  is the loss (payoff) function for Player 1 (Player 2), with \(\sigma (s, a, b)\in [0,1]\)  specifying how much Player 1 pays to Player 2 if they are at state \(s\)  and select actions \(a\)  and \(b\)  respectively; 4) \(p: \mathcal {S}\times \mathcal {A}\times \mathcal {B}\rightarrow \Delta _{\mathcal {S}}\)  is the transition function, with \(p(s^{\prime }|s, a, b)\)  being the probability of transitioning to state \(s^{\prime }\)  after actions \(a\)  and \(b\)  are taken by the two players respectively at state \(s\)  (\(\Delta _{\mathcal {S}}\)  denotes the set of probability distributions over \(\mathcal {S}\) );
5) and \(\frac{1}{2}\le \gamma <1\)  is a discount factor.The discount factor is usually some value close to 1, so we assume that it is no less than \(\frac{1}{2}\)  for simplicity. Also note that we consider the discounted setting instead of the finite-horizon episodic setting because the former captures more challenges of this problem (and is also the original setting considered in [1]}). Indeed, in the episodic setting where states have a layered structure, convergence can be directly shown in a layer-by-layer manner; see [2]}, an early version of [3]}.
