On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning

Introduction

Many real-world sequential decision-making problems involve the strategic interactions of multiple agents in a shared environment, which are commonly addressed with multi-agent reinforcement learning (MARL). Successful applications of MARL include playing the game of Go (Silver et al., 2016), Poker (Brown & Sandholm, 2018), real-time strategy games (Vinyals et al., 2019), autonomous driving (Shalev-Shwartz et al., 2016), and robotics (Kober et al., 2013).

Despite the empirical successes, sample-efficient solutions are still relatively lacking for MARL with a large number of agents, mostly due to the well-known challenge named the curse of multiagents (Jin et al., 2021): The joint action space in a MARL problem is equal to the Cartesian product of the individual action spaces of all agents, which scales exponentially in the number of agents. A typical kind of algorithms that easily fail at this challenge are those using centralized/joint learning (Boutilier, 1996; Claus & Boutilier, 1998). Specifically, centralized learning assumes the existence of a single coordinator who can access the local information of all the agents, and learns policies jointly for all of them. This centralized training (though possibly decentralized execution) approach has become a common practice in empirical MARL (Oliehoek et al., 2008; Foerster et al., 2016; Lowe et al., 2017; Rashid et al., 2018; Son et al., 2019; Mao et al., 2020a). Centralized learning essentially reduces the multi-agent problem to a single-agent one, but unfortunately suffers from the exponential dependence as it usually needs to exhaustively search the joint action space.

Such a computation bottleneck can be partially resolved by allowing communications among the agents and hence distributing the workload to each of them (Kar et al., 2013; Zhang et al., 2018; Dubey & Pentland, 2021). However, communication-based methods instead suffer from the additional communication overheads, which can be unrealistic in some real-world scenarios where communication may be expensive and/or unreliable, such as in unmanned aerial vehicle (UAV) field coverage (Pham et al., 2018).

Given the aforementioned limitations, in this paper, we are interested in a more practical setting: decentralized learningThis setting has been studied under various names in the literature, including individual learning (Leslie & Collins, 2005), decentralized learning (Arslan & Yüksel, 2016), agnostic learning (Tian et al., 2021; Wei et al., 2021), and independent learning (Claus & Boutilier, 1998; Daskalakis et al., 2020). It also belongs to a more general category of teams/games with decentralized information structure (Ho, 1980; Nayyar et al., 2013a, b).. We focus on solutions where each agent can make decisions based on only its local information (e.g., local actions and rewards), and need not communicate with its opponents or be coordinated by any central controller during learning. In fact, in our algorithms, the agents can be completely oblivious to the presence of other agents. Under such weak assumptions, decentralized algorithms are suitable for many practical MARL scenarios (Fudenberg et al., 1998), and do not suffer from the exponential sample & computation complexity. Such algorithms are naturally model-free, as they do not maintain explicit estimates of the transition functions. Compared with model-based algorithms, model-free ones typically enjoy higher time- and space-efficiency, and are more compatible with the modern deep RL architectures (Jin et al., 2018; Zhang et al., 2020b).

In this paper, we investigate the theoretical aspects of decentralized MARL in the non-asymptotic regime. We address the curse of multiagents by presenting sample-efficient model-free algorithms that scale to a large number of agents, and aim to improve the existing algorithms along this line. Our main contributions are summarized as follows.

Contributions. 1) For general-sum Markov games (Section 3), we present algorithms that learn an $\varepsilon$-approximate coarse correlated equilibrium (CCE) in $\widetilde{O}(H^{5}SA_{\max}/\varepsilon^{2})$ episodes, and an $\varepsilon$-approximate correlated equilibrium (CE) in $\widetilde{O}(H^{5}SA_{\max}^{2}/\varepsilon^{2})$ episodes, where $S$ is the number of states, $A_{\max}$ is the size of the largest individual action space, and $H$ is the length of an episode. Our algorithms rely on a novel stage-based V-learning method that significantly simplifies the algorithmic design and analysis of recent works. 2) In the important special case of Markov potential games (MPGs, Section 4), we propose an independent policy gradient algorithm that learns an $\varepsilon$-approximate Nash equilibrium (NE) in $\propto\widetilde{O}(1/\varepsilon^{4.5})$ episodes. Our algorithm utilizes a momentum-based variance reduction technique that can be executed in a decentralized way. 3) We further provide numerical results that corroborate our theoretical findings (Section 5). All our algorithms are decentralized and model-free, and readily generalize to a large number of agents.

Related Work. A common mathematical framework of MARL is stochastic games (Shapley, 1953), which are also referred to as Markov games. Early attempts to learn NE in Markov games include Littman (1994, 2001); Hu & Wellman (2003); Hansen et al. (2013), but they either assume the transition kernel and rewards are known, or only yield asymptotic guarantees. Recently, various sample-efficient methods have been proposed (Wei et al., 2017; Bai & Jin, 2020; Sidford et al., 2020; Xie et al., 2020; Bai et al., 2020; Liu et al., 2021; Zhao et al., 2021; Guo et al., 2021), mostly for learning in two-player zero-sum Markov games. Several works have investigated zero-sum games in a decentralized setting as we consider here (Daskalakis et al., 2020; Tian et al., 2021; Wei et al., 2021; Sayin et al., 2021), but these results do not carry over in any way to general-sum games or MPGs. We refer the reader to Appendix A for a more detailed discussion on these related works.

For general-sum games, Rubinstein (2016) has shown a sample complexity lower bound for learning NE that is exponential in the number of agents. Recently, Liu et al. (2021) has presented a line of results on learning NE, CE, or CCE, but their algorithm is model-based, and suffers from such exponential dependence. Song et al. (2021); Jin et al. (2021); Mao & Başar (2022) have proposed V-learning based methods for learning CCE and/or CE, and our stage-based V-learning significantly simplifies the algorithmic design and analysis along this line. Learning CE and CCE has also been extensively studied in normal-form games with no state transitions (Hart & Mas-Colell, 2000; Cesa-Bianchi & Lugosi, 2006; Blum & Mansour, 2007).

Another line of research (Macua et al., 2018; Mguni et al., 2021) has considered learning in Markov potential games. Arslan & Yüksel (2016) has shown that decentralized Q-learning can converge to NE in weakly acyclic games, which cover potential games as a special case. Their algorithm requires a coordinated exploration phase, and only yields asymptotic guarantees. Two recent works (Zhang et al., 2021; Leonardos et al., 2021) have proposed independent policy gradient methods in MPGs, which are most relevant to ours. We improve their sample complexity dependence on $\varepsilon$ by utilizing decentralized variance reduction, and we do not require the two-timescale framework to coordinate policy evaluation as in Zhang et al. (2021). Fox et al. (2021) has shown that independent natural policy gradient also converges to NE, though only asymptotic convergence has been established. Finally, MPGs have also been studied in Song et al. (2021), but their model-based method is not decentralized, and requires the agents to take turns to learn the policies.

Preliminaries

The agents interact in an unknown environment for $K$ episodes. We assume that the initial state $s_{1}$ of the environment follows a fixed distribution $\rho\in\Delta(\mathcal{S})$. At each time step $h\in[H]$, the agents observe the state $s_{h}\in\mathcal{S}$, and take actions $a_{h,i}\in\mathcal{A}_{i},i\in\mathcal{N}$ simultaneously. Agent $i$ then receives its private reward $r_{h,i}(s_{h},\bm{a}_{h})$, where $\bm{a}_{h}=(a_{h,1},\dots,a_{h,N})$, and the environment transitions to the next state $s_{h+1}\sim P_{h}(\cdot|s_{h},\bm{a}_{h})$. Note that the state transition here is general and not restricted to be deterministic. This makes decentralized learning considerably more challenging, as the agents cannot implicitly coordinate by enumerating/rehearsing all possible states. We focus on the decentralized setting, where each agent only observes the states and its own rewards and actions, but not the rewards or actions of the other agents. In fact, in our algorithms, each agent is completely oblivious of the existence of the others, and does not communicate with each other. This decentralized information structure requires each agent to learn to make decisions based on only its local information.

For ease of notation, we also write $V_{h,i}^{(\pi_{i},\pi_{-i})}(s)$ as $V_{h,i}^{\pi_{i},\pi_{-i}}(s)$, and similarly for $Q_{h,i}^{(\pi_{i},\pi_{-i})}(s,a)$.

Best response and Nash equilibrium. For agent $i$, a policy $\pi_{i}^{\star}$ is a best response to $\pi_{-i}$ for a given initial state $s_{1}$ if $V_{1,i}^{\pi_{i}^{\star},\pi_{-i}}(s_{1})=\sup_{\pi_{i}}V_{1,i}^{\pi_{i},\pi_{-i}}(s_{1})$. A policy profile $\pi=(\pi_{i},\pi_{-i})\in\Pi$ is a Nash equilibrium (NE) if $\pi_{i}$ is a best response to $\pi_{-i}$ for all $i\in\mathcal{N}$. We also have an approximate notion of Nash equilibrium as follows:

($\varepsilon$-approximate Nash equilibrium). For any $\varepsilon>0$, a policy profile $\pi=(\pi_{i},\pi_{-i})\in\Pi$ is an $\varepsilon$-approximate Nash equilibrium for an initial state $s_{1}$ if $V_{1,i}^{\pi_{i},\pi_{-i}}(s_{1})\geq\sup_{\pi_{i^{\prime}}}V_{1,i}^{\pi_{i^{\prime}},\pi_{-i}}(s_{1})-\varepsilon$, $\forall i\in\mathcal{N}$.

Markov potential game. One particular subclass of games that we are interested in is the Markov potential game. Specifically, an episodic Markov game is an MPG if there exists a global potential function $\Phi_{s}:\Pi\rightarrow[0,\Phi_{\max}]$ for every initial state $s\in\mathcal{S}$, such that for any $i\in\mathcal{N}$, any $\pi_{i},\pi_{i^{\prime}}\in\Pi_{i}$, and any $\pi_{-i}\in\Pi_{-i}$,

Our definition of MPG follows Song et al. (2021), which in turn is a variant of the definitions introduced in Macua et al. (2018); Leonardos et al. (2021); Zhang et al. (2021). It follows immediately that MPGs cover Markov teams (Lauer & Riedmiller, 2000) as a special case, a cooperative setting where all agents share the same reward function.

For non-Markov correlated policies, we can still define their value functions at step $h=1$ in a sense similar to (1). A best response $\pi_{i}^{\star}$ with respect to the non-Markov policies $\pi_{-i}$ is a policy (independent of the randomness of $\pi_{-i}$) that maximizes agent $i$’s value at step 1, i.e., $V_{1,i}^{\pi_{i}^{\star},\pi_{-i}}(s_{1})=\sup_{\pi_{i}}V_{1,i}^{\pi_{i},\pi_{-i}}(s_{1})$. The best response to the non-Markov policies of the opponents is not necessarily Markov.

(Coarse) correlated equilibrium. Given the PPAD-hardness of calculating Nash equilibria in general-sum games (Daskalakis et al., 2009), we introduce two relaxed solution concepts, namely coarse correlated equilibrium (CCE) and correlated equilibrium (CE). A CCE states that no agent has the incentive to deviate from a correlated policy $\pi$ by playing a different independent policy.

(CCE). A correlated policy $\pi$ is an $\varepsilon$-approximate coarse correlated equilibrium for an initial state $s_{1}$ if $V_{1,i}^{\pi_{i}^{\star},\pi_{-i}}(s_{1})-V_{1,i}^{\pi}(s_{1})\leq\varepsilon,\forall i\in\mathcal{N}.$

CCE relaxes NE by allowing possible correlations in the policies. Before introducing the definition of CE, we need to first specify the concept of a strategy modification.

(Strategy modification). For agent $i$, a strategy modification $\psi_{i}=\{\psi_{h,i}^{s}:h\in[H],s\in\mathcal{S}\}$ is a set of mappings from agent $i$’s action space to itself, i.e., $\psi_{h,i}^{s}:\mathcal{A}_{i}\rightarrow\mathcal{A}_{i}$.

Given a strategy modification $\psi_{i}$, for any policy $\pi$, step $h$ and state $s$, if $\pi$ selects the joint action $\bm{a}_{h}=(a_{h,1},\dots,a_{h,N})$, then the modified policy $\psi_{i}\diamond\pi$ will select $(a_{h,1},\dots,a_{h,i-1},\psi_{h,i}^{s}(a_{h,i}),a_{h,i+1},\dots,a_{h,N})$. Let $\Psi_{i}$ denote the set of all possible strategy modifications for agent $i$. A CE is a distribution where no agent has the incentive to deviate from a correlated policy $\pi$ by using any strategy modification. It is known that {NE}$\subset${CE}$\subset${CCE} in general-sum games (Nisan et al., 2007).

(CE). A correlated policy $\pi$ is an $\varepsilon$-approximate correlated equilibrium for initial state $s_{1}$ if

Stage-Based V-Learning for General-Sum Markov Games

In this section, we introduce our stage-based V-learning algorithms for learning CCE and CE in general-sum Markov games, and establish their sample complexity guarantees.

The Stage-Based V-Learning for CCE algorithm run by agent $i\in\mathcal{N}$ is presented in Algorithm 1. The agent maintains upper confidence bounds on the value functions to actively explore the unknown environment, and uses a stage-based rule to independently update the value estimates.

For each step-state pair $(h,s)\in[H]\times\mathcal{S}$, we divide the visitations to this pair into multiple stages, where the lengths of the stages increase exponentially at a rate of $(1+1/H)$ (Zhang et al., 2020b). Specifically, we let $e_{1}=H$, and $e_{i+1}=\lfloor(1+1/H)e_{i}\rfloor,i\geq 1$ denote the lengths of the stages, and let the partial sums $\mathcal{L}\stackrel{{\scriptstyle\mathclap{\tiny\mbox{def}}}}{{=}}\{\sum_{i=1}^{j}e_{i}\mid j=1,2,3,\dots\}$ denote the set of ending times of the stages. For each $(h,s)$ pair, we update our optimistic estimates $\overline{V}_{h}(s_{h})$ of the value function at the end of each stage (i.e., when the total number of visitations to $(s,h)$ lies in the set $\mathcal{L}$), using samples only from this single stage (Lines 1-1). This way, our stage-based V-learning ensures that only the most recent $O(1/H)$ fraction of the collected samples are used to calculate $\overline{V}_{h}(s_{h})$, while the first $1-O(1/H)$ fraction is forgotten. Such a stage-based update framework in some sense mimics the celebrated optimistic Q-learning algorithm with a learning rate of $\alpha_{t}=\frac{H+1}{H+t}$ (Jin et al., 2018), which also roughly uses the last $O(1/H)$ fraction of samples for value updates. Stage-based value updates also create a stage-wise stationary environment for the agents, thereby partly alleviating the well-known challenge of non-stationarity in MARL. As a side remark, stage-based Q-learning has also achieved near-optimal regret bounds in single-agent RL (Zhang et al., 2020b).

At each time step $h$ and state $s_{h}$, agent $i$ selects its action $a_{h,i}$ by following a distribution $\mu_{h,i}(\cdot\mid s_{h})$, where $\mu_{h,i}(\cdot\mid s_{h})$ is updated using an adversarial bandit subroutine (Lines 1-1). This is consistent with the recent works under the V-learning framework (Jin et al., 2021; Song et al., 2021; Mao & Başar, 2022), but with a vital improvement: Existing works using the celebrated $\alpha_{t}=\frac{H+1}{H+t}$ learning rate for V-learning inevitably entail a no-weighted-regret bandit problem, because such a time-varying learning rate assigns different weights to each step in the history. A few methods such as weighted follow-the-regularized-leader (Jin et al., 2021; Song et al., 2021) and stabilized online mirror descent (Mao & Başar, 2022) have been recently proposed to address such a challenge, by simultaneously dealing with a changing step size, a weighted regret, and a high-probability guarantee, at the cost of less natural algorithms and more sophisticated analyses. In contrast, our stage-based V-learning assigns uniform weights to each step in the previous stage, and hence leads to a standard no(-average)-regret bandit problem. This allows us to directly plug in any off-the-shelf adversarial bandit algorithm and its analysis to our problem. For example, Algorithm 1 utilizes a simple Exp3 (Auer et al., 2002) subroutine for policy updates, and a standard implicit exploration technique (Neu, 2015) to achieve high-probability guarantees. We provide a more detailed discussion on such an improvement in Remark 1 of Appendix C.

Based on the policy trajectories from Algorithm 1, we construct an output policy profile $\bar{\pi}$ that we will show is a CCE. For any step $h\in[H]$ of an episode $k\in[K]$ and any state $s\in\mathcal{S}$, we let $\mu_{h,i}^{k}(\cdot\mid s)\in\Delta(\mathcal{A}_{i})$ be the distribution prescribed by Algorithm 1 at this step. Let $\check{N}_{h}^{k}(s)$ denote the value of $\check{N}_{h}(s)$ at the beginning of the $k$-th episode. Our construction of the output policy is presented in Algorithm 2, which follows the “certified policies” introduced in Bai et al. (2020). We further let the agents sample the episode indices using a common random seedSuch common randomness is also termed a correlation device, and is standard in decentralized learning (Bernstein et al., 2009; Arabneydi & Mahajan, 2015; Zhang et al., 2019). Note that the correlation device is never used during the learning process to coordinate the exploration, but is simply used to synchronize the selection of the policies after they have been generated. A common random seed is generally considered as a mild assumption and does not break the decentralized paradigm. , and hence the output policy is correlated by nature. Note that our stage-based update rule also simplifies the generating procedure of the output policy: In the original construction of Bai et al. (2020), the certified policy plays a weighted mixture of $\{\mu_{h,i}^{k}(\cdot\mid s):k\in[K]\}$, while in Algorithm 2, we only need to uniformly sample an episode index from the previous stage.

The following theorem presents the sample complexity guarantee of Algorithm 1 for learning CCE in general-sum Markov games. Our sample complexity bound improves over Mao & Başar (2022) and matches those established in Song et al. (2021); Jin et al. (2021), while significantly simplifying their algorithmic design and analysis. The proof is deferred to Appendix C due to space limitations.

(Sample complexity of learning CCE). For any $p\in(0,1]$, set $\iota=\log(2NSA_{\max}KH/p)$, and let the agents run Algorithm 1 for $K$ episodes with $K=O(SA_{\max}H^{5}\iota/\varepsilon^{2})$. Then, with probability at least $1-p$, the output policy $\bar{\pi}$ of Algorithm 2 is an $\varepsilon$-approximate CCE.

2 Learning CE

In this subsection, we aim at learning a more strict solution concept named correlated equilibrium. Our algorithm for learning CE (a complete description presented in Algorithm 6 of Appendix D) also relies on stage-based V-learning, but replaces the no-regret learning subroutine in Algorithm 1 with a no-swap-regret learning algorithm. Our no-swap-regret algorithm follows the generic reduction introduced in Blum & Mansour (2007), and converts a follow-the-regularized-leader (FTRL) algorithm with sublinear external regret to a no-swap-regret algorithm (Jin et al., 2021). A detailed description of such a no-swap-regret FTRL subroutine as well as its regret analysis is presented in Appendix D. Again, due to the stage-based update rule, we can avoid the additional complication of dealing with a weighted swap regret as faced by recent works (Jin et al., 2021; Song et al., 2021). The construction of the output policy $\bar{\pi}$ is the same as Algorithm 2 and thus omitted. The following theorem shows that our sample complexity guarantee for learning CE improves over Song et al. (2021) and matches the best known result in the literature (Jin et al., 2021). The proof of the theorem can also be found in Appendix D.

(Sample complexity of learning CE). For any $p\in(0,1]$, set $\iota=\log(2NSA_{\max}KH/p)$, and let the agents run Algorithm 6 for $K$ episodes with $K=O(SA_{\max}^{2}H^{5}\iota/\varepsilon^{2})$. Then, with probability at least $1-p$, the output policy $\bar{\pi}$ is an $\varepsilon$-approximate CE.

As a final remark, notice that both the V-learning and the no-regret learning components of our algorithms are decentralized, which can be implemented using only the states observed and the local action and reward information, without any communication or central coordination among the agents. In addition, the sample complexity of our algorithms only depend on $A_{\max}$ instead of $\prod_{i=1}^{N}A_{i}$. This allows our methods to easily generalize to a large number of agents.

Learning NE in Markov Potential Games

In this section, we present an algorithm for learning Nash equilibria in decentralized Markov potential games, an important subclass of Markov games. Motivated by Leonardos et al. (2021); Zhang et al. (2021), we utilize a policy gradient method, where each agent independently runs a projected gradient ascent (PGA) algorithm to update their policies. We start from the case where the policy gradients can be calculated exactly (using an infinite number of samples), and then move to the more practical case where the gradients are estimated using finite samples.

(Finite-horizon distribution mismatch coefficient). Given two policies $\pi,\pi^{\prime}\in\Pi$ and an initial state distribution $\rho\in\Delta(\mathcal{S})$, we define

The PGA algorithm updates the policy as follows:

where $\pi_{i}^{(t)}$ is the policy of agent $i$ at the $t$-th iteration, $\text{Proj}_{\Pi_{i}}$ denotes the Euclidean projection onto $\Pi_{i}$, and $\eta>0$ is the step size. Here, we use the direct parameterization of the policy (Agarwal et al., 2021), where $\pi_{h,i}(a\mid s)=\theta_{h,i}^{s,a}$ for some $\theta_{h,i}^{s,a}\geq 0$ and $\sum_{a\in\mathcal{A}_{i}}\theta_{h,i}^{s,a}=1,\forall i\in\mathcal{N},h\in[H],s\in\mathcal{S},a\in\mathcal{A}_{i}$. We assume for now that the policy gradients $\nabla_{\pi_{i}}V_{1,i}^{\pi^{(t)}}(\rho)$ can be calculated exactly, and such an assumption will be relaxed in the next subsection.

Before presenting the analysis of PGA, we first introduce the following definition of an approximate stationary point.

Intuitively, $\pi$ is an approximate stationary point if the function $\Phi_{\rho}$ cannot increase by more than $\varepsilon$ along any direction that lies in the intersection of the policy space and the neighborhood of $\pi$. The following lemma establishes the equivalence between stationary points and NE.

Let $\pi=(\pi_{1},\dots,\pi_{N})$ be an $\varepsilon$-approximate stationary point of the potential function $\Phi_{\rho}$ of an MPG for some $\varepsilon>0$. Then, $\pi$ is a $D\sqrt{SH}\varepsilon$-approximate NE.

The proof of Lemma 1 relies on a gradient domination property that has been shown in single-agent RL (Agarwal et al., 2021). Its multi-agent counterpart has been studied in Zhang et al. (2021); Leonardos et al. (2021), though to the best of our knowledge, a gradient domination property in finite-horizon episodic MDPs/MPGs is still missing in the literature. For completeness, we derive such a result, together with the finite-horizon variants of the policy gradient theorem (Sutton et al., 2000) and performance difference lemma (Kakade & Langford, 2002) in Appendix E. With the above results, we arrive at the convergence guarantee of PGA in the exact gradient case. The proof of Theorem 3 is also deferred to Appendix E.

For any initial state distribution $\rho\in\Delta(\mathcal{S})$, let the agents independently run the projected gradient ascent updates (3) with a step size $\eta=\frac{1}{4NA_{\max}H^{3}}$ for $T=\frac{32NSA_{\max}D^{2}H^{4}\Phi_{\max}}{\varepsilon^{2}}$ iterations. Then, there exists $t\in[T]$, such that $\pi^{(t)}$ is an $\varepsilon$-approximate Nash equilibrium policy profile for the MPG.

2 Finite-Sample Gradient Estimates

When the exact policy gradients are not given, we need to replace $\nabla_{\pi_{i}}V_{1,i}^{\pi^{(t)}}(\rho)$ in (3) with an estimate $\hat{\nabla}_{\pi_{i}}^{(t)}(\pi^{(t)})$ that is calculated from a finite number of samples. For any policy $\pi$ used in the $t$-iteration of PGA, we use a standard REINFORCE (Williams, 1992) gradient estimator

where $R_{i}^{(t)}=\sum_{h=1}^{H}r_{h,i}^{(t)}(s_{h}^{(t)},\bm{a}_{h}^{(t)})$ is the sum of rewards obtained at iteration $t$, and $s_{1}^{(t)}\sim\rho$.

Further, it is mean-squared smooth, i.e., for any $\pi^{\prime(t)}\in\Pi_{i}$,

Each agent now runs (projected) stochastic gradient ascent (SGA) to update its policy, where the gradient estimator is given by (4). In the following, we present the analysis of a generic stochastic gradient descent method that might be of independent interest, and the SGA policy update rule is simply an instantiation of such a generic method.

For an improved sample complexity bound, we utilize a momentum-based stochastic gradient descent (SGD) method with variance reduction (Johnson & Zhang, 2013; Allen-Zhu & Hazan, 2016; Reddi et al., 2016). Our method is a variant of the non-adaptive STOchastic Recursive Momentum (STORM) algorithm proposed in Cutkosky & Orabona (2019), and is formally described in Algorithm 3. It achieves an optimal convergence rate of $O(1/T^{1/3})$, which improves over the standard convergence rate $O(1/T^{1/4})$ of SGD with no variance reduction (e.g., Ghadimi & Lan (2013)). The key advantage of this method is to apply variance reduction in a decentralized way: Compared with other SGD methods with variance reduction (e.g., Allen-Zhu & Hazan (2016); Reddi et al. (2016); Fang et al. (2018)), our momentum-based algorithm does not require a batch of samples to compute checkpoint gradients. The agents hence do not need to coordinate on when to stop updating policies and to collect a batch of samples for a fixed policy profile, a common behavior when using batch-based methods.

The following result characterizes the convergence rate of Algorithm 3, and is a variant of the analysis given in Cutkosky & Orabona (2019). The proofs of Proposition 1 and its supporting lemmas are given in Appendix G.

Suppose Assumption 1 holds, and let $x_{t+1}^{+}=\text{Proj}_{\mathcal{X}}(x_{t}-\eta_{t}\nabla F(x_{t}))$. For any $b>0$, let $k=\frac{b\sigma^{\frac{2}{3}}}{L},c=L^{2}\left(32+1/\left(7b^{3}\right)\right),w=\sigma^{2}\max((4b)^{3},2,(32b+\frac{1}{7b^{2}})^{3}/64)$, and $M=16(F(x_{1})-\inf_{x\in\mathcal{X}}F(x))\allowbreak+\frac{w^{1/3}\sigma^{2}}{2L^{2}k}+\frac{k^{3}c^{2}}{L^{2}}\ln(T+2)$. Then, the following result holds for Algorithm 3:

Since we have shown in Lemma 2 that the conditions in Assumption 1 are satisfied by the potential function $\Phi_{\rho}$ and the REINFORCE policy gradient estimator $\hat{\nabla}_{\pi_{i}}^{(t)}(\pi^{(t)})$, we can let each agent run an instance of Algorithm 3 and the convergence result in Proposition 1 directly applies. This leads us to the following sample complexity guarantee of learning Nash equilibria in MPGs. The proof of Theorem 4 can be found in Appendix F.

For any initial policies and any $\varepsilon>0$, let the agents independently run SGA policy updates (Algorithm 3) for $T$ iterations with $T=O(1/\varepsilon^{4.5})\cdot\text{poly}(N,D,S,A_{\max},H)$. Then, there exists $t\in[T]$, such that $\pi^{(t)}$ is an $\varepsilon$-approximate NE in expectation.

The polynomial sample complexity dependence on $A_{\max}$ is a natural benefit of decentralized learning, while centralized methods would typically have an exponential dependence $\prod_{i=1}^{N}A_{i}$. Such an improvement becomes more significant as the number of agents $N$ increases. Also note that our sample complexity bound in Theorem 4 holds in expectation. To obtain a standard high-probability result that holds with probability $1-p$, one could either apply Markov’s inequality and tolerate an additional $O(1/p)$ factor of sample complexity, or replace our SGA method with one that has high-probability guarantees (Li & Orabona, 2020). For completeness, we present a sample complexity lower bound in the order of $\Omega(1/\varepsilon^{2})\cdot\text{poly}(H,S,A_{\max})$ in Appendix F.2, which is achieved by a reduction to single-agent RL.

Finally, we show that our algorithm can nearly find the globally optimal NE (i.e., the NE that maximizes the potential function, which is guaranteed to exist (Leonardos et al., 2021)) in an important subclass of MPGs named smooth MPGs. Our definition of a $(\lambda,\omega)$-smooth MPG, adapted from the definition of smooth games (Roughgarden, 2009; Radanovic et al., 2019), is formally introduced in Definition 7 of Appendix F.3. Let $\pi^{\star}$ be a policy that maximizes the potential function, i.e., $\Phi_{\rho}(\pi^{\star})=\max_{\pi\in\Pi}\Phi_{\rho}(\pi)$, and let $V^{\star}_{1,i}$ denote the value function for agent $i$ under policy $\pi^{\star}$. The following theorem states that Algorithm 3 can nearly find the globally optimal NE in smooth MPGs. Its proof can be found in Appendix F.3.

In a $(\lambda,\omega)$-smooth MPG, for any initial policies and any $\varepsilon>0$, let the agents independently run SGA policy updates (Algorithm 3) for $T$ iterations with $T=O(1/\varepsilon^{4.5})\cdot\text{poly}(N,D,S,A_{\max},H)$. Then, there exists $t\in[T]$, such that

We remark that our definition of smooth MPGs generalizes that of smooth teams in Radanovic et al. (2019); Mao et al. (2020b), who assume an identical reward function of all the agents. Our approach also significantly improves the two works in that we design natural update rules for all the agents, who play symmetric roles in the self-play setting; the other two works only assign the algorithm to one agent, and have to assume that the policies of the other agent(s) change slowly.

Simulations

We empirically evaluate Algorithm 3 (SGA) on a classic matrix team task (Claus & Boutilier, 1998), and both Algorithms 1 and 3 on two Markov games, namely GoodState and BoxPushing (Seuken & Zilberstein, 2007). Figure 1 illustrates the performances of the algorithms in terms of the collected rewards. Detailed descriptions of the simulations are deferred to Appendix H due to space limitations. Overall, our simulations show more encouraging results than what our theory suggests: For Algorithm 1, the actual policy trajectories converge and achieve high rewards, even though our theoretical guarantees only hold for a “certified” output policy. Further, Algorithm 3 achieves the globally-optimal NE frequently in our simulations, even though our theory does not guarantee so in general. Both algorithms outperform “Independent” learning and in certain cases approach the performance of a “Centralized” oracle.

Concluding Remarks

In this paper, we have studied sample-efficient MARL in decentralized scenarios. We have proposed stage-based V-learning algorithms that learn CCE and CE in general-sum Markov games, and policy gradient algorithms that learn NE in Markov potential games. Our algorithms have improved existing results either through a simplified algorithmic design or a sharper sample complexity bound. An interesting future direction would be to tighten the sample complexity upper and lower bounds established in this paper. The problem of efficiently finding the globally optimal NE in generic MPGs through decentralized learning is also left open.

References

Appendix A Detailed Discussions on Related Work

A common mathematical framework of multi-agent RL is stochastic games (Shapley, 1953), which are also referred to as Markov games. Early attempts to learn Nash equilibria in Markov games include Littman (1994, 2001); Hu & Wellman (2003); Hansen et al. (2013), but they either assume the transition kernel and rewards are known, or only yield asymptotic guarantees. More recently, various sample efficient methods have been proposed (Wei et al., 2017; Bai & Jin, 2020; Sidford et al., 2020; Xie et al., 2020; Bai et al., 2020; Liu et al., 2021; Zhao et al., 2021), mostly for learning in two-player zero-sum Markov games. Most notably, several works have investigated two-player zero-sum games in a decentralized environment: Daskalakis et al. (2020) have shown non-asymptotic convergence guarantees for independent policy gradient methods when the learning rates of the two agents follow a two-timescale rule. Tian et al. (2021) have studied online learning when the actions of the opponents are not observable, and have achieved the first sub-linear regret $\widetilde{O}(K^{\frac{3}{4}})$ in the decentralized setting for $K$ episodes. More recently, Wei et al. (2021) have proposed an Optimistic Gradient Descent Ascent algorithm with a slowly-learning critic, and have shown a strong finite-time last-iterate convergence result in the decentralized/agnostic environment. Overall, these works have mainly focused on two-player zero-sum games. These results do not carry over in any way to general-sum games or MPGs that we consider in this paper.

In general-sum normal-form games, a folklore result is that when the agents independently run no-regret learning algorithms, their empirical frequency of plays converges to the set of coarse correlated equilibria (CCE) of the game (Hart & Mas-Colell, 2000). However, a CCE may suggest that the agents play obviously non-rational strategies. For example, Viossat & Zapechelnyuk (2013) have constructed an example where a CCE assigns positive probabilities only to strictly dominated strategies. On the other hand, given the PPAD completeness of finding a Nash equilibrium, convergence to NE seems hopeless in general. An impossibility result (Hart & Mas-Colell, 2003) has shown that uncoupled no-regret learning does not converge to Nash equilibrium in general, due to the informational constraint that the adjustment in an agent’s strategy does not depend on the reward functions of the others. Hence, convergence to Nash equilibria is guaranteed mostly in games with special reward structures, such as two-player zero-sum games (Freund & Schapire, 1999) and potential games (Kleinberg et al., 2009; Cohen et al., 2017).

For learning in general-sum Markov games, Rubinstein (2016) has shown a sample complexity lower bound for NE that is exponential in the number of agents. Recently, Liu et al. (2021) has presented a line of results on learning NE, CE, or CCE, but their algorithm is model-based, and suffers from such exponential dependence. Song et al. (2021); Jin et al. (2021); Mao & Başar (2022) have proposed V-learning based methods for learning CCE and/or CE, which are similar to the ones that we study here, and avoid the exponential dependence. Nevertheless, our methods significantly simplify their algorithmic design and analysis, by introducing a stage-based V-learning update rule that circumvents their rather complicated no-weighted-regret bandit subroutine.

Another line of research has considered RL in Markov potential games (Macua et al., 2018; Mguni et al., 2021). Arslan & Yüksel (2016) has shown that decentralized Q-learning style algorithms can converge to NE in weakly acyclic games, which cover MPGs as an important special case. Their decentralized setting is similar to ours in that each agent is completely oblivious to the presence of the others. Later, such a method has been improved in Yongacoglu et al. (2019) to achieve team-optimality. However, both of them require a coordinated exploration phase, and only yield asymptotic guarantees. Decentralized learning has also been studied in single-stage weakly acyclic games (Marden et al., 2009b) or potential games (Marden et al., 2009a; Cohen et al., 2017). Two recent works (Zhang et al., 2021; Leonardos et al., 2021) have proposed independent policy gradient methods in MPGs, which are most relevant to ours. We improve their sample complexity dependence on $\varepsilon$ by utilizing a decentralized variance reduction technique, and do not require the two-timescale framework to coordinate policy evaluation as in Zhang et al. (2021). Fox et al. (2021) has shown that independent Natural Policy Gradient also converges to NE in MPGs, though only asymptotic convergence has been established. Finally, MPGs have also been studied in Song et al. (2021), but their model-based method is not decentralized, and requires the agents to take turns to learn the policies.

MARL has also been studied in teams or cooperative games, which can be considered as a subclass of MPGs. Without enforcing a decentralized environment, Boutilier (1996) has proposed to coordinate the agents by letting them take actions in a lexicographic order. In a similar setting, Wang & Sandholm (2002) have studied optimal adaptive learning that converges to the optimal NE in Markov teams. Verbeeck et al. (2002) have presented an independent learning algorithm that achieves a Pareto optimal NE in common interest games with limited communication. These methods critically relied on communications among the agents (beforehand) or observing the teammates’ actions. In contrast, the distributed Q-learning algorithm in Lauer & Riedmiller (2000) is decentralized and coordination-free, which, however, only works for deterministic tasks, and has no non-asymptotic guarantees.

Efficient exploration has also been widely studied in the literature of single-agent RL, see, e.g., Brafman & Tennenholtz (2002); Jaksch et al. (2010); Azar et al. (2017); Jin et al. (2018). For the tabular episodic setting, various methods (Azar et al., 2017; Zhang et al., 2020b; Menard et al., 2021) have achieved the sample complexity of $\widetilde{O}(H^{3}SA/\varepsilon^{2})$, which matches the information-theoretical lower bound. When reduced to the bandit case, decentralized MARL is also related to the cooperative multi-armed bandit (MAB) problem (Lai et al., 2008; Avner & Mannor, 2014), originated from the literature of cognitive radio networks. The difference is that, in cooperative MAB, each agent is essentially interacting with an individual copy of the bandit, with an extra caution of action collisions; in the MARL formulation, the reward function is defined on the Cartesian product of the action spaces, which allows the agents to be coupled in more general forms. A concurrent work (Chang et al., 2021) has studied cooperative multi-player multi-armed bandits with information asymmetry. Nevertheless, (Chang et al., 2021) requires stronger conditions than our decentralized setting as their algorithm relies on playing a predetermined sequence of actions.

Appendix B Technical Lemmas

(Bubeck et al., 2015, Lemma 3.6). Let $f$ be a $\beta$-smooth function with a convex domain $\mathcal{X}$. For any $x\in\mathcal{X}$, let $x^{+}=\text{Proj}_{\mathcal{X}}\left(x-\eta\nabla f(x)\right)$ be a projected gradient descent update with $\eta=\frac{1}{\beta}$, and let $G^{\eta}(x)=\frac{1}{\eta}(x-x^{+})$. Then, the following holds true

The update rule for projected gradient ascent is $x^{+}=x+\eta G^{\eta}(x)$. If $\left\|G^{\eta}(x)\right\|_{2}\leq\varepsilon$, then

The update rule for projected gradient ascent is $\pi^{+}=\pi+\eta G^{\eta}(\pi)$. If $\eta\beta\leq 1$ and $\left\|G^{\eta}(\pi)\right\|_{2}\leq\varepsilon$, then

(Leonardos et al., 2021, Claim C.2). Consider a symmetric block matrix $C$ with $n\times n$ sub-matrices, and let $C_{ij}$ denote the sub-matrix at the $i$-th and $j$-th column. If $\left\|C_{ij}\right\|_{2}\leq L$ for some $L>0$, then it holds that $\left\|C\right\|\leq nL$, i.e., if every sub-matrix of $C$ have a spectral norm of at most $L$, then $C$ has a spectral norm of at most $nL$.

Appendix C Proofs for Section 3.1

Further, for a state $s_{h}^{k}$, let $\check{n}_{h}^{k}$ denote the number of times that state $s_{h}^{k}$ has been visited (at the $h$-th step) in the stage right before the current stage, and let $\check{l}_{h,j}^{k}$ denote the index of the episode that this state was visited the $j$-th time among the $\check{n}_{h}^{k}$ times. For notational convenience, we use $\check{n}$ to denote $\check{n}_{h}^{k}$, and $\check{l}_{j}$ to denote $\check{l}_{h,j}^{k}$, whenever $h$ and $k$ are clear from the context. With the new notations, the update rule in Line 1 of Algorithm 1 can be equivalently expressed as

In the following, we start with an intermediate result, which justifies our choice of the bonus term.

With probability at least $1-\frac{p}{2}$, it holds for all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ that

Notice that $R_{\check{n}}^{\star}$ can be considered as the averaged regret of visiting the state $s$ with respect to the optimal policy in hindsight. Such a regret minimization problem can be handled by an adversarial multi-armed bandit problem, where the loss function at step $j\in[\check{n}]$ is defined as

Algorithm 1 applies the Exp3-IX algorithm (Neu, 2015), which ensures that with probability at least $1-\frac{p}{4NHS}$, it holds for all $k\in[K]$ that

A union bound over all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ completes the proof. ∎

We would like to discuss the alternative of using V-learning with the celebrated learning rate $\alpha_{t}=\frac{H+1}{H+t}$ (Jin et al., 2018) to update $\overline{V}_{h}$ instead of employing stage-based updates. This is the case for several recent works also under the V-learning formulation for MARL (Bai et al., 2020; Jin et al., 2021; Song et al., 2021; Mao & Başar, 2022). Such a learning rate induces an update rule as follows:

where $t$ is the number of times that $s_{h}$ has been visited, and $\beta_{t}$ is some bonus term. In this way, $\overline{V}_{h,i}(s_{h})$ is updated every time the state $s_{h}$ is visited. With such a learning rate, the update rule (7) of $\overline{V}_{h,i}$ can be equivalently expressed as

where $k^{j}$ is the index of the episode such that $s_{h}$ is visited the $j$-th time. The weights $\alpha_{t}^{j}$ are given by

Compared with stage-based updates (6), we now need to upper bound a regret term of the following form:

Notice that the above definition of regret induces a adversarial bandit problem with a time-varying weighted regret, where the loss at time $j$ is assigned a weight $\alpha_{t}^{j}$. As $t$ varies, the weight $\alpha_{t}^{j}$ assigned to the same step $j$ also changes over time. These weights also cannot be pre-computed, because it relies on knowing the total number of times that a certain state $s_{h}$ is visited during the entire horizon, which is impossible before seeing the output of the algorithm. To address such an additional challenge, Bai et al. (2020) proposed a Follow-the-Regularized-Leader (FTRL) algorithm that simultaneously achieves with a changing step size, a weighted regret, and a high-probability guarantee, which inevitably leads to a more delicate analysis. In contrast, we have shown in (6) that our stage-based update rule leads to an adversarial bandit problem with a simple averaged regret. In our approach, it suffices to plug in any existing adversarial bandit solution with a high-probability regret bound, such as the Exp3-IX method that we used in Algorithm 1. Therefore, our stage-based update significantly simplifies both the algorithmic design and the analysis of V-learning in MARL.

Based on the trajectory of the distributions $\{\mu_{h,i}^{k}:i\in\mathcal{N},h\in[H],k\in[K]\}$ specified by Algorithm 1, we construct a correlated policy $\bar{\pi}_{h}^{k}$ for each $(h,k)\in[H]\times[K]$. Our construction of the correlated policies, largely inspired by the “certified policies” (Bai et al., 2020) for learning in two-player zero-sum games, is formally presented in Algorithm 4. We further define an output policy $\bar{\pi}$ that first uniformly samples an index $k$ from $[K]$, and then proceed with $\bar{\pi}_{1}^{k}$. A more formal description of $\bar{\pi}$ has been given in Algorithm 2. By construction of the correlated policies $\bar{\pi}_{h}^{k}$, we know that for any $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H+1]\times[K]$, the corresponding value function can be written recursively as follows:

and $V_{h,i}^{\bar{\pi}_{h}^{k}}(s)=0$ if $h=H+1$ or $k$ is in the first stage of the corresponding $(h,s)$ pair. We also immediately obtain that

Only for analytical purposes, we introduce two new notations $\underline{V}$ and $\undertilde{V}$ that serve as lower confidence bounds of the value estimates. Specifically, for any $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H+1]\times[K]$, we define $\underline{V}_{h,i}^{k}(s)=\undertilde{V}_{h,i}^{k}(s)=0$ if $h=H+1$ or $k$ is in the first stage of the $(h,s)$ pair, and

Notice that these two notations are only introduced for ease of analysis, and the agents need not explicitly maintain such values during the learning process. Further, recall that $V_{h,i}^{\star,\bar{\pi}_{h,-i}^{k}}(s)$ is agent $i$’s best response value against its opponents’ policy $\bar{\pi}_{h,-i}^{k}$. Our next lemma shows that $\overline{V}_{h,i}^{k}(s)$ and $\underline{V}_{h,i}^{k}(s)$ are indeed valid upper and lower bounds of $V_{h,i}^{\star,\bar{\pi}_{h,-i}^{k}}(s)$ and $V_{h,i}^{\bar{\pi}_{h}^{k}}(s)$, respectively.

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

Consider a fixed $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$. The desired result clearly holds for any state $s$ that is in its first stage, due to our initialization of $\overline{V}_{h,i}^{k}(s)$ and $\underline{V}_{h,i}^{k}(s)$ for this special case. In the following, we only need to focus on the case where $\overline{V}_{h,i}(s)$ and $\underline{V}_{h,i}^{k}(s)$ have been updated at least once at the given state $s$ before the $k$-th episode.

By the definition of $V_{h}^{\star,\bar{\nu}_{h}^{k}}(s)$, it holds with probability at least $1-\frac{p}{2NSKH}$ that

where the second step is by the induction hypothesis, the third step holds due to Lemma 7, and the last step is by the definition of $b_{\check{n}}$.

Combining the two cases and applying a union bound over all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ complete the proof of the first inequality.

Next, we prove the second inequality in the statement of the lemma. Notice that it suffices to show $\undertilde{V}_{h,i}^{k}(s)\leq V_{h,i}^{\bar{\pi}_{h}^{k}}(s)$ because $\underline{V}_{h,i}^{k}(s)=\max\{\undertilde{V}_{h,i}^{k}(s),0\}$. Our proof again relies on induction on $k\in[K]$. Similar to the proof of the first inequality, the claim apparently holds for $k=1$, and we consider the following two cases for each step $h\in[H]$ and $s\in\mathcal{S}$.

Case 1: The value of $\undertilde{V}_{h,i}(s)$ has just changed in (the end of) episode $k-1$. In this case,

By the definition of $V_{h,i}^{\bar{\pi}_{h}^{k}}(s)$, it holds with probability at least $1-\frac{p}{2NSKH}$ that

where the second step is by the induction hypothesis, the third step holds due to the Azuma-Hoeffding inequality, and the last step is by the definition of $b_{\check{n}}$.

Case 2: The value of $\undertilde{V}_{h,i}(s)$ has not changed in (the end of) episode $k-1$. Since we have excluded the case that $\undertilde{V}_{h,i}$ has never been updated, we are guaranteed that there exists an episode $j$ such that $\undertilde{V}_{h,i}(s)$ has changed in the end of episode $j-1$ most recently. In this case, we know that indices $j$ and $k$ belong to the same stage, and $\undertilde{V}_{h,i}^{k}(s)=\undertilde{V}_{h,i}^{k-1}(s)=\dots=\undertilde{V}_{h,i}^{j}(s)\leq V_{h,i}^{\bar{\pi}_{h}^{j}}(s)$, where the last step is by the induction hypothesis. Finally, observe that by our definition, the value of $V_{h,i}^{\bar{\pi}_{h}^{j}}(s)$ is a constant for all episode indices $j$ that belong to the same stage. Since we know that episode $j$ and episode $k$ lie in the same stage, we can conclude that $V_{h,i}^{\bar{\pi}_{h}^{k}}(s)=V_{h,i}^{\bar{\pi}_{h}^{j}}(s)\geq\undertilde{V}_{h,i}^{k}(s)$.

Again, combining the two cases and applying a union bound over all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ complete the proof. ∎

The following result shows that the agents have no incentive to deviate from the correlated policy $\bar{\pi}$, up to a regret term of the order $\widetilde{O}(\sqrt{H^{5}SA_{\max}/K})$.

For any $p\in(0,1]$, let $\iota=\log(2NSA_{\max}KH/p)$. Suppose $K\geq\frac{SH}{A_{\max}\iota}$, with probability at least $1-p$, it holds that

We first recall the definitions of several notations and define a few new ones. For a state $s_{h}^{k}$, recall that $\check{n}_{h}^{k}$ denotes the number of visits to the state $s_{h}^{k}$ (at the $h$-th step) in the stage right before the current stage, and $\check{l}_{h,j}^{k}$ denotes the $j$-th episode among the $\check{n}_{h}^{k}$ episodes. Similarly, let $n_{h}^{k}$ be the total number of episodes that this state has been visited prior to the current stage, and let $l_{h,j}^{k}$ denote the index of the episode that this state was visited the $j$-th time among the total $n_{h}^{k}$ times. For simplicity, we use $l_{j}$ and $\check{l}_{j}$ to denote $l_{h,j}^{k}$ and $\check{l}_{h,j}^{k}$, and $\check{n}$ to denote $\check{n}_{h}^{k}$, whenever $h$ and $k$ are clear from the context.

We hence only need to upper bound $\frac{1}{K}\sum_{k=1}^{K}(\overline{V}_{1,i}^{k}(s_{1})-\underline{V}_{1,i}^{k}(s_{1}))$. For a fixed agent $i\in\mathcal{N}$, we define the following notation:

The main idea of the subsequent proof is to upper bound $\sum_{k=1}^{K}\delta_{h}^{k}$ by the next step $\sum_{k=1}^{K}\delta_{h+1}^{k}$, and then obtain a recursive formula. From the update rule of $\overline{V}_{h,i}^{k}(s_{h}^{k})$ in (5), we know that

Further recalling the definition of $\underline{V}_{h,i}^{k}(s_{h}^{k})$, we have

Combining (13) and (14) leads to the following upper bound of the second term in (12):

So far, we have obtained the following upper bound:

Iterating the above inequality over $h=H,H-1,\dots,1$ leads to

where we used the fact that $(1+\frac{1}{H})^{H}\leq e$. In the following, we analyze the bonus term $b_{\check{n}_{h}^{k}}$ more carefully. Recall our definitions that $e_{1}=H,\ e_{i+1}=\left\lfloor(1+\frac{1}{H})e_{i}\right\rfloor,i\geq 1$, and $b_{\check{n}}=6\sqrt{H^{2}A_{i}\iota/\check{n}}$. For any $h\in[H]$,

where in the second step we again used the formula of the sum of a geometric sequence. Finally, using the fact that $\sum_{s\in\mathcal{S}}w(s)=K$ and applying the Cauchy-Schwartz inequality, we have

In the case when $K$ is large enough, such that $K\geq\frac{SH}{A_{i}\iota}$, the second term becomes dominant, and we obtain the desired result:

This completes the proof of the theorem. ∎

An immediate corollary is that we obtain an $\varepsilon$-approximate CCE when $\sqrt{SA_{\max}H^{5}\iota/K}\leq\varepsilon$, which is Theorem 1 in the main text.

Theorem 1. (Sample complexity of learning CCE). For any $p\in(0,1]$, set $\iota=\log(2NSA_{\max}KH/p)$, and let the agents run Algorithm 1 for $K$ episodes with $K=O(SA_{\max}H^{5}\iota/\varepsilon^{2})$. Then, with probability at least $1-p$, the output policy $\bar{\pi}$ constitutes an $\varepsilon$-approximate coarse correlated equilibrium.

Appendix D Proofs for Section 3.2

We first present a no-swap-regret learning algorithm for the adversarial bandit problem, which serves as an important subroutine to achieve correlated equilibria in Markov games. We consider a standard adversarial bandit problem that lasts for $T$ time steps. The agent has an action space of $\mathcal{A}=\{1,\dots,A\}$. At each time step $t\in[T]$, the agent specifies a distribution $p_{t}\in\Delta(\mathcal{A})$ over the action space, and takes an action $a_{t}$ according to $p_{t}$. The adversary then selects a loss vector $l_{t}\in^{A}$, where $l_{t}(a)\in$ denotes the loss of action $a$ at time $t$. We consider partial information (bandit) feedback, where the agent only receives the reward associated with the selected action $a_{t}$. The external regret measures the difference between the cumulative reward that an algorithm obtains and that of the best fixed action in hindsight. Specifically,

The swap regret, instead, measures the difference between the cumulative reward of an algorithm and the cumulative reward that could be achieved by swapping multiple pairs of actions of the algorithm. To be more specific, we define a strategy modification $F:\mathcal{A}\rightarrow\mathcal{A}$ to be a mapping from the action space to itself. For any action selection distribution $p$, we let $F\diamond p$ be the swapped distribution that takes action $a\in\mathcal{A}$ with probability $\sum_{a^{\prime}\in\mathcal{A},F(a^{\prime})=a}p(a^{\prime})$. The swap regretThis is a modified version of the swap regret used in Blum & Mansour (2007), which is defined as $R_{\text{swap}}(T)=\max_{F:\mathcal{A}\rightarrow\mathcal{A}}\sum_{t=1}^{T}\left(l_{t}(a_{t})-l_{t}(F(a_{t}))\right)$. is then defined as

where recall that $p_{t}$ is the distribution that the algorithm specifies at time $t$ for action selection.

We follow the generic reduction introduced in Blum & Mansour (2007), and convert a Follow-the-Regularized-Leader algorithm with sublinear external regret to a no-swap-regret algorithm (Jin et al., 2021). The resulting algorithm is presented as Algorithm 5. The following lemma shows that Algorithm 5 is indeed a no-swap-regret learning algorithm.

It is worth noting that Jin et al. (2021) presented a more general analysis with an anytime weighted swap regret guarantee. Such complication can be avoided in our algorithm, as our stage-based learning approach only entails a simple averaged swap regret analysis.

The complete Stage-Based V-Learning algorithm for CE is presented in Algorithm 6. In the following analysis, we follow the same notations as have been used in the CCE analysis. We again start with the following lemma that justifies our choice of the bonus term.

With probability at least $1-\frac{p}{2}$, it holds for all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ that

Notice that $R_{\text{swap}}(\check{n})$ can be considered as the swap regret of an adversarial bandit problem at state $s$, where the loss function at step $j\in[\check{n}]$ is defined as

Such a problem can be addressed by a no-swap-regret learning algorithm as presented in Algorithm 5. Applying Lemma 9, we obtain that with probability at least $1-\frac{p}{4NHS}$, it holds for all $k\in[K]$ that

A union bound over all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ completes the proof. ∎

We again define the notations $\bar{\pi}_{h}^{k},\bar{\pi},V_{h,i}^{\bar{\pi}_{h}^{k}},\underline{V}_{h,i}^{k}$, and $\undertilde{V}_{h,i}^{k}(s)$ in the same sense as in Appendix C. The next lemma shows that $\overline{V}_{h,i}^{k}(s)$ and $\underline{V}_{h,i}^{k}(s)$ are valid upper and lower bounds.

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

Consider a fixed $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$. The desired result clearly holds for any state $s$ that is in its first stage, due to our initialization of $\overline{V}_{h,i}^{k}(s)$ and $\underline{V}_{h,i}^{k}(s)$ for this special case. In the following, we only need to focus on the case where $\overline{V}_{h,i}(s)$ and $\underline{V}_{h,i}^{k}(s)$ have been updated at least once at the given state $s$ before the $k$-th episode.

By the definition of $\max_{\psi_{i}\in\Psi_{i}}V_{h,i}^{\psi_{i}\diamond\bar{\pi}_{h}^{k}}(s)$, it holds with probability at least $1-\frac{p}{2NSKH}$ that

where the second step is by the induction hypothesis, the third step holds due to Lemma 10, and the last step is by the definition of $b_{\check{n}}$.

Combining the two cases and applying a union bound over all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ complete the proof of the first inequality.

Next, we prove the second inequality in the statement of the lemma. Notice that it suffices to show $\undertilde{V}_{h,i}^{k}(s)\leq V_{h,i}^{\bar{\pi}_{h}^{k}}(s)$ because $\underline{V}_{h,i}^{k}(s)=\max\{\undertilde{V}_{h,i}^{k}(s),0\}$. Our proof again relies on induction on $k\in[K]$. Similar to the proof of the first inequality, the claim apparently holds for $k=1$, and we consider the following two cases for each step $h\in[H]$ and $s\in\mathcal{S}$.

Case 1: The value of $\undertilde{V}_{h,i}(s)$ has just changed in (the end of) episode $k-1$. In this case,

By the definition of $V_{h,i}^{\bar{\pi}_{h}^{k}}(s)$, it holds with probability at least $1-\frac{p}{2NSKH}$ that

where the second step is by the induction hypothesis, the third step holds due to the Azuma-Hoeffding inequality, and the last step is by the definition of $b_{\check{n}}$.

Case 2: The value of $\undertilde{V}_{h,i}(s)$ has not changed in (the end of) episode $k-1$. Since we have excluded the case that $\undertilde{V}_{h,i}$ has never been updated, we are guaranteed that there exists an episode $j$ such that $\undertilde{V}_{h,i}(s)$ has changed in the end of episode $j-1$ most recently. In this case, we know that indices $j$ and $k$ belong to the same stage, and $\undertilde{V}_{h,i}^{k}(s)=\undertilde{V}_{h,i}^{k-1}(s)=\dots=\undertilde{V}_{h,i}^{j}(s)\leq V_{h,i}^{\bar{\pi}_{h}^{j}}(s)$, where the last step is by the induction hypothesis. Finally, observe that by our definition, the value of $V_{h,i}^{\bar{\pi}_{h}^{j}}(s)$ is a constant for all episode indices $j$ that belong to the same stage. Since we know that episode $j$ and episode $k$ lie in the same stage, we can conclude that $V_{h,i}^{\bar{\pi}_{h}^{k}}(s)=V_{h,i}^{\bar{\pi}_{h}^{j}}(s)\geq\undertilde{V}_{h,i}^{k}(s)$.

Again, combining the two cases and applying a union bound over all $(i,s,h,k)\in\mathcal{N}\times\mathcal{S}\times[H]\times[K]$ complete the proof. ∎

For any $p\in(0,1]$, let $\iota=\log(2NSA_{\max}KH/p)$. Suppose $K\geq\frac{SH}{A_{\max}^{2}\iota}$. With probability at least $1-p$,

The proof follows a similar procedure as the proof of Theorem 6. From Lemma 11, we know that

We hence only need to upper bound $\frac{1}{K}\sum_{k=1}^{K}(\overline{V}_{1,i}^{k}(s_{1})-\underline{V}_{1,i}^{k}(s_{1}))$. For a fixed agent $i\in\mathcal{N}$, we define the following notation:

The main idea of the subsequent proof is to upper bound $\sum_{k=1}^{K}\delta_{h}^{k}$ by the next step $\sum_{k=1}^{K}\delta_{h+1}^{k}$, and then obtain a recursive formula. From the update rule of $\overline{V}_{h,i}^{k}(s_{h}^{k})$ in (5), we know that

Further recalling the definition of $\underline{V}_{h,i}^{k}(s_{h}^{k})$, we have

Combining (23) and (24) leads to the following upper bound of the second term in (22):

So far, we have obtained the following upper bound:

Iterating the above inequality over $h=H,H-1,\dots,1$ leads to

where we used the fact that $(1+\frac{1}{H})^{H}\leq e$. In the following, we analyze the bonus term $b_{\check{n}_{h}^{k}}$ more carefully. Recall our definitions that $e_{1}=H,\ e_{i+1}=\left\lfloor(1+\frac{1}{H})e_{i}\right\rfloor,i\geq 1$, and $b_{\check{n}}=11\sqrt{H^{2}A_{i}^{2}\iota/\check{n}}$. For any $h\in[H]$,

where in the second step we again used the formula of the sum of a geometric sequence. Finally, using the fact that $\sum_{s\in\mathcal{S}}w(s)=K$ and applying the Cauchy-Schwartz inequality, we have

In the case when $K$ is large enough, such that $K\geq\frac{SH}{A_{i}^{2}\iota}$, the second term becomes dominant, and we obtain the desired result:

This completes the proof of the theorem. ∎

An immediate corollary is that we obtain an $\varepsilon$-approximate CE when $\sqrt{SA_{\max}^{2}H^{5}\iota/K}\leq\varepsilon$, which is Theorem 2 in the main text.

Theorem 2. (Sample complexity of learning CE). For any $p\in(0,1]$, set $\iota=\log(2NSA_{\max}KH/p)$, and let the agents run Algorithm 6 for $K$ episodes with $K=O(SA_{\max}^{2}H^{5}\iota/\varepsilon^{2})$. Then, with probability at least $1-p$, the output policy $\bar{\pi}$ constitutes an $\varepsilon$-approximate correlated equilibrium.

Appendix E Proofs for Section 4.1

We start with a multi-agent variant of the performance difference lemma (Kakade & Langford, 2002) in the finite-horizon setting.

(Performance difference lemma). For any policy $\pi=(\pi_{i},\pi_{-i})\in\Pi$ and $\pi^{\prime}=(\pi_{i}^{\prime},\pi_{-i})\in\Pi$, it holds for any $i\in\mathcal{N}$ that

where $A_{h,i}^{\pi^{\prime}}(s_{h},\bm{a}_{h})=Q_{h,i}^{\pi^{\prime}}(s_{h},\bm{a}_{h})-V_{h,i}^{\pi^{\prime}}(s_{h})$ is the advantage function.

where $(a)$ uses the tower property of conditional expectation, and $(b)$ is due to the definition of the advantage function and the fact that $Q_{H,i}^{\pi^{\prime}}(s_{h},\bm{a}_{H})=r_{H}(s_{H},\bm{a}_{H})$. ∎

In the following, we reproduce a variant of the policy gradient theorem (Sutton et al., 2000) in the setting of finite-horizon MPGs.

(Policy gradient theorem). For any $i\in\mathcal{N}$, it holds that

For any fixed initial state $s_{1}\in\mathcal{S}$, differentiating both sides of the Bellman equation leads to

From the linearity of expectation, we know that for any state distribution $\rho$,

Applying the above equation recursively, we obtain that

This completes the proof of the policy gradient theorem in the finite-horizon case. ∎

With direct parameterization, we can further derive from the policy gradient theorem that for any $h\in[H],s\in\mathcal{S},a\in\mathcal{A}_{i}$,

In the following, we state and prove a finite-horizon variant of the gradient domination property, which has been shown in single-agent policy gradient methods (Agarwal et al., 2021) and infinite-horizon discounted MPGs (Zhang et al., 2021; Leonardos et al., 2021).

(Gradient domination). For any policy $\pi=(\pi_{i},\pi_{-i})\in\Pi$ in a Markov potential game, let $\pi_{i}^{\star}$ be agent $i$’s best response to $\pi_{-i}$, and let $\pi^{\star}=(\pi_{i}^{\star},\pi_{-i})$. With direct policy parameterization, for any initial state distribution $\rho\in\Delta(\mathcal{S})$, it holds that

where the $L^{\infty}$ norm takes the maximum over $[H]\times\mathcal{S}$.

From the performance difference lemma (Lemma 12), we know that

where in the last step we used the fact that

where $(a)$ again uses (29), and $(b)$ relies on the fact that

Equality $(c)$ is due to the policy gradient theorem with direct parameterization (28). Finally, putting everything together, we conclude that

where the $L^{\infty}$ norm takes the maximum over the space $[H]\times\mathcal{S}$. This completes the proof of the gradient domination property. ∎

We are now ready to prove Lemma 1 from Section 4, which states that a stationary point of the potential function implies a NE policy.

Lemma 1. Let $\pi=(\pi_{1},\dots,\pi_{N})$ be an $\varepsilon$-approximate stationary point of the potential function $\Phi_{\rho}$ of an MPG for some $\varepsilon>0$. Then, $\pi$ is a $D\sqrt{SH}\varepsilon$-approximate Nash equilibrium policy profile for this MPG.

For any $i\in\mathcal{N}$, since $\pi=(\pi_{i},\pi_{-i})$ is an $\varepsilon$-approximate stationary point of $\Phi_{\rho}$, we know from Definition 6 that

where we used the fact that $\left\|\frac{\pi_{i}^{\star}-\pi_{i}}{\sqrt{SH}}\right\|_{2}^{2}\leq 1$. Let $\pi^{\star}=(\pi_{i}^{\star},\pi_{-i})$. From the definition of the potential function, we obtain that $\nabla_{\pi_{i}}V_{1,i}^{\pi}(\rho)=\nabla_{\pi_{i}}\Phi_{\rho}(\pi)$. Further, the linearity of expectation immediately implies that $\Phi_{\rho}(\pi_{i},\pi_{-i})-\Phi_{\rho}(\pi_{i^{\prime}},\pi_{-i})=V_{1,i}^{\pi_{i},\pi_{-i}}(\rho)-V_{1,i}^{\pi_{i^{\prime}},\pi_{-i}}(\rho).$ By the gradient domination property (Lemma 14), we know that