Autonomous Navigation in Search and Rescue Simulated Environment using Deep Reinforcement Learning

Copyright © BAJECE ISSN: 2147-284X http://dergipark.gov.tr/bajece Abstract— Human assisted search and rescue (SAR) robots are increasingly being used in zones of natural disasters, industrial accidents, and civil wars. Due to complex terrains, obstacles, and uncertainties in time availability, there is a need for these robots to have a certain level of autonomy to act independently for approaching certain SAR tasks. One of these tasks is autonomous navigation. Previous approaches to develop autonomous or semiautonomous SAR navigating robots use heuristics-based methods. These algorithms, however, require environment-related prior knowledge and enough sensing capabilities, which are hard to maintain due to restrictions of size and weight in highly unstructured environments such as collapsed buildings. This study approaches the problem of autonomous navigation using a modified version of the Deep Q-Network algorithm. Unlike the classical usage of the entire game screen images to train the agent, our approach uses only the images captured by the agent's lowresolution camera to train the agent for navigating through an arena avoiding obstacles and to reach a victim. This approach is a much more relevant way of decision making in complex, uncertain contexts; since in real-world SAR scenarios, it is almost impossible to have the area's full information to be used by SAR teams. We simulated a SAR scenario, which consists of an arena full of randomly generated obstacles, a victim, and an autonomous SAR robot. The simulation results show that the agent was able to reach the victim in 56% of the evaluation episodes after 400 episodes of training.

I. INTRODUCTION
Every year, around 60.000 people die worldwide in natural disasters. The majority of the deaths are caused by building collapse in earthquakes [1]. Only a small fraction of the victims of urban disasters might survive. Consider from [2,3] that 80% of survivors of urban disasters are surface victims, i.e., the people lying on the surface of the rubble or readily visible. However, only 20% of survivors of urban disasters come from the interior of the rubble, yet the interior is often where the majority of victims are located. The complexity of the collapses and the need for a fast response after the disaster requires multiple tasks to be done simultaneously. One approach to solve this problem is the use of robots that have a variety of capabilities such as unmanned ground vehicles (UGVs) and unmanned aerial vehicles (UAVs) to assess human search and rescue experts. In other words, the number of human experts can be limited and does not serve the need for controlling the robots along with fulfilling the other critic tasks that require human interference and moral understanding. Hence, there is a need for supplying these robots with a certain level of autonomy to be able to navigate through a SAR area and thus provide some tasks without the need for human control. In [4], Murphy et al. describe the tasks that can be addressed. Those tasks include (a) reaching small and dangerous places (voids) that humans and dogs cannot reach, (b) exploring the interior and exterior of the hot zone and extending wireless communication ranges.
Navigation is one of the fundamental tasks of mobile robots. The algorithms used to approach this task are divided into two sets [5]: • Greedy heuristics-based algorithms that operate using a map, which needs to be provided or extracted from the environment. After generating such a map, the central system performs the task of path planning, which is finding the optimal or suboptimal path to reach the target. Then the robots perform the navigation through the specified path. Autonomous mobile robots that use these techniques need to localize themselves within the generated map at the start of the planned trajectory, and then monitor their motion along the path using sensors (e.g., wheel encoders and inertial sensors) which are hard to be maintained on board of a small mobile robot navigating through small voids within rubbles. • Algorithms that operate without the use of maps (e.g., DistBug); These algorithms are often used if a path has to be traveled only once and therefore does not necessarily have to be optimal. Although the Bug family algorithms use limited sensors and computation capabilities, they tend to rely on perfect position estimations. In [6], McGuire et al. concluded that the Bug algorithms performance is sensitive to sensor-related noise, which makes them hard to implement in real-world uncertain noisy cotexts.
In [7], the authors studied different search methods based on greedy heuristics, and partially observable Markov Decision Process (POMDP) to design the autonomous control of UAVs to act in search and rescue contexts. Their evaluation results showed the great potential of POMDP in SAR scenarios; they also acknowledged that using these methods requires a high computation power as the cost grows exponentially (i.e., the curse of dimensionality) and that existed algorithms were not sufficient yet to tackle real-world problems. With the rise of deep learning and the expanding computational power, researchers have been able to come up with algorithms that can be used to tackle the curse of dimensionality more efficiently and solve problems that were not intractable in the past, such as playing Atari games at a superhuman level [8] and defeating a 9-dan Go player [9].
The main purpose of this study is to approach the problem of autonomous navigation using a modified version of DQN by relying only on the agent's camera without the use of any environment-related prior knowledge or any info gathered from another source (e.g., human experts, other robots, maps). This decentralized approach using only the agent's limited visionbased capabilities is a relevant strategy in deep voids where wireless connections might be hard to maintain, and also in any other situation where no enough outside information is available in the process of decision making. The DQN algorithm modified and used in this work is a valid method of solving real-world problems that can be interpreted as a POMDP.
The rest of the paper has the following structure. Section II gives an overview of related works. Section III describes the theoretical foundations of the utilized learning algorithms. Section IV presents the simulation setup and evaluation methodology. Section V presents the results and discussion. Finally, Section VI outlines the paper along with future directions.

II. RELATED WORKS
One of the applications of autonomous navigation is creating 3D visualizations of buildings and large-scale construction sites using scanning technologies. The scanning process has been often carried out using scanners handled by people [10] or scanners on board of vehicles controlled by people [11]. In [12], Kim et al. assisted the scanning process with UAVs that generated an initial 3D map of the area, then based on this map, the optimal scanning locations are estimated, and the optimal navigation path is determined. After that, a robot equipped with a laser scanning system is used to follow the path and obtain high-resolution scans in the estimated locations. Although such techniques are powerful in navigating through large construction sites, they cannot be used to assess small UGVs navigating through small-scale indoor environments. These robots must perform navigation without any outside assessments due to the limitation of wireless sensing technologies.
The problem of autonomous navigation in search and rescue contexts has been approached previously using heuristics-based methods. A heuristic function ranks a set of options available at one point and decides which one to choose according to the ranking. These approaches require situation related prior knowledge and a wide range of sensing abilities. In the EU funded project ICARUS [13], several robots with different structures and capabilities have been designed to assess SAR experts. Small Unmanned Ground Vehicles (UGVs) used to navigate through narrow voids were supplemented with a very limited level of autonomy. This is caused by the use of heuristic algorithms that require a massive amount of sensors and power, which cannot be added to the vehicles due to the restrictions of size and weight in highly unstructured environments, such as collapsed buildings. A similar approach has been carried out in the SHERPA project [14] in which the goal was to develop a mix of ground and aerial robots to support SAR teams in realworld hostile environments.
DQN was implemented in [15] to support a UAV with the ability to navigate independently towards a specified goal in a simulated environment. They evaluated their work by comparing the success rate, and the average steps undertook by the trained agent and a random decision-making agent. This research resulted in an 8% success rate for the trained agent compared to a 5% success rate for the random-action taking agent. Although the algorithm showed some success as the trained agent outperformed the random agent in terms of success rate, it is clear that it can be further developed.
This study approaches autonomous navigation using a modified version of the DQN algorithm relying only on the agent's camera. Unlike the previous methods, this approach does not require a map to be generated or any extra sensors to monitor the agent's motion. While the recent implementation of DQN in autonomous navigation [15] used the same proposed CNN, the CNN (convolutional neural network) being used in this work for training the agent to make decisions based on the captured images has been designed with simplicity in mind to suit the simulated scenario.

A. Reinforcement Learning
RL is the machine learning paradigm concerned with training agents to act autonomously to reach certain goals in an environment. A typical reinforcement learning scenario consists of the following components: an agent (the decisionmaker), an environment in which its state changes according to the agent's actions. As the agent explores the environment, it receives a reward for each action it makes. Hence by trial and error, it learns to maximize this reward.
Formally an RL scenario is modeled as a Markov Decision Process (MDP) which consists of a tuple ( , , , , ) where is the set of states, is the set of actions, (alternatively ( ): the set of actions that can be taken at state ); R(s) is the reward function, it returns the immediate reward; ( , , ′ ) ~ ( ′ | , ) is the probability that taking action will change the environment state from to ′ ; and finally, ϵ [0,1] is the discount factor, which is how much we value future reward over the immediate one.
The main problem of an MDP is to find the optimal policy * . A policy ( ) is a function that specifies the action that should be taken at a certain state. Thus the optimal policy * is the policy that maximizes the expected long term reward (i.e., the reward from all states): probability that taking action will change the environment state from to ′ ; and finally, ϵ [0,1] is the discount factor, which is how much we value future reward over the immediate one.
A POMDP scenario can be described as follows: at each time frame the environment is in some state ∈ , the agent takes action ∈ which changes the environment state from to ′ according to the transaction probability T, after a step time, the agent receives an observation from the environment state ′ . The observation depends on the current state ′ and the previous action according to the probability Ω( , ′ , ). The goal of the agent is to find the optimal policy π* that maximizes the expected long-term reward. As the states in POMDP are not fully observable, the agents only receive partial information about the environment. This generalization is more realistic than MDP, and it can describe a variety of real-world problems. Hence it is an appropriate framework to describe the simulated scenario.

B. Q-Learning
Reinforcement learning methods fall into two categories; the policy-based and value-based methods. The policy-based methods aim at finding the optimal policy π* by starting with a parameterized policy and updating its parameters using gradient-based or gradient-free methods, on the other hand, the value-based methods use a value function that determines the expected long term reward of executing an action at a particular state, and hence providing which action to undertake. One of the most well-known value-based methods is Q-learning. It can find the optimal policy in finite stationary and fully-observable environments with discrete actions . The algorithm starts by  initializing a table called the Q-table with arbitrary Q-values. A q-value is a value that corresponds to how well an action is at a specific state. Then at each state, an action a is being selected, and its corresponding Q-value is being calculated using the Qfunction: where Q(s, a) is the Q-value of executing an action at state , ∈ (0,1] is the learning rate, and r is the immediate reward. Although Q-learning can find the optimal policy in small finite environments, it performs poorly on non-stationary partially observable complex environments.

C. Deep Q-Network
With the rise of deep learning and particularly in [8], Mnih et al. introduced the Deep Q-Network algorithm (DQN), which gave birth to the field of deep reinforcement learning. DQN was the first algorithm to reach a superhuman performance in playing Atari games from pixels. Instead of using a table to track the Q-values, they used a convolutional neural network as a function approximator to predict Q-values from states. One of the problems the RL algorithms have when using artificial neural networks as function approximators is the problem of instability. The DQN algorithm uses two separate models to stabilize the learning; namely, the main model and the target model, the main model's weights get copied to the target model every c steps. The DQN also keeps a memory buffer termed Experience Reply to store the transactions. At every training step, the DQN uses the main model to predict the action to take, and then the agent executes the action and observes a new state together with the immediate reward. After adding the new transaction to the experience replay, it takes random samples from the experience reply and uses them as data to fit the main model by minimizing the mean-square error (MSE) between the main and target models. The training process is visualized in Fig. 1.

D. The ε-Greedy Policy
The ε-greedy policy is a method used to balance the exploration and exploitation done by the agent; that is deciding at a certain point whether it should take random actions to explore unexplored space, or whether it should use the trained model's action-value estimations to predict the best action. It keeps track of a parameter ε, which represents the probability of choosing a random action. Similar to the original DQN, in this work, ε starts at 1 and decreases linearly throughout the training until it reaches a fixed point.

IV. SIMULATION SETUP AND METHODOLOGY
The scenario was simulated using Webots [16], an opensource robot simulator widely used for educational and professional purposes. It includes a complete toolbox to design environments, robots, and simulation experiments. It can execute controllers written in compiled C/C++ and Java or interpreted python and Matlab languages. In this study, the agent controller was written in python to take advantage of the required libraries (i.e., Numby, Tensorflow, and Keras).
An e-puck robot was used for its motion simplicity. It has two motors, a left wheel motor and a right wheel one. It also has a color camera with a maximum resolution of 640x480, eight light sensors, and eight distance sensors. For this research, only the camera and the motors have been used.
At the beginning of the simulation, a square arena is created. The center of the arena is at the center of the coordination, and the objects can be placed within [-1, 1] and [-1, 1] at X and Z dimensions, respectively, whereas the Y dimension remains the same. At every episode, the agents and obstacles are placed randomly. The victim robot is randomly placed according to the uniform distribution at a position within the upper left part of the arena between [-1, -0.5] and [-1, -0.5] at X and Z dimensions, respectively. Similarly, the agent is placed randomly according to the uniform distribution at the downright part of the arena between [0.5, 1] and [0.5, 1] at X and Z dimensions, respectively. The obstacles (i.e., 20 boxes) are positioned randomly according to the normal distribution of 0 mean and standard deviation of 0.5. The objects are positioned in this manner to ensure that the obstacles will get in the agent's way. Fig. 2 shows a view of the arena at the beginning of an episode.
In this work, DQN has been modified to ensure more success in the simulated scenario. These modifications are as follows:  The CNN that has been used in the original DQN has performed poorly on the simulated scenario. The agent at an early level of the training starts to memorize one action regardless of the image fed into the network, and hence it rarely reaches the victim robot. Instead, in this work, a simpler CNN has been used. It showed much better results. Fig. 3 shows the architecture of the modified CNN, which is used to predict the best action to be executed according to the image fed.  The agent was trained for 400 training episodes executed in 8 identical parts; within each part, 50 episodes were executed. At each training part, the ε-greedy policy's ε starts from 1 and decays until it reaches 0.1 after 25 episodes, which is half of a training part, as illustrated in Fig. 4.
 While in the original DQN, a stack of 4 frames is being fed into the CNN as one observation, for simplicity, we use only one image. Fig. 5 shows an image captured by the agent during training.
 The use of a simple distance-dependent reward function: where is the distance between the agent and the victim at the previous step, and is the distance between the agent and the victim at the current step.

V. RESULTS AND DISCUSSION
Several evaluation methods were used to test the suitability of the original CNN architecture proposed in [8]. The original CNN was designed to learn generalizing the learning process over many distinct Atari games, while in our scenario, the agent has to learn to interact in one environment. In other words, due to the complexity of the model, the agent starts to memorize behaviors at a very early level, and thus at one point, it starts to take only one action regardless of the image captured. This resulted in a bad performance in terms of navigating towards the target. Fig. 6 illustrates the number of steps taken by the agent to reach the victim in a single episode by using the original CNN. If the agent does not reach the victim during the episode, the finishing step will be equal to the maximum number of steps used (i.e., 1000). This is due to the low ε value 0.1 which limits the agent exploration. The line shows that using the original approach the agent was only able to reach the victim before the episode 25 (i.e., the episode at which the randomness is minimized), which demonstrates clearly that the agent is not able to reach the victim when relying on the original complex CNN and hence performs poorly in the simulated environment. Using our modified CNN proposed in the methods section, the agent showed better results when evaluated in 1000 step epochs. Fig. 7 illustrates the number of steps taken by the agent to reach the victim in a single episode by using the modified CNN. If the trained agent does not reach the victim during the episode, the finishing step will be equal to the maximum number of steps used (i.e., 1000). The line shows that using the modified approach, the agent was able to reach the victim at most of the episodes, while also reaching the victim in less number of finishing steps on average after the episode 25. This, in turn, clearly demonstrates that the agent is able to reach the victim more efficiently relying only on the trained model using the modified CNN. The finishing step is going smaller along with the training.
Since the ε is decaying linearly, this shows that the agent is performing better when it predicts the actions based on the trained model. Table 1 shows the training results of the agent during the different parts of the training. Step Training Episode Modified CNN with limit step 1000 Using the methods proposed above, the agent was trained on an Intel Core (TM) i5-3230M CPU. Training 400 episodes lasted appr. 21 hours and 7 minutes. The training episodes were executed in 8 parts to ensure the stability of the simulation physics engine (i.e., after training for more than 50 epochs, the physics engine starts to produce some delay and the simulation info file stored in the RAM reaches its limits).
After the training, the agent's performance was evaluated using the same evaluation method used in [15]. The trained agent's success rate and the number of steps it took to finish the simulation were calculated and compared with a fully randomaction taken agent. Table 2 shows a comparison between the evaluation results of this work and the previous study.
While the random agent was not able to reach the victim even once, after 400 episodes of training, the agent was able to reach a 56% success rate in 40 evaluation episodes. That means that the e-puck robot was able to reach the victim in 56% of the evaluation episodes. Moreover, it was able to reach the victim in 21 steps at least in one episode, which is a great result giving the complexity of the environment. The poor performance of the random agent in our study shows the complexity of our simulated scenario when compared with the simulation scenario in [15]. Hence, this proves how well the trained agent performed.
Compared with the results proposed in [15], this work has reached significant improvements in terms of the difference between the results of the random agent and the trained one. This is due to the use of a simpler CNN that learns to navigate through obstacles contained in similar settings, instead of the use of the original CNN that generalize the learning over many Atari games. Another factor is the used version of the εgreedy policy; that is partitioning the training into parts with an ε that starts at each part from 1 and linearly decays until it reaches a 0.1. With this method, the agent has been able to explore the changing state of the environment across episodes more efficiently.

VI. CONCLUSION AND FUTURE WORK
This paper presented a SAR simulation scenario, in which an autonomous e-puck robot's main goal is to explore an area full of randomly generated obstacles and yet to learn to navigate through them to reach a certain victim without any use of environment-related prior knowledge. The scenario and the environment, in general, can be used to test the suitability and the efficiency of different deep reinforcement learning methods to solve autonomous SAR problems. A modified DQN algorithm was implemented using some new approaches. These approaches include (a) the use of modified CNN instead of the original one, a distance-dependent reward function, and agent's low-resolution camera images to train the agent; (b) feeding one frame to the CNN as an observation instead of a stack of four images; and finally (c) training the agent in 8 parts; at each part, the ε-greedy policy's ε is decaying linearly from one until it reaches 0.1 at the middle of the training part. Using these methods, our modified DQN has shown great results compared to previous work when evaluated using the same evaluation methods and metrics, reaching a success rate of 56% at an average step of 242.
Despite the work's success, a variety of future works can be conducted to increase efficiency and real-world interpretability. The scenario can be further developed to become more realistic; e.g., by placing a variety of obstacles, increasing the number of obstacles and victims. A more complex CNN can be designed to train the agent to navigate in the developed complex scenario. The reward function can be optimized to depend on other factors, such as the distance between the agent and the nearest Note: The success rate shows the percentage of the successful episodes, in which the agent successfully reaches the victim, whereas the minimum steps show the minimum step number at which the agent reached the victim.


extfieldsofstudy:
Computer Science
Engineering
Mathematics

text:
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.