$O(T^{-1})$ Convergence of Optimistic-Follow-the-Regularized-Leader in Two-Player Zero-Sum Markov Games 
Authors: Yuepeng Yang
Cong Ma
Venue: ICLR 2023 poster (2023)
Keywords: multi-agent reinforcement learning
policy optimization
Markov game

Abstract: We prove that the optimistic-follow-the-regularized-leader (OFTRL) algorithm, together with smooth value updates, finds an $O(T^{−1})$ approximate Nash equilibrium in $T$ iterations for two-player zero-sum Markov games with full information. This improves the $\tilde{O}(T^{−5/6})$ convergence rate recently shown by Zhang et al (2022). The refined analysis hinges on two essential ingredients. First, the sum of the regrets of the two players, though not necessarily non-negative as in normal-form games, is approximately non-negative in Markov games. This property allows us to bound the second-order path lengths of the learning dynamics. Second, we prove a tighter algebraic inequality regarding the weights deployed by OFTRL that shaves an extra $\log T$ factor. This crucial improvement enables the inductive analysis that leads to the final $O(T^{−1})$ rate.

Published as a conference paper ICLR 2023
O(T-1) CONVERGENCE OF OPTIMISTIC-FOLLOWWTHH REGULARIZED-LEADER IN TWO-PLAYER ZERO-SUM MARKOV GAMES
Yuepeng Yang"
Cong Ma²
ABSTRACT
We prove that opiiiisi--foloov-teerrglliiiiidd -eaadee (OFTRL), together with smooth value updates, finds an O(T-")-aprroximate Nash equilibrium T iterations for two- player zero-sum Markov games with full information. This improves the ( convergence rate recently shown in the paper by Zhang et al. (202b)). The refined analysis hinges on two essential ingredients. First, the sum of the regrets of the two players, though not necessarily non-negative as in normal-fore games, is approximately non-negative in Markov games. This property allows us to bound the second-order path lengths of the learning dynamics. Second, prove a tighter algebraic inequality regarding the weights deployed by OFTRL that shaves an extra log T factor. This crucial improvement enables the inductive analysis that leads the final O rate.
INTRODUCTION
Multi-agent reinforcement learning (MARL) (Busoniu et al. 2008 Zhang et al. 2021) models sequential
decision-making problems in which multiple agents/players interact with each other shared environment.
MARL has recently achieved tremendous success in playing games (Vinyals et al.) 2219 Berner et al.
2019
Brown & Sandholm, 2019), which, consequently, has spurred a growing body of work on MARL; see Yang
& Wang (2020) for recent overview.
widely adopted mathematical model for MARL is the so-called Markov games (Shapley 1953 Littman
1994), which combines normal-form games Nash 1951) with Markov decision processes (Puterman 2014). In a nutshell, a Markov game starts with a certain state, followed by actions taken by the players. The players then receive their respective payoffs,, in normal-form game, and the same time the system transits to a new state as in a Markov decision process. The whole process repeats. As in normal-form games, the goal for each player is maximize her own cumulative payoff'. We defer the precise descriptions of Markov games to Section
In the simpler normal-form games, no-regret learning (Cesa- (Cesa-Bianchi & Lugosi| 2006) has long been used an effective method to achieve competence in the multi-agent environment. Take the two-player zero-sum normal-form game as an example. It easy show that standard no-regret algorithms such as follow-the- regularized-leade (FTRL) reach O (/2)-1/2)-appp (()=-1//)apprrxximmi) Nash equilibrium (Nash 1951 in T iterations. Surprisingly, the seminal paper Daskalakis et al. (201T) demonstrates that a special no-regret algorithm, built upon Nesterov's s excessive gap technique (Nesterov, 2005), achieves faster and optimal Ô(T-1) rate of convergence to the Nash equilibrium. This nice and last convergence was later established for optimistic variants of mirror descent (Rakhlin & Sridharan 2013) and FTRL (Syrgkanis et al. 2015). Since then,
DDepartment of Statistics, University of Chicago; Email: (yuepengyang, congm) @uchiccgo..eu

---

Published as a conference paper ICLR 2023
a flurry of research (Chen & Peng 2020; Daskalakis et al. 2021 Anagnostides et al., 2022a b Farina
et al. 2022) has been conducted around optimistic no-regret learning algorithms to obtain faster rate of convergence in normal-form games.
In contrast, research on the fast convergence of optimistic no-regret learning in Markov games has been scarce. In this paper, we focus on two-player zero-sum Markov arguably the simplest Markov game. /Zhang et al. (2022b) recently initiated the study of the aiimiisti-folloo-tt-errgaaaaaaai reearreerrrrlliieeeeleeeeerrr (OFTRL) algorithm in such setting and proved that OFTRL converges to an Ó(T-5/0) --pproxxmmate Nash equilibrium after T' iterations. In light of the faster O(T-)) convergence of optimistic algorithms in normal- form games, it is natural to ask
After T iterations, can OF an -aprrxxiaatt Nash equilibrium in two-player zero- sum Markov games?
In fact, this question has also been raised by Zhang et al. (022b) in the Discussion section. More promisingly, they have verified the fast convergence (i.c., O(T of OFTRL in simple two-stage Markov game; see Fig. therein.
Our main contribution in this work is answer this question affirmatively. through improving the ((T-5/6) rate demonstrated in Zhang et al. (2022b) to the optimal ((T"²) rate. The improved rate for OFTRL arises from two technical contributions. The first the approximate non-negativity of the sum of the regrets of the two players in Markov games. In particular, the sum is lower bounded by the negative estimation error of the optimal Q f-fuuction; see Lemma for the precise statement. This in stark contrast to the two-player gero-sum pormal-forn game (Anagnostides et al.) (022c) and the multi-playe general-sum normal- form game (Anagnostides et al., 2022b), which by definition, the sum of the external/swap regrets are non- negative. This approximate non-negativity proves crucial for us to control the second-order path length of the learning dynamics induced by OFTRL. In a different context- --ttttimeeary vare-ng zero-sum normal-fore games, Zhang al. (2022a) also utilizes sort of approximate non-negativity of the sum of the regrets. However, the source of this gap from non-negativity different: in Zhang et al. (2022a) it arises from the time-varying nature of the zero-sum game, while in our case with Markov games, comes from the estimation error of the equilibrium pay-off matrix by the algorithm itself.
Secondly, central to the analysis in finite-horizon Markov decision processes (and also Markov games) is the induction across the horizon. In our case, in order to carry out the induction step, we prove a tighter algebraic inequality related the weights deployed by OFTRL; see Lemma 4 In particular, an extra log I" factor. Surprisingly. this seemingly harmless log I'' factor is the key to enabling the above- mentioned induction analysis, and as by-product, removes the extra log factor in the performance guarantee of OFTRL.
shave
Note that as an imperfect remedy, Zhang et al. b022bb proposed modified OFTRL algorithm that achieves O(T=)) convergence to Nash equilibrium. However, compared to the vanilla OFTRL algorithm considered herein, the modified version tracks two Q-functions, adopts a different Q-function update procedure that can be more costly in certain scenarios, and more importantly diverges from the general policy optimization framework proposed in IZhang et al. (2022b). Our work bridges these gaps by establishing the fast convergence for the vanilla OFTRL.
Another line of algorithms used for solving Nash equilibrium is based on dynamic programming (Perolat jt al. 2013 Zhang et al. [0226] Cen et al. 202T). Unlike the single-loop structure of OFTRL, the dynamic programming approach requires nested loop, with the outer-loop iterating over the horizons and the lones-loops solving a sub-game through iterations. This requires more tuning parameters, one set for cach subproblem/layer. Such kind of extra tuning was documented in Cen et al. (202T). The nested nature of dynamic programming also demands one to predetermine a precision e and estimate the sub-game at each horizon to precision c/H. This is less convenient in practice compared to single-loop algorithm like the
2

---

Published as conference paper ICLR 2023
OFTRL study, where such predetermined precision not necessary. Another recent paper Cen et al. also discusses the advantages of single-loop algorithms over those with nested loops.
2022
1.1 RELATED WORK
Optimistic no-regret learning in games. Our work is mostly related to the line of work on proving fast convergence of optimistic no-regret algorithms in various forms of games. Daskalakis al. (2011) provide the first fast algorithm that reaches Nash equilibrium form games. Later, with the same setup, Rakhlin Sridharan 2013) prove a similar fast convergence for optimistic mirror descent (OMD). Syrgkanis al. (2015) extend the results multi-player general-sum normal-form games. In addition, Syrgkanis et al. show that when all the players adopt optimistic algorithms,
O(T-1) rate in two-player zero-sum normal-
their individual regret is at most OTT33/4) This is further improved to O(T-5/6 in the special two-player zero-sum case (Chen & Peng, 2020 More recently, via detailed analysis of higher-order smoothness, Daskalakis et al. (2021); Anagnostides et al. (2022a) manage to improve the individual regret guarantee of optimistic hedge to O(T in multi-player general-sum normal-form games, matching the result in the two-player case. A similar result is shown by Anagnostides al. (202bb) with different analysis using self-concordant barriers as the regularizer.
Several attempts have been made extend the results on optimistic no-regret learning in normal-form games to Markov games. Wei et al. (2021) design a decentralized algorithm based on optimistic gradient descent ascent that converges to a Nash equilibrium at an Ó(T-1/2) rate. Closest to us is the work by Zhang et al. (2022b) which shows an 5/76) convergence of OFTRL to the Nash equilibrium in two- player zero-sum Markov games and an ((T-3/4) convergence to a coarse correlated equilibrium in multi- player general-sum Markov games. Most recently, Erez et al. (2022) prove an O(T-1/1) individual regret for OMD in multi-player general-sum Markov games.
Two-player zero-sum Markoy games. Our work also fits into the study of two-player zero-sum Markov
games [Shapley] 1953: Littman 1994). Various algorithms (Hu & Wellman 2003 Littman 1994 Zhao
jt al. 2021 Cen al.) 2021) have been proposed the full information setting, where one assumes the players have access to the exact state-action value functions. In particular, Zhao et al. (202T); Cen et al.
12021) use optimistic approaches for normal-form games as subroutines to extend the O(T ") convergence rates to two-player zero-sum Markov games. particular, they provide last iterate convergence guarantees well. However, in doing so, their algorithms require one to approximately solve normal-form game in each itcration.
In the bandit setting, Bai & Jin (2020); Xie al. (2020); Bai et al. (2020); Liu et al. 2021); Zhang al. (2020) study the sample complexity of two-player zero-sum Markov games. In addition, Sidford et al. (220)); Jia et al. (2019;; Zhang al. (2020); Li et al. (2022) investigate the sample complexity under a generative model where one can query the Markov game at arbitrary states and actions. Last but not least, recently two-player zero-sum Markov games have been studied in the offline setting (Cui & Du 2022 Yan let al., (022), where the learner is given a set of historical data, and cannot interact with Markov games further.
PRELIMINARIES
This section provides the necessary background on Markov games and optimistie-followttte-ggggaa leader (OFTRL).
3

---

Published as a conference paper ICLR 2023
Two-player zero-sum Markov games. Denote by S. finite-horizon time- inhomogeneous two-player zero-sum Markov game, with H the horizon, S the state space, A (resp. B)) the action space for the max-player (resp. min-player),
[PA]RE]H] the transition probabilities, and r = {rx) he и the reward function. We assume state space S and action spaces A, B to be finite and have size S, A, B, respectively, and takes value in [0, 1]. Without loss of generality, we assume that the game starts at a fixed state 81 E S. Then at each step h, both players observe the current state 8n E S. The max-player picks an action ds E A and the min-player picks action by E B simultaneously, Then the max- alayer (resp. min-player) receives the reward Th (s), aj. bn) (resp. -rh ($n, Cn bn ), and the game transits step h + with the next state 8/+1 sampled from (. Sh, ah, by.) The game ends after H steps. The goal for the max- max-player is to maximize her total reward while the min-player seeks to minimize the total reward obtained by the max-player.
Markoy policies and value functions. Let {Pu kejj) be the Markov policy for the max max-erayee, where (.(. s) E AA is the distribution of actions the max- max-player picks when seeing state at step h. Here, A denotes the set of all probability distributions on the space X. Similarly, the min-player is equipped with Markov policy hen We define the value function of the policy pair (14, 2) step / to be
(s) = Ey.
Er(s: ai, bi) 8h
where the expectation is taken w.r.t. the policies {uss Marz and the state transitions {Prkon. Similarly, one can define the Q-function as
(s, Ey,,v
Σn
rrssi (i,t,) 8h. 8, an a, bn =b
Li=h
In words, both functions represent the expected future rewards received by the max-player given the current state or state-action pair.
Best responses and Nash equilibria. policy (v) ka. best response) such that for any E S and h E [H].
Fix a Markov policy v for the min-player. There exists a Markov
(1) sup VA ((s),
where the supremum is taken over all Markov policies. To simplify the notation, we denote v (s) =
v (P)) (s). Similarly, we can define V/ (s). It known that a pair (μ²", u²) of Markov policies exists and n², are best responses to the other, i.e., V/2 .²" (8) vtt" (s) vit'+(s) for all 8 S and h E [H]. Such a pair (n*, v²) is called a Nash equilibrium (NE). We may denote the value function and Q-function under any Nash equilibrium (H²,, 2=*) as
=
=
which are known to be unique even if there are multiple Nash equilibria Shapley 1953). The goal of learning in two-player zero-sum Markoy games is find an e a-approximation the NE defined as follows.
Definition (e-approximate Nash equilibrium). Fix any approximation accuracy 0. A pair (H, v) of Markov policies is an e-approximate Nash equilibrium if
NE-gap(u, v)
(si) se.
(1)
4

---

Published as conference paper ICLR 2023
Algorithm 1
for solving two-player zero-sum Markov games Stepsize 7/ reward function 7, probability transition function IP.
Input:
Initialization: 2% 0 for all h [H]
For iteration to T, do
Policy Update: for all state 8 E S, horizon h E [M].
ws [0%4 (s, + we 1/t (1.00) (0000)
1 (a 8) & exp
Σ
(2a)
us [(Q)) [4:] (s, + we IT (sx6))
(b] s) x exp
(2b)
Value Update: for all s S, a E b E from h to
(s,s,, = (1- (s,a, + a (rn + Ph ((hht)) Q @h+z2h+2l) (s,
(3)
Output average policy: for all E S, [H]
T
T
(... 8) = Σ
2 a (11s), 1n(.1s) Σ (1
(4)
An interlude: additional notations. Before explaining OFTRL, introduce some additional notations to simplify things hereafter. Fix any [H] E For any function Q S x A x B + R, we may consider (s,,'s)) be A B matrix and pn(- 8), (. s) be vectors of length A and B, respectively. Then for any policy (Jh, 2/) at horizon we may define
[PT Qui] (s) = Eampa (1) ((ss) a, b)],
[M]] Q] (8, = Bu-nun (Q(,
[Qua] (s, = E (11s b)].
The term [M]] Qun] (s) can also be written in the inner product form (un, Qua) (s) or (vn, Q mn) (s). It easy to check that for fixed a and h, the left hand sides of these definitions are standard matrix operations. In addition, for any V S + R, we define the shorthand
[AV] (s, a, 6) (...Fa((....) (V (V(')),
which allows to rewrite Bellman updates of V and Q as
vn] (s). V (s) = [MT Q' "hhvv
( a, = (n a, b) + [PAVW[H]] (s)
Now we are ready to introduce the petimistic-followe eggularizedlleader (OFTRL) algorithm for solving two-player zero-sum Markov games, which has appeared in the paper by /Zhang et al. (2022b) See A for the full specification.
In nutshell, the algorithm has three main components. The first the policy update using weighted OFTRL for both the max and min players. As one can see, compared to the standard ballow-the-regularizee leader algorithm, the weighted OFTRL adds loss predictor (Qt-ly=11]66 a) and deploys weighted update
5

---

Published as a conference paper ICLR 2023
according the weights (wi)ssss. which we shall define momentarily. The second component the backward value update ) using weighted average of the previous estimates and the Bellman updates. The last essential part is outputting weighted policy (4) over all the historical policies. As one can realize, weights play a big role in specifying the OFTRL algorithm. In particular, we set
H+1 H+
=f =
II j=++1
(1-a)),
Wa
02 01 II j= - 0₃)
(5)
which are the same choices in the paper by (Zhang et al. 2022b).
3 MAIN RESULT AND OVERVIEW OF THE PROOF
With the preliminaries in place, we are in position state our main result for OFTRL in two-player sero Markov games.
Theorem 1. Consider Algorithm 7 with 1j = C2 for some constant Cy S 1/8. The oulput policy pair (j,, 6) satisfies
NE-gap(A, D) 320C, 11 log(AA)
T
Several remarks on Theorem D are in order. First, Theorem [ demonstrates that OFTRL can find an -app----aeo Nash equilibrium in 7' iterations. This improves the ((T-5/6) rate proved in the prior work (Zhang et al. 2022b), and also matches the empirical evidence provided therein. While the paper by Zhang et al. (2022b) also provides a modified OFTRL algorithm that achieves an Ô(T-)) rate by maintaining two separate value estimators (one for the max-p max-player and the other for the min-player), the OFTRL algorithm studied herein is more natural and also computationally simpler. Second, this rate is nearly unimprovable even in the simpler two-player zero-sum normal-form games (Daskalakis al. (011). It is also worth pointing out that algorithms with Ó(T-') rate have been proposed in the literature (Cen et al. 2021| Zhao et al., (02T). However, compared to those algorithms, OFTRI does not require one to approximately solve normal-form game in each iteration. Lastly, Theorem allows any C, E 108 while C = 1/8 is optimal for the bound on NE-gap.
Before embarking on the formal proof, we would like immediately provide an overview of our proof techniques.
Step controlling NE-gap using the sum of regrets and estimation error. In the simpler normal-form game (i.e., without any state transition dynamics in Markov games), it is well known that NE-gap is controlled by the sum of the regrets the two players. This would also be the case for Markov games if in the policy update (2) by OFTRL, we use the true Q-function Q7, instead of the estimate Oi As result, intuitively, the NE-gap in Markov games should be controlled by both the sum of the regrets of the two players and also the estimation error 102/ 1i see Lemmal
Step 2: bounding the sum of regrets. Given the extensive literature on regret guarantees for optimistic algorithms (Anagnostides al. 2022c bj Zhang al. 20226), it relatively easy to control the sum of the regrets to obtain the desired O(7 rate; see Lemma 2 The key is to exploit the stability in the loss vectors.
Step 3: bounding estimation error. It then boils down to controlling the estimation error |[Q] lool in which main technical contributions lie. Due to the nature of the Bellman update 33) it not hard obtain a recursive relation for the estimation error; see the recursion (17). However, the undesirable part that the estimation error depends the maximal regret between the two players, instead of the sum of the
6

---

Published as conference paper ICLR 2023
regrets. This calls for technical innovation. Inspired by the work of Anagnosiides al. (2022c by in normal- form games, we make an important observation that the sum of the regrets Is approximately non-negative. particular, the sum lower bounded by the negative estimation error 1Q 2% b see Lemma 6 This lower bound together with the upper bound in Step 2 allows us to control the maximal regret via the estimation error (19). which further yields recursive relation (20) involving estimation errors only. Solving the recursion leads to the desired result.
4 PROOF OF THEOREM
In this section, present the proof of our main result, i.e., Theorem T We first define few useful
notations. For each step h [H], each state s E S, and each iteration & [T), we define the state-wise weighted individual regret as
(eg
max PLEAA 1=1
Σ oi (ul -1h. (o),
(6a)
(0g),((8)
= max vl E
Σ
0, (v/ -v, ((2)) ((0)))(h))))))))))))))))) (s).
(6b)
We also define the maximal regret as
regi. max max (regi,
sE8
that maximizes the players and the states. In addition, for each step h E [H], and each iteration / E [T].
we define the estimation error of the Q-function as
%% = 11 lo
With these notations in place, we first connect the NE-gap with the sum of regrets (s) + regh well as the estimation error 6
Lemma 1. One has
NE-gap(D, D) 5 Σ max (regh, (s) rog),(()) + >
[=1
See Section B.I for the proof of this lemma.
It then boils down to controlling max, (regh. (s) reg% and Et= a4 The following two lemmas provide such control.
7

---

Published as conference paper ICLR 2023
Lemma 2. For every [1]. every E S, and every iteration E [T]. one has
2H (log A)
16nH3
15) =
+ +2
a.lliil11 (-1)1
(7a)
np
t
|1 ( (8) ( |
81
2H
(log B)
16nH
2
+ 2n
aglppil11 s) - 1/h (-1
(7b)
1tt
1 8) - - I)
81
As a result, when 1j = C2
H for some constant Cy S 1/8, one has
3C, H log(AB) 4n
max (regi,, (s) 20)) S
at (1 - -) 1. |s]l (8)
+ +11r1(118 - s)l
See Section B.2 for the proof of this lemma.
Lemma 3. Choosing C. H for some constant C, S 1/8. for all h [H] and E [T], we have that
5 H log( (AB)
57, S
t
See Section B.3 for the proof of this lemma.
Combine Lemmas with Lemma to arrive at the desired conclusion that when v) C,,H-2 for some constant C, < 1/8.
H
NE-gap(i, D)
max (regT, (8) - 2eg7,
+
Σ
h=1
t=1
H
3C H3 log(AB)
56 2 H1 log(AB)
2
Otp
T
h=1
30 1 11 log( (AB)
20c -0e H AB)
< 2H
T
T
320C 1
1 H log(
T
where the penultimate inequality uses the following important lemma we have alluded to before. Lemma 4. For all one has
S 1 (1 1 !
(9)
111
8

---

Published as conference paper ICLR 2023
On the surface, this lemma shaves an extra log & factor from simple average of the sequence {1/i) ist (ef. Lemma A.3 in the paper by Zhang al. (2022b)). But more importantly, it shines in the ensuing proof of Lemma 3 by enabling the induction step. See Section B.4 for the proof of Lemma 4 and see the end of Section B.3 for the comment the benefit of this improved result.
5 DISCUSSION
In this paper, we prove that the value updates, converges to an -appoxxmaeo Nash equilibrium two-player zero-sum Markov games. This improves the 5/0) rate proved the paper Zhang et al. (2022b). Quite a few interesting directions are open. Below we single out a few of them. First, although our rate is unimprovable in the dependence on T, is likely sub-optimal in its dependence on the horizon H. Improving such dependence and proving any sort of lower bound it are both interesting and important for finite-horizon Markov games. Second, we focus on the simple two-player zero-sum games. is an important open question to see whether one generalize the proof technique herein to the multi-player general-sum Markov games and to other solution concepts in games (e.g., coarse correlated equilibria, and correlated equilibria).
algorithm, together with smooth
REFERENCES
loannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 736- 749, 2022a.
Ioannis Anagnostides, Gabricle Farina, Christian Kroer, Chung-We Wei Lec, Haipeng Luo, and Tuomas Sandholm. Uncoupled learning dynamics with o(logt) t) swap regret in multiplayer games, arXiv preprint arXiv:2204.11417 2022b.
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. arXiv preprint arXiv:2203./2056, 2022c.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. International conference machine learning, pp. 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170, 2020.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: arXiv: 1912,06800 2019.
Noam Brown and Tuomas Sandholm. Superhuman ai for multiplayer poker. Science, 365(6456))885-889, 2019.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2): 2008
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. 2021.
9

---

Published as conference paper ICLR 2023
Shicong Cen, Yuejic Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence policy optimization in zero-sum markov games. arXiv preprint arXiv:2110000550, 2022.
Nicolo
and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence external and swap regrets. Advances in Neural Information Processing Systems, 33:18990-18899, 2020.
Qiwen Cui and Simon S Du. When is offline two-player zero-sum markov game solvable? arXiv preprint vrXiv:2201.03522 2022.
Constantinos Daskalakis, Alan Deckelbaum, and Authony Kim. Near-optimal no-regret algorithms for zero- sum games. In Proceedings of the twenty-second annual ACM-SIAM symposium Discrete Algorithms, pp. 235-254. SIAM, 2011.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-27616, 2021.
Liad Erez, Tal Lancewicki, Uri Sherman, Tomer Koren, and Yishay Mansour. Regret minimization and convergence equilibria in general-sum markov games. arXiv preprint arXiv:2207.1421 14211 2022.
Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung Wei Lee, Christian Kroer, and Tuomas
Sandholm. Near-optimal no-regret learning for general convex games. arXiv preprint (rXiv:2206.08742 2022.
Junling Hu and Michael P Wellman. Nash q-learning for general-sun stochastic games. Journal of machine learning research, 4(Nov): 1039-109,, 2003.
Zeyu Jia, Lin F Yang, and Mengdi Wang. Feature-based q-learning for two-player stochastic games. arXiv preprint arXiv:/906.000 00423, 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Gen Li, Yuejie Chi, Yuting Wei, and Yuxin Chen. Minimax-optinat multi agent rl in zero-sum markov games with generative model. arXiv preprint arXiv:2208. 10458, 2022.
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pp. 7001-7010. PMLR, 2021.
John Nash. Non-cooperative games. Annals of mathematics, pp. 286 295, 1951.
Yu Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM Journal on Optimization, 16(1):235-249, 2005.
Julien Perolat, Bruno Scherrer, Bilal Piot, and Olivier Pietquin. Approximate dynamic programming for two-player zero-sum markov games. In International Conference on Machine Learning, pp. 1321-1329. PMLR, 2015.
Martin L Puterman. Markoy decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
10

---

Published as conference paper ICLR 2023
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. volume 26, 2013.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):0995-1100 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pp. 2992-3002. PMLR, 2020.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert Schapire. Fast convergence of regularized learning in games. Advances in Neural Information Processing Systems, 28, 2015.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czameeki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):300-354, 2019.
Chen- Yu Wei, Chung-Wer Lee, Mengxiao Zhang. and Haipeng Luo. Last-iterate convergence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Conference on learning theory, pp. 1259-42999 PMLR, 2021.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. Conference on learning theory, pp. 3674-3682. PMLR, 2020.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. Model-based reinforcement learning minimax-optimal for offline zero-sum markov games. arXiv preprint arXiv:2206.0044. 2022.
Yaodong Yang and Jun Wang- An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:2011.00588 2020.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based aulti rl in zero-sum markov games with near-optimal sample complexity. Advances Neural Information Processing Systems, 33: 1166-1178, 2020.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp. 321-384, 2021.
Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero- sum games. arXiv preprint arXiv:2201.127:0 2022a.
Runyu Zhang, Qinghua Liu, Huan Wang, Caiming Xiong, Na Li, and Yu Bai. Policy optimization for markov games: Unified framework and faster convergence. arXiv preprint arXiv:2206.026640, 2022b.
Yulai Zhao, Yuandong Tian, Jason D Lee, and Simon S Du. Provably efficient policy gradient methods for two-player zero-sum markov games. arXiv preprint arXiv:2102.08903, 2021.
PROPERTIES OF of
This section collects few useful properties of the sequences {athes and fathesissie Some of these results have appeared in prior work (Tin et al. 2018 Zhang et al., 20226). For completeness, we include all the proofs here.

---

Published as conference paper ICLR 2023
To help reading, we repeat the definitions below: for each
1, and
i define
H +
04 o
and
(10a)
H +
0 0
(1 0z)-
(10b)
j=+1
Lemma 5. Fix any t 2 1. The following properties are true:
1. The sequence (athisis sums to 1, i.e. Ei= of =1
2. For all sist l, one has at si/t.
3. For the relative weight defined by wi = ai/at (note that this is the same for every t 2 i), we have
Wi
af
H
$ H.
W
a
4. The sequence {at)ssis is increasing in i.
5. On the sum of squares of the weights, we have
Σ (aa))
of < +2
6. For any non-increasing sequence {b:) lsige one has
Σ aafb
bi.
Proof. Property follows directly from the definitions of {at
Jsiiee
Now we move on to Property It trivially holds for i = t. Therefore we focus on the case when Sis By definition, we have
a = 0; II (1-a,) < II a1- = II
j-1
(11)
j=i+1 H+j
j=++1
j=1+1
where the inequality holds since a; < for all Expanding the right hand side of (1], we have
< S t, and the last relation is the definition of ay.
i+1
1-1
H+i+1
H+i+2
H+t H+
where we only keep the first numerator and the last denominator. Property then follows.
Property 3 is trivial. Hence we omit the proof. In addition, Property 3 implies Property 4 since H4i-1 1.
12

---

Published as a conference paper ICLR 2023
For Property 5, the first inequality holds since 0 S a, S 1 for all 1 S i For the second inequality, one has
-
Σ> (
(H+ +1+
1 (H 1)( +i)
i=2
Expanding this as a telescoping sum, we see that
5 Σ
H H+i-1 #
1=2
1 +1+ H+1
= H2
Lastly, for Property 6, we have
Σ bbb.
Σ b. Σ (aj - 7o;
Let in = sup, fot < 1/4). Since {at} is increasing in i (ef. Property 4) and Ei= of = 1 (cf. Property 1), know that in is well defined, i.e., 1 S in I t. Since {ai)igr (resp. (brlige) is increasing (resp. increasing), we have aj < 1/tt and 6; > bi, for all i < ip. As aesult, we obtain ( < (af-11/1 b1/))b,, for all i < ig- Similarly, one has of > 1/t and b; S bi, for all i > iu. which implies (a) 1/t)b; S (a) - b/ for all i > ip. Take these two relations together to see that
S Σ (af 1/t)bio O,
where the last equality uses the fact from Property 1, namely Ei= at = 1.
B PROOF OF SUPPORTING LEMMAS IN SECTION
B.1 PROOF OF LEMMA
Invoke Lemma C.1 in the paper by Zhang et al. (022b) to obtain
NE-gap(A, D) = (si)(ss)) - (i Vi - (s
(s1)
"
2
max
max
[1t, Q7h)) - (vi N,1 pa)) (8)
jet
By the definition of the output policy (f, D). one has
T
max Ket, (10%) - (ut, Qi (m)) (8) = max Σ at
of Kut Q7 - -1V1, O7 m1))) (s).
13

---

Published as conference paper ICLR 2023
Replacing the true value function Q7 with the value estimate Q yields
T
max [1, 02PN) - (v² (QA) (s) & max pi
of (ir - (2t) p (s) + Σ air
a 1=1
where we recall 6% = 10% Qiloo- The proof finished by taking the above three relations together with the observation that
max (sg + regh.2())
oi K - (2.) (()) (s).
.
B.2 PROOF OF LEMMA
We prove the regret bound for the max- max-player (i.e., bound 7a The bound 7b) for the min-player can be obtained via symmetry.
First, we make the observation that, the policy update in Algorithm for the max-player is exactly the OFTRL algorithm (i.e., Algorithm 4 in the paper by Zhang et al. (2022b) with the loss vector St = @ (/ -), the recency bias M, we 1///-11/-11111 +), and learning rate T) n/w,. Therefore,
we can apply Lemma B.3 from Zhang et al. (022b to obtain
(s) = max
at (k+ - . (s)
jut
= al max at
Σ
wi ( (n - ph) 1hi (s)
i=1
(log A)
+
|| [w
- 11
(s.))))
(12)
11
Wi
1=1
=:r
Wi Wi-1
|1 (. 8)
th (- 1)
(13)
81)
1=2
E/Er
where we have used the fact that ue = =a/aa. We now move on to bound the term Err, Use (a + 6)² z 20² + 262 see that
[1Q02/ 0 v/ 1 (s.
22 - '/ (s. I1 +2 1 '/ O - (s, 12
21 - 113 + 2112 8) 1/-11 s)
where the second line uses Holder's inequality and the fact that ||Q) 1| s H. In view of the update rule (3 for the Q-function, we further have
11Q -i-''la
l1oo = 11- + + (ra + Ph ((rh+)) T ( 1lbs a, max (1|Q5 '1l Il + Ph [(uh+1] T Qu+1 (/4]]lo))
H.
14

---

Published as a conference paper ICLR 2023
As result, we arrive the bound
Erri S 21ja
Σ wi (a 112 + 11 11 10) - -0/1)/11 (-1
2 Σ aga + 2m H 2 abllut (8) -/ s)
where we again use the relation wi = at/a! Since faslige is decreasing in i, we can apply Property in
Lemma to obtain
Σ aaja
H z t
3H
i=1
where the second inequality follows from Property 5 in Lemma
5 In all, we see that
H
Err S
Hn
| 8) - ()
(14)
Substitute the upper bound (1) for Err, into the master bound (2) to obtain
Qg (log A)
r (s)
5
ErTI Errz
"
2H
(log A)
+ 61HH3
2n
1 8) -0, s)
nyt
1
[ 8) - (-1 |))
81
1=2
where in the first inequality we use or = (H + 1)/ +1 S 2H/L. Since || (- 8) 1//+((1 (-18)] 2
and of & 1/t (see Property 2 of Lemma 5). we can take the term i = 1 out and reach
2H (log A)
16nH3
regh, (s) s
+ H a
nt
( 8) ph (- .)
811
This finishes the proof of the regret bound 77) for the max-player. The bound (7b) for the min-player can be obtained via symmetry.
Combine the two bounds
7a and
7b see that
2H log(AB)
32mHH'
regh, (s) + (
<
nt
a
2nHH2 ot
(luÃ(--1)) 2 (-11(11))))) o)
(15)
81
1=2
||
(.(()s))) 1 ss]l3)
(16)
15

---

Published as conference paper ICLR 2023
When S 1/(8/13), one has
at- 21 aj
a/-1
S 2nl aj
81 S -4nlt
Snj
where we have used Property of Lemma i.e., oj 1-1 /at 2 1/H. Consequently, with = C, -2 for some constant C2 1/8, the bound (16) reads
, H log AB)
max (regi, (s) + re))
AnH a4 (11ah(-1
( () -10 (-1 + +112(-18) ' ())))
where we assume the choice of players is non-trivial, i.e., AB 2 2.
B.3 PROOF OF LEMMA 3
By Lemma C.2 in the paper by Zhang et al. (2022b), for any [H 1], we have the recursive relation
8%
1 regh+1:
(17)
where we recall regi+1 max, max fregh
Step Bounding rog
view of this recursion (17). one needs control the maximal regret regi+1
over the two players. Lemma 2 (s):
provides us with precise control of the individual regrets regh, (8) and
30,- H3 (log AB)
regú, (s) x
H
Σ C (s) - |s)
(18a)
t
30, H3 (log AB)
regh,2 5
2n11 Σ aille (:1)) - (-1
(18b)
where we have substituted 17 C. H for C, S 1/8 and AB 2 We have also ignored the negative terms on the right hand sides of 7a and (b). Therefore, to control individual regrets, it suffices to bound the second-order path lengths 2n Σt 2 o [ s) 1 1h (- s)ll and 2nH Σ a s) 1 (- s) To this end, the following lemma proves crucial, whose proof is deferred to the end of this section.
Lemma 6. For each and s, one has
regh regi (8) + regh 2
words, Lemma 6 reveals the approximate non-negativity the sum of the regrets. This together with the upper bound g in Lemma 2 implies
2
aillii (-)
1/ 4-1 - |>)ll + (- " {)]
2=2
3C, n
H² log(AB)
af
2t
H
16

---

Published as conference paper ICLR 2023
Feeding this back to (8a and (8b). we obtain
50 50.1H3 log
1
regi
max max (regh, (s)) - im 1,2
+
0
(19)
t
H
1m1
Step 2: Bounding %- Substituting the maximal regret bound 19) into the recursion
17
we arrive at
af + 50, H log( (AB)
%
(20)
We continue the proof of Lemma 3 via induction on h. More precisely, we aim to inductively establish the claim
1f
2(H-N) H
5C, log(AB)
6%
1+
(21)
t
k'=h
First note that the induction hypothesis holds naturally for h H 8// 0 for all 1 L T. Now
assume that the induction hypothesis true for some v h + 1 S H and for all 1 sts S T. Our goal is to
show that (2I) continues hold for the previous step h and for all t S. By the recursion (20 and the induction hypothesis, one has for any 1 < t S T: 5C, 3 log(AB)
0%
1
0f +
H Σ
2(H-N²
50 H log( AB)
5C,- H3 log( AB)
1 +
1
+
H
t
t
h 1++
Apply Lemma to obtain
50, 7 H3 log(AB)
50,11 H llog(A) 1
1 H
t
This leads the conclusion that
2(H-N)
5C 5C H3 log( AB)
5C, H3
log (AB)
8
1+
1+
1 H
k'=h+1
Σ
H
1
1
2(H 2(H-''++ 5C, H log(AB)
50, H² log(AB)
H
M=h+1
1
2(H-
5C-1 3 log( AB)
-Σ 1+ (1+
L
W=h
This finishes the induction.
This bound on 5% can be further simplified by
H
2(H-h')
5C,-1 H3 log(AB)
5%
<
H
M=
211
5C, H log(AB)
<
5e - 1
Ha log(AB)
t
17

---

Published as a conference paper ICLR 2023
This finishes the proof, and we are left with proving Lemma
Proof of Lemma 6
Recall that
(s) + regh,
max ai,
ab Kal. (014) - (vt, (Qt)TTM) (6).
Replace the estimation Qh with Q% to obtain
Σ of Kud (20%) - (v),(Q)) (()) (s)
(8) + reg),2(s) 2 max jel .21
at Kut (0h -27) v/) (ut, (0t - Q7) T Twhi (8)
Lower bounding the term involving Q 24 yields
(s) + (0) 2 max .
Σ at Kn', Qivh) - (v (vt,(12) (w (s) -2 Σ af
where recall of = 112 - Qilloo. Now observe that Ei=1 aqph( () and Ein agu 8) are valid policies, which implies
Σ at Kut - (vt, (Q1) m4,1 (s)
max at
Eajeh
Σ
aiih 1) (8)
(() -(11 Qi
Σ
(8)
max at at
1=1
i=1
((= agvh
)) (5)
aiph
.hh
Σ aivh (5)
.227
Σ
aisch
1=1
0.
Combine the above two inequalities finish the proof.
In the end, it is worth pointing out that without the improved inequality in Lemma 4, one would necessarily incur an extra log T' factor in each induction step. Consequently, the recursion will fail due the explosion at a rate of (log T
B.4 PROOF OF LEMMA
We prove the claim via induction. The base case / = 1 is true since of . 1 = S 1 1/H. Now assume that the inequality (9) holds for some t 2 1, and we aim to prove that it continues to hold at + 1. We first make the observation that for all <
++1
d =
II
(1 - a²) = (1 - a
II (1 a,) = (1 - -1-114))a/.
j gmi+1
18

---

Published as a conference paper ICLR 2023
This allows us to rewrite Σ 0/41 1 as
H+
1=1 ? = (1 - a1+1)
a++
Σ a
+ at+1
t+1
1=1
s a++1)
1
-
1 + t 1+1
01+1
H
where the second line follows from the induction hypothesis. Note that a++1 the derivation as
H+1
We can continue
#+++1
++1
++
I +
H+t+1 + H+t+1 t+1
H
1 H H+++1 t+1 (1+ H H+t+1 t+1
t+1
1
1 + H
1+1
This finishes the proof.
19


Reviews:
[{"review_id": "vPgHJrloa7I", "reviewer": "Reviewer_krEs", "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": "This paper studies solving two-player zero-sum Markov games using follow-the-regularized-leader-type algorithms. The authors propose an algorithm based on Zhang et al., 2022 and proved it has an $O(1/T)$ convergence rate to the Nash equilibrium. ", "summary_of_the_review": "The authors propose an algorithm for two-player zero-sum Markov Games with an $O(1/T)$ convergence rate to find the Nash equilibrium. I find the proposed algorithm and theory lack novelty and importance given Zhang et al., 2022, therefore I recommend a reject.", "strength_and_weaknesses": "Pros:\n- The presentation is clear.\n- The proof is correct.\n\nCons:\n- It lacks novelty for either the algorithm design or the proof. The proposed algorithm itself actually can be regarded as a special realization of  Algorithm 1 in Zhang et al. 2022, which makes the algorithm design less important. The proof also reuses lots of statements in Zhang et al., 2022 (like the proof of Lemma 1). Finally, the proposed algorithm enjoys the nearly same order of convergence rate as Algorithm 10 in Zhang et al., and I am not convinced that the proposed algorithm is simpler than Algorithm 10 in Zhang et al. since it is already simple enough. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "fZ8emSAZuA", "reviewer": "Reviewer_ceBg", "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": "The paper focuses on two player zero-sum stochastic games. It is shown that Optimistic FTRL (together with value update step) converges to a Nash equilibrium in $O(1/T)$ improving the result of Zhang et al. ", "summary_of_the_review": "I think the paper is above the bar for acceptance. If there was a score 7, I would put 7, between 6 and 8 I choose 6 but I am in favor of the paper getting in. The only reason I chose 6 is that there have appeared many papers of the same flavor/similar results the last year and reading this paper did not make me feel surprised. If needed, I will increase my score.\n\nCorrection: After checking thoroughly the paper by Zhang et al, there is an improved analysis that also achieves O(log T/T) regret, so the improvement is not as large as was mentioned in the paper. Can you argue about that? As far as I can see now, the result improves from \\log  T/T to 1/T regret. The comment/question has been addressed.", "strength_and_weaknesses": "The result is important and adds value to the current growing literature. The techniques are interesting, exploiting ideas from papers by Anagnostides et al that the sum of regrets should be non-negative (in this case are not too negative) and moreover this leads to prove that second-order path length is bounded. This idea can give a log T/T bound but the authors with extra effort remove the log T dependence.\n\nThere is another work (appeared a bit later I think) that achieves 1/T convergence using Optimistic MWU and the notion QRE (quantal response) Nash. The ideas are somewhat different as in the latter the KL divergence is used as a potential. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Ew3Q4rbdmDd", "reviewer": "Reviewer_j4CZ", "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": "This paper studies the convergence of optimistic policy optimization algorithms in two-player zero-sum Markov Games. The main result of the paper is to show that the Optimistic-Follow-The-Regularized-Leader (OFTRL) algorithm achieves an $O(T^{-1})$ convergence rate to the Nash Equilibria of the game. This settles the open problem raised in the recent work of (Zhang et al. 2022), which showed an $\\tilde{O}(T^{-5/6})$ convergence rate for the same algorithm.", "summary_of_the_review": "The paper resolves an open question on the fast convergence in Markov Games using an interesting new technique, though the result sounds a bit thin and lacking in extensions / additional results. ", "strength_and_weaknesses": "Strengths:\n\n* The paper settles the open problem raised by Zhang et al. (2022) about $T^{-1}$ convergence rate of OFTRL in Markov Games. In particular, the same work designed a modified OFTRL algorithm achieving $\\tilde{O}(T^{-1})$ rate, and also showed that empirically the original OFTRL algorithm does achieve $T^{-1}$ rate. Plus, $T^{-1}$ convergence in the easier case of zero-sum normal-form games (NFGs) is a well-established result (e.g. Rakhlin and Sridharan, 2013) and follow directly from the RVU property of OFTRL. These all seem to be urging for a positive resolution to this problem, which this paper did.\n\n* The main technique—establishing an *approximate* non-negativity of the summed regret for zero-sum NFGs with slowly changing game matrices—seems interesting and new to this line of work. As the authors mentioned, the technique of using non-negativity of regrets to establish second-order path length bounds has been used in other contexts such as fast convergence of swap regrets. However, to my best knowledge, this is its first application in Markov Games.\n\n* The topic of fast convergence in games should be of good interest to the RL/games community. \n\nWeaknesses:\n\n* Overall, the paper sounds a bit lacking in terms of completeness as for a conference paper on this topic (only one main theorem and no extensions / additional results etc). I wonder if the authors have thought about whether the techniques (approximate non-negative regret) or settings (zero-sum NFGs with slowly changing game matrices) could be useful in other problems? (For example, any relation to “time-changing zero-sum games”? see ref below). Having some additional results about related problems or techniques could genuinely improve the paper, in my opinion.  \nZhang, M., Zhao, P., Luo, H., & Zhou, Z. H. (2022). No-Regret Learning in Time-Varying Zero-Sum Games. arXiv preprint arXiv:2201.12736.\n\n* The claim of settling Zhang et al. (2022)’s open question needs to be discussed carefully, as that work also gives a modified OFTRL algorithm with the same $\\tilde{O}(T^{-1})$ rate. Currently this is discussed only in Section 3, and I suggest also adding some discussions in the introduction/related work where appropriate. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster