Policy Optimization in Zero-Sum Markov Games: Fictitious Self-Play Provably Attains Nash Equilibria
Authors: Boyi Liu
Zhuoran Yang
Zhaoran Wang
Venue:  (2021)

Abstract: Fictitious Self-Play (FSP) has achieved significant empirical success in solving extensive-form games. 
However, from a theoretical perspective, it remains unknown whether FSP is guaranteed to converge to Nash equilibria in Markov games.
As an initial attempt, we propose an FSP algorithm for two-player zero-sum Markov games, dubbed as smooth FSP, where both agents adopt an entropy-regularized policy optimization method against each other. 
Smooth FSP builds upon a connection between smooth fictitious play and the policy optimization framework. Specifically, in each iteration, each player infers the policy of the opponent implicitly via policy evaluation and improves its current policy by taking the smoothed best-response via a proximal policy optimization (PPO) step. 
Moreover, to tame the non-stationarity caused by the opponent, we propose to incorporate entropy regularization in PPO for algorithmic stability. 
When both players adopt smooth FSP simultaneously, i.e., with self-play, we prove that the sequence of joint policies converges to a neighborhood of a Nash equilibrium at a sublinear $\tilde{O}(1/T)$ rate, where $T$ is the number of iterations. To our best knowledge, we establish the first finite-time convergence guarantee for FSP-type algorithms in zero-sum Markov games.

Under review as a conference paper at ICLR 2021
POLICY OPTIMIZATION IN ZERO-SUM MARKOV
GAMES: FICTITIOUS SELF-PLAY PROVABLY ATTAINS NASH EQUILIBRIA
Anonymous authors Paper under doublc-blind review
ABSTRACT
Fictitious Self-Play (FSP) has achieved significant empirical success in solving extensive-form games. However, from a theoretical perspective, it remains un- known whether FSP guaranteed to converge to Nash equilibria in Markov games. As an initial attempt, we propose an FSP algorithm for two- two-player zero-sum Markov games, dubbed as smooth FSP, where both agents adopt an entropy-regee regguaa-eegulriizedd pol- icy optimization method against each other. Smooth FSP builds upon connection between smooth fictitious play and the policy optimization framework. Specifically, in each iteration, each player infers the policy of the opponent implicitly via policy evaluation and improves its current policy by taking the smoothed best-response via proximal policy optimization (PPO) step. Moreover, to tame the non-stationarity caused by the opponent, we propose to incorporate entropy regularization in PPÒ for algorithmic stability. When both players adopt smooth FSP simultaneously, i.e., with self-play, in a class of games with Lipschitz continuous transition and reward, we prove that the sequence of joint policies converges to a neighborhood of Nash equilibrium a sublinear O(//T) rate, where T is the number of iterations. To our best knowledge, establish the first finite-time convergence guarantee for FSP-type algorithms zero-sum Markov games.
INTRODUCTION
Multi Multi-agent reinforcement learning (MARL) Bu al., 2008 Sutton Barto 2018) has achieved great empirical success, e.g., in playing the game of Go (Silver et al. 2016 (017) Dota 2 (Berner et al. 2019), and StarCraft (Vinyals et al. 2019), which are all driven by policy optimization algorithms which iteratively update the policies that are parameterized using deep neural networks. Empirically, the popularity of policy optimization algorithms for MARL is attributed to the observations that they usually converges faster than value-base based methods that iteratively update the value functions (Mnih) ct al. 2016 Donoghue et al. 2016).
Compared with their empirical success, the theoretical aspect of policy optimization algorithms in MARL setting (Littman 1994, Hu & Wellman 2003 Conitzer & Sandholm, 2007 Pérolat et al.
2016
Zhang al.] (018)) remains less understood. Although convergence guarantees for various
policy optimization algorithms have been established under the single-agent RL setting (Sutton et al.,
Konda & Tsitsiklis 2000 Kakade 20022] Agarwal al. 2019 Wang et al. 2019), extending those theoretical guarantees to arguably one of the simplest settings of MARL, two-player zero-sum Markov game, suffers from challenges in the following two aspects. First, in such Markov game, each agent interact with the opponent as well as the environment. Seen from the perspective of each agent, it belongs to an environment that altered by the actions of the opponent. As a result, due to the existence of an opponent, the policy optimization problem of each agent has a time-varying objective function, which in stark contrast with the value-based methods such as value-iteration Shapley (1953); Littman (1994), where there is a central controller which specifies the policies of both players. When the joint policy of both players are considered, the problem of solving the optimal value function corresponds to finding the fixed point of the Bellman operator, which is defined independently of the policy of the players. Second, when viewing the policy optimization in zero-sum Markov game as optimization problem for both players together, although we have
2000

---

Under review as a conference paper at ICLR 2021
fixed objective function, the problem is minimax optimization with non-convex conccoee objective. Even for classical optimization. such a kind of optimization problem remains less less understood (Cherukuni et al. (217 Rafique et al. [018 [aakkalakis & Panageas 2018 Mertikopoulos et al. 2018). It is observed that first-order methods such as gradient descent might fail to converge (Balduzzi et al. 2018 Mazumdar & Ratlifi 2018).
As an initial step to study policy optimization for MARL, we propose a novel policy optimization algorithm for any player of a multi-player Markov game, which is dubbed smooth fictitious self- play (FSP). Specifically, when a player adopts smooth FSP, in each iteration, it first solves a policy evaluation problem that estimates the value function associate with the current joint policy of all players. Then it update its own policy via an entropy regulop--egulrrizeed proximal policy optimization (PPO) Schulman et al. (2017) step, where the update direction is obtained from the estimated value function. This algorithm can be viewed as an extension of the fictitious play (FP) algorithm that is designed for normal-fore games (Von Neumann & Morgenstern 2007 Shapley) 1953) and extensive- games (Heinrich et al. 2015 Perolat et al. 2018) to Markov gamees...me.... FP is a general algorithmic framework for solving games where an agent first infer the policy of the opponents and then adopt policy that best respond to the inferred opponents. When viewing our algorithm a FP method, instead of estimating the policies of the opponents directly, the agent infers the opponent implicitly by estimating the value function. Besides, policy update corresponds smoothed best-response policy SSenson & Poor (2019) based on the inferred value function.
To examine the theoretical merits of the proposed algorithm, we focus on two-player zero-sum Markov games and let both players follow smooth FSP, i... with self-play. Moreover, we restrict to a class of Lipschitz games (Radanovic et al. 2019) where the impact of each player's policy change on the environment is Lipschitz continuous with respect to the magnitude of policy change. For such a Markov game, we tackle the challenge of non-stationarity by imposing entropy regularization which brings algorithmic stability. In addition, to establish convergence to Nash equilibrium, we explicitly characterize the geometry of the policy optimization problem from a functional perspective. Specifically, we prove that the objective function, as bivariate function of the two players' policies, despite being non-convex and non-concave, satisfies a one-point strong monotonicity condition (Facchinei & Pang 2007) at Nash equilibrium. Thanks to such benign geometry, prove that smooth FSP converges to a neighborhood of Nash equilibrium
sublinear O(ITT) rate, where i' the number of policy iterations and Ō hides logarithmic factors. Moreover, as a byproduct of our analysis, if any of the two players deviates from the proposed algorithm, it is shown the other player that follows smooth FSP exploits such deviation by finding the best-response policy at a same sublinear rate. Such Hannan consistency property exhibited in algorithm is related to Hennes et al. (2020), which focus on normal-for formal-form& games. Thus, our results also serve as a first step towards connecting regret between minimization in
games and Markov games.
Contribution. Our contribution is two-fold. First, we propose novel policy optimization algorithm for Markov games, which can be viewed as a generalization of FP. Second, when applied to class of two-player zero-sum Markov games satisfying Lipschitz regularity condition, our algorithm provably enjoys global convergence to a neighborhood of a Nash equilibrium at a sublinear rate. To the best of our knowledge, we propose the first provable FSP-type algorithm with finite time convergence guarantee for zero-sum Markov games.
Related Work. There is large body of literature on the value-based methods to zero-sum Markoy games (Lagoudakis & Parr 2012 Pérolat et al., 2016; Zhang et al.] 2018 Zou et al. 2019). More recently, Perolat et al. (2018) prove that actor-critic fictitious play asymptotically converges to the Nash equilibriu,, while our work provides finite time convergence guarantec to neighborhood of Nash equilibrium. In addition, Zhang et al. (2200) study the sample comlexity of planning algorithm in the model-based MARL settting as opposed to the model-free setting with function approximation in this paper.
Closely related to smooth FSP proposed in this paper, there is a line of work in best-response algorithms (Heinrich et al. 2013 Heinrich & Silver (016), which have also shown great empirical performances (Dudziak) 2006) Xiao et al. 2013] Kawamura al., (017)). However, they are only applicable to extensive- form games and not directly applicable to stochastic games. Also, our smooth FSP is related to Swenson & Poor (2019), which focus on the potential games. It does not enforce crttoy--rgullaizzttinn and only provides asymptotic convergence guarantee to a neighborhood of the
2

---

Under review as a conference paper at ICLR 2021
Nash equilibrium for smooth fictitious play in multi-player two-action potential games. Moreover, work also falls into the realm of regularizing and smoothing techniques in reinforcement learning (Dai et al. 2017: Geist et al., 2019 Shani et al. 2019 Cen al. 2020). which focus the single-agent setting.
2 BACKGROUND
In this section, we briefly introduce the general setting of reinforcement learning for two-player zero-sum Markov games.
Zero-Sum Markov Games. (S,A), , P.r,,)) 7). where S C IRd is a compact state space, A and AA² are finite action spaces of Player and Player 2, respectively, P x S x A x AA2 - [0. 1] is the Markov transition kernel, r: r:S% x A x A + [-1, 1] is the reward function of Player 1, which implies that the reward function of Player is -r, and 7 E (0,1) is the discount factor. Let r1 = r and r22 = -r be the reward functions of Player and Player respectively. For notational simplicity, throughout this paper, write Player -i as Player i's opponent, where E 21. In the rest of this paper, we omit é {1,2] where it is clear from the context. Also, we denote by Eg - the expectation over the trajectory induced by the policy pair [r'; π "]
We consider the two-player zero-sum Markov game
Given a policy X'ं A S + [0. 1] of Player -i, the performance of a policy N' : A'' S + [0
of Player is evaluated by its state value function (V,-function) V.,. - R, which is defined
as
8
V
(8) Ex
Σ
nt
re(Se, ag ar) (a)))
8u =
(2.1)
Correspondingly, the performance of policy n² A' x S - [0, of Player is evaluated by its
action-value function (Q.-function) Q7 -- :Sx A' x A- - IR, which is defined by the following Bellman equation,
+2 + of = We denote by M - (8) and (s, a',")aa,a=)) = (aa) s) n (a- s) Uzi.a -s) the station- ary state distribution and the stationary state-action distribution associated with the policy pair
V. . (s')]
[ respectively. Correspondingly, we denote by E.,.,--:l [-] and [. the expectations
"'s.a"a-">va,,__.. [.] and E,,,,, [.] respectively. Throughout this paper, denote by (;,)) the
inner product between vectors.
Let [m], m3) be Nash equilibrium of the two-player zero-sum Markow game which exists (Shapley 1953) and satisfies
[(T . S [ =2) < I [TT
for all policy pairs [x 7 Here we define the performance function as
J(T), m²) E,, [VT'* ,x² (s)],
(2.2)
where v² is the stationary distribution T...
Regularized Markov Games, Based on the definition of the two-player zero-sum Markov game (S,At, A², P)),7), we define its reguapereeullrrized counterpart (S,A7, A², P, A,, A2), where \1, A2 2 are the regularization parameters. Specifically, as the two-player general-sum Markov game with the reward function of Player replaced by its It -t S A x A-i + R, which is defined as n aata (s, at A log n (aa (s).
P. p.r.y, )1, is defined
ceguopy-regularrieed counterpart
(())
(2.3)
With slight abuse of notation, we write
r (s) Exi, |ri(s,,a', a'
()) (s) Ex,, 11o0"" "ss,a" = 2'. (1)= (s) A H-
3

---

Under review as a conference paper at ICLR 2021
as the reward function and the catropy-regularize state-reward function, respectively. Here H (-1s) = Ex'Es I (a') s) log ग (a' 8) is the Shannon entropy. For Player i, the entropy-
regularized state-value function VVio-function V(0 x
: S + R and the entropy regulaazee
action-value function (Q()ntunciion) V
: x A' A R defined as
V (6)
(s) -Epi,
(s oi (sc,
ar') so =
(2.4)
(8)
2 (s.a',a- ri(s, a a a0 + Bl |s, 1) (()
(s')), (s')),
(2.5)
respectively. By the definition of t in 2.3 we have that, for all policy pairs [xr;; ; and
E S,
E
a ")] s 11+ + A, log 1A4%
which, by 2.4 and 2.5 implies that, for all policy pairs | and (s A A-:
1+ A log (A")
(8)
(s)
<
ymnax
(i)
1-
(2.6)
2 x (8, a-aa)) 10] S 113) = + 7. (1 + X log (A'1)
(2.7)
3 FICTITIOUS SELF-PLAY FOR ZERO-SUM MARKOV GAMES
In this section, we introduce smooth fictitious self-play (FSP) for two-player zero-sum Markov games.
3.1 FSP: FROM MATRIX GAMES TO MARKOV GAMES
FSP is an algorithmic framework for finding the Nash equilibria of games. It consists of two building blocks: (I) inferring the opponent's policy by playing against each other, namely fictitious play, and (II) improving the two players' policies with symmetric updating rules, namely self-play. Specifically, Player best responds to a mixed policy of Player - which is weighted average of Player -i's historical policies. Here playing mixed policy .
. + (1 a) means that, the beginning of the game, the player chooses to play the policy π with probability a and play the policy - with probability 1 a.
FSP is originally developed for normal-form games (Von Neumann & Morgenstern 2007 Shapley 1953) and extensive-form games (Heinrich et al.] [0155] Heinrich & Silver 2016). In (entropy- regularized) two-player zero-sum matrix games, which are the special cases of (entropy-regulane two-player zero-sum Markov games with |S] and no state transition, mixing two policies π and π with probabilities a and - respectively, is equivalent to averaging the corresponding Qu-functions, i.e.,
Q p ++(1-0)xx =a Q . + +11 - a.) Q7 ,-
In other words, two-player zero-sum matrix game, Player i is equivalently best responding to a weighted average of the historical Qi-functions by taking the corresponding greedy action. To generalize FSP the two-player zero-sum Markov game (S,A', AA2 P,r,7), we propose to let Player i best respond to the following weighted average of the historical marginalized Q -fnccioss the [-th iteration,
Q (3,1,0)),a')) a²) = =(1 - ax. De (s, a²) + +a. " (s,
(3.1)
where (() [0, 1] is the mixing rate. Here the marginalized Q function क (s, is defined as
(ssaa' = E.- (2 " (s,a¹,a )]
(3.2)
4

---

Under review as a conference paper at ICLR 2021
Recursively applying the symmetric updating rule in (3.1) obtain
p (s. = - On
II (1 (1-00)))))
==0
R=++1
which is the weighted average of the historical marginalized Qoyy-funetioss Here we use the convention that I -Q (R)( = 1. Correspondingly. (3.1) induces the following symmetric policy updating rule,
h.bsst (a' (8) = 1(a argmax (egmax(Qr41.aa) (1+1,008, E"EAt
(3.3)
where the obtained policy #+11 ing greedy action.
b.best best responds to Q2+1,00 defined (31
by taking the correspond-
3.2
MARKOV GAMES: FROM FSP TO SMOOTH FSP
FSP is only known to converge asymptotically even in two-player zero-sum matrix games (Robinson) Instead, consider smooth FSP, which uses the following smoothed best-response,
1951
1 ()) oc exp(Ee+1,0)s,,
(3.4)
Here the ideal energy function (0) (8, at) = Ke+1.(1)) Q Qe+ a²) is proportional to the weighted average of the historical marginalized Q()) -functioo defined in (3.1 with the normalization parameter Ke)1,(() > O.
In the sequel, we simplify the symmetric updating rules in 3.. and (.4 Let the stepsizes be
(1) Kx+1,(0) (z1(1)= d',60 (4411(0/KK.00)) (1 (r,()))
(3.5)
Recall that Dta which is the marginalized Qtanntinn,,,, is defined (3.2). Corresponding to 3.I we have the following symmetric updating rule for the energy functions,
(8 a') d'_,o) E,,(0) (s, + a4 2 (s,a²),
(3.6)
which gives the following symmetric policy updating rule equivalent to
33.
T (a' |s x (T/((a) s)) oh.o exp(ar,() 2 (s,a')}-
We call 1,)) the ideal energy function, since it is directly obtained from the symmetric updating rule 3.3). which operates in the functional space given the marginalized Q -fnnttnnss
3.3 IMPLEMENTING SMOOTH FSP
In practice, it remains to approximate the ideal energy function E4+1.(0) within a parameterized function class, which is further used to parameterize the policy T/+1- For notational simplicity, we concatenate the parameters of the policies π(41 and म,.1 into single parameter 0(+1 θ, which gives the parameterized policy pair (m². ,,,") Meanwhile, we need estimate the marginalized Q(1) function (
Té. .T. (s, a²) defined in (3.2 In practice, the parameterization of the energy function
and the marginalized N being the size of the neural network. To implement smooth FSP, given 0, E O, we find the best parameter 0,+1 E θ that minimizes the mean squared error (MSE),
(feyeffnttion are set to be neural networks, which means that θ = RN with
Egg
Σ
(E)... at) (+,1))0(,,)))))))
(3.7)
(E(1,2)
where (s, dr, (s,,() a1,() Q Th (s,a*)
(3.8)
is the estimated ideal energy function. Here Q .. (s, a²) is the estimator of the marginalized Q(1) function ( b via policy evaluation (Sutoon et al. 2000). For notational simplicity, in (377 and the rest of the paper,
(s, a²). Such estimator is obtained based on the data generated by smooth FSP
5

---

Under review as a conference paper at ICLR 2021
write the stationary state-action distribution of * associated with the policy pair (mb Too"l as ot and Mt, respectively.
and the stationary state distribution/ "6
We define the bounded function class FR with the radius R > as FR {f ll I R}. Algorithm gives the implementation of smooth FSP for two-player zero-sum Markov games.
Algorithm Smooth FSP for Two-Player Zero-Sum Markov Games
1: Require Two-player zero-sum Markov game (S,A', ,A, P.r,7) 7) number of iterations T, reg- ularization parameters (Ai (1.2), truncation parameters (Q()) (4) (1,(1,2), and stepsizes
gmax) )
(o1,(0) (9, -..2T-
2: Initialize the energy function (1) (s, ( (1,2))
3: For /. = 0, ...,, 7 1 and E { do
4: Set the policy mb. (-1s) x exp(Eo..0)s,.))..
Te (8,a²) E Fouu using the data
5: Generate the marginalized Q -functinn estimator (()
generated by fictitious play with the policy pair (=b, To,1
6: Update the estimated ideal energy function
Q Te (s,
(1,1,00),,a) x (0)00) (s., a') + ac,())
7:
Minimize
(3.7 to obtain the energy function (1) Fegue
8: End
9: Output:
MAIN RESULTS
In this section, we establish the convergence of smooth FSP for two-player zero-sum Markov games by casting regularized proximal policy optimization (PPO).
4.1 SMOOTH FSP AS REGULARIZED PPO
In the sequel, we connect the energy function update in to the estimated ideal energy function updates E(+1,00 in 3.8 update as
3.8
with regularized PPO. Corresponding define the estimated ideal policy
(.1(+ss) x exp(Er+..0)ss
(4.1)
We have the following proposition states the equivalence between smooth FSP and regularized PPO.
Proposition 4.1. For all < 5T - 1, let the stepsizes an,(1) and a'((0) of Algorithm I satisfy
A
(),()) ar,))) (/))))))))))))))))))))))))))))) 0.
At the (-th iteration of Algorithm PPO subproblem,
D the policy update in (4.1) is equivalent to solving the regularized
#41 argmax E,, (1,(0) 10) 1h (s. ) -a log né. (-1s), x (+1 T.. (-1s)) (4.2) m²
-KT T (- (115))
Here Q To. (s, )²) is the estimator of the marginalized Qto ffunction : (s,a*)
Proof. See Appendix A for detailed proof.

---

Under review as a conference paper at ICLR 2021
Proposition 4.1 implies that smooth FSP proximally improves the policy xO based on the regularized performance function,
[i) E.- (s)].
(4.3)
Proposition C.1 implies that, the smaller the regularization parameter X; is, the closer the regularized performance function J(s) is to the performance function J. In the rest of the paper, we show that, with proper choice of X smooth FSP converges to neighborhood of a Nash equilibrium [T]] m at sublinear rate of (1//T).
4.2 CONVERGENCE TO NASH EQUILIBRIUM
Let P(s; = = x² 8o ~ v) be the probability that the trajectory, which is generated by the policy pair [ with the initial state distribution so reaches the state at the timestep t. Correspondingly, let
P x ((s) - (1-
Σ
P(st =
~))
(4.4)
(=0
be the visitation measure of b with the initial state distribution 8o ~ u. Also, for notational simplicity, define
20
P U,T"
= (1- (1 Σ 7t H..((444 s| [|, n (So, ob. o v=)
(4.5)
the visitation measure of the policy pair [-'; with the initial state-action distribution " -- We lay out the following assumption on the concentrability coefficient. With slight abuse of notation, we write and T" in the subscripts as s and a', respectively, when they are point masses.
Assumption 4.2 (Concentrability Coefficient). We assume that for the two-player zero-sum Markov game (S, A A2, P,,,,, there exists >> such that
Ev- [dp a- 8,0", //===" 1/2
SC
for all s S, a² E A', and n' = ni. generated by the policy update in Line 4 of Algorithm "x"'"" x-,1 /dv" is the Radon-Nikodym derivative, where p= e,0
Here
dp"
"' is defined 4.5
8,a5,m.
The notion of concentrability coefficient in Assumption 4.2 is commonly used in the literature (Munos) & Szepesvári
2008 Antos et al. 2008 Farahmand et al. 2010 Tosatto et al. 2017 Yang et al.
2019).
For all policy pairs (r'; π "I we define the Markov state transition kernel as
p :n'"""" (-1s) Bx
[P( 1, aaaa'aaa")]
(4.6)
With a slight abuse of notation, we write p=',a=' as the Markov state transition operator induced by the Markov state transition kernel defined in (4.6). such that
(p
h[(s)
h(s')p=', (ds'' Is),
(4.7)
J'ES
where h S + R. is -nttegggae function and the Lebesgue measure over S Rd is used. Correspondingly, we define the operator norm of an operator O as
||O||op sup |10 hill, (1/lL,ss = sup 110 hllL,s))
(|bll,
where || [|),()) is the L1 Lorm over the state space S. The following assumption characterizes the Lipschitz continuity of pm',a-' and px -- with respect to -3.
Assumption 4.3 (Lipschitz Game). We assume that for the two-player zero-sum Markov game (S,A), AA,,, ,,,,,, 7), there exists > 0 such that for all s E S and [or) . "]
KL (+1s) +| 1/2 | m. px ",'"='llo 5 44 Ev
(4.8)
|n='m=5" (s) xx S KT. (m. ((1s))))))
(4.9)

---

Under review as a conference paper at ICLR 2021
The Lipschitz coefficient 4 in 4.8) of Assumption 4.3 on the nonstationary environment that Payer faces. Such a notion of influence is proposed by Radanovic al. (2019) in the tabular setting. In particular, the expected KL-divergence between the policies is used in place of the distance max,es |- (-1 π (- 8)][1 in Radanovic et al. (2019). Such assumption is also related to the linear-quadratic game (I.QG) literature (see, e.g.. Zhang et al. (2019)) where the Lipschitz continuity is established based on the special structure in the LQG model. Lemma C.2 we show that such Lipschitz coefficient 4 quantifies the Lipschitz continuity of the marginalized (tufftuntio of the antropy-regulare AS, A P,r,y, A2).
quantifies the influence of Player -i
two-player Markov game
Recall that क[+ exp(E241.00) is defined in (4.1 where E i is defined in (3.8 Also, recall that T & exp (xp+E0.11.()) (0)) is defined in Line of Algorithm where E0.41.(0) obtained by Mcanwhile, we define the ideal policy update as
minimizing (3.7 in Line 7 of Algorithm
[
1- x exp (Ep
where (0,1,00 a') = a/ (n,, + +,,(0) Q10
(s,
(4.10)
the corresponding ideal energy function update.
We lay out the following assumption on the errors that arise from the estimation of the marginalized
QGe-- function "" and the minimization of the MSE in (3.7..
Assumption 4.4 (Estimation Error). We assume that there exist e,, cj > such that for all 0 5
T
Ey- [1E (0, ||20] S at
(4.11)
En,- (E - E1+1,00 (, - - (-1))) 5
(4.12)
characterizes the estimation error through the policy updates in Line 7 of Algorithm I In particular, (4.11) upper bounds the errors arising from the minimization of the MSE (3.7).
Assumption 4.4
which is zero as long as the representation power of the parameterized class of the energy functions sufficiently strong. Meanwhile, by (3.7) and (4.10), the gap between (g.41.(0 and & E2+1,(0 involves 30d
(I) the gap between E4+1,00) and Ee+),()) which arises from the gap between (() and (II) the gap between (o..).(0) and E.+1,()) which arises the minimization of the MSE in
A 1 (e and Q
ma .o. is accurate and c zero. Hence, of in (.12 zero as long as the estimator "T." of Q(4)
We summarize 6 and of into the following total error a,
T-1
o a= 1(+ (4:
(4.13)
t=0
As discussed in Lemmas 4.7 and 4.8 of Liu et al. (019),, under Assumption 4.2 when we use sufficiently deep and wide neural networks equipped with the rectified linear unit (ReLU) activation function to parameterize the marginalized Q -functios and the energy functions, Assumption 4.4
can be satisfied with o = Ō(1) See Appendix B for a detailed discussion.
We are ready to present the following theorem the convergence of the policy sequence {i T bosisT to a neighborhood of a Nash equilibrium [T] Recall that Q and mmaa (6)
are defined in (.6) and (2.7), respectively. Also, recall that C is the concentrability coefficient in Assumption 4.2 4 the Lipschitz coefficient in Assumption 4.3] and defined in (4.13).
Theorem 4.5 (Convergence of Smooth FSP to Nash Equilibrium). Suppose that Assumptions 4.2
hold. We set the regularization parameter X; 2M, where
M, =
- [2+ (1.(1 (V (Vmmxx + Q
-0)(1-7))
(4.14)
(4)
In Algorithm I we set Cmax Q (Ax M,) and
A (t + 1) min tA, M,}' (4.15)
(10( (t 1). (1, 14: -MM}
a ar,00 =
8

---

Under review as a conference paper at ICLR 2021
For the policy sequence ([mb, ; n PosIsT-- generated by the policy update in Line 7 of Algorithm
1 we have
1 T
Σ 1=0
(r.. mē.) J [[b,. 2 (1e 22+ -M) (Q
log T
(4.16)
(1 7) mi, (1: Mi.
T
20 min.e(1.2) {}: -M}
E (E(1.2
X A log AA%
(1 (1-7)-T
Proof. See Appendix for a detailed proof. The key to our proof is the convergence of infinite- dimensional mirror descent with the primal and dual errors. In particular, the errors are characterized in Appendix B
Recall that the Lipschitz coefficient 4 is defined in Assumption 4.3 In Lemma we interpret 4 as the Lipschitz coefficient of the marginalized Q() -functinoo.. Meanwhile, recall that Theorem 4.5 requires A; 2 2M,,, where M, scales linearly with 44 Hence, the smaller the Lipschitz coefficient 4; is, the smaller the regularization parameter can be, which in turn leads a smaller regularization bias characterized in Proposition C.I Thus, the policy sequence {[m), Tē,loggeT--1 generated by Algorithm converges to smaller neighborhood of a Nash equilibrium [ m3).
We give the following two sufficient conditions for the Lipschitz coefficients. (I) The two players have similar influence to the game, i.e., 4//12 O(1): a sufficient requirement on both of the Lipschitz coefficients is
S (1 7)
/ (((0/111/////////11/// + + log |4']], i (1,2).
(II) One of the two players (without loss of generality, we assume it is Player 2) has dominant influence to the game compared to the other: let /1/12 = 2 > 0, in which case we set Mj in (4.14) as
M, 22 [2 + EiE(1,2) (V()ax + Q (0((1-)) 12 {1,2}.
Then one sufficient requirement on the ratio z is
2 (1 (1- 16(1 + 22 log (144) 1421]
[441-144)]]
As moves towards zero, the convergence guarantee approaches those for single-controne case. Please see Appendix for a more detailed illustration on case(II).
We remark in the following that, with stronger assumptions, we can strengthen Theorem 4.5 satisfy
Hannan consistency.
Remark 4.6 (Hannan Consistency). When Assumptions 4.2 4.4 hold for any policy [T"; n -= instead of only Nash equilibrium m_)] can prove that, when of the player does not update the policy as described in Algorithm|] I the opposing player can exploit the strategies it plays. Specifically, for example, when Player plays the policy sequence { JoSesT-1 while Player I updates its policy according to Algorithm
we have
T-1
sup
Σ
[J - [ib, m3)1
(4.17)
t=
σ (A1 (A1 Mi)
2 2222//( - 2 (Qmax)² log T + X log (A'
(1 71
(1- - M1)
T
which implies that the policy sequence ( Josis--1 converges the best policy in hindsight with respect to (# jogegr-.. As a consequence, we can also replace the left-hand side of (4166) by the following duality gap.
T-1 sup T 1=0
T-1 [(bb. 17)
inf
Σ
(4.18)
See Appendix | for a more detailed illustration on Remark 4.6

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approximation with policy gradient methods markov decision processes. arXiv preprint 1exivv/908... 00261, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv:/811.049/1 2018.
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted Q-iteration in continuous action-space mdps. In Advances in Neural Information Processing Systems, pp. 9-16, 2008.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584, 2019.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n n-player differentiable games. arXiv preprint 100.:::802..05000 2018.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06666 2019.
Lucian Bu, Robert Babu, Bart De Schutter, et al. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems. Man, and Cybernetics, Part C (Applications and Reviews), 38(2):15-172, 2008
Qi Cai, Zhuoran Yang, Jason Lee, and Zhaoran Wang. Neural temporal-difference learning converges global optima. arXiv preprint arXiv: 10027, 2019.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.06558, 2020.
Ashish Cherukuri, Bahman Gharesifard, and Jorge Cortes. Saddle-point dynamics: conditions for asymptotic stability of saddle points. SIAM Journal on Control and Optimization, 55(1):486-511, 2017.
Lenaic Chizat and Francis Bach, A note on lazy training in supervised differentiable programming. arXiv preprint arXiv: 1812:081, 2018
Vincent Conitzer and Tuomas Sandholm. Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. Machine Learning, 67(1-2):23 43, 2007.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. SBEED: Convergent reinforcement learning with nonlinear function approximation. arXiv preprint arXiv:1712.10285, 2017.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances in Neural Information Processing Systems, pp. 2253-2233222 22-12261,220 2016.
Constantinos Daskalakis and loannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246,
2018.
William Dudziak. Using fictitious play to find pscudo-optimal solutions for full-scale poker. In IC-AI, pp. 374-380, 2006.
Francisco Facchinei and Jong-Shi Pang. lintte-Dimensioall Variational Inequalities and Comple- mentarity Problems. Springer Science & Business Media, 2007.
10

---

Under review as a conference paper at ICLR 2021
Amis-ud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, pp. 668-576, 2010.
Matthieu Geist, Bruno Scherrer, and Olivier Pietquin. A theory of regularized Markov decision processes. arXiv preprini arXiv:/901.1 2019.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint arXiv:1603.0112,, 2016.
Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games, In International Conference on Machine Learning, pp. 805-813, 2015.
Daniel Hennes, Dustin Morrill, Shayegan Omidshafiei, R' T'mm Munos, Julien Perolat, Marc Lanctot, Audrunas Gruslys, Jean- Bant-Btt Lespiau, Paavo Parmas, Edgar Du'e ne7-Guzm an, al. Neural replicator dynamics: Multiagent learning via hedging policy gradients. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 492-501, 2020.
Junling Hu and Michael P Wellman. Nash Q-learning for general-sum stochastic games. Journal of Machine Learning Research, 4(Nov):1039-1069, 2003.
Feihu Huang, Shangqian Gao, Jian Pei, and Heng Huang. Momentum-basse policy gradient methods. arXiv preprint arXiv:2007.0668) 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems, pp. 8571-8580, 2018
Sham Kakade. A natural policy gradient. In Advances in Neural Information Processing Systems, pp. 1531-1538, 2002.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, pp. 267-274. 2002.
Keigo Kawamura, Naoki Mizukami, and Yoshimasa Tsuruoka. Neural fictitious self-play in imperfect information games with many players. In Workshop on Computer Gumes, pp. 61-74. Springer, 2017.
Valentin Khrulkov, Alexander Novikov, and Ivan Oseledets. Expressive power of recurrent neural networks. arXiv preprint 1rX0v:1711.00111, 2017.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, pp. 1008-1014, 2000.
Michail Lagoudakis and Ron Parr. Value function approximation in zero-sum Markov games. arXiv preprint urXiv:/331.055: 2012.
Andrzej Lasota and Michael C Mackey. Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics, volume 97, Springer Science & Business Media, 2013.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Jascha Schl-Dickstedi and Jeffrey Pennington. Wide neural networks any depth evolve as linear models under gradient descent. arXiv preprini arXiv: 1902.0670, 2019.
Michael Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pp. 157-163. Elsevier, 1994.
Boyi Liu, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural proxima/tuut region policy optimization attains globally optimal policy. arXiv preprint arXiv: 10306, 2019.
Eric Mazumdar and Lillian Ratliff. On the convergence competitive, multi multi-agent gradient-based learning. arXiv preprint arXiv: 1rXiv:1804.05444 080440 2018.

---

Under review as a conference paper at ICLR 2021
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-poin problems: Going the extra (gradient) mile. arXiv preprint wrXv::187.002629 2018.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International Conference on Machine Learning, pp. 1928-1937, 2016.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(May):815-88) 857, 2008.
Arkadi S Nemirovski and David Yudin. Problem Complexity and Method Efficiency in Optimization. Springer, 1983.
Yurii Nesterov. Introductory Lectures Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2013.
Brendan O' D'Dnoggue. Remi Munos, Koray Kavukcuoglu, and Volodymyr Mnih. Combining policy gradient and Q-learning. arXiv preprint 1r..i: 2016.
Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochas- tic variance-reduced policy gradient. In ICML 2018-35th International Conference Machine Learning, volume 80, pp. 4026-4035, 2018.
Julien Pérolat, Bilal Piot. Bruno Scherrer, and Olivier Pietquin. On the use of non-stationary strategies for solving two-player zero-sum markov games, In International Conference on Artificial Intelligence and Statistics, pp. 893-901, 2016.
Julien Perolat, Bilal Piot, and Olivier Pietquin. Actor-critic fictitious play in simultancous move multistage games. 2018.
Goran Radanovic, Rati Devidze, David C Parkes, and Adish Singla. Learning to collaborate in Markov decision processes. arXiv preprint 1rXiv:1901.0880 2019.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060 2018.
Julia Robinson. An iterative method of solving game. Annals of Mathematics, pp. 296-301, 1951.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (000:/777.3477 2017.
Lior Shani, Yonathan Efroni, and Shie Mannor. Adaptive trust region policy optimization: Global convergence and faster rates for regularized MDPs. arXiv preprint
02769, 2019.
Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International Conference Machine Learning, pp. 5729-5738, 2019.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484, 2016.
David Silver, Julian Schrittweeser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lueas Baker, Mattew Lai, Adrian Bolton, et al. Mastering the game of Go without human knowledge. Nature, 550(7676):354355,, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, pp. 1057-1063, 2000.
12

---

Under review as a conference paper at ICLR 2021
Brian Swenson and H Vincent Poor. Smooth fictitious play in N x 2 potential games. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pp. 1739-1743 IEEE, 2019.
Samuele Tosatto, Matteo Pirotta, Carlo D D'Eramo, and Marcello Restelli. Boosted fitted Q-iteration. In International Conference on Machine Learning, pp. 3434-3443, 2017.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft using multi-agent reinforcement learning. Nature, 575(7782)3350- -540,,3344440 2019.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior (commemora-
five edition). Princeton university press, 2007.
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01 150, 2019.
Nan Xiao, Xuehe Wang, Tichakorn Wongpiromsar,, Keyou You, Lihua Xie, Emilio Frazzoli, and Daniela Rus. Average strategy fictitious play with application to road pricing. 2013 American Control Conference, pp. 1920-1925. IEFF, 2013.
Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. arXiv preprint arXiv:1909.08610 2019.
Pan Xu, Felicia Gao, and Quanquan Gu. An improved convergence analysis of stochastic variance- reduced policy gradient. In Uncertainty in Artificial Intelligence, pp. 541-551. PMLR, 2020.
Zhuora Yang, Yuchen Xie, and Zhaoran Wang. theoretical analysis of deep Q-learning. arXiv preprint arXiv:/901.00137, 2019.
Kaiqing Zhang, Zhuoran Yang. Han Liu, Tong Zhang, and Tamer Başar. Fully decentralized multi- agent reinforcement learning with networked agents. arXiv preprint wrXiv:1802.087555 2018.
Kaiqing Zhang, Zhuoran Yang, and Tamer Basar. Policy optimization provably converges to Nash equilibria in zero-sum linear quadratic games. In Advances in Neural Information Processing Systems, pp. 11602-11614, 2019.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent RL in zero-sum Markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33, 2020.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. simite-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems, pp. 6668-8678, 2019.
13


Reviews:
[{"review_id": "y6DIzfMGfcE", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider self-play in zero-sum discounted two-player Markov games with compact state space and finite actions. They present a smooth fictitious self-play algorithm where each player adopts an entropy-regularized policy optimization method with the average of the past generated Q-values. Under appropriate assumptions, among which a Lipschitz regularity of the Markov game, the authors prove that this algorithm approximates the Nash equilibrium at a rate O(1/T) where T is the number of iteration.\n\n-Contributions\n\n-algorithmic: Smooth FSP algorithm a smooth version of fictitious self-play.\n-theoretical: Convergence rate of order O(1/T) of Smooth FSP under appropriate conditions.\n\n-Score justification/Main comments\n\nThe paper is well written. The proofs seem correct but I did not check everything in detail (see specific comments). My main concern is that the different assumptions made are a bit ad hoc (sometimes the assumption relates directly on the sequence of policies generated by the algorithm). And thus it is hard to assess if the provided bound is relevant or a trivial consequence of the assumptions (see specific comments below). As a sanity check and for a simpler proof it could be interesting to first present and analyze Smooth FSP without the estimation and approximation part first. \nIn fictitious play, each player plays the best response against the average of the past policies played by the adversary. Here it is not really the case since the policy used by one player is a  (smooth) best-response against a weighted average of the past Q-value, which depends also on the policy played by that player. Thus the link with Fictitious play is not completely clear. \nI’m also curious about the reduction of the presented algorithm to matrix game. Do we recover a known algorithm, and what can we say about the convergence rate of the algorithm? \n\n \n\n-Detailed comments \nP2: “remains less less understood” and what do you mean by “classical optimization”?\n\nP4, Section 3.1: the mixed policy as you defined it is not a policy (you cannot express as a certain function of s) thus talking about its Q-value does not make sense.\n\nP5: Is the normalization parameter \\kappa_{t+1,(i)} a learning rate of the normalization constant such that the probability sum to one? In the second case, it should be additive.\n\nP6: I do not understand the last sentence before Section 3.3 what do you mean by obtained from (3.3) and “which operates in the functional space given the marginalized”?\n\nP5, Section 3.3: \\Theta is not defined, how do you parameterized \\cE_{\\theta} exactly? What do you mean by “the estimator of the marginalized[...]”, how do you construct it?  \n\nP13, Appendix A: maybe you should say that you consider the Lagrangian on the constrained optimization problem and if it the case also add the constraint on the fact that the \\pi(a|s)\\geq 0.\n\nP6: In (4.3), you mean when \\nu_t is close enough to \\nu^*?\n\nP6, Assumption 4.2: could you provide a non-trivial example where this assumption is correct? Furthermore, the assumption is made on the algorithm that you propose rather than on the model is very suspicious. In particular, since the sequence \\pi_{\\theta^t} is a random sequence (because based on estimated quantities) in which sense the inequality holds? Almost surely?\n\nP7, (4.7): h is an integrable function with respect to which measure? And similarly, the L1-norm is defined with which measure?\n\nP7, Assumption 4.3: Could you provide a non-trivial example where this assumption is correct? And this assumption is not weaker than the one proposed by Radanovi et al because the quantities E_{\\nu^*}[ KL(…)] and max_{s} || ...||_1 are not comparable. \n\nP7, Assumption 4.4: Again since you are manipulating random quantities you should precise about what you mean by this inequality. Furthermore, there is in fact no assumption here but just introducing the notations \\epsilon_t and \\epsilon_t’ (if we allow them to be in \\bar{R}). The assumption would rather be that \\sigma = O(1). And I’m not totally convinced it is a reasonable assumption. For example in (4.1) if \\nu^t is singular with respect to \\nu^* then the MSE computed with \\nu_t will provide no information for the state where \\nu^* is supported.\n\nP8, Theorem 4.5: In fact M_i depends on \\lambda_i trough V_{(i)}^{max}…, thus it is not clear at all if you can set \\lambda_i \\geq 2M_i. In fact, you are adding an additional constraint on the different parameters. Could you make this explicit in the statement of the theorem? \n\nP16: In (C.10) in seems that you used t+1-(\\lambda_i+M_i)/(max_{i} \\lambda_i+M_i) \\leq t which is wrong.\n\nP16: In (C.11) the left-hand side should be divided by T.\n\nP23: In (G.2) it should be \\log(\\bar{\\pi}^i_{t+1}) instead of \\log(\\pi^i_{t+1})?\n\nP23, end of the proof of Lemma C.4: it is \\tilde{Q}.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "w_DSeRvAgtZ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is about the design and analysis of policy optimization algorithms that provably converge to a Nash equilibrium at a sublinear rate for a class of zero sum Markov games, which are one of the simplest settings of multi-agent RL --- in particular, for zero sum Markov games satisfying a Lipschitz regularity condition. Each players adopts an entropy-regularized policy optimization method (which the authors call as smooth Fictitious Self Play).\n\nThis is an important topic and the question studied is an important step to take given that we don't know whether Fictitious Self Play is guaranteed to converge in Markov games. However, I am quite surprised by very important related work missing in the paper. For instance, the NeurIPS 2019 paper on \"Policy Optimization Provably Converges to Nash Equilibrium in Linear Quadratic Games\" is not cited even though it is quite close to the topic of this paper: it also studies a policy optimization algorithm, linear quadratic games are also zero-sum Markov games, the objective studied is also non-convex non-concave. Of course LQ games are special class of zero-sum Markov games, but this paper makes some assumptions like Lipschitz regularity as well. Therefore claims like this paper is the first to prove convergence guarantees of policy optimization algorithms for zero sum Markov games are not quite true. The somewhat less related, but still quite close NeurIPS 2019 paper \"Model-based multi-agent RL in zero-sum Markov games with near optimal sample-complexity\" is not cited as well. These papers are not obscure: a simple search for the submitted paper's title brings up these papers.\n\nAlso, the Lipschitz regularity assumption being made is important enough that it is good to add it in the abstract, as the abstract feels misleading otherwise. And the importance/restrictiveness of this assumption is ideally discussed in more detail in the introduction. \n\nOverall I think this would make a good paper after fixing the above, but not right now. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "PNvNQ1S0c5D", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the two-player zero-sum Markov game using fictitious self-play (FSP) strategies. The authors proposed a novel entropy regularized policy optimization method for both agents. They proved the sequence of joint policies converges to a neighborhood of a Nash equilibrium at a sublinear rate. The paper is well written though the notations are a little bit complicated for readers to understand. The results seem to be rigorous. \n\nOne drawback is that the proposed algorithm is not evaluated using any empirical studies. Since the algorithm is new to the literature, it would be expected to see how it performs compared with other baseline methods in experiments. \n\nHave you considered the stochastic variance reduced policy gradient methods? There has been an active line of work (see [1-5] for some examples) that shows the variance reduction techniques can improve the convergence rate of policy optimization methods in the single-agent setting. It would be interesting to know whether the convergence of the smooth FSP can be also improved using the same techniques.\n\n[1] Papini M, Binaghi D, Canonaco G, Pirotta M, Restelli M. Stochastic Variance-Reduced Policy Gradient. InInternational Conference on Machine Learning 2018.\n[2] Xu P, Gao F, Gu Q. An improved convergence analysis of stochastic variance-reduced policy gradient. In Uncertainty in Artificial Intelligence 2019.\n[3] Shen Z, Ribeiro A, Hassani H, Qian H, Mi C. Hessian aided policy gradient. In International Conference on Machine Learning 2019.\n[4] Xu, P., Gao, F. and Gu, Q. Sample Efficient Policy Gradient Methods with Recursive Variance Reduction. In International Conference on Learning Representations 2020.\n[5] Huang F, Gao S, Pei J, Huang H. Momentum-Based Policy Gradient Methods. In International Conference on Machine Learning 2020.\n\nEquation (2.3) is not entropy regularized. Instead, the state-reward function is entropy regularized.\n\nHow is the mean squared error in (3.7) solved? In the proposed algorithm, it is assumed that this can be exactly solved. However, a practical approximation of this solution will cause additional estimation error. As is required in Equation (4.13), it seems that the authors assume the estimation error to be roughly in the order of 1/t^2. I am not sure whether this strong convergence can be established using sampled data for (3.7).\n\nThe convergence result in Theorem 4.5 is upper bounded by a very large term \\lambda_i \\log|A^i|, where \\lambda_i is larger than the Lipschitz constant, and |A^i| is the size of the action space. If I understand it correctly, both quantities are nonvanishing and thus the result in Theorem 4.5 is not convergent. I did not see any discussion in the paper to address this issue or discuss how the neighborhood can be shrunk to a smaller region. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4S2IT363AP4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of learning to play a Nash equilibrium in two-player, zero-sum Markov games.  This is a longstanding problem, with many algorithms proposed but relatively few theoretical convergence guarantees, and most of those either for quite restricted settings or with strong assumptions.  This is in stark contrast to the stateless setting of Normal Form Games, where we have many strong theoretical convergence guarantees.  The main algorithm is a version of the classic fictitious play algorithm.  Like prior adaptations of fictitious play to Markov Games, it operates on the Q-values, but a key novelty (at least in the stateful setting; similar ideas were recently applied in a special case of normal form games by Swenson and Poor 2019) is the use of a particular form of regularization in the best response process.  The main result is that as long as the game satisfies Lipschitz and Concentratability properties for each player when the other plays optimally and the policy updates are sufficiently accurate then play converges to a Nash equilibrium.\n\nI like this paper quite a bit.  It tackles a hard problem  and makes solid progress.  I think the algorithm and analysis are both nice contributions and definitely intend to study the latter further as I think aspects of it may be useful in other settings.  Overall the presentation, while dense, is clear.  However, I believe there are a few issues that could use additional discussion:\n\n 1) Why does the uniqueness, or lack thereof, of the Nash equilibrium not matter to the results?  Quite a bit of prior work has had caveats when they are not unique.  The results seem to hold if the assumptions are true for at least one equilibrium, presumably because of the minimax properties in a zero-sum setting, but I’m not quite clear how this interacts with the assumptions.  For example, if one but not all the equilibra cause the game to satisfy Assumption 4.2 and 4.3 what causes the guarantees to still hold even if initially play gravitates toward some equilibrium where they do not?\n\n2) I’m not quite clear how to interpret the convergence guarantee in Theorem 4.5.  The text after the theorem talks about the policy sequence converging to a neighborhood, while the theorem itself is about the averages across the sequence of policies.  It would help to have some more detailed discussion of exactly what sort of convergence behavior we should expect.\n\n3) I’m intrigued by the observation at the end that this algorithm is Hannan consistent under stronger assumptions.  There has been some work recent work exploring connections between regret minimization and RL and it would be worth discussing a bit how this observation relates to that literature, e.g.: \n\n@inproceedings{hennes2020neural,\n  title={Neural Replicator Dynamics: Multiagent Learning via Hedging Policy Gradients},\n  author={Hennes, Daniel and Morrill, Dustin and Omidshafiei, Shayegan and Munos, R{\\'e}mi and Perolat, Julien and Lanctot, Marc and Gruslys, Audrunas and Lespiau, Jean-Baptiste and Parmas, Paavo and Du{\\`e}{\\~n}ez-Guzm{\\'a}n, Edgar and others},\n  booktitle={Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems},\n  pages={492--501},\n  year={2020}\n}\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that a form of Fictitious Self-Play converges to the Nash equilibria in Markov games. Understanding the theoretical properties of Fictitious Self-Play is important, however the paper in its current form is not ready for publication. The paper needs a more thorough discussion on related works, the assumptions made, and as pointed out by Reviewer3, the convergence argument needs to be expanded and explained in more detail. Further, I encourage authors to add experiments and compare their algorithm with other methods. 
Decision: Reject