Learning Nash Equilibria in Zero-Sum Stochastic Games via Entropy-Regularized Policy Approximation

We explore the use of policy approximations to reduce the computational cost of learning Nash equilibria in zero-sum stochastic games. We propose a new Q-learning type algorithm that uses a sequence of entropy-regularized soft policies to approximate the Nash policy during the Q-function updates. We prove that under certain conditions, by updating the regularized Q-function, the algorithm converges to a Nash equilibrium. We also demonstrate the proposed algorithm's ability to transfer previous training experiences, enabling the agents to adapt quickly to new environments. We provide a dynamic hyper-parameter scheduling scheme to further expedite convergence. Empirical results applied to a number of stochastic games verify that the proposed algorithm converges to the Nash equilibrium, while exhibiting a major speed-up over existing algorithms.


Introduction
Stochastic Games (SG) [1] is a widely adopted framework to extend reinforcement learning [2] to multiple-agent scenarios. The resulting multi-agent reinforcement learning (MARL) framework assumes a group of autonomous agents that choose actions independently and interact with each other to reach an equilibrium [3]. When all agents are rational, the most natural solution concept is the one of a Nash Equilibrium (NE) [4]. The difficulty of extending singleagent RL methods to learn the NE stems from the fact that the interactions among agents result in a non-stationary environment and thus make learning computationally expensive and difficult to stabilize [5].
Several approaches have been proposed to learn policies in multi-agent scenarios. One set of algorithms learn directly a NE using computationally demanding operators, such as Minimax-Q [6] and Nash-Q [7]. Agents adopting these algorithms follow more rational policies but in doing so, they tend to take more time to learn these policies. For example, Minimax-Q needs to solve a linear program to compute the Nash equilibrium at each Q-function update. Even with the help of neural networks, the number of linear programs solved during the learning process still grows with the cardinality of the state and action spaces, which makes Minimax-Q infeasible for large games.
Other popular approaches that extend single-agent RL methods [8] to multi-agent scenarios include: simplifying the interactions [9,10,11], or introducing extra mechanisms in the game [12,13,14]. Such algorithms allow the agents to compute "fast" but less rational policies, but are unlikely to converge to a rational equilibrium, in general.
The recent works on entropy-regularized soft Q-learning [15] provide an efficient way to approximate Nash policies. Specifically, the two-agent Soft-Q algorithm [16] avoids the use of the expensive linear optimizations to update the Q-function. The two agents, instead, compute closed-form soft-optimal policies under an entropy regularization that explores the policy space close to the given priors. Due to fixed regularization, however, the generated policies of the two-agent Soft-Q may be far from a NE. Consequently, there is a need for algorithms that learn the NE, yet in a computationally efficient manner, that can be used in a wide variety of multi-agent situations.
To achieve convergence to NE while maintaining computational efficiency, we propose a novel adaptive entropyregularized Q-learning algorithm for zero-sum games, referred to as Soft Nash Q 2 -learning (SNQ2L) 1 . The proposed algorithm learns two different Q-values: a standard Q-value and an entropy-regularized soft Q-value. The two values are used asynchronously in a "feedback" learning mechanism: the soft policies act as an efficient Step 1. Compute the Nash policies at each state given the Q-function estimate at the current iteration t, by solving a linear program [17]. For example, the maximizing Player has the following optimization problem, max v subject to v1 T − π pl (s) T Q t (s) ≤ 0 1 T π pl (s) = 1, π pl (s) ≥ 0, (1) where π pl (s) is the policy in vector form and Q t (s) is the Q-matrix at state s. The Nash policy of the Opponent can be solved in a similar manner. We denote the solutions to these optimization problems as π pl Nash,t (s) and π op Nash,t (s), respectively. Performing the optimizations at all states s one may define the overall operation via the operator Γ Nash : Q → Π as (π pl Nash,t , π op Nash,t ) = Γ Nash Q t .
Step 2. Given a policy pair π, update the Q-function via Q t+1 (s, a pl , a op ) = R(s, a pl , a op ) + γ s ∈S T (s |s, a pl , a op ) π pl (s ) T Q t (s )π op (s ).
Similarly, we define the standard Q-function update operator as Γ 1 : Q × Π → Q. The Shapley's Method utilizes the following operator to iterate on the Q-functions.
Theorem 1 [17] is the foundation for the convergence of both Shapley's method and Minimax-Q.
Theorem 1. The operator B is a sup-norm contraction mapping with a contraction factor of γ. The fixed point of B is the Q-function corresponding to a Nash equilibrium.

Entropy-Regularized Policy Approximation
Entropy-regularized policy approximation [15] was originally introduced to reduce the maximization bias commonly seen in learning algorithms. This idea was later extended to two-agent scenarios and is referred to as the two-agent Soft-Q algorithm [16]. Two-agent Soft-Q introduces two fixed entropy-regulation terms to the reward structure and thus restricts the policy exploration to a neighborhood of the given priors. Given a policy pair (π pl , π op ), the soft-value function is defined as V π pl ,π op KL (s) = E π pl ,π op s ∞ t=0 γ t R(s t , a pl t , a op t ) − 1 β pl log π pl (a pl t |s t ) ρ pl (a pl t |s t ) where β pl > 0 and β op < 0 are inverse temperatures, and ρ pl and ρ op are priors for the Player and the Opponent.
The objective of the two-agent Soft-Q algorithm is to find the optimal solution to the max-min optimization problem max π pl min π op V KL (s; π pl , π op ). It has been shown in [16] that the optimal solution can be found through an iterative algorithm.
Step 1. With the current soft Q-function Q KL,t , construct the soft optimal policy for the Player through the closedform solution π pl KL,t (a pl |s) = where Z pl (s) is the normalization factor and Q pl KL,t is a marginalization through a log-sum-exp function The soft-optimal policy of the Opponent can be obtained in a similar manner. One can then define the soft optimal policy generating operator Γ β KL : Q × Π → Π as (π pl Nash,t , π op Nash,t ) = Γ β KL (Q KL,t , ρ). Reduce inverse temperature β 11 end 12 return πNash and Q(s, a pl , a op ).
Step 2. With the marginalization in (7), compute the optimal value at state s via One can then update the Q-function through We denote the soft update operator Γ β Note that, due to the fixed regularization, the two-agent Soft-Q algorithm does not converge to a NE in general.

Sequential Policy Approximation Algorithm
In Algorithm 1, we present the baseline SNQ2 in the cMDP settings, where the game G is known. Different from the two-agent Soft-Q with a fixed entropy regularization, the proposed algorithm decreases β over time. As a result, a sequence of policy approximations of different levels of regularization is applied, and thus enables the algorithm to converge to a NE.
Within the while loop, the algorithm first computes the Nash policies under the current estimate of the Q-function, and it uses the Nash policies as the priors to generate the soft policies. The soft policies are then used to update the Q-functions.
To prove the convergence of the baseline SNQ2 algorithm, we define the operations within the while loop in Algorithm 1 as Γ β :Q →Q, such that .
The baseline SNQ2 algorithm differs from the standard iterative algorithms, in the sense that the operator Γ β changes at every iteration, as the inverse temperature pair β = (β pl , β op ) decreases to zero. As a result, we first present our theorem regarding the convergence of sequentially applying a family of contraction mappings. The proof of Theorem 2 can be found in Appendix C. Theorem 2. Let (X , ρ) be a complete metric space, let f n : X → X be a family of contraction mappings, such that, for all n = 1, 2, . . . there exists d n ∈ (0, 1), such that ρ(f n x, f n y) ≤ d n ρ(x, y) for all x, y ∈ X . Assume that lim n→∞ d n = d ∈ (0, 1). Let x ∈ X , and let x (n) = f n · · · f 1 x be the result of sequentially applying the operators f 1 , . . . , f n to x. If the sequence of operators {f n } ∞ n=1 converges pointwise to f , then f is also a ρ-contraction mapping with contraction factor d. Furthermore, if x is the fixed point of f , then, for every x ∈ X , lim n→∞ x (n) = x .
We now present the convergence theorem of Algorithm 1. Theorem 3. Under certain regularity assumptions, by sequentially applying Γ β and gradually decreasing β to zero, Algorithm 1 converges to a Nash equilibrium.
Proof. We provide a sketch of the proof here. The complete proof can be found at the supplementary material in Appendix C. We first show that under certain regularity assumptions, the operator Γ β is a family of contraction mapping. We then show that as β approaches zero, the operator Γ β converges pointwise to an operator, which has the concatenated Nash Q-function [Q Nash , Q Nash ] T as its unique fixed point. Then, by Theorem 2, we conclude that Algorithm 1 converges to a Nash equilibrium by sequentially applying Γ β to some initial Q-function and decreasing β to zero. This baseline SNQ2 serves as a demonstration of the sequential policy approximation idea behind the SNQ2 algorithm. It does not relieve the computational burden of computing Nash policies, as we update the Nash policies at every iteration in the while loop. Due to the simplicity of the baseline algorithm, we can demonstrate its mechanism within the space limit. The standard SNQ2, on the other hand, only applies Γ Nash periodically. We present the standard SNQ2 algorithm and its convergence proof in the appendix.

Two-Agent Soft Nash Q 2 -Learning
In this section, we present the two-agent Soft Nash Q 2 -Learning algorithm (SNQ2L). This algorithm is an (asynchronous) learning version of the standard SNQ2 in Algorithm 1. Specifically, this algorithm does not have access to the dynamics of the game and uses stochastic approximations to estimate the expectation operator in (5). This SNQ2L algorithm only updates the Nash policies periodically according to a dynamic schedule, and thus reduces the computations required to find the Nash equilibrium.
Learning Rule for Q KL .
Here, t is the learning step, and V KL,t (s t+1 ) is computed as in (9) using the current Q KL,t estimate. The priors used in (9) are updated periodically using the Nash policies as indicated by the red arrow in Figure 1.
Learning Rule for Q.
To compute the estimated optimal value V t (s t+1 ), SNQ2L uses either soft policies or Nash policies. We summarize SNQ2L with dynamic schedule in Algorithm 2.

Schedule of the Hyper-parameters M and β
As presented in Algorithm 2, the trade-off between computational efficiency and approximation accuracy is embedded in the prior update frequency ∆M and the Nash update frequency T . Intuitively, when the new Nash priors are close to the old ones, the algorithm is close to convergence. In this situation, the prior update frequency should be decreased (increase ∆M ) and the algorithm should trust and exploit the priors (decrease β).
The default number of episodes between two Nash prior policy updates ∆M 0 and the default decay rate of the inverse temperature λ ∈ (0, 1) are given initially as where α 0 is the initial learning rate and T max is the maximum length of a learning episode; β 0 and β end are the initial and estimated final magnitude for both β op and β pl , and N updates is the estimated number of prior updates. This value of ∆M 0 allows the algorithm to properly explore the state-action pairs so that the first prior update is performed with an informed Q-function. In our numerical experiments we found that β 0 = 20, β end = 0.1 and N updates = 10 are a good set of values.
Algorithm 3 summarizes the dynamic schedule scheme, where the parameter σ ∈ (0, 1) is a decrease factor and the RelativeDifference captures the performance difference between old and new priors. We demonstrate the performance boost due to dynamic schedule in Section 5.5.

Warm-Starting
One can warm-start the proposed SNQ2L algorithm by first initializing the priors ρ pl and ρ op based on some previously learnt policies or expert demonstrations, and then also postponing the first prior update to exploit these priors. Using Compute V(st+1) = max π pl min a op , a pl Q(st+1, a pl , a op )π pl a pl |st+1 ; (13)  a prior policy instead of the value to warm-start the algorithm has two major advantages: first, human demonstrations can be converted into prior policies in a more streamlined manner than into value information; second, prior policies provide more consistent guidance than the values, as the priors are not updated till the first prior update. We demonstrate the effectiveness of transferring previous experience in Section 5.4.

Evaluation Criteria
Two metrics were used to evaluate the performance of different algorithms: the number of states achieving a NE and the running time 3 . For each game, we computed four different values and compared them to determine whether a state has achieved a NE: (a) the ground truth Nash value V Nash solved exactly via Shapley's method; (b) the learnt value V L ; (c) the one-sided MDP value V pl L computed by fixing the Opponent to her learnt policy and letting the Player maximize; (d) the one-sided MDP value V op L . We assume that the learnt policies achieve a NE at state s, if the values at state s satisfy Notice that the evaluation criterion above is stricter than the case of only collecting empirical win rates of different agents competing in the environment as in [6,21], since any deviation from the NE could be exploited by either agent in our criteria.
Both agents seek to avoid collision with the obstacles (marked in black). The Pursuer strives to capture the Evader by being in the same cell as the Evader. The goal of the Evader is to reach one of the evasion cells (marked in red) without being captured. Two agents simultaneously choose one of four actions on each turn: N, S, E, and W. Each executed action results in a stochastic transition of the agent's position. In the default setting, an agent has a 60% chance of successfully moving to its intended cell and a 40% chance of landing in the cell to the left of the intended direction. The 4×4 and 8×8 PEGs use the default transitions and the 6×6 PEG uses deterministic transitions. In such setting, a deterministic policy cannot be a Nash policy. Soccer. The soccer game [6] is played on a 4×5 grid as in Figure 3. Two agents, A and B, can choose one of five actions on each turn: N, S, E, W, and Stand, and the two actions selected are executed in random order. The circle represents the ball. When the agent with the ball steps in to the goal (left for A and right for B), that player scores and the game restarts at a random state. When an agent executes an action that would take it to the cell occupied by the other agent, possession of the ball goes to the stationary agent. Littman [6] argued that the Nash policies must be stochastic.
Sequential Rock-Paper-Scissor. In a sequential Rock-Paper-Scissor game (sRPS), two agents (pl and op) play Rock-Paper-Scissor repeatedly. One episode ends when one of the two agents wins four consecutive games. The states and transitions are shown in Figure 3. State s 0 corresponds to the initial state where no one has won a single RPS game, and states s 4 and s 8 are the winning (terminal) states of pl and op respectively. The Nash policies of sPRS at each state are uniform for both agents.

Comparison to Existing Algorithms
We evaluate SNQ2L on the game environments in Section 5.2 using the evaluation criteria in Section 5.1. The SNQ2L algorithm can be initialized with two types of priors, uniform 4 (SNQ2L-U) and previous experience (SNQ2L-PE). Previous experience for PEGs and Soccer is learnt in a training session of the same game but with a different dynamics. For sRPS, the previous experience is a perturbed uniform strategy. The algorithm also has the option of a fixed (a) Performance at convergence (b) Computation time (c) Performance at cutoff Figure 4: All results are averaged over ten runs. The computation time in (b) is normalized by that of Minimax-Q. We cut off the computation at 600k episodes for 8×8 PEG, due to the large state space. In most of the experiments, SNQ2L achieves a slightly better convergence to NE than Minimax-Q, while exhibiting an significant reduction in computation time. Two-agent Soft-Q, Single-Q and WoLF-PHC are fast but fail to converge to NE in all five games hence are not shown in (b). Note that two-agent Soft-Q fails completely in sRPS.
schedule (SNQ2L-FS) and a dynamic schedule (SNQ2L-DS). Unless otherwise specified, SNQ2L uses a dynamic schedule. SNQ2L was compared with four popular existing algorithms: Minimax-Q, two-agent Soft-Q, WoLF-PHC and Single-Q. We fine-tuned these existing algorithms to get the best performance so as to demonstrate their actual capabilities. We compare the convergence performance of the algorithms in Figure 4.
The sRPS game with a uniform Nash equilibrium shows that SNQ2L is capable of converging to a fully mixed strategy. In this game, two-agent Soft-Q learning fails to converge to the uniform NE, as its reward structure is regularized as in (5); Single-Q learning tries to learn a pure policy but does not converge; WoLF-PHC converges to NE at two terminal states but with large value deviation, which propagates to other states and results in poor policies.
We then examine the 4×4 PEG game. Despite the relatively small state space, the stochastic transition at all nonterminal states requires extensive exploration of the environment. We plot the convergence trends over 300k episodes and over 12k seconds for Minimax-Q and SNQ2L in Figure 5. The time-wise convergence trends in Figure 5 demonstrate the expedited convergence of SNQ2L in terms of computation time. The episode-wise trend plot shows that SNQ2L maintains the same level of convergence to NE as Minimax-Q, albeit with significantly reduced computation time. This shows that our adaptive entropy-regularized policy approximation approach is both accurate and efficient.

Effectiveness of Warm-Starting
In PEGs, the agents learn their previous experience on the same grid but with a 75% success rate. To reduce overfitting to the previous environment, the prior policy fed to the agent for a new training session is the average of the previously learnt policy and a uniform policy. As seen in Figure 5(b), previous experience does not shorten the time till convergence but instead significantly reduces the time to reach a reasonable performance. We plot the cutoff time performance of the 4×4 and 8×8 PEGs in Figure 4(c). In the 4×4 example the time to reach over 90% Nash convergence is halved from 1.2k seconds with uniform prior down to 600 seconds with previous experience. In the 8×8 example the time to 80% convergence was halved from 7.2k seconds to 3.6k seconds.
One also observes from Figure 5(a) that the policies generated by SNQ2L with previous experience converge, episodewise, slightly faster than Minimax-Q. This "warm-start" feature has appealing real-world applications, where the number of episodes interacting with the environment is the main constraint instead of computation time. In this case, one can first train prior policies using a simulator and use these as priors to the agents. With SNQ2L one can train the agents to reach a reasonable level of performance in fewer episodes, while maintaining a relatively low computation overhead.

Effectiveness of Dynamic Schedule
In Figure 5(a), we use a fixed schedule (FS) with constant prior update intervals and we compare with the dynamic schedule (DS). The latter demonstrates a faster episode-wise convergence by reducing the number of episodes in which SNQ2L exploits a bad initial prior at the beginning of the learning. As the initial learning rate is large, a Q-value based on a bad prior could be difficult to correct later on. When the algorithm is close to convergence, DS reduces the prior update frequency and thus reduces performance oscillations, as shown in Figure 5. In Figure 6, the FS is fine-tuned through trial and error, and the DS is given a sub-optimal initial schedule. DS recovers from the given sub-optimal schedule and is still capable of achieving similar, or even better, performance compared to the hand-tuned FS.

Conclusions and Future Work
We have proposed a novel algorithm for solving zero-sum games where the agents use entropy-regularized policies to approximate the Nash policies and thus reduce computation time till convergence. We proved that under certain conditions, the proposed algorithm converges to a Nash equilibrium. We conducted numerical experiments on multiple games of different sizes and levels of stochasticity. The simulation results demonstrated that the algorithm significantly reduces computation time when compared to existing algorithms. We also demonstrated the effectiveness of warmstarting in a new environment using previous experience. One interesting direction of future work is to extend the current algorithm to general-sum games.

Appendix A Derivation of the Two-Agent Soft-Q
In this appendix, we derive the entropy-regulated policy approximations that are used in the SNQ2 algorithm. Most of the derivations in this section can be found in the existing literature (see for example [15] and [16]). The limiting case when the inverse temperature β goes to zero is, however, only briefly discussed in the previous works, and without providing rigorous justification. As the convergence of the SNQ2 algorithm relies on the limiting behavior of the entropy-regulated policy approximation operators, we present several results to provide more insight to the limiting case where β approaches zero.
We first revisit the policy approximation for the single-agent scenario (see [15]). We then utilize the single-agent results to derive the corresponding operators for the two-agent zero-sum game.

A.1 Single-Agent Soft-Q Learning
The single-agent entropy-regulated policy approximation is formulated as the following optimization problem [15] such where R(s, a) is the reward collected at state s should the agent chooses action a at that state. The agent follows a policy π and uses policy ρ as its reference. The constraint in (15) is meant to restrict exploration to policies that are close to the reference policy.
The expectation operator in (14) and (15) is over all state-action trajectories ensuing by executing the policy π. Notice that the expectation of the information cost over the policy π in (15) turns out to be the Kullback-Leibler (KL) divergence between π(s) and ρ(s). To solve the optimization problem in (14)- (15) we introduce a Lagrangian multiplier (−1/β) to obtain an unconstrained optimization problem as follows As a result of this Lagrangian relaxation, a positive inverse temperature β corresponds to a maximization problem, and a negative β corresponds to a minimization problem.
The magnitude of β controls how far the optimal policy π can deviate from the reference policy ρ. If β → ∞, the information cost constraint (15) is no longer in effect, which can be seen from the complementary slackness condition. If, instead, β → 0, the optimal policy collapses to the reference policy. This is formally proved later in this section. Intuitively, when β = 0, any deviation from the reference policy would induce an infinite information cost.
The policy π that optimizes the above entropy-regulated optimization problem, is commonly referred to as the softoptimal policy. We will use the soft-optimal policies in the two-agent case to approximate the Nash policies in the next subsection.
Define the π-policy dependent soft value V π KL as where we use the shorthand notation R s, π(s) = a∈A π(a|s)R(s, a), T ss π(s) = a∈A π(a|s)T ss (a).
Next, we define the soft Q-function corresponding to the policy π at state s as Subsequently, we can also write We define the soft-optimal value as = max The corresponding soft-optimal Q-function is then defined as Given a value vector U ∈ R |S| , we define the operator B : R |S| → R |S| as follows It follows that the optimal soft value V * KL is a fixed point of the operator B. That is, the optimization in (19) reduces to finding the solution to the following equation (21) is a sup-norm contraction with contraction factor γ.
and shows that it is a contraction mapping. One can then show that, with an extra max operator added to B π , the soft value update operator B is still a contraction mapping. This step is similar to proving that the standard Bellman operator is a contraction mapping [8]. Refer to [15] and [16] for more details regarding the proof.
A major consequence of Lemma 4 is that one can find the soft optimal value V KL via iterating the operator B. In the sequel, we use V KL,t to denote the estimate of the soft-optimal value at iteration t. That is, Due to the contraction property of B, we have The resulting estimate of the soft-optimal Q-function at iteration t, is then defined as Given the current estimate Q KL,t of the soft-optimal Q-function, the optimization problem in (19) becomes To further obtain the soft-optimal policy that achieves the maximization problem defined in (26), we need the following lemma from [15]. . (27) Proof. The optimization problem in (26) can be solved via a Lagrangian relaxation, and the solution to the optimization is (27). Refer to [16] for more details.
By substituting the soft-optimal policy π KL,t from (27) back into (26), one obtains a closed-form formula for the resulting soft-optimal value. Corollary 6. Let Q KL,t be the estimate of the soft-optimal Q-function at iteration t. Then, at each state s ∈ S, the soft-optimal value corresponding to policy (27) is given by where Q KL,t is defined through V KL,t as in (25).
A similar derivation works for the minimization version of the problem in (26). Hence, we have the following corollary. Corollary 7. Let β < 0, and consider the following problem For each state s ∈ S, the soft-optimal policy that solves the minimization problem (29) has the solution , and the soft-optimal value at each state s ∈ S is given by Previous works such as [15] and [16] pay little attention to the limiting case of the operator B as the inverse temperature approaches zero. In our work, however, the limiting case of β → 0 plays an essential role in the convergence of the proposed SNQ2 algorithm. As a result, we prove the following lemma regarding the soft optimal value when β → 0. Lemma 8. As the inverse temperature approaches zero, β → 0, we have, for every t = 0, 1, 2, . . . , that where we have used the fact that a ∈A ρ(a |s) = 1 for all s ∈ S.
We conclude this subsection with the following lemma dealing with the soft-optimal policy as the inverse temperature approaches zero. Lemma 9. As β → 0, we have lim β→0 π KL,t (a|s) = ρ(a|s).
Proof. The result follows directly from Lemma 8 shows that, as β → 0, the soft value update converges to a standard value update using the provided prior, similar to the value iterations in the MDPs [8]. At the same time, as the inverse temperature approaches zero, Lemma 9 also shows that the soft-optimal policy converges to the given prior regardless of the current soft-optimal Q-function estimate.

A.2 Two-Agent Soft-Q Learning
In this section, we extend the previous lemmas to the two-agent case game-theoretic setting. These results will serve an important role in showing the convergence of the SNQ2 algorithm in competitive MDP (cMDP) settings.
Consider the two-agent zero-sum case, where the policy-dependent soft value is defined in a similar manner as in (17), as follows Define the (π pl , π op )-policy-dependent Q-value in a similar manner as in (17) Q π pl ,π op KL (s, a pl , a op ) = R(s, a pl , a op ) + γ We consider the case where the Player is the maximizer and the Opponent is the minimizer. Then, the definition of the soft-optimal value for the two-agent zero-sum game is = max π pl a pl π pl (a pl |s) min Proof. One can easily check that V π pl ,π op KL is concave in π pl and convex in π op . Then, via the Minimax Theorem [18], the soft-optimal value is unique.
Similarly to the analysis for the single-agent case, consider a value function U ∈ R |S| , and define the update operator F : R |S| → R |S| as It has been shown in [16] that the operator F is a sup-norm contraction mapping. As a result, the soft-optimal value function is the fixed point of F. That is, V KL = F V KL . One can then iterate F to find the soft-optimal value function. Let V KL,t denote the estimate of the soft-optimal value-function at iteration t. That is, Due to the contraction property of F, we have The estimate of the soft-optimal Q-function Q KL,t is related to the soft-optimal value estimate V KL,t via We now derive the closed-form formula of the operator F. Let V KL,t and Q KL,t denote the estimates at iteration t. The optimization problem in (34) then becomes, = max π pl a pl π pl (a pl |s) min Observe that (38) has the same structure as the optimization problem presented in (29). Using Corollary 7, we therefore have Combining (34) and (39), we arrive at Notice that (40) has the same structure as in (26). By Lemma 5, we have that the solution for the policy of the Player that maximizes (40) is given by π pl KL,t (a pl |s) = ρ pl (a pl |s) exp β pl Q pl KL,t (s, a pl ) a pl ∈A pl ρ(a pl |s) exp β pl Q pl KL,t (s, a pl ) . (41) Applying Corollary 6 to (40), we obtain the updated estimate of the soft-optimal value as V KL,t+1 (s) = 1 β pl log a pl ρ pl (a pl |s) exp β pl Q pl KL,t (s, a pl ) .
Since the soft-optimal value is unique, we can change the order of the max and min operators in (34). We would then have a min-max optimization problem instead. The soft-optimal policy at some iteration t of the Opponent can be then derived in a similar manner (see [16]). Namely, the maximization conducted by the Player results in the following marginalization t (s, a pl , a op ) , and the soft-optimal policy for the Opponent is .
The corresponding expression for the soft-optimal value is given by We provide the following lemma regarding the limiting behavior of the soft-optimal value and soft-optimal policies as the inverse temperatures of the Player and the Opponent both approach zero simultaneously. Lemma 11. As the inverse temperatures β pl and β op approach zero, we have the following limiting relationship regarding the soft-optimal value and the policies Proof. We first show that V KL,t is continuous with respect to β pl and β op . Consider the following log-sum-exp function, where x = (x 1 , x 2 , . . . , x n ) where λ i > 0 and i λ i = 1. One can easily show that (48) is a continuous function with respect to β and x.
The function V KL,t can then be written as follows where Q KL (a pl , ·) is a row vector. Since φ is continuous, the composition in (49) is also continuous with respect to β pl and β op . We can show the continuity of (46) and (47) through a similar argument. Now, with the continuity of V KL,t established, we can prescribe a specific trajectory 5 along which (β pl , β op ) approaches (0, 0). To mimic the manner the SNQ2 algorithm updates the values of β pl and β op , we choose the following path parameterized by β > 0: To show (45), notice that Similarly, for the numerator of the Player's soft-optimal policy in (41), we have Next, for the soft-optimal policy π pl KL,t , we have a pl ρ(a pl |s) = ρ pl (a pl |s).
One can show (47) in a similar manner.

Appendix B Sequential Policy Approximation
In this section, we present the SNQ2 algorithm in a cMDP setting. That is, we assume that the environment is known to the agents, and thus no stochastic approximation is used. We show the convergence of the SNQ2 algorithm in a cMDP setting in the next section. We first define the metric spaces used for the proof of convergence of the SNQ2 algorithm.

B.1 Metric Spaces
Metric Space of Q-functions. As our algorithm operates with two separate Q-functions, we denote the standard Q-function as Q and the soft Q-function as Q KL to differentiate between the two, even though both live in the same space Q ⊆ R |S|×|A pl |×|A op | . We equip the vector space Q with the distance metric D induced by the sup-norm. That is, for Q, Q ∈ Q, Note that (Q, D) is a complete metric space.
Metric Space of concatenated Q-functions. We first define the concatenated Q-function as We then useQ ⊆ R 2×|S|×|A pl |×|A| op as the vector space for the concatenated Q-functions. We equip the vector spacē Q with the distance metricD defined as follows: One can easily verify the identity of indiscernibles, the symmetry, and subadditivity properties ofD.
Metric Space of Policy Pairs. Similar to the Q-functions, the standard policy pair π and the soft policy pair π KL both live in the same metric space Π = ∆ |A pl | |S| × ∆ |A op | |S| . The policy π pl (s) of the Player at state s lives on the standard simplex ∆ |A pl | . With a total of |S| states, the policy π pl is an element of ∆ |A pl | |S| . A similar argument holds for π op . We define a metric W based on the total variation between two policy pairs [22] W(π, π ) = max s {d TV π pl 1 (s), π pl 2 (s) } + max s {d TV (π op 1 (s), π op 2 (s))}.

B.2 Basic Operators
Before presenting the SNQ2 algorithm, we summarize the four operators that are used in the algorithm. Note that the superscript β on Γ β 2 and Γ β KL is a scalar parameter used to parameterize the trajectory of (β pl , β op ) approaching (0, 0), via β = β pl = −β op /κ with κ > 0 by letting β → 0 + . The setup in (50) serves an example.
Standard Q-update Operator: Given a Q-function, and a policy pair π = (π pl , π op ), the standard Q-update Operator Γ 1 updates the Q-function via: Soft Q-update Operator: Γ β 2 : Q × Π → Q. Given a soft Q-function Q KL , and a reference policy pair ρ = (ρ pl , ρ op ), the soft update operator performs the following update: where Q pl KL is obtained, via marginalization, from Q pl KL (s, a pl ) = Soft Q-update Operator: Γ Nash : Q → Π. Given a Q-function, the operator Γ Nash finds the Nash policies corresponding to this Q function by solving the following two linear programs [17] max v, min u, That is, π Nash = (π pl Nash , π op Nash ) = Γ Nash Q.
Soft-Policy Generating Operator: Γ β KL : Q × Π → Π. Given a Q-function Q KL , and a reference policy pair ρ = (ρ pl , ρ op ), one can compute the corresponding soft-optimal policies for the Player and the Opponent per (41) and (43), respectively. That is,

B.3 The SNQ2 Algorithm in cMDP Setting
Algorithm 4 presents the non-learning baseline version of the SNQ2 algorithm. We present the convergence proof of the baseline SNQ2 in the next section. This baseline version of the SNQ2 serves as a demonstration of the sequential policy approximation behind the SNQ2 algorithm. It does not alleviate the computational burden of computing Nash policies, as the Nash policy is updated at every iteration. However, it is easier to show the convergence of the baseline SNQ2 algorithm to the Nash Q-function. The convergence of the general SNQ2 algorithm then follows readily using a simple argument (see Section C.3 and, in particular, Theorem 18) In Algorithm 5, we present the standard SNQ2 algorithm in the cMDP setting. Different from the baseline version, the standard SNQ2 updates the prior for the soft optimal policy every M iterations of Q-function updates.
The algorithm consists of two iteration loops: the inner loop (from line 7 to line 10) updates the Q-functions for a prescribed number M ; the outer loop (from line 5 to line 12) computes the Nash policies fed into Γ β 2 and Γ β KL , and it also reduce the inverse temperature. Reduce inverse temperature β 13 end 14 return πNash and Q(s, a pl , a op ).

Appendix C Convergence of the SNQ2 Algorithm
In this section, some regularity assumptions on the operators are introduced for the analysis of convergence. The main theorem regarding the convergence of sequentially applying a family of contraction mappings is then presented in Theorem 12. Based on that theorem, we first show the convergence of the baseline SNQ2 and then the convergence of the (standard) SNQ2.

C.1 Convergence of Sequentially Applying a Family of Contraction Mappings
The SNQ2 algorithm differs from standard iterative algorithms that utilize contraction mapping arguments, in the sense that SNQ2 utilizes a different contracting operator to update the concatenated Q-function at each iteration, as β decreases. Thus, we need the following theorem regarding the convergence of iteratively applying a family of contraction mappings. Theorem 12. Let (X , ρ) be a complete metric space, let f n : X → X be a family of ρ-contractions, such that, for all n = 1, 2, . . . there exists d n ∈ (0, 1), such that ρ(f n x, f n y) ≤ d n ρ(x, y) for all x, y ∈ X . Assume that lim n→∞ d n = d ∈ (0, 1). Let x ∈ X , and let x (n) = f n · · · f 1 x be the result of sequentially applying the operators f 1 , . . . , f n to x. If the sequence of operators {f n } ∞ n=1 converges pointwise to f , then f is also a ρ-contraction mapping with contraction factor d. Furthermore, if x is the fixed point of f , then, for every x ∈ X , lim n→∞ x (n) = x .
Proof. We first show that the limiting operator f is a contraction mapping. Let x, y ∈ X . From the pointwise converge of operators {f n } ∞ n=1 it follows that lim Since ρ is continuous [24], it follows that Since the limiting operator f is a contraction mapping, its fixed point x = f x is unique. Let x ∈ X . We then have = ρ(f n f n−1 · · · f 1 x, f n f · · · f n−1 x ) + ρ(f n x , f x ).
Since the sequence {f n } ∞ n=1 converges pointwise to f , we have for the second term, that lim Since f n is a ρ-contraction with a contraction factor d n ∈ (0, 1), we have for the first term that Let y n = ρ(x (n) , x ) and z n−1 = ρ(f n x , f x ). From the previous series of inequalities, we have shown that where, lim where d ∈ (0, 1). Using (60), along with y n ≥ 0 and z n ≥ 0 yields with the convention Since d k → d where 0 < d < 1, it follows that there exists N > 0 such that, for all k ≥ N , d k < η < 1. The first term in (61) can then be bounded as where Let k be fixed. The second term in (61) can be bounded as follows where Since z n → 0 as n → ∞, it follows that there existsz such that |z n | ≤z for all n ≥ 1. In particular, Taking limits of both sides of (61) as n → ∞ and k → ∞, and using the fact that, for 0 < x < 1, lim n→∞ nx n = 0, yields lim and thus lim n→∞ x (n) = x .

C.2 Convergence of the basedline SNQ2 Algorithm
In this section, we present the convergence proof of the baseline SNQ2. We denote the operator for each iteration of the while loop of Algorithm 1 as Γ β :Q →Q, such that In order to show the desired result, we need certain regularity assumptions on the operators to show that Γ β is a family of contraction mappings. Specifically, we assume that all the four operators are Lipschitz continuous with respect to their arguments. In our experiments, however, the algorithm converges even when some of the regularity assumptions are violated at some iteration steps. Assumption 1. There exist constants 6 d 1 , d 2 ≥ 0 such that for any admissible policies π and π and any Q-functions Q and Q , D(Γ 1 (Q, π), Γ 1 (Q , π)) ≤ d 1 D(Q, Q ), (68) D(Γ 1 (Q, π), Γ 1 (Q, π )) ≤ d 2 W(π, π ). (69) Assumption 2. For each β, there exist constants d 3 , d 4 ≥ 0 such that, for every admissible policies π and π and every soft Q-functions Q and Q , Assumption 3. There exists a constant d 5 ≥ 0 such that, for every Q-functions Q and Q , Assumption 4. For each β, there exist constants d 6 , d 7 ≥ 0 such that, for every admissible policies π and π and every soft Q-functions Q KL and Q KL , Assumption 5. The Lipschitz constants d i i = 1, . . . , 7 of the operators In the rest of this section, we prove the following convergence theorem regarding the baseline SNQ2 algorithm in the cMDP setting. Theorem 13. Under Assumption 5, the baseline SNQ2 Algorithm in the cMDP setting converges to the Nash Qfunction.
The roadmap for the proof is as follows: We first show that Γ β is a family of contraction mappings under certain assumptions. We use this result to construct the limiting operator of Γ β when β approaches zero, and show that the limiting operator corresponds to a standard Minimax update operator [17]. We finally apply Theorem 12 and show that the algorithm converges to the same Q-function as the Shapley's method (see Section 3.1 of the main text), which uses the standard Minimax update operator.
Next, we present the following theorem that provides sufficient conditions for Γ β to be a family of contraction mappings. Theorem 14. Under Assumption 5, the operator Γ β is a family ofD-contraction mappings with contraction factor d, where d is given in (75).
Proof. Let β be fixed. For any two concatenated Q-functionsQ,Q , one has For the first term in (76), we have For the second term in (76), we have Using the definition (75), we have Since, by assumption d < 1, it follows that Γ β is a family of contraction mappings.
We now construct the limiting operator Γ 0 = lim β→0 + Γ β , where β is the scalar parameter that parameterizes the trajectory of (β pl , β op ) approaching (0,0); see, for instance (50). In the sequel, we use β t to denote the inverse temperatures used at iteration t, such that lim t→∞ β t = 0 with β t > 0. Lemma 15. Consider a sequence of inverse temperature parameterized by {β t } ∞ t=1 with β t > 0, such that lim t→∞ β t = 0. Then, for every Q-function Q ∈ Q and admissible policy pair π ∈ Π, Proof. This is a direct consequence of Lemma 11.
Lemma 16. Consider a sequence of inverse temperature parameterized by {β t } ∞ t=1 with β t > 0, such that lim t→∞ β t = 0. Then, for every Q-function Q ∈ Q and every prior pair ρ ∈ Π, the soft update operator Γ β 2 converges pointwise to the standard update operator Γ 1 . That is, The step from (80) to (81) utilized the result from Lemma 11.
Theorem 17. Consider a sequence of inverse temperature parameterized by {β t } ∞ t=1 with β t > 0, such that lim t→∞ β t = 0. Then, Furthermore, Γ 0 is a strict contraction mapping with contraction factor d defined in (75), and has [Q Nash , Q Nash ] T as its fixed point, where Q Nash satisfies Q Nash = Γ 1 (Q Nash , Γ Nash Q Nash ).
The step in (84) is a result of the Lipschitz continuity of Γ 1 in Π assumed in Assumption 1, and the step in (85) is a result of Lemma 15.
Since, for all β, Γ β is a contraction mapping with a contraction factor d, by the first result in Theorem 12, the limiting operator Γ 0 as β → 0 + is also a contraction mapping with contraction factor d. Thus, the point [Q Nash , Q Nash ] T is the unique fixed point of Γ 0 .
We now put the pieces together and prove the convergence of the baseline SNQ2 as in Theorem 13.
Proof. (of Theorem 10) In Theorem 14, we have shown in that under Assumption 5, the operators Γ βt form a family of contraction mappings. In Theorem 17, we have shown that with a sequence {β t } ∞ t=1 approaches 0, the operator Γ βt converges pointwise to Γ 0 , which is a contraction mapping with [Q Nash , Q Nash ] T as its unique fixed point. Then, by Theorem 12, it follows that by sequentially applying Γ βt , the concatenated Q-function will converge to [Q Nash , Q Nash ] T . By Shapley's Theorem [17], the fixed point Q Nash corresponds to the Q-function at the Nash equilibrium of the zerosum stochastic game. Thus, the algorithm converges to a Nash equilibrium.

C.3 Convergence of the standard SNQ2 Algorithm
We extend the convergence proof on the baseline SNQ2 to the standard SNQ2, which updates the Nash policies every M Q-function updates. Assumption 6. Let the Lipschitz constants d i i = 1, . . . , 7 of the operators Γ 1 , Γ β 2 , Γ Nash , Γ β KL satisfy where d in = max{d 1 , d 2 d 7 + d 3 } and M is the number of inner iterations.
Theorem 18. Under Assumption 6, the standard SNQ2 Algorithm converges to the Nash Q-function.
Proof. Similarly to the proof of Theorem 13, we first show that the operation within the while loop in Algorithm 5 is a contraction mapping and then show the pointwise convergence and apply Theorem 12.