On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games
Authors: Runyu Zhang
Jincheng Mei
Bo Dai
Dale Schuurmans
Na Li
Venue: NeurIPS 2022 Accept (2022)
Keywords: multiagent learning
Markov potential games
policy gradient
Nash equilibrium

Abstract: Softmax policy gradient is a popular algorithm for policy optimization in single-agent reinforcement learning, particularly since projection is not needed for each gradient update. However, in multi-agent systems, the lack of central coordination introduces significant additional difficulties in the convergence analysis. Even for a stochastic game with identical interest, there can be multiple Nash Equilibria (NEs), which disables proof techniques that rely on the existence of a unique global optimum. Moreover, the softmax parameterization introduces non-NE policies with zero gradient, making it difficult for gradient-based algorithms in seeking NEs. In this paper, we study the finite time convergence of decentralized softmax gradient play in a special form of game, Markov Potential Games (MPGs), which includes the identical interest game as a special case. We investigate both gradient play and natural gradient play, with and without $\log$-barrier regularization. The established convergence rates for the unregularized cases contain a trajectory dependent constant that can be \emph{arbitrarily large}, whereas the $\log$-barrier regularization overcomes this drawback, with the cost of slightly worse dependence on other factors such as the action set size. An empirical study on an identical interest matrix game confirms the theoretical findings.

On the Global Convergence Rates of Decentralized Softmax Gradient Play in Markov Potential Games
Runyu Zhang
Jincheng Mei Google Research, Brain Team ommeigooglee.co com
Harvard University runyuzhangéras. harvard.
Bo Dai
Dale Schuurmans University of Alberta
Na Li Harvard University
Google Research, Brain Team bodai com
Google Research, Brain Team schuurmans@google, com
nal i @seas www.aard...ee......... edu
Abstract
Softmax policy gradient is popular algorithm for policy optimization in single- agent reinforcement learning, particularly since projection not needed for each gradient update. However, in multi-agent systems, the lack of central coordination introduces significant additional difficulties in the convergence analysis. Even for a stochastic game with identical interest, there can be multiple Nash Equilibria (NEs), which disables proof techniques that rely on the existence of a unique global optimum. Moreover, the softmax parameterization introduces non-NE policies with zero gradient, making it difficult for gradient-basse algorithms in seeking NEs. In this paper, we study the finite time convergence of decentralized softmax gradient play in a special form of game, Markov Potential Games (MPGs), which includes the identical interest game natural gradient play, with and without log-barrier regularization. The established convergence rates for the unregularized cases contain trajectory dependent con- stant that can be arbitrarily large, whereas the log-barrier regularization overcomes this drawback, with the cost of slightly worse dependence on other factors such the action size. An empirical study identical interest matrix game confirms the theoretical findings.
special case. We investigate both gradient play and
1 Introduction
Multi-agent systems encounter vast application in real world scenarios, such as network routing [35, 8J. social and economic decision making [36, 30), and robotic swarms [22, 14]. In these problems, a system consists of group of agents interacting of reinforcement learning (RL), increasing attention has been drawn to the possibility of applying RL algorithms, such policy gradient, multi-agent systems. However, the theoretical foundations for multi-agent reinforcement learning (MARL) remain limited. Unlike single-agent RI., the actions of other agents affect the dynamics and the decision making outcome for each individual in the system, raising additional theoretical challenges when analyzing joint performance.
shared environment. Given the recent success
The stochastic game (SG) is a classical multi-agent model that has received extensive attention in recent MARL studies. In stochastic game, the environment is represented by state space that evolves based on the joint actions agents. Each agent in a stochastic game tries to maximize its own total reward by making decisions independently, based on state information shared between agents. The stochastic game model was first introduced [31], with a series of followup works proposing NE-seeking algorithms, particularly in the RL setting (e.g. [21, 5, 32, 6, 17, 38] and citations therein). Given recent progress in the underlying theory of RL, many recent works have investigated finite
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

time iteration and sample complexity for learning NE or other general equilibria notions, such as correlated and coarse correlated equilibria (e.g. [33]).
There are different types of SGs, some with attributes that merit special attention; for example, two-player zero sum games [4, 9], which are widely used to model two player competitive games such as GO. In this paper, we will focus on another type of SG, the Markov potential game (MPG) [23, 27, 39, 18], which includes the identical interest game as a special case. The structure of a MPG enables efficient learning through the use of gradient-based algorithms such as gradient play. Recent work [39. 18] has focused on the iteration and sample complexity of finding a NE in an MPG under the direct policy parameterization, which is not practical in most real world scenarios, given the cost of projecting back to the probability simplex on every iteration. This drawback has motivated consideration of the softmax parameterization, which bypasses the projection step in the gradient update, and is perhaps the most popular approach to parameterizing policies in practice. [11] have studied natural gradient play for MPG under softmax parameterization, but only address asymptotic behavior and leave finite time complexity open.
From the perspective of analysis and practical performance, the extension from the direct to the softmax parameterization in policies is nontrivial. Even in the single agent case, as shown by [2, 24], there are policies in the softmax parameterization that have near-zero gradient and yet are far from being globally optimal, which creates difficulty for a gradient-basee points. A similar issue exists for MPGs: due to the more complex interaction between agents, there is even a greater set of policies that obtain small gradient norm but are far from NE. Based on our analysis and numerical results, even for natural gradient play-which is known to enjoy dimension free convergence in single agent learning [2]-we find in the multiagent setting that it can still become stuck in these undesirable regions. Such evidence suggests that preconditioning according to the Fisher information matrix [29, 3] is not sufficient ensure fast convergence in multi agent learning. stronger form of regularization is required, which motivates the introduction of log-barrier regularization to avoid undesirable regions of policy space.
algorithm to escape suboptimal
Algorithm
Single-agent MDP
Multi Multi-agent MPG
Gradient play,
LAIM2
O (Amax dmin E. IA
[1
(1-7)²c² [39, 18]
direct parameterization
[2]
Gradient play,
0
(1-7)>cte
M
0 ra max; |A (A:(@mma Umnn )M (1-))a
softmax parameterization
[24]
Natural gradient play,
0
[I~m)==)
O n(@mma Oennn) 0mina) (1 (1-7)ace2
softmax parameterization
[2]
|
Gradient play log- log-barrier reg.,
0
(1-7)42²
O n max |Au 2 (Almar Dminn) )M²
softmax parameterization
[2]
(1-7)422
Natural gradient play log-barrier reg, softmax parameterization
Unknown
maxi Aall - Pmmn Lm? )M
(1-7)*<²
Table 1: Summary of known convergence rate results for gradient based methods in Markov decision processes (MDPs) and MPGs respectively. The new results proved in this paper for MPGs are displayed in bold font. Complexity bounds with ** depend on additional assumption on the MPG (See Theorem 4 and 5). The definitions of variables M and e appearing in some hounds be found in (5) and (11). Note that the definition of M is slightly different from the "distribution mismatch coefficient" Doe defined in [2] (see more details in descriptions that follows Assumption 1). To make the complexity results more comparable, we slightly modify and re-derive the results in [2, 24, 39, 18).
Our contribution: In this paper, we provide finite time iteration complexity results for gradient play and natural gradient play under the softmax parameterization, considering both unregularized and log-barra barrierrirr regularized dynamics. We summarize the convergence rates and compare them to existing results for the direct parameterization and to the corresponding single agent cases in Table I. These findings suggest that regularization is crucial for obtaining fast convergence to a NE under the softmax parameterization in MPG. In Table the results for the two unregularized algorithms in the multi-agent case rely on the assumption that the set of stationary policies is isolated (which is also assumed in [11] when establishing the asymptotical convergence for natural policy gradient), and the corresponding complexity bounds contain an initialization dependent factor c. By contrast, the log-barrier regularized algorithms overcome both drawbacks, but as a tradeoff, their bounds

---

incur a slightly worse dependence on |A,] and M. We observe numerically that the oog-barrier regularized algorithms are indeed more robust against becoming trapped near undesirable non-NE stationary points. To the best of our knowledge, the finite-time iteration complexity results are the first such results for MPGs under the softmax parameterization. Though the analysis for the gradient play follows their single-agent counterparts [2. 24], the results for natural gradient play are highly non-trivial, requiring very different analysis tools which have their own merits to the literature (see Remark and Remark for more details on the technical novelty in the analysis). Our results also convey the following two messages. First, finding the NE of a multi-agent MPG is harder than finding the global optimum for the single-agent case, because multi-agent learning suffers greater risk of becoming trapped near undesirable stationary points. This is reflected in the dependence of the complexity bounds counterparts, suggesting that natural gradient play captures useful information about the geometry of the parameter space that accelerates the learning process.
in Table 1. Second, natural gradient play outperforms gradient play
2 Problem settings
We consider an infinite time horizon n-agent stochastic game (SG, [31]) MN, x
x AA, P.r (Tn), P) which is specified by an agent set N = m1) a finite state space S, a finite action space A, for each agent i E N, a transition model P (such that ((* = P(s"|s, .01....,0, is the probability of transitioning into state s' upon taking action a = (a1..... (n) state s where a, E A, action of agent i), a reward function r; : SS A - [0. 1 for each agent i, a discount factor E [0, 1), and an initial state distribution p over S. We use s(t) E S
to denote the state at time step t,, and a(t) = (a1 (t), (t),---: an (t)) E A to denote the total action.
stochastic policy π + A(A) (where A(A) is the probability simplex over A) specifies a strategy, where agents choose their actions jointly based on the current state in a stochastic fashion; i.e. Pr(a(t)] (()) = (t))))sstt). A decentralized stochastic policy is special subclass of stochastic policies with π = π1 X x Tn, such that n; : S - ((Aa), where n. is agent i's own local policy. For decentralized stochastic policies, each agent takes its action based on the current state independentl of other agents' action choices; i.e.,
(((((t)ss(t)===((())(((()))){ = -T:= (t)(sssst))
For notation simplicity, we define we use the notation -i to denote the index set N (1). In this paper we focus on tabular softmax parameterization for policy, where policy T = ..f.....,TT..... is parameterized by set of parameters 0 (0I.....,,) with 8; = =1 B.ES,, and where
where I S N is an index set. Further,
exp (0p,a)
To. (a.ls) En; exp (0x.at)
We denote agent i's total reward starting from initial states s() p as: (,(
Excory [E 7's (s()),()) a(t)) no, s(D) s] Agent i's objective is to maximize its own total re- ward J4. A Nash equilibrium (NE) is often used to characterize the equilibrium (a joint policy) where no agent has a unilateral incentive to deviate from it.
Definition 1. (Nash equilibrium) A policy 0* (0i,...,,0 0;) is called (Markov perfect) Nash equilibrium (NE) if
J,(0 02,) 2 (, 0-;),
vO, EEN
Further, we define the 'NE-gap" a policy 0 to be:
(E-gap,(()) == sups ((( 0-;) (0,,,, 0-:);
NE- NE-gap(f) = max, NE-gap, (f).
A policy 0 is an c-Nash equilibrium if: NE-gap (0) c.
We define the value function with respect to stage cost r; as:
Vi = o' a (1)) no. (0) = =]]
We define agent i's Q- Q-function and advantage function Q¹ S x A-R, (s, ((s,,a)=EE] = E ('ra(s(t),a(t) Tg. s(0) =, a())
4((s,a)==((ssc)) (s))
3

---

We further define agent i's 'averaged' Q-function Of -Sx - IR and 'averaged' advantage- function A. A, + R as:
(s, == Eo To (a (s,0; (s, A,(s,a))== E. To _ (a_=ls) ai, ami).
Finally, define the discounted state visitation distribution da of a policy нe given an initial state distribution p as:
(s( =- Ex -:)
- s|s(0)),
(3)
where Pr = s (0)) is the state visitation probability that s(t) s when executing ιTe starting at state s00). From the policy gradient theorem [34], we have that (proof given in Appendix B):
OJ.(0)
do(s)To, (s.
(4)
08 00.... s.o.
1 1-7
For the remainder of the paper, we make the following assumptions on the stochastic games we study. Assumption 1. The stochastic game M satisfies: info minses ds(s) >
Assumption I requires that every state is visited with positive probability for any policy, which is standard assumption for convergence proofs in the RL literature (e.g. [2, 24J). We will use M to denote the following quantity
(5) Note that M can be viewed as a measure of exploration sufficiency in the stochastic game, which is slightly different from the "distributional mismatch coefficient" introduced in [2] defined by
M == supa max, To(e)*
supo,0 max, (s)(s), however, both be upper bounded by max, (1~7)p(3)
We primarily focus the following subclass of stochastic games in this paper:
Definition 2. A stochastic game is called Markov potential game (MPG, [37, 23, 39, 18, 26]) if there exists a potential function á SS x A x ... x An + IR such that for any agent and any pair of policy parameters (0', 0)), (0,, 0))
E
a()))=
s00
E
E
(o(s()).(())) T= ((),) =s
E
r' ((((()) ((0())).(0))= (0)
V (6)
Without loss of generality, we assume that Φmin S <6(s,a) I Φmax for all (s. a). The definition of MPG is a generalization the notion potential game in the one-shot setting [28]. Note that identical reward game where agents share a same reward function naturally satisfies the above condition and serves important special case of MPG. For non-identical reward settings, [23, 12] found that
continuous MPGs can model applications such as the great fish war [19], the stochastic lake game [10], medium access control [23] etc. For tablular MPGs, [39, 18] also discuss necessary/sufficiet conditions that implies a MPG, as well its application and counterexamples.
Given a MPG, we define the total potential function t as:
(0) Ex(O)~p [E 7 ((s(((((((())) ne, s(0) = =]
Given the property in (6). it is straightforward to verify that the NE condition (2) is equivalent to (8; 0* (6 V i N and that for the policy gradient, 8J, 04(0) for all i, 8, 0g-
80_.., ao....
Remark (Differences between MPG and single-agenteenntralieeed MDP) Because of the exis- tence of the total potential function Q it is natural to ask whether MPG renders the multi-agent policy gradient similar to single agent policy gradient and thus results and analysis tools developed for single agent policy gradient e.g., [2, 24] would easily extended to the multiagent case. Unfortunately, this is not the case. To illustrate how it differs from aagll--ggett/centrllieed case, we can focus on the special type of MPGs where every agent has the same reward function, namely the identical interest case. In the single agent/centralized case, there is a unique global optimal solution which corresponds the convergent stationary policy. However, in the multiagent case, because the policy is decentralized, i.c., agents taking independent policies т := πΙ X ... x Tn- we loose the connection between stationary policies and optimal policies. As we shown later, the
if the rewards
identical,

---

convergent stationary policies are Nash equilibria, which are unfortunately non-unique even for the identical interest case. Moreover, key condition that used establishing the convergence rate, tojasiewicz condition (Lemma 1), is also much weaker for the multiagent case compared to single agent [24]: the left hand side is the Nash gap m ( 8-4) ((0) instead of the optimality gap max9. & (6*) ())).. Note that zero Nash gap does not imply zero optimality gap. there exists many NEs of different values. These differences disable many proof technique used for single agent case and make the analysis harder and lead to different performance results, as demonstrated in
the rest of the paper.
3 Relationship between first order stationary point and Nash equilibrium
Before studying convergence performance of gradient play algorithms, it is important to first under- stand the relationship between the stationary points and the NEs. Unfortunately, equivalence cannot be established in this setting. Standard optimization theory guarantees that all NEs are stationary points, but unfortunately not vice versa. Under softmax parameterization, there exist non-NE sta- tionary points. For example, from the gradient formulation (4), it can be shown that any non-NE deterministic policies are also stationary points. However, the notion of NE and stationarity are indeed closely related. This section aims to characterize some differences between NE and non-NE stationary points. This differentiation of the NE and non-NE stationary points is established by the non-uniform Łojasiewicz condition (also known as gradient domination) for stochastic games.
Lemma 1.
(Non Moon-unifomm Lojasiewicz inequality; proof given in Appendix D) Define
M(0) max, Jo(aj+
EagEargmax, c(0) := =min, Eaz Eargmax,, Q (o(a)))) Te: (a: (s).
Then have that
NE- NE-gap,(0) < M(O) c0) Vo,1(
The Lojasiewicz condition (gradient domination) implies that the NE-gap of policy can be bounded by the norm of its gradient, whereas the term 'non-uniform' refers to the factor v/A.Iar(0) e(1)
which
cannot be bounded uniformly for all 0. The counterpart of Lemma for single-agent MDP was first introduced [24, Lemma 8]. One major difference between Lemma 1 and [24, Lemma 8] is how c(f) is defined. In [24], c(0) == min, (a(a" (s)[s), where a" (s) is the optimal action on state (i.e., a* argmax, (s a)), whereas in MPG, because there's no globally defined Q", the af in (7) is chosen as the greedy optimal action of the current averaged Q-function (i.e., at argmax,, (s, a:)).
Note that because c(f) on the denominator can be zero for certain policies (e.g. one can verify that any non-NE deterministic policy have c(0) 0), which implies that a with gradient norm close to zero is not necessarily near a NE. Given this observation, we could differentiate the non-NE stationary points with NEs by whether c(0*) equals to zero, which is formally stated in the following lemma:
Lemma 2. (Proof given in Appendix D) Suppose 6" is a stationary point, i.e. [[V = 0. then 0 is a NE if and only if c(00) = 1, 0t is not a NE if and only if c(0*)= =0.
Unregularized gradient play
We first investigate the convergence to NE for gradient and natural gradient play, respectively. Under the softmax parameterization, the two schemes are given by
Gradient Play:
g((+1) 8.00 Vn, (10
(8)
Natural Gradient Play:
g((+1) 0.9) (
(9)
where & denotes the Moore-Penrose inverse and F((0) is the Fisher information matrix for Te.
(0) ( (-10) Ve, log Te. (a. Vo, log =ag)s(
5

---

For notational simplicity, we abbreviate the variables doco, Anto and Agt0) as d A4 and A respectively; and denote Tece (a|s) and Ty( (a:]s) x² (als) and n; (a:ls) respectively. For the softmax parameterization, we can establish the equivalence of natural gradient play and soft Q-learning [13), formally stated in the following lemma.
(1)
Lemma 3. (Proof given in Appendix C) Natural gradient play is equivalent to
(6) (t-1) (a (azls) mi (azls) exp (1)A (1)(a)))(11))))
(10)
Asymptotic convergence to Nash Equilibrium. As stated in Section 3, there exist stationary points that are not NEs. is not immediately obvious why running gradient methods avoid converging to these points, thus before studying convergence rate to NE, it is necessary to first examine whether asymptotic convergence holds. Moreover, the asymptotic convergence result is used to establish the finite time convergence rate results later (see the subsection 4.1).
Theorem 4. (Proof given in Appendix E) Suppose Assumption holds and that the stationary policies
are isolated, gradient play (8) with S
(1->)²
guarantees that lim4->+0c g(() g(cs)) where glxo)
6m
is a NE. The same argument also holds for natural gradient play (10) with 2n(2maax Amin
(1-
The proof of Theorem 4 resembles the technique used in [2] for the single agent case, where the additional assumption on the isolated stationary policies is introduced due to some specific technical difficulties encountered in multi-agent learning (see more discussion in Appendix E, which is also introduced in [11] for establishing the asymptotic convergence of NPG. We believe it is conservative condition for ensuring the asymptotic convergence. It remains an interesting open question to establish convergence without this assumption.
4.1 Finite time convergence rate
This section considers finite time convergence rate for gradient play and natural gradient play. Corresponding results for the single-agent setting be found in [24] (for gradient play) and [2. 16, 25] (for natural gradient play). Some aspects of these analyses can be carried over to the multi- agent MPG setting; however, as will be discussed later, there are several fundamental differences that make the multi-agent case more challenging.
Our convergence results rely on the observation from Section 3 and the asymptotic convergence to NE. Combining Theorem and Lemma 2, we know that c(0(1) asymptotically converges to I for (natural) gradient play, and since c(0()) > 0 for any softmax policy (because no, (a: > 0),
c inf, c(((1) > O.
(11)
We are ready to give formal convergence rates for gradient and natural gradient play respectively. Theorem 5. (Gradient play and natural gradient play; proof given in F) Suppose Assumption I holds and that the stationary policies are isolated, gradient play (8) with 17 = 6n for all T,
(1-7)² will guarantee that
Et=D NE (B
50 max;
[A Pmia) )M² )
)
)
(12)
T
(1 - 22T
(1-2)²
Natural gradient play (10) with 2n((Amax Manin
will guarantee that for all T,
ErD NE- (E-gap(O(t)) So (n(chmaxx (2min)2 ) J2M
(13)
T
(1 CTT
Here O(-) hides constant factors, M and are defined as in (5) and (11), respectively.
Remark (Proof sketch and novelty). The proof for gradient play is relatively straightforward from the non-uniform Lojasiewiez inequality and standard non-convex optimization results, which we refer readers to the appendix for more details. However, the proof for natural gradient play is more involved and existing analysis on NPG cannot be generalized this setting. For single-agent MDP, the analysis on NPG leverages the unique existence of optimal value function V* so that similar analysis for mirror-descent also carry over to NPG analysis, and thus obtain dimension

---

free convergence. However, in the multi-agen setting, there's no well-defined V as NEs can be non-unique with different potential values, thus, we need to further deploy additional structures of the total potential function Φ. Our analysis rely on the sufficient ascent lemma (Lemma 20) that lower bounds the ascent amount (0(t=1)) - (((()) for each natural gradient step (we would like to further note that this sufficient ascent lemma cannot be trivially obtained by the smoothness of $). Then, we further lower bound the ascent amount terms of NE-gap (Lemma 21). Lastly, the theorem follows by conducting standard telescoping techniques.
Discussion on 1: The complexity results in Theorem 5 both depend on 1. However, this term can become arbitrarily large. In fact, [20] show that e can be exponentially small terms of the number of states [S] for general finite MDP, even under uniform initialization, hence convergence can be very slow. This conclusion is also confirmed by numerical evidence. As pointed out by [24], even for single agent settings, policy gradient can get stuck at regions with small gradient yet far from being global optimal. Similar or even worse phenomena can be observed for multi-agent MPG, as shown in Figure (()) even for a single state game (SS) = 1) with uniform initialization, unregularized still enter regions with relatively large NE-gap while the gradient
gradient based algorithms norm and c(f) are close to zero.
More comparison with learning for single-agent MDP: For gradient play, we have established
an iteration complexity of O max, (dmay drmin ). to find an e-NE, whereas [24] show a (1-2)
complexity of O (Omax Chmin M MM
to reach an e-global optimum for policy gradient in a single
(1-7)<c'e
agent MDP. The dependence on is better in the single agent case because of the existence of global optimal policy n² and optimal total reward V*, which justify the definition of optimality gap 5, (((+)) V This, combined with the non-uniform Eojasiewicz condition which bounds d; by the gradient norm, allows one to use techniques from convex smooth analysis to show that ó, is on the scale of +. By contrast, for multi-agent learning, there can be multiple NEs with different values, hence 6; ill-defined. Further, note that the NE-gap different from the optimality gap. hence gradient ascent no longer guarantees monotonic decreasing of NE-gap (Figure I (a)), and we can only exploit non-convex optimization techniques that yield O 1 complexities.
For the same reason, the rate of convergence we obtain for natural gradient play is O (dhnax dhminn) "M which is worse than the dimension free convergence rate of O (1-ク)
(1-7)"ce"
given in [2] for single-agent MDPs. (A better exponential convergence rate for natural PG has also been proved in [16. 25] with the exponential factor being problem dependent.) Nevertheless, the dependence on 1 I and M is better than gradient play, suggesting that the preconditioning of I-y natural gradient play at least partially captures the geometry of the parameter space. We also note that the quadratic dependence on (Φmax mmin) might be a proof artifact. It remains an open question whether this can be reduced to a linear dependence.
Gradient play with log-barrier regularization
The previous section has shown that, for unregularized objectives, the convergence rate for gradient based algorithms depends factor _ that be arbitrarily large for bad initializations. This motivates investigate regularization, hopes of removing the dependence 1. For this purpose, we consider log- log-barrier regularization:
J.(0) (0) + log тे, (a-ls).
9,0s
Define:
(0) (())
Σ
log no, (a. ls).
(14)
i=1
8,0,
It is not hard to verify that the gradient with respect to Jj is:
a5.(())
a5(
do do(s) (a:)s) + -- -|
08..::
09 s.ac
1
7

---

Discussion on the choice of the regularizer: Before analyzing the resulting algorithm we first discuss the motivation for this regularizer. First, note that for each agent, the additional regularizer only depends on an agent's ' own local policy, which is desirable for multiagent RL. As an alternative, one might impose regularization by choosing
(0)) - (0) + ABg Ex=1 Ea; log ne, (a:ls);
i.e., so that the regularization weight imposed on state depends on the state visitation probability ds(s). However, in this case the gradient of the i-th agent Ve, (0) will not only depend on its own policy parameter 0,, but also other parameters of the other agents' policies 0-3. Thus, running gradient based algorithms with such a regularization scheme can no longer executed in fully decentralized manner using local policy information. Therefore, we prefer regularization (14) which does not depend on dg (s). Secondly, we adopt the log- log-barrier instead of entropy regularization due to technical rather than practical considerations. Although entropy regularization achieves fast exponential convergence in single agent learning [7, 24], for multi-agent learning. we haven't 't been able to obtain results as strong as the log-ban bog-bbrrier regularization. Intuitively, the log-barrier regularized gradient field repels the trajectory from regions with small (1: (a:]s) values (where the geometry becomes close to singular) more strongly, which enables us to obtain our current analysis. However, we emphasize that our result does not imply that log-barrier is better than entropy regularization in practice. It remains future work to determine whether entropy regularization, other methods such as trust region based methods, can achieve the same, or even better convergence rates.
5.1 Gradient play
We first consider gradient play algorithm, i.e.,
0(++1) = 0
Vo. Vo
(15)
Fortunately, similar analysis from [2] for single-agent MDP can be generalized to MPG with slight modifications. Here we only state the result and defer the proof to Appendix G.I.
Theorem 6. Under Assumption for = 6n max, [A.((19)3s and M max; LA. let ((0) be the uniform random policy, i.e., ((0) then rumning gradient play (15) for T steps, where T N O max, (A.mar Prain )M² will guarantee that minogegT-1 NE-gap(0(0) Se.
(1-+)a
(1-7))=2
Note that compared to the unregularized case in Theorem 5, it only requires Assumption 1, while the convergence rate is accelerated by eliminating the dependence on ? However, as a (worthy) tradeoff, the dependence on the action space size max; [A; now becomes quadratic. The key reason for these differences is that log-barrier regularization assures that any policy with sufficiently small gradient norm cannot be close to the boundary of the probability simplex where the non-uniform Lojasiewicz constant is large.
5.2 Natural gradient play
In the unregularized setting, we have seen that natural gradient play enjoys better convergence rate than gradient play, which motivates us to consider whether a similar advantage still holds for the regularized case. In this section we consider natural gradient play
0 ((+1)
o!t) + (F
(16)
which is equivalent to (see the proof in Appendix C)
T (++1) ((+t)) (ails) x
(0()) (ails) exp T -
(
n
(17)
d(0) (1)
(ails)
(1)
Theorem 7. (Proof given in Appendix G.2) Under Assumption 1, for
7 = min
the natural gradient play (17)
15
+ MAA,)M)) 4( max, LA|
4M
3
(--7
a
8

---

02
02
=
2
0.30
procect Mky
3.20
grodect piay
1
-1
0.14
gacuet 19
grodect bareer
0
2
0.16
0.15
Groclent
0
3
0.2
-1
Reward table
100
200
330
400
500
630
100
230
200
100
600
600
(a)
(b)
2.10
04
2.29
gi0d pily lng barte:
-0.0
201
500
200
603
600
Tarations
Rerabors
(c)
Figure I: We consider two-player identical reward matrix game shown in the reward table. We gradient play and natural gradient play (with and without log-barrier regularization) with initial policies being the uniform distribution (i.c., æ1 3. 3 5). T2 = = 1D. The subfigures (a)-(d) show how the NE- NE-gap g))( (o((((()) )l2, c((()) (defined in (7)) and ((((()) change with each iteration respectively. In Figure (c), zoom in the log10 c(0) factor for natural gradient play. In Figure (d), we also zoom out the trajectory for running gradient play to itcration 2 x 10". Here the step sizes were chosen to r = 5 while the regularization weight À was chosen to be À = 0.003. In consideration of numerical stability issues, we truncate the update step of natural gradient play with log- barrier regularization by maximum absolute value of 1 for each entry. For more numerical results and corresponding analysis see Appendix A.
will guarantee that Leso NE-gag (0(0) T
y --) + Amax; [A|[M, Further, by setting max,, LA, Aelmmmm Omin J we have ΣT-1 NE- gap()
2 max; [A:]M* ((0) 0, for
I c.
(1-7)+62
T
Remark 3. (Proof sketch and novelty) As also stated for unregularized natural gradient play, there's
no direct analysis tools we could borrow from literature for the analysis of natural gradient play. Our analysis depends on two key lemmas. The first is sufficient ascent lemma on ((((++)) (((())) for each natural gradient step (Lemma 26). Another key lemma (Lemma 24) states that the algorithm implicitly ensures that the policies never go near the boundary of the probability simplex. i.e., it can be uniformly lower-bounded by प. (a,1a)>
Vt. Combining the two lemmas,
4A1AA, M+ (1-))²)
can be concluded that the ascent value ((0(++1)) (0(1)) can be bounded by NE-gap(O''s (0)) plus
a A max, |A, [M bias term (Lemma 27 and 28), thus the proof is finished by standard telescoping technique and choosing an appropriate X.
Compared with gradient play, natural gradient play manages to reduce the time complexity by max; [AA:] factor. Further, gradient play only guarantees the minimal NE-gap smaller than c, while natural gradient play guarantees the average NE-gap along the trajectory smaller than To the best of our knowledge, this is the best time complexity bound for the softmax parameterization in a MPG.
6 An Illustrative example
This section aims to gain a better understanding of the four gradient play algorithms, (8), (10), (15), and (17). To better justify our theoretical results and provide additional insights, we choose a carefully designed simple two-player game so that our theoretical results can be easily revealed from the empirical observations. However the four algorithms also works for settings with more agents. Due to space limits, we defer the simulation with more agents in Appendix A.
The reward table as well as the performance of the four algorithms are shown in Figure 1. Comparing the log-barrier regularized algorithms to the unregularized counterparts, one can see that the regular- ized dynamics converge faster but with bias induced by the regularizer. This finding corroborates
'Code be found in https: http://tthht.cccaaaaa///////////
sof tmax-MPC

---

the analyses given in Theorem 6 and 7. By contrast, the unregularized dynamics are able to find policy with zero gap asympiotically, but tend to get stuck in regions where c(0(0) is very close to zero, as illustrated in Fig (a)(b). Specifically unregularized natural gradient play gets stuck around iteration 100-400 in region where the gradient norm and e(O(+) are both close to zero while the NE-gap is not. This corroborates the finding in Lemma Similar behavior can be observed for gradient play if we keep running the algorithm. In comparing the natural gradient play to gradient play algorithms, natural gradient play generally converges faster, which matches with our complexity analysis. However, natural gradient play with log-barrier regularization can suffer from numerical
instability due the 1/T, (t) (a,ls) term in the exponential factor. In this case, the stepsize needs to be chosen carefully. To bypass the numerical instability, we truncate the update step of natural gradient play with log- barrbrrr regularization by maximum absolute value of 1 for each entry.
7 Discussions and conclusions
We have established finite time iteration complexity bounds for gradient and natural gradient play under the softmax parameterization, considering both unregularized and log-barrier regularized dynamics, in the Markov potential game setting. To our best knowledge, these are the first finite time global convergence results for softmax gradient play for MPGs. However, our work suffers from the following limitations: firstly, the paper mainly focuses on MPG settings, which limits its application to general-sum Markov games; secondly, convergence results for the unregularized case relies on an extra assumption that the stationary points are isolated; thirdly, for the regularized case, we consider log- log-barrier regularization, which is admittedly stronger regularization compared with entropy regularization which is more frequently used in practice. Some limitations technical challenges, some might be caused by the fundamental difficulties of multi-agent learning. remains interesting open questions to sharpen the analysis, derive similar or better bounds for other regularizations, and to develop more fundamental understandings of multi-agent learning.
due to
Acknowledgment
Runyu Zhang supported by NSF AI institute: 2112085, ONR YIP: N00014-19-1-2217, NSF CNS: 2003111 I and NSF CPS: 2038603.
References
[1] P.-A. Absil, R. Mahony, and B. Andrews. Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization, 16(2):531-547, 2005.
[2] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift, 2020.
[3] S.-i. Amari. Business Media, 2012.
-eometril- methods in statistics, volume 28. Springer Science &
[4] Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pages 551-560. PMLR, 2020.
[5] M. Bowling and M. Veloso. An analysis of stochastic game theory for multiagent reinforcement learning. Technical report, Melleg Univ Pittsburgh Pa School of Computer Science, 2000.
[6] I.. Buçoniu, R. Babuška, and B. De Schutter. Multi-agent reinforcement learning: An overview. Innovations in multi-agent systems and applications-1, pages 183-221, 2010.
[7] S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
[8] R. Claes, T. Holvoet, and D. Weyns. A decentralized approach for anticipatory vehicle routing using delegate multiagent systems. IEEE Transactions on Intelligent Transportation Systems, 12(2):364-373, 2011.
10

---

[9] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning, arXiv preprint arXiv:2101.042333 2021.
[10] W. D. Dechert and S. O'Donnell. The stochastic lake game: A numerical solution. Journal of Economic Dynamics and Control, (0(9-10):1569-3
2006.
[11] R. Fox, S. McAleer, Overman, and I. Panageas. Independent natural policy gradient always converges in markov potential games. CoRR, abs/2110.106 2021.
[12] D. González-Sánchez and O. Hernández-Lerma, Discrete-time stochastic control and dynamic potential games: the Euler- Baler-Equation approach. Springer Science & Business Media, 2013.
[13] T. Haarnoja, H. Tang, P. Abbeel, and S. Levine. Reinforcement learning with deep energy-based policies. In International Conference on Machine Learning, pages 1352-1361. PMIR, 2017.
[14] Iñigo-Blasco, F. Diaz-del Rio, M. C. Romero-Ternero, D. Cagigas-Muñiz, and S. Vicente- Diaz. Robotics software frameworks for multi-agent robotic systems development. Robotics and Autonomous Systems, 60(6):803- 821, 2012.
[15] S. M. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In C. Sammut and A. G. Hoffmann, editors, Machine Learning, Proceedings of the Nineteenth International Conference (ICML 2002), University of New South Wales, Sydney, Australia, July 8-12, 2002, pages 267-274. Morgan Kaufmann, 2002.
[16] S. Khodadadian, P. R. Jhunjhunwala. S. M. Varma, and S. T. Maguluri. On the linear convergence of natural policy gradient algorithm. arXiv preprint 2rXiv:2105, 042441,44, 2021.
[17] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, Pérolat, D. Silver, and T. Graepel. A unified game-theoretic approach to multiagent reinforcement learning. arXiv preprint 17Xiv:1711.0000 2017.
[18] S. Leonardos, W. Overman, I. Panageas, and G. Piliouras. Global convergence of multi-agent policy gradient in markov potential games, arXiv preprint arXiv:2 200.0/ 0669, 2021.
[19] D. Levhari and L. Mirman. The great fish war: An example using dynamic cournot-nash solution. Bell Journal of Economics, 11(1):322-334, 1980.
[20] G. Li, Y. Wei, Y. Chi, Y. Gu, and Y. Chen. Softmax policy gradient methods can take exponential time to converge. CoRR, abs/2102. 11270, 2021.
[21] M. L. Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier, 1994.
[22] J. Liu and J. Wu. Multiagent robotic systems. CRC press, 2018.
[23] S. V. Macua, J. Zazo, and S. Zazo. Learning parametrie closed-loop policies for markov potential games. CoRR, abs/l 802.00899, 2018.
[24] Mei, C. Xiao, C. Szepesvari. and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6820-6822 PMLR, 13-18 Jul 2020.
[25] Mei, Dai, Xiao, C. Szepesvari, and D. Schuurmans. Understanding the effect of stochasticity in policy optimization. Advances in Neural Information Processing Systems, 34, 2021.
[26] D. Mguni. Stochastic potential games. arXiv preprint arXiv:2005. 2020.
[27] D. Mguni, Y. Wu, Y. Du, Y. Yang, Z. Wang. M. Li, Y. Wen, J. Jennings, and J. Wang. Learning nonzero-sum stochastic games with potentials. arXiv preprint 1rXiv:2103.0922: 2021.
[28] D. Monderer and L. S. Shapley. Potential games. Games and economic behavior, 14(1): 124-143, 1996.
[29] C. R. Rao. Information and the accuracy attainable in the estimation of statistical parameters. In Breakthroughs in statistics, pages 235-247. Springer, 1992.

---

[30] M. Roscia, M. Longo, and G. C. Lazaroiu. Smart city by multi-agent systems. In 2013 International Conference on Renewable Energy Research and Applications (ICRERA), pages 371-376. IEEE, 2013.
[31] L. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
[32] Y. Shoham, Powers, and Grenager. Multi-agent reinforcement learning: critical survey. Technical report, Technical report, Stanford University, 2003.
[33] Z. Song, S. Mei, and Y. Bai. When can we learn general-sum markov games with large number of players sample-efficiently. 2021.
[34] R. S. Sutton, D. A. McAllester, S. P. Singh, Y. Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pages 1057-1063. Citeseer, 1999.
[35] N. Tao, J. Baxter, and L. Weaver. A multi-agent, policy-gradient approach to network routing. In In: Proc. of the 18th Int. Conf. Machine Learning. Citeseer, 2001.
[36] A. G. Ventre, A. Maturo, Š. Booskoáá-Mayerovv and J. Kacprzyk. Multicriteria and Multiagent Decision Making with Applications to Economics and Social Sciences, volume 305. Springer, 2013.
[37] S. Zazo, S. V. Macua, M. Sánchez-Fernández, and Zazo. Dynamic potential games with constraints: Fundamentals and applications in communications, IEEE Transactions Signal Processing, 64(144 (4(114):806-36) -821,, 2016.
[38] K. Zhang, Z. Yang, and T. Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. arXiv preprint arXiv:1911.1063: 2019.
[39] R. Zhang, Z. Ren, and N. Li. Gradient play in multi-agent markov stochastic games: stationary points, convergence, and sample complexity. CoRR, abs/2106.0011 2021.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] [Yes]. [No]. or [N/A]. You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the
Checklist section does not count towards the page limit, In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes] See the contribution paragraph in
Section 1, assumptions in theorems, and Section 7: Discussions and Conclusions.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] As this work is primarily theoretical, we do not foresee any potentially negative societal impacts of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
12

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] The URL provided in Section 6
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A] Our experiments are deterministic
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using cxisting assets (c.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "iQ0Rpi5buDz", "reviewer": "Reviewer_4yF8", "summary": "The authors focus on the analysis of various algorithms/dynamics for Markov Potential Games, using softmax parametrization. Softmax parametrization is challenging as it creates more fixed points than Nash equilibria. Also Markov Potential Games include multiple Nash equilibria as well so this adds an extra challenge. The authors provide rates for policy gradient with softmax parametrization (note that only asymptotical was known prior to this work from Agarwal et al), natural policy gradient with softmax parametrization (here only results for single agent were known and the authors use a nice trick from Mei et al) and finally policy and natural policy gradient with log-barrier functions. The log-barrier function allows the authors to get rid of some parameter $c$ that can be arbitrarily large and typically slows down policy gradient. Mathematically speaking, this constant $c$ is because of the new fixed points that are created in the boundary due to softmax. ", "questions": "It feels that you cannot get rid of the mismatch coefficient in your rates. There are some other works though that use quantal response Nash idea and get rid of the mismatch coefficient. Is the existence of mismatch coefficient in your rates necessary even when you use log-barrier functions or you believe your analysis can be improved?  ", "limitations": "This is theoretical work", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros\nThe results are important, the authors add an important contribution related to softmax parametrization. Note that softmax parametrization is important for function approximation.\n\nCons\nThe techniques were more or less established before this work, the authors had to do a careful merge of the existing techniques and generalize the results to Markov Potential Games.  \n\nTypos: Section 3.2 title: Convergence rate, not fate. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PDlPemtpofO", "reviewer": "Reviewer_gv2p", "summary": "This paper analyzes the convergence of gradient play in Markov potential games where the players have softmax policies. Relying on recent advances in the analysis of policy gradients for softmax policies in single-agent RL, the authors first give asymptotic guarantees of convergence for both gradient play and natural gradient play and then subsequently provide finite-time convergence rates for both algorithms. These rates suffer due to a dependence on a non-uniform gradient-domination constant which may get arbitrarily large (as in the single agent case). To address this, the authors again continue as in the single-agent case and suggest doing gradient-play on a regularized version of the problem. When the amount of regularization is well chosen, the authors show that gradient-play from a fully random policy achieves fast convergence that is independent on the curvature constant 1/c but albeit with a worse dependence on the number of actions. They conclude with numerical experiments. \n", "questions": "1. Because of the Łojasiewicz Inequality it seems that all critical points of gradient-play are Nash equilibria of the game, but can there be saddle points in the potential function like those pointed out in [3] above?\n\n\n\n", "limitations": "Overall the paper is almost too straightforward an extension of prior works [1] and [3], and there does not seem to be anything particularly interesting about the combination. Making the exact contributions of this work clear would be helpful. Indeed the asymptotic global convergence guarantees and finite time rates are immediate from the potential structure and the Non-uniform Łojasiewicz Inequality. The idea of regularizing the problem seems to be a simple generalization of the idea in [1] to deal with the issue that 1/c might be arbitrarily large, but it is unclear if the multi-agent structure makes the derivation of the 1/c-less rate any more complex than in [1].", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is very well written and easy to follow, though the results are not very surprising and the proof techniques and paper overall seem to follow from [1] in a very straightforward way. While results do not in general need to be surprising to be interesting, it is unclear what the contributions of this paper are beyond the explicit rates which follow from simple non-convex optimization arguments combined with the main property of the problem: namely the Łojasiewicz Inequality. Such analyses have been done before in [2],[3] albeit without the softmax structure, and the softmax structure is handled in exactly the same way as in [1]. \n\nFurthermore, the problem setting of Markov potential games is not very well motivated. Indeed, practical examples of when these games arise and why one might formulate the problem as a MPG as opposed to a single agent problem would greatly help. \n\n[1] Agarwal et al. On the theory of policy gradient methods: Optimality, approximation, and distribution shift\n\n[2] Leonardo et al. Global convergence of multi-agent policy gradient in markov potential games\n\n[3] Zhang et al. Gradient play in multi-agent markov stochastic games: stationary points, convergence, and sample complexity", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LUD1zXQvAT", "reviewer": "Reviewer_99n7", "summary": "This paper studies the behavior of the gradient play when the policies are modeled via softmax surrogate.\nGradient play can be either first-order (policy gradient) or second-order (natural policy-gradient) method. \nIn contrast to the previous results that aim to establish results for the direct parametrization $p(a|s)=\\theta_{s,a}$, this work builds upon a series of results for Markov Potential Games and tries to establish rates of convergence to the corresponding Markov Nash equilibria.\n\nFor this setting, the authors provide three kind of results for the solution concept of Markov Nash equilibria in the generalization of identical interest RL game, known as Markov Potential Games.\n\n1) The asymptotic convergence of gradient play with softmax regularization\n2) Convergence rates which include some ``trajectory''-dependent constants\n3) The impact of log-barrier regularization in gradient play in the rates", "questions": "See the weakness section.\n\nAdditionally, I would like a clarification: Why in the single agent MDP the last row/first column does not copy automatically the result of the multi-agent case?\n\n\n\n", "limitations": "Non-applicable", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Summary of contributions. \nIn this general context, the main contributions of the manuscript under review can be stated as follows:\n(1a) In principle this is the first work that offers convergence rates for softmax policy gradient method.\n(1b) It should be mentioned that as far as the asymptotic convergence results have been already established last two years. Therefore, for the standard gradient play via softmax, I will encounter as novelty the convergence rate part\n\n(2a) The authors, via a manipulation of gradient dominance/ Polyak-Ljovasiewitz armamentum, guarantee fast convergence rates for the case of MPGs with Isolated equilibria. \n(2b) However, their convergence rate include a trajectory dependent constant which can be exponential worse.  It would be much more interesting if authors gives us examples where the worst case is achieved and how in practice this constants fluctuate. \n\n(3a) Finally, log-barrier is used for softmax regularization to get independent constant-style results.\n(3b) From applicability perspective, it is unclear how much harder is the inclusion of log-barrier to achieve the necessary result.\n(3c) Again I would like to notice that it is not the first work that applies log-barrier regularization in RL problems.\n\n\n\n\n\n\n\nEvaluation and recommendation. \n\nI believe that the core of the authors’ results is interesting: in particular, the derivation of convergence rates for softmax has been an interesting question recent years. However the positioning of the main draft, does not explain at all which are the important non-trivial observations which meshes well with existing results in the field, and which can provide further insights in the behavior of policy gradient methods to extract the promised results. \n\nI would expect from the authors a much more extensive analysis of the challenges & the burdens that the current submission tackles and what was the main intuition that leads authors to the usage of log-barrier regularization. At the end of the day, the usage of such strong regularization was a natural solution due to some collection of issues or just a matter of lack?\n\nAt the same time, the paper’s writing, presentation and positioning leaves a lot to be desired: \na fair number of results are presented in a confusing or misleading way (especially in\nregard to the state of the art), the writing style obfuscates the analysis and statements, and\nthe authors’ prose is often inconsistent with the results actually being proven.\n\nUltimately, I believe that a thoroughly rewritten version of this paper could be ultimately publishable\nin NeurIPS proceedings, but the submitted manuscript is not yet there. For this reason, I recommend a\nmajorly enlightening revision with the understanding that the paper should be rewritten from the ground\nup with emphasis on clarity, readability and ease of comparison to the existing literature on\nthe topic.\n\nIndeed, the line between asking for a border line acceptance and borderline rejecting the paper outright while encouraging resubmission at a later point is a blurry one. \nI am recommending a Border-Acceptance  because I find sufficient merit in the paper’s contributions; however, these should be stated in a way that is consistent with the Conference standards, an endeavor which will require a careful rewriting\n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "3-xGZ9dbA_c", "reviewer": "Reviewer_onZS", "summary": "This paper mainly analyzes the global convergence rates of decentralized Softmax policy play in MPG in detail, including both policy gradient and natural policy gradient, with and without log-barrier regularization, which numerically validates that the log-barrier regularized algorithms are indeed more robust against becoming trapped near undesirable non-NE stationary points. The theoretical results illustrates the complexity bounds of MPG, and the natural gradient play outperforms gradient play counterparts.", "questions": "1) What is the connection between Softmax policy and Boltzmann policy, log-barrier and entropy regularization, and how are they related to some exploration methods?\n2) The log-barrier method is introduced to avoid undesirable regions of policy space. What is the difference between this and the Trust region policy optimization based methods, e.g., MATRPO, HATRPO? How to illustrate the advantages of this regularization method?", "limitations": "Yes, the authors detail the limitations of this work and possible future research works. It could be better if the fundamental reasons of these limitations can be explained.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) One major concern for this work is the innovation of the proof sketch, which is mainly based on the properties of smooth functions and inequality transformations. \nThe authors should highlight the difficulties and solutions in the proof process.\n2) The authors give a comprehensive analysis of the convergence rate of the policy gradient methods in MPG. The theoretical results seems correct and fills the gap of Softmax policy play in MPG.\n3) The authors provide detailed descriptions of each term in the theoretical result, which are helpful for understanding.\n\nWeaknesses:\n1) Compared to entropy regularization methods, and even some trust region based methods, the authors should emphasize the necessity for log-barrier regularization. \n2) The authors should add some citations to illustrate the impact of Fisher information in line 57.\n3) The theoretical analysis contains a large number of inequality derivations, but the author omits some sources of inequality derivation, such as Lemma 29, Lemma 31, etc., which are difficult to understand.\n4) This article contains some notation errors and typos, such as the table in Introduction, the title of 3.2, etc.", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept