When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?
Authors: Ziang Song
Song Mei
Yu Bai
Venue: ICLR 2022 Poster (2022)
Keywords: reinforcement learning theory
multi-agent RL
Markov games
general-sum games

Abstract: Multi-agent reinforcement learning has made substantial empirical progresses in solving games with a large number of players. However, theoretically, the best known sample complexity for finding a Nash equilibrium in general-sum games scales exponentially in the number of players due to the size of the joint action space, and there is a matching exponential lower bound. This paper investigates what learning goals admit better sample complexities in the setting of $m$-player general-sum Markov games with $H$ steps, $S$ states, and $A_i$ actions per player. First, we design algorithms for learning an $\epsilon$-Coarse Correlated Equilibrium (CCE) in $\widetilde{\mathcal{O}}(H^5S\max_{i\le m} A_i / \epsilon^2)$ episodes, and an $\epsilon$-Correlated Equilibrium (CE) in $\widetilde{\mathcal{O}}(H^6S\max_{i\le m} A_i^2 / \epsilon^2)$ episodes. This is the first line of results for learning CCE and CE with sample complexities polynomial in $\max_{i\le m} A_i$. Our algorithm for learning CE integrates an adversarial bandit subroutine which minimizes a weighted swap regret, along with several novel designs in the outer loop. Second, we consider the important special case of Markov Potential Games, and design an algorithm that learns an $\epsilon$-approximate Nash equilibrium within $\widetilde{\mathcal{O}}(S\sum_{i\le m} A_i / \epsilon^3)$ episodes (when only highlighting the dependence on $S$, $A_i$, and $\epsilon$), which only depends linearly in $\sum_{i\le m} A_i$ and significantly improves over the existing efficient algorithm in the $\epsilon$ dependence. Overall, our results shed light on what equilibria or structural assumptions on the game may enable sample-efficient learning with many players.

Published as a conference paper at ICLR 2022
WHEN CAN WE LEARN GENERAL-SUM MARKOV GAMES WITH A LARGE NUMBER OF PLAYERS
SAMPLE-BFICIENNLLY?
Ziang Song
Song Mei
School of Mathematical Sciences, Peking University songziangêpku.
Department of Statistics, UC Berkeley songmei@berkeleey
edw.pukwueeeeuc.oo.o.oooo edu.en
Yu Bai
Salesforce Research yu.
ABSTRACT
Multi-agent reinforcement learning has made substantial empirical progresses in solving games with large number of players. However, theoretically, the best known sample complexity for finding a Nash equilibrium in general-sum games scales exponentially in the number of players due to the size of the joint action space, and there is a matching exponential lower bound. This paper investigates what learning goals admit better sample complexities in the setting of m-player general-sum Markov games with H steps, S states, and A, actions per player. First, we design algorithms for learning e-Coarse Correlated Equilibrium (CCE) in O(HSS maxism Ar/e²) episodes, and e-Correlated Equilibrium (CE) in
S max:5m A²/=²) episodes. This is the first line of results for learning CCE and CE with sample complexities polynomial in max A;. Our algorithm for learning CE integrates an adversarial bandit subroutine which minimizes a weighted swap regret, along with several novel designs in the outer loop. Second, consider the important special case of Markov Potential Games, and design an algorithm that learns an e-approximate Nash equilibrium within Ö OSSEsm A,/e²) episodes (when only highlighting the dependence on S, A,, and E), which only depends linearly in Eiem- A, and significantly improves over existing efficient algorithms in the dependence. Overall, results shed light on what equilibria structural assumptions on the game may enable sample-efficient learning with many players.
INTRODUCTION
Multi-agent reinforcement learning (RL) has achieved substantial recent successes in solving artificial intelligence challenges such GO (Silver et al., 2016; 2018), multi-player games with team play such as Starcraft (Vinyals et al., 2019) and Dota2 (Berner et al., 2019), behavior learning in social interactions (Baker et al., 2019), and economic simulation (Zheng et al., 2020; Trou et al., 2021). In many applications, multi-agent RL is able to yield high quality policies for multi-player games with a large number of players (Wang et al., 2016; Yang et al., 2018).
Despite these empirical progresses, theoretical understanding of when we can sample-efficiente solve multi-player games with large number of players remains elusive, especially the setting of multi-player Markov games. A main bottleneck here is the exponential blow-up of the joint action space-The total number of joint actions in a generic game with simultancous plays equal to the product of the number of actions for each player, which scales exponentially in the number of players. Such an exponential dependence indeed known to be unavoidable in the worst-case for certain standard problems. For example, for learning approximate Nash equilibrium from payoff queries in an one-step multi-player general-sum game, the query complexity lower bound of Chen et al. (2015) and Rubinstein (2016) shows that at least exponentially many queries (samples) is

---

Published as a conference paper at ICLR 2022
required, even when each player only has two possible actions and the query is noiseless. Moreover, for learning Nash equilibrium in Markov games, the best existing sample complexity upper bound also scales with the size of the joint action space (Liu et al., 2021).
Nevertheless, these exponential lower bounds do not completely rule out interesting theoretical inquiries- there may well be other notions of equilibria additional structures within the game that allow us to learn with a better sample complexity. This motivates us to ask the following
Question: When can we solve general-sum Markov games with sample complexity milder than exponential in the number of players?
This paper makes steps towards answering the above question by considering multi-player general- sum Markov games (MGs) with m players, H steps. S states, and A, actions per player. We make two lines of investigations: (1) Can we learn alternative notions of equilibria with better sample complexity than learning Nash; (2) Can the Nash equilibrium be learned with better sample complexity under additional structural assumptions on the game. This paper makes contributions on both ends, which we summarize as follows.
We first design an algorithm that learns the e-approximate Coarse Correlated Equilibrium (CCE) with O max4e[m] A//=²) episodes of play (Section 3). Our algorithm CCE-V V- LEARNING is a multi-player adaptation of the Nash V-Learming algorithm of Bai et al. (2020).
We design an algorithm CE- V-LEARNINN which learns the stricter notion of e-approximate Correlated Equilibrium (CE) with O( maxic(m] [m] A?/=²) episodes of play (Section 4). For Markov games, these are the first line of sample complexity results for learning CE and CCE that only scales polynomially with max A,, and improves significantly in the A; dependency over the current best algorithm which scales with IIe(()) A,.
Technically, our algorithm CE- CE-V-LEANNING makes several major modifications over CCE- V-LEARNING in order to learn the CE (Section 4.2). Notably, inspired by the connection between CE and low swap-regre learning, we use mixed-expert Leader algorithm within its inner loop to achieve low swap-regret for a particular adversarial bandit problem. Our analysis also contains new results for adversarial bandits weighted swap regret and weighted regret with predicable weights, which may be of independent interest.
Finally, we consider learning Nash equilibrium in Markoy Potential Games (MPGs), an important subclass of general-sum Markov games. By reduction to single-agent RL, we design an algorithm NASH-CA that achieves ( H E Eigjm) As/e²) sample complexity, where + max S Hm is the bound the potential function (Section 5). Compared with the recent result of Leonardos et al. (2021), we significantly improves the dependence from their 1/55.
1.1 RELATED WORK
Learning equilibria in general-sum games The sample (query) complexity of learning Nash, CE, and CCE from samples in one-step (i.e. normal form) general-sum games with players and A; actions per player has been studied extensively in literature (Hart & Mas-Colell, 2000; Hart, 2005; Stoltz, 2005; Cesa- Bianchi & Lugosi. 2006; Blum & Mansour, 2007; Fearnley et al., 2015; Babichenko & Barman, 2015; Chen et al., 2015; Fearnley & Savani, 2016; Goldberg & Roth, 2016; Babichenko, 2016; Rubinstein, 2016; Hart& & Nisan, 2018). It is known that learning Nash equilibrium requires exponential in m samples in the worst case (Rubinstein, 2016), whereas CE and CCE admit efficient poly(m, maxism A,) -ammle complexity algorithms by independent no-regret learning (Hart & Mas-Colell, 2000; Hart, 2005; Syrgkanis et al., 2015; Goldberg & Roth, 2016; Chen & Peng. 2020; Daskalakis al., 2021). Our results for learning CE and CCE can be seen as extension of these works into Markov games. We remark that even when the game is fully known, the computational complexity for finding Nash in general-sum games PPAD-hard (Daskalakis, 2013).
Markoy games Markov games (Shapley, 1953; Littman, 1994) is a widely used framework for game playing with sequential decision making, e.g. in multi-agent reinforcement learning. Algorithms with asymptotic convergence have been proposed in the early works of Hu & Wellman (2003); Littman (2001); Hansen et al. (2013). A recent line of work studies the non-asymptotic sample complexity for learning Nash in two-player zero-sum Markov games (Bai & Jin, 2020; Xie al., 2020; Bai et al.,
2

---

Published as a conference paper at ICLR 2022
2020; Zhang al., 2020; Liu al., 2021; Chen et al., 2021; Jin al., 2021; Huang et al., 2021) and learning various equilibria in general-sum Markov games (Liu et al., 2021; Bai et al., 2021), building techniques for learning mongle-agent Markov Decision Processes sample-efficiently (Azar et al., 2017; Jin et al., 2018). Learning the Nash equilibrium in general-sum Markov games are much harder than that in zero-sum Markov games. Liu et al. (2021) present the first line of results for learning Nash, CE, and CCE in general-sum Markov games; however their sample complexity scales with Iigm A, due to the model-based nature of their algorithm. Algorithms for computing CE in extensive-form games has been widely studied (Von Stengel & Forges, 2008; Celli et al., 2020; Farina et al., 2021; Morrill et al., 2021), though we remark Markov games and extensive-form games are different frameworks and our results do not imply each other.
Markov potential games Lastly, a recent line of works considers Markov potential games (Macua al., 2018; Leonardos et al., 2021: Zhang al., 2021), a subset of general-sum Markov games in which the Nash equilibrium admits more efficient algorithmss Leonardos et al. (2021) gives a sample-efficient algorithm based on the policy gradient method (Agarwal al., 2021). The special case of Markov cooperative games is studied empirically in e.g. Lowe et al. (2017); Yu et al. (2021). For one step potential games, Kleinberg et al. (2009); Palaiopanos et al. (2017); Cohen et al. (2017a) show the convergence to Nash equilibria of no-regret dynamics.
2 PRELIMINARIES
We present preliminaries for multi-player general-sum Markov games as well as the solution concept of (approximate) Nash equilibrium. Alternative solution concepts and other concrete subclasses of Markov games considered in this paper will be defined in the later sections.
Markov games A multi-player general sum Markov game (MG; Shapley (1953); Littman (1994)) with m players can be described by a tuple MG(H, S, {A P, {rr),= where H is the episode length, is the state space with |S| = S. AA, is the action space for the 7 player with [A,] = A assume A,
Without loss of generality, of joint actions taken by all the players and A = A1 X ..... x An denote the joint action space. Throughout this paper we assume that S and A, are finite. The transition probability P = (I,, hee(F)] is the collection of transition matrices, where FA, (-|s, a) As denotes the distribution of the next state when actions a are taken at state s at step h. The rewards r = {TR, The (1) se[m] is the collection of reward functions for the ith player, where (s. a) E [0, 1] gives the deterministic' reward of 7th player if actions are taken at state s step h. Without loss of generality, we assume the initial state $1 is deterministic. A key feature of general-sum games is that the rewards r; are in general different for each player and the goal of each player is to maximize her own cumulative reward.
[A.]. We let == (a1, am,) denote the vector
Markoy product policy, value function A product policy is a collection of m policies π := {n, bejm) where n; is the general (potentially (estory-dependent) policy for the i-th player. We first focus on the case of Markov product policies, in which म; {Tr, S -
and Th, (a:|s) (s) is the probability for the 7th player to take action a; at state s at step h. For a policy i and E [m]. we use T=; == [T jemm)iii to denote the policy of all but the 2th player. The value function (s) S + R is defined the expected cumulative reward for the 8th player when policy is taken starting from state s and step h:
H
= E
(wr an) Lhi=h
$
(1)
Best response & Nash equilibrium For any product policy π = {TT: Jejmm the best response for the ith player against m is defined as any policy 1 such that V (t (81) = sup;; VT ViL (s1). For any Markov product policy, this best response is guaranteed to exist (and be Markov) as the above maximization problem is equivalent to solving a Markov Decision Process (MDP) for the 4h player.
We will also use the notation V/,"" *(s1) to denote the above value function VT, 1= ((1).
Our results can be straightforwardly generalized Markov games with stochastic rewards.
3

---

Published as a conference paper at ICLR 2022
We say is a Nash equilibrium (e.g. Nash (1951); Pérolat et al. (2017)) if all players play the best response against other players, i.., for all E [m]]
(si(()) = f '(81).
Note that in general-sum MGs, there may exist multiple Nash equilibrium policies with different value functions, unlike in two-player zero-sum MGs (Shapley, 1953). To measure the suboptimality of any policy π, we define the NE-gap as
NE-gap (T) == max sup Vi, (s1) ViT,(ss)
8c/m]
For any 2 0, we say is e-approximate Nash equilibrium (s-Nash) if NE--gap(r) S.
General correlated policy & Its best response A general correlated policy i is a set of H maps {Th, : 12 x (S
A)a-11 S Aa)ne(m) The first argument of ςд is random variable w E Ω sampled from some underlying distribution, and the other arguments contain all the history information and the current state information (unlike Markov policies in which the policies only depend on the current state information). The output of Ta is general distribution of actions in A A X X Am (unlike product policies in which the action distribution a product distribution).
For any correlated policy π = ( )E(H)) and any player i, we can define a marginal policy T- as set of H maps T- == {TTh.- Ω x (S x A)*~1 S + A AA_))E Me())) where A-; := Ai .... x A A:+1 X ..... Am. and the output of -h,-i is defined as the marginal distribution of the output of πT restricted to the space A_,. For any general correlated policy æ, we can define its initial state value function (s1) similar as (I). The best response value of the 7th player against i
Vit." '(81) = sup,, Vi, "(s1), where Vi, "(s1) is the value function of the policy (Mi, -i:) (the 1th player plays according to general policy μı, and all other players play according to T- and the supremum is taken over all general policy μ4 of the 7th player.
Learning setting Throughout this paper we consider the interactive learning (i.e. exploration) setting where algorithms are able play episodes within the MG and observe the realized transitions and rewards. Our focus is on the PAC sample complexity (i.e. number of episodes of play) for any learning algorithm to output an approximate equilibrium.
2.1 EXPONENTIAL LOWER BOUND FOR LEARNING APPROXIMATE NASH EQUILIBRIUM
The focus of this paper is the setting where the number of players m is large. Intuitively, as the joint action space has size |A| I A, which scales exponentially in m (if each A, > 2), naive algorithms for learning Nash equilibrium may learn all r; (a by enumeratively querying all E A. and this costs exponential in m samples. Unfortunately, recent work shows that such exponential in m dependence is unavoidable in the worst-case for any algorithm-there is an exp()(mm) sample complexity lower bound for learning approximate Nash, even in one-xtep general-sum games (Chen et al., 2015; Rubinstein, 2016) (see Proposition A.2 for formal statement).
This suggests that the Nash equilibrium as a solution concept may be too hard to learn efficiently for MGs with large number of players, and calls for alternative solution concepts or additional structural assumptions on the game in order to achieve an improved m dependence.
EFFICIENT LEARNING OF COARSE CORRELATED EQUILIBRIA (CCE)
Given the difficulty of learning Nash when the number of players is large , consider learning other relaxed notions of equilibria for general-sum MGs. Two standard notions of equilibria for games are the Correlated Equilibrium (CE) and Coarse Correlated Equilibrium (CCE), and they satisfy [Nash} c {CE} C {CCE) for general-sum MGs (Nisan et al., 2007).
We begin by considering learning CCE (most relaxed notion above) for Markov games. Definition (e-approximate CCE for general-sum MGs). We say a (general) correlated policy a is an e-approximate Coarse Correlated Equilibrium (s-CCE) if
(v
*(11) VTT((1)) Se. 1,8
max
4

---

Published as a conference paper at ICLR 2022
We say iT is an (exact) CCE the above is satisfied with 0.
The following result shows that there exists an algorithm that can learn e-approximate CCE in general-sum Markov games within O S maxie|m] A./e²) episodes of play.
Theorem (Learning e-approximate CCE for general-sum MGs), Suppose we run the CCE-V- LEARNING algorithm (Algorithm for all m players and
11' maxie|m] Au
S
K 2 O
8²
episodes log(m max A, (pHSK/(pE)) is a log factor). Then with probability at least p. the certified policy ßे defined in Algorithm 2 is an E-CCE, i.e. maxig[m] (V (Vi,;-- ((si="sss111))))))())( V(,,
Mild dependence on action space For small enough E, the sample complexity featured in Theo- rem 2 scales as O(115 S maxielm] A Most notably, this is the first algorithm that scales with max;g(m] A,, and exhibits a sharp difference learning Nash and learning CCE in view of the exp(2((m)) lower bound for learning Nash in Proposition A.2. Indeed, existing algorithms such as Multi-Nash- Algorithm with CCE subroutine (Liu al., 2021) does require ( A II A./s²) episodes of play, which scales with [i A; due to its model-based nature. We achieve significantly better dependence on A; and also S, though slightly worse H dependence.
Overview of algorithm and techniques Our CCE- V-LEARNING algorithm (deferred to Ap- pendix B.I due to space limit) is multi adaptation of the Nash V-Learning algorithm of Bai et (2020); Tian et al. (2021) for learning Nash equilibria in two-player zero-sum MGs. Similar as Bai et al. (2020), we show that this algorithm enjoys "no-regret" like guarantee for each player at each (h, 8) (Lemma B.3). We also adopted the choice of hyperparameters in Tian et al. (2021) so that the sample complexity has slightly better dependence in //. When combined with the "certified correlated policy" procedure (Algorithm 2), our algorithm outputs a policy that is s-CCE. Our certified policy procedure is adapted from the certified policy of Bai et al. (2020), and differs in that ours output a correlated policy for all the players whereas Bai et al. (2020) outputs a product policy. The key feature enabling this max;e[m] A; dependence is that this algorithm uses decentral- ized learning for each player to learn the value function (V), instead of learning the Q function (as in Liu al. (2021)) that requires sample size scales IIim()] AG. The proof of Theorem 2 is in Appendix B.
4 EFFICIENT LEARNING OF CORRELATED EQUILIBRIA (CE)
In this section, we move on considering the harder problem of learning Correlated Equilibria (CE). We first present the definition of CE in Markov games.
Definition 3 (Strategy modification for th player). A strategy modification & == {6h, (b.s))(()))))
for player i is a set of H x S functions Φb.= (S x A)^ x A, + AA.. A strategy modification o can be composed with any policy give a modified policy o defined as follows: At any step
and state s with the history information Th-1 = ($1, a1. 8h an ah-1), if chooses to play (a1...., am)) the modified policy & will play (ai,...,a, ai-1 Ub. (Th 0;), 1i.1.......................... am) We use &; denote the set of all possible strategy modifications for player i.
Definition 4 (e-approximate CE for general-sum MGs). We say a (general) correlated policy is an E-approximate CE (c-CE) if
(V Vi,,(31) S
max sup 8E/va] gE
We say π is an (exact) CE if the above is satisfied with
Our definition of CE follows (Liu et al., 2021) and is a natural generalization of the CE for the well-studied special case of one-step (i.e. normal form) games (Nisan et al., 2007).
5

---

Published as a conference paper at ICLR 2022
4.1 ALGORITHM DESCRIPTION
Our algorithm CE-V-LEARNING (Algorithm 1) builds further on top of CCE- --LEA-NNG and Nash V-Learning, and makes several novel modifications in order learn the CE. The key feature of CE-V-LEARNING is that it uses a weighted swap regret algorithm (mixed-expert FTRL) for every (s, h, i). At a high-level, CE-V BE-V-LEARNING consists of the following steps:
Line 6-11 (Sample action using mixed-expert FTRL): For each (h, we maintain A; "sub- experts" indexed by b' [A.] (Each sub-expert represents an independent "expert" that runs her own FTRL. algorithm). Sub-expert 1' first computes an action distribution y (.) E A.A via Follow-the Seeoowthh-Regee Shhe-Regularized-Le Leaderr (FTRL; Line 8). Then employ two-step sampling procedure to obtain the action: First sample a sub-expert b from a suitable distribution μ computed from {4" [A.] then sample the actual action an,s from q².
Line 13-17 (Take action and record observations): Player takes action an,i and observes other player's actions, the reward, and the next state. Sub-expert b then computes a loss estimator and weight according to the observations, which will be used in future FTRL updates.
Line 19 (Optimistic value update): Updates the optimistic estimate of the value VA, using step-size or and bonus 3,-
Finally, after executing Algorithm for K episodes, we use the certified correlated policy procedure (Algorithm 2) to obtain our final output policy म. This procedure is a direct modification of the certified policy procedure of (Bai et al., 2020) and outputs a correlated policy (because the randomly sampled & and l in line and line 4 of Algorithm 2 are used by all the players) instead of product policy. The same procedure is also used for learning CCEs earlier in Section 3.
Here we specify the hyperparameters used in Algorithm 1:
a 1) + +t,, n vi/(A,tt, B.= B.=cH² A i/H2
(2)
The constants of used in Algorithm 2 is defined
at Im (1 an), af aj 1k
(3)
Note that for any 2 1, haiss sums to one and defines a distribution over [t].
4.2 OVERVIEW OF TECHNIQUES
Here we briefly overview the techniques used in Algorithm 1.
Minimizing swap regret via mixed-expert FTRL The key technical advance in our Algorithm I over CCE-V- -CE-V-LEARNING and Nash V-Learning is the use of mixed-expert FTRL (Line 6-11). The purpose of this is to allow the algorithm to achieve low swap regret at each (h, s) in a suitable sense-Foo For one-step (normal form) games, it is known that combining low-swap-regret learning for each player leads to an approximate CE (Stoltz, 2005; Cesa-Bianchi & Lugosi, 2006). To integrate this into Markov games, we utilize a celebrated reduction from low-swap-regret learning usual low-regret learning (Blum& & Mansour, 2007), which for any bandit problem with A; actions maintains A; sub-experts each running its own FTRL algorithm. Our particular application builds upon the two-step randomization scheme of Ito (2020) which first samples a sub-expert 6 and the action from this sub-expert. The distribution p(-) for sampling the sub-expert is carefully chosen by solving a linear system (Line 10) so that also coincides with the (marginal) distribution of the sampled action, from which the reduction follows.
FTRL with predictable weights Applied naively, the above reduction does not directly work for our purpose, as our analysis requires minimizing the weighted swap regret with weights of, whereas the reduction of Ito (2020) relies crucially on the vanilla (average) regret. We address this challenge by using a slightly modified FTRL algorithm for each sub-expert that takes in random but predictable weights (i.e. depending fully on prior information and "external" randomness). We present the analysis for such FTRL algorithm in Appendix F.4, and the consequent analysis for the weighted swap regret in Appendix F.1-F33, both of which may be of independent interest.
Proposal distributions Finally, nuanced but important new design in CE- V-LEARNING is that all sub-experts compute a proposal action distribution sample the sub-expert and the associated action.

---

Published as a conference paper at ICLR 2022
Algorithm 1 CE-V-LEARNING for general-sum MGs (i-th player's version)
Require: Hyperparameters: {al hSsssss fai)s Imssis. fBihsisk. Initialize: For any (s, a, h), set (s) H, (s) - Set pn(als) + 1/A, (als)
1/A,, (a)(() < 0, No (8) + for all (V/, a. 1,, 8, E [A.] x [4.] x [H] x S [K].
2: for episode l I...., do
3: Receive $1-
4: for step h = H do
5: // Compute proposal action distributions by FTRL
6: Update accumulator 1 := (s.) <- (s.) + 1. Set de + af/at.
7: Let by < N% (sx) for all D' E [A.] for shorthand.
8:
Compute the action distribution for all sub-experts V' [At]:
dh (a|sh) %a exp (- (- (m/y/ EYe whir (b' ( (als:))
9:
// Sample sub-expert and action from (²())
Compute μr (+Isn) E [AA by solving na (-(s%) -i= (n((blsn) doh (-1sn).
11:
Sample sub-expert b jud. (-1sp). and then action an,i ~ oh (-(an). // Take action and feed the observations to sub-expert b
12:
13:
Take action a, observe the actions an,-s from all other players.
14:
Observe reward T4 (Sh, 4, aA.-i) and the next state sh-1 from the environment.
15:
Update accumulator for the sampled sub-expert: la := (5( < NR(5k) + 1.
16:
Compute and update loss estimator
H + 1 (ra,s + min V (+1,1($h+1), H h1]] fon, = a}
Ch, (clsp)
(alsh) + meo
Set whet. (b)sk) -- ut. I/ Optimistic value update
18:
19:
VA (8n) + (1 an) W.s (sx) + aa (ra,a (Sh, ah,i an + V V4+1, (8h+1) + B.).
Algorithm 2 Certified correlated policy 7े for general-sum MGs
1: Sample k Uniform( [K)-
2: for step h = 1,.... H do
+- N (s)) (the value of (xx) at the beginning of the k'th episode). 4: Sample I [t] with (P =) = af (c.f. Eq. (3)).
3: Observe 8h and
5: Update & < kg, (sx) (the episode at the end of which the state sn is observed exactly times).
6: Jointly take action (at,1, 0h,2, ah,m)
I[ (-1sn,, where n (1s.)))))) is the policy
(-,s(-(s)) at the beginning of the k'th episode.
Then, only the sampled sub-expert takes this action, and all other proposal distributions are discarded. This is different from the original algorithms of (Blum & Mansour, 2007; Ito, 2020) in which the FTRL update come after the sub-expert sampling and only happens
the sampled sub-expert. Our design is required here otherwise the sub-experts required to predict the next time when it is sampled in order to compute the weighted FTRL update, which is impossible.
4.3 THEORETICAL GUARANTEE
We are now ready present the theoretical guarantee for our CE-V-LEARNING algorithm. Theorem 5 (Learning e-approximate CE for general-sum MGs). Suppose we run the CE-V- LEARNING algorithm (Algorithm 1) for all m players for
H maxie(m) A.e.
H max:eim) A&e
K 2 o
+
2²
7

---

Published as a conference paper at ICLR 2022
episodes f log(m [mX A,HSK/(pE)) is log factor). Then with probability at least 1 - p. the certified correlated policy क defined in Algorithm 2 an E-CE, i.e. [a suPEE4, (V1,,5 (s1) V(, S
Discussions To the best of our knowledge, Theorem presents the first result for learning CE that scales polynomially with [m] A. which is significantly better than the best known existing algorithm of Multi-Nash-V VI with CE subroutine (Liu et al., 2021) whose sample complexity scales with [m A, Similar as in Theorem 2, this follows our CE-V-LEARNING
decentralized learning for each player learn the value function (V). We also observe that our sample complexity for learning CE is higher than for learning CCE by factor of Ó( H max,e[m] A,); the additional maxig(m) [m] A; factor is expected as CE is a strictly harder notion of equilibrium. The proof of Theorem can be found in Appendix C.
LEARNING NASH EQUILIBRIA IN MARKOV POTENTIAL GAMES
In this section, we consider learning Nash equilibria in Markov Potential Games (MPGs), an important subclass of general-sume MGs. Despite the curse of number of players of learning Nash in general-sum MGs, recent work shows that learning Nash in MPGs does not require sample size exponential in m, by using stochastic policy gradient based algorithms (Leonardos et al., 2021; Zhang et al., 2021). In this section, provide an alternative algorithm NASH-CA that also achieves mild dependence on m and an improved dependence on é by simple reduction to single-agent learning.
5.1 MARKOV POTENTIAL GAMES
We first present the definition of MPGs. Our definition the finite-horizon variant² of the definitions of Macua et al. (2018); Leonardos et al. (2021); ;); Zhang et al. (2021) and is slightly more general as we only require (4) on the total return. Throughout this section, π denotes a Markov product policy. Definition 6. (Markov potential games) A general-sum Markov game is Markov potential game if there exists a potential function mapping any product policy to a real number in [0, $ Pmax]] such that for any E [m]) any two policies TG, n. of the ith player. and any policy T= of other players, the difference of the value functions of the ith player with policies (T,, and (ml π T() is equals the difference of the potential function on the same policies, i.e.,
(81) (81) - D(T,, T-i) - (( m-)).
V. 1.3
(4)
Note that the range of the potential function 4 Pmax admits a trivial upper bound T Imax I m. (this can be seen by varying n, for one i at time). An important example of MPGs is Markov Cooperative Games (MCGs) where all players share the same reward r; =
5.2 ALGORITHM AND THEORETICAL GUARANTEE
We present simple algorithm NASH-CA (Nash Coordinate Ascent) for learning e-Nash in MPGs. As its name suggests, the algorithm operates by solving single-agent Markov Decision Processes (MDPs) one player time, and intrinsically performing coordinate ascent the potential function of the Markov game. Due to the potential structure of MPGs and the boundedness of the potential function, the local improvements of players across the steps can have an accumulative effect on the potential function, and the algorithm is guaranteed to stop after a bounded number of steps. We give the full description of the NASH-CA Algorithm 3. We remark that NASH-CA is additionally guaranteed to output pure-strategy Nash equilibrium (cf. Appendix D for definition).
Theorem 7 (Sample complexity for NASH-CA). For Markov potential games, with probability at least p. Algorithm 3 terminates within 400max/ steps of the while loop, and outputs an e-approximate (pure-streed sturesstrategy) Nash equilibrium. The total episodes of play is at most
(
P 3 SM All
4 Dma H² D1= Ar
K K=0
where log(
m M.S. maxisism Ag
log factor.
ED
"Our results can easily adapted the discounted infinite time horizon setup.
8

---

Published as a conference paper at ICLR 2022
Algorithm 3 NASHI-CA for Markov potential games
Require: Error tolerance :
1: Initialize: π = [T [T)e where ( (M.0)e for some deterministic policy Th.
2: while true do
3: Execute policy и for = O H of the total return under policy
episodes and obtain (T,((T) which the empirical average
4: for player 1,...,' m do
5: Fix - and let the 7th player run UCBVI-UPLOW (Algorithm 7) for K; =0 0 O
H² episodes and get new deterministic policy n.. _
6: Execute policy (#;, xー-)) for = O H" episodes and obtain (T, m-;) which the
empirical average of the total return under policy R-1).
7:
Set A, (#, -T4) (T).
8:
if mmx A, > e/2 then
9:
Update T + F where j = arg maxiemm] A,
10:
else
return π
Discussions For small enough E, the sample complexity for the NASH-CA algorithm in the above theorem is ( S A,/=²). As mmxx S mH, this at most scales with the number of players m Σ,sm A,, which is much better than the exponential in m sample complexity for general-sum MGs without additional structures. Compared with recent results on learning Nash via policy gradients (Leonardos et al., 2021; Zhang et al., 2021). the NASH-CA algorithm also achieves poly(m, max;sm A,) dependence, and significantly improves on the dependence from their & to g-3, In addition, our algorithm does not require assumptions on bounded distribution mismatch coefficient as they do, due to the exploration nature of our single-agent MDP subroutine.
Also, compared with the sample complexity bound Ö(H'' A,/E²) of the Nash-VI algo- rithm (Liu et al., 2021) for general-sum MGs (not restricted to MPGs), our NASH-CA algo- rithm doesn't suffer from the exponential dependence do achieve looser the dependence on E, yet overall our sample complexity is still better un- less E (2 A,)/([I A;) is exponentially small. The proof of Theorem 7 can be found in Appendix D.
thanks to the MPG structure. We
A lower bound To accompany Theorem 7, we establish a sample complexity lower bound of Q(H2 >n m Ai/s²) for learning pure-strategy Nash in MCGs and hence MPGs (Theorem E. in Appendix E). This lower bound improves in the A, dependence over the naive reduction to single- player MDPs (Domingues et al., 2021), which gives S max A,/=²), though loose on the S, H dependence. The improved A, dependence is achieved by constructing novel class of hard instances on one-step games (Lemma E.2), which may be of further technical interest. However, there is still a large gap between these lower bounds and the best current upper bound of either our m
O 1=1 A:/ea) or the Ö A,/E?) of Liu et al. (2021), which leave future work.
CONCLUSION
This paper investigates the question of when can we solve general-sum Markov games (MGs) sample- efficiently with a mild dependence on the number of players. Our results show that this is possible for learning approximate (Coarse) Correlated Equilibria in general-sum MGs, as well as learning approximate Nash equilibrium in Markov potential games. both cases, our sample complexity bounds improve over existing results in many aspects. Our work opens up many interesting directions for future work, such as sharper algorithms for both problems, sample complexity lower bounds, or how perform cumple-efficieee learning in general-sum MGs with function approximations. In addition to Markov potential games, it would also be interesting to explore alternative structural assumptions that permit sample-efficient learning.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
Ziang Song is partially supported by the elite undergraduate training program of School of Mathe- matical Sciences in Peking University.
REFERENCES
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1 16,, 2021.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Yakov Babichenko. Query complexity of approximate nash equilibria. Journal of the ACM (JACM), 62(4)) 2016.
Yakov Babichenko and Siddharth Barman. Query complexity of correlated equilibrium. ACM Transactions Economics and Computation (TEAC), (4)):199,.) 2015.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International Conference on Machine Learning, pp. 551-560. PMLR, 2020.
Yu Bai, Chi Jin, and Tiancheng Yu. Near-optimal reinforcement learning with self- Advances in Neural Information Processing Systems, 33, 2020.
Yu Bai, Chi Jin, Huan Wang. and Caiming Xiong, Sample-efficient learning of stackelberg equilibria in general-sum games. arXiv preprint arXiv:2102. 1494, 2021.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint arXiv: 1rXiv.190..07528. 2019.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dębiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 1911:699/2,00680, 2019.
Avrim Blum and Yishay Mansour, From external to internal regret. Journal of Machine Learning Research, 8(6), 2007.
Andrea Celli, Alberto Marchesi, Gabriele Farina, and Nicola Gatti. No-regret learning dynamics for extensive-form correlated equilibrium. arXiv preprint arXiv:2004.06603 2020.
Nicolo Sesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Xi Chen and Binghui Peng. Hedging in games: Faster convergence of external and swap regrets. arXiv preprint wxXi:20006.0495. 2020.
Xi Chen, Yu Cheng, and Bo Tang. Well-supported versus approximate nash equilibria: Query complexity of large games. arXiv preprint arXiv:1511.00785, 2015.
Zixiang Chen, Dongruo Zhou, and Quanquan Gu. Almost optimal algorithms for two-player markov games with linear function approximation. arXiv preprint arXiv:2102.07404 2021.
Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 6372-6381, 2017a
Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu. Almost-liness linear- time algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Anmual ACM SIGACT Symposium on Theory of Computing, pp. 410-419, 2017b.
10

---

Published as a conference paper at ICLR 2022
Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizen reinforcement learning. arXiv preprint arXiv:1510.08906, 2015.
Constantinos Daskalakis. On the complexity of approximating nash equilibrium. ACM Transactions Algorithms (TALG), 9(3):1-35, 2013.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. arXiv preprint (tth:2008,069244 2021.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic rein- forcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pp. 578-59785 PMLR, 2021.
Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium. arXiv preprint arXiv:2104.013 520, 2021.
John Fearnley and Rahul Savani. Finding approximate nash equilibria of bimatrix games via payoff queries. ACM Transactions on Economics and Computation (TEAC), 144): 2016.
John Fearnley, Martin Gairing, Paul W Goldberg, and Rahul Savani. Learning equilibria of games via payoff queries. J. Mach. Learn. Res., 16:1305-1344, 2015.
Paul W Goldberg and Aaron Roth. Bounds for the query complexity of approximate equilibria. ACM Transactions on Economics and Computation (TEAC), 4(4): 2016.
Richard W Hamming. Error detecting and error correcting codes. The Bell system technical journal, 1972):147-160, 1950.
Thomas Dueholm Hansen, Peter Bro Miltersen, and Uri Zwick. Strategy iteration is strongly polynomial for 2-player surn-aased stochastic games with constant discount factor. Journal of the ACM (JACM), 6011):1-16, 2013.
Sergiu Hart. Adaptive heuristics. Econometrica, 73(5): 73(5):1401-14) 400--143, 2005.
Sergiu Hart and Andreu Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, (885))11177111111 2000.
Sergiu Hart and Noam Nisan. The query complexity of correlated equilibria. Games and Economic Behavior, 108:401-410 2018.
Junling Hu and Michael Wellman. Nash q-learning for general-sum stochastic games. Journal of machine learning research, 4(Nov):1039-1069, 2003.
Baihe Huang, Jason Lee, Zhaoran Wang, and Zhuoran Yang. Towards general function approxima- tion in zero-sum markov games. arXiv preprint arXiv:2107. 14702, 2021.
Shinji Ito. A tight lower bound and efficient reduction for swap regret. Advances in Neural Information Processing Systems, 33, 2020.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 4868-488 4878, 2018
Chi Jin, Qinghua Liu, and Tiancheng Yu. The power of exploiter: Provable multi-agent in large state spaces. arXiv preprint arXiv:2106.0333 2021.
Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 533-542, 2009.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Stefanos Leonardos, Will Overman, loannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint 106.v:200000//90 2021.
11

---

Published as a conference paper at ICLR 2022
Michael L Littman. Markov games framework for aggett reinforcement learning. In Machine learning proceedings 1994, pp. 157-1633, Elsevier, 1994.
Michael Littman. Friend-or-foe q-learning in general-sum games. In ICML, volume 1, pp. 322-328, 2001.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pp. 7001-7010. PMLR, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch, Multi-agent actor- critic for mixed cooperative-comppettvve environments. arXiv preprint arXiv: /xXv://70.002275 2017.
Sergio Valcareel Macua, Javier Zazo, and Santiago Zazo. Learning parametric closed-loop policies for markov potential games. In International Conference on Learning Representations, 2018.
Dustin Morrill, Ryan D'Orazio, Marc Lanctot, James R Wright, Michael Bowling, and Amy R
Greenwald. Efficient deviation types and learning for hindsight rationality extensive games. In International Conference on Machine Learning, pp. 78 18-8882.. PMLR, 2021.
John Nash. Non-cooperative games. Annals mathematics, pp. 286-295, 1951.
Gergely Neu. Explore no more: Improved high-probabilityy regret bounds for non-stochastic bandits. arXiv preprint arXiv:/506.033:
2015.
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Gerasimos Palaiopanos, Ioannis Panageas, and Georgios Piliouras. Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos. arXiv preprint 11X3:017033011388 2017.
Julien Pérolat, Florian Strub, Bilal Piot, and Olivier Pietquin. Learning nash equilibrium for general- sum markov games from batch data. Artificial Intelligence and Statistics, pp. 232-241, PMLR, 2017.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp. 258-265. IEEE, 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittieserr, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
David Silver, Thomas Hubert, Julian Schritwieser,, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 2018.
Gilles Stoltz. Incomplete information and internal regret in prediction of individual sequences. PhD thesis, Université Paris Sud-Paris XI, 2005.
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. Fast convergence of regularized learning games. arXiv preprint arXiv: 100:11507.00407, 2015.
Yi Tian, Yuanhao Wang, Tiancheng Yu, and Suvrit Sra. Online learning unknown markov games. In International Conference on Machine Learning, pp. 10279-10288. PMLR, 2021.
Alexander Trott, Sunil Srinivasa, Douwe der Wal, Sebastien Haneuse, and Stephan Zheng. Building a foundation for data-driven, interpretable, and robust policy design using the economist. arXiv preprint arXiv: 108. 02904, 2021.
12

---

Published as a conference paper at ICLR 2022
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-33) 2019.
Bernhard Von Stengel and Françoise Forges. Extensive-form correlated equilibrium: Definition and
computational complexity. Mathematics of Operations Research, 1304):1002-102 2008
Jun Wang. Weinan Zhang, and Shuai Yuan. Display advertising with real-time bidding (rtb) and behavioural targeting. arXiv preprint arXiv:1610.03013 2016.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultaneous- move markov games using function approximation and correlated equilibrium. In Conference on Learning Theory, pp. 3674-3682. PMLR, 2020.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. arXiv preprint arXiv:2106.04880 2021.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In International Conference on Machine Learning, pp. 5571-5580. PMLR, 2018.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955, 2021.
Kaiqing Zhang, Sham M Kakade, Tamer Başar, and Lin F Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. arXiv preprini arXiv:2007.07461, 2020.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in multi-agent markov stochastic games: Stationary points and convergence. arXiv preprint arXiv:2 00/98, 198, 2021.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C Parkes, and Richard Socher. The ai economist: Improving equality and productivity with ai-driven tax policies. arXiv preprint arXiv:2004. 13333 2020.
A EXPONENTIAL IN m LOWER BOUND FOR LEARNING NASH IN GENERAL-SUM MGs
In this section, we give sample complexity lower bound for computing approximate Nash equi- librium in one-step binary-action general-sum MGs (H = 1, S 1 and A; = 2) which has an exponential dependence in m. the number of players. The result is built on the lower bound of query complexity in Rubinstein (2016).
We use G to denote the one-step Markov game (H 1 and 5 1), in which there m players and
A = 2 actions for each player. We index the players by [m] = (1....,,y m and denote the actions space of each player by [A] {1, 2). Since restricted attention binary-action games (i.e.
A = 2), the total number of joint actions is 2m
We define (exact) query the procedure where the algorithm queries joint action [A]m and observes the (deterministic) reward ra(a) E [0, 1). We define the query complexity (Chen et al., 2015) for learning e-approximate Nash equilibrium (ANE) as the following.
Definition A.1 (Query complexity). The query complexity QC, (ANF((, e)) for learning E-ANE is defined as the smallest n such that there exists a randomized oracle algorithm A satisfying the following: for any binary-action, m-player game the algorithm A can use no more than n sequential queries of the reward to output an e-ANE with probability at least 1 1-
In one-step MGs with deterministic reward, the query complexity is equivalent to the sample com- plexity, since each query obtains reward entry. The following result in Rubinstein (2016) gives 20(m) query complexity lower bound for learning AN-ANE in m-player binary action games.
13

---

Published as a conference paper at ICLR 2022
Algorithm 4 CCE-V-Learning for General-sum MGs (i-th player's version)
Require: Hyperparameters: {attisisk, (ntIsisH (Bessisk.
1: Initialize: For any (s, a. h), set Vs,(s)) + H. (s,(s) - 0, Lnss + 0, pn(als) + 1/A..
(s) e O.
2: for episode k: = - ....,, K do
3: Receive $1.
4: for step h = l..... do
5: Take action as pa (-(ss))) observe the action da.-; from the other players.
6:
Observe reward rh, = (8h, Oh ah.-i) and next state 8/+1 from the environment.
7:
Update accumulators: t == (s < (s)))) +1.
8:
VA (SA) + (1 a+) V (5%) + Or (ra,s (shr are an + V n-1, (sh+1) + 3r) KA,i (sh) < (1 a+) kn, (5h) + a (Th,s (Sh. ah: -n + V 1-1,4 (5x+1) 3.)
9:
10:
for all a E Ai do
11:
(sn a) H [ h+ rh, (V (V441.(9111))) h]]1 {ar a} /lmm (anl(an)s))))))))))))))))))))( +n].
12:
[n,e(sh. a) + (1 - (1-ax) Ln, a) + aaInns(sn Set uun (118%) x (nel--(ne//pp (s,
Proposition A.2 (Corollary 4.5, (Rubinstein, 2016)). There exists absolute constants Eo and > O, such that for all m,
Oc, OC (ANN(m,,E)) = 2mm), where 2 cm
This result shows that it is impossible for any algorithm learn an AN-ANE for every binary action game with probability at least (1 p) using poly (m, log(1 (pp) samples: such an algorithm with p= 2-m would only use poly(m, log(2"m)) = poly(m) samples, yet the sample complexity lower bound in Proposition A.2 requires at least 20(mm exp()((m)) samples. Since Proposition A.2 allows Eo (11, this also rules out the possibility of learning e-ANE with poly (m,, log(1/p), 1/s) samples for all small e.
B PROOFS FOR SECTION
B. ALGORITHM FOR LEARNING CCE GENERAL-SUM. MARKOV GAMES
Our algorithm used to learn CCE in general-sum MGs is combination of Algorithm and Algorithm In particular, Algorithm 4 computes a set of policies and plays these policies in each episode. Algorithm 2 used the full history in Algorithm 4 to produce certified, general correlated policy which we will show to be a CCE (we will also use the same Algorithm 2 to produce the certified policy in the algorithm of learning CE). During the execution of Algorithm 2, if the index t is 0 at some step h, the certified policy can choose any action at and after step h.
In Algorithm 4, we choose the hyper- pareeeparmmeters as follows:
H + 1
Hr A,t'
AR
H2, 1
a₁ = H H+ Tt =
3, =.=
+ 20
where > 0 is some absolute constant, and = log( m max.e A,HSK
is log factor. The choice of n) follows the V-OL algorithm in Tian al. (2021) which helps to shave off H factor in the sample complexity compared with the original Nash V-Learning algorithm in Bai et al. (2020).
Here, we have a short comment on the log factor In fact, we need i to be C' Colo(( [ maxig (m]] pe
HSK
for some absolute constant C. For the cleanness of the results, in this paper, we ignore this difference since this would not harm the correctness of all the results we present.
B.2 PROOF OF THEOREM 2
We begin with auxiliary lemma on of (its definition is in (3)).
14

---

Published as a conference paper at ICLR 2022
Lemma B.1 (Lemmaa 4.1 in Jin et al. (2018)). The following properties hold for od:
1. 3/ s j=1 ad 3 o for forrevery every 1.
maxjelt of 2t and Ej=1 (o))
<
2H for every 1 1.
3. Dt=j of = =1+ H. for every j 2 1.
4. ز== d ; 2 1 for every t 1.
Property 4 above does not appear in (Jin et al., 2018), for which we provide a quick proof here:
1/t
Σ of
2
1/(21)
Σ og = 1/(21).
レー
Here, (i) uses of is increasing in j for fixed t.
Some notations The following notations will be used repeatedly (throughout this section and the next section). At the beginning of any episode le for a particular state 8h, we denote (s%) < ....
(sn) < to be all the episodes that the state 5h was visited, where (s)) is the times the state 8y has been visited before the start of k-th episode. When there is confusion, sometimes will write k = =K (sx) in short. For player i, we let Vh V h. 14 denote the values and policies maintained by Algorithm 4 at the beginning of k-th episode, and a denote taken action at step h and episode For any joint policy Pa (over all players), reward function r and value function V, we
N (#x) kj
define the operators Py and D un
(PAV EN (((.)) V(s',,
(5)
Dr [r + PAV](s)
Eanoua (r(s, an) P V (s)+1)]
(6)
Towards proving Theorem 2, we begin with simple consequence of the update rule in Algorithm which will be used several times later.
Lemma B.2 (Update rule). Fix state in time step h and fix an episode k, let t (s) and suppose s was previously visited episodes ke <... k < k at the h-th step. The update rules in Algorithm 4 gives the following equations:
v (s) aill Σ j=1
of
This (s a o Vh htIi (shtza) + +3/
(s) = Σ of rhi (h ahh--) + Kn (shtt) 133] -3,)
We next present and prove the following lemma which helps to explain why our choice of the bonus term is Br. The constant e in B, is actually the same with the constant in this lemma.
Lemma B.3 (Per-state guarantee). Fix a state s in time step and fix an episode k, -ett=N and suppose previously visited at episodes k < .... < kt < k at the h-th step. With probubility least 2, for any (i, 1,,1 [m]] x x [ x [K], there exist a constant c s.A.
Σ of puaks
(Tr. + Ph min Vih I H - n1) (s)
max
(hii
HEDA:
1=1
Σ at This ss ah a + mingV
( 1/ Scv H3 c/12
1=1
15

---

Published as a conference paper at ICLR 2022
Proof of Lemma B.3
First, decompose
This + Ih min (V h+1,8 H H- -hi) (8)
max
uxxt!_
1
Σ
a
This s ohh--) + min V-I,, hD)
==1
into (1, 8, h, 1) (ú, , 8, h,,1 where
st, s, h) = max Σ ogD axxtl (Th: + Pr min ( V441. - hi) (s)
(This Ph mi h+1,5 H 11] (s),
Σ
a/D
and
U(i,8,h,t)
of
TD
rh.s Pr min (V 4+1.1: H hi] (8)
Ph phi
o This (8 abh--) + min (V H - n1
We first bound (ii s, h, t). Define Fi as the o-algebra generated by all the random variables up to the time when 8n is observed at the 1-th episode. Recall that for j 2 ki = kg (s) = inf > 1d-1: is visited at step in episode 1} (with convention 10 0). Then {kb)21 1 sequence of increasing stopping times w.r.t. (Fi) Define G, = FRS+1. So {9))220 is also a filtration. Under
9--1 (= Fis). by the definition of operator D and P, we have
The ss an 2o'
ahi.-) + min Vi (5 H,, h} 9--1
=D uba xpbs (Th.s min (ainn H h1) (s).
So we can apply Azuma-Hoefliee inequality. Note that (a)) 2H/t by Lemma B.1. Using Azuma-Hoeffding inequality, we have with probability at least AmHSK
0l1,8,h,1)-
Σ of 2s "ia
(Th. Pn min
( (
h+1,60 H h1] (s)
xM
Σ j=1
a 2i aik.-) min ( af This s
1 H h
< 2H2 log(4mHSS/
(af)) 2 H31/t.
After taking a union bound, we have the following statement is true with probability at least - p/4
U(i, s, h, = 2 H31ft for all (i, h, [m] S [H] [K].
Then we bound R ( s. h. t). For fixed (i, h), if we define the loss function
(a(
E -a= H - h h (s. a) Py, min V V H - h)(s)] E |0. 1].
H
16

---

Published as a conference paper at ICLR 2022
Algorithm 5 Correlated policy " for general-sum Markov games
1: for step h h, h,..., H do
2: Observe 81A, and set I <- (8w).
3: Sample 1 [t] with IP(1 = j] ay.
4: Update k f (sx)).
5: Jointly take action (aw,1, aw. ................................ aw,m) IT== M (+sw))
then R hi, = H max, Ej= or (H ( e)) becomes the weighted regret with weight
of. Note that the update rule for " (ss) is essentially performing nellow-the-Regularized-d Leader (FTRL) algorithm with changing step size for each state and each step h to solve adversarial bandit problem. Lemma 17 in (Bai et al., 2020)² bounds the weight regret with high probability. Using that lemma, we have with probability at least 1
1mHS
(i, Haf A
3HА
H
H
2r Σ
ao))
+ max afe H max d/t/m jSt
17
2
2
35t
simultaneously for all E [K] By Lemma B.1 and 1/2
He. we have with probability at least 7,
1
P 4mHS
8i,,,,,,,1) S 2/HBA///+3//HP///// ( ///// As//t
S 10 10/2 for all t [K].
Again, taking union bound in all hh E [m] S [H], have with probability at least 1 p/4,
(i,,,,h,0 < 10 Au//t + 10H3 for all (i, (i, h 1) E [m]] x S x [M] x [K].
Finally, concluded that with probability at least p/2, have
Uii, h) + R (,,,,,,)) / A3A/t cH2 for all (i, 8, h, E [m] S (H] [K]
for some absolute constant c.
Recall that the certified policy से as in Algorithm is nested mixture of policies. We further define policies {* [E[K]] in Algorithm 5. By construction, the relationship between Ω and मे. is that when players jointly play policy the क, they first sample k from (niform([K)) then they play together the policy #t (Algorithm for h with the same sampled k. As result, we have the following relationship:
K Σ
(i1( =
V (81).
(7)
K
Definition B.4 (Policy starting from the h-th step). We define the policy starting from the h-th step for player i as Tzh,i := {Tw,:: Ω (S x Ayh'-h x S - A.. 1H 1y-E- At each step h' > h, Tzh, samples action based on current state, the history starting from the h-th step and a random number Ω. We use 22 denote all policies for player starting from the h-th step. Similar to Section 2, we can define general correlated policy starting from the h-th step (where the random numbers may be correlated for different players), and we use Z1 denote all such general correlated policy starting from the h-th step.
A very similar result is Lemma F.3 in paper. However, here need Lemma 17 in (Bai al., 2020) to
get the optimal H dependency.
17

---

Published as a conference paper at ICLR 2022
For 12 can define the value function starting from the h-th step as:
H
(a) = E Σ
Twsissn
(8)
We also define the value function of the best response as:
1.5h, -1 (s) ==
V (s). 2N, h,
max
One example of a policy starting from the f-th step is oे defined in Algorithm 5, so that we can define V (s) and V v+t.,,,((s))
Lemma B.5 (Valid upper and lower bounds). We have
V (s) V (thhh-())) (s),
(t) S (s)
for all 8,,,h, k) E [m] x S x H x [K] with probability at least p-
Proof of Lemma B.5 We prove this lemma by backward induction over E [H + 1]. The base case of h H + 1 is true all the value functions equal 0 by definition. Suppose the claim is true
for h We begin with upper bounding Vn, 1. (s). Let & N (s) and k k)(()) for S S to be the j'th time that is previously visited. By the definition of certified policies म,. and by the value iteration formula of MGs, we have for any policy μ4, E II
(h, (xrPP((a V ( (s))
a E
h
a~p x
af a- x
(hils, a) + -E /
1 V (s')
j=1
Here, sh,s is the policy μ4 at the h-th step, and (#n+1:H, a) is the policy μi from time h + to H with history information at h-th step be 8h. and an a. By the definition of П have (Hn-1ssls. a) E II which implies the inequality in the equation above. By taking supremum over μ4 E I2gh, and using the definition of the operator in (6), we have
sup MEEA:
of
moxi [ra. + PA
1 141, (s()).
j=1
Conditional on the high probability event Lemma B.3, we use the inductive hypothesis obtain
(s) S sup
a ID [rn.s + Ps min Vh V4 H (s))ss)
h,
Pi
1=1
Σ
0
This as a aht + min miinfT
h1 +cv A cH
(
Thi ss a
as k , ming he 11 - h3 - B,)
1=1
This ag oh ahi-.) + ht1,s (shtt) + B/
at
1=1
(s).
Here, (i) uses our choice of B, =
A3 + 2c H2 and 1 < E ト
Vi
18

---

Published as a conference paper at ICLR 2022
Mcanwhile, for (s), by the definition of certified policy and inductive hypothesis,
(8)
af
D + PA PAV
[Ph.s
Ph
1=1
Σ
of
D Ph
[Th, + Ps max 1
Then we note that a (ra, + Ph, max ( 0H((s) | Thi s. ki ki
max m (c 1.
121
is martingale difference w.r.t. the filtration {Gj12o. which is defined in the proof of Lemma B.3. So by Azuma-Hoefiding inequality, with probability at least 2mSKH
Σ
a
D m [rmm Pn max 01(ss
(9)
2 af j=1
Ky 1/ s,an an.-2)
max (141)) ).03 -2V
1
This
On this event, we have
0f D uhe [rh,
Ph max (V
-
Σ
K/ Thi 8. ah:: max L (Kitndlthn))))
j=l
Vhh (8).
Here, (i) uses Ej=1 og 2 of 2////
As a result, the backward induction would work well for all h as long as the inequalities in Lemma B.3 and (9) hold for all (i, h, [m]
x [H] [K]. Taking union bound in all (i, s, h, k) E [m] X x [ x []]. we have with probability at least 1 - p/2, the inequality in (9) is true simultaneously for all (i,8,h, k) E [m]
[H] x [K]. Therefore the inequalities Lemma
B.3 and (9) hold simultaneously for all s,,
h. k) E [m] x S x [H] x [K] with probability at least
1 - p. This finishes the proof of this lemma.
Equipped with these lemmas, we are ready to prove Theorem 2.
Proof of Theorem Conditional on the high probability event in Lemma B.5 (this happens with probability at least 1 - p), we have
V (s) 2 V. -i b,
(s),
(s) S b,7 (s)
for all E [m]
H [K]
Then, choosing and 81, we have
#
(81)
V
オ (81) (s1) (s1).
Moreover, by (7), value function of certified policy can be decomposed as
K
K
Vi.(s)
V 8 (81)
(s1)
(s1)
K
=
K
1,1
A=1
where the decomposition is due to the first line in the Algorithm 2: sample k Uniffrrm(K])
19

---

Published as a conference paper at ICLR 2022
So have
K
Vi. (s1)
(s)
-
1,
-1 (51)
V
k=1
K
Vir((1)) - vt.()s)).
K
To prove Í is an approximate CCE, only need to bound Σ (s), - Vt, (91)) Letting
(*h,( and t (s Suppose of was previously visited at episodes kl ......,k ke at the h-th step. By the update rule,
of := Vh,
o -Vna(sh)) (5 H
af ( ( 1
+ 23,1 V (++1)
j=l
0 H +
h+1,1
+
200
g=1
= of H +
+ 2c
Σ a
A
+ 4c Ead
11:
1=1
j=1
We can use Lemma B.1 which gives Σj= at/Vi S 2/1 and maxjst of S 22H/ to get
8 S al +
oe 14 + /ev H3Au// + (c + log1)/4,
where we also uses Σn-1 1/j 1 logt. I.
Taking the summation w.r.t. k, we begin by the first two terms;
K
K
Σ af Σ 11 (t=
Σ #1 (N = 0} S SH.
K (s
K
NY. (a (6)
K
Σ
(1
h+1,
H
km
J=NY (o) J+1
R
where (i) is by changing the order of summation and (ii) is by Lemma B.I.
So
Σ 1=1
K
she S SH + (1
K 8 t + 4ev A,
K
1
+
8cH
K
1 + log (x)
H
()((s)
N (s)
k=1
By pigeonhole argument,
K
N
Σ
1
- O(L)VKK.
(s)
SES
n=1
Similarly,
+ log (s)ss
< 0(1(1 Hog log K(S))) < 0(1)S( + +2)) S O(1)8)
No.
20

---

Published as a conference paper at ICLR 2022
where we assume 2 1. So we have
8h S SH + (1
+ 0
Recursing this argument for h E [H] gives
Σ 8 S eH's
To conclude,
1 K
K
-111 (
(81)
Vi,((11) KK)((1))
1
Σ
Sf.4
K
K k=
k=
50(1)SH'2/KK0
HSS max A K
iE(m)
Therefore, K 2 O H m
guarantees that we have V (81) - (T,,(s1) SE
for all i E [m]. This complete the proof of Theorem 2.
L
C PROOFS FOR SECTION
In this section we prove Theorem 5. We first define a set lower value estimates (s) (along with the upper estimates used in Algorithm 1) via the following update rule:
Kn, (sn) + (1 - an) Va,i ($k. + ag (ri. (sh, ahs an + Mn+I, ($6+1) B,)
(10)
We emphasize that Vh,, (8) are analyses quantities only for simplifying the proof, and are not used by the algorithm.
We restate and use several notations we introduced in the last section. At the beginning of any episode
for a particular state sh, we denote kj, (sx) <... < ki (ea) (sn) < & to all the episodes that the state 8y was visited, where N (ss. is the times the state Sy has been visited before the start of k-th episode. When there is no confusion, we sometimes will write k = ki (sx. in short. For player i, we let kh., Vh... μ.t denote the values and policies maintained by Algorithm 4 at the beginning of k-th episode, and a denote taken action at step h and episode k. For any joint policy μh (over all players), reward function r and value function V. we define the operators P,, and Da, as
[ a) = Ey Es--Pa(-ss.a) Vss',
Dr, [r + Ps) == Earcas [r(s, an) + E ((s++1)
The following lemma is the same as Lemma B.2 in the CCE case (except that for a different algorithm). Lemma C.1 (Update rule). Fix a state s in time step h and fix an episode k. let = N*) and suppose s was previously visited episodes k2 <... <. k < k at the h-th step. The update rule for V (s) and (8) in Algorithm and (10) gives the following equations:
V (s) = at +
Σ og This 8, at ahh..)) + Tak Vhtii + +33
j=l
(s) Σ ag Thi (s, ah aki-a) Vhite (shti) 33]
21

---

Published as a conference paper at ICLR 2022
We next prove the following lemma which helps explain choice of the bonus term 3 The constant in B, is the same with the constant in this lemma. For any policy modification yı A, - A, for the N player and one-step policy Th S - A for any h, the modified policy pi o εy is defined follows: if Th chooses to play (a1,-.. am)) the modified policy yi лл will play 04-1, 4; (P(()))) ai+1s..., am). Moreover, for Thi : -+ A.. policy y; o Th; chooses (a((a) when Th, chooses a.
Lemma C.2 (Per-state guarantee). Fix a state in time step h and fix an episode k. let t= ()) and suppose was previously visited episodes k' <... < K' < k at the h-th step. With probability 1 2. for any (i, 8, h,t E [m] x x [H] x [K]. there exist a constant s.I.
sup E
of Piou (hi + Pa mintVhtii 1+1, H 11)) (s)
PiiA-AAiia jml
of
Thes ah bo
ohi-s)
min
( -13 s ScHfAiv 21/l+ cH? An/h.
j=1
Proof of Lemma C.2
First, like the prove in Lemma B.3, we decompose
Σ af ID prout
(r..s + Ph. (i 1+1,5: H 11) (s)
sup
Piid -1 j=1
Σ af Thi ak ahi-i) + min V H hh}
into (1, s, h)t) + Ui,, h, where
hi,,,,,,t) = sup EajD
proupe P (hhi + Ph min
V ht1, H -13) (s)
-i::i 5=1
This ax aa)) + B a..) min (Vrl (41,( H 113
a a
/=1
and
si,,s,h,t) =
Σ af a
The ah aa. E. (naaaBa(Haaaalee .a. min min(Th) (Th (84+1,) --h)
j=1
Σ at Phi (s w
ah aih--)) min min(V ( H 11
We first bound U(i, s, h, t). By the same reason in proof of Lemma B.3, we can apply Azuma- Hoeffding inequality. Note that (a{)) < 2H/t by Lemma B.1. Using Azuma-Hoefdding inequality, we have with probability at least 1 4mHSK:
Uli,,,h,1)5
2 loggog(m /p) Σ (of) 2
1=1
After taking a union bound, the following statement is true with probability at least p/4,
Uli, 1,,, < 2 H//// for all (i, h,, E [m] S [H] [K].
Then we bound Rd (i, s. t). For fixed (i, 8, h), we define loss function
E Ee min miinVVle (aabl
(a(a)= H Baman H h + (h,i a)
(4144)641)) H h.].
22

---

Published as a conference paper at ICLR 2022
Algorithm Correlated policy # for general-sum Markov games
1: for step h h,..., H do
2: Observe 8yA, and set I <- (sw).
3: Sample 1 [t] with IP(1 = j) ay.
4: Update k f (sx).
5: Jointly take action (aw,1 aw, ................................ aw.m) IT= (-(w))
Then we have Lÿ(a) E [0,1] for all a and the realized loss function:
(a(ahh) kd
1 H h+ 1- rh, oh a min V ( h3l E [0,
H
an unbiased estimator of (y(akt Then R (i, s, h t) can be written as
(i,,,, = sup Σ aall((a7)))) - (ps o Mh e/
prdd j=1
Now, for any fixed step h and state s, the distributions {1s),, and visitation counts (N)(s)) b
are only updated at episodes (s). (o)),....kjjj (s). Further, these updates are exactly equivalent to the mixed-expert FTRL update algorithm which we describe in Algorithm 8. Therefore, the Rt (6, 8, () above can be bounded by the weighted swap regret bound of Lemma F.1 (choosing the log term as c log 10mSAHK) yield that
H sup P.A.
Σ ((ll((a).)) sops ph. G) 40H² A A.V 4 Aa/t for all & [K]
with probability at least 1 - (4). Taking a union bound over all (i, 8i, h) E [m]] x S x [H] we have with probability at least p/4,
Rd (i, s, t) I A. 40H2A,t/t for all (i, s, h, t) [m] x S x [ x [K].
Finally, we conclude that with probability at least p/2, we have
Uii, s, h)t) Rd (i, s, s, S cl1 for some absolute constant
AL clI2 cl1 Au/t for all (i,s, h,t, [m] S [M] [K]
We define the auxiliary certified policies # in Algorithm 6 (same Algorithm 5 for the CCE case but repeated here for clarity). Again, we have the following relationship:
K K
1,1 (8).
(11)
Definition C.3 (Policy modification starting from the h-th step). A strategy modification starting (b) (., ( Hy.. for player i is a set of S (H - functions &w... : (S x A)''' x A: - As- This strategy modification Φ2 can be composed with any policy E I1 (as in Definition B.4) give modified policy 62h defined as follows: At any step h' 2 h and state 8 with the history information starting from the h-th step Thah-1 (sh; ah.-... 5t -1--1,, if chooses play a (a1,..., ...).,))), the modified policy @ o will play (a1.... 04-1, ΦN (TTh -1, oz). Oitl...., a.)) We use 42h, denote the set of all such possible strategy modifications for player i.
from the h-th step Φ2h := {&W. 1 ,))
For any o L2h,5, ó oे also doesn't 't depend on the history before the h-th step, á 7/. E Il which implies that h.s (8) is well-defined in (8).
23

---

Published as a conference paper at ICLR 2022
Lemma C.4 (Valid upper and lower bounds). We have
V (s) 2 sup
V (s),
(s), (s) s V
for all (i, k,,, h E [m]] x [K] x [M] x S with probability at least - p/2.
Proof of Lemma C.4 We prove this lemma by backward induction over [H + 1]. The base case of h = H + 1 is true as all the value functions equal 0. Suppose the claim is true for h + 1. We
begin with upper bounding supSetgn. yook (s). Let = (x (s) and k (s) for 1 S < to be the j th time that is previously visited. By the definition of certified policies 7h and by the value iteration formula of MGs, we have for any $24...
Vis (8)
o
E
(s, + B.ra
V (l2amnla.a)os h+l.
(s')
jml
rna(l,, + Exw.Pa(lo,a)
sup
h+1i h+1 (6)
Here, db., is the strategy modification function & at the h-th step, and (dzb+1 [s, a) is the modification o from the h + 1-th step with history information to be 8h and a₁ = a. By the definition of P2n,i. we have (d>s+1|ss a) E $2Λ+1, which implies the above inequality. By taking supremum over Φ E 224, and using the definition of the operator IB in (6), we have
sup 6E 2h.
yoo Via
(s) S
sup SAA:;
Σ ofD p:opt [Fn, + Ph. sup 2
h+1 ((s)).
R+
j=1
Condition on the high probability event (with probability at least - p/2) in Lemma C.2, we can use the inductive hypothesis to obtain
sup Σ pr::iAA;
of
DD
piopp [Ph, + Ph
sup
Vntti "[(s)
j=1
Σ
ofD bionti [rn, Pn min ( R+1.0 H ns)(s)
sup
piiAitAi
j=1
Σ al
This (5 Rd , ahi-.) + min ( H h3 + +cH2 L + AH2
==1
(
Σ
of
Mhis at ah.--) (Nt H h1 +3,)
Thi (3,0hh ( + vuu V + Bz of
-V),(ss.
Here, (i) uses our choice of 8, cHl' A1, / 20 H² and J S
of Σ j=
1
20
s0
that eH2 A A cH2 Au/t < a
Meanwhile, for V (s), by the definition of certified policy and inductive hypothesis,
V (s) =
[Ph.s + PA P.V
M
>
Σ
af D 2d [Thi + Pa max ( 0)(ss).
24

---

Published as a conference paper at ICLR 2022
Note that D A Ir,, + Ps max 1
Thi s, (s.
A/. ah-,,
max h+
121
is martingale difference sequence w.r.t the filtration {9, |2, which is defined in the proof of Lemma B.3. So by Hoeffdigg inequality, with probability at least 2mSKH
Σ
aB uet (rn,s + Ph max (+)
(12)
Kr Hy 8,a0 ahiss)
H34 max max - -2V t
2 ag
Thi
j=1
On this event, we have
Σ D
[ra,
Ph max {vri 10t11.00((0
ki
(
+ max { ( - +max
( -B,1 -B,
0g
This
8, ap
j=1
Σ
bi Hy 8, , ahiss)
kiy (
a
Thi
j=1
(s).
Here, (i) uses Σソ= 0g 2 2 2f Hi/lj 2 22/2///!
As result, the backward induction would work well for all h as long the inequalities in Lemma C.2 and (12) hold for all (i, s, h, k)) E [m] S x [H] x [K]. Taking a union bound in all (i,s, h, k) E [m] x x [H] [K]. we have with probability at least 1 1- p/22, the inequality in (12) is true simultaneously for all (i, h k) E [m] x S x [H] x [K] Therefore the inequalities in Lemma
B.3 and (12) hold simultaneously for all (i, 8, h, k) [m] x S x [H] [K] with probability least 1 - p. This finishes the proof of this lemma.
Equipped with these lemmas, we ready prove Theorem 5.
Proof of Theorem 5 Conditional on the high probability event in Lemma C.4 (this happens with probability least 1 p), we have
v*) 2 sup
(b), (x) b,2 (s)
dEt2R.
for all (i, h, k) E [m] x x [H] X [K]. Then, choosing and s = 81, we have
y
(81) V (s1) S (s. 1 (s1).
sup +;
Moreover, by (1I), value function of certified policy can be decomposed as
K
K yooat (81),
(11)
V
(s1).
VileR (s1)
K
K
k=1
where the decomposition is due the first line in the Algorithm 2: sample k Unifform((] Therefore we have the following bound on supaeæ, v.da
(s1) (s)()
K
sup Vdo2 (s1) (1. = sup sec.
Σ y (s1) (i.
SEC, K
1=
25

---

Published as a conference paper at ICLR 2022
K
k K
V-
1,8 (81) -V.
V
(1,((1) - -
sup
-
k=1
By Lemma C.4 Letting 8%, == von( (+)) and t = (sh)) By the update rule, we have
t = (x (0h)
= =a + Σ
of (V h+11 - V (+h+1) + 23,1
j=l
=ff 11
0/00 h+1,
Σ 3,
j=1
5=1
14
H²L
H
= af H +
0 h+ i + 2cA, H
a
+
4c
a
j=1
==1
Taking the summation w.r.t. k, by the same argument in the proof of Theorem 2, we can get
K
max V
(81) - V2 (81)
1
(+11
V v4,((01)
1
Σ
6E
K
K
k=1
O(1SHH max A,t² 3 +0 EE m
HOS max A7t/K K :E[m]
Therefore, if K 2 0 11 max A7
+
H max A
we have max V1. (81)
Vf. S & holds for all i E [m], which means # is an e-approximate CE. This completes the proof of T'Teorem
D PROOFS FOR SECTION 5
Here, we first define pure-strategy Nash equilibrium. We say policy π is pure strategy (deterministic policy) if and only if for any (h,i,s) [H] [m] x S, (a,ss (+)= for some (s). We say ι a pure-sttaate sure-strategy Nash equilibrium if π a pure-strategy and is Nash equilibrium. Similarly, we say is a pure strategy e-approximate Nash equilibrium if is pure strategy and NE-gap (T)
Pure-strategy Nash equilibrium does not always exist in general-sum MGs, but guaranteed exist (as we will see) in Markov Potential Games.
D.1 EXISTENCE OF PURE-STRATEGY NASH EQUILIBRIA IN MARKOV POTENTIAL GAMES
A particular property of MPGs is that, there always exists pure-strategy Nash equilibrium. Such property does hold for every general-sum MG. Pure-strategy Nash equilibria preferred in many scenarios since each player can take deterministic actions.
Proposition D.1. For any Markov potential games, there exists a pure-strategy Nash equilibrium.
See Theorem 3.1 in Leonardos et al. (2021) or Proposition in Zhang et al. (2021) for a proof of Proposition D.1.
D.2 THE UCBVI-UPLON SUB-ROUTINE
In this subsection we consider the problem of learning a near optimal policy in the fixed horizon stochastic reward RL problem MDP(H, P... The setting is standard (c.f. Jin et al. (2018)) and is a special case of Markov games (c.f. Section 2) by setting the number of agents m 1. We will the same notations including policies and value functions that of the Markov games as
26

---

Published as a conference paper at ICLR 2022
Algorithm 7 UCB-VI with Upper and Lower Confidence Bounds (UCBVI-UPLOW)
1: Initialize: For any (s,a,h,s') an(s,a) - H, 2, (8, - 0, NM(s) = NN(s,a)
(s, s') 0.
2: for episode k = 1,
do
3: for step h H 1 do
4:
for (s.a) E S A do
5:
Set 1 (s)
6: if > 0 then
7:
3 Bonus(t, (V (V1+ h+1 + V h- n=11//2 a)) (c.f. Eq. (13))
8:
- (c/H) PW h+1 (s,))ss,a).
(n, min (rn + +PAVV++) a) + 3
9:
10:
2, (s, + max (Th +PhKk41))ss - 3.0}
11:
for 8 E S do
T (s(s) + Qn TA (s)); (s) t 2₁ Th (s)).
arg Ma (s,
Receive the initial state $1 from the MDP.
15: for step h h= L..... H do
Take action d₁ Th (sh), observe reward Th and next state 8/+1- Increment (s.)s,,, (sh, an), and (s,,,, ah, 8h+1) ) by 1.
17:
18:
Pa(-1sh, an) <- NA (sn, on, (.////NN,,, (8h,,)) on).
19:
Let (V ho Kh. n²) denote the value estimates and policy at the beginning of episode k.
20: return Policy nh where ki = arg min [ (V (s))).
introduced in Section 2, except that we will omit the sub-scripts i's since here we just have a single agent.
We consider the UCBVI-URE VI-UPLOW algorithm (Algorithm 7), which is adapted from (Xie et al., 2021; Liu al., 2021), for learning approximate optimal policy in reinforcement learning problems. Such an algorithm is used as sub-routine in Algorithm to learn approximate pure-strategy Nash equilibria in MPGs. We remark that although in Algorithm we propose to search for a near optimal policy, many alternative algorithms can be used to find the near optimal policy (e.g., UCBVI (Azar et al., 2017 or Q-learning (Jin et al., 2018)). Here we choose the UCBVI UPLOW algorithm because 1) it has tight sample complexity bound; 2) it outputs a deterministic policy which can be used to find pure-strategy approximate Nash equilibrium.
the UCBVI-UPLOO
algorithm
In the description of Algorithm 7, the F,, quantity appeared in lines 8,9,10, and 18 can viewed either as set of empirical probability distributions or operator: for any fixed (sh. ax), view PA (- sh, an) as probability distribution over S; for any given function V RR we can view PA as an operator by defining (P,, (s, a) := E y (-1a,a) [V(')) The V, operator in line 7 is the empirical variance operator defined as V V = P, V2 V)2.. The BONUS function in the algorithm is chosen be the Bernstein type bonus function
BONUS @2) cl c(v + H
(13)
We have the following sample complexity guarantee for the UCBVI-UPLOW algorithm returning an s-approximate optimal policy.
Lemma D.2. The UCBVI-UPLOW algorithm always returns a deterministic policy n²., Moreover, for any p E (0, 1). letting (og(SHH//)) and taking the number of episodes
K O(H S At/e² + H² Ai² /
then with probability at least P. the returned policy nh is 6-approximate optimal, i.e. sup, (f Vaah (81) S..
Proof of Lemma D.2
First, th is obviously deterministic from line 12 of Algorithm 7.
27

---

Published as a conference paper at ICLR 2022
The sample complexity guarantee of the UCBVI-UPLOW algorithm is a consequence of the sample complexity guarantee of the Nash-V VI algorithm for learning Nash in zero-sum Markov games as proved in Liu et al. (2021).
More specifically, we denote the rewards and transition matrices by {ra(s, a) hetm and P {Pr (*h++1188 [8h, an HeEH for the MDP(H, S, A, P,)). Such a MDP can be viewed as zero-sum Markov game MG(H,S, A, B, F), in which (H, A) are the same as that of the MDP, the action space for the min-player is singleton on the action of the min-player and the transition matrices (- a, b) Pn a1) do not depend on the action of the min- min-player either. Then, for any E-approximate Nash equilibrium (H,, v) of the associated zero-sum Markov game, the max-player's policy y must be e-approximate optimal for the original MDP.
so that the rewards ix a, b) = (s, a) do not depend
By this correspondence, the UCBVI-UPLOW algorithm actually a specific version of the Nash- VI algorithm in Liu et al. (2021), and Line 12 in VI-VLLU is actually specific version of line 12 Nash-V VI Liu et al. (2021): this is because this specific Markov game, Q(s, a, b) and Q(s, a, b) only depend on 8 and a, so that ny (s) arg max Qn (8, a) is actually in the CCE set CCE(Q, (s, b). Q₂ (s. b))).
By this reduction and by Theorem 4 in Liu et al. (2021), this lemma is proved.
D.3 PROOF OF THEOREM 7
We use superscript / to represent variables at the /-th step (before æ is updated) of the while loop.
Because we can choose the log factor as = 4 log( MHSK maxie|m] Ai) (this doesn't 't affect the correctness of the theorem), for each execution of UCB VCBVI-UPLOW by Lemma D.2, it return e/4-optimal deterministic policy with probability at least 8m²H Taking union bound, we have
max Vi,i mL,) - Vi,a mL, s Pi
(14)
simultaneously for all i E [m] and t < 4mH/e with probability at least 1 p/2. For the empirical estimator Vf,.- it's bounded in [0, H). Thus by Hoeffding's 's inequality, for fixed [m]] and t
2g
P(V Ví,al 2 e/8) s 2 exp
32H²
Choosing N CH2I/E2 for some large constant C, we have
P(DV. Vi,.l 2 e/8) S
ap
16m2H
Apply this inequality to 1/,, (+t,, m and (T,((T') and taking a union bound, we have
Ve ( Vi, ( اLااه S 8/8,
- v(.(('))
(15)
simultaneously for E [m] and 4m with probability at least p/2. As result, by (14) and (15), we have
max Vi,i xL,) - (L)
(1 mL,) V1, (T), mL,) 5
(16)
[i,(+')) [1,( 5/8
simultaneously for all i E [m] and t 4mH/e with probability least 1 p. On this event,
A = Ve (., - Vi7((7)
< (i, Vi,((7') e/4.
28

---

Published as a conference paper at ICLR 2022
If the while loop doesn't end after the f-th iteration and Σ 4mH/e, there exists jr s.t. Aj. 2 e/2. so we have
((x ((T²) DiFfe, m_je) (
Vi (7). x= - Vige(
A c/4 =/4..
Here, (i) follows the definition of potential function. Because bounded, the while loop ends within 44 mix/ I 4mH/E steps. Therefore, (16) holds simultaneously for all i E [m] and before the end of while loop with probability least p. Again, on this event, the while loop stops at the end of (-th step, we have maxte[m] 4 S E 2/2, then
max V1,e(H4 - V1,((T') = max V ( ग - Vi, x-,)) + (T. +'.) - Vi,((T')
s </4 Vi, = VT,(+')- - -2=/8
e/2 A S 8.
So the returned policy x' is e-approximate Nash equilibrium. Moreover, since UCBVI-UPLOW outputs pure-strategy policy and our initial policy is also pure-strategy policy, we can conclude that with probability at least 1 p. within 4 max/ steps of the while loop, Algorithm 3 outputs an E-approximate (pure-strategy) Nash equilibrium.
Finally, the number of episodes within each step of the while loop is
1 -=
Ar
S
Σ
H
+
K + N) -
+
2
8
6²
1=1
H E
H Em
Art
=0
1=1
8
So the total sample complexity (episodes) is at most
S mmax
H3S Σ
Art
① max
H Σm Art
K K
g3
g2
This concludes the proof.
E LOWER BOUND OF FINDING APPROXIMATE PURE-STRATEGY NASH EQUILIBRIUM
In this section, present an result the sample complexity lower bound for learning pure-strategy Nash equilibrium in MPGs (a harder task than learning Nash as pure-strategy Nash is a stricter notion). We remark that our lower bounds are actually constructed on Markov Cooperative Games (MCGs) which is subset of MPGs. Note that for MCGs, the potential function & is bounded in [0, H}. so by
Theorem 7, the sample complexity of Nash-CA (Algorithm 3) is Ō OΣ -
A,/=²) highlighting the Di=1 A; dependency is inevitable dependency on m and A,, i = 1,..., We would show this Σmd for learning e-approximate pure-strategs Nash equilibrium in MCGs by proving an 12 ( A//c²) lower bound.
We first present our main theorem:
Theorem E.1 (Lower bound for learning pure-strategy Nash in MCGs), Suppose A, = 2k, i = S and m 2 4. Then. there exists an absolute constant co such that for any 8 < 0.4 and any online finetuning algorithm M that oulputs pure-strategy policy T = (m....., Rm.)
1...., m. H
if the number of episodes
H2
Em A:
H
< cu
Cu
2
22
29

---

Published as a conference paper at ICLR 2022
then there exists general-sur sum Markov cooperative game MG which the algorithm M suffers from E/ suoopiiiiialltyy i.e.
EM (MMME) ()) 2 E/4,
where the expectation Eas is w.rll the randomness during the algorithm's 's execution within Markov game MG.
This theorem can be viewed as corollary of the following lemma by a simple reduction. We would prove this theorem in the next subsection. One-step (general-sum) game is game with only one state and one step. In one-step game, each player chooses an action simultaneously and then receive it's own reward. The Nash equilibrium and NE-gap can defined similarly one-step games.
Lemma E.2 (Lower bound for one-step game). Suppose A; 2k, i I...., m and 2 4. Then, there exists an absolute constant Co such that for any & S 0.4 and any online finetuning algorithm that ouiputs pure strategy के
(71, (71,--- ........ mm), if the number of samples
1 A
2km
82
g2
then there exists a one-step game M with stochastic reward, on which the algorithm suffers from e/ e/A-snbeptimality, i.e.
NE-N-- = EM max max (T;, R-;) (i( 2 E/4,
where the expectation Ey is w.r.l the randomness during the algorithm's 's execution within game M. (T(T) is the expected reward of the th player when strategy π are taken for each player.
The proof of this lemma is also in the next subsection. In the proof, we first construct class of one-step games which reward is Bernoulli()) ) or Bernoulli(} [ + +e) depending on the taken joint-action. The proportion of joint-actions with reward Bernoulli( [ + E) is relatively small. Most importantly, every pure-strategy é-approximate Nash equilibrium has reward Bernoulli + a). So in order to find an e-approximate pure-strategy Nash equilibrium, we must explore sufficient joint-actions The number of the ooint-actions with reward Bernoulli +) can be bounded by the covering number of [2k] under Hamming distance. Then we use KL divergence decomposition (Lemma E.5) to argue rigorously that need to explore sufficient joint-actions to get an e-approximate pure-strategy Nash equilibrium.
The rest of this section is organized follows: We first prove Lemma E.2 in Section E. and then prove the main Theorem E. in Section E.2.
Discussions of Theorem E.1 There's s Ei A; dependency" in the lower bound of sample com- plexity for finding a pure-strategy s-approximate Nash equilibrium in MCGs. This bound is novel and improves the existing result. The existing proof in sample complexity's lower bound of Markov games (Bai & Jin (2020)) relies on an reduction from Markov games to single-agen MDPs, so the existing lower bound's s dependency on A; (i ...... m) max,e|m] A,
Here, we don't ton't include S factor in our lower bound. The difficulty is that the NE-gap only depends on the player with the most suboptimality. For a single-agent MDP, if the player can change the policy at each state to improve the expected cumulative reward by E, then the player can change policy at all state to improve the expected cumulative reward to the utmost extent. In general-sum Markov games, different state, maybe different players change the policy for this state improve his expected cumulative reward by e. However, the definition NE-gap only allows one player to change the policy. This difference in nature makes S and Em A, incompatible in the lower bound.
we consider another notion of suboptimality, i.c., changing maximum to summation:
NE-gap's (IT)
Σ [mr]
sup VHi ((s)) - (T)((s))
This definition of NE-gap is different from the previous definition. With NE-gap', if each player can change his policy improve his expected cumulative reward by e, the NE-gap' would be at
"We only prove this lower bound when A, all equal 2k. This case is representative.
30

---

Published as a conference paper at ICLR 2022
least mE. Then similarly define e-approximate Nash equilibrium the policy such that NE-gap (x) I E. We simply point out that with this new definition of NE-gap' and E-approximate Nash equilibrium, mimicking the proof of Theorem 2 in Dann & Brunskill (2015), prove the sample complexity's lower bound for learning pure-strategy e-approximate Nash equilibrium in Markov (cooperative) games is Q2 H Ei=1 A:/e²).
E.1 PROOF LEMMA E.2
For convenience, call the joint-action (in one-step game) that is a Nash equilibrium a Nash strategy. We begin with special case Lemma E.2, i.e. the case when A, = 2 for all E [ml.
Lemma E.3, Suppose A; = 2, I...., m and m 4. Then, there exists an absolute constant co such that for any ε < 0.4 and any algorithu that outputs a pure strategy π = (T1...., Am). if the number of samples
2m
n S CO g²
then there exists a one step gume M with stochastic reward on which the algorithm suffers from e/ subopttiiiall i.e.,
Na-NE-app(T) = EM max max ue (1(TT, 7-:) (F) 2 e/4,
where the expectation EM is w.r.t the randomness during the algorithm''s 's execution within game M. (x(T)) is the expected reward of the 7th player when strategy are taken for each player.
The proof of this lemma further relies the following lemma.
Lemma E.4. There exists a one-step game for m players where each player has two actions. The 2 Moreover,
deterministic reward is 0 or 1 and the number of joint actions that have I is most
the only pure-strategy Nash equilibria are these joint actions which have reward 1.
We use r(a) to denote the reward of (joint) actions E {1, 2) and define hamming distance d(a, a') #(i: * df}. To ensure that pure-strategy Nash equilibria must have reward 1, we only need to ensure that for a E {1,2] 2mm, there exists one a' E [1,2] such that
Proof of Lemma E.4
r(a')
d(a, a') 1.
In other words, the set {a r(a) = 1} is a I-net of 21, under the distance d(.,-). By the definition of covering number, we only need prove
m
W([1.2) d, .,,,
m
Define K(m, 1) ((1, d. By hamming code (Hamming (1950)), we know that for any integer h 2 1,
K(2h 1, 1) -k1
1) by adding 0 and 1 behind the 1-net of {0, 1)--1. Taking largest such that 2* n and iterating this construction on the Hamming code we get K ((m,) 1) < 2mm-mooop0 [mog2(++)]]
Moreover, also have K(n, 1) 2K 1,
< 2 This ends the proof.
The next lemma is KL divergence decomposition (Lemma 15.1 of (Lattimore & Szepesvári, 2020))). we restate it in one-step games.
Lemma E.5 (KL divergence decomposition in one-step games). For any one-step games with stochastic reward and any algorithm. Let X (a1, 022 T2...., an, rw), where ag is the action (adaptively) chosen by the algorithm at the 1.th round and rk is the reward received at the 1thh round after ag is taken. F and Q are two probability measure for the stochastic reward. Let N (a) ()) be the total number of actions a in the first n rounds. Then
XL(X|||XX) = Σ (B(NG)))KL(P(((())Q((()))
31

---

Published as a conference paper at ICLR 2022
Then we return to the proof of Lemma E.3. Suppose game M satisfies the condition in Lemma E,4, by permuting the actions M, we get 2 games. They all satisfy the condition in Lemma E.4. Suppose the reward of the i-th game is (.) (i = ,,,,,,,"
We consider the following family of one-step games with stochastic reward: Let a (01, .2,..... . a.).
(e) (M E ((.22)) with M - - ( i
1,2.....,
where one-step game M the reward is sampled from Bernoulli(M (a)) if the joint action a (d1, dg,..... a.). Moreover, we define _M as a game whose reward is sampled from Bernoulli()) independent of the action.
We further let v denote the uniform distribution on (1,
Proof of Lemma E.3 Fix a one-step game M Me), by Lemma E.4, it's clear that pure- strategy Nash equílibria form a set D == a E {a : (a) = 1}. We have # D S 2mm-1/m. For any online finetuning algorithm A that outputs pure strategy न. Suppose ā takes joint-action (a1, 02, ... am) From the structure the (E), we know
NE-Gap R = (a & D()),
where P, is w.r.. the randomness the algorithm and game M So we only need use n, the number of samples to give lower bound of P; & D()).
Since X {ai, r.. an. rn) } is sufficient statisties for the posterior distribution D have Pi & D(9)= 2 inf P & D(
g
Eive TV( Xle,) inf E Po((() & D(1)
(0)
E TV(X
2
(6))
2
1Fo 1x,))
2
(1) 1
B V
Bp, (BC/
2
2
Above, (i) follows from the definition of total variation distance; (ii) uses the fact that under Po., we can't get any information about a", so ExxxPo(g(XX) D( ( inequality; (iv) uses KL divergence decomposition (Lemma E.5).
(iii) uses Pinsker's
For D(), we have
(0((()))
1
2 - E. + +e))
KL(Po(la)(PP(aa))
KL
2
1
log 4
< 4
if E (0, 0.4). For a g D(, (TaPP(aaa))I(((-aaa)) = 0. So
E, & D()) > E
2 Σ
Er, (a))ss
aED(
2E
E2, (N())s2
2
aE D
(80)
n1 (+)
2
32

---

Published as a conference paper at ICLR 2022
n
c².
2
Above, (i) uses Jensen's inequality, (it) uses the fact that Ep. (N ] is independent of i which gives
Σ
Er, [N(]]
Σ Re, [N(a)
Σ
2
DED
iaEDoS
2m n D
where EEaeDO 1 |D( because of the permutation. Finally, we choose co then
32 if S 32
1
(a & 2
So there's game instance ( which the algorithm suffer from e/4 sub-optimality.
The difference between Lemma E.3 and E.2 the size of action space. To prove the A; 2k case, we need to generalized E.4 to the case each player have 2k actions.
Lemma E.6. For all positive integers m and k. There exists a one-step game for m players where each player has 2k actions. The deterministic reward 0 or and the number of joint actions that have is at most 2.(2k) Moreover, the only pure-strategy Nash equilibria are these joint actions km
which has reward 1.
Proof of Lemma E.6 We would prove this lemma by induction. Without loss of generality, we suppose the action for each player is 2, ..., 2k. First, we define the hamming distance between two vectors.
d(x, v) = # ar1) + y())-
The joint action space is [2k] f1, (1....... 2m Suppose we have an 1-net [2k]m D, which means for every [2k] we can find a E D, s.t. d(x, y) I 1. If the reward of game satisfy:
r r(a) for all a a D, and r(a) = 0 for all a & D.
Then for every pure strategy a which has reward 0, we can find another pure strategy a' s.t. r(a') = 1 and d(a, a') = 1. This means that one player change to obtain higher reward. So is not pure-strategy Nash equilibrium.
As result, number of joint actions that have reward is at most that have reward is actually D), so need to prove
construct game based on the 1-net. The only thing left be verified is that the
2-(2k) Am Note that the number joint actions
N([2k]",,, ,d1)) 2 (2k)
(17)
km
where ((,dd,s) denotes the covering number.
For = 1, from the proof of Lemma E,4, (17) is true. For & > 1, we first decompose [2k] into k. smaller blocks, i.e.
2(4, 12 ... (m) [211 21 {26₂ 1,24, .... x x2mm - 1, 112
where (4. 12..2..... 1m) "k Among these Tm blocks, we choose the blocks which satisfy k/4 + 12 + ..... Im Apparently, there are m blocks satisfying m|l, +2 + lm Because (17) true for = 1, we can pick a 1-net of Ω(1, 1, 1,...,1) with at most 2.2" elements. By a translation, (all elements add constant vector), we can pick 1-net of each block with at most
2.2m elements.
Totally there are at most 2.2"m 2:22 elements. These elements form a set P. We would km
prove P is 1-net of [2
In fact, for any x E [ suppose x is in 244, (.,1,,,,.,4444 After translating this block to 2(1, 1,..,, 1). is coincided with æo.
33

---

Published as a conference paper at ICLR 2022
S+
$
S_
Figure 1: A class of hard-to-learn MDPs where 84 and 8_ are absorbing state.
If zo E P. change 4 to i such that k144 + 12 + Lm. Suppose x' is the vector in block 12....,,ny, Im) that corresponds to zu in $2(1, 1,..,, ...,,,) 1). This gives E P. Moreover, d(x, x') S (m) only changes the first component.
1 because the translation from (2(12, 12.... .......,,n (mm
xo of P. we can find z in P 1211, ( 1) such that d(æg, m²) = because P I........... 1-net. Suppose To and 2 differs at the j-th component. We can change 1, to 1 s.t. k(4 15+1 +... Im- Suppose a' corresponds to x' in ( (m) and x" in 044..... 1-..... .m). By the definition of P, we know x" E Moreover, æ and only differ at the j-th component because of translation and the fact that zo and zó only differ at the j-th component. x' and x" also only differ at the j-th component because of translation. So we have and x" may only differ at the j-th component, i.e. d( ((x x²) S 1.
+ + ......4......
Recall that x" E: P. To conclude. can always find another vector P such that d(x, y) < 1. this means P is a 1-net of [2k]]". So (17) is proved.
Using this fundamental lemma and suppose game M satisfies the condition in Lemma E.6, by permuting the actions of M, we get (2k) games. They all satisfy the condition in Lemma E.6. Suppose the reward of the i-th game is (-) (i = 1, (2k:)")))))
We consider the following family of one-step games with stochastic reward: Let a (01, .2...., ).
1 x (a)e, i 1,2, (2k)
M){) (M E E|2K"" with M (a)
(18)
where in one-step game M the reward is sampled from (ernouli(MM))) (a)) if the joint action is a (0), ......, a.). Moreover, we define (0 as game whose reward is sampled from Bermoulli( independent of the action.
Then by the same argument in proof of Lemma E.3, we can easily prove Lemma E.2.
E.2 PROOF OF THEOREM E.
We are now ready to prove Theorem E.1 based on Lemma F.2.
Because 5 2 3, we construct class of general-sum Markov games as follows (see figure 1): the set of all joint-actions A can be divided into two sets + an A-
Transition Starting from $1, for E At, Ett.Prs4 a) = + 2(H-IT and Pi(s__ss a)
20 For a A=, (i a) = (1 = 3. For all h 2 1 and a E A.
(x(41194,0) and
1.
Rewards For any a and E [m], (1, a) 0 Or., a) and (s_, a) = 0, where h > 1. This also implies the Markov game cooperative.
If choose A+ as the joint action with reward Bernoullis + +e in M defined in (18). By the construction, for any pure-strategy policy æ, if the joint actions taken at step 1 is A+, have
34

---

Published as a conference paper at ICLR 2022
Algorithm 8 Mixed-expert FTRL for weighted adversarial bandits
Require: Hyper-parameters {meisesT {shssss Sequence
Initialize: Accumulators ty 0 for all 6' [A].
2: for t= 1, .,, do
3: Compute weight ut <- of/at.
4: Compute action distributions for all sub sub-experts d' E [A] by FTRL:
(a) Ne exp (-ORa//
by Σ
wy (6)) (a)
5: Compute p² [Ai by solving the linear system p²()) = Σイ= (b')0 ())
6: Sample sub-expert p'.
7: Sample action a' q" from sub-expert 6.
8: Play the action a', and observe the (bandit-feodback loss la(a').
9: Update accumulator for sub-expert b: ts + to + 1.
Compute the loss estimate 2), (.) E R as
10:
E, (a)1 fa = a'}
2 (a) F
(a) + 9
11:
Set Wh, (b) & Ut.
NE-gap(1) 2 E. The only useful information each episode is the transition at step 1. Transition from $1 to 84 can be viewed getting reward and transition from 81 s can be viewed as getting a 0 reward. So learning pure-strategy Nash equilibrium of this class of Markov games is equivalent learning pure-strategy Nash equilibrium of game for m players with stochastic reward. As result, by Lemma E.2, if the number of episodes
D A
2
De=14 4
K 40
S
4co
2 - 1)3
g2
then there exists general-sum Markov cooperative game MG on which the algorithm suffers from // e44-suboptimality, i.c.
E 2 8/4.
This finish the proof of Theorem E.I.
F ADVERSARIAL BANDIT WITH Low WEIGHTED SWAP REGRET
In this section, we describe and analyze our main algorithm for adversarial bandits with low weighted swap regret. Our Algorithm, Mixed-expert adversarial bandits, is described in Algorithm 8.
(FTRL) for weighted
Problem setting Throughout this section, we consider a standard (adversarial) bandit problem with action space is [A] = [I,...,AA A} for some A 2 1. We assume that the realized loss values & E [0, 1]4 and let (a) = [a]] denote the expected loss conditioned on (as usual) all information before the sampling of the action a' in Line & The hyperparameters in Algorithm
chosen
1)+ = 7t. ===== (A)()), VI((A),,
where the log factor
4 = log 88 8H/TTp))
(19)
35

---

Published as a conference paper at ICLR 2022
F.1 MAIN RESULT FOR ADVERSARIAL BANDIT WITH LOW WEIGHTED SWAP REGRET
We first define a strategy modification. A strategy modification is function F [A] - [A] which also be applied any action distribution μr E A., such that F o y gives the swap distribution which takes action F(a) with probability ja(a).
The swap regret (Blum Mansour, 2007; Ito, 2020) measures the difference between the cumulative realized loss for the algorithm and that for swapped action sequences generated by an arbitrary strategy modification P. Here, we consider weighted version of the swap regret with some non-negative weights { defined as
Rewap(? (1) ==
max
- ((F(()))))
(20)
[[]
We will also consider slightly modified version of the swap regret used in our analyses for learning CE, defined as
Rewap (1) == Σ
max
- - oFo
(21)
where p' is t-th action distribution (from which the action at is sampled from) played by the algorithm.
We now state main result of this section.
Lemma F.1 (Bound on weighted swap regret). If we execute Algorithm 8 for T rounds and the weights {ai} are chosen according to (2), then with probability least p/2, we have the following bounds on the swap regret simultaneously for all t E [T]:
Σ ailli(a') - (((((')) C(HA HAi/t),
Rawap(t)
Reway
max F[[A|-[A|
- (CUAV HA//O)
where C > O is some absolute constant.
The rest of this section is devoted to proving Lemma F.I, organized as follows. We first present some important properties of Algorithm in Section F:2. We then prove Lemma F.1 in Section F.3 using new auxiliary results on weighted adversarial bandits with predictable weights. Lastly, these auxiliary results stated and proved in Appendix F.4.
F.2 PROPERTIES OF ALGORITHM 8
Solution of the linear system In Line 5, we need to compute p' E A(A) by solving the linear system p²(-)= = Σt= p² (1")g" (.). Such p-(-) can be interpreted as the stationary distribution of a Markov chain over [A] with transition probability Pbblla) = (b).. This guarantees the existence of p' A such that (-) Σd= (b')a" (-). Moreover, p (-) can be computed efficiently (see e.g. Cohen et al. (2017b)).
FTRL update for each sub-expert Here we show that, the updates for any particular sub-expert b E [A] in Algorithm 8 is exactly equivalent an FTRL update (with loss sequence being the ones only over the episodes which ó sampled) which we summarize Algorithm This is important our proof relies on reducing the weighted swap regret linear combination of weighted regrets for each sub-expert b E [A].
To this, fix any b E [A]. When is sampled in Line 6 episode t, we have accumulator to and weight w., (b) 44 = /f at the end of episode Action al is chosen from distribution
(a() xa exp ((hh/wwr)
wy (b') (b)) (a)
36

---

Published as a conference paper at ICLR 2022
after (b) ue af/aa is observed. The loss estimate L, is
2r (a) + Le (a)1
(a + The
So from the sub-expert b's perspective, she is performing FTRL (follow the regularized leader) with changing step size and random weight (We summarize this Algorithm 9). Suppose the sub-expert chosen episode kı, k2,, kit, then the weighted regret for sub-expert b becomes
Rb( = sup 8" EAA
Σ
(b) ) ( (00+k..)) (00))
(22)
Bounded weight (b)
Recall {at} is chosen as in (2). We have the following bound:
af a af 01 a1(1-02) 02) ... (1 (1-aa)
1
(H + (H + 3)... ... +1) (H + +1)
1.2 (t-1) 1)
So for any s T' we have
a:/at < (H + W.
(23)
The weight Wn, (b) = af/a have a (non-random) upper bound W.
F.3 PROOF OF LEMMA F.1
We use b denote the sampled sub-expert at the i-th episode. Define 9 the r-algebra generated by all the random variables observed up to the end of the i-th episode.
First observe that for Rswap(t) (t) have the bound
Rewap (t) = max Σ -
FMAA- 1=1
< max
- &((())))((F())+++
max -(F(())))(((())))
[ 1=1
also, for Rewap()) we have the bound
Rewap (t)
max
Σ aalle((at- (F
[A
< max [A]
Σ
- ((0()))-((((()))))
[[A Σ (F
max
Term 11 and II can be bounded by concentration in similar fashion; here first focus term 11. Observe that at the i-th episode, as p' obtained Line 5 solves the equation
p'(a) - Σ p' (a).
we have b² p-) and a' ~ (-) has the same marginal distribution conditioned on G--1. where G--1 denote the -lalebrra generated by f; and all the random variables in the first i-1 episodes. There-
fore, fixing any strategy modification F [A] -> [A], we have (o(((((((bt) ((F((a)))) )
a bounded martingale difference sequence w.r.t. the filtration {G.), so by Azuma-Hoeffune inequality and (a{2 < 2H/tt.
H log 1/p t
Σ ((((((())))) 4(F(a))) ((F 2
Sp.
37

---

Published as a conference paper at ICLR 2022
As there is at most A strategy modifications, substitute with (4AA and take union bound to get
11 = m&x F [A
- (AAA://A)))AAAAAA CCC C.HHAu/t
(24)
simultaneously for all i E (T) with probability at least 1 - p/4. We also note that, by similar argument (as be is also distributed according to pt conditioned on the past), we have that
Σ ((((((((()) - (F p' p-)))))))=1-- s CVHA./ [A
max
(25)
Therefore for bounding both Rawap (t) and Rswap(t) (t), it suffices to bound term I.
We next bound term I. Define Uy == E [t] b' = b} and let ni be the value of t, at the end of the 1-th episode, i.e, nú = # (i 6² =b]] 6). We also suppose the sub-expert b was chosen at episode
I = k kg..... k2 up episode L. Then we have
Σ all((a)) ((F(0))
- all((d') ((F(b))
Cay (a Eug (F(b))
PEA
ni.
ΣΣ
al
(b) (a ) Exz (F(b))
BEAT=1
2ºt k 0 = a /at which is a simple
Here the last equation is because our choice of (b) corollary from the definition of af in Eq. (3).
Then because
w- (b)lea - 4, (F(b)) & max wr (b)le2g (att) (be4 =R((),
where R, (b) defined in (22) is the weighted regret (b) for sub-expert b, we can use our result on weighted adversarial bandits with predictable weights (Lemma F.2) bound this term (The upper bound W of the weight wbbb) can be taken as (H + 7)2 by the calculation of (23). Moreover, w, (b) = a, / and {ar )/ is increasing, so (w,(b))rz is non non-decreasing.). Recall that our choice of log term v = 4 log 4HAT log ATolo where p' S p/(AA). Thus by Lemma F.2, with probability at least p/(AA).
p
(b( < 15 max w. (b) (b) V Ambg+ +1 o) rsn
for all [7].
Taking a union bound, we get
Re(b)= < 15 max w,y(b) V Vnnfe++ + for all (t, E [T] x [A]
(26)
with probability at least p/4. On this event, we have
max Σ a(I(()') [A
a w (b)(ee (
(4g(F(
max
bEAT=1
38

---

Published as a conference paper at ICLR 2022
mi
0 w (b)(44)(( -4a (1)) F: [A]
Σ
max
aj (b)
BEA
Σ PEA
a max wT -- (1) Ang. + 15x)
h " O4
(15 Anle 15c)
ai
BEAA
2H
Σ
V Anje + 15c).
aEA
Here, (i) uses (26), (ii) uses the of is increasing w.r.t t' and (iii) uses maxosrsi of S 2H/t. Finally, because ΣeEA nj = t, by the concavity of + xz we have with probability at least 1 p/4.
1= max a'lli(aa)) -((E((a))(((((()))) =
(((F(b)))
30H
Σ
(V
Anng Ante Ange+ +.)
[A] i=1
t
hEA
30H
(AVEL + Ac)
t
30/H Au/
Combining this with (24) and (25), we finish the proof.
F.4 AUXILIARY LEMMAS FOR WEIGHTED ADVERSARIAL BANDIT WITH PREDICTABLE WEIGHTS
In this subsection, we consider the Follow the Regularized Leader (FTRL) algorithm (Lattimore & Szepesvári, 2020) with
1. changing step size,
2. weighted regret with --e--uusurablle weights and loss distributions,
3. high probability regret bound.
We present these results because the predictable weights would use are potentially unbounded from above; if weights are predictable and also bounded, then there may be an easier analysis.
Interaction protocol We first describe the interaction protocol between the environment and the player for this problem. At each episode t, the environment adversarially choose weight wa which takes values in R and distributions (Cet)ag[A)) where each Cat a distribution that takes values in P((0, 1)) (the space of distributions supported on [0, 1)). Then the player receives the weight wt. chooses an action a,, and observes a loss (4(0e) ~ La.,t- The action chosen at can be based on all the information in D, = {(a, wi, (a;)), w.)) Then, the environment can observe the player's action at and the incurred loss realization (a,), and use these information and some external randomness 2 to choose the weight and distributions (We-1. (La.(41)a((A) of the next episode. We will consider the following variant of FTRL algorithm for the player.
We denote l = (Br~c., [eEE(A) measurable. For some 0r E A the regret of the player up to episode is defined as
[0, 1]4 which is random vector but is (((aat)EE(A)
R =
w. (l(((())) (8",2,))
1=1
39

---

Published as a conference paper at ICLR 2022
Algorithm 9 FTRL for Weighted Regret with Changing Step Size and Predictable Weights for episode f I...., do
2: Observe wi > 0.
3: (a(a) &a exp(-(nu/w) >i= w;)((a)).
4: Take action a4 (-), and observe loss (at).
5:
(a()) + (,(a)1 {a, at /0,((a) + 76) for all a.
Let (2)) be sequence of external random variables which are identically and independently distributed as Unif([0, 1]) and are independent of all other random variables. We define F, aHaa, E, (es)) to be the sigma algebra generated by the random chosen action a,, the random loss (a.)). and the external random variables z; by episode I. We assume that the random weights and the random loss distributions (w,, (Cet (e())) are a FF)ec21-rredicabbl sequence, in the sense that (w,, (Lat)ae(A) is F:-1---maaa meeasurbll. Then Fs contains all information (random chosen action, random observed loss, random weight, and random loss distributions) before action 0++1 taken.
We assume the predictable sequence (we) ISieT have global (non-random) upper bound W. Then we define the log term log(AT[[ogg) W W1/p). We set
1) 76
At
F.4.1 REGRET BOUND
In the following, we consider to give high probability weighted regret bound for Algorithm 9.
Lemma F.2. Let (wt, (Lat) (((A))))) be any Fi-predictable sequence satisfying S mitteg W; S maxigt W; S for some constant (non-random) W > almost surely. Moreover suppose wi is non-decreasing. Then, following Algorithm with probability at least - 4p, for any 0 E AA and t < T we have
Σ we(li(a') (0" (.)) S 15 max my
[VAL++ + +1]
iSt
where log(AT([og, W1/p).
Proof. This lemma follows from the bound in Lemma F.3 and concentration step that we establish below.
Define M [lgg2 W7, and (k) w;1 {w, s 2*}. Then w;(k) is also F; measurable. We Consider sequence (w, - (0,, 4)) Since w, meeauuuurarbee.. (f, (0,, [-1 which means (w)()))(((()) (0,, (4)) )22 is martingale difference sequence
w.r.t filtration (FF). So by Azuma-Hoefiding inequality,
I Σ (x)()((s((a))) (0,, s 22 21 1
P TM
Taking a union bound, we have
PP vk [M], Σ wi(k)((((a') (0,, 5 2t 2211
2 1 P/TT.
(27)
Denote k' floga maxigt wi]. then we have
Vk E [M] Σ w. (K))(()((a') - (0,,4)) s 2" 2tc
C Σ w: (K))((()))))) 4.) < 2² 2th c Σ (l((aaa²) - (0,, 4,) S max Wi 2t
2
ist
40

---

Published as a conference paper at ICLR 2022
Then probability bound gives
Σ (((((()'- (0,, (0,,)))) - max wi 2
22-1/7 P/T.
ist
Taking a union bound, we get
w - (0,, max w, 2tz for all t [T]
with probability at least p. Summing the above and the regret bound shown in Lemma E.3, we finish the proof.
L
Lemma F.3. Let (wi, (La))e(()))121 be any Fe-predictable sequence satisfying S minggi W, S
maxis: Wi S W for some constant (non-ram moon-random) W > almost surely. Moreover, suppose wi is
non-decreasing. Then, following Algorithm with probability at least - 3pr any 0" E A and
t S T we have
wi (0. e2) < 10 max wy
[VAtc+
ist
where log(AT[[og, W1/p).
Proof. The regret (0)) can be decomposed into three terms
Rs (0*) wi (0, ((,
Wi 0, 0", E. + Σ ws 0c, l,
E.) + Σ wi 0r, Z; - Es
(A)
(B)
(C)
and we bound (A) in Lemma F.5, (B) in Lemma F.6 and (C) Lemma F.7.
Setting 17, % v - the conditions in Lemma F.5 and Lemma F.7 satisfied. Putting them together and take union bound, we have with probability 1 3p
Wi log A
A
R2 (0")
new;
Wet E5t
A
7:ll max Wy W: 2t 2 max wat/ i5!
17
i5t
1=1
Av 1
max Wi i5t
VAul+
+1+ 2V
VAt + s]
<10 uy
for allll a
tst
This proves the lemma.
The rest of this section is devoted the proofs of the Lemmas used in the proofs of Lemma F.3. We begin the following useful lemma adapted from Lemma in Neu (2015), which is crucial in constructing high probability guarantees.
Lemma F.4. For any predictable sequence of coefficients C, , (F))z2 and fixing we have with probability at least 1 - -p/(AT).
Cr S.A. C3 E [0, 2ya 4 w.f.t
Wi cr,, E, -6)-)))
(i) < max Wil eSt
41

---

Published as a conference paper at ICLR 2022
Proof. Define M [loge W7, and wa(k) w;1 (w, S ] By definition,
(x(k));; (a) = w/ (x)),, (a) {a= = =
wx( (a) 1 fa
0, (a) +%
0: (a) 1 7
2
2 (o)=aa)
(0)
(1) 2 log
(1+ 2% 2,, (a) (1) - a}
27 + 2w (e) (0)
2%
2+0, (a)
where (i) because
1+2/2 log (1 + 2) for all =20.
Defining the sum
wi(k) 2
mx(k)
S
cas (i) S.
2 (c,, e))
Then S, is F,-1 measurable since wt, Cts b are Fi meesurabbe. Using E. to denote the condi- tional expectation BI. [F.], we have
Cj (a)
1+ 27,w,(k),, (a) fa. = a}
)
E
exp
S.
E,-
exp
2
log
240 (a)
(6)
c: (a) (k)k, (a) 1 {a; = =
S E
1
240; (a)
c (a) w (k)&, (a) 1 {a+ a}
E
1 1
200, (a)
1 S < exp(S:)
where (1) is because log (1 + =2) < log (1 + 21 21) for any 0 < 21 < 1 and 22 2 -1. Here we are using the condition c (a) < 2x, to guarantee the condition is satisfied.
Equipped with the above bound, we can now prove the concentration result.
P
S s. S.)
PP
exp
Σ
S
5:)
ATM P
i=1
Li=1
p
Eg-1
exp
Σ
S. ss))
ATM
P
(3, s.)
[exp (S. s.
B12
exp
Er_1
ATM
P
(3, si)
Ex-2
exp
ATM
P ATM
S .... S
So we have
IP wi (1:) ct. 83 E.) < 22²1) 21 - pP((AMM)
Taking union bound,
P Vk E [M]
Σ t=1
(1) ( (co l, - (,) s - 2²11) 21 (AT)..
(28)
42

---

Published as a conference paper at ICLR 2022
Denote k' [log2 maxşgı wy) ], and note that
{Ak [M], Σ wi(k) (ai C, - -1i) -
s 2
C Σ ws (k') ( (cts - (b) s 2² of $ Σ wi (cis - .ai
S
max wil ist
Therefore, we have
P
wi
Cia
li - 1i)
s 2
max wit ist
21 (1-D/(AT).
This proves the lemma.
Using Lemma F.4, we can bound the (A) separately below.
Lemma F.5. If; S 2% for all i S t and {n/ / F22 is non-increasing, with probability 1 fof any E [7] and 0 E EAA
Wr log A
A Σ
1 W01t
Σ wi 0, 0r E
S
1Jc
2 ise
Proof. We the standard analysis of FTRL with changing step size, for example Exercise 28.12(b) in Lattimore & Szepesvári (2020). Notice the essential step size is n//w, which is non- increasing and the essential loss vector is w have
log A
KL(0++1
Σ w/ 0: 0", 0T,E.)
+
Σ
Wi (0:
01)1,es)
778
We claim that
(0. 0,01, Es)
KL (L(0++1|104
1h 2
0, 2
(29)
n7
In fact, applying Theorem 26.13 in Lattimore & Szepesvári (2020) gives that
0.1. (I(0++1110s) ?i u4,0 + (1 w;)0 P.).
7/4
for some u; E [0, 1]. Note that our E, only have at most one non-zero entry, i.e. E,(() >
if and only
if a = a; If 02 (a:) 2 O2+1 (a:), we have
tK 7) u,O, + (1 m):)) 0=) 2 (u,((((ss)
u,)0++1 (a:))
2
2
?h (B, P.) s 1h 0, (a,)))
2
Otherwise, (,(a,) < (.-1(a;)) so we have
(0, 0.11. &.)
[0:(a;) - 6 (a)1(a))((((a)) and and
-KL(0++1|00./mr < 0. In both cases, (29) is correct. As a result,
wi 0: 0-, 0Z,,)
Wi log A m
news (0.
2
1=1
We log A
wwwli (a)
nl
i=1 REA
W; log
+
1
Σ
Σ
ma,le E, (a) + max wit
7
2
Sst
i=1 aeA
43

---

Published as a conference paper at ICLR 2022
we log A
A
Σ
n:w;
+ max Wil iSt
2
where (i) is by using Lemma F.4 with (a(a) 7ji The any-time guarantee is justified by taking union bound.
Lemma F.6.
With probability 1 for any [T].
wi - 2,) S (0
Yow; + max wi v 2tt.
est
Proof. We further decompose the left side into
Σ
Ews(Be (0., l. - 1s
Σ wi 0i,ks l - Ea-1(ei))
+ Σ mi 0,
1
[2:]
i=1
The first term bounded by
Σ wi - B.-11(1) -1,1111
Σ wi
Oi,hi
0₂ 4
0; + Yi
i=1
7i
0j.
< A
0g
+ 7
To bound the second term, we use similar argument in the proof of Lemma F44, we define maxig: Wi, M [log, W1. and (k) = w; { w. S 2 }² notice
(B..2.
O, (a)
1 = a} (a)++1 REAA
[a =1
aEAA
thus (w)(k) (0,, F.-1 2,) Mi is bounded martingale difference sequence w.r.t. the filtration (Fi) By Azuma-Hoefiding inequality,
Σ (1b) 1, E5 - 2.) s we(k)) I / 2t t(20g2
with probability at least - p/TM. Taking a union bound, we get
wx(kk) (0,, 1 E. S 22. 1228 for all (f, E (T) x [M]
with probability at least p. On this event, choosing k' [log2 w]. have
wi 0,, E. [2
wi(k! (0, E.- 2.1 Es
i=1
2 22 max w; 22
This ends the proof.
Lemma E7. With probability p. for any E [T] and any 0" A if non-increasing in
Σ wi 00 - Ls s max Wil/ wit/7.
ist
44

---

Published as a conference paper at ICLR 2022
Proof. Define a basis {e of R by
af otherwise.
eg (a)
Then for all the j E [A], apply Lemma E.4 with q = 7tej. Since now cs(a) S yt S Y. the condition in Lemma F.4 is satisfied. As result, for any t E [T] and j [A], have with probability least 1 - p/ (TA) that
Σ wi (e,, e.) S 2 max wis/Th
ist
Taking a union bound, we have with probability at least p.
wi (e 2 - f.) S 2 max wo//te for (i,1) E [m]] x [T].
ist
Since any 0* is convex combination of {es on this event, we also have
we 00, 2, -6a) s 22max w/t7/ for all t e [
i=1
This finishes the proof.
45


Reviews:
[{"review_id": "asGcuqcxPQM", "reviewer": "Reviewer_Qf6T", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n1. The sample complexity of  $\\epsilon$-CE for general-sum games is significant and worth publishing. \n2. The proof of Theorem 6 is novel to me. In particular, the authors utilize the weighted swap regret lemma to derive the gap to the best CE agent. \n\nWeaknesses:\n1. The result of $\\epsilon$-CCE (Theorem 3) is based on previous results. It is not surprising given previous analysis about Nash-V learning (Tian 2021, et. al,)\n2. As pointed by the authors, the dependences on $S$ and $H$ are not tight yet.", "summary_of_the_paper": "This paper studies the problem of finite horizon multi-agent general-sum Markov games.  The proposed algorithm CE-V-Learning achieves $\\epsilon$-coarse correlated equilibirum (CCE) using $\\tilde{O}(H^5S\\max_{1\\leq i \\leq m}A_i/\\epsilon^2)$  episodes, and $\\epsilon$-correlated equilibrium (CE) using $\\tilde{O}(H^6S\\max_{1\\leq i \\leq m}A_i/\\epsilon^2)$  episodes. The sample complexity is polynomial in $\\max_{1\\leq i\\leq m}A_i$, while previous results had an exponential dependence on $m$ ($\\Pi_{1\\leq i\\leq m}A_i$).", "summary_of_the_review": "Overall, the paper is well written and the theorectical results are worth publishing. ", "strength_and_weaknesses": "", "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": "aKAbpj6hr3", "reviewer": "Reviewer_bdjf", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: The paper presents the first sample efficient algorithm for multi-player general sum Markov game and prove its convergence to CCE and CE. Though there are many *similar* types of paper in the field of theoretical reinforcement learning (i.e., a new setting with new sample efficient algorithm etc.), I found this one interesting. It solves an important question and the technique is non-trivial.\n\n\n\nMinor issues:\n(1) Proposition 1 and Theorem A.2 are results of Rubinstein et al. 2016. Though the authors make this clear enough, I suggest them make it cleaner (e.g. merge into one single proposition), since it is not the contribution of this paper, and I think it is only used to motivated this paper (hence no need to expand with one page.)\n\n(2) There are some recent paper that accelerates the classic no regret algorithms that approach CE or CCE. Though it is not directly related, I suggest cite them as they are closely related to this paper.\n\n[1] Syrgkanis, Vasilis, et al. \"Fast Convergence of Regularized Learning in Games.\" Advances in Neural Information Processing Systems 28 (2015)\n\n[2] Chen, Xi, and Binghui Peng. \"Hedging in games: Faster convergence of external and swap regrets.\" Advances in Neural Information Processing Systems 33 (2020).", "summary_of_the_paper": "The paper proposes algorithm for learning coarse correlated equilibrium (CCE) and correlated equilibrium (CE) of multi-player general-Sum Markov Games, the propose algorithm has polynomial dependence on the number of state and the horizons. The proposed algorithm builds upon the Nash V-learning of (Bai et al. 2020), and incorporate several new ideas.", "summary_of_the_review": "Overall, I think it is interesting paper with solid contribution. I vote for acceptance.\n\n\n------------------------------------------------------\nPost rebuttal:\n\nThe author revised their paper and addressed some minor issues. My positive evaluation for the paper remains and I vote for acceptance.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "DapLh9gt74g", "reviewer": "Reviewer_q1AK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n+ The sample complexity of learning Markov games is a timely and important topic in the areas of multi-agent reinforcement learning.\n+ This paper provides new insights on what type of equilibria and/or structural assumptions on Markov games may admit sample-efficient learning polynomially in the size of the joint action spaces.\n\nWeaknesses:\n- Although the authors showed polynomial sample complexity for NE of Markov potential games, there appears to be a large gap to the lower bound.\n- Some part of the paper is hard to follow and need better explanations.", "summary_of_the_paper": "This paper studied the sample complexity for learning the coarse correlated equilibrium (CCE) and correlated equilibrium (CE) of m-player general-sum Markov games (MG), as well as learning the Nash equilibrium (NE) of Markov potential games (MPG). For MG, the authors proposed an algorithm with sample complexity that grows polynomially in $\\max_{i\\leq m} A_i$ to achieve $\\epsilon$-approximate CCE and CE. For MPG, the authors proposed an algorithm with sample complexity that grows polynomially in $\\sum_{i\\leq m} A_i$ to achieve $\\epsilon$-approximate NE.", "summary_of_the_review": "1. This paper considered the sample complexity of learning multi-player Markov games with relaxed equilibrium notions (CE and CCE) and special structure (Markov potential games). The results in this paper are quite interesting. However, starting from Section 4, the presentation is a bit hard to follow. First, the algorithm for CCE, the first key equilibrium of MG, is relegated to the appendix. I went over the proof quickly and it appears a technique from [Tian et al. 2021] has been adopted to improve an H factor in [Bai et al. 2020]. However, [Bai et al. 2020] considered NE and it remains unclear what difference the properties of CCE make in this paper to allow the authors to achieve the claimed sample complexity.\n\n2. The description of the CE algorithm is also unclear. It seems the FTRL technique is the key to the design of this algorithm. Is this technique brand new or adapted from some earlier work? Also, it might be better to define some jargons (e.g., sub-expert) for readers to fully understand the meaning of the algorithm. Also, it would be better to provide more intuition behind the algorithm design for CE. The authors mentioned that they adopted and modified the policy of [Bai et al. 2020]. It would be better if the authors could be more specific on what modifications are needed here.\n\n3. Although the paper is mostly a theory paper, it would be nice if the authors could provide some experimental results to verify the sample complexity of the proposed algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AocLBAmOT6k", "reviewer": "Reviewer_6yah", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This is technical paper with very impressive results. I am really surprised with the running time of the provided algorithm for convergence of their algorithm to Nash equilibria in Markov potential games ($1/\\epsilon^3$ improving the $1/\\epsilon^6$). Note though that the updates are not simultaneous, in the sense that one agent updates at a time. Moreover, the analysis and lower bounds look quite nice. I feel this paper should get accepted!", "summary_of_the_paper": "The paper studies general sum episodic Markov Games. They provide an algorithm which is effectively V-learning with Follow the regularized leader subroutine (FTRL is hedge algorithm in their case). They prove convergence of their algorithm to $\\epsilon$- CCE (coarse correlated equilibria) and $\\epsilon$-CE equilibrium policies in $1/\\epsilon^2$ with dependence on \\max_{i} A_{i} (cardinality of action space of an individual rather than the whole action space). This happens due to ``independent updates\" of the agents. Moreover for the case of potential markov games, they manage to show $1/\\epsilon^3$ convergence to $\\epsilon$-Nash pure Nash policies, improving Leonardos et al paper and solving an open question about convergence to deterministic policies. \nHowever, the agents do not update simultaneously (i.e., the updates are not concurrent!). They also provide lower bounds.", "summary_of_the_review": "I feel the paper has quite nice technical contributions. The results are very interesting too. ", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes algorithms for learning (coarse) correlated equilibrium in multi-agent general-sum Markov games, with improved sample complexities that are polynomial in the maximum size of the action sets of different players. This is a very solid work along the line of multi-agent reinforcement learning and there is unanimous support to accept this paper. Thus, I recommend acceptance.
Decision: Accept (Poster)