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

1 Introduction

Stochastic Games (SG) [Owen, 1982] is a widely adopted framework to extend reinforcement learning [Sutton and Barto, 1998] to multiple-agent scenarios. The resulting multiagent reinforcement learning (MARL) framework assumes a group of autonomous agents that choose actions independently and interact with each other to reach an equilibrium [Busoniu et al., 2008]. When all agents are rational, the most natural solution concept is the one of a Nash Equilibrium (NE) [Nash, 1951]. 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 [Matignon et al., 2012].

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 [Littman, 1994] and Nash-Q [Hu and Wellman, 2003]. 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 Qfunction 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.

* Equal contribution.

Other popular approaches that extend single-agent RL methods [Bertsekas and Tsitsiklis, 1996] to multi-agent scenarios include: simplifying the interactions [Foerster et al., 2018b; Bowling and Veloso, 2001; Littman, 2001], or introducing extra mechanisms in the game [Lowe et al., 2017; Li et al., 2019; Foerster et al., 2018a]. 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 [Fox et al., 2016] provide an efficient way to approximate Nash policies. Specifically, the two-agent Soft-Q algorithm [Grau-Moya et al., 2018] 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 Q2 -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 approximation of the Nash policies to update the standard Q-value; the Nash policies from the standard Q-function are computed periodically to update the priors that guide the soft policies (see Figure 1). Consequently, SNQ2L reduces the frequency of using the expensive Minimax operator, and thus expedites convergence to the NE. Since the balance between the prior update frequency and computational efficiency plays a critical role in the performance of the SNQ2L algorithm, we also introduce a dynamic schedule scheme that adaptively changes the prior update frequency. The proposed algorithm has the potential of transferring previous experiences to new environments by incorporating a prior to "warm start" the learning process.

1 SNQ2 refers to the non-learning version of the algorithm, which has access to the game dynamics.

Contributions. The contributions of this paper can be summarized as: (1) we propose a new algorithm for multi-agent games and prove the convergence of the proposed algorithm to a NE; (2) we demonstrate a major speed-up in convergence to a NE over existing algorithms; (3) we provide a dynamic schedule scheme of hyper-parameters to further expedite convergence; and (4) we demonstrate the ability of the algorithm to transfer previous experience to a new environment.

2 Background

Two-agent Zero-sum Stochastic Games. In two-agent stochastic games, two agents, henceforth referred to as the Player (pl) and the Opponent (op), respectively, interact in the same stochastic environment. In this paper we are interested, in particular, in zero-sum games where one of the agent's gain is the other agent's loss [Filar and Vrieze, 2012]. A zero-sum stochastic game G is formalized by the tuple G = 〈S,Apl ,Aop , T ,R, γ〉, where S denotes a finite state space, and Apl and Aop are the finite action spaces. To choose actions, the Player uses a (Markovian) policy πpl : S×Apl → [0, 1] and the Opponent uses πop : S×Aop → [0, 1], which together produce the next state according to the state transition function T : S × S ×Apl ×Aop → [0, 1]. As a consequence of simultaneously taking these actions, the agents receive a reward R : S × Apl × Aop → [Rmin,Rmax]. The constant γ ∈ (0, 1) is the discount factor. For zero-sum games, the Player seeks to maximize the total expected reward, whereas the Opponent seeks to minimize it. We denote the value at each state induced by the policy pair π = (πpl , πop ) as V π (s) = Eπ [∑∞t=0 γ tR(st, apl t , aop t )|s0 = s]. We denote by Π the set of all admissible policy pairs.

Nash Equilibrium. Operating at a Nash equilibrium, no agent can gain by unilaterally deviating from her policy. Formally, at a NE (πpl⋆ , πop⋆ ), at each state s ∈ S satisfies

for all admissible policies πpl , πop . Even though multiple Nash equilibria could exist in a zero-sum SG, the minimax (optimal) value at a NE is unique and can be computed [Von Neumann et al., 2007] via V ∗ (s) = maxπpl minπop V πpl ,πop (s) = minπop maxπpl V πpl ,πop (s).

3 Sequential Policy Approximations

The SNQ2L algorithm uses sequential policy approximations to relieve the computational burden seen in the Minimax-Q algorithm. In this section, we introduce the baseline SNQ2 algorithm in a competitive MDP (cMDP) setting. That is, we assume the game G is known. Later on, we will extend the algorithm for RL problems where G is only partially known. The proposed algorithm uses entropy-regularized soft policies to approximate the Nash equilibrium at each iteration. We prove the convergence of such algorithm to a NE in the Supplementary material. In the process, we define four operators that are useful in presenting the proposed algorithm.

3.1 Shapley's Method

Shapley's method [Filar and Vrieze, 2012] is an iterative algorithm commonly used to solve the Nash equilibrium of a zero-sum stochastic game 2 . Each iteration of the algorithm consists of two operations.

Step 1. Compute the Nash policies at each state given the Q-function estimate at the current iteration t, by solving a linear program [Filar and Vrieze, 2012]. For example, the maximizing Player has the following optimization problem,

where πpl (s) is the policy in vector form and Qt(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

Step 2. Given a policy pair π, update the Q-function via

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 [Filar and Vrieze, 2012] 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.

2 Minimax-Q is an asynchronous learning version of Shapley's method.

3.2 Entropy-Regularized Policy Approximation

Entropy-regularized policy approximation [Fox et al., 2016] 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 twoagent Soft-Q algorithm [Grau-Moya et al., 2018]. 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

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 VKL(s; πpl , πop ). It has been shown in [GrauMoya et al., 2018] that the optimal solution can be found through an iterative algorithm.

Step 1. With the current soft Q-function QKL,t, construct the soft optimal policy for the Player through the closed-form solution

where Z pl (s) is the normalization factor and Qpl 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

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 Γβ2 : Q×Π→Q as

Note that, due to the fixed regularization, the two-agent SoftQ algorithm does not converge to a NE in general.

Algorithm 1: Baseline SNQ2 in the cMDP Settings

• 1 Inputs: Game tuple G = 〈S,Apl ,Aop , T ,R, γ〉; 2 Set Q(s, apl , aop ) =QKL(s, apl , aop ) = 0; 3 Set βpl and βop to some large values; 4 while Q and QKL not converged do 5 Update Nash policies: πNash ←ΓNash(Q); 6 Update soft optimal policies: πKL ←ΓβKL (QKL, πNash); 7 Update Q-function: Q ←Γ1(Q, πKL); 8 Update soft Q-function: QKL ←Γβ2 (QKL, πNash); 9 Q←Q , QKL ←QKL ; 10 Reduce inverse temperature β 11 end
• 12 return πNash and Q(s, apl , aop ).

3.3 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 twoagent 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 B.

Theorem 2. Let (X, ρ) be a complete metric space, let fn : X → X be a family of contraction mappings, such that, for all n = 1, 2, . . . there exists dn ∈ (0, 1), such that ρ(fnx, fny) ≤ dn ρ(x, y) for all x, y ∈ X. Assume that limn→∞dn = d ∈ (0, 1). Let x ∈ X, and let x(n) = fn · · · f1x be the result of sequentially applying the operators f1, . . . , fn to x. If the sequence of operators {fn}∞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, limn→∞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 the Appendix. 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.

4 Two-Agent Soft Nash Q2 -Learning

In this section, we present the two-agent Soft Nash Q2 - 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 QKL.

Here, t is the learning step, and VKL,t(st+1) is computed as in (9) using the current QKL,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 Vt(st+1), SNQ2L uses either soft policies or Nash policies. We summarize SNQ2L with dynamic schedule in Algorithm 2.

4.1 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 ∆M0 and the default decay rate of the inverse

Algorithm 2: SNQ2-Learning Algorithm

temperature λ ∈ (0, 1) are given initially as

where α0 is the initial learning rate and Tmax is the maximum length of a learning episode; β0 and βend are the initial and estimated final magnitude for both βop and βpl , and Nupdates is the estimated number of prior updates. This value of ∆M0 allows the algorithm to properly explore the state-action pairs so that the first prior update is performed with an informed Qfunction. In our numerical experiments we found that β0 = 20, βend = 0.1 and Nupdates = 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.

4.2 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 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

Algorithm 3: Dynamic Schedule for M and β

• 1 Inputs: old and new priors ρ, ρnew; old prior update length ∆M; old inverse temperatures β; current Q; 2 Compute Vold(s) = [ρpl (s)]T Q(s)ρop (s) and Vnew(s) = ρpl new(s)T Q(s)ρop new(s), for all s; 3 Compute RelativeDifference(s) = |Vnew(s) - Vold(s)|/|Vnew(s)|; 4 Count the number of states n, where RelativeDifference(s) < δ; 5 if n/|S| ≥ Threshold then 6 ∆M =min{∆M/σ,∆Mmax}, βnew = max{λ βold, βmin}; 7 else 8 ∆M =max{σ∆M,∆Mmin}, βnew = βold; 9 end 10 return ∆M, βnew.

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.

5 Numerical Experiments

To evaluate the performance of the proposed algorithm, we tested and compared SNQ2L with four existing algorithms (Minimax-Q [Littman, 1994], Two-agent Soft-Q [Grau-Moya et al., 2018], WoLF-PHC [Bowling and Veloso, 2001], Single-Q [Tan, 1993]) for three zero-sum game environments: a Soccer game as in [Littman, 1994], a two-agent Pursuit-Evasion Game (PEG) [Guan et al., 2020] and a sequential Rock-Paper-Scissor game (sRPS).

5.1 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 VNash solved exactly via Shapley's method; (b) the learnt value VL; (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 [Littman, 1994; Lagoudakis and Parr, 2002], since any deviation from the NE could be exploited by either agent in our criteria.

5.2 The Game Environments

Pursuit-Evasion. The pursuit-evasion game (PEG) is played on three grids of different sizes (4×4, 6×6 and 8×8).

3 Implemented in a Python environment with AMD Ryzen 1920x. Matrix games at each state are solved via Scipy's linprog.

The 8×8 grid is shown in Figure 2. In a PEG, two agents simultaneously choose one of four directions on each turn. In the default setting, an agent has a 60% success rate of moving to its intended cell and a 40% chance of landing in the cell to the left of the intended direction. In such setting, a deterministic policy cannot be a Nash policy.

Soccer. The soccer game [Littman, 1994] is played on a 4×5 grid as in Figure 2. 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 into the goal (left for A and right for B), that agent scores and the game restarts at a random state. When an agent executes an action that takes it to the cell occupied by the other agent, possession of the ball goes to the stationary agent. Littman argued that the Nash policies must be stochastic.

Sequential Rock-Paper-Scissor. In a sequential RockPaper-Scissor game (sRPS), two agents play the RPS game repeatedly. The sRPS game ends when one of the agents wins four consecutive RPS games. The Nash policies of sPRS at each state are uniform for both agents.

5.3 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 schedule (SNQ2LFS) 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 3.

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 uniformNE, 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

4 For sRPS, the default prior is randomly generated, as uniform policies are the Nash policy for this game.

(a) Performance at convergence

(c) Performance at cutoff

Figure 4: Convergence trends of different algorithms in 4×4 PEG.

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

The time-wise convergence trends in Figure 4 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 MinimaxQ, albeit with significantly reduced computation time. This shows that our adaptive entropy-regularized policy approximation approach is both accurate and efficient.

5.4 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 4(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 3(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 4(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.

5.5 Effectiveness of Dynamic Schedule

In Figure 4(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 4. In Figure 5, 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.

6 Conclusions and FutureWork

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.