Year: 2021

Abstract:
Recent success in cooperative multi-agent reinforcement learning (MARL) relies on centralized training and policy sharing. Centralized training eliminates the issue of non-stationarity MARL yet induces large communication costs, and policy sharing is empirically crucial to efficient learning in certain tasks yet lacks theoretical justification. In this paper, we formally characterize a subclass of cooperative Markov games where agents exhibit a certain form of homogeneity such that policy sharing provably incurs no suboptimality. This enables us to develop the first consensus-based decentralized actor-critic method where the consensus update is applied to both the actors and the critics while ensuring convergence. We also develop practical algorithms based on our decentralized actor-critic method to reduce the communication cost during training, while still yielding policies comparable with centralized training.

text: Recent success in cooperative multi-agent reinforcement learning (MARL) relies on centralized training and policy sharing. Centralized training eliminates the issue of non-stationarity MARL yet induces large communication costs, and policy sharing is empirically crucial to efficient learning in certain tasks yet lacks theoretical justification. In this paper, we formally characterize a subclass of cooperative Markov games where agents exhibit a certain form of homogeneity such that policy sharing provably incurs no suboptimality. This enables us to develop the first consensus-based decentralized actor-critic method where the consensus update is applied to both the actors and the critics while ensuring convergence. We also develop practical algorithms based on our decentralized actor-critic method to reduce the communication cost during training, while still yielding policies comparable with centralized training.

heading: 1 INTRODUCTION
text: Cooperative multi-agent reinforcement learning (MARL) is the problem where multiple agents learn to make sequential decisions in a common environment to optimize a shared reward signal, which finds a wide range of real-world applications such as traffic control (Chu et al., 2019), power grid management (Callaway & Hiskens, 2010), and coordination of multi-robot systems (Corke et al., 2005). Efficient learning for large and complex cooperative MARL tasks is challenging. Naively reducing cooperative MARL to single-agent RL with a joint observation-action space imposes significant scalability issues, since the joint space grows exponentially with the number of agents. Approaches that treat each agent as an independent RL learner, such as Independent Q-Learning (Tan, 1993), overcome the scalability issue yet fail to succeed in complicated tasks due to the nonstationarity caused by other learning agents’ evolving policies. To address these challenges, the paradigm of Centralized Training and Decentralized Execution (CTDE) is then proposed, where a centralized trainer is assumed to access to information of all agents during training to approximate the global (action-)value function, whereas each agent only needs local information for its action selection during decentralized policy execution (Lowe et al., 2017; Foerster et al., 2017). The centralized critic eliminates non-stationarity during training, while the policy decentralization ensures scalability during execution. Besides, existing CTDE methods almost always enable policy parameter sharing to further improve learning scalability and efficiency, where agents also share the parameters of their decentralized policies.
However, in many real-world scenarios, there is not a readily available centralizer that conveniently gathers the global information from all agents, and therefore agents need to rely on all-to-all communication for centralized training, incurring enormous communication overheads for large numbers of agents. This motivates us to think about whether it is possible to train agents in a decentralized and communication-efficient manner, while still keeping the benefits of the centralized training of CTDE. Moreover, despite its wide adoption, little theoretical understanding has been provided to justify policy parameter sharing. Agents should at least exhibit a certain level of homogeneity before it is feasible to share their policies. For example, if the observation and/or action spaces vary across agents, then their decentralized policies cannot even have the same architecture. Even if it is feasible, it is unclear whether restricting the agents to share their policy parameters will introduce any suboptimality.
In this paper, we address these aforementioned issues centered around the CTDE framework. We begin by formally characterizing a subclass of Markov games where the cooperative agents exhibit a certain form of homogeneity such that it is not only feasible but also incurs no suboptimality to share their decentralized policies, thus providing a first theoretical justification for policy parameter sharing. We then develop a decentralized actor-critic algorithm for homogeneous MGs where agents share their critic and actor parameters with consensus-based updates, for which we prove an asymptotic convergence guarantee with linear critics, full observability, and other standard assumptions. To our knowledge, this is the first decentralized actor-critic algorithm that enjoys provable convergence guarantees with policy (i.e., actor) consensus. To account for communication efficiency, we develop a simple yet effective bandit-based process that wisely selects when and with whom to perform the parameter census update based on the feedback of policy improvement during training. To further account for partial observability, we develop an end-to-end learnable gating mechanism for the agents to selectively share their observations and actions for learning the decentralized critics. This series of innovations are capable of transforming any CTDE algorithm into its decentralized and communication-efficient counterpart, with policy consensus in homogeneous MGs for improved efficiency. Our empirical results demonstrate the effectiveness of these innovations when instantiated with a state-of-the-art CTDE algorithm, achieving competitive policy performance with only a fraction of communication during training.
Our contribution is therefore summarized as three-fold: (1) the characterization of a subclass of cooperative Markov games, i.e. homogeneous Markov games (MGs), where policy sharing provably incurs no loss of optimality; (2) a decentralized MARL algorithm for homogeneous MGs that enjoys asymptotic convergence guarantee with policy consensus; and (3) practical techniques that transform CTDE algorithms to their decentralized and communication-efficient counterparts.

heading: 2 RELATED WORK
text: Communication in cooperative MARL. Communication is key to solving the issue of nonstationarity in cooperative MARL. The CTDE paradigm (Lowe et al., 2017; Foerster et al., 2017) assumes a centralized unit during training to learn a joint value function. Other methods, such as CommNet (Sukhbaatar et al., 2016) and BiCNet (Peng et al., 2017), do not assume a centralized unit and instead allow agents to share information by all-to-all broadcasting, effectively relying on centralized communication. These methods require centralized/all-to-all communication that impedes their application to large numbers of agents. Although follow-up work such as IC3Net (Singh et al., 2018) and VBC (Zhang et al., 2019) proposes algorithms to learn when to communicate, agents there still perform all-to-all communication before others decide whether to receive. We instead entirely abandon centralized/all-to-all communication, letting each agent decide whom to communicate to purely based on its local observation. There is another line of work, Networked MARL (NMARL) (Zhang et al., 2018), that where agents lie on a predefined network such that neighboring agents can freely communicate. Our approach instead learns sparse communication that is dynamically adjusted during decentralized training, even if the predefined network topology can be dense.
Policy parameter sharing and consensus. Policy parameter sharing is widely adopted in MARL where agents share the same action space, yet it has not been theoretically justified except under the mean-field approximation where the transition dynamics depends on the collective statistics of all agents and not on the identities and ordering of individual agents (Nguyen et al., 2017a;b; Yang et al., 2018). A recent result from Kuba et al. (2021) states that enforcing policy parameter sharing in a general cooperative MG can lead to a suboptimal outcome that is exponentially-worse with the number of agents. We are the first to 1) formally characterize the subclass of homogeneous MGs without the notion of mean-field approximation, where enforcing policy parameter incurs no suboptimality and 2) develop an algorithm that performs policy parameter sharing in homogeneous MGs in a soft manner with decentralized consensus-based policy update with convergence guarantees. Zhang & Zavlanos (2019) also develop a policy consensus algorithm for decentralized MARL, yet they do not assume homogeneity and thus need each agent to represent the joint policy for consensus.
Communication-efficient MARL. There have been several recent works that also aim to achieve communication-efficiency in decentralized MARL. Chen et al. (2021b) use pre-specified communication topology and reduce communication frequency for actor-critic via mini-batch updates; in contrast, our work adaptively learn sparse communication topology during the decentralized training
process. Chen et al. (2021a) generalize their method of communication-efficient gradient descent from distributed supervised learning (Chen et al., 2018) to distributed reinforcement learning with policy gradient methods, where they assume the existence of a centralized controller that gather the policy gradients from decentralized agents which only communicate when the change in gradient exceeds a predefined threshold; in contrast, our method does not rely on a centralized controller, and we empirically demonstrate the benefit of our adaptive communication learning over a rulebased baseline inspired by Chen et al. (2021a). Gupta et al. (2020) learn discrete messages among agents with a fixed communication topology, where the communicated messages are used to form the policy for action selection rather than for decentralized training.

heading: 3 HOMOGENEOUS MARKOV GAME
text: We consider a cooperative Markov game (MG) 〈N ,S,A, P,R〉 with N agents indexed by i ∈ N = {1, ..., N}, state space S, action spaceA = A1×· · ·×AN , transition functionP : S×A×S → [0, 1] , and reward functionsR = {Ri}i∈N withRi : S×A → R for each i ∈ N . In Section 3, we assume full observability for simplicity, i.e., each agent observes the state s ∈ S. Under full observability, we consider joint policies, π : S × A → [0, 1], that can be factored as the product of local policies πi : S × Ai → [0, 1], π(a|s) = ∏ i∈N π i(ai|s). Let r(s, a) := 1N ∑ i∈N R
i(s, a) denote the joint reward function, and let γ ∈ [0, 1] denote the discount factor. Define the discounted return from time step t as Gt = ∑∞ l=0 γ
lrt+l, where rt := r(st, at) is the reward at time step t. The agents’ joint policy π = (π1, ..., πN ) induce a value function, which is defined as V π(st) = Est+1:∞,at:∞ [Gt|st], and action-value function Qπ(st, at) = Est+1:∞,at+1:∞ [Gt|st, at]. The agents are cooperative in the sense that they aim to optimize their policies with respect to the joint reward function, i.e., maxπ J(π) = Es0:∞,a0:∞ [G0].

heading: 3.1 HOMOGENEOUS MG: DEFINITION, PROPERTIES, AND EXAMPLES
text: As along as the action spaces {Ai}i∈N are homogeneous, policy sharing among {πi}i∈N is feasible. However, such policy sharing can incur suboptimal joint policies for general MGs, as we will see in an example introduced by Kuba et al. (2021) and revisited in this subsection. Here, we characterize a subclass of Markov games in Definition 1 requiring conditions stronger than homogeneous action spaces, where policy sharing provably incurs no suboptimality. Definition 1 (Homogeneous Markov game). Markov game 〈N ,S,A, P,R〉 is homogeneous if:
(i) The local action spaces are homogeneous, i.e., Ai = Aj ∀i, j ∈ N . Further, the state is decomposed into local states with homogeneous local state spaces, i.e., s = (s1, ..., sN ) ∈ S = S1 × · · · × SN with Si = Sj ∀i, j ∈ N .
(ii) The transition function and the joint reward function are permutation invariant. Formally, for any st = (s1t , ..., s N t ), st+1 = (s 1 t+1, ..., s N t+1) ∈ S and at = (a1t , ..., aNt ) ∈ A, we have
P (Mst+1|Mst,Mat) =P (M ′st+1|M ′st,M ′at), R(Mst,Mat) = R(M ′st,M ′at)
for any M,M ′ ∈ M, where R(s, a) := (R1(s, a), ..., RN (s, a)), Mx denotes a permutation M of ordered list x = (x1, ..., xN ), andM is the set of all possible permutations.
(iii) Each agent i ∈ N has access to a bijective function oi : S → O (i.e., each agent has full observability) that maps states to a common observation space O. These observation functions {oi}i∈N are permutation preserving with respect to the state, i.e., for any s ∈ S and any M ∈M, (
o1(Ms), ..., oN (Ms) ) = M ( o1(s), ..., oN (s) ) .
By Definition 1, besides requiring homogeneous action spaces, our characterization of homogeneous MGs further requires that the global state can be factored into homogeneous local states (condition (i)) such that the transition and reward functions are permutation invariant (condition (ii)). Moreover, condition (iii) requires each agent to have an observation function to form its local representation of the global state. The main property of the homogeneous MG is that, after representing the global state with the observation functions, policy sharing incurs no suboptimality. This is formally stated in Theorem 1. Proofs of all the theorems are included in the appendix.
Theorem 1. Let Π be the set of state-based joint policies, i.e., Π = {π = (π1, ..., πN ) : πi : S × Ai → [0, 1]}, and let Πo be the set of observation-based joint policies, i.e., Πo = {πo = (π1o , ..., π N o ) : π i o : O ×Ai → [0, 1]}. In homogeneous MGs, we have
max π=(π1,...,πN )∈Π J(π) = max πo=(π1o,...,π N o )∈Πo J(πo) = max πo=(π1o,...,π N o )∈Πo: π1o=...=πNo J(πo).
To provide more intuition for homogeneous MGs, we here give an example from Multi-Agent Particle Environment (MPE) (Lowe et al., 2017) and a non-example from Kuba et al. (2021). Appendix D provides more examples and non-examples show the generality of our homogeneous MG subclass.
Example: Cooperative Navigation. In a Cooperative Navigation task in MPE, N agents move as a team to cover N landmarks in a 2D space. The landmarks are randomly initialized at the beginning of an episode, and fixed throughout the episode. Under full observably where each agent can observe the information (locations and/or velocities) of all agents and landmarks, we can cast a Cooperative Navigation task as a homogeneous MG by verifying the three conditions in Definition 1: (i) The local state of agent i consists of its absolute location li = (lix, l i y) ∈ R2 and its absolute velocity vi = (vix, v i y) ∈ R2 with respect to the common origin, as well as the absolute locations of all N landmarks, {ck = (ckx, cky)}Nk=1. Therefore, the location state spaces are homogeneous, and the concatenation of all the location states preserves the global state of the task. Since local action is the change in velocity, the local action spaces are also homogeneous. (ii) The transition function determines the next global state by the current state and all agents’ actions according to physics, and thus it is permutation invariant. The reward function Ri determines the reward for agent i according to the distances between all the agents and the landmarks to encourage coverage, as well as penalties to discourage collisions if any, resulting in a permutation invariant joint reward function. (iii) In MPE, agents’ observations are based on relative, instead of absolute, locations and/or velocities of other agents and/or landmarks. For Cooperative Navigation, such observations happen to define observation functions that are bijective and permutation preserving. Specifically, function oi yields the observation for agent i that consists of its absolute location li and velocity vi, the relative location lij := l
j − li and velocity vij := vj − vi of other agents j ∈ N \ {i}, and the relative location cik := c
k − li of all the landmarks k = 1, .., N . Non-Example: a stateless MG. Kuba et al. (2021) recently shows that enforcing policy parameter sharing is exponentially-worse than the optimality without such a restriction in the following stateless MG: Consider a cooperative MG with an even number of N agents, a state s fixed as the initial state, and the joint action space {0, 1}N , where 1) the MG deterministically transits from state s to a terminal state after the first time step, and 2) the reward in state s is given by R(s, 01:N/2, 11+N/2:N ) = 1 and R(s, a1:N ) = 0 for all other joint actions. It is obvious that the optimal value of this MG (in state s) is 1, while Kuba et al. (2021) prove that the optimal value under policy parameter sharing is 1/2N−1. This MG is not a homogeneous MG: the agents are relying on the raw state to represent their policies, and therefore their observation functions are identity mappings oi(s) = s, which is not permutation preserving and violates Definition 1(iii).

heading: 3.2 POLICY CONSENSUS FOR HOMOGENEOUS MGS
text: Theorem 1 theoretically justifies the parameter sharing among the actors with observation-based representations, which enables us to develop the first decentralized actor-critic algorithms with consensus update among local (observation-based) actors.
Formally, the critic class Q(·, ·;ω) is parameterized with ω to approximate the global action-value function Qπ(·, ·). Upon on-policy transition (st, at, {rit}i∈N , st+1, at+1) sampled by the current policy, the critic parameter ωi for each agent i ∈ N is updated using its local temporal difference (TD) learning followed by a consensus update (Zhang et al., 2018):
ω̃it = ω i t + βω,t · δit · ∇ωQ(st, at;ωit), ωit+1 = ∑ j∈N cω,t(i, j) · ω̃ j t (1)
where rit = R i(st, at) is the local reward of agent i, δit = r i t + γQ(st+1, at+1;ω i t) − Q(st, at;ωit) is the local TD error of agent i, βω,t > 0 is the critic stepsize, and Cω,t = [cω,t(i, j)]i,j∈N is the critic consensus matrix. The observation-based actor for each agent i ∈ N is parameterized as πi(ai|oi(s); θi) with parameter θi, which is updated based on the multi-agent policy gradient
derived from the critic followed by a consensus update:
θ̃it+1 = θ i t + βθ,t ·Q(st, at;ωit) · ∇θi log πi(ait|oi(st); θit), θit+1 = ∑ j∈N cθ,t(i, j) · θ̃ j t (2)
where the observation-based actor class π(·|·; θ) is assumed to be differentiable, βθ,t > 0 is the actor stepsize, and Cθ,t = [cθ,t(i, j)]i,j∈N is the actor consensus matrix.
Compared with existing decentralized actor-critic methods for cooperative MARL (e.g., (Zhang et al., 2018)), the subclass of homogeneous MGs in Definition 1 makes it possible to perform actor consensus (i.e., policy consensus) in Equation (2) that is not possible for general MGs. Theorem 2 states the convergence of {ωit} and {θit} generated by (1)(2) with the linear critic class and under standard assumptions on the stepsizes, consensus matrices, and stability.
Theorem 2. Under standard assumptions for linear actor-critic methods with consensus update, with {ωit} and {θit} generated from Equations (1) and (2), we have limt ωit = ω∗ and limt θit = θ∗ almost surely for any i ∈ N , where θ∗ is a stationary point associated with update (2), and θi∗ is the minimizer of the mean square projected Bellman error for the joint policy parameterized by θ∗.
Theorem 2 and its proof generalize the results in Zhang et al. (2018) to the case where not only the critics but also the actors perform the consensus update. Please refer to Appendix B which provides the exact assumptions, the convergence points, and our proof.

heading: 4 PRACTICAL ALGORITHM
text: The convergence of our decentralized actor-critic algorithm in Section 3.2 relies on the assumptions of linear function approximators, full observability, and well-connected consensus. In this section, we develop a practical algorithm that relaxes these assumptions and achieves communication efficiency. Specifically, the decentralized actors and critics are represented by neural networks. We consider the partial observability setting where the agents cannot directly observe the global state st such that their observation functions {oi} are not bijective. Further, similar to Network MARL (Zhang et al., 2018), we assume the agents can communicate through a time-variant network Gt := (N , Et) with vertex set N and directed edge set Et ⊆ {(i, j) : i, j ∈ N , i 6= j}. Denote the neighbors of agent i at time step t as N it := {j : (i, j) ∈ Et}. With agents only partially observing the global state, we in Section 4.1 develop an architecture for the agents to learn to share their local observations and actions in a communication efficient manner. To achieve communication efficiency on the actor-critic parameter consensus, in Section 4.2 we develop an effective bi-level multi-armed bandit for the agents to learn to exchange the parameters only when it benefits learning. Appendix E provides implementation details of our algorithm.

heading: 4.1 EFFICIENT OBSERVATION-ACTION COMMUNICATION
text: We primarily focus on the type of partial observability where the state is not fully observably by individual agents but jointly observable, i.e., the mapping from st to {oi(st)}i∈N is bijective. For example, this joint observability is satisfied in Cooperative Navigation, where all agents’ observations can determine the state. Thus, each agent can use the observations and actions of its own as well as from its neighbors for its critic to approximate the global action-value. To encourage communication efficiency, we propose an architecture, communication network, that selects a subset Cit ⊆ N it for observation-action communication, such that agent i’s critic becomes Qi({(okt , akt )}k∈{i}∪Cit ). For the texts below, we abuse notation oit := o
i(st) to denote the observation and omit the subscript of time step t when the context is clear.
Communication network. The communication network Ci of agent i outputs cij ∈ {0, 1} indicating whether to communicate with neighbor j ∈ N i, i.e., Ci = {j ∈ N i : cij = 1}. Specifically, we choose an L-layer graph convolutional networks (GCN) to implement Ci, which can deal with arbitrary input size determined by |N i| and achieve permutation invariance. Specifically, the input to this GCN is a fully connected graph with one vertex (oi, eij(o
i)) per neighbor j ∈ N i, where eij(o
i) embeds information of neighbor j that can be extracted from oi. For example, when agents’ identities are observable, eij(o
i) can be (the embedding of) the ID of neighbor j. When identities are not observable, eij(o i) preserves information specific to neighbor j, such as the physical distance
from j to i in MPE. The GCN’s last layer outputs the logits {lij} from which {cij}j∈N i are sampled. To enable differentiability of the sampling, we use the reparameterization trick Straight-Through Gumbel-Softmax (Jang et al., 2016).
Actor and critic networks. Our proposed communication network is compatible with any multiagent actor-critic architecture. Our experiments mainly explore deterministic actors ai = πi(oi). Similar to the communication network, the critic network Qi({(ok, ak)}k∈{i}∪Ci) is also implemented by an L-layer GCN to deal with arbitrary input size and achieve permutation invariance, where the input to the first layer is the fully connected graph with vertices {(ok, ak)}k∈{i}∪Ci .
Training. Critic Qi directly guides agent i’s actor update using the deterministic policy gradient. Critic Qi itself is updated to minimize the TD loss LiTD = Eot,at,rt,ot+1 [(Qit − yit)2], where ot := (o1t , ..., o N t ) is the joint observation, at := (a 1 t , ..., a N t ) is the joint action, Q i t := Qi({(okt , akt )}k∈{i}∪Cit ) is the abbreviated notation for the critic value of agent i at timestep t, and yit := r i t + γQ i t+1 is the TD target. Due to the differentiability enabled by Gumbel-Softmax, the gradient can flow from Qi to communication network Ci. Commonly used in the literature (Jang et al., 2016), the update of Ci is guided by a regularization term α| 1|Cit| ∑ j∈Cit
Softmax(lij) − η|, which places a restriction on the amount of communication allowed defined by rate η.

heading: 4.2 A BI-LEVEL BANDIT FOR PARAMETER CONSENSUS
text: The parameter consensus defined in Equations (1)(2) requires each agent i to communicate with all other agents j where the (i, j) entry of the consensus matrix is non-zero. To achieve communication efficiency, existing literature mainly considers gossip algorithms where each agent only communicated with one neighbor j per communication round (Boyd et al., 2006), i.e., the consensus matrix entries satisfy c(i, j) = c(i, i) = 1/2. Here, we develop a novel bi-level multi-armed bandit to further improve communication efficiency over gossip algorithms, where at each round each agent chooses whether or not to perform consensus at the high level, and if yes, chooses which neighbor to perform gossip consensus update. For ease of exposition, we assume that 1) the agents perform a gradient step and decide whether and how to perform parameter consensus every episode indexed by m = 1, 2, ..., and 2) every agent can always choose from all other agents for parameter consensus, i.e., N it = N \ {i}. Extensions to more general settings are straightforward. We next formally describe this bi-level bandit for an arbitrary agent i, dropping the superscript i for convenience.
Arms. The high-level is a 2-armed bandit determining whether to perform consensus at each round m. Denote the selected high-level arm at round m as x1m, where x 1 m = 0, 1 corresponds to performing and not-performing consensus, respectively. The low-level is a (N − 1)-armed bandit, and we let x2m ∈ N \ {i} denote the selected low-level arm at round m. Rewards. We design different reward functions for the arms in the two levels, as they have different goals. The high-level bandit aims to 1) reduce communication while 2) maintaining a reasonable performance of the learned consensus matrices. Requirement 2) can be captured by the difference of the episodic rewards at different time steps, and requirement 1) can be measured by the frequency of selecting to perform consensus. Let Gm be the total rewards of episode m. To compute the reward r1m for the high-level, we first normalize G
m using the latest l episodes high-level records to fulfill requirement 2), followed by the rewarding or penalizing depending on the sign of normalized Gm to fulfill requirement 1), and finally mapped to to [−1, 1]. The low-level bandit only considers the performance of the learned policy, and the reward r2m can be computed by the normalization of G m using latest l episodes low-level records, then be mapped to [−1, 1]. Note that high-level bandit records every episode, whereas low-level bandit only records a episode when high-level choose to communicate. Equation (3) specifies the details.
r1m ← Gm −mean(G(m−l+1):m)
std(G(m−l+1):m)
r1m ←
{ r1m/ ∑l l′=1 1[x 1 l′ = 0], if rm ≥ 0.
r1m ← r1m/ ∑l l′=1 1[x 1 l′ = 1], otherwise.
r1m ← 2 · sigmoid(r1m)− 1
r2m ← Gm −mean(G(m−l+1):m)
std(G(m−l+1):m)
r2m ← 2 · sigmoid(r2m)− 1 (3)
The reward functions designed above are in nature non-stationary, since the agents are continuously updating their policies, which directly influence the values of the episodic reward difference. Here we choose the adversarial bandit algorithm Exponentially Weighted Average Forecasting (CesaBianchi & Lugosi, 2006) to learn the bi-level bandit.

heading: 5 EXPERIMENTS
text: Our experiments aim to answer the following questions in Sections 5.1-5.3, respectively: 1) How communication-efficient is our algorithm proposed in Section 4 against baselines and ablations? 2) How empirically effective is policy consensus? Specifically, compared with not using policy consensus, can policy consensus converge to better joint policies faster? 3) What are the qualitative properties of the learned communication rules?
Environments. We evaluate our algorithm on three tasks in Multi-Agent Particle Environment (MPE) with the efficient implementation by Liu et al. (2020), each of which has a version with N = 15 agents and another with N = 30 agents. As described in Section 3.1, these MPE environments can be cast as homogeneous MGs provided full observability and the permutation preserving observation functions. We set the communication range to be k = 10 < N nearest agents for all the environments to introduce partial observability. The details of the observation functions in each environment are as follows. Cooperative Navigation: There are 15, 30 landmarks for N = 15, 30 respectively. The observation of an agent contains its own absolute location, the relative locations of the nearest 10 agents, and the relative location of the 11 nearest landmarks. Cooperative Push: N cooperating agents are tasked to push a large ball to a target position. There are 2, 2 landmarks for N = 15, 30 respectively. The observation of an agent contains its own absolute location, the relative locations of the nearest 10 agents, and the relative location of the 2 landmarks. Predator-and-Prey: N cooperating predators (agents) are tasked to capture p preys. The preys are pre-trained and controlled by the environment. There are 5, 10 preys and 5, 10 landmarks (blocks) for N = 15, 30 respectively. Each predator can see p = 3, 5 preys, l = 3, 5 landmarks, k = 10, 10 other predators for N = 15, 30 respectively. The observation of an agent contains its own absolute location, the relative locations of the nearest k agents (predators), the nearest p preys, and the relative location of the l nearest landmark.
Baselines. We use Permutation Invariant Critic (Liu et al., 2020), the state-of-the-art CTDE actorcritic algorithm on MPE, as our centralized training algorithm to derive the following decentralized training baselines. Full-Communication employs all-to-all communication for both observationaction and parameters, i.e., at each time step, each agent receives the observations and actions from all other neighbors for its critic, as well as critic and policy parameters from all other neighbors for its consensus update. Independent learning (IL) employs no communication, i.e., each agent uses its local observations and actions only for its critic and performs no consensus update. Random selects at random 1) a subset of neighbors for observation-action sharing and 2) a single neighbor for gossip parameter consensus. For parameter consensus, we consider a Rule-based baseline, where each agent saves a copy of the parameters from the latest communications with other agents. When agent i considers doing communication at t, it calculates the l1 norm of the parameters of Qi and Q̂j which is the latest copy of j’s parameters it saves. The norm serves as the score to rank the other agents. Intuitively, the high parameter difference implies dramatic behavioral differences. The agent j with the highest score is selected to do parameter consensus, and the copy of agent j’s critic parameter is recorded by agent i. For fair comparisons, the Random and Rule-based baselines incur the same communication cost (i.e., the fraction of neighbors for observation-action communication, and the frequency for parameter consensus) as learned by our bandit method.

heading: 5.1 COMMUNICATION EFFICIENCY AGAINST BASELINES AND ABLATIONS
text: Figure 1 shows the learning curves comparing our communication-efficient decentralized actor-critic algorithm described in Section 4 against the baselines of Full-Communication, IL, and Random, with the observation-action communication rate set as 50%. The results clearly verify the importance of observation-action and parameter communication, as Full-Communication outperforms IL by significant margins uniformly in all the tasks. As will be confirmed in Section 5.3, our algorithm complies with the given observation-action communication rate, and its bandit learning chooses to communicate with a neighbor for parameter consensus only roughly 95% less frequently than Full-
Communication. Our algorithm significantly outperforms the Random baseline that uses the same amount of communication in almost all the tasks, and achieves performances comparable with FullCommunication in several tasks. Remarkably, Random barely outperforms IL in Cooperative Push, suggesting that efficient communication for decentralized training is challenging.
Ablation: parameter communication. We perform ablations on the three environments with N = 15 agents. Fix the observation-action communication pattern to be learned by the proposed communication network, we can see in Figure 2 that parameter consensus strategy learned by our bi-level bandit outperforms the Random parameter consensus baseline, the Rule-based parameter consensus strategy, and even the parameter consensus using Full-Communication in Predator-andPrey, and behaves comparably to parameter consensus using Full-Communication in Cooperative Push, using random parameter consensus and Rule-based parameter consensus in Cooperative Navigation. Noticeably, the Rule-based algorithm behaves similar to the Random parameter consensus baseline in the three scenarios. A possible explanation is that the parameters of the other agents an agent records are outdated, as the Rule-based algorithm uses the same communication frequency (around 95%) learned by the bi-level bandit. Another explanation is that parameter consensus harms exploration, and the balance of them cannot be handled by the Rule-based algorithm which only considers marinating homogeneous behaviors between agents.
Ablation: observation-action communication. Figure 3 shows that increasing communications is not always helpful. In particular, fixing our communication network as the communication pattern, learning with 20% observation-action communication rate performs the worst among the three environments. The one learned with 80% observation-action communication rate performs the best in Cooperative Navigation, performs similarly to the one learned with 50% observation-action communication rate in Cooperative Push, and even performs worse in Predator-and-Prey than the one learned with learned with 50% observation-action communication rate.

heading: 5.2 EFFECTIVENESS OF POLICY CONSENSUS
text: Theorem 2 assures that policy consensus in distributed actor-critic methods for Homogeneous MGs provably converges to a local optimum, yet it remains open questions whether such a local is good
and whether the convergence is fast. Our experiments in this subsection empirically investigate these questions by comparing the learning curves with and without policy parameter consensus. We separately consider 1) the setting where the agents employ all-to-all communication for their critics and parameter consensus, such that the assumptions of full observability and well-connected consensus matrices in Theorem 2 are satisfied, and 2) the setting where the agents learn to communicate efficiently with our communication network and the bandit. The results in Figure 4 show that policy parameter consensus is always beneficial with our communication-efficient method and, surprisingly, it can negatively impact the training with all-to-all communication (e.g., Predator-and-Prey). One plausible explanation is that, while it might speed up convergence, policy parameter consensus can harm exploration, leading to worse local optima.

heading: 5.3 QUALITATIVE ANALYSES OF THE LEARNED COMMUNICATION RULE
text: We first qualitatively examine the observation-action communication rule learned by our communication network. We plot the output of our communication network, i.e., the probabilities of communicating with the k = 10 distance-sorted neighbors, as the learning progresses. Interestingly, the rule learned by our communication network encourages communicating with the nearest neighbors. For example, in Cooperative Navigation with the 50% communication rate as shown in Figure 5, the probabilities of agents communicating with nearest 5 neighbors are over 75%, around 25% for the 6th nearest agent, around 0% for the other neighbors. We provide the counterparts of Figure 5 for all the environments in Appendix C.
Figure 6 shows the probability of choosing the high-level arm of performing consensus as the learning progresses, averaged across the runs of all the environments. The result shows that, with the designed bandit’s reward function, the average probability of selecting to communicate decreases from around 50% to less than 10%.

heading: 6 CONCLUSION
text: In this paper, we characterize a subclass of cooperative Markov games where the agents exhibit a certain form of homogeneity such that policy sharing provably incurs no loss of optimality. We develop the first multi-agent actor-critic algorithm for homogeneous MGs that enjoys asymptotic convergence guarantee with decentralized policy consensus. For practical usage, we propose techniques that can efficiently learn to communicate with other agents in exchange of observations, actions, and parameters. The empirical results show that our proposed algorithm performs better than several baselines in terms of communication efficiency.

heading: A PROOF OF THEOREM 1
text: The set of bijections {oi}i∈N induces a one-to-one mapping between Π and Πo, and therefore the first equality holds. For the second equality, consider an arbitrary state s = (s1, ..., sN ) ∈ S and the permutation M that swaps a pair of agents (i, j), such that Ms = M(..., si, ..., sj , ...) = (..., (Ms)i = sj , ..., (Ms)j = si, ...).. Due to the permutation invariance of the transition and reward functions by condition (ii) of Definition 1, there exists an optimal state-based joint policy π∗ ∈ Π such that πi∗(·|s) = π j ∗(·|Ms). Consider the corresponding optimal observation-based joint policy π∗o ∈ Πo that is the bijective mapping of π∗, such that πi∗o(·|oi(s)) = πi∗(·|s) and πj∗o(·|oj(Ms)) = πj∗(·|Ms). We therefore have
πi∗o(·|oi(s)) = πj∗o(·|oj(Ms)). (4)
Further, since {oi}i∈N are permutation preserving by condition (iii) of Definition 1, we have oi(s) = oj(Ms) ∈ O in Equation (4). Since Equation (4) holds for arbitrary s ∈ S and i, j ∈ N , and thus it follows that
πi∗o(·|o) = πj∗o(·|o) ∀o ∈ O, (5)
i.e., the second equality holds. This concludes the proof.
A.1 ILLUSTRATIVE EXAMPLE FOR THE PROOF
We here provide an illustrative example in Figure 7 to aid the proof. The example Markov game consists of three agents i ∈ {1, 2, 3} placed on the left (L), middle (M ), and right (R), one in each position, with a triangle placed in front of each agent that is either pointing up (4) or down (5). The agents have homogeneous action spaces {↑, ↓}. The agents also have homogeneous local state spaces {L,M,R} × {4,5}, repenting its position and the shape in front. The game ends after the first timestep, and the agents share the following reward function: 1) if the number of the4 is even, reward is +1 when the agents behind4 choose to go up (↑) and the agents behind5 choose to go down (↓); 2) if the number of the4 is odd, reward is +1 when the agents behind 4 choose to go down (↓) and the agents behind 5 choose to go up (↑); 3) reward is 0 otherwise. Thus, the Markov game satisfies Definition 1(i)(ii). The agents’ local observations preserve their absolute positions (i.e., L, M , or R) and consist the three shapes ordered clockwise starting from the shape right in front. For example, the local observation of agent i = 1 on the left of Figure 7 is o1 = (L,454). As verified by the second row in Figure 7, the local observations are permutation preserving to satisfy Definition 1(iii). Therefore, the Markov game is homogeneous by Definition 1.
The third row in Figure 7 verifies Equations (4)(5) that are key to the proof.

heading: B PROOF OF THEOREM 2

heading: B.1 ASSUMPTIONS
text: We make the following assumptions that are necessary to establish the convergence.
Assumption 1. The Markov game has finite state and action spaces and bounded rewards. Further, for any joint policy, the induced Markov chain is irreducible and aperiodic.
Assumption 2. The critic class is linear, i.e., Q(s, a;ω) = φ(s, a)>ω, where φ(s, a) ∈ RK is the feature of (s, a). Further, the feature vectors φ(s, a) ∈ RK are uniformly bounded by any (s, a). The feature matrix Φ ∈ R|S||A|×K has full column rank. Assumption 3. The stepsizes βω,t and βθ,t satisfy∑
t βω,t = ∑ t βθ,t =∞, ∑ t β 2 ω,t <∞, ∑ t β 2 θ,t <∞, βθ,t = o (βω,t) .
In addition, limt βω,t+1β−1ω,t = 1.
Assumption 4. We assume the nonnegative matrices Ct ∈ {Cω,t, Cθ,t} satisfy the following conditions: (i) Ct is row stochastic (i.e., Ct1 = 1) and E[Ct] is column stochastic (i.e., 1>E[Ct] = 1> ) for all t > 0; (ii) The spectral norm of E[(W>t (I − 1N 11
>)Wt] is strictly smaller than one; (iii) Wt and (st, {rit}) are conditionally independent given the σ-algebra generated by the random variables before time t.
Assumption 5. The critic update is stable, i.e., supt ∥∥ωit∥∥ <∞, for all i. For the actor update, {θit} belongs to a compact set for all i and t.

heading: B.2 CRITIC CONVERGENCE
text: In this subsection, we establish critic convergence under a fixed joint policy in Lemma 3. Specifically, given a fixed joint policy π = (π1, ..., πN ), we aim to show that the critic update converges to ωπ , which is the unique solution to the Mean Square Projected Bellman Error (MSPBE):
ωπ = arg min ω
‖Φω −ΠTπ(Φω)‖2Dπ ,
which also satisfies
Φ>Dπ [Tπ(Φωπ)− Φωπ] = 0,
where Tπ is the Bellman operator for π, Π is the projection operator for the column space of Φ, and Dπ = diag[dπ(s, a) : s ∈ S, a ∈ A] for the stationary distribution dπ induced by π. Lemma 3. Under the assumptions , for any give joint policy π, with distributed critic parameters ωit generated from Equation 1 using on-policy transitions (st, at, rt, st+1, at+1) ∼ π, we have limt ω i t = ωπ almost surely (a.s.) for any i ∈ N , where ωπ is the MSPBE minimizer for joint policy π.
Proof. We use the same proof techniques as Zhang et al. (2018).
Let φt = φ(st, at), δt = [δ1t , ..., δ N t ] >, and ωt = [ω1t , ..., ω N t ] > . The update of ωt in Equation 1 can be rewritten in a compact form of ωt+1 = (Cω,t ⊗ I)(ωt + βω,tyt) where ⊗ is the Kronecker product, I is the K × K identity matrix, and yt = [δ1t φ>t , ..., δNt φ>t ]> ∈ RKN . Define operator 〈·〉 : RKN → RK as
〈ω〉 = 1 N (1> ⊗ I)ω = 1 N ∑ i∈N ωi
for any ω = [(ω1)>, ..., (ωN )>]> ∈ RKN with ωi ∈ RK for any i ∈ N . We decompose ωt into its agreement component 1 ⊗ 〈ωt〉 and its disagreement component ω⊥,t := ωt − 1 ⊗ 〈ωt〉. To prove ωt = ω⊥,t + 1⊗ 〈ωt〉 a.s.−−→ 1⊗ ωπ , we next show ω⊥,t a.s.−−→ 0 and 〈ωt〉 a.s.−−→ ωπ respectively.

heading: Convergence of ω⊥,t
text: a.s.−−→ 0. We first establish that, for any M > 0, we have
sup t
E [∥∥β−1ω,tω⊥,t∥∥2 · 1{supt‖ωt‖≤M}] <∞. (6)
To show Equation 6, let {Ft} be the filtration of Ft = σ(rτ−1sτ , aτ , ωτ , Cω,τ−1; τ ≤ t), J = 1 N (11
> ⊗ I) such that Jωt = 1 ⊗ 〈ωt〉, (I − J)ωt = ω⊥,t. The following facts about ⊗ will be useful:
(A⊗B)(C ⊗D) = (AC)⊗ (BD) (7)
This enables us to write ω⊥,t+1 as
ω⊥,t+1 =(I − J)ωt+1 =(I − J) [(Cω,t ⊗ I)(ωt + βω,tyt)] =(I − J) [(Cω,t ⊗ I)(1⊗ 〈ωt〉+ ω⊥,t + βω,tyt)] (By Equation 7 and Assumption 4, we have (Cω,t ⊗ I)(1⊗ 〈ωt〉) = (Cω,t1)⊗ (I〈ωt〉) = 1⊗ 〈ωt〉)
=(I − J) [1⊗ 〈ωt〉+ (Cω,t ⊗ I)(ω⊥,t + βω,tyt)] =(I − J) [(Cω,t ⊗ I)(ω⊥,t + βω,tyt)] ((I − J)(1⊗ 〈ωt〉) = 0) =[(I − 11>/N)⊗ I] [(Cω,t ⊗ I)(ω⊥,t + βω,tyt)] (I − J = (I − 11>/N)⊗ I) =[(I − 11>/N)Cω,t ⊗ I](ω⊥,t + βω,tyt) (By Equation 7).
We then have
E [∥∥β−1ω,t+1ω⊥,t+1∥∥2 | Ft]
(‖x‖2 = x>x,A = (I − 11>/N)Cω,t ⊗ I, A>A = C>ω,t(I − 11>/N)Cω,t ⊗ I)
= β2ω,t β2ω,t+1
E [( β−1ω,tω⊥,t + yt )> ( C>ω,t(I − 11>/N)Cω,t ⊗ I ) ( β−1ω,tω⊥,t + yt ) | Ft ] (A = C>ω,t(I − 11>/N)Cω,t, B = I, ‖A⊗B‖ = ‖A‖ ‖B‖) (x>Ax =
∥∥x>Ax∥∥ ≤ ∥∥x>∥∥ ‖A‖ ‖x‖ = ‖A‖x>x) (Cω,t and (rt, yt) are independent conditioning on Ft)
≤ β2ω,t β2ω,t+1
ρE [( β−1ω,tω⊥,t + yt )> ( β−1ω,tω⊥,t + yt ) | Ft ] (where ρ is the spectral norm of E[C>ω,t(I − 11>/N)Cω,t])
= β2ω,t β2ω,t+1
ρ ( E [∥∥β−1ω,tω⊥,t∥∥2 | Ft]+ 2E [〈β−1ω,tω⊥,t, yt〉 | Ft]+ E [‖yt‖2 | Ft])
(By Cauchy-Schwarz |〈u, v〉| ≤ ‖u‖ ‖v‖)
≤ β2ω,t β2ω,t+1
ρ ( E [∥∥β−1ω,tω⊥,t∥∥2 | Ft]+ 2E [∥∥β−1ω,tω⊥,t∥∥ ‖yt‖ | Ft]+ E [‖yt‖2 | Ft])
(Quantities are deterministic given Ft)
= β2ω,t β2ω,t+1
ρ (∥∥β−1ω,tω⊥,t∥∥2 + 2 ∥∥β−1ω,tω⊥,t∥∥ ‖yt‖+ ‖yt‖2) . (8)
Since E[‖yt‖2 |Ft] = E[ ∑ i∈N ∥∥δitφt∥∥2 |Ft] with δit = rt + γφ>t ωit − φ>t+1ωit, by Assumptions 1 and 2 the rewards rt and the features φt are bounded, and thus we have that E[‖yt‖2 |Ft] is bounded on set {supτ≤t ‖ωτ‖ ≤ M} for any given M > 0. We can then following the proof of Lemma 5.3 in Zhang et al. (2018) and its sequel to show Equation 6 and conclude the step of ω⊥,t a.s.−−→ 0.

heading: Convergence of 〈ωt〉
text: a.s.−−→ ωπ . We write the update of 〈ωt〉 as
〈ωt+1〉 = 1
N (1> ⊗ I)ωt+1
= 1
N (1> ⊗ I) [(Cω,t ⊗ I)(1⊗ 〈ωt〉+ ω⊥,t + βω,tyt)]
=〈ωt〉+ βω,t〈(Cω,t ⊗ I)(yt + β−1ω,tω⊥,t)〉 (By Equation 7).
We rewrite the above update as
〈ωt+1〉 =〈ωt〉+ βω,tE [〈δt〉φt | Ft] + βω,tξt (9) where ξt =〈(Cω,t ⊗ I)(yt + β−1ω,tω⊥,t)〉 − E [〈δt〉φt | Ft]
We can verify that the following conditions hold (with probability 1) regarding the update of 〈ωt〉 in Equation 9:
1. E [〈δt〉φt | Ft] is Lipschitz continuous in 〈ωt〉,
2. ξt is a martingale difference sequence and satisfies E[‖ξt+1‖2 | Ft] ≤ K(1 + ‖ωt‖2) for some constant K,
such that the conditions in Assumption B.1 of Zhang et al. (2018) are satisfied (with probability 1) and the behavior of Equation 9 is related to its corresponding ODE (see Theorem B.2 in Zhang et al. (2018)):
˙〈ω〉 = ∑ s,a dπ(s, a)E [〈δ〉φ|s, a]
= ∑ s,a dπ(s, a)Es′,a′ [( r(s, a) + γφ>(s, a)〈ω〉 − φ>(s, a)〈ω〉 ) φ(s, a)|s, a ] =Φ>Dπ(γP π − I)Φ〈ω〉+ Φ>DπR
Note that (γPπ− I) has all eigenvalues with negative real parts, so does (Φ>Dπ(γPπ− I)Φ) since Φ is assumed to be full column rank. Hence, the ODE is globally asymptotically stable, with its equilibrium satisfying
Φ>Dπ [R+ (γP π − I)Φ〈ω〉] = 0,
which is the MSPBE minimizer, i.e., 〈ω〉 = ωπ . This concludes the step of 〈ωt〉 a.s.−−→ ωπ and the proof of Lemma 3.

heading: B.3 ACTOR CONVERGENCE
text: In this subsection, we establish the convergence of actor update with critic parameters ωit in Equation 2 replaced with the critic convergence point established in Lemma 3. Then, by the two-timescale nature of the algorithm, we establish the convergence of {ωit} and {θit} generated by Equation 1 and Equation 2.
Let θ = [(θ1)>, ..., (θN )>]> and ωθ be the critic convergence point for joint policy parameterized by θ as established in Lemma 3. Define
Ait,θ = Q(st, at;ωθ) ψ i t,θ = ∇θi log πi(ait|oi(st); θi)
for an arbitrary θ. We study the variant of Equation 2 where ωit is replaced by ωθt :
Ait,θt =Q(st, at;ωθt) ψ i t,θt = ∇θi log π i(ait|oi(st); θit)
θ̃it+1 =θ i t + βθ,t ·Ait,θt · ψ i t,θt θit+1 = ∑ j∈N cθ,t(i, j) · θ̃it (10)
which can be rewritten as
θt+1 = (Cθ,t ⊗ I)(θt + βθ,tyt,θt)
where yt,θt = [(A 1 t,θt · ψ1t,θt) >, ..., (ANt,θt · ψ N t,θt )>]>.
Similar to the critic convergence, we make the decomposition θt = θ⊥,t + 1 ⊗ 〈θt〉 and then show θ⊥,t a.s.−−→ 0 and convergence of 〈θt〉 respectively.

heading: Convergence of θ⊥,t
text: a.s.−−→ 0. In light of the argument for ω⊥,t a.s.−−→ 0 in the proof of Lemma 3, it suffices to show that the the boundedness of yt,θt . Here, yt,θt = [(A 1 t,θt ·ψ1t,θt) >, ..., (ANt,θt ·ψ N t,θt )>]> is bounded because 1) Ait,θt = Q(st, at;ωθt) is bounded since ωθt is the MSPBE minimizer; (2) ψit,θt is bounded since by Assumption 5 it is a continuous function over a compact set.
Convergence of 〈θt〉. We write the update of 〈θt〉 in Equation 10 as
〈θt+1〉 = 1
N (1> ⊗ I)θt+1
= 1
N (1> ⊗ I) [(Cθ,t ⊗ I)(1⊗ 〈θt〉+ θ⊥,t + βθ,tyt,θt)]
=〈θt〉+ βθ,t〈(Cθ,t ⊗ I)(yt,θt + β−1θ,t θ⊥,t)〉 (By Equation 7).
We rewrite the above update as
〈θt+1〉 =〈θt〉+ βθ,tEst∼d〈θt〉,at∼π〈θt〉 [〈yt,θt〉 | Ft] + βθ,tξt where ξt =〈(Cθ,t ⊗ I)(yt,θt + β−1θ,t θ⊥,t)〉 − Est∼d〈θt〉,at∼π〈θt〉 [〈yt,θt〉 | Ft]
where Ft = σ(θτ , τ ≤ t), π〈θt〉 is the joint policy where each individual policy is parameterized by 〈θt〉. Note that ξt is a martingale difference sequence. By Assumption 5 ξt is bounded and further by Assumption 3 we have ∑ t ‖βθ,tξt‖ 2 <∞. By arguments in the proof of Theorem 4.7 in Zhang et al. (2018), we can apply Kushner-Clark lemma and conclude that 〈θt〉 converges almost sure to a point in the set of asymptotically stable equilibria of
˙〈θ〉 = Est∼d〈θ〉,at∼π〈θ〉 [ 〈yt,〈θ〉〉 ] = Est∼d〈θ〉,at∼π〈θ〉 [∑ i Ait,〈θ〉 · ψ i t,〈θ〉 ] .
C VISUALIZATION OF THE LEARNED COMMUNICATION RULE

heading: D EXAMPLES AND NON-EXAMPLES OF HOMOGENEOUS MG

heading: D.1 EXAMPLES
text: MPE tasks with homogeneous agents. We have explained in Section 3.1 that the Cooperative Navigation task in MPE is an example of homogeneous MG. By repeating the same arguments, we can show that all other MPE tasks with homogeneous agents are example of homogeneous MG, including cooperative push and predator-and-prey as we have used for our experiments in Section 5. Specifically, each agent’s observation contains its absolution location and velocity, as well as the relative location and/or velocity of other agents and environment objects (e.g., landmarks, the ball and the target position in cooperative push, preys). For predator-and-prey, either the predators or the preys form a team of homogeneous agents.
SMAC scenarios with homogeneous ally units. StarCraft Multi-Agent Challenge (SMAC) is another benchmark environment for cooperative MARL. In a number of SMAC scenarios, the team of agents consists of ally units of a single unit type (e.g., Marines), and they are tasked to defeat an enemy team controlled by the environment, with examples including 3m, 8m, 25m, 8m vs 9m, 2m vs 1z, 6h vs 8z, etc. Each ally unit (i.e., agent) observes the following attributes of both ally and enemy units: distance, relative x, relative y, health, shield, and unit type. Thus, an SMAC scenario with homogeneous ally units is similar to MPE’s predator-and-prey in the sense how it satisfies the conditions in Definition 1. Thus, SMAC scenarios with homogeneous ally units are homogeneous MGs.
Team sports. Sports with homogeneous players forming a team are homogeneous MGs, with examples including basketball, American football, soccer(associate football)/ice hockey excluding the goalkeeper. In these team sports, players’ local views naturally forms their observations that satisfy Definition 1(iii).
Traffic with homogeneous vehicles. Traffic consisting vehicles of the same type (e.g., the same car-following model) is an example of homogeneous MG. Like team sports, vehicles’ local views naturally forms their observations that satisfy Definition 1(iii). Unlike team sports, these vehicles are unnecessarily cooperative, but their reward functions are permutation invariant to satisfy Definition 1(ii).
Surveillance with drones. Drone surveillance is an application of cooperative MARL, where a set of (homogeneous) drones is tasked to collectively monitor a ground area. Since the drones’ objective is to cover the ground area, the task is analogous to MPE’s Cooperative Navigation to satisfy the conditions in Definition 1.

heading: D.2 NON-EXAMPLES
text: MPE tasks with heterogeneous agents. As the counterpart of Cooperative Navigation with homogenous agents, Liu et al. (2020) introduce heterogeneous navigation where half of the agents are small and fast and the other half are big and slow. In such an MPE task, the transition function is not permutation invariant, and therefore it is not a homogeneous MG.
SMAC scenarios with heterogeneous ally units. If the ally units in an SMAC scenario are of different types, then the transition function is not permutation invariant, and therefore it is not a homogeneous MG. These SMAC scenarios include 2s3z, 3s5z, MMM2, etc.
Multi-Agent MuJoCo In a MuJoCo task, a robot aims to learn an optimal way of motion. MultiAgent MuJoCo (Peng et al., 2020) controls each part of the robot with an agent, for example, a leg for a spider. Since the parts of a robot are heterogeneous, Multi-Agent MuJoCo can violate condition (i) of Definition 1.
E IMPLEMENTATION DETAILS
E.1 ARCHITECTURE OVERVIEW

heading: E.2 PSEUDOCODE
text: Algorithm 1 Pseudocode of our communication-efficient actor-critic algorithm
1: init {Ci}Ni=1, {Qi}Ni=1, {πi}Ni=1,memory, {records i l}Ni=1, {records i h}Ni=1. 2: for episode m = 1, 2, . . . , L do 3: for agent i = 1, 2, . . . , N do 4: sample x1m from agent i’s high-level bandit. 5: if x1m == 0 then 6: sample x2m from agent i’s low-level bandit. 7: Agent i does parameter consensus with agent x2m. 8: end if 9: end for

heading: 10: Gm = 0
text: 11: for t = 1, 2, . . . , T do 12: Get ot+1, rt by interacting with the environment; Put ot, at, ot+1, rt into the memory. 13: Gm ← rt + γGm 14: end for 15: if len(memory) > batch size then 16: for i = 1, 2, . . . , N do 17: sample a batch from memory. 18: licritic = 0 . Loss for agent i’s critic and comm net. 19: for oit, ait, oit+1, rit in batch[i] do 20: Cit ← Ci(oit), Cit+1 ← Ci(oit+1) 21: Qit ← Qi({(okt , akt )}k∈{i}∪Cit );Q i t+1 ← Qi({(okt+1, akt+1)}k∈{i}∪Cit+1) 22: yit := r i t + γQ i t+1
23: licritic ← licritic + (Qit − yit)2 + α| 1|Cit| ∑ j∈Cit
Softmax(lij)− η| 24: end for 25: licritic ← licritic/batch size 26: Send licritic to the Adam optimizer for the update. 27: end for 28: for i = 1, 2, . . . , N do 29: sample a batch from memory. 30: liactor = 0 . Loss for agent i’s actor. 31: for oit in batch[i] do 32: ait ← πi(oit) 33: Cit ← Ci(oit), Cit+1 ← Ci(oit+1) 34: Qit ← Qi({(okt , akt )}k∈{i}∪Cit ) 35: liactor ← liactor −Qit 36: end for 37: liactor ← liactor/batch size 38: Send liactor to the Adam optimizer for the update. 39: end for 40: for agent i = 1, 2, . . . , N do 41: Push Gm into recordsih. 42: Keep the latest l elements of recordsih; Compute r 1 m designed in (3) 43: Update agent i’s high-level bandit by r1m. 44: if x1m == 0 then 45: Push Gm into recordsil . 46: Keep the latest l elements of recordsil; Compute r 2 m designed in (3) 47: Update agent i’s low-level bandit by the r2m. 48: end if 49: end for 50: end if 51: end for

heading: E.3 HYPERPARAMETERS

heading: F EXPERIMENTS ON A TOY EXAMPLE OF HOMOGENEOUS MG
text: Theorem 2 proves the asymptotic convergence of our decentralized actor-critic updates in Equations (1)(2) with actor consensus for homogeneous MGs, which generalizes the asymptotic convergence result without actor consensus (Zhang et al., 2018). While the actor-critic updates converge asymptotically both with and without actor consensus, obtaining their convergence rates require non-trivial finite-time analysis that remains an open problem. Here, we empirically compare the actor-critic updates in Equations (1)(2) with and without actor consensus on a toy example of homogeneous MG, leaving the finite-time analysis for future work.
The toy example. We have provided the stateless MG in Kuba et al. (2021) in Section 3.1 as a nonexample. If we augment each agent i with a unique local state si, then it is easy to verify that these local states satisfy Definition 1(ii) and it is ease to construct local observations, oi = (si, s1, .., sN ), that satisfy Definition 1(iii), such that the MG becomes an example of homogeneous MG.
Results. We define the unique local states by the trigonometric function, si = cos( i−1N−1π), i = 1, ..., N . We use feature function φ(s, a) = concat[{si, one hot(ai)}i] for the linear critic, and parameterize the actor as a linear function of oi followed by softmax over the two actions. The consensus matrix is 1/N everywhere for both the critics and the actors. For effective training, we 1) replace the sparse reward function with a denser one, R(s, a) := meani:si≥0{1[ai = 1]} − meani:si<0{1[ai = 1]}, such that the optimal joint action is ai = 1 for i ≤ N/2 and ai = 0 for i > N/2 that gets a reward of +1, and 2) instead of using the decaying stepsizes as suggested in Assumption 3, which we found is not effective for training, we use the optimizer of Adam for adaptive learning rates. Figure 10 show the results for N = 10, 50. While both converge, actor consensus slightly improves the learning efficiency.

heading: G EXPERIMENTS WITH VARIOUS AMOUNTS OF COMMUNICATION

Review summaries:
This paper proposes a consensus-based actor-critic algorithm for multi-agent RL with limited communication during the training phase. This is in contrast to standard centralized training approaches such as MADDPG or COMA that assume access to the complete data form all agents for training critics. The paper motivates the proposed algorithm by an analysis of homogeneous Markov games (MGs), a subclass of MGs where parameter sharing preserves policy optimality. Inspired by the networked MARL consesus method of Zhang et al. (2018), the paper proposes a policy consensus algorithm that learns with which neighbours to share actions and observations or to perform consesus-based updates on policy and critic parameters using a bi-level bandit method. The effectiveness of the proposed algorithm in reducing the required communication during training is empirically verified in a suite of experiments in the multi-agent particle environment (MPE) domains.

This paper considers a subclass of cooperative Markov games where agents exhibit a certain form of homogeneity such that policy sharing provably incurs no sub-optimality. Based on this property, the paper develops a consensus-based decentralized actor-critic method where the consensus update is applied to both the actors and the critics while ensuring convergence. Furthermore, heuristic algorithms have been developed and incorporated into the consensus-based decentralized actor-critic method to reduce the communication cost during training. 

This paper studies homogeneous/permutation invariant MARL setting and prove a theorem that says there is no loss in restricting to identical policies, thus justifying policy parameter sharing. Then, a consensus-based MARL actor-critic method is proposed. Further, a communication-efficient protocol is proposed to improve communication efficiency.