When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?

Introduction

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) and 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 general-sum Markov games (MGs) with $m$ players, $H$ steps, $S$ states, and $A_{i}$ 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 $\varepsilon$-approximate Coarse Correlated Equilibrium (CCE) with $\widetilde{\mathcal{O}}(H^{5}S\max_{i\in[m]}A_{i}/\varepsilon^{2})$ episodes of play (Section 3). Our algorithm CCE-V-Learning 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 $\varepsilon$-approximate Correlated Equilibrium (CE) with $\widetilde{\mathcal{O}}(H^{6}S\max_{i\in[m]}A_{i}^{2}/\varepsilon^{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 $\max_{i\in[m]}A_{i}$, and improves significantly in the $A_{i}$ dependency over the current best algorithm which scales with $\prod_{i\in[m]}A_{i}$.

Technically, our algorithm CE-V-Learning makes several major modifications over CCE-V-Learning in order to learn the CE (Section 4.2). Notably, inspired by the connection between CE and low swap-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 $\widetilde{\mathcal{O}}(\Phi_{\max}H^{3}S\sum_{i\in[m]}A_{i}/\varepsilon^{3})$ sample complexity, where $\Phi_{\max}\leq Hm$ is the bound on the potential function (Section 5). Compared with the recent result of Leonardos et al. (2021), we significantly improves the $\varepsilon$ dependence from their $1/\varepsilon^{6}$.

The sample (query) complexity of learning Nash, CE, and CCE from samples in one-step (i.e. normal form) general-sum games with $m$ players and $A_{i}$ actions per player has been studied extensively in literature (Hart and Mas-Colell, 2000; Hart, 2005; Stoltz, 2005; Cesa-Bianchi and Lugosi, 2006; Blum and Mansour, 2007; Fearnley et al., 2015; Babichenko and Barman, 2015; Chen et al., 2015; Fearnley and Savani, 2016; Goldberg and Roth, 2016; Babichenko, 2016; Rubinstein, 2016; Hart and 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 ${\rm poly}(m,\max_{i\leq m}A_{i})$-sample complexity algorithms by independent no-regret learning (Hart and Mas-Colell, 2000; Hart, 2005; Syrgkanis et al., 2015; Goldberg and Roth, 2016; Chen and 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 PPAD-hard (Daskalakis, 2013).

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 and 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 and 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., 2021b; 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 $\prod_{i\leq m}A_{i}$ due to the model-based nature of their algorithm. Algorithms for computing CE in extensive-form games has been widely studied (Von Stengel and Forges, 2008; Celli et al., 2020; Farina et al., 2021; Morrill et al., 2021), though we remark Markov games and extensive-form games are different frameworks and our results do not imply each other.

Concurrent to our work, Jin et al. (2021a); Mao and Başar (2022) also present results for learning CE/CCE in general-sum Markov games, both using variants of the V-Learning algorithm similar as ours. Mao and Başar (2022) provide an $\widetilde{O}(H^{6}S\max_{i\in[m]}A_{i}/\varepsilon^{2})$ sample complexity for learning $\varepsilon$-CCE, which has one additional $H$ factor than our Theorem 2. Jin et al. (2021a) provide an $\widetilde{O}(H^{5}S\max_{i\in[m]}A_{i}/\varepsilon^{2})$ sample complexity for learning $\varepsilon$-CCE similar as our Theorem 2, and $\widetilde{O}(H^{5}S\max_{i\in[m]}A_{i}^{2}/\varepsilon^{2})$ sample complexity for learning $\varepsilon$-CE; the latter result is an $H$ factor better than our Theorem 5, which we remark is due to their use of a slightly different swap regret minimization algorithm from ours. Also, both works above only consider CE/CCE for general-sum Markov games, and do not present results for learning Nash equilibria for 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.

Preliminaries

We present preliminaries for multi-player general-sum Markov games as well as the solution concept of (approximate) Nash equilibrium. Alternative solution concepts and other concrete subclasses of Markov games considered in this paper will be defined in the later sections.

For any product policy $\pi={\left\{\pi_{i}\right\}}_{i\in[m]}$, the best response for the $i^{\text{th}}$ player against $\pi_{-i}$ is defined as any policy $\pi^{\dagger}$ such that $V_{1,i}^{\pi^{\dagger},\pi_{-i}}(s_{1})=\sup_{\pi^{\prime}_{i}}V_{1,i}^{\pi^{\prime}_{i},\pi_{-i}}(s_{1})$. For any Markov product policy, this best response is guaranteed to exist (and be Markov) as the above maximization problem is equivalent to solving a Markov Decision Process (MDP) for the $i^{\text{th}}$ player. We will also use the notation $V_{1,i}^{\dagger,\pi_{-i}}(s_{1})$ to denote the above value function $V_{1,i}^{\pi^{\dagger},\pi_{-i}}(s_{1})$.

We say $\pi$ 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\in[m]$,

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 $\pi$, we define the NE-gap as

For any $\varepsilon\geq 0$, we say $\pi$ is $\varepsilon$-approximate Nash equilibrium ($\varepsilon$-Nash) if $\text{NE-gap}(\pi)\leq\varepsilon$.

A general correlated policy $\pi$ is a set of $H$ maps $\pi\mathrel{\mathop{:}}=\{\pi_{h}:\Omega\times(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}\to\Delta_{\mathcal{A}}\}_{h\in[H]}$. The first argument of $\pi_{h}$ is a random variable $\omega\in\Omega$ sampled from some underlying distribution, and the other arguments contain all the history information and the current state information (unlike Markov policies in which the policies only depend on the current state information). The output of $\pi_{h}$ is a general distribution of actions in $\mathcal{A}=\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{m}$ (unlike product policies in which the action distribution is a product distribution).

For any correlated policy $\pi=\{\pi_{h}\}_{h\in[H]}$ and any player $i$, we can define a marginal policy $\pi_{-i}$ as a set of $H$ maps $\pi_{-i}\mathrel{\mathop{:}}=\{\pi_{h,-i}:\Omega\times(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{S}\to\Delta_{\mathcal{A}_{-i}}\}_{h\in[H]}$ where $\mathcal{A}_{-i}\mathrel{\mathop{:}}=\mathcal{A}_{1}\times\cdots\times\mathcal{A}_{i-1}\times\mathcal{A}_{i+1}\times\cdots\times\mathcal{A}_{m}$, and the output of $\pi_{h,-i}$ is defined as the marginal distribution of the output of $\pi_{h}$ restricted to the space $\mathcal{A}_{-i}$. For any general correlated policy $\pi$, we can define its initial state value function $V_{1,i}^{\pi}(s_{1})$ similar as (1). The best response value of the $i^{\text{th}}$ player against $\pi$ is $V^{\dagger,\pi_{-i}}_{1,i}(s_{1})=\sup_{\mu_{i}}V^{\mu_{i},\pi_{-i}}_{1,i}(s_{1})$, where $V^{\mu_{i},\pi_{-i}}_{1,i}(s_{1})$ is the value function of the policy $(\mu_{i},\pi_{-i})$ (the $i^{\text{th}}$ player plays according to general policy $\mu_{i}$, and all other players play according to $\pi_{-i}$), and the supremum is taken over all general policy $\mu_{i}$ of the $i^{\text{th}}$ player.

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.

1 Exponential lower bound for learning approximate Nash equilibrium

The focus of this paper is the setting where the number of players $m$ is large. Intuitively, as the joint action space has size $|\mathcal{A}|=\prod_{i=1}^{m}A_{i}$ which scales exponentially in $m$ (if each $A_{i}\geq 2$), naive algorithms for learning Nash equilibrium may learn all $r_{i}(\bm{a})$ by enumeratively querying all $\bm{a}\in\mathcal{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(\Omega(m))$ sample complexity lower bound for learning approximate Nash, even in one-step general-sum games (Chen et al., 2015; Rubinstein, 2016) (see Proposition A.0 for formal statement).

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.

Efficient Learning of Coarse Correlated Equilibria (CCE)

Given the difficulty of learning Nash when the number of players $m$ is large , we consider learning other relaxed notions of equilibria for general-sum MGs. Two standard notions of equilibria for games are the Correlated Equilibrium (CE) and Coarse Correlated Equilibrium (CCE), and they satisfy ${\left\{{\rm Nash}\right\}}\subset{\left\{{\rm CE}\right\}}\subset{\left\{{\rm CCE}\right\}}$ for general-sum MGs (Nisan et al., 2007).

We begin by considering learning CCE (most relaxed notion above) for Markov games.

We say a (general) correlated policy $\pi$ is an $\varepsilon$-approximate Coarse Correlated Equilibrium ($\varepsilon$-CCE) if

We say $\pi$ is an (exact) CCE if the above is satisfied with $\varepsilon=0$.

The following result shows that there exists an algorithm that can learn an $\varepsilon$-approximate CCE in general-sum Markov games within $\widetilde{\mathcal{O}}(H^{5}S\max_{i\in[m]}A_{i}/\varepsilon^{2})$ episodes of play.

Suppose we run the CCE-V-Learning algorithm (Algorithm 4) for all $m$ players and

episodes ($\iota=\log(m\max_{i\in[m]}A_{i}HSK/(p\varepsilon))$ is a log factor). Then with probability at least $1-p$, the certified policy $\widehat{\pi}$ defined in Algorithm 2 is an $\varepsilon$-CCE, i.e. $\max_{i\in[m]}(V_{1,i}^{\dagger,\widehat{\pi}_{-i}}(s_{1})-V_{1,i}^{\widehat{\pi}}(s_{1}))\leq\varepsilon$.

For small enough $\varepsilon$, the sample complexity featured in Theorem 2 scales as $\widetilde{\mathcal{O}}(H^{5}S\max_{i\in[m]}A_{i}/\varepsilon^{2})$. Most notably, this is the first algorithm that scales with $\max_{i\in[m]}A_{i}$, and exhibits a sharp difference in learning Nash and learning CCE in view of the $\exp({\Omega(m)})$ lower bound for learning Nash in Proposition A.0. Indeed, existing algorithms such as Multi-Nash-VI Algorithm with CCE subroutine (Liu et al., 2021) does require $\widetilde{\mathcal{O}}(H^{4}S^{2}\prod_{i=1}^{m}A_{i}/\varepsilon^{2})$ episodes of play, which scales with $\prod_{i\in[m]}A_{i}$ due to its model-based nature. We achieve significantly better dependence on $A_{i}$ and also $S$, though slightly worse $H$ dependence.

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.0). We also adopted the choice of hyperparameters in Tian et al. (2021) so that the sample complexity has a slightly better dependence in $H$. When combined with the “certified correlated policy” procedure (Algorithm 2), our algorithm outputs a policy that is $\varepsilon$-CCE. Our certified policy procedure is adapted from the certified policy of Bai et al. (2020), and differs in that ours output a correlated policy for all the players whereas Bai et al. (2020) outputs a product policy. The key feature enabling this $\max_{i\in[m]}A_{i}$ dependence is that this algorithm uses decentralized learning for each player to learn the value function ($V$), instead of learning the $Q$ function (as in Liu et al. (2021)) that requires sample size scales as $\prod_{i\in[m]}A_{i}$. The proof of Theorem 2 is in Appendix C.

Efficient Learning of Correlated Equilibria (CE)

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.

A strategy modification $\phi\mathrel{\mathop{:}}={\left\{\phi_{h,s}\right\}}_{(h,s)\in[H]\times\mathcal{S}}$ for player $i$ is a set of $H\times S$ functions $\phi_{h,s}:(\mathcal{S}\times\mathcal{A})^{h-1}\times\mathcal{A}_{i}\to\mathcal{A}_{i}$. A strategy modification $\phi$ can be composed with any policy $\pi$ to give a modified policy $\phi\diamond\pi$ defined as follows: At any step $h$ and state $s$ with the history information $\tau_{h-1}=(s_{1},\bm{a}_{1},\cdots,s_{h-1},\bm{a}_{h-1})$, if $\pi$ chooses to play $\bm{a}=(a_{1},\dots,a_{m})$, the modified policy $\phi\diamond\pi$ will play $(a_{1},\dots,a_{i-1},\phi_{h,s}(\tau_{h-1},a_{i}),a_{i+1},\dots,a_{m})$. We use $\Phi_{i}$ denote the set of all possible strategy modifications for player $i$.

We say a (general) correlated policy $\pi$ is an $\varepsilon$-approximate CE ($\varepsilon$-CE) if

We say $\pi$ is an (exact) CE if the above is satisfied with $\varepsilon=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).

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 weighted swap regret algorithm (mixed-expert FTRL) for every $(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 $A_{i}$ “sub-experts” indexed by $b^{\prime}\in[A_{i}]$ (Each sub-expert represents an independent “expert” that runs her own FTRL algorithm). Sub-expert $b^{\prime}$ first computes an action distribution $q^{b^{\prime}}(\cdot)\in\Delta_{\mathcal{A}_{i}}$ 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 $\mu$ computed from $\{q^{b^{\prime}}\}_{b^{\prime}\in[A_{i}]}$, then sample the actual action $a_{h,i}$ from $q^{b}$.

Line 13-17 (Take action and record observations): Player $i$ takes action $a_{h,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 $\overline{V}_{h,i}$ using step-size $\alpha_{t}$ and bonus $\overline{\beta}_{t}$.

Finally, after executing Algorithm 1 for $K$ episodes, we use the certified correlated policy procedure (Algorithm 2) to obtain our final output policy $\widehat{\pi}$. 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:

The constants $\alpha_{t}^{j}$ used in Algorithm 2 is defined as

Note that for any $t\geq 1$, $\{\alpha_{t}^{j}\}_{1\leq j\leq t}$ sums to one and defines a distribution over $[t]$.

2 Overview of techniques

Here we briefly overview the techniques used in Algorithm 1.

Minimizing swap regret via mixed-expert FTRL The key technical advance in our Algorithm 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 and Lugosi, 2006). To integrate this into Markov games, we utilize a celebrated reduction from low-swap-regret learning to usual low-regret learning (Blum and Mansour, 2007), which for any bandit problem with $A_{i}$ actions maintains $A_{i}$ 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 $\mu(\cdot)$ for sampling the sub-expert is carefully chosen by solving a linear system (Line 10) so that $\mu$ 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 $\alpha_{t}^{i}$, 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.4, and the consequent analysis for the weighted swap regret in Appendix G.1-G.3, 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. 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 and 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.

3 Theoretical guarantee

We are now ready to present the theoretical guarantee for our CE-V-Learning algorithm.

Suppose we run the CE-V-Learning algorithm (Algorithm 1) for all $m$ players for

episodes ($\iota=\log(m\max_{i\in[m]}A_{i}HSK/(p\varepsilon))$ is a log factor). Then with probability at least $1-p$, the certified correlated policy $\widehat{\pi}$ defined in Algorithm 2 is an $\varepsilon$-CE, i.e. $\max_{i\in[m]}\sup_{\phi\in\Phi_{i}}(V_{1,i}^{\phi\diamond\widehat{\pi}}(s_{1})-V_{1,i}^{\widehat{\pi}}(s_{1}))\leq\varepsilon$.

To the best of our knowledge, Theorem 5 presents the first result for learning CE that scales polynomially with $\max_{i\in[m]}A_{i}$, 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 $\prod_{i\in[m]}A_{i}$. Similar as in Theorem 2, this follows as our CE-V-Learning uses decentralized learning for each player to learn the value function ($V$) . We also observe that our sample complexity for learning CE is higher than for learning CCE by a factor of $\widetilde{\mathcal{O}}(H\max_{i\in[m]}A_{i})$; the additional $\max_{i\in[m]}A_{i}$ factor is expected as CE is a strictly harder notion of equilibrium. The proof of Theorem 5 can be found in Appendix D.

Finally, combining Theorem 2 & 5 with the exponential lower bound for learning Nash (Section 2.1), we obtain a full characterization of which equilibria can be learned with ${\rm poly}(m)$ sample complexity in general-sum Markov games: This is possible for CCE and CE, but not Nash.

Learning Nash Equilibria in Markov Potential Games

In this section, we consider learning Nash equilibria in Markov Potential Games (MPGs), an important subclass of general-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 $\varepsilon$ by a simple reduction to single-agent learning.

We first present the definition of MPGs. Our definition is the finite-horizon variantOur results can easily adapted to the discounted infinite time horizon setup. 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, $\pi$ denotes a Markov product policy.

(Markov potential games) A general-sum Markov game is a Markov potential game if there exists a potential function $\Phi$ mapping any product policy to a real number in $[0,{\Phi_{\rm max}}]$, such that for any $i\in[m]$, any two policies $\pi_{i},\pi_{i}^{\prime}$ of the $i^{\text{th}}$ player, and any policy $\pi_{-i}$ of other players, the difference of the value functions of the $i^{\text{th}}$ player with policies $(\pi_{i},\pi_{-i})$ and $(\pi_{i}^{\prime},\pi_{-i})$ is equals the difference of the potential function on the same policies, i.e.,

Note that the range of the potential function ${\Phi_{\rm max}}$ admits a trivial upper bound ${\Phi_{\rm max}}\leq mH$ (this can be seen by varying $\pi_{i}$ for one $i$ at a time). An important example of MPGs is Markov Cooperative Games (MCGs) where all players share the same reward $r_{i}\equiv r$.

2 Algorithm and theoretical guarantee

We present a simple algorithm Nash-CA (Nash Coordinate Ascent) for learning an $\varepsilon$-Nash 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 that Nash-CA is additionally guaranteed to output a pure-strategy Nash equilibrium (cf. Appendix E for definition).

For Markov potential games, with probability at least $1-p$, Algorithm 3 terminates within $4\Phi_{\text{max}}/\varepsilon$ steps of the while loop, and outputs an $\varepsilon$-approximate (pure-strategy) Nash equilibrium. The total episodes of play is at most

where $\iota=\log(\frac{mHSK\max_{1\leq i\leq m}A_{i}}{\varepsilon p})$ is a log factor.

For small enough $\varepsilon$, the sample complexity for the Nash-CA algorithm in the above theorem is $\widetilde{\mathcal{O}}({\Phi_{\rm max}}H^{3}S\sum_{i\leq m}A_{i}/\varepsilon^{3})$. As $\Phi_{\max}\leq mH$, this at most scales with the number of players as $m\sum_{i\leq m}A_{i}$, 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 ${\rm poly}(m,\max_{i\leq m}A_{i})$ dependence, and significantly improves on the $\varepsilon$ dependence from their $\varepsilon^{-6}$ to $\varepsilon^{-3}$. In addition, our algorithm does not require assumptions on bounded distribution mismatch coefficient as they do, due to the exploration nature of our single-agent MDP subroutine.

Also, compared with the sample complexity bound $\widetilde{\mathcal{O}}(H^{4}S^{2}\prod_{i=1}^{m}A_{i}/\varepsilon^{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 $\varepsilon$, yet overall our sample complexity is still better unless $\varepsilon<(\sum_{i=1}^{m}A_{i})/(\prod_{i=1}^{m}A_{i})$ is exponentially small. The proof of Theorem 7 can be found in Appendix E.

To accompany Theorem 7, we establish a sample complexity lower bound of $\Omega(H^{2}\sum_{i=1}^{m}A_{i}/\varepsilon^{2})$ for learning pure-strategy Nash in MCGs and hence MPGs (Theorem F.0 in Appendix F). This lower bound improves in the $A_{i}$ dependence over the naive reduction to single-player MDPs (Domingues et al., 2021), which gives $\Omega(H^{3}S\max_{i\in[m]}A_{i}/\varepsilon^{2})$, though is loose on the $S,H$ dependence. The improved $A_{i}$ dependence is achieved by constructing a novel class of hard instances of on one-step games (Lemma F.0), 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 $\widetilde{\mathcal{O}}(\sum_{i=1}^{m}A_{i}/\varepsilon^{3})$ or the $\widetilde{\mathcal{O}}(\prod_{i=1}^{m}A_{i}/\varepsilon^{2})$ of Liu et al. (2021), which we leave as future work.

Conclusion

This paper investigates the question of when can we solve general-sum Markov games (MGs) sample-efficiently with a mild dependence on the number of players. Our results show that this is possible for learning approximate (Coarse) Correlated Equilibria in general-sum MGs, as well as learning approximate Nash equilibrium in Markov potential games. 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.

Acknowledgement

Ziang Song is partially supported by the elite undergraduate training program of School of Mathematical Sciences in Peking University.

References

Appendix A Exponential in m𝑚m Lower Bound for Learning Nash in General-sum MGs

In this section, we give a sample complexity lower bound for computing approximate Nash equilibrium in one-step binary-action general-sum MGs ($H=1$, $S=1$ and $A_{i}=2$) which has an exponential dependence in $m$, the number of players. The result is built on the lower bound of query complexity in Rubinstein (2016).

We use $\mathcal{G}$ to denote the one-step Markov game ($H=1$ and $S=1$), in which there are $m$ players and $A=2$ actions for each player. We index the players by $[m]=\{1,\dots,m\}$ and denote the actions space of each player by $[A]=\{1,2\}$. Since we restricted attention to binary-action games (i.e. $A=2$), the total number of joint actions is $2^{m}$.

We define a (exact) query as the procedure where the algorithm queries a joint action $\bm{a}\in[A]^{m}$ and observes the (deterministic) reward $r_{i}(\bm{a})\in$. We define the query complexity (Chen et al., 2015) for learning $\varepsilon$-approximate Nash equilibrium (ANE) as the following.

The query complexity $QC_{p}({\rm ANE}(m,\varepsilon))$ for learning $\varepsilon$-ANE is defined as the smallest $n$ such that there exists a randomized oracle algorithm $\mathcal{A}$ satisfying the following: for any binary-action, m-player game $\mathcal{G}$, the algorithm $\mathcal{A}$ can use no more than $n$ sequential queries of the reward to output an $\varepsilon$-ANE with probability at least $1-p$.

In one-step MGs with deterministic reward, the query complexity is equivalent to the sample complexity, since each query obtains a reward entry. The following result in Rubinstein (2016) gives a $2^{\Omega(m)}$ query complexity lower bound for learning $\varepsilon_{0}$-ANE in $m$-player binary action games.

There exists absolute constants $\varepsilon_{0}>0$ and $c>0$, such that for all $m$,

This result shows that it is impossible for any algorithm to learn an $\varepsilon_{0}$-ANE for every binary action game with probability at least $(1-p)$ using ${\rm poly}(m,\log(1/p))$ samples: such an algorithm with $p=2^{-cm}$ would only use ${\rm poly}(m,\log(2^{cm}))={\rm poly}(m)$ samples, yet the sample complexity lower bound in Proposition A.0 requires at least $2^{\Omega(m)}=\exp(\Omega(m))$ samples. Since Proposition A.0 allows $\varepsilon_{0}=\Theta(1)$, this also rules out the possibility of learning $\varepsilon$-ANE with ${\rm poly}(m,\log(1/p),1/\varepsilon)$ samples for all small $\varepsilon$.

Appendix B Q function and Bellman equations

From these definitions, we have the Bellman equations

for all $(i,s,\bm{a},h)\in[m]\times\mathcal{S}\times\mathcal{A}\times[H]$ (where we have set $V_{H+1,i}^{\pi}(s)=0$ for all $h,i\in[H]\times[m]$).

Appendix C Proofs for Section 3

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 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:

where $c>0$ is some absolute constant, and $\iota=\log(\frac{m\max_{i\in[m]}A_{i}HSK}{p\varepsilon})$ is a log factor. The choice of $\eta_{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 $\iota$. In fact, we need $\iota$ to be $C\log(\frac{m\max_{i\in[m]}A_{i}HSK}{p\varepsilon})$ 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.

C.2 Proof of Theorem 2

We begin with an auxiliary lemma on $\alpha^{j}_{t}$ (its definition is in (3)).

The following properties hold for $\alpha_{t}^{j}$:

1. $\frac{1}{\sqrt{t}}\leq\sum_{j=1}^{t}\frac{\alpha_{t}^{j}}{\sqrt{j}}\leq\frac{2}{\sqrt{t}}$ for every $t\geq 1$ .

2. $\max_{j\in[t]}\alpha_{t}^{j}\leq\frac{2H}{t}$ and $\sum_{j=1}^{t}\left(\alpha_{t}^{j}\right)^{2}\leq\frac{2H}{t}$ for every $t\geq 1$ .

3. $\sum_{t=j}^{\infty}\alpha_{t}^{j}=1+\frac{1}{H}$ for every $j\geq 1$.

4. $\sum_{j=1}^{t}\frac{\alpha_{t}^{j}}{j}\geq\frac{1}{2t}$ for every $t\geq 1$.

Property 4 above does not appear in (Jin et al., 2018), for which we provide a quick proof here:

Here, (i) uses $\alpha_{t}^{j}$ is increasing in $j$ for fixed $t$. ∎

Towards proving Theorem 2, we begin with a simple consequence of the update rule in Algorithm 4, which will be used several times later.

Fix a state $s$ in time step $h$ and fix an episode $k$, let $t=N_{h}^{k}(s)$ and suppose s was previously visited at episodes $k^{1}<\dots<k^{t}<k$ at the $h$-th step. The update rules in Algorithm 4 gives the following equations:

We next present and prove the following lemma which helps to explain why our choice of the bonus term is $\overline{\beta}_{t}$. The constant $c$ in $\overline{\beta}_{t}$ is actually the same with the constant $c$ in this lemma.

Fix a state $s$ in time step $h$ and fix an episode $k$, let $t=N_{h}^{k}(s)$ and suppose s was previously visited at episodes $k^{1}<\dots<k^{t}<k$ at the $h$-th step. With probability at least $1-\frac{p}{2}$, for any $(i,s,h,t)\in[m]\times\mathcal{S}\times[H]\times[K]$, there exist a constant c s.t.

into $R^{\star}(i,s,h,t)+U(i,s,h,t)$ where

So we can apply Azuma-Hoeffding inequality. Note that $\sum_{j=1}^{t}(\alpha_{t}^{j})^{2}\leq 2H/t$ by Lemma C.0. Using Azuma-Hoeffding inequality, we have with probability at least $1-\frac{p}{4mHSK}$

After taking a union bound, we have the following statement is true with probability at least $1-p/4$,

Then we bound $R^{\star}(i,s,h,t)$. For fixed $(i,s,h)$, if we define the loss function

simultaneously for all $t\in[K]$ . By Lemma C.0 and $\eta_{t}=\sqrt{\frac{H\iota}{A_{i}t}}$, we have with probability at least $1-\frac{p}{4mHS}$

Again, taking a union bound in all $(i,s,h)\in[m]\times\mathcal{S}\times[H]$, we have with probability at least $1-p/4$,

Finally, we concluded that with probability at least $1-p/2$, we have

Recall that the certified policy $\widehat{\pi}$ as in Algorithm 2 is a nested mixture of policies. We further define policies $\{\widehat{\pi}_{h}^{k}\}_{h\in[H],k\in[K]}$ in Algorithm 5. By construction, the relationship between $\widehat{\pi}$ and $\widehat{\pi}_{h}^{k}$ is that when players jointly play policy the $\widehat{\pi}$, they first sample $k$ from $\text{Uniform}([K])$, then they play together the policy $\widehat{\pi}_{1}^{k}$ (Algorithm 5 for $h=1$) with the same sampled $k$. As a result, we have the following relationship:

We define the policy starting from the $h$-th step for player $i$ as $\pi_{\geq h,i}\mathrel{\mathop{:}}=\{\pi_{h^{\prime},i}:\Omega\times(\mathcal{S}\times\mathcal{A})^{h^{\prime}-h}\times\mathcal{S}\to\Delta_{\mathcal{A}_{i}}\}_{h^{\prime}=h}^{H}$. At each step $h^{\prime}\geq h$, $\pi_{\geq h,i}$ samples action based on current state, the history starting from the $h$-th step and a random number $\omega\in\Omega$. We use $\Pi_{\geq h,i}$ to denote all policies for player $i$ starting from the $h$-th step. Similar to Section 2, we can define general correlated policy starting from the $h$-th step (where the random numbers may be correlated for different players), and we use $\Pi_{\geq h}$ to denote all such general correlated policy starting from the $h$-th step.

For $\pi\in\Pi_{\geq h}$, we can define the value function starting from the $h$-th step as:

We also define the value function of the best response as:

One example of a policy starting from the $h$-th step is $\widehat{\pi}_{h}^{k}$ defined in Algorithm 5, so that we can define $V_{h,i}^{\widehat{\pi}_{h}^{k}}(s)$ and $V_{h,i}^{\dagger,\widehat{\pi}_{h,-i}^{k}}(s)$.

for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$ with probability at least $1-p$.

Proof of Lemma C.0 We prove this lemma by backward induction over $h\in[H+1]$. The base case of $h=H+1$ is true as all the value functions equal by definition. Suppose the claim is true for $h+1$. We begin with upper bounding $V_{h,i}^{\dagger,\widehat{\pi}_{h,-i}^{k}}(s)$. Let $t=N_{h}^{k}(s)$ and $k^{j}=k_{h}^{j}(s)$ for $1\leq j\leq t$ to be the $j$’th time that $s$ is previously visited. By the definition of certified policies $\widehat{\pi}_{h,i}^{k}$ and by the value iteration formula of MGs, we have for any policy $\mu_{i}\in\Pi_{\geq h,i}$,

Conditional on the high probability event in Lemma C.0, we use the inductive hypothesis to obtain

Here, (i) uses our choice of $\overline{\beta}_{j}=c\sqrt{\frac{H^{3}A_{i}\iota}{j}}+2c\frac{H^{2}\iota}{j}$ and $\frac{1}{\sqrt{t}}\leq\sum_{j=1}^{t}\frac{\alpha_{t}^{j}}{\sqrt{j}},\frac{1}{t}\leq\sum_{j=1}^{t}\frac{2\alpha_{t}^{j}}{j}$.

Meanwhile, for $\underline{V}_{h,i}^{k}(s)$, by the definition of certified policy and inductive hypothesis,

Here, (i) uses $\sum_{j=1}^{t}\alpha_{t}^{j}\beta_{j}\geq 2\sum_{j=1}^{t}\alpha_{t}^{j}\sqrt{H^{3}\iota/j}\geq 2\sqrt{H^{3}\iota/t}.$

As a result, the backward induction would work well for all $h$ as long as the inequalities in Lemma C.0 and (9) hold for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$. Taking a union bound in all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$, we have with probability at least $1-p/2$, the inequality in (9) is true simultaneously for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$. Therefore the inequalities in Lemma C.0 and (9) hold simultaneously for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$ with probability at least $1-p$. This finishes the proof of this lemma. ∎

Equipped with these lemmas, we are ready to prove Theorem 2.

Proof of Theorem 2 Conditional on the high probability event in Lemma C.0 (this happens with probability at least $1-p$), we have

for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$. Then, choosing $h=1$ and $s=s_{1}$, we have

Moreover, by (7), value function of certified policy can be decomposed as

where the decomposition is due to the first line in the Algorithm 2: sample $k\leftarrow$Uniform($[K]$).

To prove $\widehat{\pi}$ is an approximate CCE, we only need to bound $\sum_{k=1}^{K}\left(\overline{V}_{1,i}^{k}(s_{1})-\underline{V}_{1,i}^{k}(s_{1})\right)$. Letting $\delta_{h,i}^{k}:=\overline{V}_{h,i}^{k}(s_{h}^{k})-\underline{V}_{h,i}^{k}(s_{h}^{k})$ and $t=N_{h}^{k}(s_{h}^{k})$. Suppose $s_{h}^{k}$ was previously visited at episodes $k^{1},\dots,k^{t}$ at the $h$-th step. By the update rule,

We can use Lemma C.0 which gives $\sum_{j=1}^{t}\alpha_{t}^{j}/\sqrt{j}\leq 2/t$ and $\max_{j\leq t}{\alpha_{t}^{j}}\leq 2H/t$ to get

where we also uses $\sum_{j=1}^{t}1/j\leq 1+\log t$.

Taking the summation w.r.t. k, we begin by the first two terms;

where (i) is by changing the order of summation and (ii) is by Lemma C.0.

where we assume $\iota\geq 1$. So we have

Recursing this argument for $h\in[H]$ gives

Therefore, $K\geq\mathcal{O}(\frac{H^{5}S\max_{i\in[m]}A_{i}\iota}{\varepsilon^{2}}+\frac{SH^{4}\iota^{3}}{\varepsilon})$ guarantees that we have $V_{1,i}^{\dagger,\widehat{\pi}_{-i}}(s_{1})-V_{1,i}^{\widehat{\pi}}(s_{1})\leq\varepsilon$ for all $i\in[m]$. This complete the proof of Theorem 2. ∎

Appendix D Proofs for Section 4

In this section we prove Theorem 5. We first define a set of lower value estimates $\underline{V}_{h,i}^{k}(s)$ (along with the upper estimates used in Algorithm 1) via the following update rule:

We emphasize that $\underline{V}_{h,i}^{k}(s)$ are analyses quantities only for simplifying the proof, and are not used by the algorithm.

The following lemma is the same as Lemma C.0 in the CCE case (except that for a different algorithm).

Fix a state $s$ in time step $h$ and fix an episode $k$, let $t=N_{h}^{k}(s)$ and suppose s was previously visited at episodes $k^{1}<\dots<k^{t}<k$ at the $h$-th step. The update rule for $\overline{V}_{h,i}(s)$ and $\underline{V}_{h,i}(s)$ in Algorithm 1 and (10) gives the following equations:

We next prove the following lemma which helps explain our choice of the bonus term $\overline{\beta}_{t}$. The constant $c$ in $\overline{\beta}_{t}$ is the same with the constant $c$ in this lemma. For any policy modification $\varphi_{i}:\mathcal{A}_{i}\to\mathcal{A}_{i}$ for the $i^{\text{th}}$ player and one-step policy $\pi_{h}:\mathcal{S}\to\Delta_{\mathcal{A}}$ for any $h$, the modified policy $\varphi_{i}\diamond\pi_{h}$ is defined as follows: if $\pi_{h}$ chooses to play $\bm{a}=(a_{1},\dots,a_{m})$, the modified policy $\varphi_{i}\diamond\pi_{h}$ will play $(a_{1},\dots,a_{i-1},\varphi_{i}(a_{i}),a_{i+1},\dots,a_{m})$. Moreover, for $\pi_{h,i}:\mathcal{S}\to\Delta_{\mathcal{A}_{i}}$, policy $\varphi_{i}\diamond\pi_{h,i}$ chooses $\varphi_{i}(a)$ when $\pi_{h,i}$ chooses $a$.

Fix a state $s$ in time step $h$ and fix an episode $k$, let $t=N_{h}^{k}(s)$ and suppose s was previously visited at episodes $k^{1}<\dots<k^{t}<k$ at the $h$-th step. With probability $1-\frac{p}{2}$, for any $(i,s,h,t)\in[m]\times\mathcal{S}\times[H]\times[K]$, there exist a constant c s.t.

Proof of Lemma D.0 First, like the prove in Lemma C.0, we decompose

into $R^{\star}(i,s,h,t)+U(i,s,h,t)$ where

We first bound $U(i,s,h,t)$. By the same reason in proof of Lemma C.0, we can apply Azuma-Hoeffding inequality. Note that $\sum_{j=1}^{t}(\alpha_{t}^{j})^{2}\leq 2H/t$ by Lemma C.0. Using Azuma-Hoeffding inequality, we have with probability at least $1-\frac{p}{4mHSK}$,

After taking a union bound, the following statement is true with probability at least $1-p/4$,

Then we bound $R^{\star}(i,s,h,t)$. For fixed $(i,s,h)$, we define loss function

Now, for any fixed step $h$ and state $s$, the distributions ${\left\{q_{h}^{b}(\cdot|s)\right\}}_{b}$ and visitation counts ${\left\{N_{h}^{b}(s)\right\}}_{b}$ are only updated at episodes $k_{h}^{1}(s),\dots,k_{h}^{t}(s)$. Further, these updates are exactly equivalent to the mixed-expert FTRL update algorithm which we describe in Algorithm 8. Therefore, the $R^{\star}(i,s,h,t)$ above can be bounded by the weighted swap regret bound of Lemma G.0 (choosing the log term as $\iota=4\log\frac{10mSAHK}{p}$) to yield that

with probability at least $1-p/(4mSH)$. Taking a union bound over all $(i,s,h)\in[m]\times\mathcal{S}\times[H]$, we have with probability at least $1-p/4$,

Finally, we conclude that with probability at least $1-p/2$, we have

We define the auxiliary certified policies $\widehat{\pi}_{h}^{k}$ in Algorithm 6 (same as Algorithm 5 for the CCE case but repeated here for clarity). Again, we have the following relationship:

A strategy modification starting from the $h$-th step $\phi_{\geq h}\mathrel{\mathop{:}}={\left\{\phi_{h^{\prime},s}\right\}}_{(h^{\prime},s)\in\{h,h+1,\dots,H\}\times\mathcal{S}}$ for player $i$ is a set of $S\times(H-h+1)$ functions $\phi_{h^{\prime},s}:(\mathcal{S}\times\mathcal{A})^{h^{\prime}-h}\times\mathcal{A}_{i}\to\mathcal{A}_{i}$. This strategy modification $\phi_{\geq h}$ can be composed with any policy $\pi\in\Pi_{\geq h}$ (as in Definition C.0) to give a modified policy $\phi_{\geq h}\diamond\pi$ defined as follows: At any step $h^{\prime}\geq h$ and state $s$ with the history information starting from the $h$-th step $\tau_{h:h^{\prime}-1}=(s_{h},\bm{a}_{h},\cdots,s_{h^{\prime}-1},\bm{a}_{h^{\prime}-1})$, if $\pi$ chooses to play $\bm{a}=(a_{1},\dots,a_{m})$, the modified policy $\phi\diamond\pi$ will play $(a_{1},\dots,a_{i-1},\phi_{h^{\prime},s}(\tau_{h:h^{\prime}-1},a_{i}),a_{i+1},\dots,a_{m})$. We use $\Phi_{\geq h,i}$ denote the set of all such possible strategy modifications for player $i$.

For any $\phi\in\Phi_{\geq h,i}$, $\phi\diamond\widehat{\pi}_{h}^{k}$ also doesn’t depend on the history before the $h$-th step, so $\phi\diamond\widehat{\pi}_{h}^{k}\in\Pi_{\geq h}$, which implies that $V_{h,i}^{\phi\diamond\widehat{\pi}_{h}^{k}}(s)$ is well-defined in (8).

for all $(i,k,h,s)\in[m]\times[K]\times[H]\times\mathcal{S}$ with probability at least $1-p/2$.

Proof of Lemma D.0 We prove this lemma by backward induction over $h\in[H+1]$. The base case of $h=H+1$ is true as all the value functions equal . Suppose the claim is true for $h+1$. We begin with upper bounding $\sup_{\phi\in\Phi_{\geq h,i}}V_{h,i}^{\phi\diamond\widehat{\pi}_{h}^{k}}(s)$. Let $t=N_{h}^{k}(s)$ and $k^{j}=k_{h}^{j}(s)$ for $1\leq j\leq t$ to be the $j$’th time that $s$ is previously visited. By the definition of certified policies $\widehat{\pi}_{h,i}^{k}$ and by the value iteration formula of MGs, we have for any $\phi\in\Phi_{\geq h,i}$,

Condition on the high probability event (with probability at least $1-p/2$) in Lemma D.0, we can use the inductive hypothesis to obtain

Here, (i) uses our choice of $\overline{\beta}_{j}=cH^{2}A_{i}\sqrt{\frac{\iota}{j}}+2c\frac{H^{2}A_{i}\iota}{j}$ and $\frac{1}{\sqrt{j}}\leq\sum_{j=1}^{t}\frac{\alpha_{t}^{j}}{\sqrt{j}},\frac{1}{t}\leq\sum_{j=1}^{t}\frac{2\alpha_{t}^{j}}{j}$, so that $cH^{2}A_{i}\sqrt{\iota/t}+cH^{2}A_{i}\iota/t\leq\sum\alpha_{t}^{j}\overline{\beta}_{j}$.

Meanwhile, for $\underline{V}_{h,i}^{k}(s)$, by the definition of certified policy and inductive hypothesis,

Here, (i) uses $\sum_{j=1}^{t}\alpha_{t}^{j}\beta_{j}\geq 2\sum_{j=1}^{t}\alpha_{t}^{j}\sqrt{H^{3}\iota/j}\geq 2\sqrt{H^{3}\iota/t}.$

As a result, the backward induction would work well for all $h$ as long as the inequalities in Lemma D.0 and (12) hold for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$. Taking a union bound in all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$, we have with probability at least $1-p/2$, the inequality in (12) is true simultaneously for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$. Therefore the inequalities in Lemma C.0 and (12) hold simultaneously for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$ with probability at least $1-p$. This finishes the proof of this lemma. ∎

Equipped with these lemmas, we are ready to prove Theorem 5.

Proof of Theorem 5 Conditional on the high probability event in Lemma D.0 (this happens with probability at least $1-p$), we have

for all $(i,s,h,k)\in[m]\times\mathcal{S}\times[H]\times[K]$. Then, choosing $h=1$ and $s=s_{1}$, we have

Moreover, by (11), value function of certified policy can be decomposed as

where the decomposition is due to the first line in the Algorithm 2: sample $k\leftarrow$Uniform($[K]$). Therefore we have the following bound on $\sup_{\phi\in\Phi_{i}}V_{1,i}^{\phi\diamond\widehat{\pi}}(s_{1})-V_{1,i}^{\widehat{\pi}}(s_{1})$:

By Lemma D.0 Letting $\delta_{h,i}^{k}:=\overline{V}_{h,i}^{k}(s_{h}^{k})-\underline{V}_{h,i}^{k}(s_{h}^{k})$ and $t=N_{h}^{k}(s_{h}^{k})$. By the update rule, we have

Taking the summation w.r.t. k, by the same argument in the proof of Theorem 2, we can get

Therefore, if $K\geq\mathcal{O}(\frac{H^{6}S\max_{i\in[m]}A_{i}^{2}\iota}{\varepsilon^{2}}+\frac{H^{4}S\max_{i\in[m]}A_{i}\iota^{3}}{\varepsilon})$, we have $\max_{\phi\in\Phi}V_{1,i}^{\phi\diamond\widehat{\pi}}(s_{1})-V_{1,i}^{\widehat{\pi}}(s_{1})\leq\varepsilon$ holds for all $i\in[m]$, which means $\widehat{\pi}$ is an $\varepsilon$-approximate CE. This completes the proof of Theorem 2. ∎

Appendix E Proofs for Section 5

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.

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.0.

E.2 The UCBVI-UPLOW sub-routine

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. We 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 UCBVI-UPLOW 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.

We have the following sample complexity guarantee for the UCBVI-UPLOW algorithm returning an $\varepsilon$-approximate optimal policy.

The UCBVI-UPLOW algorithm always returns a deterministic policy $\pi^{k_{\star}}$. Moreover, for any $p\in(0,1]$, letting $\iota=\log(SAHK/p)$ and taking the number of episodes

then with probability at least $1-p$, the returned policy $\pi^{k_{\star}}$ is $\varepsilon$-approximate optimal, i.e., $\sup_{\mu}V_{1}^{\mu}(s_{1})-V_{1}^{\pi^{k_{\star}}}(s_{1})\leq\varepsilon$.