Correcting experience replay for multi-agent communication
Authors: Sanjeevan Ahilan
Peter Dayan
Venue: ICLR 2021 Spotlight (2021)
Keywords: multi-agent reinforcement learning
experience replay
communication
relabelling

Abstract: We consider the problem of learning to communicate using multi-agent reinforcement learning (MARL). A common approach is to learn off-policy, using data sampled from a replay buffer. However, messages received in the past may not accurately reflect the current communication policy of each agent, and this complicates learning. We therefore introduce a 'communication correction' which accounts for the non-stationarity of observed communication induced by multi-agent learning. It works by relabelling the received message to make it likely under the communicator's current policy, and thus be a better reflection of the receiver's current environment. To account for cases in which agents are both senders and receivers, we introduce an ordered relabelling scheme. Our correction is computationally efficient and can be integrated with a range of off-policy algorithms. We find in our experiments that it substantially improves the ability of communicating MARL systems to learn across a variety of cooperative and competitive tasks.

Published as a conference paper at ICLR 2021
CORRECTING EXPERIENCE REPLAY FOR MULTI-AGENT COMMUNICATION
Sanjeevan Ahilan
Peter Dayan
Gatsby Computational Neuroscience Unit University College London
Max Planck Institute for Biological Cybernetics and University of Tübingen
ahi 1 lan@gatstin wag...ss..... .uw.ttsyy.....o......
wwl.ul... acc.uk
ABSTRACT
We consider the problem of learning to communicate using multi-agent reinforce- ment learning (MARL). A common approach is to learn off-policy, using data sampled from a replay buffer. However, messages received the past may not accurately reflect the current communication policy of each agent, and this com- plicates learning. We therefore introduce a 'communication correction' which ac- counts for the non-stationarity of observed communication induced by multi-agent learning. works by relabelling the received message to make it likely under the communicator's 's current policy, and thus be better reflection of the receiver's s current environment. To account for cases in which agents are both senders and receivers, introduce ordered relabelling scheme. Our correction is compu- tationally efficient and can be integrated with a range of off-policy algorithms. We find in our experiments that substantially improves the ability of communicating MARL systems to learn across a variety of cooperative and competitive tasks.
INTRODUCTION
Since the introduction of deep Q-learning (Mnih et al., 2013). it has become very common to use previous online experience, for instance stored replay buffer, to train agents in an offline manner. An obvious difficulty with doing this is that the information concerned may be out of date, leading the agent woefully astray in cases where the environment of an agent changes over time. One obvious strategy is to discard old experiences. However, this is wasteful it requires many more samples from the environment before adequate policies can learned, and may prevent agents from leveraging past experience sufficiently act in complex environments. Here, we consider an alternative, Orwellian possibility, of using present information to correct the past, showing that can greatly improve an agent's ability to learn.
We explore a paradigm case involving multiple agents that must learn to communicate to optimise their own task-related objectives. As with deep Q-learning, modern model-free approaches of- ten seek to Icarn this communication off-policy. using experience stored in a replay buffer (Foer-) ster et al. 2016 2017 Lowe al., 2017 Peng al.) 2017). However, multi-agent reinforcement learning (MARL) can be particularly challenging as the underlying game-theoretic structure is well known to lead to -tasstaiiona,ity, with past experience becoming obsolete as agents come progres- sively to use different communication codes. It is this that our correction addresses.
Altering previously communicated messages particularly convenient for our purposes as it has no direct effect on the actual state of the environment (Lowe et al., 2019). but quantifiable effect on the observed message, which constitutes the receiver's "social environment". We can therefore determine what the received message would be under the communicator's current policy, rather than what was when the experience was first generated. Once this determined, we can simply relabel the past experience to better reflect the agent's 's current social environment, form of off-environment correction (Ciosek& & Whiteson 2017).
We apply our 'communication correction' using the framework of centralised training with decen- tralised control (Lowe et al., 2017;; Foerster et al.) 2018). in which extra information in this case the policies and observations of other agents is used during training to learn decentralised multi-

---

Published as a conference paper at ICLR 2021
agent policies. We show how it can be combined with existing off- off-policy algorithms, with little computational cost, to achieve strong performance in both the cooperative and competitive cases.
BACKGROUND
Markov Games A partially observable Markov game (POMG) (Littman 1994 Hu etal. 1998) for N agents is defined by set of states S, sets of actions AI....,AN and observations 01, ON for each agent. general, the stochastic policy of agent i may depend on the set of action-observation
histories H; = (O; x A.)* such that T; Hi x A; + [0, 1]. In this work we restrict ourselves to history-independerr stochastic policies TT : O x A, + [0, 1]. The next state is generated according to the state transition function P S A A., x [0, 1]. Each agent obtains deterministic rewards defined as r; : X A X x A., - 0: : O There is an initial state distribution Po S + [0, and each agent aims to maximise its own discounted sum of future rewards Eg-pp, a~m a~m D t=o (r, a)] where π = ( F } is the set of policies for all agents, (aI...., aN) is the joint action and pr is the discounted state distribution induced by these policies starting from po.
R and receives a deterministic private observation
As an agent continually interacts with its environment it receives experiences (or, de: 1, 0141) ) at each time step. However, rather than using those experiences immediately for learning, it is possible to store such experience in a replay buffer, D, and sample them at later point in time for learning (Mnih et al.) 2013). This breaks the correlation between samples, reducing the variance of updates and the potential to overfit to recent experience. In the single-agent case, prioritising samples from the replay buffer according to the temporal- differencc error has been shown to be effective (Schaul al., 2013). In the multi-agent case, Foerster et al. (2017) showed that issues of non-stationarity could be partially alleviated for independent Q-learners by importance sampling and use of oow-dimeniional 'fingerprint" such as the training iteration number.
Experience Replay
MADDPG Our method can be combined with variety of algorithms, but we commonly em- ploy it with multi-agent deep deterministic policy gradients (MADDPG) (Lowe et al. (017), which we describe here. MADDPG is an algorithm for centralised training and decentralised control of multi-agent systems (Lowe al. 2017 Foerster et al. 2018), in which extra information is used to train each agent's 's critic in simulation, whilst keeping policies decentralised such that they can be deployed outside of simulation. It uses deterministic policies, in DDPG (Lillicrap et al.) 2015), which condition only on each agent's local observations and actions. MADDPG handles the non- stationarity associated with the simultaneous adaptation of all the agents by introducing separate centralised critic Q." (o, a) for each agent where 4l corresponds to the set of deterministic policies N4 O A of all agents. Here we have denoted the vector of joint observations for all agents o.
The multi-agent policy gradient for policy parameters 0 of agent is:
Vo. J(B,) Eo, (ooa-D/Vo,,, Qf (o. a) a)lol=
where 'D is the experience replay buffer which contains the tuples (o, a, r, o'). Like DDPG, each Qf is approximated by a critic Q!" which is updated to minimise the error with the target.
((w,) Eo.aaaa.ro=
y)
where y = r; + (o', a') is evaluated for the next state and action, as stored in the replay buffer. We use this algorithm with some additional changes (see Appendix A.. for details).
Communication One way to classify communication is whether it is explicit or implicit. Implicit communication involves transmitting information by changing the shared environment (e.g. scat- tering breadcrumbs). By contrast, explicit communication can be modelled as being separate from the environment, only affecting the observations of other agents. In this work, we focus explicit communication with the expectation that dedicated communication channels will be frequently in- tegrated into artificial multi-agent systems such driverless cars.
2

---

Published as a conference paper at ICLR 2021
Although explicit communication does not formally alter the environmental state, it does change the observations of the receiving agents, change to what we call its 'social environment | For agents which act in the environment and communicate simultancously, the set of actions for each agent A A x Am is the Cartesian product of the sets of regular environment actions A and explicit communication actions AT". Similarly, the set of observations for each receiving agent O Of x OTT is the Cartesian product of the sets of regular environmental observations O and explicit communication observations OF Communication may be targeted to specific agents or broadcast to all agents and may be costly or free. The zero cost formulation is commonly used and known as 'cheap talk' in the game theory community (Farrell Rabin 1996).
In many multi simulators the explicit communication action is related to the observed commu- nication in simple way, for example being transmitted to the targeted agent with or without noise on the next time step. Similarly, real world systems may transmit communication in well understood way, such that the observed message can be accurately predicted given the sent message (partieu- larly if crror-orrrcctonn is used). By contrast, the effect of environment actions is generally difficult to predict, as the shared environment state will typically exhibit more complex dependencies.
METHODS
Our general starting point is consider how explicit communication actions and observed mes- sages might be relabelled using an explicit communication model. This model often takes a simple form, such depending only on what was communicated on the previous timestep. The observed messages 0 given communication actions at" are therefore sampled (denoted by ~>) from:
o ~ p(o a²T)
(3)
Examples of such a communication model could be an agent i receiving a noiseless message from a single agent j such that o, = dyt or receiving the message corrupted by Gaussian noise 01141 ~ (aa,, o) where a is a variance parameter. We consider the noise-free case in the multi- agent simulator for all bar one of our experiments, although the general idea can be applied to more complex, noisy communication models.
A communication model such this allows to correct past actions and observations in consis- tent way. To understand how this is possible, we consider a sample from a multi-agent replay buffer which is used for off- learning. In general, the multi-agent system current time t' receives observations oy, collectively takes actions ar using the decentralised policies π, receives rewards T1+11 (split into environmental rewards +1 and messaging costs rf'-1) and the next observations O These experiences are stored as a tuple in the replay buffer for later use to update the multi- agent critic(s) and policies. For communicating agents, we can describe sample from the replay buffer D as the tuple:
of 0ig ag T T1+1 T4+1: 0 0711 D
(4)
where separately denote environmental (e) and communication (m) terms, and t indexes time in the past (rather than the current time t'). For convenience we can ignore the environmental tuple of observations, actions and reward as we do not alter these, and consider only the communication tuple (o at" r o Using the communication model at time t', we can relate a change in az" to change in 0221- If we also keep track of at"h,
similarly change of" In our experiments we assume for simplicity that communication is costless (the 'cheap talk' setting), which means that mm O, however in general we could also relabel rewards using a model of communication cost p(r a."). Equipped with an ability to rewrite history, we next consider how to use it, to improve multi-agent learning.
3.1 OFT-ENVIRONMENT RELABELLING
A useful perspective for determining how to relabel samples is to consider each multi-agent expe- rience tuple separately, from the perspective of each agent, rather than as a single tuple received by
which could also by descrihed change each agent's 's helief state.
3

---

Published as a conference paper at ICLR 2021
bntvionmennt
Sert messiage
of
m at
T++1
14
Taa off
Speaker
p(o 11
pio a(")
Listener
o
at
Tt+1
t++1
Received message
Figure 1: Consider a multi-agent experience tuple for a Listener agent receiving communication from Speaker agent. In this simplified illustration the Speaker agent receives only environment observations, the Listener only receives communication. Our communication correction relabels the Listener's experience by generating and then generating the new Listener observation using the communication model p(o la"")) We shade in red the parts of the experience tuple which we relabel. Note that this relabelling only takes place for the Listener's ' sampled multi-agent experience, and not for the Speaker, as in this example itself Listener.
message using the Speaker's current policy л (a." lot)
the Speaker
all agents as is commonly assumed. For a given agent's tuple, we can examine all the observed mes- sages which constitutes its social environment (including even messages sent other agents, which will be seen by a centralised critic). These were generated by past policies of other agents, and since then these policies may have changed due learning or changes in exploration. Our first approach therefore to relabel the communication tuple (o!" .a."" r of 1); for agent by instead querying the current policies other agents, replacing the communication actions accordingly and using the transition model compute the new observed messages. For agent this procedure is:
m 0-i.t) à à ~ T=i(a o ~ p(o amm,,)
where -i indicates agents other than and we use to indicate that has been relabelled from its original value. Once the message has been relabelled for all agents, construct the overall relabelled joint observation by concatenation:
ō of 6
(6)
We illustrate our Communication Correction (CC) idea in Figure for the case of two agents, one sending out communication (the Speaker) and the other receiving communication (the Listener).
We experiment with feedforward policies which condition actions on the immediate observation, but this general idea could also applied with recurrent networks using a history of observations am π :aa". hh.it);; we discuss this in Future Work (Section (). In our feedforward case, we sample an extra 0,-1 in order to determine (using the other agents policies) the new 6,", which allows us relabel the point of sampling from the replay buffer. Our relabelling approach could also straightforwardly be incorporated with attention- models which also learn to whom to communicate (Das et al. (2019), but for experiments assume this is determined by the envi- ronment rather than the model.
3.2 ORDERED RELABELLING
One additional complexity to our approach that the policies of the other agents may themselves be conditioned received communication in addition to environmental observations. Our initial description ignores this effect, applying only a single correction. However, we can better account for this by sampling from the replay buffer an extra k samples into the past. Starting from the

---

Published as a conference paper at ICLR 2021
k'th sample into the past, Ôi-k OL-k- Using Equations and 6 according to:
we can then relabel
ō ~ p(0 Oi-k1,,
We iteratively apply this correction until ō++1 is generated. In general, this is approximation if the starting joint observation Ot-k depends on communication, but the corrected communication would likely be less off-ennironment than before. Furthermore, for episodic environments an exact correction could be found by correcting from the first time step of each episode.
In our experiments we consider Directed Acyclic Graph (DAG) communication structure which also allows for exact corrections. In general a DAG structure may be expressed in terms of an adjacency matrix which is nilpotent; there exists some positive integer n such that D Vm 2 n. If s is the smallest such we can set k = 1 which allows information to propagate from the root nodes of the DAG to the leaves. Agents which are not root nodes will not need A updates for the influence of their messages to be propagated and so, for efficiency, for messages steps into the past we only generate messages which will have a downstream effect steps later (where 0 < c S k). In general, we call our approach an Ordered Communication Correction (OCC), as opposed to our previous First-step Communication Correction (FCC) which only does one update.
3.3 IMPLEMENTATION
We include the full algorithm in Appendix A.9 We find in our experiments that relabelling can be done rapidly with little computational cost. Although different agents require different relabelling, the majority of the relabelling shared (more so proportionally for increasing N). For simplicity, we can therefore relabel only a single multi- experience for the N agents, and then correct for each agent by setting its own communication action back its original value, well as the downstream observations on the next time step. Once the sampled minibatch has been altered for each agent, we then use for training an off-policy multi-agent algorithm. our experiments we use MADDPG and Multi-Agent Actor-Critic (MAAC) (see Appendix (A.4) (Igbal & Sha, (019) but our method could also be applied to other algorithms, such as value-decomposition networks (Sunehag al. 2017) and QMIX (Rashid et al. 2018).
RESULTS
We conduct experiments in the multi-agent particle environ- men (MPE), a world with a continuous observation and dis- crete action space, along with some basic simulated physics. For common problems in the MPF, immediate observations sum- marise relevant history, such as velocity, such that optimal poli- cies can be learned using feedforward networks, which use for both policy and critic. We provide precise details on imple- mentation and hyperparameters in Appendix A.
4.1 COOPERATIVE COMMUNICATION WITH 5 LANDMARKS
Our first experiment, introduced by Lowe et al. 2017), is known co-
as Cooperative Communication (Figure 2 It involves operative agents, Speaker and Listener, placed in an envi- ronment with landmarks of differing colours. On each episode, the Listener must navigate to randomly selected landmark; and both agents obtain reward proportional to its negative distance from this target. However, whilst the Listener observes its rel- ative position from each of the differently coloured landmarks, it does not know which landmark is the target. Instead, the colour of the target landmark is seen by an immobile Speaker. The Speaker sends a message to the Listener at every time step, and so successful performance on the task corresponds to it helping the Listener reach the target.
Figure 2: Cooperative Commu- nication with 5 landmarks. Only the Speaker knows the target colour and must guide the Lis- tener to the target landmark.
5

---

Published as a conference paper at ICLR 2021
-8
-10
Mean Reward
Meam Reward
-14
Comm MADOPG
-14
MADOPG-FF
-16
MAAC
-18
MADOPG-CC
-20
-20
5000
10000
15000
20000
25600
30000
35000
40000
Episodes
Figure 3: Cooperative Communication with 5 landmarks. (Left) MADDPG with communication correction (MADDPG+CC) substantially outperforms MADDPG (n=20, shaded region is standard error in the mean). (Right) Smoothed traces of individual MADDPG and MADDPG+CC runs. MADDPG+CC often has rapid improvements in its performance whereas MADDPG is slow to change.
Whilst Lowe al. (2017) considered a problem involving only 3 landmarks (and showed that de- centralised DDPG fails on this task), we increase this to 5. This is illustrated in Figure 2 which shows a particular episode where the dark blue Listener has correctly reached the dark blue square target, due to the helpful communication of the Speaker. We show performance ure 3 Perhaps surprisingly both MADDPG and MAAC struggle to perfectly solve the problem in this case, with reward values approximately corresponding only reliably reaching 4 of the 5 pos- sible targets. We also implement a multi-agen fingerprint for MADDPG (MADDPG+FP) similar the one introduced by Foerster al. (2017). by including the training iteration index as input the critic (see Appendix A.5). but we do not find it to improve performance. By contrast, introduc- ing communication correction substantially improves both methods, enabling all 5 targets be reached more often. By looking at smoothed individual runs for MADDPG+CC we can see that often induces distinctive rapid transitions from the 4 target plateau the 5 target solution, whereas MADDPG does not. We hypothesise that these rapid transitions are due to our relabelling enabling the Listener adapt quickly to changes the Speaker's s policy exploit cases where it has learned to select better communication action (before it unlearns this).
this task in Fig-
We also consider a version of Cooperative Communication in which randomly, 25% of the time, a sent message is not received. By relabelling with the same communication model, which also drops 25% of messages, we find again that MADDPG+CC does better than MADDPG (Appendix A.6).
4.2 HIRRARCHICAL COMMUNICATION
We next consider a problem with a hierarchical communica- tion structure, which
to elucidate the differences be- tween first-step and ordered communication corrections (MAD- DPG+FCC MADDPG+OCC), Our Hierarchical Communi- cation problem (Figure 4 involves four agents. One agent is a Listener and must navigate to one of four coloured landmarks, but it cannot see what the target colour is. The remaining three Speaker agents can each see different colours which are certain not to be the target colour (indicated by their own colour in the diagram). However, only one Speaker can communicate with the Listener, with the rest forming a communication chain. To solve this task, the first Speaker must learn to communicate what colour knows not to be correct, the middle Speaker must integrate its own knowledge communicate the two colours which not correct (for which there are possibilities). and the final Speaker must use this to communicate the identity of the target landmark the Listener, which must navigate to the target.
Figure 4: Hierarchical Commu- nication. Three Speakers, with limited information and commu- nicating in chain, must guide the Listener to the target.

---

Published as a conference paper at ICLR 2021
leaming
-8
-10
Mean Reward
-12
-14
FCC
Attar learning
00
-16
-0
MADDPG+FCC
MADDPG+OCC
02
5000 10000 15000
20000
25000
30000
35000
40000
90
02
Episodes
Figure 5: Hierarchical Communication. (Left) MADDPG+OCC substantially outperforms alter- natives on this task (n=20). (Right) Correlation matrices for joint communication actions. Past communication from before learning is poor reflection of communication after learning. OCC applicd to past samples recovers this correlation structure whereas FCC only partially recovers this.
We analyse performance of MADDPG, MADDPG+FCC and MADDPG+OCC on this task in Figure S Whilst MADDPG+FCC applies the communication correction for each agent, it only does this over one time step. which prevents newly updated observations being used to compute the next correction. By contrast, the ordered MADDPG+OCC, with 3. starts from the root node, updates downstream observations and then uses the newly updated observations for the next update and so on (exploiting the DAG structure for more efficient updates). Our results show that MADDPG learns very slowly on this task and performs poorly, and MADDPG+FCC also performs poorly, with no evidence a significant improvement over MADDPG. By contrast, MADDPG+OCC performs markedly better, learning at much more rapid pace, and reaching higher mean performance.
We would like to find out if the improved perfor- mance may be related the ability our method recover correlations in communication. We there-
fore also examine the correlation matrices for the vector of joint communication actions. After hav- ing trained our MADDFG+OCC agents for 30, 000 compare samples of communica- tion from the starting point of learning and after learning has taken place. We that the correlation matrices are substantially different, with an intricate structure after learning reflecting the improved per- formance on the task. Without a communication correction, a 'before learning' sample would be changed, and the sample would therefore be a poor reflection of the current social environment. Using MADDPG+FCC we recover some of this structure, but there are still large differences, whereas MAD- DPG+OCC recovers this perfectly. This indicates that an ordered relabelling scheme is beneficial, and suggests that it may be increasingly important as the depth of the communication graph increases.
Iean Reward for Alles
episodes,
0.
MADOPG Allies (vs MADOPG Adversary) MADOPG-CC
Adversary)
0.0
MADOPG Allies (vs MADDPG+ Adversary)
2500
12500
Episodes
Figure 6: Covert Communication. When the Allies use the CC their performance is im- proved, whereas when their adversary uses their performance is diminished (n=20).
4.3 COVERT COMMUNICATION
In our next experiment, we consider competitive task first introduced by Lowe et al. (2017) called Covert Communication. In this task there are three agents; two Allies, one being Speaker and another Listener, and Adversary. The Speaker sends messages which are received by both the Listener and the Adversary. However, whilst the Speaker would like the Listener to decode the message, it does want the Adversary to decode the message. Both Speaker and Listener observe

---

Published as a conference paper at ICLR 2021
-10
-14
-18
MADDPG
MADDPG
5000 10000
15000
20000
25000
30000
35000
40000
Episodes
Figure 7: Cooperative Communication with Multiple Targets. (Left) One mobile Speaker agent and two Listener agents must each move to cover the target of their own colour. However, only the Speaker can see the target colours. For visualisation we overlay the Speaker's ' two discrete messages. (Right) The communication correction improves the performance of MADDPG (n=20).
a cryptographic "key', which varies per episode and which the Adversary does not have access to. Reward for the Allies is the difference between how well the Listener decodes the message and how well the Adversary decodes the message (with O reward when both agents decode equally well).
One of the reasons this problem is interesting is because, unlike the previous Speaker-Listende prob- lems which were ultimately cooperative, here there are competing agents. This is known to be able to induce large amounts of non-stationarity in communication policies and the environment. We therefore expect our experience relabelling to be effective in such situations, whether it be used for the Allies or the Adversary. Our results in Figure O demonstrate this; using the communication cor- rection for the Allies but not the Adversary improves the Allies performance, whereas using it for the Adversary but not the Allies degrades the Allies performance. We find that this is because the communication correction allows agents to rapidly adapt their policies when their opponents change their policy to reduce their reward. For MADDPG+CC Allies, this involves ignoring the key and instead learning to exploit structure in the Adversary's behaviour to do better than if the opponent were random (sce Appendix A.8 for an analysis).
4.4 COOPERATIVE COMMUNICATION WITH MULTIPLE TARGETS
In our final experiment, we apply our method to situation in which the Speaker also takes environ- ment actions and communicates cooperatively with two Listeners (Figure There are landmarks and each agent is assigned randomly chosen target landmark. Each agent must navigate to cover its own target but only the Speaker sees the three target colours and so must communicate with the Listeners, sending different messages to each of them, to guide them to their targets. As with Cooperative Communication, we find that MADDPG+CC substantially outperforms MADDPG.
5 RELATED WORK
Multi-agent RL has rich history (Busoniu al. 2008). Communication is key concept; however, much prior work on communication relied on pre-detined communication protocols. Learning com- munication was however explored by Kasai et al. (2088) in the tabular case, and has been shown to resolve difficulties of coordination which can be difficult for independent learners (Mataric 1998] Panait & Luke 2005). Recent work in the deep RL era has also investigated learning to commu- nicate, including how it can be learned by backpropagating through the communication channel Foerster et al. 2016; Sukhbaatar et al., 2016 Havrylov & Titov 2017 Peng et al.) 2017 Mordatch & Abbeel|2011 Although we do not assume such convenient differentiability in our experiments, our method is in general applicable to this case, for algorithms which use a replay buffer. Other approaches which have been used to improve multi-agent communication include attention-based methods (Jiang & Lu 2018:) Iqbal & Sha 2219 Das et al.) 2019), intrinsic objectives (Jaques et al.
2019] Ficcles et al. 2019) and structured graph-based communication (Agarwal al. 2019).
8

---

Published as a conference paper at ICLR 2021
Improvements to multi-agent experience replay were also considered by Foerster al. (2017) who used decentralised training. Importance sampling as an off-environment correction was only found to provide slight improvements, perhaps due to the classical problem that importance ratios can have large or even unbounded variance (Robert & Casella 2013), or with bias due to truncation. Here focus specifically on communicated messages; this allows us relabel rather than reweight samples and avoid issues of importance sampling. Of course, our method does not alter environment actions and so importance sampling for these may still be beneficial. In addition, may in some cases be beneficial to condition our relabelled messages on these environment actions, perhaps using autoregressive policies (Vinyals et al., 2017).
Our approach also bears resemblance to Hindsight Experience Replay (HER) Andrychowicz et al., 2017). which can be used for environments which have many possible goals. It works by replacing the goal previously set for the agent with one which better matches the observed episode trajectory, which is helpful in sparse reward problems. This idea has been applied to hierarchical reinforcement learning (Levy et al. 2018), field which can address single-agent problems by invoking a hierarchy of communicating agents (Dayan & Hinton 1993 Vezhnevets et al. 2017). In such systems, goals set by a learning agent, and one can also relabel its experience by replacing the goal it previously set with one which better reflects the
saapoorall--xteeddeeee observed transition (Nachum et al, 2018). Such ideas could naturally be combined with multi-agent HRL methods (Ahilan & Dayan 2019 Vezhnevets et al.] (2019). but they rely on communication corresponding to goals or reward functions. In contrast, our method can be applied more generally, any communicated message.
FUTURE WORK
Similar to prior work using the MPE we experimented with problems which could be solved using feedforward policies (Lowe et al. 2017 Igbal & Sha 2019 Agarwal et al. (201)). In the future it would be interesting extend our idea to richer problems solvable only by recurrent policies, which depend on the history of observations and actions. One strategy would be to build on existing meth- ods which use experience replay with recurrent networks (Hausknecht & Stone, 2015 Kapturowski eet al. 2018) whilst additionally relabelling when traversing the replay buffer. However, an addi- tional challenge in this setting is that a communicating agent may signal its intended environmental actions prior to taking them, and a naive relabelling would not account for this. When relabelling in the recurrent setting it may therefore be beneficial to condition on these fixed future environment actions, perhaps consider the communication and environment as part of an hierarchical whole, and relabel them in a coordinated manner. These merit further investigation.
We also did not conduct experiments with loopy communication graphs. For problems of this nature, an exact correction requires relabelling from the start of each episode (although a steps back approximation may be sufficient in some cases). Whilst the general principal of the OCC updates are unchanged in this case, it may be more computationally efficient to sample and sequentially relabel full episodes of experience rather than individual experiences, as was done in this work.
CONCLUSIONS
We have shown how off-policy learning for communicating agents can be substantially improved by relabelling experiences. Our communication correction exploited the simple communication model which relates sent message received message, and allowed us to relabel the received message with one more likely under the current policy. To address problems with agents who were both senders and receivers, we introduced an ordered relabelling scheme, and found overall that our method improved performance on both cooperative and competitive tasks. Our method provides a window into a general strategy for learning in non-stationary environments, in which acquired information in the present is used to alter past experience in order to improve future behaviour.
ACKNOWLEDGMENTS
We would like to thank Danijar Hafner and Rylan Schaeffer for helpful comments. Sanjeevan Ahilan received funding from the Gatsby Computational Neuroscience Unit. Peter Dayan received funding from the Max Planck Society and the Alexander von Humboldt Foundation.

---

Published as a conference paper at ICLR 2021
REFERENCES
Akshat Agarwal, Sumit Kumar, and Katia Sycara. Learning transferable cooperative behavior in multi-agent teams. arXiv preprint arXiv: (9990600022.,... 2019.
S Ahilan and P Dayan. Feudal multi-agent hierarchies for cooperative reinforcement learning. In Workshop on Structure & Priors Reinforcement Learning (SPiRL 2019) at ICLR 2019, pp- 1-11,2015
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, pp. 5048-5058, 2017.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. comprehensive survey of multiagent rein- forcement learning. IEEE Transactions Systems, Man, And Cybemettcs-Paatt C: Applications and Reviews, 38 (2), 2008, 2008.
Kamil Ciosek and Shimon Whiteson. Offer: Off-environment reinforcement rentrrrmmnn learning. 2017.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Mike Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. In International Conference Machine Learning, pp. 1538-1546, 2019.
Peter Dayan and Geoffrey E. Hinton. Feudal reinforcement learning. In Advances in neural infor- mation processing systems, pp. 271-278, 1993.
Tom Eccles, Yoram Bachrach, Guy Lever, Angeliki Lazaridou, and Thore Graepel. Biases for emer- gent communication multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 13111-13121, 2019.
Joseph Farrell and Matthew Rabin. Cheap talk. Journal of Economic perspectives, 10(3):003-118, 1996.
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Jakob Foerster, Nantas Nardelli, Gregory Farquhar, Triantafyllos Afouras, Philip HS Torr, Pushmeet Kohli, and Shimon Whiteson. Stabilising experience replay for deep multi-agent reinforcement learning, arXiv preprint 1.XXiv1102..88888 2017.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Emil Julius Gumbel. Statistical theory of extreme values and some practical applications. NBS Applied Mathematics Series, 33, 1954.
Matthew Hausknecht and Peter Stone. Deep recurrent q-learning for partially observable mdps. arXiv preprint arXiv:1507.06522. 2015.
Serhii Havrylov and Ivan Titov. Emergence of language with multi-agent games: Learning com- municate with sequences of symbols. In Advances in neural information processing systems, pp- 2149-2159, 2017.
Junling Hu, Michael P Wellman, et al. Multiagent reinforcement learning: theoretical framework and an algorithm. In ICML, volume 98, pp. 242-250. Citeseer, 1998.
Shariq Iqbal and Fei Sha. Actor-ateention-critic for multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning, pp. 2961-2970, 2019.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv: /6/ I. 1.01 144, 2016.
10

---

Published as a conference paper at ICLR 2021
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega. Dj Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference Machine Learning, pp- 3040-3049, 2019.
Jiechuan Jiang and Zongqing Lu. Learning attentional communication for multi-agent cooperation. In Advances in neural information processing systems, pp. 7254-7264, 2018.
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent ex- perience replay in distributed reinforcement learning. International conference on learning representations, 2018.
Tatsuya Kasai, Hiroshi Tenmoto, and Akimoto Kamiya. Learning of communication codes in multi- agent reinforcement learning problem. In 2008 IEEE Conference on Soft Computing in Industrial Applications, pp. 1-6. IEEE, 2008.
Andrew Levy, Robert Platt, and Kate Saenko. Hierarchical reinforcement learning with hindsight. arXiv preprint arXiv: arXiv:/805.08 0//00, /80, 2018
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv: arXiv:/509.000 509.02977, 2015.
Michael L Littman. Markov games as framework for multi-agent reinforcement learning. In Machine Learning Proceedings 1994, pp. 157-163. Elsevier, 1994.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compettivee environments. Advances Neural Information Pro- cessing Systems, pp. 6379-63999 2017.
Ryan Lowe, Jakob Foerster, Y-Lan Boureau, Joelle Pineau, and Yann Dauphin. On the pitfalls of measuring emergent communication. arXiv preprint 19XX:::993.05160 2019.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv:1611.0077 1.00/2, 2016.
Maja Mataric. Using communication to reduce locality in distributed multiagent learning. Journal of experimental & theoretical artificial intelligence, 10(3):357 1998.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Joannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Igor Mordatch and Pieter Abbeel. Emergence of grounded compositional language in multi-agent populations. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Ofir Nachum, Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. arXiv preprint 1805.088880.0222 2018.
Liviu Panait and Sean Luke. Cooperative mueti-agent learning: The state of the art. Autonomous agents and multi-agent systems, 11(3))387 2005.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. nets: Emergence of human-level coordination in learning
Multiagent indirectionalll-cooriiim to play starcraft combat games. arXiv preprint arXiv 1703./0/0030066 10069, 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 arXiv: 1485, 2018.
Christian Robert and George Casella. Monte Carlo statistical methods. Springer Science & Business Media, 2013.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv: / 1.05952, 2015.
11

---

Published as a conference paper at ICLR 2021
Sainbayar Sukhbaatar, Rob Fergus, al. Learning multiagent communication with backpropaga- tion. In Advances Neural Information Processing Systems, pp. 2244-2252, 2016.
Peter Sunehag, Guy Lever, Audrunas Cruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, al. Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv: Tekiv:/700.05200000 2017.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference Machine Learning, pp. 3540-3549, 2017.
Alexander Sasha Vezhnevets, Yuhuai Wu, Remi Leblond, and Joel Leibo. Options responses: Grounding behavioural hierarchies multi-agent arXiv preprint 1rXiv:1906.01470, 2019.
Oriol Vinyals. Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets,
Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, al. Starcraft ii: A new challenge for reinforcement learning. arXiv preprint
2017.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. arXiv preprint arXiv: 1804. 2018.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 HYPERPARAMETERS
For all algorithms and experiments, we used the Adam optimizer with a learning rate of 0.001 and 0.01 for updating the target networks. The size of the replay buffer was 10" and updated the network parameters after every 100 samples added to the replay buffer. We used batch size of 1024 episodes before making an update. We trained with 20 random seeds for all experiments and show using shaded region the standard error in the mean.
For MADDPG we the implementation of Iqbal & Sha (2019 For MADDPG and all MADDPG variants, hyperparameters were optimised using a line search centred on the experimental parameters used in Lowe al. (2017) but with 64 neurons per layer in each feedforward network (each with two hidden layers). We found a value of 0.75 worked best on Cooperative Communication with 6 landmarks evaluated after 50, 000 episodes. We use the Straight-Through Gumbel Softmax estimator with an inverse temperature parameter of to generate discrete actions (see
For MAAC and MAAC+CC, we use the original implementation with unchanged parameters of Iqbal & Sha 2019 For our feedforward networks this corresponded to two hidden layers with 128 neurons per layer, attend heads and 0.99.
A.2 DISCRETE OUTPUT WITH STRAIGHT- THROUGH GUMBEL SOFTMAX
We work with discrete action space and so for MADDPG, following prior work (owee et al. 2017 Iqbal & Sha, 2019), we use the Gumbel Softmax Estimator (Jang al., 2016; Maddison et al. 201 In particular we use the Straight-Throug Max trick (Gumbell 1954) on the forward pass to generate a discrete sample from the categorical distribution, and the continuous approximation to it, the Gumbel Softmax, on the backward pass, to compute a biased estimate the gradients.
Gumbel Estimator, which uses the Gumbel-
The Gumbel Softmax enables us compute gradients of a sample from the categorical distribution. Given a categorical distribution with class probabilites π, we can generate k-dimensional sample vectors y A on the simplex, where:
y: cxp((g: + log 83)
exp((0) + log क 73)
for i 1,..., where De are samples drawn from Gumbel F and / is inverse temperature parameter. Lower values of 3 will incur greater bias, but lower variance of the estimated gradient.
A.3 MADDPG
Although the original MADDPG proposed the multi-agent policy gradient of Equation 1 this can cause over-generalisation when a ~ D is far from the current policies of other agents (Wei et 2018). We use correction introduced by Iqbal Shal (2019) (for all variants of MADDPG), by sampling actions from the feedforward policy rather than the replay buffer, and providing this as input to the centralised critic.
al.
Vp, ((::) ((00))=BoDD) aa-
amp V (o, (o, (0)a))a.za())))
One minor difference from Iqbal Sha (2019) that they generate the discrete action of other agents using the greedy action whereas we instead take a Humbel-Soffman sample with 3 = 1.
huuns///gthbbbbom//mnnggii////lu hhanps//gthuu..om/aaaraaaaaaa cwwp:/aaarrggggaa2211110AA4
using the procedure Uniform(O, 1) and computing g log( log(u)))
13

---

Published as a conference paper at ICLR 2021
-20
-10
Moan Reward
-14
-60
-16
MADOPG
-18
-100
MADDPG CC trained with 25% drapped messages MADOPG+CE trained aithout dropped
-20 5000 10000
15000
20000
25000
30000 35000 40000
0.25
0.5
0.75
Probability of Dropped Message for Evaluation
Figure 8: Cooperative Communication with Dropped Messages. (Left) Correcting communication whilst accounting for error improves the performance of MADDPG (n=20) (Right) We compare the performance of model trained without dropped messages to one trained with 25% dropped messages. The model trained with dropped messages learns to be more robust to it than the model trained without (mean reward for each bar was averaged over 5000 episodes).
A.4 MULTI--GENT ACTOR ATTENTION CRITIC
Introduced by Igbal & Sha 2019). MAAC learns the centralised critic for each agent by selectively paying attention information from other agents. This allows each agent to query other agents for information about their observations and actions and incorporate that information into the estimate of its value function. In the case of MAAC+CC there just single shared critic and so we provide all altered samples to the same critic and do N critic updates (where N is the number of agents), and compare to MAAC which also does critic updates but with the unaltered samples.
A.5 MULTI-AGENT FINGERPRINT
We incorporate a multi-agent fingerprint similar to the one introduced by Foerster et al. (217)). We do this by additionally storing the training iteration number. As training iteration numbers get very large, and we find this hurts performance (we do not do use batch normalisation), we divide this number by 100, 000 before storing (we typically train over 40, 000 episodes, which corresponds to 1, 000, 000 iterations). We then train MADDPG in the conventional way, but additionally provide this number the centralised critic, Foerster et al. (2017) also varied exploration and so provide the exploration parameter to the decentralised critics. We do not do this as we keep exploration fixed throughout training (with Gumbel 3 = 1).
A.6 COOPERATIVE COMMUNICATION WITH DROPPED MESSAGES
We adapt the Cooperative Communication experiment such that 25% of sent messages are not re- ceived (the receiver sees all zeros). When correcting communication message would be and then randomly drop 25% of messages (MADDPG+CC), We drop messages by sampling from the communication model, irrespective of whether the original message that was sent was dropped or not (although an alternative approach of dropping the same messages could be explored in future). We find that applying this correction (MADDPG+CC) leads better per- formance than MADDPG (Figure 8 left). We also test relabelling approach which ignores the dropped message probability and simply relays them without error (MADDPG+CC No Error). As expected, this does much worse than MADDPG+CC, with performance approximately equal to MADDPG (although initial learning is faster).
compute what the new
Perhaps surprisingly, dropping messages 25% of the time does not provide an impediment to MAD- DPG+CC learning an effective policy. As the Listener can observe its own instantaneous velocity, it is possible that when no message is received it learns continue moving towards the target it is already heading to, which works most of the time. Interestingly, if we compare a model trained with dropped messages to trained without by evaluating it on the same task but with different proba- bilities of dropped messages, we find that the model trained with dropped messages is substantially more robust (Figure 8 right).
14

---

Published as a conference paper at ICLR 2021
A.7 EXPERIMENTAL ENVIRONMENTS
We provide a description of our environments in the main text but provide further information here. The episode length for all experiments was 25 time steps. For Cooperative Communication we alter the original problem by including two extra landmarks and by providing reward according to the negative distance from the target rather than the negative squared difference (as this elicits better performance in general). Our reward plots show the reward per episode.
For Hierarchical Communication, the information to the target landmark is distributed amongst Speakers who cannot move and communicate in a chain to the Listener. As with Cooperative Com- munication we display rewards per episode and use the negative distance rather than the negative square distance.
For Covert Communication we plot the average reward per time step and use the original task, with one minor change of dividing the reward by 2. This ensures that the magnitude of the Allies rewards less than or equal to (for example, when the Allies are always right and the Adversary is always wrong the Allies reward is 1).
For Cooperative Communication with Multiple Targets, each agent must navigate to its target land- mark but only the Speaker sees all three target colours. The Speaker sends separate discrete mes- sages to each Listener. A shared reward equal to the summed negative distance of each agent from its target is provided to all agents. Our reward plots show the reward per episode divided by 3 (the number of agents).
A.8 ANALYSIS OF COVERT COMMUNICATION
When used for the Allies, our communication correction substantially improved their perfor- mance. Interestingly, we found that rather than use the key, MADDPG+CC is able to learn communication actions which mislead its ad- versary into making the wrong choice, whilst simultaneously helping the Listener to make the right choice. This enables MADDPG+CC to achieve more reward than could be achieved against random opponent (on average this would be 0.5). To emphasise this, we also trained agents on the same problem but with- out providing the Allies with the key. We find that when both Allies and the Adversary are trained using MADDPG the reward for the Al- lies is zero, because the Allies cannot adapt any faster than the Adversary. By contrast, perfor- mance for the MADDPG+CC Allies against MADDPG opponent remains very good, with the MADDPG+CC Allies continuing out-adapt the Adversary, causing it to perform even worse than random.
0.8
Mean Reward for Alles
0.4
0.0
MADDPG Allis (vs MADDPG Adversary) MADDPG+CC MADDPG Adversary)
-0.2
5000
7500
10000
12500
15000 17500 20000
Episodes
Figure 9: Covert Communication without the key (n=20). MADDPG+CC Allies outperform MAD- DPG Allies.
A.9 ALGORITHM
We outline our Ordered Communication Correction algorithm here (First-step CC can be recovered by setting K = 1). We write it for the general case, although fewer updates can be used to achieve equivalent results if the communication graph is a DAG. For notational simplicity we use a ~ (a o) to indicate that each agent's ' policy т. receiving input o; was used to generate a, and thus collectively the joint action a. Note that our description of the set of actions A, = AA x AT allows agents to both act and communicate simultaneously; in cases where agents only do one of these we allow for a 'no op' action.
An alternative way define actions for each agent A, is to divide them into disjoint environment actions AC and explicit communication actions AAm such that AC U A A, and A n AT = (Lowe al. 2019). To deal with this case one would require only minor alterations the algorithm.
15

---

Published as a conference paper at ICLR 2021
Algorithm 1: Ordered Communication Correction
Given:
An off- ooflpo multi-agent RL algorithm A using centralised training with decentralised policies
One-step communication under model p(o af")) which relates sent messages received messages
Feedforward policies
Initialise A;
Initialise replay buffer D;
Initialise number of steps to correct K; foreach episode do Receive initial state æ and joint observations o;
foreach step of episode do
Select joint action a ~ Ta o) using current policies (with exploration);
Execute actions which transitions environment state to x and observe rewards r, and next state o':
Store (o, a, a, o') in replay buffer D;
a +- x';
Sample from D at random indexes t multi mulli--gent minibatch
B. (Ot-K,.... Ot, T++1, 01+1);
δt- K 0t-K:
for k: = K,..., do
Compute new messages T ~ (aa Ōt=k);;
Compute new observed messages 0t k-1+1 ~ p(o am=));
0z-k41 = - ① o
end for
à aj + aT for i O.....N. N do
Set agent i's sent and received messages back to original value (where is index of receiving agents);
am a 2 a.
oth 6 @ o
mnt 141,-1 41.
m
B ( aj Tt+ 6 11
Perform one step of optimisation for agent i using A with relabelled minibatch B
end for end foreach end foreach
16


Reviews:
[{"review_id": "vfrn-Uc9CYA", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper considers communication games when agents use experience replay. The agents' communication protocol may change over time, leaving outdated symbols in the replay buffer which are then trained on. This paper proposes replacing the old communication actions with up-to-date actions as the transitions are sampled, and shows that this leads to greatly improved convergence speed and higher performance plateaus.\n\n--------------------\n\nPositives:\n\n- The problem of multiagent communication and how to learn it is important and relevant to the ICLR community. The solution presented here seems like a natural fit with the problem and popular agent architectures and is well presented.\n\n- The paper is well motivated and well written.  Overall it was an enjoyable and easy read!\n\n- The experiments in Figures 4, 5, and 6 seem like great choices to show the strengths of the approach.  They're simple, well described, and well targeted.\n\n--------------------\n\nNegatives:\n\n- I feel like there's a pretty obvious question about \"What happens in richer domains?\" that (unless I missed it) isn't addressed in the paper - I'll expand on that in my 'Questions to clarify recommendation' section below. While the technique seems to work very well in the experiments chosen for the paper, I wish the paper touched a bit more on upcoming challenges, possible foreseen problems, and next steps.\n\n--------------------\n\nRecommendation and Justification:\n\nOverall, I feel like this was a strong paper and should be accepted. My only real negative was that I am excited to know more about what comes next.\n\n--------------------\n\nQuestions to clarify recommendation:\n\nThe three environments presented in the paper, if I've understood them correctly, are pretty straightforward in that 1) the speaker only has communication actions (and no environment actions), and 2) seems to only have one consistent message to communicate during the entire episode (after perhaps waiting to receive a message from others, in Hierarchical Communication). But right from the abstract onwards, I was wondering about possible problems in richer domains, where it seems like this technique could be harmful. Specifically, what if by updating the old communication action to one chosen by the current policy, we present a communication action that no longer aligns with the old environment action, which we do not update?  I felt like this was a pretty natural question, but unless I missed it, the paper doesn't mention possible problems like this.\n\nI'll ground this in an example, similar to Cooperative Communication.  Imagine a two-player gridworld where the players cannot see each other, but are rewarded for arriving at the same map location.  Similar to Bach and Stravinsky / Battle of the Sexes, each player has a different preference over locations, but being at the same location is most important. Let's call the locations Left and Right.  To enable coordination, let one player be a Speaker that can take communication actions to signal the other player as to where they should meet in that episode. While that permits greedy Speaker policies (always announce their preferred location and then go there) and greedy Listener policies (always go to their preferred location, regardless of Speaker's announcement), it would also allow the speaker to arrange a correlated equilibrium: announce a randomly chosen location in each episode and then go there, to maximize joint reward beyond any greedy Nash equilibrium policy.\n\nHere's where I see a possible failure with the technique in this paper.  Assume that the replay buffer contains an episode where the speaker emitted symbol L (for left) and then took environment actions to move to the Left location.  Later in training, using the technique presented here, we might sample this experience, update the symbol to L', and still move Left.  As described in this paper, I would expect that should work, and converge faster than by using the out-of-date symbol L.  However, it seems possible that the newer Speaker policy might prefer to move Right on that episode instead.  Updating the symbol would change it from old L to new R', but since the technique does not (and cannot, without a world model) update the environment actions, it seems like the listener and speaker would then train on this misaligned tuple of communication action R' and environment actions to move Left.  I would expect this confusing example to be much worse than training on the original example with the outdated but still aligned communication actions.\n\nMore generally: how can we make sure that the updated communication actions still align in intent with the agent's environment actions that we cannot change? It seems like conditioning the communication action on the agent's environment action for that timestep might help, but would only be a partial solution: if an agent must speak now but take their first significant environment action in the future, we would have the same problem.\n\nMy questions regarding this point are:\n- Do you agree that this could be a problem in richer environments than those presented in the paper?\n- If so, do you foresee an easy solution, or will this be a challenge for future work?\n\nI think the paper is strong enough as-is, and does not need an experiment in this paper to investigate richer games like this.  However, if the authors agree that the technique could fail to help or could harm convergence in richer settings than those presented in the paper to support the technique, then I think a couple of sentences about future challenges and future work are warranted.\n\n-------------------\n\nIssues and Suggestions:\n\n- Nit: Pg2, Experience Replay. The first sentence describes the agent as receiving (s_t, a_t, ..., s_t+1) at each time step. Should this be (o_t, ..., o_t+1), since the agent receives observations and not environment states?\n\n- Typo: Pg2, MADDPG.  'uses deterministic polices' --> policies\n\n- Suggestion: Pg3, Methods section and Equation 4. Equation 4 describes the tuple as containing r^e_t+1, r^m_t+1, but the text in the paragraph above only mentions r_t'+1, and the text below only indirectly clarifies what r^e and r^m are when it describes the cheap talk setting where r^m=0.  This threw me for a while when I read the equation, and scanned back up the page to try to see where r^e and r^m were defined, and they aren't. I suggest changing the sentence in the previous paragraph from \"receives rewards r_t'+1\" to something like \"receives rewards r_t'+1 (split into an environmental reward r^e and a messaging cost r^m)...\" to clarify this before the symbols are used.\n\n- Typo: Pg4, Ordered Relabelling. \"may themselves by conditioned\" --> \"may themselves be conditioned\"\n\n- Clarify: Pg4, under equation 6. The sentence \"...we sample an extra o^m_t-1 in order to determine (using the other agents' policies) the new \\^{o}^m_t, which allows us to relabel...\". I don't understand what this sentence is trying to say. Which player is this for? The symbol \\^{o}^m_t doesn't appear in equations 5 or 6, so I don't understand what sampling an extra o^m_t-1 would do, since it's to compute a symbol that doesn't connect with the equations being discussed. Maybe I'm just missing something obvious, but I spent a couple of minutes trying to figure this out, before giving up and moving on.\n\n- Nit: Pg5, Implementation. Extremely minor, but the phrasing \"we can therefore only relabel...\" suggests a limitation of the approach (e.g., we are only able to do this...) whereas I think you're suggesting a performance win (we can do this using only...). I feel like flipping the words to \"we can therefore relabel only a single...\" better communicates that.\n\n- Typo: Pg9 and 10, References. In both of the references including Pieter Abbeel, his affiliation is prefixed (OpenAI Pieter Abbeel). No other authors' affiliations are listed, so this just seems like a .bib typo.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RjflIVxgHu8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "---- Summary ----\nThe paper proposes a method for modifying an experience replay when learning in communication environments, by relabelling messages using the latest policy.\n\n---- Reasons for score ----\nThe paper addresses the problem of non-stationarity in an important class of multiagent environment. The correction proposed is simple, and effective in the domains it is tested in. My main concern is how broadly the method applies, which I am uncertain of from the paper.\n\n---- Pros ----\nThe paper provides a simple way to better leverage replay data for communication environments, addressing non-stationarity in those environments. This is an important problem in multiagent environments.\n\nThe experiments show improvements in learning speed and final reward in some communication domains. These cover a few important cases for the algorithm, including hierarchical communication and communication with an adversarial listener.\n\nThe paper is well situated in the literature on emergent communication, and it is clear and well written throughout.\n\n---- Cons ----\nMy main worry is that the paper leaves me uncertain on when the method can be applied. The OCC algorithm suggests that a necessary condition is that the message graph is acyclic. However, this limitation is not explicitly discussed, and I am also unsure whether an acyclic message graph is a sufficient condition. For example, does the method apply with multiple listeners acting in the same environment, or when the speaker also acts? It would strengthen the paper to be more precise about the settings where these algorithms can be applied and can be expected to help.\n\nThe discussion on Covert Communication in the appendix significantly changed how I understood the results of this experiment; in particular, the agents have not solved the task intended in the environment (using the key to communicate), but instead appear to be constantly changing strategy to outpace the listener - with the key being irrelevant. This is hinted at in the main text, but I think it is central enough to the interpretation of the experiment that it should be moved there.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q5tHYpMxP-2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers a multi-agent reinforcement learning (MARL) scenario where agents take actions based on the current observation alone. The paper proposes a communication correction mechanism where, during the centralized training, messages there were received in the past from other agents are reevaluated according to the updated policy. This way old messages can be updated instead of discarded, which is more efficient overall. \n\nThe paper is clearly written and easy to follow. The experiments are enough to convince that the communication correction idea is effective. The idea is not very deep or insightful, so the significance of the contribution depends on how useful this trick will be in practice. This is completely fine, but since I'm not doing research in this area, it's hard for me to judge if this idea will be of value to other researchers, given the existing alternatives in the literature. Therefore my review focuses on the presentation of the idea. \n\nI'm missing some intuition regarding why applying this correction is always \"safe\". Couldn't it somehow drift since it always gives so much importance to the new learned actions? what if for some period of time the new actions are worse than the old ones? Have you encountered any scenarios where this correction (at least if not properly tuned) degraded the performance? \n\nPlease elaborate on the assumption of actions that only depend on current observation. This seems very restrictive. How common is this assumption in the relevant literature? As a Markov strategy, it makes more sense if the state summarized the history of the game in some intelligent way. Is this the case for the scenarios you tested? \n\nI think it can be insightful to also experiment with a scenario where communication is noisy. Specifically,  the scenario when there is a probability of p that a message is not received looks interesting to me. The reason is that this kind of randomness seems to be essentially different than the noiseless case, as opposed to a weak Gaussian noise. With this kind of noise, the sampling part of the algorithm will often sample a communication error when trying to relabel a message, effectively discarding the old message. Is this desirable or acceptable? Would one need to prevent this possibility if communication is random? Since questions like this arise (if it makes sense), I'd be careful not to make statements about how easily the method can be applied for more general scenarios (like with noise), especially since the paper is 100% empirical so we only see that what was tested works. Also, please define the ~ sign explicitly to avoid confusion. \n\nIs this a realistic assumption that p(o|a) is known? it requires a model for the type of noise and communication failures that will occur in real-time, making the method not entirely model-free. Please discuss. \n\nI didn't find Fig.1 very helpful. What does it contribute over (5)? \n\nIf you used the correction in Section A.3, why is (1) presented in the paper? seems a bit misleading to clarify that only in the appendix. \n\nPlease add a reference for \"cheap talk\". \n\nThe abstract should what is the basis for the claim that \"it substantially improves...\", so at least mention this is based on experiments. \n\n\"We analyze the performance of this task in Figure 3\" - seems to be an overstatement, there is no analysis here, just reporting the results of the experiment. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5ZKXaiombHH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors present a fun and effective idea to translate a peer's message in terms of one agent's own experience. The benefit of doing so makes sense intuitively and is verified to be effective empirically.\n\n\nStrengths:\n\n+ The motivation is clear, and the key idea is well-presented. Paper is positioned well in relevant works of communication-aided MARL research.\n\n+ Evaluation is thorough and indicative of the authors' claims.\n\n\nMajor Concerns:\n\n- The reviewer has yet to discover a major issue with the paper with regard to its correctness, contribution, novelty, and effectiveness.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a simple and intuitive way to improve how to learn a communication protocol off-policy in the non-stationary situation in which messages received in the past do not reflect an agent's current policy. The authors introduce a communication correction that relabels the received message adjusting it to the current policy. The authors show that this method, besides being simple, is effective in a number of experiments. As observed by some reviewers, an issue with the method is that it is not clear how it would scale up to more complex environments than those considered. However, the authors addressed the concerns during the response phase, both adding new experiments, and with a clear statement of what are the outstanding issues. The paper is certainly a clever and solid contribution to the area of multi-agent communication learning, and I am strongly in favour of accepting it.

Decision: Accept (Spotlight)