Cheap Talk Discovery and Utilization in Multi-Agent Reinforcement Learning
Authors: Yat Long Lo
Christian Schroeder de Witt
Samuel Sokota
Jakob Nicolaus Foerster
Shimon Whiteson
Venue: ICLR 2023 poster (2023)
Keywords: Reinforcement Learning
Multi-Agent Reinforcement Learning

Abstract: By enabling agents to communicate, recent cooperative multi-agent reinforcement learning (MARL) methods have demonstrated better task performance and more coordinated behavior. Most existing approaches facilitate inter-agent communication by allowing agents to send messages to each other through free communication channels, i.e., \emph{cheap talk channels}. Current methods require these channels to be constantly accessible and known to the agents a priori. In this work, we lift these requirements such that the agents must discover the cheap talk channels and learn how to use them. Hence, the problem has two main parts: \emph{cheap talk discovery} (CTD) and \emph{cheap talk utilization} (CTU). We introduce a novel conceptual framework for both parts and develop a new algorithm based on mutual information maximization that outperforms existing algorithms in CTD/CTU settings. We also release a novel benchmark suite to stimulate future research in CTD/CTU.

Published as a conference paper at ICLR 2023
CHEAP TALK DISCOVERY AND UTILIZATION IN MULTI-AGENT REINFORCEMENT LEARNING
Yat Long Lo University of Oxford Dyson Robot Learning Lab richie. wo@dyson..nnooooom com
Christian Schroeder de Witt FLAIR, University of Oxford cs rebotss wx.ac..cuu.
Samuel Sokota
Jakob Foerster
Camegie Mellon University
FLAIR, University of Oxford
ssokota@andrew cmu. edu
jakob. foersterseng ox ac uk
Shimon Whiteson
University of Oxford
shimon. wwwtesonssssstto.oooooo
ABSTRACT
By enabling agents communicate, recent cooperative multi-agent reinforcement learning (MARL) methods have demonstrated better task performance and more coordinated behavior. Most existing approaches facilitate inter-agent communica- tion by allowing agents to send messages to each other through free communication channels, i.e., cheap talk channels. Current methods require these channels be constantly accessible and known to the agents a priori. In this work, we lift these requirements such that the agents must discover the cheap talk channels and learn how to use them. Hence, the problem has two main parts: cheap talk discovery (CTD) and cheap talk utilization (CTU). We introduce novel conceptual frame- work for both parts and develop new algorithm based mutual information maximization that outperforms existing algorithms in CTD/CTU settings. We also release novel benchmark suite to stimulate future research in CTD/CTU.
INTRODUCTION
Effective communication is essential for many multi-agent systems in the partially observable setting, which is common in many real-world applications like elevator control (Crites & Barto 1998) and sensor networks (Fox et al., 2000). Communicating the right information at the right time becomes crucial completing tasks effectively. In the multi-agent reinforcement learning (MARL) setting, communication often occurs on free channels known as cheap talk channels. The agents' goal is to learn an effective communication protocol via the channel. The transmitted messages can be either discrete or continuous (Foerster et al. 2016).
Existing work often assumes the agents have prior knowledge (e.g., channel capacities and noise level) about these channels. However, such assumptions do not always hold. Even if these channels' existence can be assumed, they might not be persistent, i.e., available every state. Consider the real-world application of inter-satellite laser communication. In the case, communication channel is only functional when satellites are within line of sight. This means positioning becomes essential (Lakshmi et al. 2008). Thus, Without these assumptions, agents need the capability to discover where to best communicate before learning a protocol in realistic MARL settings.
In this work, we investigate the setting where these assumptions cheap talk channels are lifted. Precisely, these channels are only effective in a subset the state space. Hence, agents must discover where these channels are before they can learn how to them. We divide this problem into two sequential steps: cheap talk discovery (CTD) and cheap talk utilization (CTU). The problem is a strict generalization of the common setting used in the emergent communication literature with

---

Published as a conference paper at ICLR 2023
less assumptions, which is more akin to real-world scenarios (see appendix A for more in-depth discussions on the setting's significance and use cases).
(a)
(b)
Figure I: The two learning stages for CTD/CTU based on PBMaze. Stage (a): Discover the functional phone booths; Stage (b): Form protocol use the phone booth and learn to interpret the messages (left), and solve the task (right). The blue and red agents are the sender and the receiver respectively
This setting is particularly difficult suffers from the temporal credit assignment problem (Sutton 1984) for communicative actions. Consider an example we call the phone booth maze (PBMaze), the environment has sender and receiver, placed into two separate rooms. The receiver's s goal is to escape from the correct exit out of two possible exits. Only the sender knows which one is the correct exit. The sender's goal to communicate this information using functional phone booths.
This leads to two learning stages. Firstly, they need to learn to reach the booths. Then, the sender has learn form protocol, distinguishing different exit information while the receiver has to learn to interpret the sender's protocol by trying different exits. This makes credit assignment particularly difficult communicative actions do not lead to immediate rewards. Additionally, having communicative actions that are only effective in small subset of the state space further makes a challenging joint exploration problem, especially when communication necessary for task completion. Figure I provides a visual depiction of the two learning stages in this environment.
As whole, our contributions are four-fold. Firstly, we provide formulation of the CTD and CTU problem. Secondly, we introduce configurable environment to benchmark MARL algorithms on the problem. Thirdly, we propose method to solve the CTD and CTU problems based on information theory and advances in MARL, including off-belie belief learning (Hu et al.) 2021 OBL) and differentiable inter-agent learning (Foerster et al.) 2016 DIAL). Finally, we show that our proposed approach empirically compares favourably other MARL baselines, validate the importance of specific components via ablation studies and illustrate how our method can act as a measure of channel capacity to learn where best communicate.
2
RELATED WORK
The use of mutual information (MI) has been explored in the MARL setting, WWng et al. (0119) pro- pose shaping reward based on MI between agents' transitions to improve exploration, encouraging visiting critical points where one can influence other agents. Our proposed method also has an MI term for reward shaping. Their measure might behave similarly to ours but is harder to compute and requires full environmental states during training. Sookota et al. (0022) propose method to discover implicit communication protocols using environment actions via minimum entropy cou- pling, separating communicative and communicaateee decision-mall making. We propose similar problem decomposition by separating state and action spaces into two subsets based on whether communication occur not. Unlike in Sokota al. (2022). foeus explicit communication
2

---

Published as a conference paper at ICLR 2023
where specialized channels for communication exist. Jaques et al. 2019 propose rewarding agents for having causal influences over other agents' policies using MI between agents' actions. Jaques) et al. (2019) is the closest to work but still assumes the omnipresence and prior knowledge of communication channels.
Many recent papers investigate various aspects of communication in MARL., Foerster et al. (2016) propose DIAL to learn how to communicate by allowing gradients to flow across agents. We use DIAL component of our proposed framework. /Sukhbaatar al. (2016) propose CommNet to learn how to communicate. Unlike DIAL, it uses mean-pooling to process messages and handle dynamic number of agents. Das al. (019) proposes a targeted communication architecture to tackle the issue of what messages to send and who to send them to. (Singh et al. (2018) propose gating mechanism to learn when to communicate, achieving better training efficiency scalability by reducing redundant communication. Jiang & Lu (20T8) proposes an attention mechanism to learn when and who to communicate by dynamically forming communication groups. our work, we focus the problem of discovering where to communicate, rather than how to communicate, who to communicate, and when to communicate. Hence, our contributions are orthogonal to existing works.
BACKGROUND
Throughout this work, we consider decentralized partially observable Markov decision pro- cesses (Dec-POMDPs) with N agents (Oliehoek & Amato 2016) in the form of a tuple G = (S, A, P, R, Z, 2, n, 7)- E S is the true state of the environment. At each time step, each agent i E N chooses an action a E A' to form a joint action a E A = A x A X A This leads to a tran- sition the environment according the transition function P(s'ls, a ...aa) S x AxS - [0, 1]. All agents share the same reward function R(s, a): : S x A - R. 7 E [0, 1) is a discount factor. Each agent i receives individual observations = Z based the observation function (T((s) S + Z.
The environment trajectory and the action-observation history (AOH) of an agent are denoted as T (so, 80, .t, at) and Ti (12 dy (((
E T = (Z A)" respectively. A stochastic policy π (a' TxA [0. 1] conditions on AOH. The joint policy π has a corresponding action-value function Q" (8t, ax) = IF se=t ae41:0 RR 82, 0z). where R. = = 7'r++a is the
discounted return. Tt+ the reward obtained time + from the reward function R. The
distribution of states is commonly referred to as belief B (T(r") P(r(r(,T).
3.1 OFF-BELIEF LEARNING
OBL (Hu et al. 2021 is a recent method to learn policies that do not interpret the actions of other agents and assumes other agents would do the same. Precisely, it induces agents to not reason about each other's private information and actions by conditioning their beliefs only on information revealed by the environment and interpreting their actions as if they were performed by random agent. This is often desirable as making incorrect assumptions can cause coordination failure. Therefore, learning base policy that maximizes reward without any conventions is important, especially when agents work with others who they have not met before, a problem known as zero-shot coordination (ZSC).
The OBL operator assumes all agents to be playing common policy To up T¹ and π₃ thereafter. Then, an agent's 's belief B, conditioned on their AOH can be computed as:
B (T|=") P(T|r", mo)
We denote the state-action value for playing mo up to T' and playing na thereafter to be t (alr"), which is the expected return of sampling т from Bn, (r') with all players playing म starting from the end of this trajectory. The counterfactual state-action value function is defined as follows:
Q (al7")
Σ Bmo (T)()T))[[[(sss a) T(T++177)V (T(41)))
TesTet1
To compute an OBL policy using value iteration methods, the Bellman equation for = (7*) for each agent is expressed follows:
00:- (0+) =
(3)
E Te ((T
Σ
R(se, av) > mae ) (aLtAlTEHN)
(1
or-
3

---

Published as a conference paper at ICLR 2023
Under this setting, the states reached by my may be reached at very low probabilities under xg- The variant learned-belief OBL (Hu al., 2021 LB-OBL) addresses this by using an approximate belief' Br, that takes 7; as input and samples a trajectory from an approximation of P(r|T',TO) To). Q-learning is then performed with an altered target value. Particularly, a new 7' is resampled from Bn (r.). Next, a transition to r/4 is simulated with other agents playing policy _ The bootstrapped value is then max, Q(a(T(+)) Hence, LB-OBL only involves fictitious transitions. The action oj ~ æ applied both the actual environment and sampled fictitious state. The learning target then becomes the sum of fictitious rewards ry, T and the fictitious bootstrapped value max, Q(al We use exact belief models this work to remove the influence of belief learning.
3.2 DIFFERENTIABLA
AGENNT LEARNING
Foerster et al. (2116) propose DIAL to learn how to communicate. It allows agents to give each other feedback about their communicative actions, by opening up communication channels for gradients to flow through from one agent to another. Such richer feedback improves sample complexity with more efficient discovery of protocols. During training, there are direct connections between one agent's s network output and another agent's input through communicative actions. Agents can then send real-valued messages and are only restricted to discrete messages during execution. These real-valued messages are generated from the networks, allowing end-to-end backpropagation across agents.
The proposed network is called C-net, an extension of deep Q Q-networks (Silver et al. 2016 DQN). It has two set of outputs, namely the Q-values Q(-) of the environment actions Aenv and the real-valued messages m The former performs actions selection while the latter is sent to another agent after the discretize/rgullrizze unit DRU (R)) processes it. The DRU regularizes messages during learning, DRU Logistic( ( o)), and discretizes them during execution, D RU (m]) 1 1mm > 0}. a is the standard deviation of the noise added to the cheap talk channel. The gradient term for m is backpropagated to the sender based on the message recipient's error. Hence, the sender can adjust m to minimize the downstream loss. Note that we use the OBL loss here instead of DQN loss.
4 PROBLEM FORMULATION
We consider each agent's action space A to be decomposable into two subspaces, namely, the environment action space Aenv and communication action space Acomm. The former are actions that only affect the environment state. The latter are actions that have no immediate effect on the environment state or the reward received, but can alter other agents' observations. Exemplifying with PBMaze, Aenr for the sender are actions that move its locations like Up and Down, while Acomm are actions that send messages to the receiver like Hint Up and Hin! Down.
In this setting, agents do not inherently know where to best communicate and only subset of states allows communication. We refer to this subset as the communicative state space Scomm E S:
Definition 4.1. The communicative state space Scomm of an environment is a subspace of its state space S. Assume the environment is in state se E Scomm at least one agent in se can modify another agent's 's observation by taking an action a E Acomm-
Similarly, the communicative joint observation space Ocomm defined as follows:
Definition 4.2. The communicative joint observation space Ocomm of environment is subspace of its joint observation space C, defined as Coomm. {S(ss))ss. E Scomm,; }. Assume the environment is in state S. Scomm with a joint observation 0g Ocomm, at least one agent, agent N, can modify another agent j E N.j * i's observation, o by taking an action a E Acomm-
++1
With these definitions, the cheap talk discovery and utilization problem can be formalized as follows:
Definition 4.3. For given S, MI(ss Σi-. Σj-N, [(A', Oa) be a function that com- putes the pairwise mutual information (PMI) of an agent's actions and another agent's observations. The inner term is defined in equation 5, Let (TT) = E, [_ MM Te). be the discounted sum of PMI of policy II, where IT the set of all possible policies. Cheap talk discovery the
4

---

Published as a conference paper at ICLR 2023
problem of learning a policy ddiacover in which agents take actions in Aene that maximizes v(T). An optimal x ddscover satisfies the condition:
(Tdissooee) 2 ((T))
VT E II
Definition 4.4. Given state 8, is in Scomm with corresponding AOH at time I, cheap talk utiliza- tion is the problem of learning a policy Tutil which agents take communicative actions in A Acomv to share information to improve task performance. For policy E IT, R. = EE, [_ T its expected return starting from St. An optimal uutt can then defined as:
Ruuest uest
R
VotT mAR
T IT and VT, s.t. 8t E Seomm
We reiterate that this is challenging joint exploration problem, especially when communication is necessary for task completion. Because agents need to stumble upon state Se E Scomm. which is often much smaller subspace than and there are no incentivizing signals reach these states as communicative actions Acomm do not lead to immediate rewards.
Thus, we hypothesize that this problem decomposition, i.c. first learn to discover the Scomm before learning how to use the communicative channels, could ease this joint exploration problem's 's severity.
5
METHODOLOGY
5.1 CHEAP TALK DISCOVERY
Our proposed method has two components, namely, mutual information (MI) maximization and OBL (Hu et al., 2021). The former induces agents to discover cheap talk channels based on MI. The latter our base learning algorithm with sound theoretical properties that are beneficial to the following CTU step.
5.1.1 MUTUAL INFORMATION MAXIMIZATION
Agents do not have immediate incentives to discover cheap talk channels. To do so, an agent has to know where send messages other agents successfully (i.c., channels that can influence another agent's observations). Hence, we propose novel reward and loss functions based on MI. The proposed reward function encourages greater mutual information (MI) between the sender's (denoted agent 1) actions A' and the receiver's (denoted as agent 2) observations 0 It is expressed as:
R' (st, at) = R(st, a+) + (T O²).
where 3 is hyperparameter. The first term is the task reward. The second term is the MI reward:
E [og(p(a"(o') - -og(p((a))(
(5)
We assume access the environment simulator estimate p(a" lo²). The proposed reward function
can then be substituted in the update equation To estimate p(a o²²), the term can be expanded to:
(A) = H(A') + H(O?) - H(A),0?)
Σ
[-p(a') (og'))oo((((a)))
Σ log(p(()))
al A
P~02
Σ
I-p(a', o²) log(ooaa'
(at .09)
(44 .09)
where = pair of agents in an environment irrespective of the receiver. Hence, we can apply this method to all possible receivers by summing all I(A', O'), i N. A 1 to discover the cheap talk channels.
Ea [p(a o²)] and p(a' 0²) p(oolla))p(( Note that this generalizes to any
The MI reward term alone does not maximize I (A O?). Specifically, for a given policy, since the term is computed based taking all the actions from state, the MI reward for staying within
5

---

Published as a conference paper at ICLR 2023
Scomo and for taking action in Acomm are equal. Hence, a policy learned only with MI reward is incentivized to reach Scomm without necessarily using communicative actions. Ideally, I [(A', O²) is maximized when a policy favors the communicative actions equally when in Soomm.
To learn a policy that does maximize [(A', (()), we propose an MI loss function, using the parame- terized policy Tg. The additional term directly maximizes T(A", O²), which is maximized when the policy takes actions in Acomm more. For each iteration i, the loss function is expressed as:
(..).) L. (0,) <I O²;
(7)
where B. (8:) (see Appendix I(A', :2:
(0;=m))))))))))mm mo); and A are OBL loss MI loss iteration and neprarrameeerr respectively. We add a minus sign that minimizing the loss maximizes the MI term. The combination of the MI reward and loss should allow the discovery of cheap talk channels with greater MI. We denote our discovery method cheap talk discovery learning (CTDL)
5.1.2 DISCOVERING CHANNELS WITHOUT CONVENTIONS FORMATION
During discovery learning, agents should simply learn where the channels are without forming any protocols (i.e., conventions) on how to use them. This is because the protocols formed would affect the rewards received. To do so, we employ OBL as our base algorithm.
Particularly, has appealing theoretical properties which are beneficial for this setting, theoreti- cally guarantees to converge to policy without any conventions (Hu et al. 2021p. This means OBL with CTDL would learn a policy that discovers the channels while not having preference over any communicative actions, which would allow more flexible adaptation when properties of channels alter. Hence, though not explored here, better performance in 7SC can expected.
For our example environment, the agent should prefer the actions Hint Up and Hint Down equally after cheap talk discovery. If the agents are in a slightly different environment with the phone booths sending negated versions of the messages agent sends, policy without conventions should adapt quicker given that it has no preference over communicative actions.
5.2 CHEAP TALK UTILIZATION
With channels discovered, agents are ready to learn how to use them through protocol formation (i.e.. form consensus of how messages are interpreted). Many off-the-shelf algorithms can be used for CTU. Here, we use DIAL (Foerster et al. 2016),, which has been shown to learn protocols efficiently. Note that OBI, will be replaced by independent Q-learning (Tan) 1993 IQL. updates to allow protocol formation in CTU.
Given that the original DIAL requires feedforwarding through an episode's 's full trajectory to maintain the gradient chain, modifications to DIAL are needed to work in this setting for two reasons:
First, the base learning algorithm an experience-replay based method that learns from transition batches, not trajectories. Second, unlike in the original DIAL which messages are sent in every step I, the messages can only be sent successfully when the environment state is in Scomm. Hence, direct gradient connections only happen occasionally in episode.
To make DIAL compatible with this setting, we use a separate replay buffer to keeps track of the transitions and only consider trajectory when messages are sent successfully. The buffer stores full episodes with flags indicating which transitions to allow direct gradient connections. We denote our discovery method with DIAL cheap talk discovery and utilization learning (CTDUL). The transition from CTD to CTU is a task-dependent hyperparameter and is determined empirically. Appendix Cland D shows how gradients flow in CTDUL and the corresponding pseudocode.
6 EXPERIMENTAL SETUP
As part of our contribution, we designed a configurable environment with discrete state and action space the phone booth maze evaluate agents in the CTD/CTU setting, as described in Section I
To enable extensive investigations, the environment allows phone booths of configurable properties including usage cost and noise level, and decoy booths that not functional. The agents' observation

---

Published as a conference paper at ICLR 2023
contains view information of the room agent is in and role-specific information (e.g. the sender and receiver have goal information and communication token respectively). Agents have the environment actions of UP, DOWN, LEFT, RIGHT, and NO-OP. There are two communicative actions, HINT-UP and HINT-DOWN which only has an effect when agents are in the functional phone booths, updating the receiver's s communication token to fixed value. Rewards of 1.0 and -0.5 are given for choosing a correct exit and an incorrect exit respectively with no reward given otherwise. By changing the can vary their capacities, measured by the MI reward. The left of Figure shows the MI of each location in the sender's š room in two different environment configurations, in which one has only one functional booth and the other has three booths with one noisy booth. These are computed based equation 5 on all possible combinations of the sender and receiver locations.
phone booths' properties,
We use two configurations of the environment for our experiments, which we name Single Phone Booth Maze (SPBMaze) and Multiple Phone Booth Maze (MPBMaze). Please see Appendix [F environment visualizations and design features, and Appendix H for environment parameters used.
Architecturally, we use the R2D2 architecture (Kapturowski et al. 2018) with separate commu- nication head like in C-Net (Foerster et al.) (016)) For baselines, state-of-the-art methods are used including IQL. OBL (Hu et al. 2021)) QMIX (Rashid et al. 2018)) MAA2C (Papoudakis et al. 2021
and IQL with social influence reward (Jaques et al. [019 SI).
We trained all methods for 12000 episodes (80000 episodes for CTU) and evaluated on test episodes every 20 episodes by taking the corresponding greedy policy. Each algorithm reports averaged results from 4 random seeds with standard error. We performed hyperparameter sweep over common hyperparameters, fixing them across all methods, and specific sweeps for method-specific parameters. Please Appendix and G for training and hyperparameter details.
7 RESULTS
7.1 DISCOVERING CHEAP TALK CHANNELS
Cheap Talk Discovery in SPBMaze
SPBMaze
MDeMs2e
17.5
0.69
15.0
10L
0
0
0
1.1
1.1
CBL
12.5
GMIX
MAA2C
10.0
51
7.5
0.0 0.8 1.0 5.0
022
0 2000 4000
5000
8000
10000
12000
Epioades
Figure 2: Left: MI reward for each location in the sender's room of SPBMaze and MPBaze show phone booths of different properties. Values are computed by iterating over all possible receiver's 's position for each sender's position. Senders start at positions with green borders. The position with purple border is the costly phone booth which incurs cost to use. The top phone booth in MPBaze has noise factor of 0.5, i.e., lower MI. Right: CTD performance for CTDL, and baselines. The horizontal grey line indicates the optimal number of step to reach the booth. For the ease of plotting, when an agent cannot discover the booth, we set the step as the episode length.
To quantify the performance in CTD, the functional phone booth in SPBMaze. The fewer the number of steps used, the better an algorithm is CTD. See Table 4 for detailed configuration of SPBMaze.
the number of steps it takes for the sender to first reach
Figure (Right) shows the performances of our proposed method CTDL and the baselines. CTDL, using MI reward and loss, discovers the functional phone booth quickly in optimal number of steps (as shown by the horizontal grey line). Meanwhile, without the proper incentives, all the baseline methods cannot discover the functional phone booth within the episode limit.
Even though SI uses a reward term based on MI like ours (i.e., the influence an agent's message has on another agent's action (Jaques al. 2019)), ), it becomes insufficient to discover cheap talk
7

---

Published as a conference paper at ICLR 2023
channels in this setting the messages sent only has effect in small subset of the state space. Note that without discovering the channels, agents will not be able to learn how to communicate. Hence, we expect the baseline methods cannot leverage communication channels to solve tasks.
7.2
LEARNING POLICIES WITH MAXIMIZED MUTUAL INFORMATION
IQL
IQL +
QMIX
MAA2C
2.4
0.4
2
0.2
Action Probabiity
Right
09
Up
Down
PAyh
UD Down
00
10
Down
09
10) DOAT
0.4
DBL
4.4
OBL
51
0.4
CTDL
0P
Up
Down
My/::
Up Down
0.
Left Right
Down
HSC
HICE
0.0
Left 41 0p
H:6 H11
Action
Action
Figure 3: Algorithms' sender policy when both agents are at the functional phone booth SPBMaze. CTDL learns policy with the most MI by preferring communicative actions equally.
To assess whether an algorithm can learn policies that maximize MI (i.e., I(A OO?) in this setting, we look at the sender's policy when both agents are at the functional phone booth. To reiterate, such policy uniformly prefers Acomm over Aene when using communication channel without forming any protocol. Figure shows different algorithms' sender policy when in the functional phone booth.
We include two variants that receive scalar intermediate reward (IR) when both agents are at functional phone booths. As discussed in section [5.ITT] these reward shaping methods do not maximize MI, although cheap talk channels are discovered. Instead, they learn to prefer actions that keep them in Seomm which includes certain environment actions.
Contrarily, our proposed MI loss used in CTDL leads polices with the most MI by preferring Acomm (i.e., Hint-Up and Hint-Down) uniformly over Aen.. This explains why CTDL has the best CTD performance it directly maximizes PMI in Definition Acomm also means no conventions are formed during discovery learning as they are preferred equally under different goals (i.e. different correct exits in SPBMaze), demonstrating the effect of OBL.
Note that this uniformity over
7.3 UTILIZING CHEAP TALK CHANNELS
Cheap
Study CTDUL SPBMaze
DBL
OBL
DEL D-AL
Tesk Runninng Reward
OMI MAXIC 51
Task Rumning Rieward
CTDUL Mustrilationn
CTCU, JOOL MI Pastmbation DAAL
CTDUL
0.2
10000 20000
30000
40000 50000 Episodes
GCOOD
70000 .83300
0
10000 20000
30000
40000 Episodes
50000 60000
70000
80000
Figure 4: Left: CTU performance for CTDUL and baselines on SPBMaze. The vertical grey line indicates the start of CTU learning for CTDUL. Right: Ablation experiment on SPBMaze for CTDUL. The curves are smoothed by a factor of 0.99 with standard errors plotted as shaded areas.
Figure (left) shows the overall task performance of the proposed CTDUL and baselines in solving the SPBMaze. Being unable communicate the goal information successfully, the receiver can only guess by escaping randomly (i.e., achieving an expected reward of 0.25 = 1.0 x 0.5 + (-0.5) x 0.5). Hence, all baselines converge the suboptimal solution of random guessing.
From Figure [gguree(nige (right) and Figure (left), (left), we can infer that the senders in the baselines do not reach the functional phone booth communicate protocols can be formed. Centralized training baselines
8

---

Published as a conference paper at ICLR 2023
(e.g., QMIX. MAA2C), which are designed to assign credits better since they have centralized components to learn better value functions using full state information, also converge to suboptimal solutions. Their poor performances illustrate the difficulty of this joint exploration problem.
In contrast, our proposed method CTDUL obtains significantly higher rewards than random guessing by employing DIAL to learn how to use the discovered channel. The grey vertical line is when DIAL begins after discovery learning. Qualitatively, we observe how our method solves the problem in which the receiver waits the functional booth until receiving a message from the sender. Then, it goes to the correct exit according to the protocol learned. The results show how our proposed problem decomposition and MI maximization components make the difficult problem easier solve.
Figure A (right) shows task performance on SPBMaze for our ablation study with CTDUL. Specifi- cally, we look the task performance when we individually remove components used, namely MI maximization and DIAL. As we can see, nontrivial solutions can only be learned if both of them are used. Removing one of them leads to the suboptimal solution of random guessing. Furthermore, we observe significant performance dip when OBL is replaced with IQL, empirically supporting the importance of not forming any conventions during CTD as pointed out section 5.1.2
7.4 MUTUAL INFORMATION AS A MEASURE OF CHANNEL CAPACITY
Task Reward
IR
MI Reward
25
25
Naise Factor 0.1
Notse
Average Number Booth
20-
20
15
10-
Nooth
Benthh
Boath
Cowily
Booth
Perfect
Booth
Nothyy
Booth
Costly
Booth
Perfect
Booth
Notsy (looth
Figure 5: Bar plot of average number of booth visits of each phone booth type in MPBMaze with varying noise factors for the noisy booth. The error hars are standard errors for the average number of booth visits for each booth type.
We hypothesize that our proposed MI reward can be a pseudomeasure of channel capacity, a way to discover where best to communicate when an environment has multiple channels. To verify, we run baselines and our proposed method for CTD on MPBMaze which has three channels, namely, the Perfect Booth, the Costly Booth, and the Noisy Booth. Note that a booth with noise has a probability of dropping a message. See Table 4 in the Appendix for the detailed configuration of MPBMaze.
Figures 5 compare which booth the sender chooses to visit when different reward functions are used. The optimal behavior is to visit the Perfect Booth the most as it has no noise and usage cost. All algorithms learn to avoid the Costly Booth given its direct effect on the reward. Comparing methods that use IR and MI rewards, the IR reward cannot distinguish between the Perfect Booth and the Noisy Booth and consistently visit the Noisy Booth as visits to both booths rewarded equally and the Noisy Booth is closer to the sender.
On the contrary, the MI reward method is able visit the Perfect Booth consistently the MI reward has an interpretation and measurement of noise and channel capacity (i.e., A channel with greater noise would necessarily mean a lower expected MI reward). As the noise factor decreases, the two booths become less distinguishable, which we observe a decreased in number of booth visits to the perfect booth for the agent with MI reward when the noise factor is 0.1.
CONCLUSION
In this work, we take away the common and arguably unrealistic assumptions in MARL that commu- nication channels are known and persistently accessible to the agents. Under this setting, agents have

---

Published as a conference paper at ICLR 2023
to first discover where to best communicate before learning how to use the discovered channels. We first provide a novel problem formulation for this setting denoted as the cheap talk discovery and utilization problem. Then, based this problem decomposition, we propose method based on MI maximization with OBL and DIAL to tackle this problem end-to-end. Experimentally. by evaluating framework against hate-offtheeart baselines in our proposed environment suite, we show that our framework can effectively discover communication channels and subsequently use them to solve tasks, while all the baselines fail do so. We also empirically attribute the framework's success to its key capabilities in learning policies with maximized MI and without convention formation during CTD. Finally, we demonstrate how our MI metric can serve as a pseudomeasure for channel capacity, to be used to learn where best to communicate. We hope this work can inspire investigation in more realistic settings for communication like the one introduced here.
ACKNOWLEDGMENTS
We thank Tarun Gupta for providing code implementations RI environments for our reference during the ideation phase of the project. We thank Michael Noukhovitch for helpful feedback.
REFERENCES
Robert H Crites and Andrew G Barto. Elevator group control using multiple reinforcement learning agents. Machine learning, (3(2))235-266 1998.
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. PMLR, 2019.
Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. Advances neural information processing systems, 29, 2016.
Dieter Fox, Wolfram Burgard, Hannes Kruppa, and Sebastian Thrun. A probabilistic approach to collaborative multi-robot localization. Autonomous robots, 8(3):225-33) -344,,44, 2000.
Hengyuan Hu and Jakob N Foerster. Simplified action decoder for deep multi-agent reinforcement learning. In International Conference on Learning Representations, 2019.
Hengyuan Hu, Adam Lerer, Brandon Cui, Luis Pineda, Noam Brown, and Jakob Foerster. Off-belief learning. In International Conference on Machine Learning, pp. 3369943799 PMLR, 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. PMLR, 2019.
Jiechuan Jiang and Zongging Lu. Learning attentional communication for multi-agent cooperation. Advances in neural information processing systems, 31, 2018
Steven Kapturowski, Georg Ostrovski, John Quan, Remi Munos, and Will Dabney. Recurrent experience replay in distributed reinforcement learning. In International conference on learning representations, 2018
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 14Xivv:412.6990 2014.
K Shantha Lakshmi, MP Senthil Kumar, and KVN Kavitha. Inter-satellite laser communication system. In 2008 International Conference on Computer and Communication Engineering, pp. 978-983. IEEE, 2008
Frans A Oliehoek and Christopher Amato. A concise introduction to decentralized POMDDS Springer, 2016.
10

---

Published as a conference paper at ICLR 2023
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 8026-8037, 2019.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 0295-43044 PMLR, 2018.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. International Conference on Learning Representations, 2018.
Samuel Sokota, Christian Schroeder de Witt, Maximilian Igl, Luisa M Zintgraf, Philip Torr, Martin Strohmeier, Zico Kolter, Shimon Whiteson, and Jakob Nicolaus Foerster. Communicating via markov decision processes. In Proceedings of the 39th International Conference Machine Learning, ICML'22 JMLR.org. 2022.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropagation. Advances in neural information processing systems,
2016.
Richard Stuart Sutton. Temporal credit assignment in reinforcement learning. PhD thesis, University of Massachusetts Amherst, 1984.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993.
Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang. Influence-based multi-agent exploration.
In International Conference on Learning Representations, 2019.
Xihuai Wang, Zhicheng Zhang, and Weinan Zhang. Model-based multi-agent reinforcement learning: Recent progress and prospects. arXiv preprint arX6v:2203.10603, 2022.
A PROBLEM SIGNIFICANCE AND USE CASES
The full problem setting of solving Dec-POMDPs is NEXP-complete. As such, it is not reasonable expect method that can solve large arbitrary Dec-POMDPs. To get around this, the "emergent communication" literature usually focuses on setting where there is fixed communication channel that is known a-priori.
We strictly generalise this setting by instead proposing a method that can first discover channels within the environment and next utilise them. Clearly, this cannot cover all problem Dec-POMDPs due to the constraints mentioned above but includes a broader set of potentially practically relevant applications.
In terms of use cases, the problem applies whenever real-world communication through a medium among agents is considered. Because more often than not, there will be some spatial constraints on communication in realistic settings. Any kind of communication channel used in the real-world (e.g., radio link, cell phone signal), does not have perfect signal strength, and often transmission errors could happen (e.g., noise). The signal strength varies lot depending your environment and current surroundings (e.g. indoor vs outdoor, underwater, environment interference in certain locations like behind mountain). Hence, for communication to happen efficiently and successfully, being able to learn where to communicate and learn where best to communicate is crucial which our problem setting addresses.
11

---

Published as a conference paper at ICLR 2023
Even in communication without explicit medium, say if robot wants to signal to another one with lights but they need a line of sight, communication becomes spatially constrained. We believe these examples illustrate how important this problem setting is when considering communication learning in more realistic environments.
Furthermore, the setting also sheds light munication. As illustrated our experiments with noisy channels, our mutual information reward provides pseudomeasure of capacity. The investigation provides path forward regarding capacity- constrained communication, by establishing two levels of capacity constraints i.e., capacity con- strained by the environment/physical space, size of Scomm. and the capacity for individual channels. Our method provides the first attempt to tackle both types of capacity constraints learning where to communicate and learning where best to communicate.
complete picture of
constrained com-
B
OBL LOSS
As in Hu et al. 2021), for given trajectory sampled from replay buffer, T,OL is expressed as TD-error:
T
Σ (OBI = 2
r + + max (2((
(8)
where Q₂ the target network. As T' contains fictitious transitions, we can not pass the whole sequence to RNN like in normal Q-learning. Thus, precompute the target G¹, r rr max, (g(alT(+2) during rollouts and store the sequence of targets along with the real trajectory into the replay buffer.
C GRADIENT CHAIN OF THE PROPOSED ARCHITECTURE
t+1
22
Agent
Action Select
Action Select
Network
Network
m
DRU
0- ++1
Agent
Network
Network
Action Select
Action Select
a
o
Environment
SreuudoEEvirooment
Figure 6: How gradients flow through our proposed architecture, with reference (0066)
Foerster al.
D PSEUDOCODE OF THE PROPOSED ARCHITECTURE
Algorithm T outlines the pseudocode of the proposed architecture to tackle the cheap talk discovery and utilization problem.
12

---

Published as a conference paper at ICLR 2023
Algorithm Pseudocode for our proposed method
for each agent do
Initialize replay memory for OBL DOBL with capacity N Initialize replay memory for DIAL DDIAL with capacity N
Initialize action value function Q with random weights 8 using architecture C-Net based on
R2D2
Initialize target action value function Q with random weights 0- = 0, using architecture C-Net based on R2D2
Initialize Num Discovery Episode
Discovery__Eiiidde
Initialize Discovery. Saaovery_Stgeeeeaa as True
end for
for e= 1, Max Leisode do Initialize
repeat
for each agent do
Select a from o based on policy derived from Q. e.g. e-greedy policy or stochastic OBL policy
Take action to observe reward r and next state o'
Take action a in Revdoo-Enviromment to perform OBL sampling with mutual information computation
Store the transition into DOBL if High mutual information is observed then
Store trajectory into DDIAL end if
Sample random minimatch of transitions from DoBL Sample random minimatch transitions from DDIAL if Discovery Staage then
Perform a gradient descent step on (. =I(AA, (2:))) with respect to the network weights
else
Perform gradient descent step on (y: Q(0, 1)) for DIAL with respect to the
network weights
Perform gradient descent step on L L (0,) with respect to the network weights end if
Every C steps, set Q = Q end for
until 8 Sterminal
if > Num Discovery_ Episode then
Set Discovery_ Stage as False
end if
end for
E ENVIRONMENT DESIGN
Figure visualizes two instances of the environment used in our experiments. Red cables indicate connectivity with dashed ones indicating the existence of noise. The yellow booth here indicates that it is a costlier booth to use.
For observations, each consists of tensor of 3 channels plus some role-specific information. The channels are the wall channel, phone booth channel, and the agent channel, which are essentially binary grid encoding each position for the existence of wall, phone booth, and the agent respectively. For role-specific information, the sender has an additional 2-bit encoding vector goal information. Specifically, the receiver should go up. the sender would get a vector of [1 0). If the receiver should go down, the sender would get (0 1] instead. For the receiver, if the sender performs HINT-UP with both of them at the functional booths, would -1. On the other hand, the sender performs HINT-DOWN, it would be 1. Many aspects of this environment are configurable to allow extensive investigation and exploration of different algorithms, some key adjustable features are highlighted in table E
13

---

Published as a conference paper at ICLR 2023
Figure 7: Two instances of the PBMaze with different configurations used in the experiments
F NETWORK ARCHITECTURE AND TRAINING
Instead of using convolutional layers as in Kapturowski al. (2018), we use fully-connected neural networks with a recurrent component as our neural network model. Hence, we flatten the observation from the environment into a vector by first fattening the 3-channel tensor and then concatenate it with the role-based information (i.e., goal encoding or communication token). Precisely, the input is first processed by an LSTM layer to handle partial observability. Then, is followed by a two-layer and two-headed fully-connected neural network of hidden size 128. The two heads are used to compute the action-value function and the advantage function respectively. All neural network components implemented using the neural network library PyTorch (Paszke et al., (019), with the weights initialized using Xavier initialization. In terms of training, we use the Adam optimizer to train our models (Kingma & Ba 2014). Training done in internal cluster with mix of GTX 1080 and RTX 2080 GPUs.
G HYPERPARAMETERS SETTING
This section covers details in setting hyperparameters for various methods used in this work. They are covered two separate sections depending on whether parameter common all used methods or not.
G.1 COMMON PARAMETERS
To determine the best parameters that are common to all the methods used, we performed a hypa- rameter sweep over some key common parameters. Specifically, the search performed on the learning rate and target network update frequency in the lists of [0.01, 0.001, 0.0001, 0.00001] and [50, 100, 200, 500]. The results averaged over 3 random seeds, each trained for 25000 episodes. The best set of parameters for learning rate and target network update frequency are 0.0001 and 100, respectively. Other common parameters set to values in table G.1
G.2 METHOO--PECIICC PARAMETERS
Method-spedde specific parameters are set to values in table
H ENVIRONMENT PARAMETERS
Parameters of the environments used in the experiments are summarized in Table
14

---

Published as a conference paper at ICLR 2023
Configurable Descrritioon
parame-
ter
lengths
the length of each of the agent's 's rooms. The longer it is, the harder the exploration becomes. the starting location of each of the agents.
starting
points
correct re-
The reward that is given when the receiver exits from the correct door.
ward
wrong ward
The reward that is given when the receiver exits from the wrong door.
use inter-
If set as true, it gives an intermediate reward for if both agents are at the functional booths, used for debugging purposes.
mediate
reward
episode
Episode length, meaning the episode terminates it reaches this number of steps.
limit
booth
Among functional phone booths, they are configurable in two major ways, namely, cost and noise. The former refers to the cost of using the booth and the latter is modeled as the probability a phone booth dropping a message. Locations of functional booths.
types
booth lo- cations number of decoy booths booth
The number of decoy booths the sender's room. Decoy booths refer to booths that are not functional and not connected to the booth in the receiver's room. They appear booths the agent's observation (i.e., the booth channel).
If set true, the decoy phone booths' locations are reinitialized whenever the environment is reset for the next episode, making the problem more difficult.
reinitial-
ization
use
If set true, the environment would compute the mutual information reward, used in the proposed method.
mutual in-
formation reward
If set true, the environment would return the necessary information (i.e., tensor masks for each term in equation to compute the mutual information loss in batch-based manner.
mutual in- formation
loss
Table 1: Configurable parameters for the PBMaze
Hyperparameter
Value
Discount Factor
0.99
Batch Size
Replay Buffer Size
10000
Temperature
1.0
Non-Linearity
ReLU
Table 2: Common parameters used across algorithms
I
LIMITATIONS
While our proposed framework provides a promising approach to learn where to communicate (i.c., CTD/CTU) by first discovering cheap talk channels and subsequently learning how to use them, is important to be aware of the assumptions and limitations of the framework for future work.
To begin with, approach assumes access to perform MI computation and OBL respectively. While there are recent approaches learning environment models (Wang al. (022) and belief models (Hu & Foerster) 2019). how well these learned components work with each other remains unexplored. Advances in these areas would improve the overall robustness of our proposed framework.
environment simulator and (perfect) belief
15

---

Published as a conference paper at ICLR 2023
IQL.
IQL
IR
OBL
CTDL/CTDIMMIX
MAA2C
SI
Starting
1.0
1.0
N/A
N/A
1.0
1.0
1.0
e Decay
0.00001
0.00001
N/A
N/A
0.00001
0.00001
0.00001
Step
Minimum
0.1
0.1
N/A
N/A
0.1
0.1
0.1
6
Initial Ex-
1000
1000
1000
1000
1000
1000
1000
ploration
Step
IR
N/A
1.0
N/A
N/A
N/A
N/A
N/A
at Entropy
N/A
N/A
N/A
0.0
N/A
N/A
N/A
Factor
Mutual
N/A
N/A
N/A
2.0
N/A
N/A
N/A
Infor-
mation
Reward
Factor
K. Mutual
N/A
N/A
N/A
1.0
N/A
N/A
N/A
Informa-
tion Loss
Factor
learning
N/A
N/A
N/A
N/A
0.0005
0.0001
N/A
rate
critic
N/A
N/A
N/A
N/A
N/A
0.0001
N/A
learning
rate
critic hid-
N/A
N/A
N/A
N/A
N/A
32
N/A
den size
hypernetworRN/A
N/A
N/A
N/A
64
N/A
N/A
hidden size
number
N/A
N/A
N/A
N/A
N/A
N/A
of hyper layers social in- fluence
N/A
N/A
N/A
N/A
N/A
N/A
5.0
ward coef- ficient
temperature
1.0
1.0
0.1
0.1
1.0
1.0
1.0
Table 3: Method-specific parameters
Another crucial assumption made is the direct and immediate causal relationship between a commu- nicative action and receiver's observation which might be less reliable in the real-world setting. For instance, there will be delay and transmission time when sending messages. In more visually-rich and open-ended settings, there could also be many confounding changes in the receiver's observation when communication actions are taken. In these cases, further advances are needed to correctly assign credits to communicative actions when computing MI.
Last but not least, the transition from CTD to CTU determined empirically from experiments. A more principled approach to automate this decision would make method more robust. For instance. based on Definition 4.3) a method could be developed to indicate whether an agent has been able to discover a channel consistently (i.c., a discovery policy with maximized PMT). Once threshold is reached, it can move on to the utilization stage.
16

---

Published as a conference paper at ICLR 2023
SPBMaze
MPBMaze (5
lengths (sender's room, ceiver's room)
(8, 4)
starting points (sender's co- ordinates, receiver's coordi- nates)
((4, 1), (2, 1))
(3. 1), (1, 1))
correct reward
1.0
1.0
wrong reward
-0,5
-0.5
episode limit
20
booth types
I functional booth, 0 cost to use and O noise factor
functional phone booths. The first one has a cost of 0.4 and 0 noise factor. The second one has 0 cost and O) noise factor. The third one has 0 cost and æ E [0.1, 0.3, 0.5] as noise factor across sets of exper- iments
number decoy booths booth reinitialization
False
False
Table 4: Table for environment configurations of each environment used in the experiments
J BROADER IMPACT
With the rapid progress in MARL and multi-agent learning systems in general, confidently expect that more multi-agent learning systems will be deployed in the real world which communication will play integral part to their successes. Our formulation and method for learning where to communicate would lead to more robust communication and subsequently more coordinated behavior among agents by equipping them with the ability discover the best and most reliable places to communicate. This is essential in such real-world applications when the reliability of communication often varies by locations and situations.
By increasing the applicability of multi-agent learning systems, our work may exacerbate some risks of deploying machine learning systems like increasing unemployment (e.g., replacing warehouse workers with fully autonomous warehouse) and advancing automated weaponry. Particularly to our method, by equipping systems with the ability to discover where to communicate, it could encourage adversarial attacks to deployed machine learning systems through communication which would lead to unintended and potentially harmful actions and disrupt learned communication protocols.
K FUTURE WORK
For future work, we are interested in testing our framework more complex settings and address some limitations discussed in Appendix | For instance, the ability discover communication channels can be formulated as skills and organized hicrarchical manner to solve harder tasks. would also be insightful to benchmark different algorithms for cheap talk utilization in this setting.
17


Reviews:
[{"review_id": "omsWj4ouEBN", "reviewer": "Reviewer_4J9r", "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": "This paper demonstrates that current methods in multi-agent reinforcement learning (MARL) do not suffice for a scenario where communication between agents is possible--but only in a subset of the state space. For a case of two agents, it proposes a method of training MARL agents via a two-stage process of first learning a policy that will enable communication and then learning an optimal policy starting from a communication-enabling state. The method successfully learns to enable cooperative problem solving in a simple environment.\n\nNote: I previously reviewed this paper as a NeuRIPS submission.", "summary_of_the_review": "This is an interesting paper for the MARL field. There is currently a disconnect between the real-world (where communication may be limited) and MARL scenarios which make strong assumptions on the possibility of communication. This paper raises the interesting question of what can be done when communication is difficult. Furthermore, if the question of how to enable communication are further investigated, this might have implications for theories of the socio-biological origins of culture and language.\n\nThus, I recommend acceptance. [no change to recommendation after rebuttal]", "strength_and_weaknesses": "+ Interesting problem\n+ Novel approach of separating discovery and utilization, which seems justified\n+ Thoughtful choice of combination of learning methods\n- Only applied to two agents (show an example with more agents)\n- States that the number of iterations in discovery stage is a \"tuning parameter\", but doesn't give any easy way to adjust this other than trial and error.  (Give more guidance how to set number of iterations, e.g. provide a testing procedure for whether sufficiently many iterations has been reached, or comment on such a possibility.) [after rebuttal: authors are looking into this]", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XvEEDlBK6A", "reviewer": "Reviewer_3EzS", "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": "", "summary_of_the_paper": "Authors design and implement an algorithm that operates under fewer assumptions than some communication-based MARL works. Agents learn to discover which environment actions and communicative actions to take, so as to maximize the mutual information (MI) with respect to observation at the receiver's end. The proposed CTDUL outperforms several baselines in the phone booth maze environment.", "summary_of_the_review": "Proposed method works well for a specific setting, whose characteristics can be better marketed as more realistic. Some definitions need clarification, and related literature can benefit from a closer investigation into the papers suggested above.", "strength_and_weaknesses": "Paper addresses a well-defined niche by relaxing a set of common assumptions found in some communication-based MARL methods. The tested evaluation environment is intuitive. Claims made with an intuitive approach (MI maximization) are shown to function correctly in the empirical evaluation.\n\nA number of factors can make the paper much stronger: problem positioning, clarified definition (especially action and channel), varied environments, better justified baseline choice, and comments on computation overhead.\n\nWhile the problem addressed is clearly an interesting setting, real-world settings might question its practicality. If the communication channels are not even known a priori, could there really be multiple agents who happen to have access to the same channels and also coincidentally need to cooperate? Consider a swarm of drones. If one common administrator is operating all of those drones as in a search-and-rescue operation, it is almost always the case that their communication channels are known pre-dispatch. On the other hand, if different operators are managing each of those drones as in individual drone racing competitions, then it may well be the case that there simply is no need for cooperative/coordinated flight management. It feels as though the removal of assumptions inadvertently led to a less realistic problem setting, so a better problem positioning could more effectively highlight the significance of the proposed solution to the problem.\n\nCommunicative actions and channels could be defined more clearly. If the term \"channels\" are correctly aligned with the same term in the radio communications sense, then communicative actions being \"hint up\" or \"hint down\" can be a misinterpretation of communication. Instead, should the concepts of channels remain faithful to radio communications literature, then the problem of which channels to discover should also pertain to the communication channels, such as which bandwidths. The current formulation of A_comm is probably more aptly described as message encoding since the chosen action answers the question of \"which message should be sent\". However, if this indeed is the case, then CTDUL's A_comm would simply be hard-coded actions.\n\nIt would be a valuable addition to the paper to investigate CTDUL's performance in other environments, such as SMAC or MAMuJoCo.\n\nIt would also be an insightful curation of CTDUL's positioning to include SchedNet (ICLR 2019), which addressed medium contention and medium access constraints in MARL, and DIAYN (2018), which is an information-theoretic approach to RL exploration and then identify CTDUL's strengths, differences, and delimitation.\n\nPlease also elaborate on the cost of computing pairwise mutual information and how this affects the empirical performance of CTDUL.", "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": "NAXBuobIzR", "reviewer": "Reviewer_Hktd", "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": "", "summary_of_the_paper": "The authors propose a more realistic multi-agent communication setup and provide a corresponding experimental environment. The authors also propose a corresponding learning framework based on MI to solve the corresponding communication problem, and the experiments show that their approach has significant advantages.", "summary_of_the_review": "The author has researched a novel and interesting scene, but the writing as a whole needs further improvement.", "strength_and_weaknesses": "Strength.\n* The authors propose a more realistic setting\n* The authors provide a corresponding experimental environment\n* Experiments show that their approach has significant advantages\n\nWeaknesses:\n* The notation used in section PROBLEM FORMULATION is cumbersome and the overall definition is redundant\n* The method seems to be relatively simple, and it is surprising why it works so well, and I hope the author will open source code subsequently.\n* Because in the current setting, the communication action directly affects part of the information in obs, does this mean that it is easier to find the communication status by MI? Can such an approach be extended to other scenarios?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5D4ZxfRaohn", "reviewer": "Reviewer_eTc7", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposes a method for agents to learn how to communicate using free communication channels, named \"cheap talk channels\". The problem is divided into two separate problems, namely to discover cheap talk and to utilize cheap talk. There is a communication space, separate from the environment action space. Not all states allow communication, so an agent can communicate only if it gets to a state that allows communication. The method proposed is base on maximizing mutual information. Since discovery is separate from utilization, when agents discover a communication channel, they do need to learn how to use the communication channel. To learn how to utilize the communication channel, the agent use DIAL, an existing method to learn efficiently communication protocols. The experimental work covered in the paper is done for a problem where the agents have to discover phone booths before learning how to use them to communicate.", "summary_of_the_review": "The method proposed seems incremental, built on existing algorithms. The specific example used to illustrate the problem seems to have been artificially created to justify the use of existing algorithms.", "strength_and_weaknesses": "Strengths: the formalization of the problem to learn how to  communicate is divided in two separate steps, which simplifies the learning process.\nWeaknesses: the specific problem of discovery phone booths and learning how to communicate seems artificially complex.  It is not clear the restrictions assumed are realistic, and will make sense in a variety of application domains. The setting of the problem seems to be artificial, designed for the purpose of using existing methods, OBL and DIAL.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster