Communication-Efficient Actor-Critic Methods for Homogeneous Markov Games
Authors: Dingyang Chen
Yile Li
Qi Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: multi-agent reinforcement learning
multi-agent communication

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.

Published as a conference paper at ICLR 2022
COMMUNICATION-EERIICHH ACTOR-CRITIC METHODS FOR HOMOGENEOUS MARKOV GAMES
Dingyang Chen', Yile Li, Qi Zhang'
1 Artificial Intelligence Institute, University of South Carolina di dingyange ema il sc.sc..de edu, qz5ecse. sC. edu
ABSTRACT
Recent success in cooperative multi-agent reinforcement learning (MARL) relies on centralized training and policy sharing. Centralized training climinates the is- of non-stationarity MARL yet induces large communication costs, and policy sharing empirically crucial to efficient learning in certain tasks yet lacks theo- retical justification. In this paper, formally characterize a subclass of coopera- tive Markov games where agents exhibit a certain form of homogeneity such that policy sharing provably incurs no suboptimality. This enables us develop the first consensus-based decentralized actor-critic method where the consensus up- date applied to both the actors and the critics while ensuring convergence. We also develop practical algorithms based on our decentralized actor-critt method to reduce the communication cost during training, while still yielding policies comparable with centralized training.
INTRODUCTION
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 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 sig- nificant 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 the non- stationarity caused by other learning agents' evolving policies. To address these challenges, the paradigm of Centralized Training and Decentralized Execution (CTDE) then proposed, where centralized trainer is assumed to access to information of all agents during training to approx- imate the global (action-)vaal yvalue function, whereas each agent only needs local information for its action selection during decentralized policy execution (Lowe al. 2017 Foerster al., (017). The centralized critic eliminates non-stationarity during training, while the policy decentralization en- sures 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 readily available centralizer that conveniently gathers the global information from all agents, and therefore agents need rely on all-to-all commu- nication for centralized training. incurring enormous communication overheads for large numbers of agents. This motivates us think about whether possible to train agents in decentralized and communication-effiiiee. 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 certain level of homogeneity be- fore is feasible to share their policies. For example, if the observation and/or action spaces vary across agents, then their decentralized policies cannot 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.

---

Published as a conference paper at ICLR 2022
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 certain form of homogeneity such that it is not only feasible but also incurs suboptimality to share their decentralized policies, thus providing first theoretical justification for policy parameter sharing. We then develop decentralized actor-critic algorithm for homogeneous MGs where agents share their critic and actor parameters with consensus-based updates, for which we prove an asymp- totic convergence guarantee with linear crities, full observability, and other standard assumptions. To our knowledge, this is the first decentralized actor-critic algorithm that enjoys provable conver- gence 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 per- form 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 cmmmunication-effcciee counterpart, with policy consensus in homogeneous MGs for improved efficiency. Our empirical results demonstrate the effectiveness of these innovations when instanti- ated with a state-of-the-an 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 subelass of cooperative Markov games, i.c. 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- -efficciiinn counterparts.
2 RELATED WORK
Communication in cooperative MARL. Communication is key to solving the issue of non- stationarity in cooperative MARL. The CTDE paradigm (Lowe et al. 2017 Foerster et (017) 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. (017)) do not assume a centralized unit and instead allow agents to share information by all-to-all broadcasting, effectively relying on cen- tralized communication. These methods require centralized/all-to-
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--or 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.
communication, letting each agent decide whom to communicate to
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 statisties of all agents and not on the identities and ordering of individual agents (Nguyen et al. 2017a b Yang et al., 2018 recent result from Kuba et al. (20TT) states that enforcing policy parameter sharing in general cooperative MG can lead to a suboptimal outcome that is exponentially-won worse with the num- ber 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 (219) also develop a policy consensus algorithm for decentralized MARL, yet they do not assume homogeneity and thus need each agent represent the joint policy for consensus.
Communication-effciient MARL. There have been several recent works that also aim to achieve communication eeffriittiiooeefiiiieeyy in decentralized MARL. Chen et al. (2021b) use pre-specified commu- nication 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
2

---

Published as a conference paper at ICLR 2022
process. Chen al. (2021a) generalize their method of communication-effan 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 predefined threshold; in contrast, our method does not rely centralized controller, and we empirically demonstrate the benefit of our adaptive communication learning over rule- based baseline inspired by Chen al. (2021a). Gupta 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.
HOMOGENEOUS MARKOV GAME
with N agents indexed by E N We consider a cooperative Markov game (MG) S, [I....,N) N.. state space S, action space A = A X .... x AA,, transition function P S x A x S [0, 1]. and reward functions = (R' Jev with R : x + R for each i E N. In Section we assume full observability for simplicity, i.e., each agent observes the state E S. Under full observability, we consider joint policies, : A 00. that can be factored as the product of local policies n' S A + [0, 1J. T(ass) IIEV H' (a'ls) Let r(s,a) a) ;= N EiEN R'(s, denote the joint reward function, and let E [0, denote the discount factor. Define the discounted return from time step / as G. = -i= Przz, where r, == r(s,, dx) is the reward at time step The agents' joint policy π = (T² ,..., n N) induce a value function, which is defined as V*(ss) = B aeioo [G.]s,]. and action-value function (8,, az) E to ar+1 [Ge|s: 0r]- The agents are cooperative in the sense that they aim to optimize their policies with respect to the joint reward function, i.e., max, (TT Esg.se A0::e [Go].
3.1 HOMOGENEOUS MG: DEFINITION, PROPERTIES, AND EXAMPLES
As along as the action spaces {A' JieN are homogeneous, policy sharing among { FieN is feasible. However, such policy sharing can incur suboptimal joint policies for general MGs, we will see in an example introduced by Kuba et al. 202T) and revisited in this subsection. Here, we characterize a subclass of Markov games in Definition requiring conditions stronger than homogeneous action spaces, where policy sharing provably incurs no suboptimality.
Definition (Homogeneous Markov game). Markov game
P,
R) is homogeneous if:
(i) The local action spaces are homogeneous, i.e., A = A' Vi,j N. Further, the state is decomposed into local states with homogeneous local state spaces, i.e., = (s ..... s.V S S x ... x S with S S Vi,j E.
(ii) The transition function and the joint reward function are permutation invariant and permu- tation preserving. Formally, for any st (s!,..,,s)) &N 8141 = (8/+1, s..,,..11 s E S and ar = (at, -.,, a A. we have
P(M M Ma,) = PPM MM's M'a.). R(Mst, Ma.) MR oz)
for any M, M' M, where R(s a) (R' a),..., RN a)). Mr denotes permuta- tion M ordered list r = (x ..., x N)) and M the set of all possible permutations.
(iii) Each agent i E N has access to bijective function of S + O (i.c., each agent has full observability) that maps states to a common observation space O. These observation functions {or hev are permutation preserving with respect to the state, i.c., for any E S and any M E M.
((Ms) = M (o'(
By Definition [ besides requiring homogeneous action spaces, our characterization of homogeneous MGs further requires that the global state can be factored into homogeneous local states (condition ( such that the transition and reward functions are permutation invariant (condition (ū).. Moreover, condition (in) 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
3

---

Published as a conference paper at ICLR 2022
state with the observation functions, policy sharing incurs suboptimality. This is formally stated in Theorem 1 and proved in Appendix[A
Theorem 1. Let II be the set of state-based joint policies, i.e., II - { - (5* s..,.... x ; x² S A' + [0, 1]}, and let II, be the set of observation-bass joint policies, ie.. II fTo
(T. To To 10:00 x A' + [0, 1]3. In homogeneous MGs, we have
max
((T) T-= Jell,
max
(TT)
max JEllo x]= =
(TTO..
en
To provide more intuition for homogeneous MGs, we here give an example from Multi-Agent Parti- cle Environment (MPE) (Lowe et al. (017) and non-example from|Kuba et al. (202I). Appendix[D provides more examples and non-examples show the generality of our homogeneous MG subclass.
Example: Cooperative Navigation. In Cooperative Navigation task in MPF, 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 homogeneous MG by verifying the three conditions in Definition
(i) The local state of agent i consists of its absolute location 1' = (L2: (2) E R and its absolute velocity v² = (v vt)) E R with respect to the common origin, well as the absolute locations of all N landmarks, fch (ct ( 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 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 Ht 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 preserving joint reward function. (iii) In MPE, agents' observations are based 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 of yields the observation for agent that consists of its absolute location I and velocity v², the relative location 13 := 1 1' and velocity o/ := v o² of other agents j N \ {i), and the relative location cj. == c² l' of all the landmarks k = I,..,N.
Non- Non-Example: a stateless MG. Kuba et al. 2021 recently shows that enforcing policy param- eter sharing is exponentially than the optimality without such a restriction in the following stateless MG: Consider cooperative MG with even number of N agents, state s fixed as the initial state, and the joint action space (0. 1 1) where 1) the MG deterministically transits from state s to a terminal state after the first time step, and 2) the reward in state is given by R(s, 0//N/2 1 14-N/2:N)
1 and R(s, a I:N) = 0 for all other joint actions. It is obvious that the optimal value of this MG (in state x) is 1, while Kuba et al. (202T) prove that the optimal value under policy parameter sharing is 1/2 This MG is not homogeneous MG: the agents relying on the raw state to represent their policies, and therefore their observation functions are identity mappings o' (sss) = s, which not permutation preserving and violates Definition i
3.2 POLICY CONSENSUS FOR HOMOGENEOUS MGs
Theorem I theoretically justifies the parameter sharing among the actors with observation- bbased representations, which enables us to develop the first decentralized actor-critic algorithms with con- sensus update among local ddbservation-baseld actors.
Formally, the critic class (():w) is parameterized with w to approximate the global action-value function (-(...) Upon on-policy transition (st, (r. (rihee, $141, a(+1) sampled by the current policy, the critic parameter wt for each agent E W is updated using its local temporal difference (TD) learning followed by a consensus update (Zhang et al. 2018):
at = wi + Buss 5% (.s(s,)aaw)))
wht1 EjeN of
(1)
where ri = R (s,, ax) is the local reward of agent i, 8 = ri + 7Q(544) (((4)11, - (an is the local TD error of agent i, Batt > is the critic stepsize, and Cwit (c,, is
4

---

Published as a conference paper at ICLR 2022
Table I:
Cooperative MARL settings in prior and our work. A: Agent-specific reward, T: Team
shared reward, FO: Fully observable, JFO: Jointly fully observable, PO: Partially observable.
Reward
State observability
(De)Centralized
Memory-based policy
Section 3, and
A
FO
D
No
Zhang et al. 2018)
Sections 4 and
A
JFO
D
No
Example paper:
A
JFO
C
No
Lowe ct al. (2017)
Example paper:
PO
C
Yes
Rashid et al. (2018)
the critic consensus matrix. The observation-based actor for each agent i E A is parameterized lo'a"oo' (s); 8*) with parameter 8', which is updated based the multi-agent policy gradient derived from the critic followed by a consensus update:
0++ = 0; So. Q(s actt) Dz log x (a of (s)):
0 EEEN co.(( 07 (2)
where the observation-based actor class ((:1:;)) is assumed to be differentiable, Bo. > 0 the actor stepsize, and Co.+ [co,((t,]] j)i the actor consensus matrix.
Compared with existing decentralized actor-critic methods for cooperative MARL (e.g.. (Zhang al. 2018)), the subclass of homogeneous MGs in Definition makes it possible perform actor consensus (i.e., policy consensus) in Equation (2) that is not possible for general MGs. Theorem 2 states the convergence of {w[} and { generated by 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 {wit} and {0]} generated from Equations 7 and (2), we have lim; wi = we and lim, 0 = 0, almost surely for any i E N, where 0, is stationary point associated with update (2), and 0 is the minimizer of the mean square projected Bellman error for the joint policy parameterized by f..
Theorem 2 and its proof generalize the results in Zhang et al. 2008)) to the case where not only the crities but also the actors perform the consensus update. Please refer Appendix B which provides the exact assumptions, the convergence points, and our proof. 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 open problem. In Appendix [F] we empirically compare the actor-critic updates with and without actor consensus on toy example homogeneous MG, with the results showing that the actor consensus slightly accelerates the convergence.
4 PRACTICAL ALGORITHM
The convergence of our decentralized actor-critic algorithm in Section 32 relies the assump- tions of linear function approximators, full observability, and well-connected consensus. In this section, develop practical algorithm that relaxes these assumptions and achieves communica- tion 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 8₁ such that their observation functions {o') are not bijective. Further, similar to Network MARL (Zhang al., 2018), we assume the agents can communicate through a time-varian network G. = (N,E,) with vertex set V and directed edge set & C [(i,]) i.j E N # j}. Denote the neighbors agent at time step as Ni := (j (i.j) E E.). With agents only partially observ- ing the global state, we in Section 4.1 develop an architecture for the agents to learn to share their local observations and actions a communication efficient manner. To achieve communication
efficiency the actor-critic parameter consensus, in Section 4.2 develop an effective bi-level multi-armed bandit for the agents to learn to exchange the parameters only when it benefits learning. Table summarizes the differences between the problem settings considered in Sections and
as well as in the literature. Below we describe our key design choices, and Appendix provides implementation details of our algorithm.
5

---

Published as a conference paper at ICLR 2022
4.1 EFFICIENT OBSERVATION-ACTIN COMMUNICATION
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 8t (s)(s))EEN is bijective. For example, this joint observability is satisfied in Cooperative Navigation, where all agents' observa- tions can determine the state. Thus, each agent can use the observations and actions its own as well as from its neighbors for its critic to approximate the global action-value. To encourage communi- cation efficiency, we propose an architecture, communication network, that selects a subset C₁ S Ni for observation-action communication, such that agent i's critic becomes Q' Q'([(o,. : of )hke)e ((ke())c;)) ) For the texts below, we abuse notation of := o' (s:) to denote the observation and omit the subscript of time step t when the context is clear.
Communication network. The communication network OH of agent outputs cj E { indicat- ing whether to communicate with neighbor j E N i..., Ci [j E A : c) = 11. Specifically, we choose an L-layer graph convolutional networks (GCN) to implement C², which can deal with arbitrary input size determined by [W'| and achieve permutation invariance. Specifically, the input to this GCN is fully connected graph with one vertex (o', ()))) per neighbor j E A,, where (o') embeds information of neighbor that can be extracted from o². For example, when agents' identities are observable, (ot) can be (the embedding of) the ID of neighbor j. When identities are not observable, (o') 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 (1)) from which (c) Jeas are sampled. To enable differentiability of the sampling, we use the reparameterization trick Straight-Througe Gumbel-Softmas (Jang al. 2016).
Actor and critic networks. Our proposed communication network is compatible with any multi- agent actor-critic architecture. Our experiments mainly explore deterministic actors a = n ro'). Similar to the communication network, the critic network Q' ('((o" a²) ('e)ccc)) is also imple- mented 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 ((o", )=))Re(()Ce..
Training. Critic Q' directly guides agent i's actor update using the deterministic policy gra- dient. Critic Q' itself is updated to minimize the TD loss LiTD Bo l(Q) "))²]. where Ot := (o)..., of is the joint observation, a := (a..... a.N) is the joint action, Qi Q'(too at" k (squec)) is the abbreviated notation for the critic value of agent at timestep i, and yt := ri + 7Qi41 is the TD target. Due to the differentiability enabled by Softbel-,fttmx,, the gradient can flow from Q' to communication network C".. Commonly used in the literature (Jang et al. 2016), the update of C* is guided by regularization term a:| 1 C;I Σjec; Softmax m.
which places a restriction on the amount of communication allowed defined by rate r7.
4.2 BI-LEVEL BANDIT FOR PARAMETER CONSENSUS
requires each agent i to communicate with all other agents j where the j) entry of the consensus matrix is non-zero To achieve communication efficiency, existing literature mainly considers gossip algorithms where each agent only communi- cated with one neighbor j per communication round (Boyd et al. 2006). i.c. the consensus matrix entries satisfy e(t,)) c(i, i) 1/2. Here, we develop 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., Ni WA (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.
The parameter consensus defined in Equations 2 2
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 2 where z,, = 0, 1 corresponds to perform- ing and not-performing consensus, respectively. The low-level is (N 1)-armed bandit, and we let 2 E EN [i} denote the selected low-level arm at round m.
Arms.

---

Published as a conference paper at ICLR 2022
Rewards. We design different reward functions for the arms in the two levels, 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 G be the total rewards of episode m. To compute the reward rm for the high-level, we first normalize Gm using the latest episodes high-level records to fulfill requirement 2), followed by the rewarding or penalizing depending on the sign of normalized G 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 r can be computed by the normalization of Gm using latest episodes low-level records, then be mapped to [-1, 1j. Equation (3 shows the details.
Im t G mean (G(
22 G mean (amannGGmmm+1)mmm
Im 5- m E [x] 0),
rm 2 O. otherwise.
std(G(m (c((Gmm-+1):m))
r + / -i= - 1 [ 1).
2 m 2 sigmoid(r
rm f- 2. (igmodidd))"))) -
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 choose the adversarial bandit algorithm Exponentially Weighted Average Forecasting (Cesa- Bianchi & Lugosi 2006) to learn the bi-level bandit.
5 EXPERIMENTS
respectively: 1) How communication-efficii 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?
Our experiments aim to answer the following questions in Sections 5.1 5.3
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 = 15 agents and another with N = 30 agents. As described in Section 3.1 these MPE environ- ments can be cast as homogeneous MGs provided full observability and the permutation preserving observation functions. We set the communication range to be k 10 < 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 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 large ball
target position. There are 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-ande and-Prey: N cooperating predators (agents) are tasked to capture p preys. The preys are pre-trained and con- trolled 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, 1 = 3, 5 landmarks, & = 10, 10 other predators for = 15, 30 respectively. The observation of an agent contains its own absolute location, the relative locations of the nearest & agents (predators), the nearest p preys, and the relative location of the nearest landmark.
Baselines. We use Permutation Invariant Critic (Liu al. 2020), the state-of-the art CTDE actor- critic algorithm on MPE, as our centralized training algorithm to derive the following decentralized training baselines. Full-Communication employs all-to-all communication for both observation- action and parameters, i.e., at each time step, each agent receives the observations and actions from all other neighbors for its critic, well critic and policy parameters from all other neighbors for its consensus update. Independent learning (IL) employs no communication, i.c., each agent uses its local observations and actions only for its critic and performs no consensus update. Random selects at random 1) subset of neighbors for observation -atattiiionnnnnnnnnoooo action sharing and 2) single neighbor

---

Published as a conference paper at ICLR 2022
navigation.nl n15
navi sowigation.ogg n30
push push_n15 n.5
push_ n30
n15
prey. 030
-2000
-1400
-2000
WW
12200
200
-3000
14000
1500
-2500
-4000
50
100
116000
50
300
1100
30
100
-3000
50
100
30
100
-420
50
150
Cull-Communication
Random
Figure 1: Comparison of our algorithm with Full-Communication, II, and Random.
for gossip parameter consensus. For parameter consensus, we consider Rule-based baseline, where each agent saves a copy of the parameters from the latest communications with other agents. When agent considers doing communication at t, it calculates the ( norm of the parameters of Q' and Qi 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 paramcter is recorded by agent i. For fair comparisons, the Random and Rule-based basclines incur the same communication cost (i.c., the fraction of neighbors for observation-action communication, and the frequency for parameter consensus) as learned by our bandit method.
5.1
COMMUNICATION EFFICIENCY AGAINST BASELINES AND ABLATIONS
Figure Sarree[showws the learning curves comparing our communication-efficee decentralized actor-critic algorithm described in Section aggaistt the baselines of colll-Comuiication, II., and Random, with the observation-action communication rate set 50%. The results clearly verify the importance of observation-action and parameter communication, as mull-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 bascline that uses the same amount of communication in almost all the tasks, and achieves performances comparable with Full- Communication in several tasks. Remarkably, Random barely outperforms II in Cooperative Push, suggesting that efficient communication for decentralized training is challenging.
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 cull-Communication Predator-and- Prey, and behaves comparably to parameter consensus using Full-Communication in Cooperative Push, using random parameter consensus and Rule-based parameter consensus Cooperative Nav- igation. Noticeably, the Rule-based algorithm behaves similar to the Random parameter consensus baseline in the three scenarios. possible explanation is that the parameters of the other agents an agent records are outdated, 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:
Ablation: observation-action communication. In Appendix G nication rate other than 50%, and the results show that our method dominate the baselines across various choices for the communication rate.
also experiment with commu-
5.2 EFFECTIVENESS OF POLICY CONSENSUS
Theorem 2 aassures that policy consensus in distributed actor-critic methods for Homogeneous MGs provably converges to 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 sepa- rately consider 1) the setting where the agents employ all-to-all communication for their critics and
8

---

Published as a conference paper at ICLR 2022
nevigation_ni _15
push_n15
prey_nis
navigation
push, n115
prey_nis
-186
Ours Das Moseriee
traning (241)
260
Dun
Figure 2: Comparison of parameter consensus by Figure 3: Comparison of learning with and w/o our bandit with Random and Rule-based.
policy consensus.
navigation_nis
Figure 4: Y: communication rate. X: training step (log scale). Communication rate for the 10
neighbors in Cooperative Navigation (N = 15), with the distance increasing from left to right.
parameter consensus, such that the assumptions of full observability and well-comnected consensus matrices Theorem 2 are satisfied, and 2) the setting where the agents learn to communicate effi ciently with our communication network and the bandit. The results in Figure 3 show that policy parameter consensus is always beneficial with our communication-efian ingly, negatively impact the training with all-to-all communication (c.g., Predator-and-Prey One plausible explanation is that, while it might speed up convergence, policy parameter consensus harm exploration, leading to worse local optima.
method and, surpris-
5.3 QUALITATIVE ANALYSES OF THE LEARNED COMMUNICATION RULE
We first qualitatively examine the observation-action communica-
tion rule learned by our communication network. We plot the output of our communication network, i.e,, the probabilities of communi- cating with the k 10 distance-sorted neighbors, as the learning progresses. Interestingly, the rule learned by communication network encourages communicating with the nearest neighbors. For example, in Cooperative Navigation with the 50% communication rate as shown in Figure the probabilities agents communicat- ing with nearest 5 neighbors nearest agent, around 0% for the other neighbors. We provide the counterparts of Figure all the environments in Appendix [
prob of param cancersus
2.8 024
75%, around 25% for the 6th
10
12"
training step (log scale)
Figure 5: Probability of com- munication in the high-level bandit across all environ- ments and seeds.
Figure 5) shows the probability of choosing the high-level arm of performing consensus the learning progresses, averaged across the runs of all the environments. The result shows that, with the de- signed bandit's 's reward function, the average probability of selecting to communicate decreases from around 50% to less than 10%.
6 CONCLUSION
In this paper, we characterize a subclass of cooperative Markov games where the agents exhibit 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 tech- niques 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 basclines in terms of communication efficiency.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
We thank the anonymous reviewers for their thoughtful comments and supportive discussion. We thank Yan Zhang for an early discussion on this work.
REFERENCES
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, (2(6):2508-2555 2006.
Duncan S Callaway and Ian A Hiskens. Achieving controllability of electric loads. Proceedings of the IEEE, 19)1:1844119, 2010.
Nicolò Besa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. 2006. ISBN 978-0-
521-84108-5. doi: 10. (0.101//C809780511155
Tianyi Chen, Georgios Giannakis, Tao Sun, and Wotao Yin. Lag: Lazily aggregated gradient for communication-efiin -effriinnneffi distributed learning. Advances in neural information processing systems, 2018.
Tianyi Chen, Kaiqing Zhang, Georgios B Giannakis, and Tamer Basar. Communication policy gradient methods for distributed reinforcement learning. IEEE Trunsactions on Control of Network Systems, 2021a.
Ziyi Chen, Yi Zhou, Rongrong Chen, and Shaofeng Zou. Sample and communication--ffiiienn decentralized actor-critic algorithms with finite-time analysis. arXiv preprint arXiv:2109.03699 2021b.
Tianshu Chu, Jie Wang, Lara Codecà, and Zhaojian Li. Multi-agent deep reinforcement learning for large-scale traffic signal control. IEEE Transactions on Intelligent Transportation Systems, 21)) 1086-1095, 2019.
Peter Corke, Ron Peterson, and Daniela Rus. Networked robots: Flying robot navigation using sensor net. Robotics research. The eleventh international symposium, pp. 234-243. Springer, 2005.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. arXiv preprint trXiv:1705.0892 2017.
Shubham Gupta, Rishi Hazra, and Ambedkar Dukkipati. Networked multi-agent reinforcement learning with emergent communication. arXiv preprint arXiv:2004.0273) 027800 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizzatio with gumbel-softmax. arXiv preprint 1rXiv:1611.011 2016.
Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint arXiv:2 122.1 2021.
Iou-Jen Liu, Raymond A Yeh, and Alexander G Schwing. Pic: permutation invariant critic for multi- agent deep reinforcement learning. In Conference on Robot Learning, pp. 590-602. PMLR, 2020.
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- agent actor-critic for mixed pnperaativecompetttvvv environments. In Advances in neural infor- mation processing systems, pp. -379, 2017.
Duc Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. Collective multiagent sequential decision making under uncertainty. In Thirty-First AAAI Conference on Artificial Intelligence, 2017a.
Duc Thien Nguyen, Akshat Kumar, and Hoong Chuin Lau. Policy gradient with value function approximation for collective multiagent planning. (2017). Advances in Neural Information Pro- cessing Systems: Proceedings of NIPS, pp. 4-9, 2017b.
10

---

Published as a conference paper at ICLR 2022
Bei Peng. Tabish Rashid, Christian A Schroeder de Witt, Pierre-Alexadee Kamienny, Philip HS Torr, Wendelin Böhmer, and Shimon Whiteson. Facmac: Factored multi-agent centralised policy gradients. arXiv preprint arXtv:2003.06709, 2020.
Peng Peng, Ying Wen, Yaodong Yang. Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent pnnrecttioaaly-ccordintteee nets: Emergence of human-level coordination in learning to play stareraft combat games. arXiv preprint
2017.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foer- ster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint PvrXiv:8803. 1485, 2018.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. arXiv preprint 0rXiv:18/2.097555 2018.
Sainbayar Sukhbaatar, Arthur Szlam, and Rob Fergus. Learning multiagent communication with backpropagation. arXiv preprint 1rXiv:660.007766 2016.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In In Proceed- ings of the Tenth International Conference on Machine Learning, pp- 330-337. Morgan Kauf- mann, 1993.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In International Conference on Machine Learning, pp. 5571-5580. PMLR, 2018.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. In International Conference on Machine Learning, pp. 5872-5881. PMLR, 2018.
Sai Qian Zhang, Qi Zhang, and Jieyu Lin. Efficient communication in multi-agent reinforcement learning via variance based control. arXiv preprint arXiv:1909.0266 2019.
Yan Zhang and Michael M Zavlanos. Distributed off-policy actor-critic reinforcement learning with policy consensus. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 4674- 4679. IEEE, 2019.
11

---

Published as a conference paper at ICLR 2022
A PROOF OF THEOREM 1
The set of bijections her induces a one-to-one mapping between and IT,, and therefore
the first equality holds. For the second equality, consider an arbitrary state = (s) ( s E S and the permutation M that swaps pair of agents (i,j), such that Ms = M (..,,5 s ..... 8) ,..)
(..., (Ms)
..., (Ms)²
...).. Due the permutation invariance of the transition and
reward functions by condition (i) of Definition I there exists an optimal wate-based joint policy TT II such that T: (-18) rd (-MMs. Consider the corresponding optimal observation-basee
joint policy Too E II, that the bijective mapping of ua, such that (-1o = (-(sss and
Tho(- (Ms)) = (-IMs) We therefore have
(-o((((())) = (-o (Ms)).
(4)
Further, since {or) JEN are permutation preserving by condition (iii) of Definition 1 of (Ms) E O in Equation (4). Since Equation (4) holds for arbitrary s E S and i.j E., and thus follows that
we have o' (s)
(-10) (-1) Vo O,
(5)
i.e. the second equality holds. This concludes the proof.
A.1 ILLUSTRATIVE EXAMPLE FOR THE PROOF
gt = (L,4)
ga of = (M.9)
(M,
(1223)
pormute
(3.1,)
8 <" (R.
5 (8,4)
8" s' (1,4) (VAA)
ol (1VA)
(764)
(o1,0%,0)
Defivition
(0%
(MAV)
(AAV)
(ARA) =
(
m (o =1 (o)) ( ( (o =1= m!,(a²)
mlo(o) xloo0) v(...)
(
Figure 6: An illustrative example for the proof of Theorem Please see the text for details.
We here provide illustrative example in Figure 6 to aid the proof. The example Markov game consists of three agents i E (1, 2, 3) placed on the left (L), middle (M), and right (R), one in each position, with triangle placed in front of each agent that is either pointing up (A) or down (v). The agents have homogeneous action spaces 41.
The agents also have homogeneous local state spaces (L, x {A, 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 the A is even, reward is when the agents behind A choose to go up (f) and the agents behind V choose to go down ()); 2) if the number of the A is odd, reward +1 when the agents behind A choose to go down (L) and the agents behind V choose to go up (t): 3) reward is 0 otherwise. Thus, the Markov game satisfies Definition [
The agents' local observations preserve their absolute positions (i.e., I., M, or R) and consist the three shapes ordered clockwise starting from the shape right in front. For example, the local obser- vation of agent = 1 on the left of Figure is o² = (L, A v A). As verified by the second row in Figure 6. the local observations are permutation preserving satisfy Definition 11I) Therefore, the Markov game is homogeneous by Definition [
The third row in Figure 6 verifies Equations
S that are key to the proof.
12

---

Published as a conference paper at ICLR 2022
B PROOF OF THEOREM 2
B.1 ASSUMPTIONS
We make the following assumptions that 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 linear, i.c., Q(s, a; w) ó(s, a)T w. where ( a) E R the feature of (s, a). Further, the feature vectors d(s, IR are uniformly bounded by any (s,a).
The feature matrix & [[SS]AA has full column rank.
Assumption 3. The stepsizes Sw,e and So. satisfy
Bw E. Bo, 20, E.pe,t 0o, E.Po. < co, BB, = (Bw.)).
In addition, lim; Sw,
Assumption 4. We assume the nonnegative matrices C {Cw.s Co,e) satisfy the following condi- tions: (i) C, is row stochastic (i.e., C,1 1) and [[C, is column stochastic (i.e., 1 [TC[C 1
for >>> 0; (ii) The spectral norm of (WW (I - * W;] is strictly smaller than one; (iii) We and (s;, (ri)) are conditionally independent given the o-algebra generated by the random variables before time t.
Assumption 5. The critic update is stable, i.e., sup, |ww|| < co, for all i. For the actor update, {0:} belongs to a compact set for all and t.
B.2 CRITIC CONVERGENCE
In this subsection, we establish critic convergence under fixed joint policy in Lemma 3 cally, given fixed joint policy = (m',..., T²), ), we aim to show that the critic update converges to Wa, which the unique solution the Mean Square Projected Bellman Error (MSPBE):
Specifi-
We = arg min (h IIT (TT=
which also satisfies
+ T DD [T- [w,] 0,
where Tx is the Bellman operator for π, II is the projection operator for the column space of 4 and Dr = diag dd (s. E S, a E A] for the stationary distribution d- induced by w.
Lemma 3. Under the assumptions for any give joint policy म, with distributed critic parameters w| generated from Equation | using on-policy transitions (St, at Tt, 8t-1; ac+1) ~ we have lim; W = Wy almost surely (a.s.) for any N. where wa is the MSPBE minimizer for joint policy
Proof. We use the same proof techniques as Zhang et al. (2018).
Let o, o(s,, a,), &, [6] ...,, 6, and W: [w] .... W The update of we in Equation
can be rewritten in a compact form w++1 (Cw,t @ 1) [w; + B. where @ is the Kronccker product, I is the x K identity matrix, and yt = [8] (:) IR KN + R
ot al E RKN. Define operator
1 (w) = N (1 @D
Σ IEN
N
for any ~ = ((-1)T ()T E RRN with w R for any N. We decompose w, into its agreement component 1l @ (wr) and its disagreement component Wi,t Wi W1,1 (1)) a.e, 1 & Wn we next show Wi, a.a, and (1)) a.a, we respectively.
1 6 (wx). To prove
13

---

Published as a conference paper at ICLR 2022
Convergence of wi,t " 0. We first establish that, for any M > 0, we have
sup E
|لW (sup, lwo co.
(6)
To show Equation 6 let } be the filtration of Fi O Or Wr, Cu.r-1:7 S t), J
N (11 @ I) such that Jur @ (wx), (I J)w Wh,e. The following facts about % will be useful:
(A (C & D) (AC) @ (BD)
This enables us write w1,++1 as
W1 W1,+1 =(1 J)wr+1
=(1 - J) [[Cw @ [) + Sw,t
= [I J) [)C( : & [) @ (wx) + tLie + (1))
(By Equation 7 and Assumption
F we have (Cu, @ [) @ (w)) = (Cu,))) @ (41)
=(1 J) [1 (wi) + (Cw. @ (W + Sw,t
=(1 - J) [[Cw., @ 1)(W1. + Bw))
((1 (I-J)(1 @ (w)) = 0)
=[( - /NT @ [[wa @ (WW + (8))
(1 J
11 (1-
=I(1 11 1 C,, @ 1](WL, + (w)
(By Equation 7
We then have
E
(1 1| [i
(||=112 ITa
x, A (I -11 /NNC/NCC & I, A= - -I /1T/N)Cuu 8T)
Si, E (B0t +.) T (C 11 /N)C/ & 1) (S5, + uz) | |Ft
(A CJ, - 11
B 1,1|4
|||||| BBI
(x TcTAs Ax = AaTAAll) s ||= |Alll |||||| = ||||| - xx)
(Ca,t and (t) are independent conditioning on F.)
< B pl ( + v.) (BT + 31) Fi
(where p is the spectral norm of E[C (I 11 CN)C
Be,
(I
[1 || Fr 2 (1 M1) [F] E [1 1Ft
Ba
(By Cauchy-Schwarz Ku, v) ||||| [|ul])
L [E |
|
+ 2E [|| llvell [ + |Isell? | (Fil)
8 W.1+1
(Quantities are deterministic given Fi)
B2, B3
/ (11 1|?
|| |l [1ye ll + [lbel
FFl with o = + ro, w/ w. by Assumptions and the rewards r, and the features di are bounded, and thus we have that [T]lvvl' 11 [J.]] bounded on set {sup,<: ||wy|| < M) } for any given M > 0. We can then following the proof of Lemma 5.3
Since [| [FF. = EI |/
in Zhang et al. (2018) and its sequel to show Equation 6 and conclude the step of W a.e. 0.
14

---

Published as a conference paper at ICLR 2022
Convergence of (wi))
_ Wx.
We write the update of (we)
(W++1)
& Twr+1
N
1
@ 1) [(Cu,t @ () @ (w)) twia + Bw.)
(wwr) + ( @ (iv + (w))w))))
(By Equation 7
We rewrite the above update as
(We+1) [ww) [66)) Fil Sw & =(Cuuu @ (y= + 80, ,)) - (()))) Fi]
(9)
where
We can verify that the following conditions hold (with probability 1) regarding the update of (wx) in Equation
1. E (6) Fr) is Lipschitz continuous in (wz))
2. & martingale difference sequence and satisfies B[ll@++1|| 1| [F] S K(1 + [|well]) 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 g related to its corresponding ODE (see Theorem B.2 in Zhang et al. 2018)):
(w) Σ (s, (0))ols)
Σ d= B. [(r(s, + 70
(s, (o x (s, ((s,))|s,a)
+ 1)) (w) +
D.R
Note that PT T) has all eigenvalues with negative real parts, does (Φ Dr T) since is assumed to be full column rank. Hence, the ODE is globally asymptotically stable, with its equilibrium satisfying
Φ DD R + PT (w)( = 0,
which is the MSPBE minimizer, i.e., (w) Wr. This concludes the step of (wi) ena wi and the
proof Lemma 3
L
B.3 ACTOR CONVERGENCE
In this subsection, we establish the convergence of actor update with critic parameters w/ 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 {w/) and (0,) generated by Equation and
Equation 2
Let (
(ON)T] and wi be the critic convergence point for joint policy parameterized by 0 as established in Lemma 3 Define
A ((tt, azs we)
vii V log n' (atlo"
for arbitrary 0. We study the variant of Equation 2 where w/ is replaced by wa,:
Ai.o =Q(st, (ajwwa wa,)
vi. V log (a/lo' (s)))
Ø: = 30. Ai,o, vi.
0: 1+1 Σ co.(i,,)
(10)
JEN
15

---

Published as a conference paper at ICLR 2022
which can be rewritten as
Bct1 (Co,+ @ (), + -0,
where yt,o, [(A,,, V2o0) , v ]T.
Similar to the critic convergence, we make the decomposition 0, -0, & (0.) and then show 01. ", and convergence of (0,) respectively.
Convergence of O1, - O. In light of the argument for wi,t 0... 0 in the proof of Lemma 3
suffices to show that the the boundedness of yr,a, Here, v/,,, [(A),,, v ..... (A 1i,00 bounded because Ai,o, (st, ax; wo,) is bounded since wa, the MSPBE minimizer; (2)
vi.. is bounded since by Assumption 5 it is a continuous function over a compact set.
Convergence of (0.). We write the update of (0t) in Equation 10 as
(0.+1) @ 1)
(1 1) [[Co, T) (0.) +11+ + -o,
= = + S0. (CC,, & DV,, + P0.1111) (By Equation
We rewrite the above update as
(0c+1) (0a) + B9, Be
Ky),.) Fil + A0,
where E ( @ (3,. + 0g. 01.)) Be (or [yy.,,)) [F]
where F: = 000, (), (, is the joint policy where each individual policy is parameterized by (0t). Note that & is martingale difference sequence. By Assumption 5 & is bounded and further by Assumption we have E. Ee < oc. By arguments the proof of Theorem 4.7 in Zhang ett al. (2018),
apply Kushner- Clark lemma and conclude that (0t) converges almost sure to point in the set of asymptotically stable equilibria
(0) Esrndios arai [(v), = Esenddess (8
Σ Ai.oo vir
16

---

Published as a conference paper at ICLR 2022
C VISUALIZATION OF THE LEARNED COMMUNICATION RULE
navigation
navigation
push n15
push
push_n30 n30
prey_n15
prey_n30
Figure 7: Y-axis: average communication rate. X-axis: training step in log scale. The average communication rate for detectable 10 nearby agents, with the order increasing distance from left to right.
17

---

Published as a conference paper at ICLR 2022
D EXAMPLES AND
OF HOMOGENEOUS MG
D.1 EXAMPLES
MPE tasks with homogeneous agents. We have explained 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
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-an 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. 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 87, 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 uyip.type. Thus, an SMAC scenario with homogeneous ally units is similar to MPE's predator-and andaa in the sense how it satisfies the conditions in Definition [. 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 (
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 Unlike team sports, these vehicles are unnecessarily cooperative, but their reward functions are permutation invariant to satisfy Definition
naturally forms their observations that satisfy Definition [
Surveillance with drones. Drone surveillance is an application of cooperative MARL, where set of (homogeneous) drones is tasked collectively monitor 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
D.2 NON-EXAMPLES
MPE tasks with heterogeneous agents. As the counterpart of Cooperative Navigation with ho- mogenous agents, Liu et (2020) introduce heterogeneous navigation where half of the agents are small and fast and the other half are big and slow. In such MPE task, the transition function is not permutation invariant, and therefore it is not 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 homogencous MG. These SMAC scenarios include 2s3z, 3s5z, MMM2, etc.
Multi-Agent MuJoCo In MuJoCo task, robot aims to learn optimal way of motion. Multi- Agent MuloCo (Peng et al. 2020) controls each part of the robot with an agent, for example, a leg for spider. Since the parts of robot are heterogeneous, Multi-Agent MuloCo can violate condition
i of Definition [
18

---

Published as a conference paper at ICLR 2022
E
IMPLEMENTATION DETAILS
E
ARCHITECTURE OVERVIEW
agmip
agesca
Sof tmmax)
ci -
=1- k,
Cill -i
Lof of
(CGCN)
dinjoo
agest
i ot
agenc
w6-e/o0 (16)
ob
da eloo
Figure 8: As an illustration, suppose there are agents (i,j, k; (. At time step agent receives the observation of which contains information about three neighboring agents: j, k and 1. Then, agent uses its communication network C' (GCN) determine which observable agents worth communicating (agent k and / in this case) by the complete graph of agent j. & and I. Agent and the selected agent and forms complete graph which fed into the critic Q' (GCN).
19

---

Published as a conference paper at ICLR 2022
E.2 PSEUDOCODE
Algorithm Pseudocode of our communicationn-effiieeee actor-critic algorithm
1: init {C")
Ti=1: [Q'] {
N J== memory, {records) i=1: {records), 1.N /i=1
[i=1
2:
for episode m 1,2,... do
3:
for agent i 11,2.... N do
4:
sample zm from agent i's high-level bandit. if x = 0 then
5:
6:
sample z;, from agent i's low-level bandit. Agent does parameter consensus with agent x
7:
8:
end end for
9:
10:
Gm =0
for t
1, ..... do Get 0c+1, Fi by interacting with the environment; Put 0r+1, into the memory.
12:
G. c Tt +G
14:
end for
if len (memory) > batch.sizz then for i- 2, N do
16:
17:
sample a batch from memory. eritic
18:
P Loss for agent i's critic and comm net.
19:
for oi, ot 1. rffiin in batch[i] do
20:
C; t (ot), Ci+1 + (o(())
21:
Qi Q'((oof de) Q Q'(1(o[(11 (ft
22:
3/ = +
23:
1 Jemee t Lenic + (Q vt)² + al पमे Ejec; Softmax(!y) nl
end for
25:
enttic f- / batch_size
26:
Send T to the Adam optimizer for the update.
end for
28:
for i 1.2...., N do
sample a batch from memory.
30:
actor
0
Loss for agent i's actor.
31:
for of in batch[i] do
32:
n' (o;)
33:
C. - (oi), & (o(41))
34:
Q + Q'(oof at) (e)
35:
y lactor 1a Qi
36:
end for
37:
75 Lictoon batch bbtch size Send lictor to the Adam optimizer for the update.
38:
39:
end for
40:
for agent i 1, do
41:
Push Gm into records)
42:
Keep the latest elements of records),; Compute r designed in Update agent i's high-level bandit by ry.
43:
44:
if x! = 0 then
45:
Push Gm into records).
46:
Keep the latest elements of records); Compute r designed in Update agent i's low-level bandit by the r
48:
end if
end for
50:
end if
51:
end for
20

---

Published as a conference paper at ICLR 2022
E.3 HYPERPARAMETERS
Table 2: Hyperparameters
Hyperparameter
Value
Episode length
25
Number of training episodes
40000
Discount factor
0.95
Communication network architecture
Concatio', (obs dim))-GCN (2aaaayyer2222-FC((()Gunnaaaaa
Communication network optimizer Critic network architecture
Adam with learning rate 0.001
-CCggGCNNNyNN -CN_layer--F(((28)
-GNN CCN..lyyr2-FC(1200 (C(1128)-Max.poo-FCCC/
Critic network optimizer Policy network architecture
Adam with learning rate 0.01
o
dim)
Policy network optimizer Gumbel-Softtax temperature
Adam with learning rate 0.01
Batch size from replay buffer Frequency of evaluation
256
per 1000 episodes
#Latest episodic rewards bandit store
10
Regularization for the communication network (a)
searched in
21

---

Published as a conference paper at ICLR 2022
F EXPERIMENTS ON A ToY EXAMPLE OF HOMOGENEOUS MG
= 10
N = 50
1.0
1.0
0.8
0.8
Reward
0.6
Reward
0.6
0.4
0.4
w/ actor consensus
0.2
w/ actor consensus
actor consensus
w/o actor consensus
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
1.0
Training Step (1e5)
Training Step (1e6)
Figure 9: Learning curves on the toy example.
Theorem 2 proves the asymptotic convergence of our decentralized actor-critic updates in Equations ( with actor consensus for homogeneous MGs, which generalizes the asymptotic convergence result without actor consensus (Zhang al. 2018). While the actor-critic updates converge asymp- totically 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 up- dates in Equations 2 with and without actor consensus 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 2021 in Section 3.1 example. we augment each agent i with unique local state 8", then it is easy to verify that these local states satisfy Definition
(ii and it is ease construct local observations, o² (s', s.)
that satisfy Definition
(ii) such that the MG becomes an example of homogeneous MG.
Results. We define the unique local states by the trigonometric function, s² cos x-) T),
N,..,NN. N. We use feature function 6(8, a) = concat|fs* hoo_)) for the linear critic, and parameterize the actor as linear function of of 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) = mean, 20 [a = 1]] moan [I 1]}, such that the optimal joint action a²
for S N/2 and a' = for i N/2 that gets reward of +1, and 2) instead of using the decaying stepsizes suggested Assumption 3 which we found not effective for training, we use the optimizer Adam for adaptive learning rates. Figure 9 show the results for N = 10, 50. While both converge, actor consensus slightly improves the learning efficiency.
22

---

Published as a conference paper at ICLR 2022
G EXPERIMENTS WITH VARIOUS AMOUNTS OF COMMUNICATION
Navigation n15
Push n15
Push n30
Frandomralt_
Irandomrralt_eece
Frandom.rafe
2000
2000
episodic reward
-200
episodic reward
-1350
episodic reward
-2200
22400
-1400
-2600
-1450
2800
-1500
-2600
11000
2800
20
60 100
20 40
80
100
20
60 100
observation-actionn comm %
observation-action comm %
observation-action comm
Figure 10: Performance of our algorithm and the baselines under different observation-action com- munication thresholds. For fair comparison, the frequency of doing parameter consensus is the same for all the algorithms under different observation-action communication budgets. The error bar cap- tures the standard deviation of the mean performance of the last 5 training policies (at 9e5, 9.25e5, 9.5e5, 9.75e5, 10e5 steps) across 4 seeds.
23


Reviews:
[{"review_id": "rQwxdLOA8Tl", "reviewer": "Reviewer_WXRa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I felt that the paper provides some new insights and perspectives on whether policy sharing will incur sub-optimality in MARL. Specifically, when the MDP satisfies the conditions in Definition 1, there is no loss of optimality by searching a shared/same policy among agents. \n\nHowever, for the reason below, I felt that the paper is not ready to publish in its current form. \n\n1. Since the convergence results of this paper essentially is a special case of [R1], the main contribution lies in identifying the subclass of MDP in which policy sharing will incur sub-optimality. However, this needs better elaboration. Specifically, proof of Theorem 1 in Appendix is hard to follow. It would be better if authors can better elaborate the proof and clarify the intuition on this. \n\n2. It is not clear how general this subclass of MDP/MG is. From now, authors only provide the cooperative navigation example, which seems quite restrictive. If authors can justify the generality of this class, it will add more value to this work. \n\n3. The theory of this work is rather work. I would be good if authors can quantify the theoretical benefits of using policy sharing relative to no-sharing policies in [R1] if there is no optimality loss of search a shared policy. \n\n4. There are in fact many work on communication-efficient multi-agent RL. A more detailed literature review might be needed, e.g., [R2], [R3]. \n\n5. Some minor issues. Markov game usually refers to agents with competing objective functions, but it is treated as cooperative games in this paper. In Theorem 1, should $\\pi_o^i: S \\times O \\rightarrow [0, 1]$ be  $\\pi_o^i: O \\times A\\rightarrow [0, 1]$?\n\nReferences: \n\n[R1] Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning, pp. 5872–5881. PMLR, 2018.\n\n[R2] Tianyi Chen, Kaiqing Zhang, Georgios B. Giannakis, and Tamer Başar. \"Communication-Efficient Policy Gradient Methods for Distributed Reinforcement Learning.\" arXiv preprint arXiv:1812.03239 (2018).\n\n[R3] Gupta, Shubham, Rishi Hazra, and Ambedkar Dukkipati. \"Networked multi-agent reinforcement learning with emergent communication.\" arXiv preprint arXiv:2004.02780 (2020).\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "Overall, I felt that while the paper provides some new insights and perspectives on policy sharing in MARL, it needs additional efforts to be accepted in top conferences.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ljWBhv-ceP", "reviewer": "Reviewer_HWuo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros: \n\n(1) A new subclass of cooperative MARL is proposed.\n\n(2) Both the new algorithm in Section 4.1 and transforming technique in Section 4.2 strategically select the important communication links, which reasonably improves communication efficiency. \n\n(3) Networks for communication, actor and critics are very general: Both use neural networks and the networks for communication is time-varying. \n\n(4) There are abundant experiments.\n\nConcerns: \n\n(1) **I found your method seems to be significantly outperformed by full-communication in Figure 1 \\& 4 and the left two subfigures of Figure 2. You might add figures with the number of communications as x labels. Hopefully your method can outperform all the others in the new figures.**. These additional figures might be put in Appendix if the page limit does not allow. \n\n(2) In Figure 2, the blue line means ours with bandit, right? If so, your statement that it outperforms ours with full communication (green line) in the Cooperative Push task looks incorrect. \n\n(3) In the example of cooperative navigation in Section 3, the observation function $o^i$ seems not bijective which is required by Definition 1, since $o^i(\\ell,v)=o^i(\\ell+c_1\\mathbf{1},v+c_2\\mathbf{1})$ for any $c_1,c_2\\in\\mathbb{R}$. Do the Cooperative Push and Predator-and-Prey in your experiment fit your Definition 1? Are there more examples that fit your Definition 1? \n\n**The above three concerns are the major reasons why I reject this paper. If you solve them, I will change to accept.**\n\n(4) The introduction said \"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 non-stationarity caused by other learning agents’ evolving policies. \" A counterexample might be [1] which proposes a fully decentralized algorithm for cooperative MARL, where each agent only knows and independently learns its own policy. Despite non-stationarity, [1] still obtains efficient finite-time sample complexity and communication complexity. What do you think is your advantage over [1]?\n\nReference:\n[1] Chen, Z., Zhou, Y., Chen, R., \\& Zou, S. (2021). Sample and communication-efficient decentralized actor-critic algorithms with finite-time analysis. ArXiv:2109.03699.\n\n(5) The TD step (1) seems to use the actions of all the agents, which in many cases are private and sensitive information that agents do not want to share. \n\n(6) In Figure 1, Which version of your method is used? (e.g. has bandit? ) Why is the Rule-based parameter consensus not shown?\n\n(7) At the end of Section 4.1, the regularizer contains binary variables $c_j^i$ randomly obtained from the logits (output). How did you compute the gradient of $c_j^i$ in back proporgation? You might consider the average of the output logits. \n\n(8) At the beginning of Section 4.2, I do not understand why equations (1) \\& (2) require the communication matrix without zero entries. I think Assumption 4 in Assumption B.1 allows some zero entries. \n\nMinor comments:\n\n(1) To my knowledge, the name \"Markov game\" is usually used to define **competitive not cooperative** MARL. You might use \"cooperative MARL\". \n\n(2) In the second item of Definition 1, the permutations $M_i$ and $M_j$ are not associated with agents $i$, $j$, right? If so, you could use notations like $M$ and $M'$ without index. \n\n(3) In the example of cooperative navigation in Section 3, are landmarks fixed or moving? If the former, then their locations $c^k$ are better not to be considered state variables since state variables form a Markov chain.\n\n(4) In the equation in Theorem 1, the two $\\subset$ should be $\\in$, and for the third $\\max$, you could use $\\pi_o=(\\pi_o^1,\\ldots,\\pi_o^N)\\in\\Pi_o: \\pi_o^1=\\ldots=\\pi_o^N$. Also $\\pi_{*o}^i$ defined in the proof of Theorem 1 is a function from $\\mathcal{O}$ to $[0,1]$, not from $\\mathcal{S}\\times\\mathcal{O}$. You may need to accordingly adjust that in Theorem 1.  \n\n(5) In the non-example, the joint action space is $\\{0,1\\}^n$ (add $\\{\\}$). Also should the maximum value without policy sharing be $\\sum_{i=0}^{\\infty} \\gamma^i \\cdot 1=\\frac{1}{1-\\gamma}$?\n\n(6) Right above Theorem 2, it is better to tell the specific appendix section (e.g. Section B.1) in \"(refer to the appendix for details)\". \n\n(7) In Assumption 3 in Appendix B.1, do you really need $\\sum_t \\beta_{\\omega,t}^2=\\sum_t \\beta_{\\theta,t}^2$? \n\n(8) In \"Communication network\" on page 5: What's the difference between $C^i$ and $\\mathcal{C}^i$? In \"The GCN's last layer output the ...\", use \"outputs\". In \"which can deal with arbitrary input size determined by |Ni| achieve permutation invariance\" whose grammar seems incorrect, do you mean \"to achieve\" or \"and achieve\"? \n\n(9) In Section 4.1, you might add words like \"(refer to Appendix ??)\" to clarify the details of the neural architectures and training process to make the algorithm more reproducible, and add the corresponding appendix sections. \n\n(10) At the beginning of Section 4.2, you might use \"Equations (1) \\& (2)\". It currently looks like (12). \n\n(11) In Section 4.2: It is better to define by equation. In $r_{m} \\leftarrow \\frac{G^{m}-\\operatorname{mean}\\left(G^{m-l+1: m}\\right)}{\\operatorname{std}\\left(G^{m-l+1: m}\\right)}$, you might add parenthesis to $m-\\ell+1$, as it might be misunderstood as $m-\\ell+(1:m)$.\n\n(12) If feasible, a finite-time (non-asymptotic) result with convergence rate, sample complexity, and communication complexity is preferred.", "summary_of_the_paper": "This work proposes (1) a new subclass of cooperative MARL named homogeneous Markov game; (2) the first decentralized actor-critic algorithm with both policy sharing and provable convergence; and (3) a practical technique that transforms centralized training algorithms to their decentralized and communication-efficient counterparts by using bandit to select communication links per iteration. Experiments demonstrate its communication efficiency while preserving comparable performance with full communication. ", "summary_of_the_review": "This work makes multiple innovations, as aforementioned in my summary and pros. However, the first two concerns imply that the advantage of the proposed algorithm does not seem to be well supported by experiments, and the third concern seems to imply lack of practical examples for your proposed homogeneous Markov game. Hence, I tend to reject. **Once you figure out the first three concerns, I will change my score to accept.**", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TYQa_DzRBx3", "reviewer": "Reviewer_eGTR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n- I like that the paper addresses the importance of communication during training which is ignored in the mainstream CTDE approaches. This potentially has impacts when full centralization of training data is not possible, but some amount of data sharing is still feasible.\n- I appreciate the theoretical analysis of policy sharing, a practical technique that is often used in MARL but so far not fully understood why or when it works well. I think the paper lays a nice grounding for this for the fully observable setting, by defining cases where policy sharing will preserve policy optimality.\n\n## Weaknesses\n1. The theoretical analysis for the partially observable setting is lacking. Since the paper looks at reactive or memoryless policies, it cannot make any theoretical claims about optimality preservation in the partially observed case (see also detailed comments). While analyzing the fully observable case is valuable, the paper could be much stronger with an appropriate analysis of the partially observable case.\n2. The paper should make a stronger link between the theory and empirical results. Now, all experiments are in domains that break some of the assumptions for the theory. The paper could benefit from experiments also in a simpler toy example where hypotheses could be verified. The connection of the policy sharing and communication aspects of the paper could also be clearer. See below for further comments.\n3. The paper should discuss the relation of the homogeneous MG to other formulations where agent identity does not affect the reward or transition, or policies are averaged or a consensus is condiered, such as 1) Collective Dec-POMDPs, Nguyen et al., \"Policy gradient with value function approximation for collective multiagent planning\", NIPS 2017, or 2) Yang et al., \"Mean Field Multi-Agent Reinforcement Learning\", ICML 2018, to mention a couple of examples.\n\n## Detailed comments\n- The connection of the policy sharing and communication aspects of the paper could be clearer. I think both are useful topics to consider, but I think I am missing why joint treatment in a single paper for both is helpful. Maybe the authors could help clarify this for me.\n\n- In a standard Markov game (and the cooperative MG defined in the paper), the state is observable by all the players. Why do we need to postulate the existence of a common observation space in Definition 1 (iii)? Is it not enough to work with the permutation invariance w.r.t. state to prove Theorem 1 (for state-based policies)? \n\n- The examples in 3.1 give valid reasoning about the practical importance of the common observation space, but I find the overall presentation somewhat confusing given that at the start of Sect. 3 it is stated the section only concerns the fully observed case. The same conflation of full and partial observability also appears in 3.2. To be clear, I think the results are correct for the fully observed case, but the presentation is confusing and should be improved.\n\n- The paper should be very careful about treatment of and claims about the partially observable case, since the analysis is not performed in the Dec-POMDP framework. The paper cannot make any claims to preserve optimality in the partially observable case, simply because it already foregoes optimality by restricting to memoryless policies (specifically, policies that depend only on the latest observation, not the history of observations/actions). Perhaps the best memoryless policy is preserved under the conditions given in the paper, but this may be arbitrarily worse than an optimal policy.\n\n- I am not an expert in networked MARL methods, but I could not quickly decipher how Theorem 2 differs from Theorems 4.6 and 4.7 in Zhang et al. (2018), or if this is a statement of the same result in a different form. Additional comments here would be helpful. Why is the convergence result for homogeneous MGs not a straightforward implication of the convergence proofs for general MGs in Zhang et al.?\n\n- A figure would be quite helpful to better understand the overall flow of the practical algorithm in Sect. 4.\n\nOn the experimental results:\n- The empirical evaluation is nice in the sense that it considers the MPE domains which are standard in MARL. Nevertheless, focusing on MPE also means the findings are demonstrated in a single class of domains only.\n- In all the domains considered, the full observability and other assumptions required in the theoretical analysis are broken to some degree. Why not include experiments in some toy domains where the implications of the theory can be demonstrated when the conditions required are indeed satisfied? Then, the claim \"we develop the first multi-agent actor-critic algorithm for homogeneous MGs that enjoys asymptotic convergence guarantee...\" can truly be verified.\n- It is surprising that the proposed method with communication does not do any better than random in Prey 30 (Fig. 1, rightmost plot). Why is this the case?\n- I am a puzzled by what Fig. 6 is telling us. I would assume that naturally throughout the course of the training, the need for consensus-making decreases as the agents converge. This is even encouraged when communication has a cost (as defined end of Sect. 4). Is this the message of Fig. 6?\n\nMinor:\nIn the statement of Thm. 1: S \\times O should be O \\times A ?\nIn several places throughout the paper, curly braces denoting sets are not displayed, e.g. 0, 1 should be {0, 1}.\nQuality of figures should be improved overall, e.g., including axis labels and cleaner formatting \n\n*Comments added after the rebuttal, edited after author response:*\n\nI thank the authors for addressing my concerns and providing a rebuttal. I am generally satisfied with the response.\n\nOn the positive side, the rebuttal addresses all of my minor concerns. The new experiment in a toy domain is likewise a welcome addition. The rebuttal makes clear the differences to collective Dec-POMDPs and similar models. \n\nThe rebuttal does provide clarity regarding the setting addressed in the paper (communication in Dec-MDPs). The authors' comment also further clarifies this and it can be argued the formulation in the paper is sufficient, although it can be further improved by including the table. My main concerns have been addressed, and I increased my score to reflect this. ", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper contributes a theoretical analysis of policy sharing in fully-observable multi-agent RL, and a practical algorithm for training agents in communication-limited settings. The underlying assumptions and limits of the theoretical analysis have been clarified by the authors. With this, the paper makes a decent overall contribution that is also clear in context of other literature in Dec-(PO)MDP and Markov Game models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MoqwTePIoXJ", "reviewer": "Reviewer_smsi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \n\nVery interesting setting. Permutation invariant MARL captures many real-world applications but is less studied rigorously. This paper provides a nice analysis for the Permutation invariant MARL. \n\nWeakness:\n\n1. Definition 1 (iii) assumes bijective observation, so essentially the state is fully observable? If so, this should be emphasized. \n2. In Theorem 1, I am confused with the notation. Originally, each $\\pi^i$ maps $\\mathcal{S}\\times\\mathcal{A}^i$ to $[0,1]$. With the observation based policy, I expect $\\pi_o^i$ to map $\\mathcal{O}\\times\\mathcal{A}^i$ to $[0,1]$, not the definition in Theorem 1. \n3.  Section 4.1: I do not follow how the critic network works. Each $Q^{i}$ depends on the observation and action of neighbors. But if no communication is between $(i,j)$ at time $t$ (i.e. $c_j^i = 0$), how to evaluate the critic network without knowing neighbor’s action/observation?\n4. Section 4.2: I do not follow the relationship between Section 4.2 and Section 4.1. Section 4.1 already provides a way for selective communication.  Is the method in Section 4.2 separate from that in Section 4.1, or they somehow work together?\n", "summary_of_the_paper": "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. \n", "summary_of_the_review": "Overall I think this paper considers a very interesting setting. Permutation invariant MARL captures many real-world applications but is less studied rigorously, and this paper fills the gap. \n\nI do think the presentation can be improved and some clarification needs to be made (see the \"weakness\" part).  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes a contribution in the literature of cooperative multi-agent reinforcement learning by proposing a decentralized and communication-efficient training framework under a fully observable setting. The paper first defines the homogeneous or permutation invariant subclass of Markov games (homogeneous MG), where it is proved that sharing policy parameters does not loose optimality. The paper then proposes an actor-critic algorithm for the homogeneous MG. The proposed approach is empirically supported. The reviewers had originally raised concerns or confusions, but no major concerns remain after discussion. 

Overall, the paper studies an interesting and practically relevant setting, providing new insights and solid basis for policy sharing that has been used in the literature without much understanding.
Decision: Accept (Poster)