TAPE: Leveraging Agent Topology for Cooperative Multi-Agent Policy Gradient

Recent years has witnessed dramatic progress of reinforcement learning (RL) and multi-agent reinforcement learning (MARL) in real life applications, such as unmanned vehicles (Liu et al. 2022), traffic signal control (Noaeen et al. 2022) and on-demand delivery (Wang et al. 2023). Taking advantage of the centralized training decentralized execution (CTDE) (Oliehoek, Spaan, and Vlassis 2008; Kraemer and Banerjee 2016) paradigm, current cooperative MARL methods (Du et al. 2023; Wang et al. 2020a, b; Peng et al. 2021; Zhang et al. 2021; Zhou, Lan, and Aggarwal 2022) adopt value function factorization or a centralized critic to provide centralized learning signals to promote cooperation and achieve implicit or explicit credit assignment. Multi-agent policy gradient (MAPG) (Lowe et al. 2017; Foerster et al. 2018; Zhou et al. 2020; Zhang et al. 2021; Zhou, Lan, and Aggarwal 2022; Du et al. 2019) applies RL policy gradient techniques (Sutton and Barto 2018; Silver et al. 2014; Lillicrap et al. 2015) to the multi-agent context. In CTDE, MAPG methods adopt centralized critics or value-mixing networks (Rashid et al. 2020b, a; Wang et al. 2020a) for individual critics so that agents can directly update their policies to maximize the global $Q$ value $Q^{\bm{\pi}}_{tot}$ in their policy gradient. As a result, agents cooperate more effectively and obtain better expected team rewards.

The centralized critic approach has an inherent problem known as centralized-decentralized mismatch (CDM) (Wang et al. 2020c; Chen et al. 2022). The CDM issue refers to sub-optimal, or explorative actions of some agents negatively affecting policy learning of others, causing catastrophic miscoordination. The CDM issue arises because sub-optimal or explorative actions may lead to a small or negative centralized global $Q$ value $Q^{\bm{\pi}}_{tot}$, even if other agents take good or optimal actions. In turn, the small $Q^{\bm{\pi}}_{tot}$ will make the other agents mistake their good actions as bad ones and interrupt their policy learning. The Decomposed Off-Policy (DOP) approach (Wang et al. 2020c) deals with sub-optimal actions of other agents by linearly decomposed individual critics, which ignore the other agents’ actions in the policy gradient. But the use of individual critics severely limits agent cooperation.

We give an example to illustrate the issue of learning with centralised critics and individual critics respectively. Consider an one-step matrix game with two agents $A$, $B$ where each agent has two actions $a_{0},a_{1}$. Reward $R(a_{0},a_{0})=2,R(a_{0},a_{1})=-4,R(a_{1},a_{0})=-1$ and $R(a_{1},a_{1})=0$. Assume agent $A$ has a near-optimal policy with probability $\epsilon$ choosing non-optimal action $a_{1}$ and is using the COMA centralized critic (Foerster et al. 2018) for policy learning. If agent $A$ takes optimal action $a_{0}$ and $B$ takes the non-optimal action $a_{1}$, agent $A$’s counterfactual advantage $Adv_{A}(a_{0},a_{1})=Q_{tot}^{\bm{\pi}}(a_{0},a_{1})-\left[\left(1-\epsilon\right)Q_{tot}^{\bm{\pi}}(a_{0},a_{1})+\epsilon Q_{tot}^{\bm{\pi}}(a_{1},a_{1})\right]=-4\epsilon<0$, which means agent $A$ will mistakenly think $a_{0}$ as a bad action. Consequently, the sub-optimal action of agent $B$ causes agent $A$ to decrease the probability of taking optimal action $a_{0}$ and deviate from the optimal policy. Similar problems will occur with other centralized critics. If we employ individual critics, however, cooperation will be limited. Assume both agents’ policies are initialized as random policies and learning with individual critics. For agent $A$, $Q_{A}(a_{0})=\mathbb{E}_{a_{B}\sim\pi_{B}}[Q^{\bm{\pi}}_{tot}(a_{0},a_{B})]=0.5\times 2-0.5\times 4=-1$. Similarly, we can get $Q_{A}(a_{1})=-0.5,\ Q_{B}(a_{0})=0.5,\ Q_{B}(a_{1})=-2$. The post-update joint-policy will be $(a_{1},a_{0})$ and receive reward $-1$, which is clearly sub-optimal.

In this paper, we aims to alleviate the CDM issue without hindering agent’s cooperation capacity by proposing an agent topology framework to describe the relationships between agents’ policy updates. Under the agent topology framework, agents connected in the topology consider and maximize each other’s utilities. Thus, the shared objective makes each individual agent forms a coalition with its connected neighbors. Agents only consider the utilities of agents in the same coalition, facilitating in-coalition cooperation and avoiding influence of out-of-coalition agents. Based on the agent topology, we propose Topology-based multi-Agent Policy gradiEnt (TAPE) for both stochastic and deterministic MAPG, where the agent topology can alleviate the bad influence of other agents’ sub-optimality without hindering cooperation among agents. Theoretically, we prove the policy improvement theorem for stochastic TAPE and give a theoretical explanation for improved cooperation by exploiting agent topology from the perspective of parameter-space exploration.

Empirically, we use three prevalent random graph models (Erdős, Rényi et al. 1960; Watts and Strogatz 1998; Albert and Barabási 2002) to constitute the agent topology. Results show that the Erdős–Rényi (ER) model (Erdős, Rényi et al. 1960) is able to generate the most diverse topologies. With diverse coalitions, agents are able to explore different cooperation patterns and achieve strong cooperation performance. Evaluation results on a matrix game, Level-based foraging (Papoudakis et al. 2021) and SMAC (Samvelyan et al. 2019) show that TAPE outperforms all baselines and the agent topology is able to improve base methods’ performance by both facilitating cooperation among agents and alleviating the CDM issue. Moreover, to show the efficacy of the agent topology, we conduct multiple studies and devise a heuristic graph search algorithm.

Contributions of this paper are three-fold: Firstly, We propose an agent topology framework and Topology-based multi-Agent Policy gradiEnt (TAPE) to achieve compromise between facilitating cooperation and alleviating CDM issue; Secondly, we theoretically establish policy improvement theorem for stochastic TAPE and elaborate the cause for improved cooperation by agent topology; Finally, empirical results demonstrate that the agent topology is able to alleviate the CDM issue without hindering cooperation among agents, resulting in strong performance of TAPE.

The cooperative multi-agent task in this paper is modelled as Decentralized Partially Observable Markov Decision Process (Dec-POMDP) (Oliehoek and Amato 2016). A Dec-POMDP is a tuple $G=\left\langle I,S,\mathcal{A},P,r,\mathcal{O},O,n,\gamma\right\rangle$, where $I=\{1,..,n\}$ is a finite set of $n$ agents, $S$ is the state space, $\mathcal{A}$ is the agent action space and $\gamma$ is a discount factor. At each timestep, every agent $i\in I$ picks an action $a_{i}\in\mathcal{A}$ to form the joint-action $\mathbf{a}\in\mathbf{A}=\mathcal{A}^{n}$ to interact with the environment. Then a state transition will occur according to a state transition function $P(s^{\prime}|s,\mathbf{a}):S\times\mathbf{A}\times S\rightarrow[0,1]$. All agents will receive a shared reward by the reward function $r(s,\mathbf{a}):S\times\mathbf{A}\rightarrow\mathbb{R}$. During execution, every agent draws a local observation $o\in\mathcal{O}$ by an observation function $O(s,a):S\times A\rightarrow\mathcal{O}$. Every agent stores an observation-action history $\tau^{a}\in T=(\mathcal{O}\times\mathcal{A})$, based on which agent $i$ derives a policy $\pi_{i}(a_{i}|\tau_{i})$. The joint policy $\bm{\pi}=\{\pi_{1},..,\pi_{n}\}$ consists of policies of all agents. The global $Q$ value function $Q^{\bm{\pi}}_{tot}(s,\mathbf{a})=\mathbb{E}_{\bm{\pi}}[\sum_{i=0}\gamma^{i}r_{t+i}|s_{t}=s,\mathbf{a}_{t}=\mathbf{a}]$ is the expectation of discounted future reward summed over the joint-policy $\bm{\pi}$.

The policy gradient in stochastic MAPG method DOP is: $g=\mathbb{E}_{\bm{\pi}}\left[\sum_{i}k_{i}(s)\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})Q_{i}^{\phi_{i}}(s,a_{i})\right]$, where $k_{i}\geq 0$ is the positive coefficient provided by the mixing network, and the policy gradient in deterministic MAPG methods is $g=\mathbb{E}_{\mathcal{D}}\left[\sum_{i}\nabla_{\theta_{i}}\pi_{i}(\tau_{i})\nabla_{a_{i}}Q^{\bm{\pi}}_{tot}(s,\bm{a})|_{a_{i}=\pi_{i}(\tau_{i})}\right]$, where $Q^{\bm{\pi}}_{tot}$ is the centralized critic and $\pi_{i}$ is the policy of agent $i$ parameterized $\theta_{i}$.

Multi-Agent Policy Gradient The policy gradient in stochastic MAPG methods has the form $\mathbb{E}_{\bm{\pi}}\left[\sum_{i}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})G_{i}\right]$ (Foerster et al. 2018; Wang et al. 2020c; Lou et al. 2023b; Chen et al. 2022), where objective $G_{i}$ varies across different methods, such as counterfactual advantage (Foerster et al. 2018) and polarized joint-action value (Chen et al. 2022). The objective in DOP is individual aristocratic utility (Wolpert and Tumer 2001), which ignores other agents’ utilities to avoid the CDM issue, but the cooperation is also limited by this objective. It is worth noting that polarized joint-action value (Chen et al. 2022) also aims to address the CDM issue, but it only applies to stochastic MAPG methods, and the polarized global $Q$ value can be very unstable. Deterministic MAPG methods use gradient ascent to directly maximize the centralized global $Q$ value $Q^{\bm{\pi}}_{tot}$. Lowe et al. (Lowe et al. 2017) model the global $Q$ value with a centralized critic. Current deterministic MAPG methods (Zhang et al. 2021; Peng et al. 2021; Zhou, Lan, and Aggarwal 2022) adopt value factorization to mix individual $Q$ values to get $Q^{\bm{\pi}}_{tot}$. As the global $Q$ value is determined by the centralized critic for all agents, sub-optimal actions of one agent will easily influence all others.

In this section, we propose Topology-based multi-Agent Policy gradiEnt (TAPE), which exploits the agent topology for both stochastic and deterministic MAPG. This use of the agent topology provides a compromise between facilitating cooperation and alleviating CDM. The primary purpose of the agent topology is to indicate relationships between agents’ policy updates, so we focus on policy gradients of TAPE here and cover the remainder in supplementary material. First, we will define the agent topology.

The agent topology describes how agents should consider others’ utility during policy updates. Each agent is a vertex $v\in\mathcal{V}$ and $\mathcal{E}$ is the set of edges. For a given topology, $(\mathcal{V},\mathcal{E})$, if $e_{ij}\in\mathcal{E}$, the source agent $i$ should consider the utility of the destination agent $j$ in its policy gradient. The only constraint we place on a topology is that $\forall\ i,\ e_{ii}\in\mathcal{E}$, because agents should at least consider their own utility in the policy gradient. The topology captures the relationships between agents’ policy updates, not their communication network at test time (Foerster et al. 2016; Das et al. 2019; Wang et al. 2019; Ding, Huang, and Lu 2020). Connected agents consider and maximize each other’s utilities together. Thus, the shared objective makes each individual agent form a coalition with the connected neighbors. We use the adjacency matrix $E$ to refer the agent topology in what follows.

In our agent topology framework, DOP (Wang et al. 2020c) (policy gradient given in section 2) and other independent learning algorithms’ has an edgeless agent topology. The adjacency matrix is the identity matrix and no edge exists in the topology. With no coalition, DOP agent will only maximize its own individual utility $Q_{i}$, and hence is poor at cooperation. Although DOP adopts a mixing network for the individual utilities to enhance cooperation, an agent’s ability to cooperate is still limited, which we will empirically show in the matrix game experiments. Methods with centralized critic such as COMA (Foerster et al. 2018), FACMAC (Peng et al. 2021) and PAC (Zhou, Lan, and Aggarwal 2022) yields the fully-connected agent topology. In these methods, there is only one coalition with all of the agents in it (all edges exist in the topology), and all agents update their policies based on the centralized critic. Consequently, they suffer from the CDM issue severely, because the influence of an agent’s sub-optimal behavior will spread to the entire multi-agent system.

In this section, we first demonstrate that by ignoring other agents in the policy gradient to avoid bad influence of their sub-optimal actions, cooperation among agents is severely harmed. To this end, three one-step matrix games that require strong cooperation are proposed. Then, we evaluate the efficacy of the proposed methods on (a) Level-Based Foraging (LBF) (Papoudakis et al. 2021); (b) Starcraft II Multi-Agent Challenge (SMAC) (Samvelyan et al. 2019), and answer several research questions via various ablations and a heuristic graph search technique. Our code is available here¹¹1github.com/LxzGordon/TAPE.

In this paper, we propose an agent topology framework, which aims to alleviate the CDM issue without limiting agents’ cooperation capacity. Based on the agent topology, we propose TAPE for both stochastic and deterministic MAPG methods. Theoretically, we prove the policy improvement theorem for stochastic TAPE and give a theoretical explanation about the improved cooperation among agents. Empirically, we evaluate the proposed methods on several benchmarks. Experiment results show that the methods outperform their base methods and other baselines in terms of convergence speed and performance. A heuristic graph search algorithm is devised and various studies are conducted, which validate the efficacy of our proposed agent topology.

Limitation and Future Work In this work, we consider constructing agent topology with existing random graph models without learning-based methods. Our future work is to adaptively learn the agent topology that can simultaneously facilitate agent cooperation and alleviate the CDM issue.

In this section, we give the derivation of the following policy gradient for stochastic TAPE

	$\displaystyle\nabla J(\theta)$	$\displaystyle=\mathbb{E}_{\bm{\pi}}\left[\sum_{i}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})\mathbf{U}_{i}\right]$		(5)
		$\displaystyle=\mathbb{E}_{\bm{\pi}}\left[\sum_{i,j}E_{ij}k_{j}(s)\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})Q_{j}^{\phi_{j}}(s,a_{j})\right],$

where $\bm{U}_{i}=\sum\limits_{j=1}^{n}E_{ij}U_{j}$ is the coalition utility of agent $i$ with other agents connected in the agent topology, $U_{j}(s,a_{j})=Q^{\phi}_{tot}(s,\bm{a})-\sum\limits_{a_{j}^{\prime}}\pi_{j}({a_{j}^{\prime}}|\tau_{j})Q^{\phi}_{tot}(s,({a_{j}^{\prime}},\bm{a}_{-j}))$ is the aristocrat utility of agent $j$ from (Wolpert and Tumer 2001; Wang et al. 2020c), and $\forall i,E_{ii}=1$, i.e. all agents are connected with themselves.

Proof. First, we will reformulate the aristocrat utility for the policy gradient

		$\displaystyle U_{i}(s,a_{j})=Q^{\phi}_{tot}(s,\bm{a})-\sum\limits_{a_{j}^{\prime}}\pi_{i}({a_{j}^{\prime}}|\tau_{i})Q^{\phi}_{tot}(s,({a_{j}^{\prime}},\bm{a}_{-i}))$
		$\displaystyle=\sum\limits_{j}k_{j}(s)Q^{\phi_{j}}_{j}(s,a_{j})-$
		$\displaystyle\sum\limits_{a_{j}^{\prime}}\pi_{i}({a_{j}^{\prime}}|\tau_{i})\left[\sum\limits_{j\neq i}k_{j}(s)Q^{\phi_{j}}_{j}(s,a_{j})+k_{i}(s)Q^{\phi_{i}}_{i}(s,{a_{j}^{\prime}})\right]$
		$\displaystyle=k_{i}(s)Q^{\phi_{i}}_{i}(s,a_{i})-k_{i}(s)\sum\limits_{a_{j}^{\prime}}\pi_{i}({a_{j}^{\prime}}|\tau_{i})Q^{\phi_{i}}_{i}(s,{a_{j}^{\prime}})$
		$\displaystyle=k_{i}(s)\left[Q^{\phi_{i}}_{i}(s,a_{i})-\sum\limits_{a_{j}^{\prime}}\pi_{i}({a_{j}^{\prime}}|\tau_{i})Q^{\phi_{i}}_{i}(s,{a_{j}^{\prime}})\right].$

$U_{j}(s,a_{j})=k_{j}(s)\left[Q_{j}^{\phi_{j}}(s,a_{j})-\sum\limits_{a_{j}^{\prime}}\pi_{j}({a_{j}^{\prime}}|\tau_{j})Q_{j}^{\phi_{j}}(s,{a_{j}^{\prime}})\right]$. So policy gradient $g$ is

	$\displaystyle g$	$\displaystyle=\mathbb{E}_{\bm{\pi}}\left[\sum_{i,j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})U_{j}(s,a_{j})\right]$
		$\displaystyle=\mathbb{E}_{\bm{\pi}}\Bigg{[}\sum_{i,j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)$
		$\displaystyle\left(Q_{j}^{\phi_{j}}(s,a_{j})-\sum\limits_{a_{j}^{\prime}}\pi_{j}({a_{j}^{\prime}}|\tau_{j})Q_{j}^{\phi_{j}}(s,{a_{j}^{\prime}})\right)\Bigg{]}.$

Let $q_{j}(s)=\sum\limits_{a_{j}^{\prime}}\pi_{j}({a_{j}^{\prime}}|\tau_{j})Q_{j}^{\phi_{j}}(s,{a_{j}^{\prime}})$. Consider a given agent $i$

	$\displaystyle g_{i}$	$\displaystyle=\mathbb{E}_{\bm{\pi}}\left[\sum_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)\left(Q_{j}^{\phi_{j}}(s,a_{j})-q_{j}(s)\right)\right]$
		$\displaystyle=\mathbb{E}_{\bm{\pi}}\left[\sum_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)Q_{j}^{\phi_{j}}(s,a_{j})\right]-$
		$\displaystyle\mathbb{E}_{\bm{\pi}}\left[\sum_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)q_{j}(s)\right].$

Since

		$\displaystyle\mathbb{E}_{\bm{\pi}}\left[\sum_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)q_{j}(s)\right]$
	$\displaystyle=$	$\displaystyle\sum\limits_{s}d^{\bm{\pi}}(s)\sum\limits_{a_{i}}\sum\limits_{\bm{a}^{-i}}\pi_{i}(a_{i}|\tau_{i})\bm{\pi}^{-i}(\bm{a}^{-i}|\bm{\tau}^{-i})$
		$\displaystyle\sum_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)q_{j}(s)$
	$\displaystyle=$	$\displaystyle\sum\limits_{s}d^{\bm{\pi}}(s)\sum\limits_{j}\sum\limits_{\bm{a}^{-i}}E_{ij}\bm{\pi}^{-i}(\bm{a}^{-i}|\bm{\tau}^{-i})k_{j}(s)q_{j}(s)$
		$\displaystyle\sum\limits_{a_{i}}\pi_{i}(a_{i}|\tau)\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})=0,$

$g_{i}=\mathbb{E}_{\bm{\pi}}\left[\sum_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)Q_{j}^{\phi_{j}}(s,a_{j})\right]$. Thus,

$$\nabla J(\theta)=\mathbb{E}_{\bm{\pi}}\left[\sum_{i,j}E_{ij}k_{j}(s)\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})Q_{j}^{\phi_{j}}(s,a_{j})\right]$$

is the policy gradient of stochastic TAPE.$\hfill\square$

In this section, we give proof of the policy improvement theorem of stochastic TAPE. As in previous works (Degris, White, and Sutton 2012; Wang et al. 2020c; Feinberg et al. 2018), we relax the requirement that $Q^{\phi}_{tot}$ is a good estimate of $Q^{\bm{\pi}}_{tot}$ and simplify the $Q$-function learning process as the following MSE problem to make it tractable.

$$L(\phi)=\sum\limits_{\bm{a},s}p(s)\bm{\pi}(\bm{a}|\bm{\tau})\left(Q^{\bm{\pi}}_{tot}(s,\bm{a})-Q^{\phi}_{tot}(s,\bm{a})\right)^{2}$$

(6)

where $\bm{\pi}$ is the joint policy, $Q^{\bm{\pi}}_{tot}(s,\bm{a})$ is the true value and $Q^{\phi}_{tot}(s,\bm{a})$ is the estimated value.

To make this proof self-contained, we first borrow Lemma 1 and Lemma 2 from (Wang et al. 2020c). Lemma 1 states that the learning of centralized critic can preserve the order of local action values. Without loss of generality, we consider a given state $s$.

Lemma 1. We consider the following optimization problem:

$$L_{s}(\phi)=\sum\limits_{\bm{a}}\bm{\pi}(\bm{a}|\bm{\tau})\left(Q^{\bm{\pi}}(s,\bm{a})-f(\bm{Q}^{\phi}(s,\bm{a}))\right)^{2}$$

(7)

Here, $f(\bm{Q}^{\phi}(s,\bm{a})):R^{n}\rightarrow R$, and $\bm{Q}^{\phi}(s,\bm{a}))$ is a vector with the $i^{th}$ entry being $Q_{i}^{\phi_{i}}(s,a_{i})$. $f$ satisfies that $\forall i,a_{i},\frac{\partial f}{\partial Q^{\phi_{i}}_{i}(s,a_{i})}>0$.

Then, for any local optimal solution, it holds that

$$Q^{\bm{\pi}}_{i}(s,a_{i})\geq Q^{\bm{\pi}}_{i}(s,a^{\prime}_{i})\Longleftrightarrow Q^{\phi_{i}}_{i}(s,a_{i})\geq Q^{\phi_{i}}_{i}(s,a^{\prime}_{i}),\ \ \ \forall i,a_{i},a^{\prime}_{i}.$$

Proof. A necessary condition for a local optimal is

	$\displaystyle\frac{\partial L_{s}(\phi)}{\partial Q^{\phi_{i}}_{i}(s,a_{i})}=\pi_{i}(a_{i}|\tau_{i})\sum\limits_{\bm{a}_{-i}}\prod\limits_{j\neq i}\pi_{j}(a_{j}|\tau_{j})$
	$\displaystyle\left(Q^{\bm{\pi}}(s,\bm{a})-f(\bm{Q}^{\phi}(s,\bm{a}))\right)(-\frac{\partial f}{\partial Q^{\phi_{i}}_{i}(s,a_{i})})=0.$

This implies that, for $\forall i,a_{i}$, we have

		$\displaystyle\sum\limits_{\bm{a}_{-i}}\prod\limits_{j\neq i}\pi_{j}(a_{j}|\tau_{j})\left(Q^{\bm{\pi}}(s,\bm{a})-f(\bm{Q}^{\phi}(s,\bm{a}))\right)=0$
	$\displaystyle\Rightarrow$	$\displaystyle\sum\limits_{\bm{a}_{-i}}\bm{\pi}_{-i}(\bm{a}_{-i}|\bm{\tau}_{-i})f\left(\bm{Q}^{\phi}\left(s,(a_{i},\bm{a}_{-i})\right)\right)=Q_{i}^{\bm{\pi}}(s,a_{i}).$

Let $q(s,a_{i})$ denote $\sum\limits_{\bm{a}_{-i}}\bm{\pi}_{-i}(\bm{a}_{-i}|\bm{\tau}_{-i})f\left(\bm{Q}^{\phi}\left(s,(a_{i},\bm{a}_{-i})\right)\right)$. We have

$$\frac{\partial q(s,a_{i})}{\partial Q_{i}^{\phi_{i}}(s,a_{i})}=\sum\limits_{\bm{a}_{-i}}\bm{\pi}_{-i}(\bm{a}_{-i}|\bm{\tau}_{-i})\frac{f\left(\bm{Q}^{\phi}\left(s,(a_{i},\bm{a}_{-i})\right)\right)}{\partial Q_{i}^{\phi_{i}}(s,a_{i})}>0.$$

Therefore, if $Q_{i}^{\bm{\pi}}(s,a_{i})\geq Q_{i}^{\bm{\pi}}(s,a^{\prime}_{i})$, then any local minimal of $L_{s}(\phi)$ satisfies $Q^{\phi_{i}}_{i}(s,a_{i})\geq Q^{\phi_{i}}_{i}(s,a^{\prime}_{i})$.$\hfill\square$

The mixer module of our method satisfies $\forall i,a_{i},\frac{\partial f}{\partial Q^{\phi_{i}}_{i}(s,a_{i})}>0$, so Lemma 1 holds after the policy evaluation converges.

Lemma 2. For two sequences $\{a_{i}\}$, $\{b_{i}\},i\in[n]$ listed in an increasing order. if $\sum_{i}b_{i}=0$, then $\sum_{i}a_{i}b_{i}\geq 0$.

Proof. We denote $\overline{a}=\frac{1}{n}\sum_{i}a_{i}$, then $\sum_{i}a_{i}b_{i}=\overline{a}(\sum_{i}b_{i})+\sum_{i}\tilde{a}_{i}b_{i}$, where $\sum_{i}\tilde{a}_{i}=0$. Without loss of generality, we assume that $\overline{a}_{i}=0$, $\forall i$. $j$ and $k$ which $a_{j}\leq 0,a_{j+1}\geq 0$ and $b_{k}\leq 0,b_{k+1}\geq 0$. Since $a,b$ are symmetric, we assume $j\leq k$. Then, we have

	$\displaystyle\sum\limits_{i\in[n]}a_{i}b_{i}$	$\displaystyle=\sum\limits_{i\in[1,j]}a_{i}b_{i}+\sum\limits_{i\in[j+1,k]}a_{i}b_{i}+\sum\limits_{i\in[k+1,n]}a_{i}b_{i}$
		$\displaystyle\geq\sum\limits_{i\in[j+1,k]}a_{i}b_{i}+\sum\limits_{i\in[k+1,n]}a_{i}b_{i}$
		$\displaystyle\geq a_{k}\sum\limits_{i\in[j+1,k]}b_{i}+a_{k+1}\sum\limits_{i\in[k+1,n]}b_{i}.$

As $\sum\limits_{i\in[j+1,n]}b_{i}\geq 0$, we have $-\sum_{i\in[j+1,k]}b_{i}\leq\sum_{i\in[k+1,n]}b_{i}$

Thus $\sum_{i\in[n]}a_{i}b_{i}\geq(a_{k+1}-a_{k})\sum_{i\in[k+1,n]}b_{i}\geq 0$.$\hfill\square$

The next lemma states that for any policies with tabular expressions updated by stochastic TAPE policy gradient, the larger the local critic’s value $Q_{i}^{\phi_{i}}(s,a_{i})$, the larger update stepsize $\beta_{s,a_{i}}$ for $a_{i}$ under state $s$, and vice versa.

Lemma 3. For any pre-update joint policy $\bm{\pi}$ and updated joint policy $\hat{\bm{\pi}}$ by stochastic TAPE policy gradient with tabular expressions that satisfy $\hat{\pi}_{i}(a_{i}|\tau_{i})=\pi_{i}(a_{i}|\tau_{i})+\beta_{a_{i},s}\delta$ for any agent $i$, where $\delta$ is a sufficiently small number, $\forall s,a^{\prime}_{i},a_{i}$, it holds that

$$Q_{i}^{\phi_{i}}(s,a_{i})\geq Q_{i}^{\phi_{i}}(s,a^{\prime}_{i})\Longleftrightarrow\beta_{a_{i},s}\geq\beta_{a^{\prime}_{i},s}.$$

(8)

Proof. We start by showing the connection between $Q_{i}^{\phi_{i}}(s,a_{i})$ and $\beta_{a_{i},s}$. $\nabla_{\theta_{i}}J(\theta)$ is the policy gradient for agent $i$

	$\displaystyle\nabla_{\theta_{i}}J(\theta)$	$\displaystyle=\mathbb{E}_{\bm{\pi}}\left[\sum_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)Q_{j}^{\phi_{j}}(s,a_{j})\right]$
		$\displaystyle=\sum\limits_{s}d^{\bm{\pi}}(s)\sum\limits_{a_{i}}\sum\limits_{\bm{a}^{-i}}\pi_{i}(a_{i}|\tau_{i})\bm{\pi}^{-i}(\bm{a}^{-i}|\bm{\tau}^{-i})$
		$\displaystyle\qquad\qquad\sum\limits_{j}E_{ij}\nabla_{\theta_{i}}\log\pi_{i}(a_{i}|\tau_{i})k_{j}(s)Q_{j}^{\phi_{j}}(s,a_{j})$
		$\displaystyle=\sum\limits_{s,\bm{a}^{-i}}d^{\bm{\pi}}(s)\bm{\pi}^{-i}(\bm{a}^{-i}|\bm{\tau}^{-i})$
		$\displaystyle\qquad\qquad\sum\limits_{a_{i}}\sum\limits_{j}E_{ij}\nabla_{\theta_{i}}\pi_{i}(a_{i}|\tau_{i})k_{j}(s)Q_{j}^{\phi_{j}}(s,a_{j}).$

With a little abuse of notation, we let $d(s,\bm{\tau}^{-i})=d^{\bm{\pi}}(s)\bm{\pi}^{-i}(\bm{a}^{-i}|\bm{\tau}^{-i})$ for simplicity, where $\bm{\tau}$ is joint agent action-observation history and $-i$ stands for excluding agent $i$. Thus, without loss of generality, consider some given state $s$ and joint action $\bm{a}$, the policy gradient $g_{i}$ for agent $i$ is

	$\displaystyle g_{i}$	$\displaystyle=d(s,\bm{\tau}^{-i})\sum\limits_{j}E_{ij}\nabla_{\theta_{i}}\pi_{i}(a_{i}|\tau_{i})k_{j}(s)Q_{j}^{\phi_{j}}(s,a_{j})$		(9)
		$\displaystyle=d(s,\bm{\tau}^{-i})\nabla_{\theta_{i}}\pi_{i}(a_{i}|\tau_{i})k_{i}(s)Q_{i}^{\phi_{i}}(s,a_{i})+$
		$\displaystyle\qquad\qquad d(s,\bm{\tau}^{-i})\sum\limits_{j\neq i}E_{ij}\nabla_{\theta_{i}}\pi_{i}(a_{i}|\tau_{i})k_{j}(s)Q_{j}^{\phi_{j}}(s,a_{j}).$

Since the policies are with tabular expressions, then $\pi_{i}(a_{i}|\tau_{i})=\theta_{a_{i},\tau_{i}}$. And the update $\beta_{a_{i},s}$ is in proportion to the gradient, so that

$$\beta_{a_{i},s}\propto g_{i}=d(s,\bm{\tau}^{-i})k_{i}(s)Q_{i}^{\phi_{i}}(s,a_{i})+C.$$

where $C$ is a constant independent of $a_{i}$ and $Q_{i}^{\phi_{i}}(s,a_{i})$.