Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence

Introduction

Multi-agent reinforcement learning (RL) studies how multiple players learn to maximize their long-term returns in a setup where players’ actions influence the environment and other agents’ returns (Busoniu et al., 2008; Zhang et al., 2021a). Recently, multi-agent RL has achieved significant success in various multi-agent learning scenarios, e.g., competitive game-playing (Silver et al., 2016, 2018; Vinyals et al., 2019), autonomous robotics (Shalev-Shwartz et al., 2016; Levine et al., 2016), and economic policy-making (Zheng et al., 2020; Trott et al., 2021). In the framework of stochastic games (Shapley, 1953; Fink, 1964), most results are established for fully-competitive (i.e., two-player zero-sum) games; e.g., see Daskalakis et al. (2020); Wei et al. (2021b); Cen et al. (2021). However, to achieve social welfare for AI (Dafoe et al., 2020, 2021; Stastny et al., 2021), it is imperative to establish theoretical guarantees for multi-agent RL in Markov games with cooperation.

Policy gradient methods (Williams, 1992; Sutton et al., 2000) have received significant attention for both single-agent (Bhandari & Russo, 2019; Agarwal et al., 2021) and multi-agent RL problems (Zhang et al., 2019; Daskalakis et al., 2020; Wei et al., 2021b). Independent policy gradient (Zhang et al., 2021a; Ozdaglar et al., 2021) is probably the most practical protocol in multi-agent RL, where each player behaves myopically by only observing her own rewards and actions (as well as the system states), while individually optimizing its own policy. More importantly, independent learning dynamics do not scale exponentially with the number of players in the game. Recently, Daskalakis et al. (2020); Leonardos et al. (2022); Zhang et al. (2021b) have in fact shown that multi-agent RL players could perform policy gradient updates independently, while enjoying global non-asymptotic convergence. However, these results are only focused on the basic tabular setting in which the value functions are represented by tables; they do not carry over to large-scale multi-agent RL problems in which the state space size is potentially infinite and the number of players is large. This motivates the following question:

Can we design independent policy gradient methods for large-scale Markov games, with non-asymptotic global convergence guarantees?

In this paper, we provide the first affirmative answer to this question for a class of mixed cooperative/competitive Markov games: Markov potential games (MPGs) (Macua et al., 2018; Leonardos et al., 2022; Zhang et al., 2021b). In particular, we make the following contributions:

We propose an independent policy gradient algorithm – Algorithm 1 – for learning an $\epsilon$-Nash equilibrium of MPGs with $O(1/\epsilon^{2})$ iteration complexity. In contrast to the existing results (Leonardos et al., 2022; Zhang et al., 2021b), such iteration complexity does not explicitly depend on the state space size.

We consider a linear function approximation setting and design an independent sample-based policy gradient algorithm – Algorithm 2 – that learns an $\epsilon$-Nash equilibrium with $O(1/\epsilon^{5})$ sample complexity. This appears to be the first result for learning MPGs with function approximation.

We establish the convergence of an independent optimistic policy gradient algorithm – Algorithm 3 that has been proved to converge in learning zero-sum Markov games (Wei et al., 2021b) – for learning a subclass of MPGs: Markov cooperative games. We show that the same type of optimistic policy learning algorithm provides an $\epsilon$-Nash equilibrium in both zero-sum Markov games and Markov cooperative games while the players are oblivious to the types of games being played. To the best of our knowledge, this appears to be the first game-agnostic convergence result in Markov games.

Markov potential games (MPGs). In stochastic optimal control, the MPG model dates back to Dechert & O’Donnell (2006); González-Sánchez & Hernández-Lerma (2013). More recent studies include Zazo et al. (2016); Mazalov et al. (2017); Macua et al. (2018); Mguni et al. (2018) and all of these studies focus on systems with known dynamics. MPGs have also attracted attention in multi-agent RL. In the infinite-horizon setting, Leonardos et al. (2022); Zhang et al. (2021b) extended the policy gradient method (Agarwal et al., 2021; Kakade, 2001) for multiple players and established the iteration/sample complexity that scales with the size of state space; Fox et al. (2022) generalized the natural policy gradient method (Kakade, 2001; Agarwal et al., 2021) and established the global asymptotic convergence. In the finite-horizon setting, Song et al. (2022) built on the single-agent Nash-VI (Liu et al., 2021) to propose a sample efficient turn-based algorithm and Mao et al. (2022) studied the policy gradient method. Earlier, Wang & Sandholm (2002); Lowe et al. (2017) studied Markov cooperative games and Kleinberg et al. (2009); Palaiopanos et al. (2017); Cohen et al. (2017a) studied one-state MPGs; both of these are special cases of MPGs. We note that the term: Markov potential game has also been used to refer to state-based potential MDPs (Marden, 2012; Mguni et al., 2021), which are different from the MPGs that we study; see counterexamples in Leonardos et al. (2022).

Policy gradient methods for Markov games. Despite recent advances on the theory of policy gradient (Bhandari & Russo, 2019; Agarwal et al., 2021), the theory of policy gradient methods for multi-agent RL is relatively less studied. In the basic two-player zero-sum Markov games, Zhang et al. (2019); Bu et al. (2019); Daskalakis et al. (2020); Zhao et al. (2021) established global convergence guarantees for policy gradient methods for learning an (approximate) Nash equilibrium. More recently, Cen et al. (2021); Wei et al. (2021b) examined variants of policy gradient methods and provided last-iterate convergence guarantees. However, it is much harder for the policy gradient methods to work in general Markov games (Mazumdar et al., 2020; Hambly et al., 2021). The effectiveness of (natural) policy gradient methods for tabular MPGs was demonstrated in Leonardos et al. (2022); Zhang et al. (2021b); Fox et al. (2022); Zhang et al. (2022). Moreover, Xie & Zhong (2020); Wang et al. (2021a); Yu et al. (2021); Peng et al. (2021) reported impressive empirical performance of multi-agent policy gradient methods with function approximation in cooperative Markov games, but the theoretical foundation has not been provided.

Independent learning recently received attention in multi-agent RL (Daskalakis et al., 2020; Zhang et al., 2021a; Ozdaglar et al., 2021; Sayin et al., 2021; Jin et al., 2021a; Song et al., 2022; Kao et al., 2022), because it only requires local information for learning and naturally yields algorithms that scale to a large number of players. The algorithms in Leonardos et al. (2022); Zhang et al. (2021b); Fox et al. (2022); Zhang et al. (2022) can also be generally categorized as independent learning algorithms for MPGs.

Game-agnostic convergence. Being game-agnostic is a desirable property for independent learning in which players are oblivious to the types of games being played. In particular, classical fictitious-play warrants average-iterate convergence for several games (Robinson, 1951; Monderer & Shapley, 1996; Hofbauer & Sandholm, 2002). Although online learning algorithms, e.g., the one based on multiplicative weight updates (MWU) (Cesa-Bianchi & Lugosi, 2006), offer average-iterate convergence in zero-sum matrix games, they often do not provide last-iterate convergence guarantees (Bailey & Piliouras, 2018), which motivates recent studies (Daskalakis & Panageas, 2018; Mokhtari et al., 2020; Wei et al., 2020). Interestingly, while MWU converges in last-iterate for potential games (Palaiopanos et al., 2017; Cohen et al., 2017a), this is not the case for zero-sum matrix games (Cheung & Piliouras, 2020). Recently, Leonardos et al. (2021); Leonardos & Piliouras (2022) established last-iterate convergence of $Q$-learning dynamics for both zero-sum and potential/cooperative matrix games. However, it is open question whether an algorithm can have last-iterate convergence for both zero-sum and potential/cooperative Makov games.

Preliminaries

In this section, we introduce Markov potential games (MPGs), define the Nash equilibrium, and describe the problem setting.

We consider an $N$-player, infinite-horizon, discounted Markov potential game (Macua et al., 2018; Leonardos et al., 2022; Zhang et al., 2021b),

where ${\mathcal{A}}_{-i}$ is the set of actions of all but the $i$th player. We use the shorthand $\bar{Q}_{i}^{\pi}$ for $\bar{Q}_{i}^{\pi_{i},\,\pi_{-i}}$ when $\pi_{i}$ and $\pi_{-i}$ are from the same joint policy $\pi$. It is straightforward to see that $V_{i}^{\pi},Q_{i}^{\pi}$, and $\bar{Q}_{i}^{\pi}$ are bounded between and $1/(1-\gamma)$.

We recall the notion of (Markov perfect stationary) Nash equilibrium (Fink, 1964). A joint policy $\pi^{\star}$ is called a Nash equilibrium if for each player $i=1,\ldots,N$,

and called an $\epsilon$-Nash equilibrium if for $i=1,\ldots,N$,

Nash equilibria for MPGs with finite states and actions always exist (Fink, 1964). When the state space is infinite, we assume the existence of a Nash equilibrium; see Takahashi (1962); Maitra & Parthasarathy (1970, 1971); Altman et al. (1997) for cases with countable or compact state spaces.

Given policy $\pi$ and initial state $s^{(0)}$, we define the discounted state visitation distribution,

It is useful to introduce a variant of the performance difference lemma (Agarwal et al., 2021) for multiple players; for other versions, see Zhang et al. (2019); Daskalakis et al. (2020); Zhang et al. (2021b); Leonardos et al. (2022).

For the $i$th player, if we fix the policy $\pi_{-i}$ and any state distribution $\mu$, then for any two policies $\widehat{\pi}_{i}$ and $\bar{\pi}_{i}$,

where $\bar{Q}_{i}^{\bar{\pi}_{i},\pi_{-i}}\!(s,a_{i})\!=\!\sum_{a_{-i}}\!\!\!\!\pi_{-i}{(a_{-i}|s)}Q_{i}^{\bar{\pi}_{i},\pi_{-i}}\!(s,a_{i},a_{-i}).$

It is common to use the distribution mismatch coefficient to measure the exploration difficulty in policy optimization (Agarwal et al., 2021). We next define a distribution mismatch coefficient for MPGs (Leonardos et al., 2022) in Definition 1, and its minimax variant in Definition 2.

For any distribution $\mu\in\Delta({\mathcal{S}})$ and policy $\pi\in\Pi$, the distribution mismatch coefficient $\kappa_{\mu}$ is the maximum distribution mismatch of $\pi$ relative to $\mu$, $\kappa_{\mu}\mathrel{\mathop{:}}=\sup_{\pi\,\in\,\Pi}\,\left\|d_{\mu}^{\pi}/\mu\right\|_{\infty}$, where the division ${d_{\mu}^{\pi}}/{\mu}$ is evaluated in a componentwise manner.

For any distribution $\mu\in\Delta({\mathcal{S}})$, the minimax distribution mismatch coefficient $\widetilde{\kappa}_{\mu}$ is the minimax value of the distribution mismatch of $\pi$ relative to $\nu$, $\widetilde{\kappa}_{\mu}\mathrel{\mathop{:}}=\inf_{\nu\,\in\,\Delta({\mathcal{S}})}\sup_{\pi\,\in\,\Pi}\,\left\|d_{\mu}^{\pi}/\nu\right\|_{\infty}$, where the division $d_{\mu}^{\pi}/\nu$ is evaluated in a componentwise manner.

Independent Learning Setting

We examine an independent learning setting (Zhang et al., 2021a; Daskalakis et al., 2020; Ozdaglar et al., 2021) for Markov potential games in which all players repeatedly execute their own policy and update rules individually. At each time $t$, all players propose their own polices $\pi_{i}^{(t)}$: ${\mathcal{S}}\to\Delta({\mathcal{A}}_{i})$ with the player index $i=1,\ldots,N$, while a game oracle can either evaluate each player’s policy or generate a set of sample trajectories for each player. In repeating such protocol for $T$ times, each player behaves myopically in optimizing its own policy.

To evaluate the learning performance, we introduce a notion of regret,

which averages the worst player’s local gaps in $T$ iterations: $\max_{\pi_{i}^{\prime}}V_{i}^{\pi_{i}^{\prime},\,\pi_{-i}^{(t)}}(\rho)-V_{i}^{\pi^{(t)}}(\rho)$ for $t=1,\ldots,T$, where $\max_{\pi_{i}^{\prime}}V_{i}^{\pi_{i}^{\prime},\,\pi_{-i}^{(t)}}(\rho)$ is the $i$th player best response given $\pi_{-i}^{(t)}$. In $\text{Nash-Regret}(T)$, we compare the learnt joint policy $\pi^{(t)}$ with the best policy that the $i$th player can take by fixing $\pi_{-i}^{(t)}$. We notice that Nash-Regret is closely related to the notion of dynamic regret (Zinkevich, 2003) in which the regret comparator changes over time. This is a suitable notion because the environment is non-stationary from the perspective of an independent learner (Matignon et al., 2012; Zhang et al., 2021a).

To obtain an $\epsilon$-Nash equilibrium $\pi^{(t^{\star})}$ with a tolerance $\epsilon>0$, our goal is to show the following average performance,

The existence of such $t^{\star}$ is straightforward,

Since each summand above is non-negative, $V_{i}^{\pi^{(t^{\star})}}(\rho)\geq V_{i}^{\pi_{i}^{\prime},\,\pi_{-i}^{(t^{\star})}}(\rho)-\epsilon$ for any $\pi_{i}^{\prime}$ and $i=1,\ldots,N$, which implies that $\pi^{(t^{\star})}$ is an $\epsilon$-Nash equilibrium.

For an independent learning setting without uncertainty in gradient evaluation, we introduce a policy gradient method for Markov potential/cooperative games in Section 4. In Section 5, we utilize a sample-based approach with function approximation to address the scenario in which true gradient is not available and, in Section 6, we provide the game-agnostic convergence analysis.

Independent Policy Gradient Methods

In this section, we assume that we have access to exact gradient and examine a gradient-based method for learning a Nash equilibrium in Markov potential/cooperative games.

A natural independent learning scheme for MPGs is to let every player independently perform policy gradient ascent (Leonardos et al., 2022; Zhang et al., 2021b). In this approach, the $i$th player updates its policy according the gradient of the value function with respect to the policy parameters,

where the calculation for the gradient in (4.1) can be found in Agarwal et al. (2021); Leonardos et al. (2022); Zhang et al. (2021b).

Update rule (4.1) may suffer from a slow learning rate for some states. Since the gradient with respect to $\pi_{i}(a_{i}\,|\,s)$ scales with $d^{\pi}_{\rho}(s)$ – which may be small if the current policy $\pi$ has small visitation frequency to $s$ – the corresponding states may experience slow learning progress. To address this issue, we propose the following update rule (equivalent to (2) in Algorithm 1):

which essentially removes the ${d^{\pi}_{\rho}(s)}/(1-\gamma)$ factor in standard policy gradient (4.1) and alleviates the slow-learning issue. Interestingly, update rule (4) for the single-player MDP has also been studied in Xiao (2022), concurrently. However, since the optimal value is not unique, the analysis of Xiao (2022) does not apply to our multi-player case for which many Nash policies exist and the set that contains them is non-convex (Leonardos et al., 2022). We also note that regularized variants of (4) for the single-player MDP appeared in Lan (2022); Zhan et al. (2021).

Furthermore, in contrast to (4.1), our update rule (4) is invariant to the initial state distribution $\rho$. This allows us to establish performance guarantees simultaneously for all $\rho$ in a similar way as typically done for natural policy gradient (NPG) and other policy mirror descent algorithms for single-player MDPs (Agarwal et al., 2021; Lan, 2022; Zhan et al., 2021).

Theorem 1 establishes performance guarantees for Algorithm 1; see Appendix B.1 for proof.

For MPG (1) with an initial state distribution $\rho$, if all players independently perform the policy update in Algorithm 1 then, for two different choices of stepsize $\eta$, we have

Depending on the stepsize $\eta$, Theorem 1 provides two rates for the average Nash regret: $T^{-{1}/{4}}$ and $T^{-{1}/{2}}$. The technicalities behind these choices will be explained later and, to obtain an $\epsilon$-Nash equilibrium, our two bounds suggest respective iteration complexities,

Compared with the iteration complexity guarantees in Leonardos et al. (2022); Zhang et al. (2021b), our bounds in Theorem 1 improve the dependence on the distribution mismatch coefficient $\kappa_{\rho}$ and the state space size $S$. Since our minimax distribution mismatch coefficient $\widetilde{\kappa}_{\rho}$ satisfies

our $\widetilde{\kappa}_{\rho}$-dependence or $\min(\kappa_{\rho},S)$-dependence are less restrictive than the explicit $S$-dependence in Leonardos et al. (2022); Zhang et al. (2021b). Importantly, this permits our bounds to work for systems with large number of states, and makes Algorithm 1 suitable for sample-based scenario with function approximation (see Section 5). With polynomial dependence on the number of players $N$ instead of exponential, Algorithm 1 overcomes the curse of multiagents (Jin et al., 2021a; Song et al., 2022). In terms of problem parameters $(\gamma,A,N,C_{\Phi})$, our iteration complexity either improves or becomes slightly worse.

When the state space is infinite, explicit $S$-dependence disappears in our iteration complexities. Implicit $S$-dependence only exists in the distribution mismatch coefficient $\kappa_{\rho}$ or $\widetilde{\kappa}_{\rho}$. However, it is easy to bound $\kappa_{\rho}$ by devising an initial state distribution without introducing constraints on the MDP dynamics. For instance, in MPGs with agent-independent transitions (in which every state is a potential game and transitions do not depend on actions (Leonardos et al., 2022)), if we select $\rho$ to be the stationary state distribution $d_{\rho}^{\pi}$ then $\kappa_{\rho}=1$ regardless of the state-space size $S$.

A key step of the analysis is to quantify the policy improvement regarding the potential function $\Phi$ in each iteration. Similar to the standard descent lemma in optimization (Arora, 2008), applying the projected policy gradient algorithm to a smooth $\Phi$ yields the following ascent property (cf. Eq. (9) in Leonardos et al. (2022) and Lemmas 11 and 12 in Zhang et al. (2021b)),

where $\beta>0$ is related to the smoothness constant (or the second-order derivative) of the potential function. However, since the search direction in our policy update is not the standard search direction utilized in policy gradient, this ascent analysis does not apply to our algorithm.

To obtain such improvement bound, it is crucial to analyze the joint policy improvement. Let us consider two players $i$ and $j$: player $i$ changes its policy from $\pi_{i}$ to $\pi_{i}^{\prime}$ to maximize its own reward based on the current policy profile $(\pi_{i},\pi_{j})$ and player $j$ changes its policy from $\pi_{j}$ to $\pi_{j}^{\prime}$ in its own interest. What is the overall progress after they independently change their policies from $(\pi_{i},\pi_{j})$ to $(\pi_{i}^{\prime},\pi_{j}^{\prime})$? One method of capturing the joint policy improvement exploits the smoothness of the potential function, which is useful in the standard policy gradient ascent method (Leonardos et al., 2022; Zhang et al., 2021b). In our analysis, we connect the joint policy improvement with the individual policy improvement via the performance difference lemma. In particular, as shown in Lemma 3, Lemma 2 and Lemma 21 provide an effective means for analyzing the joint policy improvement. The proposed approach could be of independent interests for analyzing other Markov games.

In Lemma 3, we obtain two different joint policy improvement bounds by dealing with the cross terms in two different ways (see the proofs for details). Hence, we establish two different Nash-Regret bounds in Theorem 1: one has better dependence on $T$ while the other has better dependence on $\kappa_{\rho}$. Even though, it is an open issue how to achieve the best of the two, we next show that this is indeed possible for a special case: Markov cooperative games.

2 Faster rates for Markov cooperative games

When all players use the same reward function, i.e., $r=r_{i}$ for all $i=1,\ldots,N$, MPG (1) reduces to a Markov cooperative game. In this case, $V_{i}^{\pi}=V^{\pi}$ and $Q_{i}^{\pi}=Q^{\pi}$ for all $i=1,\ldots,N$ and Algorithm 1 works immediately. Thus, we continue to use $\text{Nash-Regret}_{i}(T)$ that is defined through $V_{i}^{\pi_{i}^{\prime},\,\pi_{-i}^{(t)}}=V^{\pi_{i}^{\prime},\,\pi_{-i}^{(t)}}$ and $V_{i}^{\pi^{(t)}}=V^{\pi^{(t)}}$.

Theorem 2 provides a Nash-Regret bound for Markov cooperative games; see Appendix B.2 for proof.

For MPG (1) with identical rewards and an initial state distribution $\rho$, if all players independently perform the policy update in Algorithm 1 with stepsize $\eta=(1-\gamma)/(2NA)$ then,

For Markov cooperative games, Theorem 2 achieves the best of the two bounds in Theorem 1 and an $\epsilon$-Nash equilibrium is achieved with the following iteration complexity,

This iteration complexity improves the ones provided in Leonardos et al. (2022); Zhang et al. (2021b) in several aspects. In particular, we have introduced the minimax distribution mismatch coefficient $\widetilde{\kappa}_{\rho}$, which is upper bounded by $\kappa_{\rho}$. Since we take this $\widetilde{\kappa}_{\rho}$, our bound improves the $\kappa_{\rho}$-dependence in Leonardos et al. (2022); Zhang et al. (2021b) from $\kappa_{\rho}^{2}$ to $\kappa_{\rho}$. We note that if we view the Markov cooperative game as an MPG, then the value function $V^{\pi}$ serves as a potential function $\Phi$ which is bounded between and $1/(1-\gamma)$. Thus, our $(1-\gamma)$-dependence matches the one in Zhang et al. (2021b) and improves the one in Leonardos et al. (2022) by $(1-\gamma)^{2}$.

Independent Policy Gradient with Function Approximation

We next remove the exact gradient requirement and apply Algorithm 1 to the linear function approximation setting. In what follows, we assume that the averaged action value function is linear in a given feature map.

Moreover, $\left\|{\phi_{i}}\right\|\leq 1$ for all $s,a_{i}$, and $\left\|{w_{i}^{\pi}}\right\|\leq W$ for all $\pi$.

Without loss of generality, we can assume $W\leq{\sqrt{d}}/(1-\gamma)$; see Lemma 8 in Wei et al. (2021a). Assumption 1 is a multi-agent generalization of the standard linear $Q$ assumption (Abbasi-Yadkori et al., 2019) for single-player MDPs. It is different from the multi-agent linear MDP assumption (Xie et al., 2020; Dubey & Pentland, 2021) in which both transition and reward functions are linear in given feature maps. In contrast, Assumption 1 qualifies each player to estimate its averaged action value function without observing other players’ actions. A special case of Assumption 1 is the tabular case in which the sizes of state/action spaces are finite, and where we can select $\phi_{i}$ to be an indicator function. Since the feature map $\phi_{i}$ is locally-defined coordination between players is avoided (Zhao et al., 2021).

Since RL with function approximation is statistically hard in general, e.g., see Weisz et al. (2021); Wang et al. (2021b) for hardness results, assuming regularity of underlying MDPs is necessary for the application of function approximation to multi-agent RL in which either the value function (Xie et al., 2020; Dubey & Pentland, 2021; Jin et al., 2021b; Huang et al., 2022) or the policy (Zhao et al., 2021) is approximated. Because of restrictive function approximation power, the main challenge is the entanglement of policy improvement (or optimization) and policy evaluation (or approximation) errors. In Theorem 3 and Theorem 4, we show that optimization and approximation errors are decoupled under Assumption 1 so that we can control them, separately. Our analysis can be generalized to some neural networks, e.g., overparametrized neural networks (Liu et al., 2019), a rich function class that allows splitting optimization and approximation errors, which we leave for future work.

After each player collects $K$ samples, in Phase 2, they use these samples to estimate $\bar{Q}_{i}^{(t)}(\cdot,\cdot)$, which is required for policy updates. By Assumption 1,

where $w_{i}^{(t)}$ represents $w_{i}^{\pi^{(t)}}$. Our goal is to obtain a solution $\widehat{w}_{i}^{(t)}\approx w_{i}^{(t)}$ using samples, and estimate $\bar{Q}_{i}^{(t)}(s,a_{i})$ via

where $\nu_{i}^{(t)}(s,a_{i})\mathrel{\mathop{:}}=d_{\rho}^{(t)}(s)\circ\pi^{(t)}_{i}(a_{i}\,|\,s)$ and $L_{i}^{(t)}(w_{i}^{(t)})=0$ by Assumption 1. We make the following assumption for the expected regression loss of $\widehat{w}_{i}^{(t)}$.

Fix a state distribution $\rho$. For any sequence of iterates $\widehat{w}_{i}^{(1)},\ldots,\widehat{w}_{i}^{(T)}$ for $i=1,\ldots,N$ that are generated by Algorithm 2, there exists an $\epsilon_{\text{stat}}<\infty$ such that

for all $i$ and $t$, where the expectation is on randomness in generating $\widehat{w}_{i}^{(t)}$.

The bound for $\epsilon_{\text{stat}}$ can be established using standard linear regression analysis (Audibert & Catoni, 2009) and it is given by \epsilon_{\text{stat}}=O\big{(}\frac{dW^{2}}{K(1-\gamma)^{2}}\big{)}. This bound can be achieved by applying the stochastic projected gradient descent method (Hsu et al., 2012; Cohen et al., 2017b) to the regression problem.

After obtaining $\widehat{Q}^{(t)}_{i}(\cdot,\cdot)$, we update the polices in (8) which is different from the update in Algorithm 1 in two aspects: (i) the gradient direction $\widehat{Q}^{(t)}_{i}(\cdot,\cdot)$ is the estimated version of $\bar{Q}^{(t)}_{i}(\cdot,\cdot)$; and (ii) the Euclidean projection set becomes $\Delta_{\xi}({\mathcal{A}}_{i})\mathrel{\mathop{:}}=\{\,(1-\xi)\,\pi_{i}(\cdot\,|\,s)+\xi\,\text{Unif}_{{\mathcal{A}}_{i}},\forall\pi_{i}(\cdot\,|\,s)\,\}$ that introduces $\xi$-greedy policies for exploration (Leonardos et al., 2022; Zhang et al., 2021b), where $\xi\in(0,1)$.

Theorem 3 establishes performance guarantees for Algorithm 2; see Appendix C.2 for proof.

Let Assumption 1 hold for MPG (1) with an initial state distribution $\rho$. If all players independently run Algorithm 2 with \xi=\min\Big{(}\left(\frac{\kappa_{\rho}^{2}NA\epsilon_{\text{stat}}}{(1-\gamma)^{2}W^{2}}\right)^{\frac{1}{3}},\frac{1}{2}\Big{)} and Assumption 2 holds, then

Theorem 3 shows the additive effect of the function approximation error $\epsilon_{\text{stat}}$ on the Nash regret of Algorithm 2. When $\epsilon_{\text{stat}}=0$, Theorem 3 matches the rates in Theorem 1 in the exact gradient case. As in Algorithm 1, even though update rule (8) iterates over all $s\in{\mathcal{S}}$, we do not need to assume a finite state space ${\mathcal{S}}$. In fact, (8) only “defines” a function $\pi_{i}^{(t)}(\cdot~{}|~{}s)$ instead of “calculating” it. This is commonly used in policy optimization with function approximation, e.g., Cai et al. (2020); Luo et al. (2021). To execute this algorithm, $\pi_{i}^{(t)}(\cdot~{}|~{}s)$ only needs to be evaluated if necessary, e.g., when the state $s$ is visited in Phase 1 of Algorithm 2.

When we apply stochastic projected gradient updates to (7), Algorithm 2 becomes a sample-based algorithm and existing stochastic projected gradient results directly apply. Depending on the stepsize choice, an $\epsilon$-Nash equilibrium is achieved with sample complexities (see Corollary 1 in Appendix C.4),

Compared with the sample complexity guarantees for the tabular MPG case (Leonardos et al., 2022; Zhang et al., 2021b), our sample complexity guarantees hold for MPGs with potentially infinitely large state spaces. When we specialize Assumption 1 to the tabular case, our second sample complexity improves the sample complexity in Leonardos et al. (2022); Zhang et al. (2021b) from $O({1}/{\epsilon^{6}})$ to $O({1}/{\epsilon^{5}})$.

As before, we get improved performance guarantees when we apply Algorithm 2 to Markov cooperative games.

Let Assumption 1 hold for MPG (1) with identical rewards and an initial state distribution $\rho>0$. If all players independently perform the policy update in Algorithm 2 with stepsize $\eta=(1-\gamma)/(2NA)$ and exploration rate \xi=\min\Big{(}\left(\frac{\kappa_{\rho}^{2}NA\epsilon_{\text{stat}}}{(1-\gamma)^{2}W^{2}}\right)^{\frac{1}{3}},\frac{1}{2}\Big{)}, with Assumption 2,

where ${\mathcal{R}}(\eta)=\frac{\sqrt{\kappa_{\rho}AN}}{(1-\gamma)^{2}\sqrt{T}}.$

We prove Theorem 4 in Appendix C.3 and show sample complexity $TK=O({1}/{\epsilon^{5}})$ in Corollary 2 of Appendix C.4.

Game-Agnostic Convergence

In Section 4 and Section 5, we have shown that our independent policy gradient method converges (in best-iterate sense) to a Nash equilibrium of MPGs. For the same algorithm in two-player case, however, (Bailey & Piliouras, 2019) showed that players’ policies can diverge for zero-sum matrix games (a single-state case of zero-sum Markov games). A natural question arises:

Does there exist a simple gradient-based algorithm that provably converges to a Nash equilibrium in both potential/cooperative and zero-sum games?

Unfortunately, classical MWU and optimistic MWU updates do not converge to a Nash equilibrium in zero-sum and coordination games simultaneously (Cheung & Piliouras, 2020). Recently, this question was partially answered by Leonardos et al. (2021); Leonardos & Piliouras (2022) in which the authors established last-iterate convergence of $Q$-learning dynamics to a quantal response equilibrium for both zero-sum and potential/cooperative matrix games. In this work, we provide an affirmative answer to this question for general Markov games that cover matrix games. Specifically, we next show that optimistic gradient descent/ascent with a smoothed critic (see Algorithm 3 in Appendix A) – an algorithm that converges to a Nash equilibrium in two-player zero-sum Markov games (Wei et al., 2021b) – also converges to a Nash equilibrium in Markov cooperative games.

In Theorem 5, we establish asymptotic last-iterate convergence of Algorithm 3 in Markov cooperative games; see Appendix D.1 for proof.

For MPG (1) with two players and identical rewards, if both players run Algorithm 3 with $0<\eta<(1-\gamma)/(32\sqrt{A})$ and a non-increasing $\{\alpha^{(t)}\}_{t\,=\,1}^{\infty}$ that satisfies $0<\alpha^{(t)}<1/6$ and $\sum_{t\,=\,t^{\prime}}^{\infty}\alpha^{(t)}=\infty$ for any $t^{\prime}\geq 0$, then the policy pair $(x^{(t)},y^{(t)})$ converges to a Nash equilibrium when $t\rightarrow\infty$.

Last-iterate convergence in Theorem 5 is measured by the local gaps $\max_{x^{\prime}}(V^{x^{\prime},y^{(t)}}(\rho)-V^{x^{(t)},y^{(t)}}(\rho))$ and $\max_{y^{\prime}}(V^{x^{(t)},y^{\prime}}(\rho)-V^{x^{(t)},y^{(t)}}(\rho))$, i.e., a policy pair $(x^{(t)},y^{(t)})$ constitutes an approximate Nash policy for large $t$. The condition on algorithm parameters $\eta$ and $\alpha^{(t)}$ in Theorem 5 is mild in sense that it is straightforward to take a pair of such parameters that ensures last-iterate convergence in zero-sum Markov games (Wei et al., 2021b). Hence, Algorithm 3 enjoys last-iterate convergence in both two-player Markov cooperative and zero-sum competitive games. Compared with the result (Fox et al., 2022), our proof of Theorem 5 utilizes gap convergence instead of point-wise policy convergence that is restricted to isolated fixed points of the algorithm dynamics. Moreover, our algorithm works for both cooperative and competitive Markov games.

In the following Theorem 6, we further strengthen our result of Theorem 5 and show the sublinear Nash-Regret bounds for Algorithm 3 in both two-player Markov cooperative and zero-sum competitive games; see Appendix D.2 for proof.

(i) For MPG (1) with two players and identical rewards ($r_{1}=r_{2}=r$), if both players independently run Algorithm 3 with $\alpha^{(t)}=\frac{1}{6\sqrt{t}}$ and $\eta=\frac{(1-\gamma)^{2}}{32\sqrt{SA}}$, then

(ii) For a two-player zero-sum Markov game ($r_{1}=-r_{2}=r$), if both players independently run Algorithm 3 with the same choice of $\alpha^{(t)}$ and $\eta$, then

For two-player Markov cooperative/competitive games, Theorem 6 establishes the same rate $T^{-1/6}$ for the Nash regret and the average duality gap, respectively. Alternatively, independent players in Algorithm 3 can find an $\epsilon$-Nash equilibrium after $O(1/\epsilon^{6})$ iterations, no matter which types of games are being played. To the best of our knowledge, Theorem 6 appears to be the first game-agnostic convergence for Markov cooperative/competitive games with finite-time performance guarantees. We leave the extension to more general Markov games for future work.

Experimental Results

To demonstrate the merits and the effectiveness of our approach, we examine an MDP in which every state defines a congestion game. This example is borrowed from Bistritz & Bambos (2020) and it includes MPG as a special case.

Figure 1 shows that our independent policy gradient with a large stepsize (green curve) quickly converges to a Nash equilibrium. We note that stepsize $\eta\geq 0.001$ does not provide convergence of the projected stochastic gradient ascent (Leonardos et al., 2022). In contrast, our approach allows large stepsizes for a broad range of initial distributions; see Appendix G for additional details.

Concluding Remarks

We have proposed new independent policy gradient algorithms for learning a Nash equilibrium of Markov potential games when the size of state space and/or the number of players are large. In the exact gradient case, we show that our algorithm finds an $\epsilon$-Nash equilibrium with $O(1/\epsilon^{2})$ iteration complexity. Such iteration complexity does not explicitly depend on the state space size. In the sample-based case, our algorithm works in the function approximation setting, and we prove $O(1/\epsilon^{5})$ sample complexity in a potentially infinitely large state space. This appears to be the first result for learning MPGs with function approximation. Moreover, we identify a class of independent policy gradient algorithms that enjoys last-iterate convergence and sublinear Nash regret for both zero-sum Markov games and Markov cooperative games (a special case of MPGs). This finding sheds light on an open question in the literature on the existence of such an algorithm.

Future directions include extending techniques that offer faster rates for the single-agent policy gradient methods (Lan, 2022; Zhan et al., 2021; Xiao, 2022) to independent multi-agent learning and applying independent policy gradient for other large-scale Markov games.

Acknowledgements

The work of D. Ding and M. R. Jovanović is supported in part by the National Science Foundation under awards ECCS-1708906 and 1809833. The work of C.-Y. Wei is supported by NSF Award IIS-1943607. The work of K. Zhang is supported in part by the Simons-Berkeley Research Fellowship. Part of this work was done while K. Zhang was visiting Simons Institute for the Theory of Computing.

References

Appendix A Algorithms in Section 5 and Section 6

Appendix B Proofs for Section 4

In this section, we provide proofs of Theorem 1 and Theorem 2 in Appendix B.1 and Appendix B.2, respectively.

We first seek to decompose the difference of a potential function $\Phi^{\pi}(\mu)$ at two different policies for any state distribution $\mu$.

We prove (10) by induction on the number of players $N$. In the basic step: $N=2$, the right-hand side of (10) becomes

which equals to the left-hand side: $\Psi^{\pi_{1}^{\prime},\pi_{2}^{\prime}}-\Psi^{\pi_{1},\pi_{2}}$.

Assume the equality (10) holds for $N$ players. We next consider the induction step for $N+1$ players . By subtracting and adding $\Psi^{\pi_{\leq N},\,\pi^{\prime}_{N+1}}$,

In (11), we use the shorthand $\pi^{\prime}_{\leq N}$ and $\pi_{\leq N}$ for $\{\pi^{\prime}_{k}\}_{k\,=\,1}^{N}$ and $\{\pi_{k}\}_{k\,=\,1}^{N}$, respectively. We note that ${\textbf{Diff}_{\leq N}}$ or ${\textbf{Diff}_{N+1}}$ can be viewed as a function for $N$ players if we fix the $(N+1)$th policy. By the induction assumption, for the first term ${\textbf{Diff}_{\leq N}}$,

where we use $\pi_{>j}^{\prime}$ to represent $\{\pi_{k}^{\prime}\}_{k\,=\,j+1}^{N}$.

Adding ${\textbf{Diff}_{N+1}}$ to the last equivalent expression of ${\textbf{Diff}_{\leq N}}$ above yields

where the first equality has a slight abuse of the notation: $\pi_{>j}^{\prime}$ represents $\{\pi_{k}^{\prime}\}_{k\,=\,j+1}^{N+1}$ in the first double sum and $\pi_{>j}^{\prime}$ represents $\{\pi_{k}^{\prime}\}_{k\,=\,j+1}^{N}$ in the second double sum. Therefore, (10) holds for $N+1$ players. The proof is completed by induction. ∎

We apply Lemma 2 to the potential function $\Phi^{\pi}(\mu)$ at two consecutive policies $\pi^{(t+1)}$ and $\pi^{(t)}$ in Algorithm 1, where $\mu$ is an initial state distribution. We use the shorthand $\Phi^{(t)}(\mu)$ for $\Phi^{\pi^{(t)}}(\mu)$, the value of potential function at policy $\pi^{(t)}$.

For MPG (1) with any state distribution $\mu$, the potential function $\Phi^{\pi}(\mu)$ at two consecutive policies $\pi^{(t+1)}$ and $\pi^{(t)}$ in Algorithm 1 satisfies

where $\eta$ is the stepsize, $N$ is the number of players, $A$ is the size of one player’s action space, and $\kappa_{\mu}$ is the distribution mismatch coefficient relative to $\mu$ (see $\kappa_{\mu}$ in Definition 1).

We let $\pi^{\prime}=\pi^{(t+1)}$ and $\pi=\pi^{(t)}$ for brevity. By Lemma 2 with $\Psi^{\pi}=\Phi^{\pi}(\mu)$, it is equivalent to analyze

Bounding $\textbf{Diff}_{\alpha}$. By the property of the potential function $\Phi^{\pi}(\mu)$,

where the second equality is due to Lemma 1 using $\widehat{\pi}_{i}=\pi_{i}^{\prime}$ and $\bar{\pi}_{i}=\pi_{i}$. The optimality of $\pi_{i}^{\prime}=\pi_{i}^{(t+1)}$ in line 4 of Algorithm 1 leads to

Bounding $\textbf{Diff}_{\beta}$. For simplicity, we denote $\widetilde{\pi}_{-ij}$ as the joint policy of players $N\backslash\{i,j\}$ where players $<i$ and $i\sim j$ use $\pi$ and players $>j$ use $\pi^{\prime}$. For each summand in $\textbf{Diff}_{\beta}$,

where $(a)$ is due to the property of the potential function, $(b)$ is due to Lemma 1; for $(c)$, we use Lemma 4, Lemma 20, and the fact that $\sum_{s}d_{\mu}^{\widetilde{\pi}_{-ij},\pi_{i}^{\prime},\pi_{j}^{\prime}}(s)=1$ and $\left\|{\bar{Q}_{i}^{\widetilde{\pi}_{-ij},\,\pi_{i},\,\pi_{j}}(s,\cdot)}\right\|_{\infty}\leq\frac{1}{1-\gamma}$; The last inequality $(d)$ follows a direct result from the optimality of $\pi_{i}^{\prime}=\pi_{i}^{(t+1)}$ given by (14) and $\|\cdot\|\leq\sqrt{A}\|\cdot\|_{\infty}$ and $\|\cdot\|_{1}\leq\sqrt{A}\|\cdot\|$:

We now complete the proof of (i) by combining (12), (15), and (16).

Alternatively, by Lemma 21, we can bound each summand of $\textbf{Diff}_{\beta}$ by

Combining the inequality above with (12) and (15) finishes the proof of (ii). ∎

Suppose $i<j$ for $i,j=1,\ldots,N$. Let $\widetilde{\pi}_{-ij}$ be the policy for all players but $i,j$ and $\pi_{i}$ be the policy for player $i$. For any two policies for player $j$: $\pi_{j}$ and $\pi_{j}^{\prime}$, we have

We note that $\bar{Q}_{i}^{\widetilde{\pi}_{-ij},\,\pi_{i},\,\pi_{j}^{\prime}}(s,\cdot)$ and $\bar{Q}_{i}^{\widetilde{\pi}_{-ij},\,\pi_{i},\,\pi_{j}}(s,\cdot)$ are averaged action value functions for player $i$ using policy $\pi_{i}$, but they have different underlying averaged MDPs because of different policies executed by player $j$. Hence, we can directly apply Lemma 19. Specifically, let $(r,p)$ be the averaged reward and transition functions for player $i$ induced by $(\widetilde{\pi}_{-ij},\pi_{j})$, and $(\widetilde{r},\widetilde{p})$ be those induced by $(\widetilde{\pi}_{-ij},\pi_{j}^{\prime})$. Then,

Application of two inequalities above to Lemma 19 competes the proof. ∎

By the optimality of $\pi_{i}^{(t+1)}$ in line 4 of Algorithm 1,

Hence, if $\eta\leq\frac{1-\gamma}{\sqrt{A}}$, then for any $\pi_{i}^{\prime}\in\Pi_{i}$,

where in $(a)$ we apply the Cauchy-Schwarz inequality and that $\|p-p^{\prime}\|\leq\|p-p^{\prime}\|_{1}\leq 2$ for any two distributions $p$ and $p^{\prime}$; $(b)$ is because of $\|{\bar{Q}_{i}^{(t)}(s,\cdot)}\|\leq\frac{\sqrt{A}}{1-\gamma}$ and $\eta\leq\frac{1-\gamma}{\sqrt{A}}$. Therefore, for any initial distribution $\rho$,

where $(a)$ is due to Lemma 1 and we slightly abuse the notation $i$ to represent $\operatorname*{argmax}_{i}$, in $(b)$ we slightly abuse the notation $\pi_{i}^{\prime}$ to represent $\operatorname*{argmax}_{\pi_{i}^{\prime}}$, in $(c)$ we choose an arbitrary $\nu\in\Delta({\mathcal{S}})$ and use the following inequality:

We apply the Cauchy–Schwarz inequality in $(d)$, and finally we replace $i$ ( $\operatorname*{argmax}_{i}$ in $(a)$) in the last square root term in $(e)$ by the sum over all players.

If we proceed (17) with $\nu=\operatorname*{argmin}_{\nu\,\in\,\Delta({\mathcal{S}})}\max_{\pi\,\in\,\Pi}\|d^{\pi}_{\rho}/\nu\|_{\infty}$, then,

where in $(a)$ we apply the first bound (i) in Lemma 3 (with $\mu=\nu$) and use Definition 2: $\widetilde{\kappa}_{\rho}=\min_{\nu\,\in\,\Delta({\mathcal{S}})}\max_{\pi\,\in\,\Pi}\|d^{\pi}_{\rho}/\nu\|_{\infty}$, and in $(b)$ we use $|\Phi^{\pi}(\nu)-\Phi^{\pi^{\prime}}(\nu)|\leq C_{\Phi}$ for any $\pi,\pi^{\prime}$, and further simplify the bound in $(b)$. We complete the proof for the first bound by taking stepsize $\eta=\frac{(1-\gamma)^{2.5}\sqrt{C_{\Phi}}}{NA\sqrt{T}}$ (by the upper bound of $C_{\Phi}$ given in Lemma 18, the condition $\eta\leq\frac{1-\gamma}{\sqrt{A}}$ is satisfied).

If we proceed (17) with the second bound (ii) in Lemma 3 with the choice of $\eta\leq\frac{(1-\gamma)^{4}}{8\kappa_{\nu}^{3}NA}$, then,

We next discuss two special choices of $\nu$ for proving our bound. First, if $\nu=\rho$, then $\eta\leq\frac{(1-\gamma)^{4}}{8\kappa_{\rho}^{3}NA}$. By letting $\eta=\frac{(1-\gamma)^{4}}{8\kappa_{\rho}^{3}NA}$, the last square root term can be bounded by $O\left(\sqrt{\frac{\kappa_{\rho}^{4}NATC_{\Phi}}{(1-\gamma)^{6}}}\right)$. Second, if $\nu=\frac{1}{S}\mathbf{1}$, the uniform distribution over ${\mathcal{S}}$, then $\kappa_{\nu}\leq\frac{1}{S}$, which allows a valid choice $\eta=\frac{(1-\gamma)^{4}}{8S^{3}NA}\leq\frac{(1-\gamma)^{4}}{8\kappa_{\nu}^{3}NA}$. Hence, we can bound the last square root term by $O\left(\sqrt{\frac{S^{4}NATC_{\Phi}}{(1-\gamma)^{6}}}\right)$. Since $\nu$ is arbitrary, combining these two special choices completes the proof. ∎

B.2 Proof of Theorem 2

We first establish policy improvement regarding the $Q$-function at two consecutive policies $\pi^{(t+1)}$ and $\pi^{(t)}$ in Algorithm 1.

For MPG (1) with identical rewards and an initial state distribution $\rho>0$, if all players independently perform the policy update in Algorithm 1 with stepsize $\eta\leq\frac{1-\gamma}{2N}$, then for any $t$ and any $s$,

where $\eta$ is the stepsize and $N$ is the number of players.

Fixing the time $t$ and the state $s$, we apply Lemma 2 to

where $Q^{(t)}\mathrel{\mathop{:}}=Q^{\pi^{(t)}}$ (recall that $\pi$ is a joint policy of all players). By Lemma 2, for any two policies $\pi^{\prime}$ and $\pi$,

where $\widetilde{\pi}_{-ij}$ is a joint policy of players $N\backslash\{i,j\}$ in which players $<i$ and $i\sim j$ use $\pi$, and players $>j$ use $\pi^{\prime}$. Particularly, we choose $\pi^{\prime}=\pi^{(t+1)}$ and $\pi=\pi^{(t)}$. Thus, we can reduce (18) into

where $(a)$ is due to the optimality condition (14) and $Q^{(t)}(s,a)\leq\frac{1}{1-\gamma}$, $(b)$ is due to $\langle x,y\rangle\leq\frac{\left\|{x}\right\|^{2}+\left\|{y}\right\|^{2}}{2}$, and $(c)$ follows the choice of $\eta\leq\frac{1-\gamma}{2NA}$. ∎

By Lemma 1 and Lemma 5, we have for any $\nu\in\Delta({\mathcal{S}})$,

By the same argument as the proof of Theorem 1,

where in $(a)$ we slightly abuse the notation $i$ to represent $\operatorname*{argmax}_{i}$ as in (17), in $(b)$ we take $\nu=\operatorname*{argmin}_{\nu\in\Delta({\mathcal{S}})}\max_{\pi\,\in\,\Pi}\|d_{\rho}^{\pi}/\nu\|_{\infty}$ and use the definition of $\widetilde{\kappa}_{\rho}$ from Definition 2, and we replace $i$ ($\operatorname*{argmax}_{i}$ in $(a)$) in the last square root term in $(c)$ by the sum over all players, and we apply (19) in $(d)$.

Finally, we complete the proof by taking stepsize $\eta=\frac{1-\gamma}{2NA}$ and using $V^{(T+1)}(\nu)-V^{(1)}(\nu)\leq\frac{1}{1-\gamma}$. ∎

Appendix C Proofs for Section 5

In this section, we provide proofs of Theorem 3 and Theorem 4 in Appendix C.2 and Appendix C.3, respectively.

C.2 Proof of Theorem 3

We apply Lemma 2 to the potential function $\Phi^{\pi}(\rho)$ at two consecutive policies $\pi^{(t+1)}$ and $\pi^{(t)}$ in Algorithm 2, where $\rho$ is the initial state distribution. We use the shorthand $\Phi^{(t)}(\rho)$ for $\Phi^{\pi^{(t)}}(\rho)$, the value of potential function at policy $\pi^{(t)}$. The proof extends Lemma 3 by accounting for the statistical error in Assumption 2.

Let Assumption 1 hold. In Algorithm 2, the potential function $\Phi^{\pi}(\rho)$ at two consecutive policies $\pi^{(t+1)}$ and $\pi^{(t)}$ satisfies

where $\eta$ is the stepsize, $N$ is the number of players, $A$ is the size of one player’s action space, $W$ is the 2-norm bound of $\widehat{w}_{i}^{(t)}$, and $\kappa_{\rho}$ is the distribution mismatch coefficient relative to $\rho$ (see $\kappa_{\rho}$ in Definition 1).

We let $\pi^{\prime}=\pi^{(t+1)}$ and $\pi=\pi^{(t)}$ for brevity. We first express $\Phi^{(t+1)}(\rho)-\Phi^{(t)}(\rho)=\textbf{Diff}_{\alpha}+\textbf{Diff}_{\beta}$, where $\textbf{Diff}_{\alpha}$ and $\textbf{Diff}_{\beta}$ are given as those in (12).

Bounding $\textbf{Diff}_{\alpha}$. By the property of the potential function $\Phi^{\pi}(\rho)$ and Lemma 1,

The optimality of $\pi_{i}^{\prime}=\pi_{i}^{(t+1)}$ in line 14 of Algorithm 2 leads to

where $(a)$ follows the inequality $\langle x,y\rangle\leq\frac{\left\|{x}\right\|^{2}}{2\eta^{\prime}}+\frac{\eta^{\prime}\left\|{y}\right\|^{2}}{2}$ for $\eta^{\prime}>0$, and we choose $\eta^{\prime}=2\eta$ in $(b)$.

Bounding $\textbf{Diff}_{\beta}$. For simplicity, we denote $\widetilde{\pi}_{-ij}$ as the joint policy of players $N\backslash\{i,j\}$ where players $<i$ and $i\sim j$ use $\pi$ and players $>j$ use $\pi^{\prime}$. As done in the proof of Lemma 3, we can bound each summand in $\text{Diff}_{\beta}$ except for the last step from $(c)$ to $(d)$,

where $(d)$ follows a direct result from the optimality of $\pi_{j}^{(t+1)}$ given by (20),

and that $\|\cdot\|_{1}\leq\sqrt{A}\|\cdot\|$. Therefore,

We now complete the proof of (i) by combining (21) and (22) and we also employ that

where $(a)$ follows the definition of $\kappa_{\rho}$ and $(b)$ is the definition of $L_{i}^{(t)}(\widehat{w}_{i}^{(t)})$:

Alternatively, as done in Lemma 3, we can apply Lemma 21 to each summand of $\textbf{Diff}_{\beta}$ and show that

Combining the inequality above with (21) finishes the proof of (ii). ∎

By the optimality of $\pi_{i}^{(t+1)}$ in line 14 of Algorithm 2,

where the last inequality is because of $\|{\widehat{Q}_{i}^{(t)}(s,\cdot)}\|\leq W$ and $\xi\leq\frac{1}{2}$. Hence, if $\eta\leq\frac{1}{W}$, then for any $\pi_{i}^{\prime}\in\Pi_{i}$,

where we apply (24) and the Cauchy-Schwarz inequality in $(a)$, and $(b)$ is because $\|{\widehat{Q}_{i}^{(t)}(s,\cdot)}\|\leq W$ and $\eta\leq\frac{1}{W}$. As done in the proof of Theorem 1, the different steps begin from $(b)$ in (17),

where we slightly abuse the notation $\pi_{i}^{\prime}$ in $(b)$ to represent $\operatorname*{argmax}_{\pi_{i}^{\prime}}$ and $i$ represents $\operatorname*{argmax}_{i}$ as in (17), $(c)$ is due to the definition of the distribution mismatch coefficient (see it in Definition 1):

$(d)$ follows the Cauchy–Schwarz inequality, the inequality $\sqrt{\sum_{i}x_{i}}\leq\sum_{i}\sqrt{x_{i}}$ for any $x_{i}\geq 0$, the Jensen’s inequality, and the definition of $L_{i}^{(t)}(\widehat{w}_{i}^{(t)})$,

If we proceed (25) with the first bound (i) in Lemma 6, then,

where we apply the first bound (i) in Lemma 6 and the telescoping sum for $(a)$, and we use the boundedness of the potential function: $|\Phi^{\pi}-\Phi^{\pi^{\prime}}|\leq C_{\Phi}$ for any $\pi$ and $\pi^{\prime}$, and further simplify the bound in $(f)$ by Assumption Assumption 2. We complete the proof of (i) by taking stepsize $\eta=\frac{(1-\gamma)^{3/2}\sqrt{C_{\Phi}}}{WN\sqrt{AT}}$ and exploration rate $\xi\leq\left(\frac{\kappa_{\rho}^{2}NA\epsilon_{\text{stat}}}{(1-\gamma)^{2}W^{2}}\right)^{\frac{1}{3}}$.

If we proceed (25) with the first bound (ii) in Lemma 6 with the choice of $\eta\leq\frac{(1-\gamma)^{4}}{16\kappa_{\rho}^{3}NA}$, then,

which completes the proof if we choose $\eta=\frac{(1-\gamma)^{4}}{16\kappa_{\rho}^{3}NA}$ and exploration rate $\xi\leq\left(\frac{\kappa_{\rho}^{2}NA\epsilon_{\text{stat}}}{(1-\gamma)^{2}W^{2}}\right)^{\frac{1}{3}}$. ∎

C.3 Proof of Theorem 4

We first establish policy improvement regarding the $Q$-function at two consecutive policies $\pi^{(t+1)}$ and $\pi^{(t)}$ in Algorithm 2.

For MPG (1) with identical rewards and an initial state distribution $\rho>0$, if all players independently perform the policy update in Algorithm 2 with stepsize $\eta\leq\frac{1-\gamma}{2N}$, then for any $t$ and any $s$,

where $\eta$ is the stepsize and $N$ is the number of players,

where $(a)$ is due to the optimality condition (20), the inequality $\langle x,y\rangle\leq\frac{\left\|{x}\right\|^{2}}{2\eta^{\prime}}+\frac{\eta^{\prime}\left\|{y}\right\|^{2}}{2}$ for $\eta^{\prime}>0$, and $Q^{(t)}(s,a)\leq\frac{1}{1-\gamma}$, $(b)$ is due to $\langle x,y\rangle\leq\frac{\left\|{x}\right\|^{2}+\left\|{y}\right\|^{2}}{2}$ and $\eta^{\prime}=2\eta$, and $(c)$ follows the choice of $\eta\leq\frac{1-\gamma}{4N}$. ∎

where $(a)$ follows the definition of $\kappa_{\rho}$ and $(b)$ is the definition of $L_{i}^{(t)}(\widehat{w}_{i}^{(t)})$.

By the same argument as the proof of Theorem 3,

By taking expectation and the Jensen’s inequality,

We complete the proof by taking stepsize $\eta=\frac{1-\gamma}{2NA}$, exploration rate $\xi\leq\left(\frac{\kappa_{\rho}^{2}NA\epsilon_{\text{stat}}}{(1-\gamma)^{2}W^{2}}\right)^{\frac{1}{3}}$, and using $V^{(N+1)}-V^{(1)}\leq\frac{1}{1-\gamma}$. ∎

C.4 Sample complexity

We present our sample complexity guarantees for Algorithm 2 in which the regression problem (7) in each iteration is approximately solved by the stochastic projected gradient descent (38). We measure the sample complexity by the total number of trajectory samples $TK$, where $T$ is the number of iterations and $K$ is the batch size of trajectories.

Assume the setting in Theorem 3 except for Assumption 2. Suppose we compute $\widehat{w}_{i}^{(t)}\mathrel{\mathop{:}}=\frac{1}{K}\sum_{k\,=\,1}^{K}\beta_{k}^{(K)}{w}_{i}^{(k)}$ via a stochastic projected gradient descent (38) with stepsize $\lambda^{(k)}=\frac{2}{2+k}$ and $\beta_{k}^{(K)}=\frac{1/\lambda^{(k)}}{\sum_{r\,=\,1}^{K}1/\lambda^{(r)}}$. Then, if we choose stepsize $\eta=\frac{(1-\gamma)^{3/2}\sqrt{C_{\Phi}}}{WN\sqrt{AT}}$ and exploration rate $\xi=\min\left(\left(\frac{\kappa_{\rho}^{2}ANd}{(1-\gamma)^{4}K}\right)^{\frac{1}{3}},\frac{1}{2}\right)$, then,

Furthermore, if we choose stepsize $\eta=\frac{(1-\gamma)^{4}}{16\kappa_{\rho}^{3}NA}$ and exploration rate $\xi=\min\left(\left(\frac{\kappa_{\rho}^{2}ANd}{(1-\gamma)^{4}K}\right)^{\frac{1}{3}},\frac{1}{2}\right)$, then,

Moreover, their sample complexity guarantees are $TK=O(\frac{1}{\epsilon^{7}})$ or $TK=O(\frac{1}{\epsilon^{5}})$, respectively, for obtaining an $\epsilon$-Nash equilibrium.

By the unbiased estimate in Appendix C.1, the stochastic gradient $\widehat{\nabla}_{i}^{(t)}$ in (38) is also unbiased. We note the variance of the stochastic gradient is bounded by $\frac{1}{(1-\gamma)^{2}}$. By Lemma 23, if we choose $\lambda^{(k)}=\frac{2}{2+k}$ and $\beta_{k}^{(K)}=\frac{1/\lambda^{(k)}}{\sum_{r\,=\,1}^{K}1/\lambda^{(r)}}$, then

where $L_{i}^{(t)}(w_{i}^{(t)})=0$. by Assumption 1. Therefore, substitution of $\epsilon_{\text{stat}}\leq\frac{dW^{2}}{(1-\gamma)^{2}K}$ into Theorem 3 yields desired results.

Finally, we let the upper bound on $\text{Nash-Regret}(T)$ be $\epsilon>0$ and calculate the sample complexity $TK=O(\frac{1}{\epsilon^{7}})$ or $TK=O(\frac{1}{\epsilon^{5}})$, respectively. ∎

Assume the setting in Theorem 4 except for Assumption Assumption 2. Suppose we compute $\widehat{w}_{i}^{(t)}\mathrel{\mathop{:}}=\frac{1}{K}\sum_{k\,=\,1}^{K}\beta_{k}^{(K)}{w}_{i}^{(k)}$ via a stochastic projected gradient descent (38) with stepsize $\lambda^{(k)}=\frac{2}{2+k}$ and $\beta_{k}^{(K)}=\frac{1/\lambda^{(k)}}{\sum_{r\,=\,1}^{K}1/\lambda^{(r)}}$. Then, if we choose stepsize $\eta=\frac{1-\gamma}{WNA\sqrt{T}}$ and exploration rate $\xi=\min\left(\left(\frac{\kappa_{\rho}^{2}AN}{(1-\gamma)^{4}K}\right)^{\frac{1}{3}},\frac{1}{2}\right)$, then,

Moreover, the sample complexity guarantee is $TK=O(\frac{1}{\epsilon^{5}})$ for obtaining an $\epsilon$-Nash equilibrium.

The proof follows the proof steps of Corollary 1 above. ∎

Appendix D Proofs for Section 6

In this section, we prove Theorem 5 and Theorem 6 in Appendix D.1 and Appendix D.2, respectively.

It is convenient to introduce an auxiliary sequence $\{\alpha^{(t,\tau)}\}_{\tau\,=\,0}^{\infty}$ associated with the learning rate $\{\alpha^{(t)}\}_{t\,=\,1}^{\infty}$,

It is straightforward to verify that $\sum_{\tau\,=\,0}^{t-1}\alpha^{(t-1,\tau)}=1$ for $t\geq 1$.

In Algorithm 3, ${\mathcal{V}}_{s}^{(t)}=\sum_{\tau\,=\,1}^{t}\alpha^{(t,\tau)}(x_{s}^{(\tau)})^{\top}{\mathcal{Q}}_{s}^{(\tau)}y_{s}^{(\tau)}$ for all $s,t$.

We prove it by induction. When $t=0$ and $t=1$, it holds trivially by noting that ${\mathcal{V}}_{s}^{(0)}=0$ and $\alpha^{(1,1)}=\alpha^{(1)}$. Assume that it holds for $0,1,\ldots,t-1$. By the update rule for ${\mathcal{V}}_{s}^{(t)}$ in Algorithm 3,

where $(a)$ follows the induction hypothesis and $(b)$ is due to the definition of $\alpha^{(t,\tau)}$. ∎

In Algorithm 3, for every state $s$ and time $t\geq 1$,

where $z_{s}^{(t)}=(x_{s}^{(t)},y_{s}^{(t)})$ and $\bar{z}_{s}^{(t)}=(\bar{x}_{s}^{(t)},\bar{y}_{s}^{(t)})$.

We decompose the difference into three terms:

We next deal with $\textbf{Diff}_{x}$, $\textbf{Diff}_{y}$, and $\textbf{Diff}_{xy}$, separately.