Year: 2021

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 Ai actions per player. First, we design algorithms for learning an ε-Coarse Correlated Equilibrium (CCE) in Õ(HSmaxi≤mAi/ε) episodes, and an ε-Correlated Equilibrium (CE) in Õ(HSmaxi≤mAi /ε) episodes. This is the first line of results for learning CCE and CE with sample complexities polynomial in maxi≤mAi. 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 ε-approximate Nash equilibrium within Õ(S ∑ i≤mAi/ε ) episodes (when only highlighting the dependence on S, Ai, and ε), which only depends linearly in ∑ i≤mAi and significantly improves over the best known algorithm in the ε dependence. Overall, our results shed light on what equilibria or structural assumptions on the game may enable sample-efficient learning with many players.

text: ∑ i≤mAi/ε
3) episodes (when only highlighting the dependence on S, Ai, and ε), which only depends linearly in ∑ i≤mAi and significantly improves over the best known algorithm in the ε dependence. Overall, our results shed light on what equilibria or structural assumptions on the game may enable sample-efficient learning with many players.

heading: 1 INTRODUCTION
text: Multi-agent reinforcement learning (RL) has achieved substantial recent successes in solving artificial intelligence challenges such as 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; Trott 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-efficiently solve multi-player games with a large number of players remains elusive, especially in 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 simultaneous plays is equal to the product of the number of actions for each player, which scales exponentially in the number of players. Such an exponential dependence is indeed known to be unavoidable in the worst-case for certain standard problems. For example, for learning an 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; Rubinstein, 2016) shows that at least exponentially many queries (samples) is 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 or 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 generalsum Markov games (MGs) withm players,H steps, S states, andAi 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 ε-approximate Coarse Correlated Equilibrium (CCE) with Õ(H5Smaxi∈[m]Ai/ε2) episodes of play (Section 3). Our algorithm CCE-VLEARNING is a multi-player adaptation of the Nash V-Learning algorithm of Bai et al. (2020).
• We design an algorithm CE-V-LEARNING which learns the stricter notion of ε-approximate Correlated Equilibrium (CE) with Õ(H6 maxi∈[m]A2i /ε2) 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 maxi∈[m]Ai, and improves significantly in the Ai dependency over the current best algorithm which scales with ∏ i∈[m]Ai.
• Technically, our algorithm CE-V-LEARNING makes several major modifications over CCEV-LEARNING in order to learn the CE (Section 4.2). Notably, inspired by the connection between CE and low swap-regret learning, we use a mixed-expert Follow-The-Regularized 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 on weighted swap regret and weighted regret with predicable weights, which may be of independent interest.
• Finally, we consider learning Nash equilibrium in Markov Potential Games (MPGs), an important subclass of general-sum Markov games. By a reduction to single-agent RL, we design an algorithm NASH-CA that achieves Õ(ΦmaxH3S ∑ i∈[m]Ai/ε
3) sample complexity, where Φmax ≤ Hm is the bound on the potential function (Section 5). Compared with the recent result of (Leonardos et al., 2021), we significantly improves the ε dependence from their 1/ε6.

heading: 1.1 RELATED WORK
text: Learning equlibria 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 names with m players and Ai 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,maxi≤mAi)-sample complexity algorithms by independent no-regret learning (Hart & Mas-Colell, 2000; Hart, 2005; Syrgkanis et al., 2015; Goldberg & Roth, 2016; Chen & Peng, 2020; Daskalakis et 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 is still PPAD-hard (Daskalakis, 2013).
Markov 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 et al., 2020; Bai et al., 2020; Zhang et al., 2020; Liu et al., 2021; Chen et al., 2021; Jin et al., 2021; Huang et al., 2021) and learning various equilibria in general-sum Markov games (Liu et al., 2021; Bai et al., 2021), building on techniques for learning single-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 ∏ i≤mAi due to the model-based nature of their algorithm. Algorithms for learning CE in extensive-form games has been studied in (Celli et al., 2020), 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 et al., 2018; Leonardos et al., 2021; Zhang et al., 2021), a subset of general-sum Markov games in which the Nash equilibrium admits more efficient algorithms. Leonardos et al. (2021) gives a sample-efficient algorithm based on the policy gradient method (Agarwal et 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.

heading: 2 PRELIMINARIES
text: 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, {Ai}mi=1 ,P, {ri} m i=1), where H is the episode length, S is the state space with |S| = S, Ai is the action space for the ith player with |Ai| = Ai. Without loss of generality, we assume Ai = [Ai]. We let a := (a1, · · · , am) denote the vector of joint actions taken by all the players and A = A1 × · · · × Am denote the joint action space. Throughout this paper we assume that S and Ai are finite. The transition probability P = {Ph}h∈[H] is the collection of transition matrices, where Ph(·|s,a) ∈ ∆S denotes the distribution of the next state when actions a are taken at state s at step h. The rewards ri = {rh,i}h∈[H],i∈[m] is the collection of reward functions for the ith player, where rh,i(s,a) ∈ [0, 1] gives the deterministic1 reward of ith player if actions a are taken at state s at step h. Without loss of generality, we assume the initial state s1 is deterministic. A key feature of general-sum games is that the rewards ri are in general different for each player i, and the goal of each player is to maximize her own cumulative reward.
Policy, value function A product policy is a collection of m policies π := {πi}i∈[m] where πi is the (potentially history-dependent) policy for the i-th player. We first focus on the case of Markov product policies, in which πi = {πh,i : S → ∆Ai}h∈[H], and πh,i(ai|s) is the probability for the ith player to take action ai at state s at step h. For a policy π and i ∈ [m], we use π−i := {πj}j∈[m],j 6=i to denote the policy of all but the ith player. The value function V πh,i(s) : S → R is defined as the expected cumulative reward for the ith player when policy π is taken starting from state s and step h:
V πh,i(s) := Eπ
[ H∑
h′=h
rh′,i(sh′ ,ah′) ∣∣∣∣∣sh = s ] . (1)
Definition of the Q function and Bellman equations can be found in Appendix B.
Best response & Nash equilibrium For any product policy π = {πi}i∈[m], the best response for the ith player against π−i is defined as any policy π† such that V π†,π−i 1,i (s1) = supπ′i V π′i,π−i 1,i (s1). For any Markov product policy, this best response is guaranteed to exist as the above maximization problem is equilvalent to solving a Markov Decision Process (MDP) for the ith player. We will also use the notation V †,π−i1,i (s1) to denote the above value function V π†,π−i 1,i (s1).
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.e., for all i ∈ [m],
V π1,i(s1) = V †,π−i 1,i (s1).
1Our results can be straightforwardly generalized to Markov games with stochastic rewards.
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(π) := max i∈[m] [ sup µi V µi,π−i 1,i (s1)− V π 1,i(s1) ] .
For any ε ≥ 0, we say π is ε-approximate Nash equilibrium if NE-gap(π) ≤ ε.
General correlated policy A general correlated policy π is a set of H maps π := {πh : R × (S ×A× R)h−1 × S → ∆A}h∈[H]. The first argument of πh is a random variable z ∈ R, 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 πh is a general distribution of actions in A = A1 × · · · × Am (unlike product policies in which the action distribution is a product distribution). The random variable z is sampled from some underlying distribution which may be shared among all steps h ∈ [H]. For any correlated policy π = {πh}h∈[H] and any player i, we can define a marginal policy π−i as a set of H maps π−i := {πh,−i : R × (S × A × R)h−1 × S → ∆A−i}h∈[H] where A−i := A1 × · · · ×Ai−1 ×Ai+1 × · · · ×Am, and the output of πh,−i is defined as the marginal distribution of the output of πh restricted to the space A−i. For any general correlated policy π, we can define its initial state value function V π1,i(s1) similar as (1). The best response value of the i th player against π is V †,π−i1,i (s1) = supµi V µi,π−i 1,i (s1), where V µi,π−i 1,i (s1) is the value function of the policy (µi, π−i) (the ith player plays according to general policy µi, and all other players play according to π−i), and the supremum is taken over all general policy µi of the ith player.
Learning setting Throughout this paper we consider the interactive learning (i.e. exploration) setting where algorithms are able to 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.

heading: 2.1 EXPONENTIAL LOWER BOUND FOR LEARNING APPROXIMATE NASH EQUILIBRIUM
text: 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| = ∏m i=1Ai which scales exponentially in m (if each Ai ≥ 2), naive algorithms for learning Nash equilibrium may learn all ri(a) by enumeratively querying all a ∈ 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(Ω(m)) sample complexity lower bound for learning approximate Nash, even in one-step general-sum games (Chen et al., 2015; Rubinstein, 2016):
Proposition 1 (Lower bound for learning approximate Nash (Rubinstein, 2016); Formal version deferred to Proposition A.2). There exists some absolute constant ε0 > 0 and a family of m-player general-sum Markov games for any m with H = 1, S = 1, Ai = 2, and deterministic rewards, such that any algorithm that is able to find an ε0-approximate Nash equilibrium with high probability must at least play 2Ω(m) samples (episodes).
This suggests that the Nash equilibrium as a solution concept may be too hard to learn efficiently for MGs with a 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.

heading: 3 EFFICIENT LEARNING OF COARSE CORRELATED EQUILIBRIA (CCE)
text: Given the difficulty of learning Nash when the number of players m is large (Proposition 1), we consider learning other relaxed notions of equilibria for general-sum MGs. Two standard notions of equilibria for games are the Correlated Equilbrium (CE) and Coarse Correlated Equilibrium (CCE), and they satisfy {Nash} ⊂ {CE} ⊂ {CCE} for general-sum MGs (Nisan et al., 2007). We begin by considering learning CCE (most relaxed notion above) for Markov games.
Definition 2 (ε-approximate CCE for general-sum MGs). We say a (general) correlated policy π is an ε-approximate Coarse Correlated Equilibrium (CCE) if
max i∈[m]
( V †,π−i 1,i (s1)− V π 1,i(s1) ) ≤ ε.
We say π is an (exact) CCE if the above is satisfied with ε = 0.
The following result shows that there exists an algorithm that can learn an ε-approximate CCE in general-sum Markov games within Õ(H5Smaxi∈[m]Ai/ε2) episodes of play. Theorem 3 (Learning ε-approximate CCE for general-sum MGs). There exists an algorithm CCEV-LEARNING (Algorithm 4) for m-player general-sum MGs, such that running it for
K ≥ O ( H5Smaxi∈[m]Aiι
ε2 + H4Sι3 ε
) ,
episodes (ι = log(mmaxi∈[m]AiHSK/(pε)) is a log factor), we have with probability at least 1 − p that the certified policy π̂ defined in Algorithm 2 is an ε-approximate CCE, i.e. maxi∈[m] ( V †,π̂−i 1,i (s1)− V π̂1,i(s1) ) ≤ ε.
Mild dependence on action space For small enough ε, the sample complexity featured in Theorem 3 scales as Õ(H5Smaxi∈[m]Ai/ε2). Most notably, this is the first algorithm that scales with maxi∈[m]Ai, and exhibits a sharp difference in learning Nash and learning CCE in view of the exp(Ω(m)) lower bound for learning Nash in Proposition 1. Indeed, existing algorithms such as Multi-Nash-VI Algorithm with CCE subroutine (Liu et al., 2021) does require Õ(H3S2 ∏m i=1Ai/ε
2) episodes of play, which scales with ∏ i∈[m]Ai due to its model-based nature. We achieve significantly better dependence on Ai and also S, though slightly worse H dependence.
Overview of algorithm and techniques Our CCE-V-LEARNING algorithm (deferred to Appendix C.1 due to space limit) is a multi-player adaptation of the Nash V-Learning algorithm of Bai et al. (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 a “no-regret” like guarantee for each player at each (h, s) (Lemma C.3), with choice of hyperparameters coming from Tian et al. (2021) in order to achieve a slightly better sample complexity. When combined with our “certified correlated policy” procedure (Algorithm 2), our algorithm outputs a policy that is ε-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 instead of a product of independent policies as in Bai et al. (2020). The key feature allowing this maxi∈[m]Ai dependence is that this algorithm uses uncoupled learning for each player, as opposed to the centralized model-based algorithm of Liu et al. (2021). The full proof of Theorem 3 can be found in Appendix C.

heading: 4 EFFICIENT LEARNING OF CORRELATED EQUILIBRIA (CE)
text: In this section, we move on to considering the harder problem of learning Correlated Equilibria (CE). We first present the definition of CE in Markov games. Definition 4 (Strategy modification for ith player). A strategy modification φ := {φh,s}(h,s)∈[H]×S for player i is a set of S × H functions φh,s : Ai → Ai. A strategy modification φ can be composed with any policy π to give a modified policy φ π defined as follows: At any step h and state s, if π chooses to play a = (a1, . . . , am), the modified policy φ π will play (a1, . . . , ai−1, φh,s(ai), ai+1, . . . , am). We use Φi denote the set of all possible strategy modifications for player i. Definition 5 (ε-approximate CE for general-sum MGs). We say a (general) correlated policy π is an ε-approximate CE if
max i∈[m] sup φ∈Φi
( V φ π1,i (s1)− V π 1,i(s1) ) ≤ ε.
We say π is an (exact) CE if the above is satisfied with ε = 0.
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).

heading: 4.1 ALGORITHM DESCRIPTION
text: Our algorithm CE-V-LEARNING (Algorithm 1) builds further on top of CCE-V-LEARNING and Nash V-Learning, and makes several novel modifications in order to learn the CE. The key feature of CE-V-LEARNING is that it uses a ow weighted swap regret algorithm (mixed-expert FTRL) for all (s, h, i). At a high-level, CE-V-LEARNING consists of the following steps:
• Line 6-11 (Sample action using mixed-expert FTRL): For each (h, s) we maintain Ai “subexperts” indexed by b′ ∈ [Ai] (Each sub-expert represents an independent “expert” that runs her own FTRL algorithm). Sub-expert b′ first computes an action distribution qb ′ (·) ∈ ∆Ai via
Follow-the-Regularized-Leader (FTRL; Line 8). Then we employ a two-step sampling procedure to obtain the action: First sample a sub-expert b from a suitable distribution µ computed from {qb′}b′∈[Ai], then sample the actual action ah,i from qb.
• Line 13-17 (Take action and record observations): Player i takes action ah,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 V h,i using step-size αt and bonus βt.
Finally, after executing Algorithm 1 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 k and l in line 1 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: αt = (H + 1)/(H + t), ηt = √ ι/Ait, βt = cH 2Ai √ ι/t+ 2cH2ι/t. (2)
The constants αjt used in Algorithm 2 is defined as α0t := ∏t k=1 (1− αk) , α j t := αj ∏t k=j+1 (1− αk) . (3)
Note that for any t ≥ 1, {αjt}1≤j≤t sums to one and defines a distribution over [t].

heading: 4.2 OVERVIEW OF TECHNIQUES
text: Here we briefly overview the techniques used in Algorithm 1.
Minimizing swap regret via mixed-expert FTRL. The key technical advance in our Algorithm 1 over CCE-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—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 to usual low-regret learning (Blum & Mansour, 2007), which for any bandit problem withAi actions maintains Ai 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 b and the action from this sub-expert. The distribution µ(·) 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 αit, 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 G.2, and the consequent analysis for the weighted swap regret in Appendix G.1, both of which may be of independent interest.
Proposal distributions. Finally, a nuanced but important new design in CE-V-LEARNING is that all sub-experts compute a proposal action distribution to sample the sub-expert and the associated action.
Algorithm 1 CE-V-LEARNING for general-sum MGs (i-th player’s version) 1: Initialize: For any (s, a, h), set V h,i(s) ← H , Nh(s) ← 0. Set µh(a|s) ← 1/Ai, qb ′
h (a|s) ← 1/Ai, `b ′ h,t(a|s)← 0, N b ′
h (s)← 0 for all (b′, a, h, s, t) ∈ [Ai]× [Ai]× [H]× S × [K]. 2: for episode k = 1, . . . ,K do 3: Receive s1. 4: for step h = 1, . . . ,H do 5: // Compute proposal action distributions by FTRL 6: Update accumulator t := Nh(sh)← Nh(sh) + 1. Set ut ← αtt/α1t . 7: Let tb′ ← N b ′ h (sh) for all b ′ ∈ [Ai] for shorthand. 8: Compute the action distribution for all sub-experts b′ ∈ [Ai]:
qb ′ h (a|sh) ∝a exp ( − (ηtb′/ut) ∑tb′ τ=1 wh,τ (b ′|sh)`b ′ h,τ (a|sh) ) .
9: // Sample sub-expert b and action from qb(·) 10: Compute µh(·|sh) ∈ ∆[Ai] by solving µh(·|sh) = ∑Ai b′=1 µh(b ′|sh)qb ′
h (·|sh). 11: Sample sub-expert b ∼ µh(·|sh), and then action ah,i ∼ qbh(·|sh). 12: // Take action and feed the observations to sub-expert b 13: Take action ah,i, observe the action ah,−i from the other players. 14: Observe reward rh,i = rh,i(sh, ah,i,ah,−i) and next state sh+1 from the environment. 15: Update accumulator for sampled sub-expert: tb := N bh(sh)← N bh(sh) + 1. 16: Compute loss estimator
`bh,tb(a|sh)← [ H − h+ 1− (rh,i + min{V h+1,i(sh+1), H − h}) ] /H · 1 {ah,i = a}
qbh(ah|sh) + γtb .
17: Set wh,tb(b|sh)← ut. 18: // Optimistic value update 19: V h,i (sh)← (1− αt)V h,i (sh) + αt ( rh,i (sh, ah,i,ah,−i) + V h+1,i (sh+1) + βt ) .
Algorithm 2 Certified correlated policy π̂ for general-sum MGs 1: Sample k← Uniform([K]). 2: for step h = 1, . . . ,H do 3: Observe sh, and set t← Nkh (sh) (the value of Nh(sh) at the beginning of the k’th episode). 4: Sample l ∈ [t] with P(l = j) = αjt (c.f. Eq. (3)). 5: k ← klh(sh) (the episode at the end of which the state sh is observed exactly l times). 6: Jointly take action (ah,1, ah,2, . . . , ah,m) ∼ ∏m i=1 µ k h,i(·|sh), where µkh,i(·|sh) is the policy
µh,i(·|sh) at the beginning of 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 for the sampled sub-expert. Our design is required here as otherwise the sub-experts are required to predict the next time when it is sampled in order to compute the weighted FTRL update, which is impossible.

heading: 4.3 THEORETICAL GUARANTEE
text: We are now ready to present the theoretical guarantee for our CE-V-LEARNING algorithm. Theorem 6 (Learning ε-approximate CE for general-sum MGs). Suppose we run the CE-VLEARNING algorithm (Algorithm 1) for all m players for
K ≥ O ( H6Smaxi∈[m]A 2 i ι
ε2 + H4Smaxi∈[m]Aiι 3 ε
) ,
episodes (ι = log(mmaxi∈[m]AiHSK/(pε)) is a log factor). Then with probability at least 1 − p, the certified correlated policy π̂ defined in Algorithm 2 is an ε-approximate CE i.e. maxi∈[m] supφ∈Φi V φ π h,i (s1)− V π̂1,i(s1) ≤ ε.
Discussions To the best of our knowledge, Theorem 6 presents the first result for learning CCE that scales polynomially with maxi∈[m]Ai, which is significantly better than the best known existing algorithm of Multi-Nash-VI with CE subroutine (Liu et al., 2021) whose sample complexity scales with ∏ i∈[m]Ai. Similar as in Theorem 3, this follows as our CE-V-LEARNING performs uncoupled learning for each player, whereas Liu et al. (2021) uses model-based centralized learning.
We also observe that our sample complexity for learning CE is higher than for learning CCE by a factor of Õ(H maxi∈[m]Ai), which is expected as CE is a strictly harder notion of equilibrium and required a more sophisticated mixed-expert FTRL technique in the inner loop of the algorithm.
Finally, combining Theorem 3 & 6 with the exponential lower bound for learning Nash (Section 2.1), we obtain a full characterization of which equilibria can be learned with poly(m) sample complexity in general-sum Markov games: This is possible for CCE and CE, but not Nash.

heading: 5 LEARNING NASH EQUILIBRIA IN MARKOV POTENTIAL GAMES
text: In this section, we consider learning Nash equilibria in Markov potential games (MPGs), an important subclass of general-sum 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, we provide an alternative algorithm NASH-CA that also achieves a mild dependence on m and an improved dependence on ε by a simple reduction to single-agent learning.

heading: 5.1 MARKOV POTENTIAL GAMES
text: We first present the definition of MPGs. Our definition is the finite-horizon variant2 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 7. (Markov potential games) A general-sum Markov game is a Markov potential game if there exists a potential function Φ : (∆A1)
H × · · · × (∆Am)H → [0,Φmax], such that for any i ∈ [m], any two policies πi, π′i of the ith player, and any policy π−i of other players, the difference of the value functions of the ith player with policies (πi, π−i) and (π′i, π−i) is equals the difference of the potential function on the same policies, i.e.,
V πi,π−i 1,i (s1)− V π′i,π−i 1,i (s1) = Φ(πi, π−i)− Φ(π ′ i, π−i). (4)
Note that the range of the potential function Φmax admits a trivial upper bound Φmax ≤ mH (this can be seen by varying πi for one i at a time). An important example of MPGs is Markov Cooperative Games (MCGs) where all players share the same reward ri ≡ r.

heading: 5.2 ALGORITHM AND THEORETICAL GUARANTEE
text: We present a simple algorithm NASH-CA (Nash Coordinate Ascent) for learning an ε-approximate Nash equilibrium in MPGs. As its name suggests, the algorithm operates by solving single-agent Markov Decision Processes (MDPs) one player at a time, and intrinsically performing coordinate ascent on 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 in Algorithm 3. We remark in passing that NASH-CA is additionally guaranteed to output a pure-strategy Nash equilibrium (cf. Appendix E for definition). Theorem 8 (Sample complexity for NASH-CA). For Markov potential games, with probability at least 1 − p, Algorithm 3 terminates within 4Φmax/ε steps of the while loop, and outputs an ε-approximate (pure-strategy) Nash equilibrium. The total episodes of play is at most
K = O ( ΦmaxH 3S ∑m i=1Aiι
ε3 +
ΦmaxH 3S2 ∑m i=1Aiι 2
ε2
) ,
2Our results can easily adapted to the discounted infinite time horizon setup.
Algorithm 3 NASH-CA for Markov potential games Require: Error tolerance ε
1: Initialize: π = {πi}i∈[m], where πi = {πh,i}(h,i)∈[H]×[m] for some deterministic policy πh,i. 2: while true do 3: Execute policy π for N = Θ(H
2ι ε2 ) episodes and obtain V̂1,i(π) which is the empirical average
of the total return under policy π. 4: for player i = 1, . . . ,m do 5: Fix π−i, and let the ith player run UCBVI-UPLOW (Algorithm 7) for Ki = Θ(H 3SAiι ε2 +
H3S2Aiι 2
ε ) episodes and get a new deterministic policy π̂i. 6: Execute policy (π̂i, π−i) for N = Θ(H 2ι ε2 ) episodes and obtain V̂1,i(π̂i, π−i) which is the empirical average of the total return under policy (π̂i, π−i). 7: Set ∆i ← V̂1,i(π̂i, π−i)− V̂1,i(π). 8: if maxi∈[m] ∆i > ε/2 then 9: Update πj ← π̂j where j = arg maxi∈[m] ∆i.
10: else 11: return π
where ι = log(mHSKmax1≤i≤m Aiεp ) is a log factor.
Discussions For small enough ε, the sample complexity for the NASH-CA algorithm in the above Theorem is Õ(ΦmaxH3S ∑ i≤mAi/ε
3). As Φmax ≤ mH , this at most scales with the number of players as m ∑ i≤mAi, 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,maxi≤mAi) dependence, and significantly improves on the ε dependence from their ε−6 to ε−3. In addition, our algorithm does require assumptions such 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 Õ(H3S ∏m i=1Ai/ε
2) of the Nash-VI algorithm (Liu et al., 2021) for general-sum MGs (not restricted to MPGs), our NASH-CA algorithm doesn’t suffer from the exponential dependence on m thanks to the MPG structure. We do achieve a looser in the dependence on ε, yet overall our sample complexity is still better unless ε < ( ∑m i=1Ai)/( ∏m i=1Ai) is exponentially small.
A lower bound To accompany Theorem 8, we establish a sample complexity lower bound of Ω(H2 ∑m i=1Ai/ε
2) for learning pure-strategy Nash in MCGs and hence MPGs (Theorem F.1 in Appendix F). This lower bound improves in the Ai dependence over the naive reduction to singleplayer MDPs (Domingues et al., 2021), which gives Ω(H3Smaxi∈[m]Ai/ε2), though is loose on the S,H dependence. The improved Ai dependence is achieved by constructing a novel class of hard instances of on one-step games (Lemma F.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 Õ( ∑m i=1Ai/ε 3) or the Õ( ∏m i=1Ai/ε 2) of Liu et al. (2021), which we leave as future work.

heading: 6 CONCLUSION
text: This paper investigates the question of when can we solve general-sum Markov games (MGs) sampleefficiently 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. In 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 to perform sample-efficient 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.

heading: B Q FUNCTION AND BELLMAN EQUATIONS
text: In general-sum Markov games, recall that we have defined the value function V πh,i(s) : S → R of a Markov product policy π as the expected cumulative reward for the ith player when policy π is taken
starting from state s and step h:
V πh,i(s) := Eπ
[ H∑
h′=h
rh′,i(sh′ ,ah′) ∣∣∣∣∣sh = s ] .
We can similarly define the Q-value function Qπh : S ×A → R as the expected cumulative rewards received by the ith player starting from state-action pair (s,a) and step h:
Qπh,i(s,a) := Eπ
[ H∑
h′=h
rh′,i(sh′ ,ah′) ∣∣∣∣∣sh = s,ah = a ] .
For convenience of notation, we define operators Ph and Dπ: For any value function V and any action-value function Q,
[PhV ](s,a) := Es′∼Ph(·|s,a)V (s ′), [DπQ](s) := Ea∼π(·|s)Q(s,a).
From these definitions, we have the Bellman equations
Qπh,i(s,a) = (rh,i + PhV πh+1,i)(s,a), V πh,i(s) = (DπhQπh,i)(s)
for all (i, s,a, h) ∈ [m]×S ×A× [H] (where we have set V πH+1,i(s) = 0 for all h, i ∈ [H]× [m]).

heading: C PROOFS FOR SECTION 3

heading: C.1 ALGORITHM FOR LEARNING CCE IN GENERAL-SUM MARKOV GAMES
text: Our algorithm used to learn CCE in general-sum MGs is a combination of Algorithm 4 and Algorithm 2. 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 a 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-parameters as follows:
αt = H + 1
H + t , ηt =
√ Hι
Ait , βt = c
√ H3Aiι
t + 2c
H2ι
t ,
where c > 0 is some absolute constant, and ι = log(mmaxi∈[m] AiHSKpε ) is a log factor. The choice of ηt follows the V-OL algorithm in Tian et al. (2021) which helps to shave off an 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 ι to be C log(mmaxi∈[m] AiHSKpε ) 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.

heading: C.2 PROOF OF THEOREM 3
text: We begin with an auxiliary lemma on αjt (its definition is in (3)).
Lemma C.1 (Lemma 4.1 in Jin et al. (2018)). The following properties hold for αjt :
1. 1√ t ≤ ∑t j=1 αjt√ j ≤ 2√ t for every t ≥ 1 .
2. maxj∈[t] α j t ≤ 2Ht and ∑t j=1 ( αjt )2 ≤ 2Ht for every t ≥ 1 .
3. ∑∞ t=j α j t = 1 + 1 H for every j ≥ 1.
4. ∑t j=1 αjt j ≥ 1 2t for every t ≥ 1.
Algorithm 4 CCE-V-Learning for General-sum MGs (i-th player’s version) 1: Initialize: For any (s, a, h), set V h,i(s) ← H , V h,i(s) ← 0, Lh,i ← 0, µh(a|s) ← 1/Ai, Nh(s)← 0.
2: for episode k = 1, . . . ,K do 3: Receive s1. 4: for step h = 1, . . . ,H do 5: Take action ah ∼ µh(·|sh), observe the action ah,−i from the other players. 6: Observe reward rh,i = rh,i(sh, ah,ah,−i) and next state sh+1 from the environment. 7: Update accumulators: t := Nh(sh)← Nh(sh) + 1. 8: V h,i (sh)← (1− αt)V h,i (sh) + αt ( rh,i (sh, ah,ah,−i) + V h+1,i (sh+1) + βt
) 9: V h,i (sh)← (1− αt)V h,i (sh) + αt ( rh,i (sh, ah,ah,−i) + V h+1,i (sh+1)− βt
) 10: for all a ∈ Ai do 11: `h,i(sh, a)← 1H [H−h+1−rh,i−min{V h+1,i(sh+1), H−h}]1 {ah = a} /[µh(ah|sh)+ηt].
12: Lh,i(sh, a)← (1− αt)Lh,i(sh, a) + αtLh,i(sh, a) 13: Set µh(·|sh) ∝ exp[−(ηt/αt)Lh,i(sh, ·)].
Property 4 above does not appear in (Jin et al., 2018), for which we provide a quick proof here:
t∑ j=1 αjt j ≥ t∑ j=[t/2] αjt j ≥ 1/t t∑ j=[t/2] αjt (i) ≥ 1/(2t) t∑ j=1 αjt = 1/(2t).
Here, (i) uses αjt is increasing in j for fixed t.
We will use the following notations several times later (in this and the next section): suppose state s was visited at episodes k1, k2, . . . at the h-th step. Since the definition of kj depends on the state s and step h, we will write kj as kjh(s) when there is a possibility of confusion. We also define N s h(k) as the number of times the state s has been visited at h-th step before the start of k-th episode. We denote V
k , V k and µk for values and policies at the beginning of k-th episode; And akh is the taken
action at step h and episode k. We also use Dµh [r + PhV ](s) to denote
Eah∼µh [(r(s,ah) + Esh+1∼Ph(·|s,ah)V (sh+1)].
for all reward function r and value function V .
Towards proving Theorem 3, we begin with a simple consequence of the update rule in Algorithm 4, which will be used several times later. Lemma C.2. Let t = Nkh (s) and suppose s was previously visited at episodes k1, . . . , kt < k at the h-th step. The update rules in Algorithm 4 is equivalent to the following equations.
V k
h,i(s) = α 0 tH + t∑ j=1 αjt [ rh,i ( s, ak j h ,a kj h,−i ) + V kj h+1,i ( sk j h+1 ) + βj ] ,
V kh,i(s) = t∑ j=1 αjt [ rh,i ( s, ak j h ,a kj h,−i ) + V k j h+1,i ( sk j h+1 ) − βj ] .
We next prove the following lemma which helps to explain why our choice of the bonus term is βt. The c in βt is actually the same with the c in this lemma. Lemma C.3. Let t = Nkh (s) and suppose s was previously visited at episodes k1, . . . , kt < k at the h-th step. With probability at least 1− p2 , for any (i, s, h, t) ∈ [m]× S × [H]× [K], there exist a constant c s.t.
max µ t∑ j=1 αjtDµ×µkjh,−i ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ] ≤ c √ H3Aiι/t+ cH 2ι/t.
Proof of Lemma C.3 First, we decompose
max µ t∑ j=1 αjtDµ×µkjh,−i ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ]
into R?(i, s, h, t) + U(i, s, h, t) where
R?(i, s, h, t) := max µ t∑ j=1 αjtDµ×µkjh,−i ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjtDµkjh,i×µkjh,−i
( rh,i + Ph min{V kj h+1,i, H − h} ) (s),
and
U(i, s, h, t) := t∑ j=1 αjtDµkjh,i×µkjh,−i ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ] .
We first bound U(i, s, h, t). Define Fj as the σ-algebra generated by all the random variables up to the end of the j -th episode. Then kj are increasing stopping times w.r.t. (Fj). Define Gj as the stopped filtration Fkj . Under Gj−1, by the definition of operator D and P, we have
E [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ∣∣∣∣Gj−1]
=D µk j
h,i×µ kj h,−i
( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
So we can apply Azuma-Hoeffding inequality. Note that ∑t j=1(α j t )
2 ≤ 2H/t by Lemma C.1. Using Azuma-Hoeffding inequality, we have with probability at least 1− p4mHSK
U(i, s, h, t) = t∑ j=1 αjtDµkjh,i×µkjh,−i ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ]
≤ √√√√2H2 log(4mHSK/p) t∑ j=1 (αjt ) 2 ≤ 2 √ H3ι/t.
After taking a union bound, we have the following statement is true with probability at least 1− p/4, U(i, s, h, t) ≤ 2 √ H3ι/t for all (i, s, h, t) ∈ [m]× S × [H]× [K].
Then we bound R?(i, s, h, t). For fixed (i, s, h), if we define the loss function
`j(a) = 1
H E ai=a,a−i∼µk j h,−i [H − h+ 1− rh,i(s,a)− Ph min{V
kj h+1,i, H − h}(s)] ∈ [0, 1].
Algorithm 5 Correlated policy π̂kh for general-sum Markov games 1: for step h′ = h, . . . ,H do 2: observe sh′ , and set t← Nkh′(sh′). 3: sample l ∈ [t] with P(l = j) = αjt . 4: k ← klt(sh′). 5: jointly take action (ah′,1, ah′,2, . . . , ah′,m) ∼ ∏m i=1 µ k h′,i(·|sh′).
Then R?(i, s, h, t) = H maxµ ∑t j=1 α j t 〈 µ− µkjh,i, `j 〉 becomes the weighted regret with weight αjt . Note that the update rule for µk j
h,i(·|s) is essentially performing follow the regularized leader (FTRL) algorithm with changing step size for each state s and each step h to solve an adversarial bandit problem. Lemma 17 in Bai et al. (2020)3 bounds the weight regret with high probability. Using that lemma, we have with probability at least 1− p4mHS ,
R?(i, s, h, t) ≤ Hα t t logAi ηt + 3HAi 2 t∑ j=1 ηjα j t +H √√√√2ι t∑ j=1 (αjt ) 2 + H 2 max j≤t αjt ι+H max j≤t αjt ι/ηt
simultaneously for all t ∈ [K] . By Lemma C.1 and ηt = √
Hι Ait , we have with probability at least 1− p4mHS
R?(i, s, h, t) ≤ 2 √ H3Aiι/t+ 3 √ H3Aiι/t+ 2 √ H3ι/t+H2ι/t+ 2 √ H3Aiι/t
≤ 10 √ H3Aiι/t+ 10H 2ι/t for all t ∈ [K].
Again, taking a union bound in all (i, s, h) ∈ [m] × S × [H], we have with probability at least 1− p/4,
R?(i, s, h, t) ≤ 10 √ H3Aiι/t+ 10H 2ι/t for all (i, s, h, t) ∈ [m]× S × [H]× [K].
Finally, we concluded that with probability at least 1− p/2, we have U(i, s, h, t) +R?(i, s, h, t) ≤ c √ H3Aiι/t+ cH 2ι/t for all (i, s, h, t) ∈ [m]× S × [H]× [K].
for some absolute constant c.
Suppose the output certified correlated policy in Algorithm 2 is π̂. To go on with the proof, we need to capture the characteristic of the certified correlated policy π̂. Algorithm 5 constructs a series of new policies. These π̂kh is independent of the history before step h. From the construction, there’s a relationship between π̂ and π̂kh: when players jointly play policy π̂, they first sample k from Uniform([K]), then they use policy π̂k1 according to the same sampled k together. As a result, we have the following relationship:
V π̂1,i(s1) = 1
K K∑ k=1 V π̂k1 1,i (s1) (5)
Lemma C.4. We have
V k h,i(s) ≥ V †,π̂kh,−i h,i (s), V k h,i(s) ≤ V π̂kh h,i (s)
for all (i, s, h, k) ∈ [m]× S × [H]× [K] with probability at least 1− p.

heading: Proof of Lemma C.4
text: 3A very similar result is Lemma G.4 in our paper. But we need Lemma 17 in Bai et al. (2020) to get the optimal H dependency.
We proof this lemma by backward induction. The claim is true for h = H + 1. Suppose the claim is true for h + 1. We begin with V †,π̂kh,−i h,i (s), by the definition of certified policy, letting t = N k h (s), because π̂kh which can be decomposed as a series of π̂ kj h+1, we have for any policy µi,
V µi,π̂
k h,−i
h,i (s) = t∑ j=1 αjtDµh,i×µkjh,−i [rh,i + PhV µi,π̂ kj h+1,−i h+1,i ](s).
By taking supermum, we have
V †,π̂kh,−i h,i (s) ≤ sup
µi t∑ j=1 αjtDµi×µkjh,−i [rh,i + PhV †,π̂k j h+1,−i h+1,i ](s).
If the inequality in Lemma C.3 is true, then we use the induction hypothesis and the inequality in Lemma C.3 to obtain
V †,π̂kh,−i h,i (s) ≤ sup
µi t∑ j=1 αjtDµi×µkjh,−i [rh,i + Ph min{V kj h+1,i, H − h}](s)
≤ t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ] + c √ H3Aiι/t+ cH 2ι/t
(i) ≤ t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h}+ βj ]
≤ t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + V kj h+1,i ( sk j h+1 ) + β̄j ] = V k
h,i(s). Here, (i) uses our choice of βj = c √ H3Aiι j + 2c H2ι j and 1√ t ≤ ∑t j=1 αjt√ j , 1t ≤ ∑t j=1 2αjt j .
Meanwhile, for V kh,i(s), by the definition of certified policy and induction hypothesis,
V π̂kh h,i (s) = t∑ j=1 αjtDµkjh [rh,i + PhV π̂k j h+1,i](s)
≥ t∑
j=1
αjtDµkjh [rh,i + Ph max { V k j h+1,i, 0 } ](s).
Then we note that { D µk j h [rh,i + Ph max { V k j h+1,i, 0 } ](s)− [ rh,i ( s, a kjh h ,a kjh h,−i ) + max{V k j h h+1,i(s kjh h+1), 0} ]} j≥1 is a martingale difference w.r.t. the filtration Gj , which is defined in the proof of Lemma C.3. So by Azuma-Hoeffding inequality, with probability at least 1− p2mSKH
t∑ j=1 αjtDµkjh [rh,i + Ph max{V kj h+1,i, 0}](s)
≥ t∑
j=1
αjt [ rh,i ( s, a kjh h ,a kjh h,−i ) + max{V k j h h+1,i(s kjh h+1), 0} ] − 2 √ H3ι
t .
(6)
On this event, we have
t∑ j=1 αjtDµkjh [rh,i + Ph max { V k j h+1,i, 0 } ](s)
(i) ≥ t∑
j=1
αjt [ rh,i ( s, a kjh h ,a kjh h,−i ) + max { V kjh h+1,i(s kjh h+1), 0 } − βj ] = V kh,i(s).
Here, (i) uses ∑t j=1 α j tβj ≥ 2 ∑t j=1 α j t √ H3ι/j ≥ 2 √ H3ι/t.
As a result, the backward induction would work well for all h as long as the inequalities in Lemma C.3 and (6) hold for all (i, s, h, k) ∈ [m] × S × [H] × [K]. Taking a union bound in all (i, s, h, k) ∈ [m]× S × [H]× [K], we have with probability at least 1− p/2, the inequality in (6) is true simultaneously for all (i, s, h, k) ∈ [m]× S × [H]× [K]. Therefore the inequalities in Lemma C.3 and (6) hold simultaneously for all (i, s, h, k) ∈ [m]× S × [H]× [K] with probability at least 1− p. This finishes the proof of this lemma.
Equipped with these lemmas, we are ready to prove Theorem 3.
Proof of Theorem 3 Suppose the inequalities in Lemma C.4 hold (this happens with probability at least 1− p):
V k h,i(s) ≥ V †,π̂kh,−i h,i (s), V k h,i(s) ≤ V π̂kh h,i (s)
for all (i, s, h, k) ∈ [m]× S × [H]× [K]. Then, choosing h = 1 and s = s1, we have
V †,π̂k1,−i 1,i (s1)− V π̂k1 1,i (s1) ≤ V k 1,i(s1)− V k 1,i(s1).
Moreover, by (5), value function of certified policy can be decomposed as
V π̂1,i(s) = 1
K K∑ k=1 V π̂k1 1,i (s), V µ1,π̂−i 1,i (s1) = 1 K K∑ k=1 V µ1,π̂ k 1,−i 1,i (s1)
where the decomposition is due to the first line in the Algorithm 2: sample k ←Uniform([K]). So we have
V †,π̂−i 1,i (s1)− V π̂ 1,i(s1) ≤
1
K K∑ k=1 ( V †,π̂k1,−i 1,i (s1)− V π̂k1 1,i (s1) )
≤ 1 K K∑ k=1 ( V k 1,i(s1)− V k 1,i(s1) ) .
To prove π̂ is an approximate CCE, we only need to bound ∑K k=1 ( V k 1,i(s1)− V k 1,i(s1) ) . Letting
δkh,i := V k h,i(s k h)−V k h,i(s k h) and t = N k h (s). Suppose s was previously visited at episodes k 1, . . . , kt at the h-th step. By the update rule,
δkh,i = V k h,i(s k h)− V k h,i(s k h)
= α0tH + t∑ j=1 αjt [V k h+1,i(s kj h+1)− V k h+1,i(s kj h+1) + 2βj ]
= α0tH + t∑ j=1 αjtδ kj h+1,i + t∑ j=1 2αjtβj
= α0tH + t∑ j=1 αjtδ kj h+1,i + 2c t∑ j=1 αjt
√ AiH3ι
j + 4c t∑ j=1 αjt H2ι j .
We can use Lemma C.1 which gives ∑t j=1 α j t/ √ j ≤ 2/t and maxj≤t αjt ≤ 2H/t to get
δkh,i ≤ α0tH + t∑
j=1
αjtδ kj h+1,i + 4c √ H3Aiι/t+ 8cH 3ι(1 + log t)/t,
where we also uses ∑t j=1 1/j ≤ 1 + log t.
Taking the summation w.r.t. k, we begin by the first two terms;
K∑ k=1 α0tH = K∑ k=1 H1 {t = 0} = K∑ k=1 H1 { Nkh (s k h) = 0 } ≤ SH.
K∑ k=1 Nkh (s k h)∑ j=1 αj Nkh (s k h) δ kjh(s k h) h+1,i (i) ≤ K∑ k′=1 δk ′ h+1,i ∞∑ j=Nk
′ h (s k′ h )+1
α Nk ′ h (s k′ h )
j
(ii)
≤ (1 + 1 H ) K∑ k′=1 δk ′ h+1,i,
where (i) is by changing the order of summation and (ii) is by Lemma C.1.
So K∑ k=1 δkh,i ≤ SH + ( 1 + 1 H ) K∑ k=1 δkh+1,i + 4c √ H3Aiι K∑ k=1 1√ Nkh (s) + 8cH3ι K∑ k=1 1 + logNkh (s) Nkh (s) .
By pigeonhole argument,
K∑ k=1 1√ Nkh (s) = ∑ s∈S NKh (s)∑ n=1 1√ n ≤ O(1) √ SK.
Similarly,
K∑ k=1 1 + logNkh (s) Nkh (s) ≤ O(1)(1 + log(K)S(1 + log(K/S))) ≤ O(1)S(ι+ ι2) ≤ O(1)Sι2,
where we assume ι ≥ 1. So we have K∑ k=1 δkh,i ≤ SH + ( 1 + 1 H ) K∑ k=1 δkh+1,i +O(1) √ H3AiSKι+O(1)SH3ι3.
Recursing this argument for h ∈ [H] gives K∑ k=1 δk1,i ≤ eH2S +O(1) √ H5AiSKι+O(1)SH4ι3.
To conclude,
V †,π̂−i 1,i (s1)− V π̂ 1,i(s1) ≤
1
K K∑ k=1 ( V k 1,i(s1)− V k 1,i(s1) ) = 1 K K∑ k=1 δk1,i
≤O(1)SH4ι3/K +O (√ H5S max
i∈[m] Aiι/K
) .
Therefore, K ≥ O(H 5Smaxi∈[m] Aiι ε2 + SH4ι3 ε ) guarantees that we have V †,π̂−i 1,i (s1)− V π̂1,i(s1) ≤ ε for all i ∈ [m]. This complete the proof of Theorem 3.

heading: D PROOFS FOR SECTION 4
text: Before proving Theorem 6, we note that through the execution of Algorithm 1, we can record V kh,i(s) similar to Algorithm 4 which has update rule:
V h,i (sh)← (1− αt)V h,i (sh) + αt ( rh,i (sh, ah,ah,−i) + V h+1,i (sh+1)− βt ) . (7)
Auxiliary information V h,i (sh) is necessary for our proof.
We restate and use several notations we introduced in the last section: suppose state s was visited at episodes k1, k2, . . . at the h-th step. Since the definition of kj depends on the state s and step h, we will write kj as kjh(s) when there is a possibility of confusion. We also define N s h(k) as the number of times the state s has been visited at h-th step before the start of k-th episode. We denote V k , V k and µk for values and policies at the beginning of k-th episode; And akh is the taken action at step h and episode k. We also use Dµh [r + PhV ](s) to denote
Eah∼µh [(r(s,ah) + Esh+1∼Ph(·|s,ah)V (sh+1)].
The following lemma is the same as Lemma C.2 in the CCE case. Lemma D.1. Let t = Nkh (s) and suppose s was previously visited at episodes k1, . . . , kt < k at the h-th step. The update rule for V h,i(sh) and V h,i(sh) in Algorithm 1 and (7)is equivalent to the following equations.
V k
h,i(s) = α 0 tH + t∑ j=1 αjt [ rh,i ( s, ak j h ,a kj h,−i ) + V kj h+1,i + βj ] ,
V kh,i(s) = t∑ j=1 αjt [ rh,i ( s, ak j h ,a kj h,−i ) + V k j h+1,i ( sk j h+1 ) − βj ] .
We next prove the following lemma which helps explain our choice of the bonus term βt. The c in βt is the same with the c in this lemma. Lemma D.2. Let t = Nkh (s) and suppose s was previously visited at episodes k1, . . . , kt < k at the h-th step. With probability 1− p2 , for any (i, s, h, t) ∈ [m]× S × [H]× [K], there exist a constant c s.t.
sup φ∈Φi t∑ j=1 αjtDφh,s µkjh ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ] ≤ cH2Ai √ 2ι/t+ cH2Aiι/t.
Proof of Lemma D.2 First, like the prove in Lemma C.3, we decompose
sup φ∈Φi t∑ j=1 αjtDφh,s µkjh ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ]
into R?(i, s, h, t) + U(i, s, h, t) where
R?(i, s, h, t) := sup φ∈Φi t∑ j=1 αjtDφh,s µkjh ( rh,i + Ph min{V kj h+1,i, H − h} ) (s)
− t∑
j=1
αjtEa−i∼µkjh,−i
[ rh,i ( s, ak j h ,a−i ) + E
sh+1∼Ph(·|s,ak j h ,a−i) min{V k
j h+1,i(sh+1), H − h} ] ,
and
U(i, s, h, t) := t∑ j=1 αjtEa−i∼µkjh,−i [ rh,i ( s, ak j h ,a−i ) + E sh+1∼Ph(·|s,ak j h ,a−i) min{V k j h+1,i(sh+1), H − h} ]
− t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ] .
We first bound U(i, s, h, t). By the same reason in proof of Lemma C.3, we can apply AzumaHoeffding inequality. Note that ∑t j=1(α j t )
2 ≤ 2H/t by Lemma C.1. Using Azuma-Hoeffding inequality, we have with probability at least 1− p4mHSK ,
U(i, s, h, t) ≤ √√√√2H2 log(4mHSK/p) t∑ j=1 (αjt ) 2 ≤ 2 √ H3ι/t.
After taking a union bound, the following statement is true with probability at least 1− p/4, U(i, s, h, t) ≤ 2 √ H3ι/t for all (i, s, h, t) ∈ [m]× S × [H]× [K].
Then we bound R?(i, s, h, t). For fixed (i, s, h), we define loss function
`j(a) = 1
H E ai=a,a−i∼µk j h,−i [H − h+ 1− rh,i(s,a)− Esh+1∼Ph(·|s,a,a−i) min{V
kj h+1,i(sh+1), H − h}].
Then we have `j(a) ∈ [0, 1] for all a and the realized loss function:
˜̀ j(a
kj h ) = 1
H [H − h+ 1− rh,i(s, ak
j h ,a kj −i)−min{V kj h+1,i(s kj h+1), H − h}] ∈ [0, 1].
is an unbiased estimator of `j(ak j h ). Then R ?(i, s, h, t) can be written as
R?(i, s, h, t) = H sup φ∈Φi t∑ j=1 αjt [`j(a kj h,i)− 〈φ µk j h,i, `j〉].
For fixed step h, state s, suppose s is visited at episode k1h(s), . . . , k t h(s). So q b h(a|s) and N bh(s) is only updated at episode k1h(s), . . . , k t h(s). Focusing on how q b h(a|s) and N bh(s) are updated when s is visited for the j-th time at step h, we can formulate the update algorithm as Algorithm 8. So we can bound R?(i, s, h, t) using Lemma G.2.
Then by Lemma G.2, if we choose the log term as ι = 4 log 10mSAHKp , we have
H sup φ∈Φi t∑ j=1 αjt [`j(a kj h,i)− 〈φh,s µk j h,i, `j〉] ≤ 40H2Ai √ ι/t+ 40H2Aiι/t for all t ∈ [K]
with probability at least 1− p/(4mSH). Taking a union bound over all (i, s, h) ∈ [m]× S × [H], we have with probability at least 1− p/4,
R?(i, s, h, t) ≤ 40H2Ai √ ι/t+ 40H2Aiι/t for all (i, s, h, t) ∈ [m]× S × [H]× [K].
Finally, we concluded that with probability at least 1− p/2, we have U(i, s, h, t) +R?(i, s, h, t) ≤ cH2Ai √ ι/t+ cH2Aiι/t for all (i, s, h, t) ∈ [m]×S × [H]× [K].
for some absolute constant c.
Suppose the output certified correlated policy in Algorithm 2 is π̂. To go on with the proof, we need to capture the characteristic of the certified correlated policy π̂. Algorithm 6 constructs a series of new policies (same as Algorithm 5). These π̂kh is independent of the history before step h. From the construction, there’s a relationship between π̂ and π̂kh: when players jointly play policy π̂, they first sample k from Uniform([K]), then they use policy π̂k1 according to the same sampled k together. As a result, we have the following relationship:
V π̂1,i(s) = 1
K K∑ k=1 V π̂k1 1,i (s) (8)
Algorithm 6 Correlated policy π̂kh for general-sum Markov games 1: for step h′ = h, . . . ,H do 2: observe sh′ , and set t← Nkh′(sh). 3: sample l ∈ [t] with P(l = j) = αjt . 4: k ← klt(sh′). 5: jointly take action (ah′,1, ah′,2, . . . , ah′,m) ∼ ∏m i=1 µ k h′,i(·|sh′).
Lemma D.3. We have
V k
h,i(s) ≥ sup φ∈Φi
V φ π̂kh h,i (s), V k h,i(s) ≤ V π̂kh h,i (s)
for all (i, k, h, s) ∈ m× [K]× [H]× S with probability at least 1− p/2.
Proof of Lemma D.3 We proof this lemma by backward induction. The claim is true for h = H+1. Suppose the claim is true for h+ 1. We begin with supφ∈Φi V φ π̂kh h,i (s), by the definition of certified policy. Letting t = Nkh (s), because π̂ k h which can be decomposed as a series of policies, π̂ kj
h+1, for any φ ∈ Φi, we have
V φ π̂kh h,i (s) = t∑ j=1 αjtDφ µkjh [rh,i + PhV φ π̂k j h+1 h+1,i ](s).
Taking supermum, we have
sup φ∈Φi
V φ π̂kh h,i (s) ≤ sup
φ∈Φi t∑ j=1 αjtDφ µkjh [rh,i + Ph supφ∈Φi V φ π̂k j h+1 h+1,i ](s)
If the inequality in Lemma D.2 is true, then we can use the induction hypothesis and the inequality in Lemma D.2 to obtain
sup φ∈Φi t∑ j=1 αjtDφ µkjh [rh,i + Ph supφ∈Φi V φ π̂k j h+1 h+1,i ](s)
≤ sup φ∈Φi t∑ j=1 αjtDφ µkjh [rh,i + Ph min{V kj h+1,i, H − h}](s) ≤ t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h} ] + cH2Ai √ ι/t+ cH2Aiι/t
(i) ≤ t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + min{V k j h+1,i(s kj h+1), H − h}+ βj ]
≤ t∑
j=1
αjt [ rh,i ( s, ak j h ,a kj h,−i ) + V kj h+1,i + β̄j ] =V k
h,i(s). Here, (i) uses our choice of βj = cH 2Ai √ ι j + 2c H2Aiι j and 1√ j ≤ ∑t j=1 αjt√ j , 1t ≤ ∑t j=1 2αjt j .
Meanwhile, for V kh,i(s), by the definition of certified policy and induction hypothesis,
V π̂kh h,i (s) = t∑ j=1 αjtDµkjh [rh,i + PhV π̂k j h+1 h+1,i](s)
≥ t∑
j=1
αjtDµkjh [rh,i + Ph max{V kj h+1,i, 0}](s).
Note that { D µk j h [rh,i + Ph max { V k j h+1,i, 0 } ](s)− [ rh,i ( s, a kjh h ,a kjh h,−i ) + max{V k j h h+1,i(s kjh h+1), 0} ]} j≥1 is a martingale difference sequence w.r.t. the filtration Gj , which is defined in the proof of Lemma C.3. So by Azuma-Hoeffding inequality, with probability at least 1− p2mSKH ,
t∑ j=1 αjtDµkjh [rh,i + Ph max{V kj h+1,i, 0}](s)
≥ t∑
j=1
αjt [ rh,i ( s, a kjh h ,a kjh h,−i ) + max{V k j h h+1,i(s kjh h+1), 0} ] − 2 √ H3ι
t .
(9)
On this event, we have t∑
j=1
αjtDµkjh [rh,i + Ph max { V k j h+1,i, 0 } ](s)
(i) ≥ t∑
j=1
αjt [ rh,i ( s, a kjh h ,a kjh h,−i ) + max { V kjh h+1,i(s kjh h+1), 0 } − βj ]
≥ t∑
j=1
αjt [ rh,i ( s, a kjh h ,a kjh h,−i ) + V kjh h+1,i(s kjh h+1)− βj ] = V kh,i(s).
Here, (i) uses ∑t j=1 α j tβj ≥ 2 ∑t j=1 α j t √ H3ι/j ≥ 2 √ H3ι/t.
As a result, the backward induction would work well for all h as long as the inequalities in Lemma D.2 and (9) hold for all (i, s, h, k) ∈ [m]×S × [H]× [K]. Taking a union bound in all (i, s, h, k) ∈ [m] × S × [H] × [K], we have with probability at least 1 − p/2, the inequality in (9) is true simultaneously for all (i, s, h, k) ∈ [m]× S × [H]× [K]. Therefore the inequalities in Lemma C.3 and (9) hold simultaneously for all (i, s, h, k) ∈ [m]×S × [H]× [K] with probability at least 1− p. This finishes the proof of this lemma.
Equipped with these lemmas, we are ready to prove Theorem 6.
Proof of Theorem 6 Suppose the inequalities in Lemma D.3 hold (this happens with probability at least 1− p):
V k
h,i(s) ≥ sup φ∈Φi
V φ π̂kh h,i (s), V k h,i(s) ≤ V π̂kh h,i (s)
for all (i, s, h, k) ∈ [m]× S × [H]× [K]. Then, choosing h = 1 and s = s1, we have
max φ∈Φi
V φ π̂k1 1,i (s1)− V π̂k1 1,i (s1) ≤ V k 1,i(s1)− V k 1,i(s1).
Moreover, by (8), value function of certified policy can be decomposed as
V π̂1,i(s1) = 1
K K∑ k=1 V π̂k1 1,i (s1), V φ π̂ 1,i (s1) = 1 K K∑ k=1 V φ π̂k1 1,i (s1),
where the decomposition is due to the first line in the Algorithm 2: sample k ←Uniform([K]). So we have
max φ∈Φi V φ π̂1,i (s1) = sup φ∈Φi
1
K K∑ k=1 V φ π̂k1 1,i (s1)
≤ 1 K K∑ k=1 sup φ∈Φi V φ π̂k1 1,i (s1).
The we bound maxφ∈Φi V φ π̂ 1,i (s1)− V π̂1,i(s1),
max φ∈Φi
V φ π̂1,i (s1)− V π̂ 1,i(s1) ≤
1
K K∑ k=1 ( sup φ∈Φi V φ π̂k1 1,i (s1)− V π̂k1 1,i (s1) )
≤ 1 K K∑ k=1 ( V k 1,i(s1)− V k 1,i(s1) ) .
By Lemma D.3 Letting δkh,i := V k h,i(s k h)− V k h,i(s k h) and t = N k h (s). By the update rule, we have
δkh,i = V k h,i(s k h)− V k h,i(s k h)
= α0tH + t∑ j=1 αjt [V k h+1,i(s kj h+1)− V k h+1,i(s kj h+1) + 2βj ]
= α0tH + t∑ j=1 αjtδ kj h+1,i + t∑ j=1 2αjtβj
= α0tH + t∑ j=1 αjtδ kj h+1,i + 2cAiH 2 t∑ j=1 αjt √ ι j + 4c t∑ j=1 αjt H2Aiι j .
Taking the summation w.r.t. k, by the same argument in the proof of Theorem 3, we can get
max φ∈Φ
V φ π̂1,i (s1)− V π̂ 1,i(s1) =
1
K K∑ k=1 ( V k 1,i(s1)− V k 1,i(s1) ) = 1 K K∑ k=1 δk1,i
≤O(1)SH4 max i∈[m] Aiι 3/K +O
(√ H6S max
i∈[m] A2i ι/K
) .
If K ≥ O(H 6Smaxi∈[m] A 2 i ι ε2 + H4Smaxi∈[m] Aiι 3 ε ), we have maxφ∈Φ V φ π̂ 1,i (s1)− V π̂1,i(s1) ≤ ε holds for all i ∈ [m], which means π̂ is an ε-approximate CE. This completes the proof of Theorem 3.

heading: E PROOFS FOR SECTION 5
text: Here, we first define pure-strategy Nash equilibrium. We say policy π is a pure strategy (deterministic policy) if and only if for any (h, i, s) ∈ [H]× [m]×S , πh,i(ai|s) = Iai=a′h,i(s) for some a ′ h,i(s). We say π a pure-strategy Nash equilibrium if π is a pure-strategy and is a Nash equilibrium. Similarly, we say π is a pure strategy ε-approximate Nash equilibrium if π is a pure strategy and NE-gap(π) ≤ ε. Pure-strategy Nash equilibrium does not always exist in general-sum MGs, but is guaranteed to exist (as we will see) in Markov Potential Games.

heading: E.1 EXISTENCE OF PURE-STRATEGY NASH EQUILIBRIA IN MARKOV POTENTIAL GAMES
text: A particular property of MPGs is that, there always exists a pure-strategy Nash equilibrium. Such a property does not hold for every general-sum MG. Pure-strategy Nash equilibria are preferred in many scenarios since each player can take deterministic actions. In this section, we will focus on learning a pure-strategy Nash equilibrium of MPGs. Proposition E.1. For any Markov potential games, there exists a pure-strategy Nash equilibrium.
See Theorem 3.1 in Leonardos et al. (2021) or Proposition 1 in Zhang et al. (2021) for a proof of Proposition E.1.
Algorithm 7 UCB-VI with Upper and Lower Confidence Bounds (UCBVI-UPLOW) 1: Initialize: For any (s, a, h, s′): Qh(s, a) ← H , Qh(s, a) ← 0, Nh(s) = Nh(s, a) = Nh(s, a, s
′)← 0. 2: for episode k = 1, . . . ,K do 3: for step h = H, . . . , 1 do 4: for (s, a) ∈ S ×A do 5: Set t← Nh(s, a). 6: if t > 0 then 7: β ← BONUS(t, V̂h[(V h+1 + V h+1)/2](s, a)) (c.f. Eq. (10)) 8: γ ← (c/H) · P̂h(V h+1 − V h+1)(s, a). 9: Qh(s, a)← min { (rh + P̂hV h+1)(s, a) + γ + β,H } .
10: Q h (s, a)← max { (rh + P̂hV h+1)(s, a)− γ − β, 0 } 11: for s ∈ S do 12: πh(s)← arg maxa∈AQh(s, a). 13: V h(s)← Qh(s, πh(s)); V h(s)← Qh(s, πh(s)). 14: Receive the initial state s1 from the MDP. 15: for step h = 1, . . . ,H do 16: Take action ah = πh(sh), observe reward rh and next state sh+1. 17: Increment Nh(sh), Nh(sh, ah), and Nh(sh, ah, sh+1) by 1. 18: P̂h(·|sh, ah)← Nh(sh, ah, ·)/Nh(sh, ah). 19: Let (V k
h, V k h, π k) denote the value estimates and policy at the beginning of episode k. 20: return Policy πk? where k? = arg mink∈[K](V k 1(s1)− V k 1(s1)).

heading: E.2 SINGLE AGENT REINFORCEMENT LEARNING AND THE UCBVI-UPLOWSUB-ROUTINE
text: We first remark that although in Algorithm 3 we propose to use the UCBVI-UPLOW algorithm 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 UCBVIUPLOW algorithm because 1) it has a tight sample complexity bound; 2) it outputs a deterministic policy which can be used to find a pure-strategy approximate Nash equilibrium.
In this subsection we consider the problem of learning a near optimal policy in the fixed horizon stochastic reward RL problem MDP(H,S,A,P, r). 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 use the same notations including policies and value functions as that of the Markov games as 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-UPLOW algorithm (Algorithm 7), which is adapted from (Xie et al., 2021; Liu et al., 2021), for learning approximate optimal policy in reinforcement learning problems. Such an algorithm is used as a sub-routine in Algorithm 3 to learn approximate pure-strategy Nash equilibria in MPGs.
In the description of Algorithm 7, the P̂h quantity appeared in lines 8,9,10, and 18 can be viewed either as a set of empirical probability distributions or as an operator: for any fixed (sh, ah), we can view P̂h(·|sh, ah) as a probability distribution over S; for any given function V : S → R, we can view P̂h as an operator by defining (P̂hV )(s, a) := Es′∼P̂h(·|s,a)[V (s
′)]. The V̂h operator in line 7 is the empirical variance operator defined as V̂hV = P̂hV 2 − (P̂hV )2. The BONUS function in the algorithm is chosen to be the Bernstein type bonus function
BONUS(t, σ̂2) = c( √ σ̂2ι/t+H2Sι/t). (10)
We have the following sample complexity guarantee for the UCBVI-UPLOW algorithm returning an ε-approximate optimal policy.
Lemma E.2. The UCBVI-UPLOW algorithm always returns a deterministic policy πk? . Moreover, for any p ∈ (0, 1], letting ι = log(SAHK/p) and taking the number of episodes
K ≥ O(H3SAι/ε2 +H3S2Aι2/ε),
then with probability at least 1 − p, the returned policy πk? is ε-approximate optimal, i.e., supµ V µ 1 (s1)− V π k? 1 (s1) ≤ ε.
Proof of Lemma E.2 First, πk? is obviously deterministic from line 12 of Algorithm 7.
The sample complexity guarantee of the UCBVI-UPLOW algorithm is a consequence of the sample complexity guarantee of the Nash-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 {rh(s, a)}h∈[H] and P = {Ph(sh+1|sh, ah)}h∈[H] for the MDP(H,S,A,P, r). Such a MDP can be viewed as a zero-sum Markov game MG(H,S,A,B,P, r̄), in which (H,S,A) are the same as that of the MDP, the action space for the min-player is a singleton B = 1 so that the rewards r̄h(s, a, b) ≡ rh(s, a) do not depend on the action of the min-player and the transition matrices Ph(·|s, a, b) = Ph(·|s, a1) do not depend on the action of the min-player either. Then, for any ε-approximate Nash equilibrium (µ, ν) of the associated zero-sum Markov game, the max-player’s policy µ must be ε-approximate optimal for the original MDP.
By this correspondence, the UCBVI-UPLOW algorithm is actually a specific version of the Nash-VI algorithm in Liu et al. (2021), and Line 12 in UCBVI-UPLOW is actually a specific version of line 12 in Nash-VI in Liu et al. (2021): this is because in this specific Markov game, Q(s, a, b) and Q(s, a, b) only depend on s and a, so that πh(s) = arg maxa∈AQh(s, a) is actually in the CCE set CCE(Qh(s, a, b), Qh(s, a, b)).
By this reduction and by Theorem 4 in Liu et al. (2021), this lemma is proved.

heading: E.3 PROOF OF THEOREM 8
text: In this subsection, we give a formal proof of Theorem 8.
Proof of Theorem 8 We use superscript t to represent variables at the t-th step (before π is updated) of the while loop.
Because we choose the log factor as ι = log(mHSKmaxi∈[m] Aiεp ), for each execution of UCBVIUPLOW, by Lemma E.2, it return a ε/4-optimal deterministic policy with probability at least 1− pε8m2H . Taking a union bound, we have
max µi
V1,i(µi, π t −i)− V1,i(π̂ti , πti) ≤ ε/4 (11)
simultaneously for all i ∈ [m] and t ≤ 4mH/ε with probability at least 1− p/2. For the empirical estimator V̂ t1,i, it’s bounded in [0, H]. Thus by Hoeffding’s inequality, for fixed i ∈ [m] and t
P(|V̂ t1,i − V t1,i| ≥ ε/8) ≤ 2 exp ( − Nε 2
32H2 ) Choosing N = CH2ι/ε2 for some large constant C, we have
P(|V̂ t1,i − V t1,i| ≥ ε/8) ≤ εp
16m2H .
Apply this inequality to V̂ t1,i(π̂ t i , π t −i) and V̂1,i(π t) and taking a union bound, we have
|V̂ t1,i(π̂ti , πt−i)− V1,i(π̂ti , πt−i)| ≤ ε/8 |V̂ t1,i(πt)− V1,i(πt)| ≤ ε/8 (12)
simultaneously for all i ∈ [m] and t ≤ 4mHε with probability at least 1− p/2. As a result, by (11) and (12), we have
max µi
V1,i(µi, π t −i)− V1,i(π̂ti , πti) ≤ ε/4
|V̂ t1,i(π̂ti , πt−i)− V1,i(π̂ti , πt−i)| ≤ ε/8
|V̂ t1,i(πt)− V1,i(πt)| ≤ ε/8
(13)
simultaneously for all i ∈ [m] and t ≤ 4mH/ε with probability at least 1− p. On this event, ∆ti = V̂ t 1,i(π̂ t i , π t −i)− V̂ t1,i(πt)
≤ V1,i(π̂ti , πt−i)− V1,i(πt) + ε/4. If the while loop doesn’t end after the t-th iteration and t ≤ 4mH/ε, there exists jt s.t. ∆tjt ≥ ε/2, so we have
Φ(πt+1)− Φ(πt) = Φ(π̂tjt , πt−jt)− Φ(πt) (i) = V1,jt(π̂ t jt , π t −jt)− V1,jt(πt)
≥ ∆tjt − ε/4 = ε/4. Here, (i) follows the definition of potential function. Because Φ is bounded, the while loop ends within 4Φmax/ε ≤ 4mH/ε steps. Therefore, (13) holds simultaneously for all i ∈ [m] and t before the end of while loop with probability at least 1− p. Again, on this event, if the while loop stops at the end of t-th step, we have maxi∈[m] ∆ti ≤ ε/2, then
max µi
V1,i(µi, π t −i)− V1,i(πt) = max
µi V1,i(µi, π
t −i)− V1,i(π̂ti , πt−i) + V1,i(π̂ti , πt−i)− V1,i(πt)
≤ ε/4 + V̂ t1,i(π̂ti , πt−i)− V̂ t1,i(πt) + 2ε/8 = ε/2 + ∆ti ≤ ε.
So the returned policy πt is a ε-approximate Nash equilibrium. Moreover, since UCBVIUPLOWoutputs a pure-strategy policy and our initial policy is also a 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 ε-approximate (pure-strategy) Nash equilibrium.
Finally, the number of episodes within each step of the while loop is
N + m∑ i=1 (Ki +N) = O ( H3S ∑m i=1Aiι ε2 + H3S2 ∑m i=1Aiι 2 ε + H2mι ε2 ) = O ( H3S ∑m i=1Aiι
ε2 + H3S2
∑m i=1Aiι 2
ε
) .
So the total sample complexity (episodes) is at most K = O ( ΦmaxH 3S ∑m i=1Aiι
ε3 +
ΦmaxH 3S2 ∑m i=1Aiι 2
ε2
) .

heading: F SAMPLE COMPLEXITY LOWER BOUND OF FINDING APPROXIMATE PURE-STRATEGY NASH EQUILIBRIUM
text: In this section, we present an result on the sample complexity’s lower bound for learning a purestrategy Nash equilibrium in MPGs. We concentrate on Markov cooperative games (MCGs), which are also MPGs. Note that for MCGs, the potential function Φ is bounded in [0, H], so by Theorem 8, the sample complexity of Nash-CA (Algorithm 3) is Õ( ∑m i=1Ai/ε
3) highlighting the dependency on ε, m and Ai, i = 1, . . . ,m. We would show this ∑m i=1Ai dependency is inevitable for learning
ε-approximate pure-strategy Nash equilibrium in MCGs by proving an Ω( ∑m i=1Ai/ε 2) lower bound.

heading: F.1 LOWER BOUND FOR FINDING APPROXIMATE PURE-STRATEGY NASH EQUILIBRIUM IN
text: MCGS
We first present our main theorem: Theorem F.1. Suppose Ai = 2k, i = 1, . . . ,m , H ≥ 2, S ≥ 3 and m ≥ 4. Then, there exists an absolute constant c0 such that for any ε ≤ 0.4 and any online finetuning algorithmM that outputs a pure-strategy policy π̂ = (π̂1, . . . , π̂m), if the number of episodes
K ≤ c0 H2 ∑m i=1Ai ε2 = c0 2kmH2 ε2 ,
then there exists general-sum Markov cooperative game MG on which the algorithmM suffers from ε/4-suboptimality,i.e. EMNE-gap(π̂) ≥ ε/4, where the expectation EM is w.r.t. the randomness during the algorithm’s execution within Markov game MG.
This theorem can be viewed as a corollary of the following lemma by a simple reduction. We would prove this theorem in the next subsection. One-step (general-sum) game is a game with only one state and one step. In a one-step game, all players choose an action simultaneously and then receive it’s own reward. The Nash equilibrium and NE-gap can be defined similarly in one-step games. Lemma F.2. Suppose Ai = 2k, i = 1, . . . ,m and m ≥ 4. Then, there exists an absolute constant c0 such that for any ε ≤ 0.4 and any online finetuning algorithm that outputs a pure strategy π̂ = (π̂1, . . . , π̂m), if the number of samples
n ≤ c0 ∑m i=1Ai ε2 = c0 2km ε2 ,
then there exists a one-step game M with stochastic reward, on which the algorithm suffers from ε/4-suboptimality,i.e.
EMNE-Gap(π̂) = EM max i [ max πi ui(πi, π̂−i)− ui(π̂) ] ≥ ε/4,
where the expectation EM is w.r.t. the randomness during the algorithm’s execution within game M. ui(π) is the expected reward of the ith 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 a class of one-step games which reward is Bernoulli( 12 ) or Bernoulli( 1 2 +ε) depending on the taken joint-action. The proportion of joint-actions with reward Bernoulli( 12 + ε) is relatively small. Most importantly, every pure-strategy ε-approximate Nash equilibrium has reward Bernoulli( 12 + ε). So in order to find an ε-approximate pure-strategy Nash equilibrium, we must explore sufficient joint-actions. The number of the joint-actions with reward Bernoulli( 12 + ε) can be bounded by the covering number of [2k]m under Hamming distance. Then we use KL divergence decomposition (Lemma F.5) to argue rigorously that we need to explore how many joint-actions to get an ε-approximate pure-strategy Nash equilibrium.
There’s ∑m i=1Ai dependency
4 in the lower bound of sample complexity for finding pure-strategy ε-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-agent MDPs, so the existing lower bound’s dependency on Ai, i = 1, . . . ,m is maxi∈[m]Ai .
Here, we don’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 ε, then the player can change policy at all state to improve the expected cumulative reward to the utmost extent. In general-sum Markov games, at different state, maybe different players can change the policy for this state to improve his expected cumulative reward by ε. However, the definition NE-gap only allows one player to change the policy. This difference in nature makes S and ∑m i=1Ai incompatible in the lower bound.
4We only prove this lower bound when Ai all equal to 2k. This case is representative.
If we consider another notion of suboptimality, i.e., changing maximum to summation:
NE-gap′(π) := ∑ i∈[m] [ sup µi V µi,π−i 1,i (s1)− V π 1,i(s1) ] .
This definition of NE-gap is different from the previous definition. With NE-gap′, if each player can change his policy to improve his expected cumulative reward by ε, the NE-gap′ would be at least mε. Then we can define ε-approximate Nash equilibrium similarly as the policy pi such that NE-gap′(π) ≤ ε. We simply point out that with this new definition of NE-gap′ and ε-approximate Nash equilibrium, mimicking the proof of Theorem 2 in Dann & Brunskill (2015), we can prove the sample complexity’s lower bound for learning a pure-strategy ε-approximate Nash equilibrium in Markov (cooperative) games is Ω(H2S ∑m i=1Ai/ε 2).

heading: F.2 PROOF IN LOWER BOUND
text: In this subsection, we complete the proof of results we proposed in last subsection. For convenience, we call the joint-action (in one-step game) which is Nash equilibrium Nash strategy. We begin with a special case of Lemma F.2, i.e. the case when Ai = 2 for all i ∈ [m]. Lemma F.3. Suppose Ai = 2, i = 1, . . . ,m and m ≥ 4. Then, there exists an absolute constant c0 such that for any ε ≤ 0.4 and any algorithm that outputs a pure strategy π̂ = (π̂1, . . . , π̂m), if the number of samples
n ≤ c0 2m
ε2 ,
then there exists a one step game M with stochastic reward on which the algorithm suffers from ε/4-suboptimality,i.e.,
EMNE-Gap(π̂) = EM max i [ max πi ui(πi, π̂−i)− ui(π̂) ] ≥ ε/4,
where the expectation EM is w.r.t. the randomness during the algorithm’s execution within game M. ui(π) is the expected reward of the ith player when strategy π are taken for each player.
The proof of this lemma further rely on the following lemma. Lemma F.4. There exists a one-step game for m players where each player has two actions. The deterministic reward is 0 or 1 and the number of joint actions that have 1 is at most 2 m+1
m . Moreover, the only pure-strategy Nash equilibria are these joint actions which have reward 1.
Proof of Lemma F.4 We use r(a) to denote the reward of (joint) actions a ∈ {1, 2}m and define d(a,a′) = #{i : ai 6= a′i}. To ensure pure-strategy Nash equilibria must have reward 1. We need to ensure that for a a ∈ {1, 2}m, there exists one a′ ∈ {1, 2}m such that
r(a′) = 1, d(a,a′) ≤ 1.
In other words, the set {a : r(a) = 1} is a 1-net of {1, 2}m under the distance d(·, ·). By the definition of covering number, we only need to prove
N ({1, 2}m, d, 1) ≤ 2 m+1
m .
Define K(m, 1) = N ({1, 2}m, d, 1). By hamming code (Hamming (1950)), we know that for any integer k ≥ 1,
K(2k − 1, 1) = 22 k−k−1.
Moreover, we also have K(n, 1) ≤ 2K(n− 1, 1) by adding 0 and 1 behind the 1-net of {0, 1}n−1. Taking largest k such that 2k − 1 ≤ n and iterating this construction on the Hamming code we get K(m, 1) ≤ 2m−[log2(m+1)] ≤ 2 m+1
m . This ends the proof.
The next lemma is the KL divergence lemma (Lemma 15.1 of (Lattimore & Szepesvári, 2020)]), we restate it in one-step games.
Lemma F.5 (KL divergence decomposition in one-step games). For any one-step games with stochastic reward and any algorithm. Let X = (a1, r1,a2, r2, . . . ,an, rn), where ak is the action (adaptively) chosen by the algorithm at the kthround and rk is the reward received at the kthround after ak is taken. P 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
KL(X|P‖X|Q) = ∑ a EP[N(a)]KL(P(·|a)‖Q(·|a)).
Then we return to the proof of Lemma F.3. Suppose a game M satisfies the condition in Lemma F.4 is M , by permuting the actions of M , we get 2m games. They all satisfy the condition in Lemma F.4. Suppose the reward of the i-th game is r(i)(·) . We consider the following family of one-step games with stochastic reward: Let a = (a1, a2, . . . , am).
M(ε) = {M(i) ∈ R{1,2} m withM(i)(a) = 1 2 + r(i)(a)ε, i = 1, 2, . . . , 2m},
where in one-step game M(i), the reward is sampled from Bernoulli(M(i)(a)) if the i-th player picks ai and a = (a1, a2, . . . , am). Moreover, we defineM(0) as a game whose reward is sampled from Bernoulli( 12 ) independent of the action.
We further let ν denote the uniform distribution on {1, 2, . . . , 2m}.
Proof of Lemma F.3 Fix a one-step game M(i) ∈ M(ε), by Lemma F.4, it’s clear that purestrategy Nash equilibria form a set D(i) := a ∈ {a : r(i)(a) = 1}. We have #D(i) ≤ 2m+1/m. For any online finetuning algorithm A that outputs a pure strategy π̂. Suppose π̂ means the i-th player’s action is âi and let â = (â1, â2, · · · , âm). From the structure of the M(ε), we know
NE-Gap(π̂) = εPi(â 6∈ D(i)),
where Pi is w.r.t. the randomness of the algorithm and gameM(i). So we only need to use n, the number of samples to give a lower bound of Pi(â 6∈ D(i)).
Since X = {a1, r1, · · · ,an, rn} is a sufficient statistics for the posterior distribution D(i), so we have
Ei∼νPi(â 6∈ D(i)) ≥ inf g Ei∼νPi(g(X) 6∈ D(i))
(i) ≥ inf g Ei∼νP0(g(X) 6∈ D(i))− Ei∼νTV(X|P0 , X|Pi)
(ii)
≥ 1 2 − Ei∼νTV(X|P0 , X|Pi)
(iii)
≥ 1 2 − Ei∼ν
√ 1
2 KL(X|P0‖X|Pi)
(iv) =
1 2 − Ei∼ν
√ 1
2 ∑ a EP0 [N(a)]KL(P0(·|a)‖Pi(·|a)).
Above, (i) follows from the definition of total variation distance; (ii) uses the fact that under P0, we can’t get any information about a?, so Ei∼νP0(g(X) 6∈ D(i)) = 1− |D (1)| 2m ≥ 1 2 ; (iii) uses Pinsker’s inequality; (iv) uses KL divergence decomposition (Lemma F.5).
For a ∈ D(i), we have KL(P0(·|a)‖Pi(·|a)) =KL (( 1
2 ,
1
2
) ‖ ( 1
2 − ε, 1 2 + ε )) = 1
2 log
1
1− 4ε2 ≤4ε2
if ε ∈ (0, 0.4]. For a 6∈ D(i), KL(P0(·|a)‖Pi(·|a)) = 0. So
Ei∼νPi(â 6∈ D(i)) ≥ 1
2 − Ei∼ν
√ 2 ∑
a∈D(i) EP0 [N(a)]ε2
(i) ≥ 1 2 − √ 2Ei∼ν ∑
a∈D(i) EP0 [N(a)]ε2
(ii) =
1 2 − √ 2 n|D(i)| 2m ε2
≥ 1 2 − √ 4 n m ε2.
Above, (i) uses Jensen’s inequality, (ii) uses the fact that EP0 [N(a)] is independent of i which gives Ei∼ν ∑
a∈D(i) EP0 [N(a)] =
1
2m ∑ a EP0 [N(a)] ∑ i:a∈D(i) 1
= 1
2m n|D(1)|,
where ∑ i:a∈D(i) 1 = |D(1)| is because of the permutation. Finally, we choose c0 = 1 32 , if n ≤ 1 32 2m ε2 , then Ei∼νPi(â 6∈ D(i)) ≥ 1
4 .
So there’s a game instanceM(i) on which the algorithm suffer from ε/4 sub-optimality.
The difference between Lemma F.3 and F.2 is the size of action space. To prove the Ai = 2k case, we need to generalized F.4 to the case each player have 2k actions. Lemma F.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 is 0 or 1 and the number of joint actions that have 1 is at most 2·(2k) m
km . Moreover, the only pure-strategy Nash equilibria are these joint actions which has reward 1.
Proof of Lemma F.6 We would prove this lemma by induction. Without loss of generality, we suppose the action for each player is 1, 2, . . . , 2k. First, we define the hamming distance between two vectors. d(x,y) := #{i : x(i) 6= y(i)}. The joint action space is [2k]m = {1, 2, . . . , 2k}m. Suppose we have an 1-net of [2k]m, D, which means for every y ∈ [2k]m, we can find a x ∈ D, s.t. d(x,y) ≤ 1. If the reward of a game satisfy:
r(a) = 1 for all a ∈ D, and r(a) = 0 for all a 6∈ 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 can change to obtain higher reward. So a is not a pure-strategy Nash equilibrium.
As a result, we can construct a game based on the 1-net. The only thing left to be verified is that the number of joint actions that have reward 1 is at most 2·(2k) m
km . Note that the number of joint actions that have reward 1 is actually |D|, so we need to prove
N ([2k]m, d, 1) ≤ 2 · (2k) m
km , (14)
where N (·, d, ε) denotes the covering number. For k = 1, from the proof of Lemma F.4, (14) is true. For k > 1, we first decompose [2k]m into km smaller blocks, i.e.
Ω(l1, l2, . . . , lm) = {2l1 − 1, 2l1} × {2l2 − 1, 2l2} × · · · ,×{2lm − 1, 2lm},
where {l1, l2, . . . , lm} ∈ [k]m. Among these km blocks, we choose the blocks which satisfy k|l1 + l2 + · · ·+ lm. Apparently, there are km−1 blocks satisfying m|l1 + l2 + · · ·+ lm. Because (14) is true for k = 1, we can pick a 1-net of Ω(1, 1, . . . , 1) with at most 2·2 m
m elements. By a translation, (all elements add a constant vector), we can pick a 1-net of each block with at most 2·2 m
m elements. Totally there are at most 2·2 mkm−1
m = 2·(2k)m km elements. These elements form a set P . We would
prove P is a 1-net of [2k]m.
In fact, for any x ∈ [2k]m, suppose x is in Ω(l1, l2, . . . , lm). After translating this block to Ω(1, 1, . . . , 1), x is coincided with x0.
If x0 ∈ P , change l1 to l′1 such that k|l′1 + l2 + · · · + lm. Suppose x′ is the vector in block Ω(l′1, l2, . . . , lm) that corresponds to x0 in Ω(1, 1, . . . , 1). This gives x
′ ∈ P . Moreover, d(x,x′) ≤ 1 because the translation from Ω(l1, l2, . . . , lm) to Ω(l′1, l2, . . . , lm) only changes the first component.
If x0 6∈ P , we can find x′0 in P ∩ Ω(1, 1, . . . , 1) such that d(x0,x′0) = 1 because P |Ω(1,1,...,1) is a 1-net. Suppose x0 and x′0 differs at the j-th component. We can change lj to l ′ j s.t. k|l1 + l2 + · · ·+ lj−1 + l′j + lj+1 + · · ·+ lm. Suppose x′0 corresponds to x′ in Ω(l1, . . . , lm) and x′′ in Ω(l1, . . . , lj−1, l ′ j , lj+1, . . . , lm). By the definition of P , we know x
′′ ∈ P . Moreover, x and x′ only differ at the j-th component because of translation and the fact that x0 and x′0 only differ at the j-th component. x′ and x′′ also only differ at the j-th component because of translation. So we have x and x′′ may only differ at the j-th component, i.e. d(x,x′′) ≤ 1. Recall that x′′ ∈ P . To conclude, we can always find another vector y ∈ P such that d(x,y) ≤ 1, this means P is a 1-net of [2k]m. So (14) is proved.
Using this fundamental lemma, by the argument in proof of Lemma F.3, we can easily prove Lemma F.2. So here we omit the proof.
Finally, we give a proof of Theorem F.1 based on Lemma F.2.
Proof of Theorem F.1 Because S ≥ 3, we construct a class of general-sum Markov games as follows (see figure 1): the set of all joint-actions A can be divided into two sets A+ an A−.
Transition Starting from s1, for a ∈ A+, P1(s+|s1,a) = 12 + ε 2(H−1) and P1(s−|s1,a) = 1 2 − ε 2(H−1) . For a ∈ A
−, P1(s+|s1,a) = P1(s−|s1,a) = 12 . For all h ≥ 1 and a ∈ A, Ph(s+|s+,a) = 1 and Ph(s−|s−,a) = 1.
Rewards For any a and i ∈ [m], r1,i(s,a) = 0 rh,i(s+,a) = 1 and rh,i(s−,a) = 0, where h > 1. This also implies the Markov game is cooperative.
If we choose A+ as the joint action with reward Bernoulli( 12 + ε) inM (i). By the construction, for any pure-strategy policy π, if the joint actions taken at step 1 is a 6∈ A+, we have NE-gap(π) ≥ ε. The only useful information in each episode is the transition at step 1. Transition from s1 to s+ can be viewed as getting a 1 reward and transition from s1 to s− can be viewed as getting a 0 reward. So learning pure-strategy Nash equilibrium of this class of Markov games is equivalent to learning pure-strategy Nash equilibrium of a game for m players with stochastic reward. As a result, by
Algorithm 8 Mixed-expert FTRL for weighted adversarial bandits 1: Input: Sequence { αit }
1≤i≤t<∞. 2: Initialize: Accumulators tb′ ← 0 for all b′ ∈ [A]. 3: for t = 1, 2, . . . , T do 4: Compute weight ut ← αtt/α1t . 5: Compute action distributions for all sub-experts b′ ∈ [A] by FTRL:
qb ′ (a) ∝a exp ( −(ηtb′/ut) · tb′∑ τ=1 wτ (b ′)̂̀b′τ (a) ) .
6: Compute pt ∈ ∆[A] by solving the linear system pt(·) = ∑A b′=1 p t(b′)qb ′ (·). 7: Sample sub-expert b ∼ pt. 8: Sample action at ∼ qb from sub-expert b. 9: Play the action at, and observe the (bandit-feedback) loss ˜̀t(at).
10: Update accumulator for sub-expert b: tb ← tb + 1. 11: Compute the loss estimate ̂̀btb(·) ∈ RA≥0 as
̂̀b tb
(a)← ˜̀ tb(a)1 {a = at} qb(a) + γtb .
12: Set wtb(b)← ut.
Lemma F.2, if the number of episodes K ≤ c0 ∑m i=1Ai
ε2/(H − 1)2 ≤ 4c0 H2 ∑m i=1Ai ε2 ,
then there exists general-sum Markov cooperative game MG on which the algorithm suffers from ε/4-suboptimality, EMNE-gap(π̂) ≥ ε/4. This finish the proof of Theorem F.1.

heading: G WEIGHTED ADVERSARIAL BANDIT WITH LOW SWAP REGRET
text: This section is for Algorithm 8. We suppose the action space is [A]. An strategy modification is a function F : [A]→ [A] and for any action distribution µ, F µ gives the swap distribution which takes action F (a) with probability µ(a).
Throughout this section, we assume that the realized loss values ˜̀t ∈ [0, 1]A, and let `t(a) := Et[˜̀t(a)] where Et denotes the expectation w.r.t. the randomness in sampling at(Line 7 and Line 8 in Algorithm 8) at the t-th episode.
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 F . Here, we consider the weighted swap regret which attaches different weights at different episodes. It can be defined as
Rswap(t) := max F :[A]→[A] t∑ i=1 αit[`i(a i)− `i(F (ai))]. (15)
Besides swap regret, we also define R(t) as
R(t) := max F :[A]→[A] t∑ i=1 αit[`i(a i)− 〈 F (pi), `i 〉 ], (16)
where pt is the distribution from which we sample the sub-expert at the t-th episode. We need to bound R(t) in the proof of Lemma D.2. The following of this section is organized as follows: we first start with some properties of Algorithm 8. Then we bound (15) and (16) in Lemma G.1 and Lemma G.2 respectively. Finally, we end with auxiliary lemmas for weighted adversarial bandit with predictable weights.
Solution of the linear system In line 6, we need to compute pt ∈ ∆[A] by solving the linear system pt(·) = ∑A b′=1 p t(b′)qb ′ (·). Such pt(·) can be interpreted as the stationary distribution of a Markov chain over [A] with transition probability P(b|a) = qa(b). This guarantee the existence of pt ∈ ∆[A] such that pt(·) = ∑A b′=1 p t(b′)qb ′ (·). Moreover, pt(·) can be computed efficiently (see e.g. Cohen et al. (2017b)).
FTRL performance of the sub-expert We can focus on the action distribution qb of sub-expert b. When b is sampled in line 7 at episode t. We have accumulator tb and weight wtb(b) = ut = α t t/α 1 t at the end of episode t. Action at is chosen from distribution
qb(a) ∝a exp ( −(ηtb/wtb) · tb−1∑ τ=1 wτ (b ′)̂̀bτ (a) )
after wtb(b) = ut = α t t/α 1 t is observed. The loss estimate ̂̀tb is
̂̀b tb
(a)← ˜̀ tb(a)1 {a = at} qb(a) + γtb .
So from the sub-expert b’s perspective, he is performing FTRL (follow the regularized leader) with changing step size and random weight (We summarize this in Algorithm 9). Suppose the sub-expert b is chosen at episode t = k1, k2, . . . , ktb , then the weighted regret for sub-expert b becomes
Rt(b) := tb∑ τ=1 wτ (b)(`kτ (a kτ )− 〈θ∗, `kτ 〉). (17)
Bounded weight wi(b) This kind of weight wtb(b) = αtt α1t
is designed delicately to ensure the desired αit weight in the swap regret:
Rswap(t) = max F :[A]→[A] t∑ i=1 αit[`i(a i)− `i(F (ai))].
We would explain this in detail in the proof of Lemma G.1. Moreover, because
αtt α1t ≤ 1 α1t = 1 α1(1− α2) · · · (1− αt) = (H + 2)(H + 3) · · · (H + t) 1 · 2 · · · (t− 1) ≤ (H + t)H+1.
So αtt/α 1 t ≤ (H + T )2H ≡W. (18)
The weight wnb(b) = α t t/α 1 t have a (non-random) upper bound W .
Choice of hyperparameter We choose the parameter
ηt = γt =
√ ι
At ,
where the log factor
ι = 4 log 8HAT
p . (19)

heading: G.1 MAIN RESULT FOR MINIMIZING WEIGHTED SWAP REGRET
text: In this subsection, we would state and prove the main result for bounding (15) and (16) with high probability.
Lemma G.1 (Bound on weighted swap regret). If we execute Algorithm 8 for T rounds, then with probability at least 1− p/2, we have the following bound on the swap regret simultaneously for all t ∈ [T ]:
max F :[A]→[A] t∑ i=1 αit[`i(a i)− `i(F (ai))] ≤ 35(HA √ ι/t+HAι/t).
Proof of Lemma G.1 We use bi to denote the sampled sub-expert b at the i-th episode. Define Gi as the σ-algebra generated by all the random variables observed up to the end of the i-th episode.
First observe that
max F :[A]→[A] t∑ i=1 αit[`i(a i)− `i(F (ai))]
≤ max F :[A]→[A] t∑ i=1
αit[`i(a i)− `i(F (bi))]︸ ︷︷ ︸
I
+ max F :[A]→[A] t∑ i=1
αit[`i(F (b i))− `i(F (ai))]︸ ︷︷ ︸
II
.
We first bound term II by concentration. Note that at the i-th episode, as pi obtained in Line 6 solves the equation
pi(a) = A∑ b′=1 pi(b′)qb ′ (a′),
we have bi ∼ pi(·) and ai ∼ qbi(·) has the same marginal distribution conditioned on Gi−1, where Gi−1 denote the σ-algebra generated by `i and all the random variables in the first i−1 episodes. Therefore, fixing any strategy modification F : [A]→ [A], we have { αit[`i(F (b i))− `i(F (ai))] }
1≤i≤t is a bounded martingale difference sequence w.r.t. the filtration {Gi}, so by Azuma-Hoeffding inequality and ∑t i=1(α j t ) 2 ≤ 2H/t,
P ( t∑ i=1 αit[`i(F (b i))− `i(F (ai))] ≥ 2 √ H log 1/p t ) ≤ p.
As there is at most AA strategy modifications, we can substitute p with p/(4AAT ), and take a union bound to get
II = max F :[A]→[A] t∑ i=1 αit[`i(F (b i))− `i(F (ai))] ≤ 2 √ HA log(4AT/p)/t ≤ 2 √ HAι/t (20)
simultaneously for all t ∈ [T ] with probability at least 1− p/4. We next bound term I. Define Ub := { i ∈ [t] : bi = b } and let ntb be the value of tb at the end of
the t-th episode, i.e. ntb = # { i : bi = b } . We also suppose the sub-expert b was chosen at episode t = kb1, k b 2, . . . , k
b ntb up to episode t. Then we have
t∑ i=1 αit[`i(a i)− `i(F (bi))] = ∑ b∈A ∑ i∈Ub αit[`i(a i)− `i(F (b))]
= ∑ b∈A ntb∑ τ=1 α1t α kbτ t α1t [`kbτ (a kbτ )− `kbτ (F (b))]
= ∑ b∈A ntb∑ τ=1 α1twτ (b)[`kbτ (a kbτ )− `kbτ (F (b))].
Here the last equation is because our choice of wτ (a) = α kbτ kbτ /α1kbτ = α kbτ t /α 1 t which is a simple corollary from the definition of αit in Eq. (3).
As we have seen in (17), the term ntb∑ τ=1 wτ (b)[`kbτ (a kbτ )− `kbτ (F (b))],
is exactly the weighted regret Rt(b) for sub-expert b. Because
Rt(b) := ntb∑ τ=1 wτ (b)[`kbτ (a kbτ )− `kbτ (F (b))] ≤ maxθ∗ ntb∑ τ=1 wτ (b)[`kbτ (a kbτ )− 〈 `kbτ , θ ∗〉], we can use our result on weighted adversarial bandits with predictable weights (Lemma G.3) to bound this term (the upper bound W of the weight wτ (b) can be taken as (H + T )2H by the calculation of (18)). Recall that our choice of log term is ι = 4 log 4HATp = log ATdlog2We p′ where p
′ ≤ p/(4A). Thus by Lemma G.3, with probability at least 1− p/(4A),
Rt(b) ≤ 15 max τ≤ntb wτ (b)
[√ Antbι+ ι ] for all t ∈ [T ].
Taking a union bound, we get
Rt(b) ≤ 15 max τ≤ntb wτ (b)
[√ Antbι+ ι ] for all (t, b) ∈ [T ]× [A] (21)
with probability at least 1− p/4. On this event, for all F : [A]→ [A], we have
t∑ i=1 αit[`i(a i)− `i(F (bi))] = ∑ b∈A ntb∑ τ=1 α1twτ (b)[`kbτ (a kbτ )− `kbτ (F (b))]
= ∑ b∈A α1tRt(b)
(i) ≤ ∑ b∈A α1t max τ≤ntb wτ (a)(15 √ Antbι+ 15ι) (ii) = ∑ b∈A α1t α kb nt b t α1t (15 √ Antbι+ 15ι)
(iii) ≤ ∑ a∈A 2H/t(15 √ Antbι+ 15ι).
Here, (i) uses (21), (ii) uses the αt ′ t is increasing w.r.t. t ′ and (iii) uses max0≤t′≤t αt ′
t ≤ 2H/t. Finally, because ∑ b∈A n t b = t, by the concavity of x 7→ √ x, we have with probability at least 1− p/4,
I = max F :[A]→[A] t∑ i=1 αit[`i(a i)− `i(F (bi))] ≤ 30H/t (∑ b∈A ( √ Antbι+ ι) ) ≤ 30H/t(A √ tι+Aι)
= 30HA √ ι/t+ 30HAι/t.
Combining this with (20), we finish the proof.
Lemma G.2. If we execute Algorithm 8 for T rounds, then with probability at least 1− p, we have the following bound simultaneously for all t ∈ [T ]:
max F :[A]→[A] t∑ i=1 αit[`i(a i)− 〈F pi, `i〉] ≤ 40(HA √ ι/t+HAι/t).
Proof of Lemma G.2 Similar to the proof of Lemma G.1, we define Gi−1 as the σ-algebra generated by `i and all the random variables in the first i−1 episodes. Note that for any fixed strategy modification F : [A] → [A], we have that { αit[`i(F (a i))− 〈 F pi, `i 〉 ] } 1≤t≤T is a bounded
martingale difference sequence w.r.t. the filtration {Gi}. So by Azuma-Hoeffding and ∑t i=1(α j t )
2 ≤ 2H/t, we have
P ( t∑ i=1 αit[`i(F (a i))− 〈 F pi, `i 〉 ] ≥ 2 √ H log 1/p t ) ≤ p.
The number of strategy modifications is AA, so we can substitute p with p/(4AAT ), and take a union bound to get, with probability at least 1− p/2,
max F :[A]→[A] t∑ i=1 αit[`i(F (a i))− 〈 F pi, `i 〉 ] ≤ 2 √ HA log(4AT/p)/t ≤ 2 √ HAι/t for all t ∈ [T ].
By Lemma G.1, with probability at least 1− p/2, we have
max F :[A]→[A] t∑ i=1 αit[`i(a i)− `i(F (ai))] ≤ 35(HA √ ι/t+HAι/t) for all t ∈ [T ].
So we conclude that with probability at least 1− p, for all t ∈ [T ], we have
max F :[A]→[A] t∑ i=1 αit[`i(a i)− 〈 F pi, `i 〉 ]
≤ max F :[A]→[A] t∑ i=1 αit[`i(a i)− `i(F (ai))] + max F :[A]→[A] t∑ i=1 αit[`i(F (a i))− 〈 F pi, `i 〉 ]
≤ 40(HA √ ι/t+HAι/t).
This proves the lemma.

heading: G.2 AUXILIARY LEMMAS FOR WEIGHTED ADVERSARIAL BANDIT WITH PREDICTABLE WEIGHTS
text: In this subsection, we consider the Follow the Regularized Leader (FTRL) algorithm with
1. changing step size, 2. weighted regret with Ft−1-measurable weights and loss distributions, 3. high probability regret bound.
We present these results because the predictable weights we 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 a weight wt which takes values in R>0, and distributions (Lat)a∈[A], where each Lat is 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 at, and observes a loss ˜̀t(at) ∼ Lat,t. The action chosen at can be based
Algorithm 9 FTRL for Weighted Regret with Changing Step Size and Predictable Weights 1: for episode t = 1, . . . , T do 2: Observe wt > 0. 3: θt(a) ∝ exp(−ηt/wt ∑t−1 i=1 wi ̂̀ i(a)).
4: Take action at ∼ θt(·), and observe loss ˜̀t(at). 5: ̂̀t(a)← ˜̀t(a)1 {at = a} /(θt(a) + γt).
on all the information in Dt ≡ {(ai, wi, ˜̀i(ai))i≤t−1, wt}. Then, the environment can observe the player’s action at and the incurred loss realization ˜̀t(at), and use these information and some external randomness zt to choose the weight and distributions (wt+1, (La,t+1)a∈[A]) of the next episode. We will consider the following variant of FTRL algorithm for the player.
We denote `t ≡ (E˜̀∼Lat [˜̀])a∈[A] ∈ [0, 1] A which is a random vector but is σ((Lat)a∈[A])measurable. For some θ∗ ∈ RA, the regret of the player up to episode t is defined as
Rt ≡ t∑ i=1 wi(`i(ai)− 〈θ∗, `i〉).
Let (zt)t≥1 be a 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 Ft = σ({ai, ˜̀i, zi}i≤t) to be the sigma algebra generated by the random chosen action ai, the random loss ˜̀ i(ai), and the external random variables zi by episode t. We assume that the random weights and the random loss distributions (wt, (Lat)a∈[A])t≥1 are a (Ft)t≥1-predictable sequence, in the sense that (wt, (Lat)a∈[A]) is Ft−1-measurable. Then Ft contains all information (random chosen action, random observed loss, random weight, and random loss distributions) before action at+1 is taken.
We assume the predictable sequence (wt)1≤t≤T have a global (non-random) upper bound W . Then we define the log term ι = log(AT dlog2W e/p). We set
ηt = γt =
√ ι
At .

heading: G.2.1 REGRET BOUND
text: In the following, we consider to give a high probability weighted regret bound for Algorithm 9.
Lemma G.3. Let (wt, (Lat)a∈[A])t≥1 be any Ft-predictable sequence satisfying 1 ≤ mini≤t wi ≤ maxi≤t wi ≤W for some constant (non-random)W > 0 almost surely. Then, following Algorithm 9, with probability at least 1− 4p, for any θ∗ ∈ ∆A and t ≤ T we have
t∑ i=1 wi(`i(a i)− 〈θ∗, `i〉) ≤ 15 max i≤t wi · [√ Atι+ ι ] ,
where ι = log(AT dlog2W e/p).
Proof. This lemma follows from the bound in Lemma G.4 and a concentration step that we establish below.
Define M = dlog2W e, and wi(k) = wi1 { wi ≤ 2k } . Then wi(k) is also Fi−1 measurable. We
Consider sequence { wi(k)(`i(a i)− 〈θi, `i〉) } i≥1. Since wi is Fi−1-measurable, E[wi(`i(a
i) − 〈θi, `i〉)|Fi−1] = 0, which means { wi(k)(`i(a i)− 〈θi, `i〉) } i≥1 is a martingale difference sequence w.r.t. filtration (Fi). So by Azuma-Hoeffding inequality,
P ( t∑ i=1 wi(k)(`i(a i)− 〈θi, `i〉) ≤ √ 2 · ιt(2k)2 ) ≥ 1− p TM .
Taking a union bound, we have
P ( ∀k ∈ [M ],
t∑ i=1 wi(k)(`i(a i)− 〈θi, `i〉) ≤ 2k √ 2tι
) ≥ 1− p/T. (22)
Denote k′ = dlog2 maxi≤t wie, then we have{ ∀k ∈ [M ],
t∑ i=1 wi(k)(`i(a i)− 〈θi, `i〉) ≤ 2k √ 2tι }
⊆ { t∑ i=1 wi(k ′)(`i(a i)− 〈θi, `i〉) ≤ 2k √ 2tι } ⊆ { t∑ i=1 wi(`i(a i)− 〈θi, `i〉) ≤ 2 max i≤t wi √ 2tι } .
Then probability bound gives
P ( t∑ i=1 wi(`i(a i)− 〈θi, `i〉) ≤ 2 max i≤t wi √ 2tι ) ≥ 1− p/T.
Taking a union bound, we get
t∑ i=1 wi(`i(a i)− 〈θi, `i〉) ≤ 2 max i≤t wi √ 2tι for all t ∈ [T ]
with probability at least 1− p. Summing the above and the regret bound shown in Lemma G.4, we finish the proof.
Lemma G.4. Let (wt, (Lat)a∈[A])t≥1 be any Ft-predictable sequence satisfying 1 ≤ mini≤t wi ≤ maxi≤t wi ≤W for some constant (non-random)W > 0 almost surely. Then, following Algorithm 9, with probability at least 1− 3p, for any θ∗ ∈ ∆A and t ≤ T we have
t∑ i=1 wi 〈θi − θ∗, `i〉 ≤ 10 max i≤t wi · [√ Atι+ ι ] ,
where ι = log(AT dlog2W e/p).
Proof. The regret Rt(θ∗) can be decomposed into three terms
Rt (θ ∗) = t∑ i=1 wi 〈θi − θ∗, `i〉
= t∑ i=1 wi 〈 θi − θ∗, ̂̀i〉︸ ︷︷ ︸ (A) + t∑ i=1 wi 〈 θi, `i − ̂̀i〉︸ ︷︷ ︸ (B) + t∑ i=1 wi 〈 θ∗, ̂̀i − `i〉︸ ︷︷ ︸ (C)
and we bound (A) in Lemma G.6, (B) in Lemma G.7 and (C) in Lemma G.8. Setting ηt = γt = √ ι At , the conditions in Lemma G.6 and Lemma G.8 are satisfied. Putting them together and take union bound, we have with probability 1− 3p
Rt (θ ∗) ≤wt logA ηt + A 2 t∑ i=1 ηiwi + max i≤t wiι+A t∑ i=1 γiwi + 2 max i≤t wi √ 2tι+ 2 max i≤t wiι/γt
≤max i≤t wi
[ √ Aιt+ 3 √ Aι
2 t∑ i=1 1√ t + ι+ 2 √ 2tι+ 2 √ Atι ] ≤10 max
i≤t wi
[√ Atι+ ι ] for all t ∈ [T ]
This proves the lemma.
The rest of this section is devoted to the proofs of the Lemmas used in the proofs of Lemma G.4. We begin the following useful lemma adapted from Lemma 1 in Neu (2015), which is crucial in constructing high probability guarantees. Lemma G.5. For any predictable sequence of coefficients c1, c2, . . . , ct s.t. ci ∈ [0, 2γi]A w.r.t. (Fi)i≥1 and fixing t, we have with probability at least 1− p/(AT ),
t∑ i=1 wi 〈 ci, ̂̀i − `i〉 ≤ 2 max i≤t wiι
Proof. Define M = dlog2W e, and wi(k) = wi1 { wi ≤ 2k } . By definition,
wi(k)̂̀i (a) =wi(k)˜̀i (a)1 {ai = a} θi (a) + γi ≤ wi(k) ˜̀ i (a)1 {ai = a}
θi (a) + wi(k)˜̀i(a)1{ai=a}
2k γi
= 2k
2γi
2γiwi(k)˜̀i(a)1{ai=a} 2kθi(a)
1 + γiwi(k) ˜̀ i(a)1{ai=a}
2kθi(a)
(i) ≤ 2 k
2γi log
( 1 +
2γiwi(k)˜̀i (a)1 {ai = a} 2kθi (a)
)
where (i) is because z1+z/2 ≤ log (1 + z) for all z ≥ 0.
Defining the sum
Ŝi = wi(k)
2k
〈 ci, ̂̀i〉 , Si = wi(k)
2k 〈ci, `i〉 ,
Then Si is Fi−1-measurable since wi, ci, `i are Fi−1-measurable. Using Ei[·] to denote the conditional expectation E[·|Fi], we have
Ei−1 [ exp ( Ŝi )] ≤ Ei−1 [ exp (∑ a ci (a) 2γi log ( 1 + 2γiwi(k)˜̀i (a)1 {ai = a} 2kθi (a) ))] (i)
≤ Ei−1 [∏ a ( 1 + ci (a)wi(k)˜̀i (a)1 {ai = a} 2kθi (a) )]
= Ei−1 [ 1 +
∑ a ci (a)wi(k)˜̀i (a)1 {ai = a} 2kθi (a) ] = 1 + Si ≤ exp (Si)
where (i) is because z1 log (1 + z2) ≤ log (1 + z1z2) for any 0 ≤ z1 ≤ 1 and z2 ≥ −1. Here we are using the condition ci (a) ≤ 2γi to guarantee the condition is satisfied. Equipped with the above bound, we can now prove the concentration result.
P [ t∑ i=1 ( Ŝi − Si ) ≥ ι ] ≤ P [ exp [ t∑ i=1 ( Ŝi − Si )] ≥ ATM p ]
≤ p ATM Et−1
[ exp [ t∑ i=1 ( Ŝi − Si )]]
≤ p ATM Et−2
[ exp [ t−1∑ i=1 ( Ŝi − Si )] Et−1 [ exp ( Ŝt − St )]]
≤ p ATM Et−2
[ exp [ t−1∑ i=1 ( Ŝi − Si )]] ≤ · · · ≤ p
ATM .
So we have
P ( t∑ t=1 wi(k) 〈 ci, ̂̀i − `i〉 ≤ 2kι) ≥ 1− p/(ATM).
Taking a union bound,
P ( ∀k ∈ [M ], t∑ t=1 wi(k) 〈 ci, ̂̀i − `i〉 ≤ 2kι) ≥ 1− p/(AT ). (23)
Denote k′ = dlog2 maxi≤t wie, and note that{ ∀k ∈ [M ], t∑ t=1 wi(k) 〈 ci, ̂̀i − `i〉 ≤ 2kι}
⊆ { t∑ t=1 wi(k ′) 〈 ci, ̂̀i − `i〉 ≤ 2k′ι} ⊆ { t∑ t=1 wi 〈 ci, ̂̀i − `i〉 ≤ 2 max i≤t wiι } .
Therefore, we have
P ( t∑ i=1 wi 〈 ci, ̂̀i − `i〉 ≤ 2 max i≤t wiι ) ≥ 1− p/(AT ).
This proves the lemma.
Using Lemma G.5, we can bound the (A)(B)(C) separately as below. Lemma G.6. If ηi ≤ 2γi for all i ≤ t, with probability 1− p, for any t ∈ [T ] and θ∗ ∈ ∆A,
t∑ i=1 wi 〈 θi − θ∗, ̂̀i〉 ≤ wt logA ηt + A 2 t∑ i=1 ηiwi + 1 2 max i≤t wiι
Proof. We use the standard analysis of FTRL with changing step size, see for example Exercise 28.13 in Lattimore & Szepesvári (2020). Notice the essential step size is ηt/wt,
t∑ i=1 wi 〈 θi − θ∗, ̂̀i〉 ≤ wt logA ηt + 1 2 t∑ i=1 ηiwi 〈 θi, l̂ 2 i 〉 ≤ wt logA
ηt +
1
2 t∑ i=1 ∑ a∈A ηiwi ̂̀i (a) (i) ≤ wt logA ηt + 1 2 t∑ i=1 ∑ a∈A ηiwi`i (a) + max i≤t wiι
≤ wt logA ηt + A 2 t∑ i=1 ηiwi + max i≤t wiι
where (i) is by using Lemma G.5 with ci(a) = ηi. The any-time guarantee is justified by taking union bound.
Lemma G.7. With probability 1− p, for any t ∈ [T ], t∑ i=1 wi 〈 θi, `i − ̂̀i〉 ≤ A t∑ i=1 γiwi + 2 max i≤t wi √ 2tι
Proof. We further decompose the left side into t∑ i=1 wi 〈 θi, `i − ̂̀i〉 = t∑ i=1 wi 〈 θi, `i − Ei−1[̂̀i]〉+ t∑ i=1 wi 〈 θi,Ei−1[̂̀i]− ̂̀i〉.
The first term is bounded by t∑ i=1 wi 〈 θi, `i − Ei−1[̂̀i]〉 = t∑ i=1 wi 〈 θi, `i − θi θi + γi `i 〉
= t∑ i=1 wi 〈 θi, γi θi + γi `i 〉 ≤ A t∑ i=1 γiwi
To bound the second term, we use similar argument in the proof of Lemma G.5 , we define w = maxi≤t wi, M = dlog2W e. and wi(k) = wi1 { wi ≤ 2k } , notice〈
θi, ̂̀i〉 ≤∑ a∈A θi (a) 1 {at = a} θi(a) + γi ≤ ∑ a∈A 1 {ai = a} = 1,
thus {wi(k) 〈 θi,Ei−1[̂̀i]− ̂̀i〉}ti=1 is a bounded martingale difference sequence w.r.t. the filtration
{Fi}ti=1. By Azuma-Hoeffding inequality,
t∑ i=1 wi(k) 〈 θi,Ei−1[̂̀i]− ̂̀i〉 ≤ √√√√2ι t∑ i=1 wi(k)2 ≤ √ 2ι · t(2k)2
with probability at least 1− p/TM . Taking a union bound, we get t∑ i=1 wi(k) 〈 θi,Ei−1[̂̀i]− ̂̀i〉 ≤ √2ι · t22k , for all (t, k) ∈ [T ]× [M ]
with probability at least 1− p. On this event, choosing k′ = dlog2 we, we have t∑ i=1 wi 〈 θi,Ei−1[̂̀i]− ̂̀i〉 ≤ t∑ i=1 wi(k ′) 〈 θi,Ei−1[̂̀i]− ̂̀i〉
≤2k ′√ 2ι · t ≤ 2 max i wi √ 2ι · t.
This ends the proof.
Lemma G.8. With probability 1− p, for any t ∈ [T ] and any θ∗ ∈ ∆A, if γi is non-increasing in i, t∑ i=1 wi 〈 θ∗, ̂̀i − `i〉 ≤ 2 max i≤t wiι/γt
Proof. Define a basis {ej}Aj=1 of R A by
ej (a) = { 1 if a = j 0 otherwise
Then for all the j ∈ [A], apply Lemma G.5 with ci = γtej . Since now ci(a) ≤ γt ≤ γi, the condition in Lemma G.5 is satisfied. As a result, for any t ∈ [T ] and j ∈ [A], we have with probability at least 1− p/(TA) that
t∑ i=1 wi 〈 ej , ̂̀i − `i〉 ≤ 2 max i≤t wiι/γt
Taking a union bound, we have with probability at least 1− p, t∑ i=1 wi 〈 ej , ̂̀i − `i〉 ≤ 2 max i≤t wiι/γt for all (j, t) ∈ [m]× [T ].
Since any θ∗ is a convex combination of {ej}Aj=1, on this event, we also have t∑ i=1 wi 〈 θ∗, ̂̀i − `i〉 ≤ 2 max i≤t wiι/γt for all t ∈ [T ].
This finishes the proof.

Review summaries:
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.

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.

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.  However, the agents do not update simultaneously (i.e., the updates are not concurrent!). They also provide lower bounds.

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$).