Coordinated Multi-Agent Exploration Using Shared Goals
Authors: Iou-Jen Liu
Unnat Jain
Alex Schwing
Venue:  (2021)
Keywords: Multi-agent RL
Deep RL
Exploration

Abstract: Exploration is critical for good results of deep reinforcement learning algorithms and has drawn much attention. However, existing multi-agent deep reinforcement learning algorithms still use mostly noise-based techniques. It was recognized recently that noise-based exploration is suboptimal in multi-agent settings, and exploration methods that consider agents' cooperation have been developed. However, existing methods suffer from a common challenge: agents struggle to identify states that are worth exploring, and don't coordinate their exploration efforts toward those states. To address this shortcoming, in this paper, we proposed coordinated multi-agent exploration (CMAE): agents share a common goal while exploring. The goal is selected by a normalized entropy-based technique from multiple projected state spaces. Then, agents are trained to reach the goal in a coordinated manner. We demonstrated that our approach needs only $1\%-5\%$ of the environment steps to achieve similar or better returns than state-of-the-art baselines on various sparse-reward  tasks, including a sparse-reward version of the Starcraft multi-agent challenge (SMAC).

Under review as a conference paper at ICLR 2021
COORDINATED MULTI-AGENT EXPLORATION USING SHARED GOALS
Anonymous authors Paper under double-blind review
ABSTRACT
Exploration is critical for good results of deep reinforcement learning algorithms and has attracted much attention. However, existing multi-agent deep reinforce- ment learning algorithms still use mostly noise-based techniques. was recog- nized recently that noise-based exploration is suboptimal in multi-agent settings, and exploration methods that consider agents' cooperation have been developed. However, existing methods suffer from a common challenge: agents struggle to identify states that are worth exploring, and don't coordinate their exploration ef- forts toward those states. To address this shortcoming, in this paper, we proposed coordinated multi-agent exploration (CMAE): agents share a common goal while exploring. The goal is selected by a normalized entropy-bace -based technique from multiple projected state spaces. Then, agents are trained to reach the goal in a coordinated manner. We demonstrated that approach needs only 1% 5% of the environment steps to achieve similar or better returns than state-of-the-art baselines on various sparse-reward tasks, including a sparse-reward version of the Starcraft multi-agent challenge (SMAC).
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) is an increasingly important field. Indeed, many real-world problems are naturally modeled using MARL techniques. For instance, tasks from areas as diverse as robot fleet coordination (Swamy et al.) 2020 Hüttennauch et al., (019) and au- tonomous traffic control (Bazzan 2008 Sunehag et al. 2018) fit MARL formulations.
To address MARL problems, early work followed the independent single-agent reinforcement learn- ing paradigm (Tampuu et al.] 2015) Tan 1993, Matignon et al.) 2012). However, more recently, specifically tailored techniques such as monotonic value function factorization (QMIX) (Rashid) al. 2018), multi-agent deep deterministic policy gradient (MADDPG) (Lowe et al. 2017). and counterfactual multi-agent policy gradients (COMA) (Foerster et al. 2018) have been developed. Those methods excel in multi-agent setting because they address the non-stationary issue of MARL and develop communication protocols between agents. Despite those advances and the resulting reported performance improvements, common issue remained: all of the aforementioned methods use exploration techniques from classical algorithms. Specifically, these methods employ noise-based exploration, i.e., the exploration policy noisy version of the actor policy. For in- stance, Lowe et al. (2017) add Ornstein- Chistein-Uhlenbeck (OU) (Uhlenbeck & Ornstein 1930) noise or Gaussian noise to the actor policy. Foerster al. (2016); Rashid et al. (2018); Yang al. (2018); Foerster et al. (2017) use variants of e-greedy exploration, where a random suboptimal action is selected with probability e.
It was recognized recently that use of classical exploration techniques is sub-optimal in multi-agent reinforcement learning setting. Specifically, |Mahajan et al.) (2019) show that QMIX with e-greedy exploration results in slow exploration and sub-optimality. Mahajan et al. (201)) improve explo- ration by conditioning an agent's behavior on a shared latent variable controlled by hierarchical policy. Even more recently. Wang al. (2020) encourage coordinated exploration by considering the influence of one agent's 's behavior on other agents' behaviors.
While all of the aforementioned exploration techniques for multi-agent reinforcement learning sig- nificantly improve results, they suffer from a common challenge: agents struggle to identify states that are worth exploring, and don't coordinate their exploration efforts toward those states. To give

---

Under review as a conference paper at ICLR 2021
an example, consider push-box task, where two agents need to jointly push heavy box specific location before observing a reward. In this situation, instead of exploring the environment independently, agents need to coordinate pushing the box within the environment to find the specific location.
To address this issue, propose coordinated multi-agent exploration (CMAE), where multiple agents share a common goal. We achieve this by first projecting the joint state space to multiple subspaces. We develop a normalized entropy (Cover & Thomas. 1991 [ b-bssd technique select goal from the under-explored subspaces. Then, exploration policies are trained to reach the goals in a coordinated manner.
To show that CMAE improves results, we evaluate our approach on various environments with sparse-rewards from Wang et al. (2020), and the sparse-reward version of the Starcraft multi-agent challenge (SMAC) (Samvelyan et al. 2211)) which requires coordinated actions among agents over extended time steps before observing a reward. The experimental results show that our approach needs only 1% 5% of environment steps to achieve similar or better average test episode returns than current state-of-the-ar baselines.
2 PRELIMINARIES
In this section, we define the multi multi-agent Markov decision process (MDP) in Sec. 2.1 and introduce the multi-agent reinforcement learning setting in Sec. 2.2
2.1 MULNTI-GEENT MARKOV DECISION PROCESS
We model cooperative multi-agent system multi-agent Markov decision process (MDP). An n-agent MDP is defined by a tuple G = (S,A, T, R, 2, O. n, Y, H). S is the global state space of the environment. is the action space. At each time step each agent's policy Tú i (n....,n].
selects an action of E A. All selected actions form a joint action a' E AA. The transition function maps the current state sf and the joint action a' to the next state s .i.... T S x A" - S. All agents receive a collective reward r' E R according to the reward function R S x A" + The
goal of all agents' policies is to maximize the collective expected return Hf 7'r", where 7 E [0. 1] is the discount factor, is the horizon, and r' is the collective reward obtained at timestep t. Each agent i observes local observation of Z according to the observation function O S + Z. Note, observations usually reveal partial information about the global state. For instance, suppose the global state contains the location of agents, while the local observation of an agent may only contain the location of other agents within a limited distance. All agents' local observations form a joint observation, denoted by o'.
M V,, where V, C R (Samvelyan et al. 2019 Lowe et al. 2017 Rashid et al. 2018 Foerster et al. 2018 Mahajan et al.) 2019). We refer to V as a "state component." The set of all component spaces of a product space referred to as the component set. For instance, the component set of S is {Vi E (1...., M]}. Each entity, e.g., agents, objects, etc., in the environment are described by a set of state compo- nents. We refer to set of state components that is associated with entity in the environment as an 'entity set.' For instance, in a 2-agent push-box environment, where two agents can only collaboratively push a box to a goal location, we have the global state space S = I[ V,, where (Vi, V2), (V,, V4), }, (V,, Va} represent the location of agent one, agent two, and the box, separately. Consequently, {V1, V2J. (V., V4), (Vs, Vo} are three entity sets.
global state space S is the product of component spaces V,, i.e.,
2.2 MULTII-GRNT REINFOR LEARNING
In this paper, we follow the standard centralized training and decentralized execution (CTDE) paradigm (Lwe et al., 2017 Rashid et al., 20188) Focrster et al. 20188 Mahajan et al. 2019). That is, training time, the learning algorithm has access to all agents' local observations, actions, and the global state. At execution time, i.e,, at test time, each individual agent's 's policy only has access to its own local observation.
The proposed CMAE is applicable to off-policy MARL methods (e.g., Rashid et al. 2018 Lowe
al. 2017 Sunehag al. 2018; Matignon et al. 2012) In off-policy MARL, exploration poli-
2

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Training with Coordinated Multi-Agent Exploration (CMAE)
Initialize exploration policies (μ: K== target policies (TT)) counters fcs Jimi Initialize the environment and replay buffer DD Initialize = 1; for episode = 1.... do Reset the environment, and observe global states sf and observations o' = ..) for t 1... do UpdateCouuner(((a) o'))
Select actions a' using a mixture exploration and target policies a44 + (1 a.m
a decreases linearly to 0;
Apply a' to the environment:
Observe rewards r", state s and local observations o²+1;
Add transition tuple {s", o', sa,s o r²) to D;
TrainTarget( (f 12 D);
end
TrainExp( ( fc* {c*] D);
end
cies Mi, E {l,..., n2 are responsible for collecting data from the environment. The data in the form of transition tuple (s', o a', , s441, , stored in replay memory D, i.e., f(s', of, a', s )). The target policies are trained using transition tuples from the replay memory.
COORDINATED MULTI-AGENT EXPLORATION (CMAE)
In the following we first present an overview of CMAE before we discuss the method more formally.
The goal is to train the target policies { (ie (1......} of n agents to maximize the en- vironment episode return. Classical off-policy algorithms (Lowe al. 2017, Rashid et al.) 2018) typically use noisy version of the target policies Ti as the exploration policies μ4. i.e., to collect data actions are selected based on exploration policies μ4, In contrast, in CMAE, we propose train the exploration policies by training with modified reward. Specifically, target polices are trained to maximize the usual external episode return. In contrast, exploration policies are trained to collect data from subspaces that haven't 't been well explored. We find this strategy to significantly improve training of target policies in the multi-agent reinforcement learning setting because this strategy can encourage multiple agents jointly explore configurations of the state space.
Overview:
Alg. I summarizes this approach. At each step, mixture the exploration policies {nr) and target policies {TT { are used to select actions. The resulting experience tuple is then stored in replay memory D. The target policies are trained directly using the data within the replay memory D at each step. Note that the exploration policies will only be updated the end of each episode using a reshaped reward that encourages exploration polices to explore under-explored subspaces in collaborative manner.
In the following we will provide details about how we propose to train the exploration policies.
3.1 TRAINING OF EXPLORATION POLICIES
To train the exploration policies (45, E [1.....m] we use modified reward A. This modified reward specifies the goal of the exploration. For example, in the two-agent push-box task, specify a specific joint location of both agents and the box as a goal. Note, the agents will ignore all external rewards and only
positive reward when the goal, i.e., the specified position is reached. The reward for the goal is set to b while the rewards for all other situations are zero.
To find the goal situation
K counters Ck. k (1....,K) K). A counter C operates dow-dimensional subspace S₂ of the state space S, i.e., S, S. Occurrence of every configuration 8k E Sz. within the low-dimensi subspace will be recorded using the current replay buffer D.
3

---

Under review as a conference paper at ICLR 2021
Algorithm 2: Train Exploration Policies (TrainExp)
Input: exploration policies (14)²=1 counters {cx } replay buffer D; Initialize bonus b;
Compute normalized entropy (1k) of subspace k based on associated counter cx: k* = arg min; <7k;;
Sample batch = } from D; J.M
g arg se Cx. (projx (s));
for {s* o', a,st+1, o r²) E do
if = then
r²
else
p" 0:
end
Update {uil-n by (s' o' a,, ,
end
Let proje be the projection from global state space to the subspace k. Formally, we obtain
(s()
Σ SED
[projj (s) = sk].
where [[:] is the indicator function (1 if argument is true; O otherwise) and proja (s) denotes the restriction of state s E to subspace Sy. Note that we are successively incrementing the counts, i.., the counters e are not recomputed from scratch every time we train the exploration policies.
We subsequently normalize the counters cx(*:) into a probability distribution Pr (8x) (x())// Esees Cs (8x) which is then used to compute normalized entropy T/2 H mmxx -(Eoes, Ph (s) log pa (s))/ Ixg([S+)). We select the subspace k* with the smallest normalized en- tropy. From this subspace we choose the joint goal state by first sampling a batch of states B from the replay buffer. From those states we select in second step the state with the smallest count the goal state i.e,, = arg mingen CKe (8). Sampling of states is performed in order to avoid selecting unreachable states as goal, i.e., we encourage explore states that have seen rarely but least once.
Given the goal state g. train the exploration policies 14, using the replay buffer 'D modified by revised reward f = b if sy. = Note, f = 0 otherwise. Consequently, the exploration policies pi focus exclusively on achieving the desired goal g. This strategy is summarized Alg. 2
As an alternative to the aforementioned subspace selection method, one could use probabilistic subspace selection, where the probability of subspace being chosen is inversely proportional its normalized entropy. The two different subspace selection approaches result in different exploration behaviors. Specifically, the probabilistic subspace selection will encourage exploration policies to explore more subspaces while the smallest normalized entropy method focuses on the most under- explored subspace.
3.2 SELECTING SUBSPACES
Which K subspaces do we choose? As discussed in Sec. 2.1 we assume the global state space S to be composed out of a set of . component spaces V. The number of possible subspaces is equivalent to the size of the powerset, i.e., 2MM This is clearly intractable.
To address this, we select subset of subspaces in levels. In each level we consider entities jointly. Recall, that entities are agents, objects, etc., that are represented within the state space S. Suppose the global state space has N entity sets Ai...., Av. In level < N, subspace's 's component set is the union of distinct entity sets. Formally, let DE be a component set subspace in level 1, we have
DE = U A, VE (th.....)))
IEE
4

---

Under review as a conference paper at ICLR 2021
where (f).,..0))) represents the set of all I-combinations of ......,N..
Note that there are many equivalent component sets in a level, if agents are homogeneous, ie., agents have identical action and observation space and are controlled by the same policy.
To see this, consider the two-agent push-box task again. The state space S is composed of the com- ponent set (V1, V2, Va, Va. VG. Ve}, with three entity sets {Vi, V2), (Vs, Va), (Vs, Vo} representing the location of agent one, agent two, and the box. Suppose the two agents are homogeneous. The component sets (Vi V22 Vg, Vol and (V3, V4, Vg. Vol are equivalent, because both of them consider the locations of one agent and the box jointly. Since the agents are homogeneous, it is irrelevant which agent is considered. Assigning different counters to equívalent subspaces will encourage an exploration policy to visit states that are visited by fellow homogeneous agents. This results in less efficient exploration. Therefore, equivalent subspaces share one common counter. The subspace Sk a counter Cj is associated with is defined by S NVLDDR V,, where Eg is a component set of subspace k.
In addition, we also consider level 0, where the component set of each subspace has only one ele- ment. Empirically, we found that level subspace leads very efficient exploration in some tasks.
Note that this strategy of selecting subspaces is relatively simple still and does not scale well. We defer development of more complex selection strategies future work. Here we are primarily interested in studying the efficacy of training an exploration strategy with such rewards, which we study in the next section.
EXPERIMENTAL RESULTS
We evaluate the proposed CMAE approach on two challenging environments: 1) the sparse-reward cooperative task from Wang et al. (2020): 2) the sparse-reward version of the Starcraft multi-agent challenge (SMAC) (Samvelyan et al. 2019). In both environments, agents need to coordinate their behavior over extended periods of time to obtain reward.
Environments: We first consider the following four tasks on the sparse-reward environments pro- vided by Wang et al. (2020):
Pass: Two agents operate within two rooms of 30 x 30 grid. There is one switch in each room, the rooms are separated by a door and agents start the same room. The door will open only when one of the switches is occupied. The agents see collective positive reward and the episode terminates only when both agents changed to the other room. The task is considered solved if both agents are in the right room.
Secret-room: Secret-room extends Pass. There are two agents and four rooms. One large room the left and three small rooms the right. There is one door between each small room and the large room. The switch in the large room controls all three doors. The switch in each small room only controls the rooms door. The agents need to navigate one of the three small rooms, i.e. target room, to receive positive reward. The grid size is 25 x 25. The task is considered solved if both agents are in the target room.
Push-box: There are two agents and one box in 15 x 15 grid. Agents need to push the box to the wall to receive positive reward. The box is heavy, so both agents need to push the box in the same direction at the same time to move the box. The task is considered solved if the box is pushed to the wall.
Island: Two agents, nine treasures, and a wolf operate in 10 x 10 grid. Agents get col- lective reward of 10 for collecting a treasure and a collective reward of 300 when crushing the wolf. The wolf and agents have maximum energy of eight and five respectively. The energy will decrease by one when being attacked. Therefore, one agent cannot crush the wolf. The agents need to collaborate complete the task. The task is considered solved if the wolf killed.
We also consider four tasks in SMAC Samvelyan et al. 2019):
3m-dense: There are three marines in each team. Agents need to collaboratively eliminate the three marines the other team. An agent sees a reward of +1 when it causes damage
5

---

Under review as a conference paper at ICLR 2021
Secret
Push Box
Island
Teurec
Pan con
Pai
Teyaen san
Succue Duat
0.-
8.4
m
04
0.5 Instnomment Stepe
20
0.5
1.0
20
Doviromment Stops
Envirommnn Stepe
Environmen Skepe
Figure I: Results on Pass, Secrel room, Push-box, and Island environment.
Method (target success rate)
Ours
EITI
EDTI
IDQ
IDQ + RND
Pass (80%)
2.61M 0.10M
384M 1.2M
381M
2.8M
5500
500M
Secret-Room (80%)
1.71M=0.055M
448M 10.0M
382M 9.4M
-50M
500M
Push-Box Box (10%)
0.52M=0.04M
307M+2.3M
160M=12.1NM
500M
500M
Push-Bos (80%)
0.02M
307M 9M
160M=8.2M
500M
500M
Island (20%)
7
4.0M+
322M 1.4M
500M
500M
Island (50%)
13.9M 0.211
500M
> 500M
> 500M
> 500M
Table 1: Environment steps required achieve the indicated target success on Pass, Secret Room, Push-Bot and Island environments.
to an enemy's health. A reward of - is received when its health decreases. All the rewards are collective. A reward of +220 obtained when enemies are eliminated.
8m-dense: Similar to 3m-dense, but with eight marines on each team.
3m-sparse: Similar to 3m-dense, the reward sparse. Agents only see reward +1 when all enemies are crushed.
8m-sparse: Similar to 3m-sparse, but with eight marines on each team.
Experimental Setup:
For the grid world task, we combine CMAE with Q-learning. For Pass, Secret-room, and Push- box, the Q value function is represented via a table. For Island we DQN (Mnih et al.) 2013) 2013). The Q-function is parameterized by a three-layer perceptron (MLP) with hidden units per layer and ReLU activation function. We compare CMAE with exploration via information-theonm theoretic influence (EITT) and exploration via tecision-thheoreicc influence (EDTT) (Wang et al. (020), which state-of-the-art algorithms the four tasks. EITT and EDTI (Wang al. (020)) results obtained using the official code. For a more complete comparison, we also show the results of independent Q-learning (IDQ) with e-greedy and independent Q-learning with popular single agent exploration techniques, such as random network distillation (Burda et al. (019).
For the SMAC tasks, we combine CMAE with the official code for QMIX (Rashid al. 2018). We compare with MAVEN (Mahajan et al. 2019), QMIX (Rashid et al. 2018). QTRAN (Son et al., 2019). and VDN (Sunehag et al. 2018). All of the aforementioned methods reported impressive performance on the dense-reward version of SMAC. To our best knowledge, CMAE is the first to report results on the sparse-reward version of any SMAC tasks.
For all the experiments, we consider level 0 to level 3 subspaces. Please see the Appendix for more details.
To assess efficacy of CMAE we use the following evaluation procedure: we test the target policies in an independent test environment every 400k environment steps during the training. Each test consists of ten testing episodes. We repeat all experiments using three runs with different seeds.
Evaluation Protocol:
We first compare CMAE with EITI and EDTI on Pass, Secret Room, Push-Box, and Island. The results are summarized in Fig. T where test task success rate versus number of environment steps is shown. We observe CMAE to achieve 100% success rate Pass, Secret Room, and Push- Box within 2M environment steps. In contrast, EITI and EDTI (Wang et al. 2020) need more than 300M steps to achieve an 80% success rate (Tab. 1.. In Island, CMAE achieves success rate
Results:

---

Under review as a conference paper at ICLR 2021
3m Sparse
Am Sparse
3m Dense
Dense
W
Seocuat Satee
Stutco Rota
Enviremna Skpp
Exr Eav.RNEEN Skgge
Envioranct Steps
Ice
Figure 2: Results on SMAC: 3m- 8m-sparse, 3m-dense, 8m-e environment.
Push Box Subepace Efficiency
Subspace Efficiency
Island Subspace Efficiency
2.5
Figure 3: Normalized entropy of different levels I on Push-box, Puss, and Island environments.
(capture rate) above 50% within 20M environment steps (Fig. In contrast, EITI and EDTI need more than 480M and 322M steps to achieve a 20% success rate [T. The main reasons that ETTT and EDTI need much more environment steps: they require large number of samples estimate the influence of one agent's behavior on other agents' between each update. Specifically, EITI and EDTI need 64,000 environment steps between each update, which makes them less sample efficient. IDQ with e-greedy and IDQ with RND does not achieve any success in those tasks.
On SMAC, we compare CMAE with MAVEN (Mahajan et al.) 2019), QMIX (Rashid et al. 2018). QTRAN (Son et al. 2019), and VDN (Sunehag et al., 2018). The results are summarized in Fig. In sparse-reward tasks, MAVEN, QMIX, QTRAN, and VDN have at most 2% winning rate. In contrast, CMAE achieves win rate higher than 80%. Recently, Taiga et al. (2020) point out that many existing exploration strategies excel in challenging sparse-reward tasks but fail in simple tasks that can be solved by using classical methods such as e-greedy. To ensure CMAE doesn't fail
in simpler tasks, we run experiments on dense-reward SMAC tasks. As shown in Fig. 2 CMAE achieves similar performance to state-of-the art baselines in simpler dense-reward SMAC tasks.
To investigate which subspaces CMAE selects, we plot the normalized entropy of different sub- spaces in Fig. 3, In the Push-Box task, CMAE mostly chooses the boxes location explore. In the Island task, CMAE mostly explores the health of the wolf. For the Pass task, instead of exploring subspaces, CMAE explores the full global space.
We also compare the exploration behavior of CMAE to e-greedy using the Secret room environment. As shown in Fig. early during training, both CMAE and e-greedy explore only locations in the left room. However, after 1.5M steps, CMAE agents are able to frequently visit the right three rooms while e-greedy still mostly visits the left room.
Following the reviewers' suggestions, we also consider a shared count-based bonus on the group observations as a baseline. We study Q-learning with this shared count-based bonus on the group observations for the Secret-room and Push-box tasks. The shared count method achieves a 5.1% + 1.3% and 2.2% + 1.1% success rate on Secret-room and Push-box respectively. In contrast, our approach can achieve 100% + 0.1% success rate in both tasks. The training curves are shown in Fig. 5 The count-based bonus method is sub-optimal because group observation not necessarily the most efficient subspace to explore. This demonstrates the effecctivnness of our subspace selection mechanism.
In addition, to demonstrate CMAE is applicable to wide variety of challenging tasks. We conduct experiments on the SMAC Sh_vs_82-denss (super hard) and 6h.vs_ -t-saar (super hard) tasks, where the opponent agents' AI are set the 'super hard' level. In 6h_vs_8 -r-dense (super hard), an agent sees a reward of +1 when it causes damage to an enemy's ' health. A reward of - is received when its health decreases. In 6h 8z-sparse (super hard), an agent only see non-zero
7

---

Under review as a conference paper at ICLR 2021
300K env. steps
1.5M env. steps
Agent
Agent
Agent
Agent 2
e-greedy
Figure 4: Visitation map of Ours (CMAE) and baseline the Secret-Room environment.
Secret Room
Push Box
Dmxi Sk.nel cordi
Saindiore
0.8
0.8
Success Rate
0.5
0.6
Success
0.4
0.2
0.2
0.8
0.0
0.5
Environment Steps
lef
Environment Steps
le6
Figure 5: Results of our approach and shared count baseline Secret-room and Push-box.
reward when opponent is eliminated or a teammate is eliminated. We compare our approach to MAVEN Mahaaaa et al. 2019), which reports the state-of-the-at results on this task. All approaches are trained for 8M steps. In 6h.vs st.ys_8--sparss (super hard), CMAE achieves 45.6% 3.2% win rate while MAVEN achieves a 4.3% + 0.9% win rate. In 6h vs 8z-dense (super hard), CMAE and MAVEN achieve 60.9% + 1.3% and 61.2% +: 2.3% success rate respectively. This illustrates that dense reward environments tend to be easier than sparse ones. The training curves are shown in Fig.
RELATED WORK
We discuss recently developed methods for exploration in reinforcement learning, multi-agent rein- forcement learning and concurrent reinforcement learning subsequently.
Exploration for Reinforcement Learning: A wide variety of exploration techniques for deep rein- forcement learning have been studied, deviating from classical noise-based methods. Generalization of count-based approaches, which give near-optimal results in tabular reinforcement learning, to en- vironments with continuous state spaces have been proposed. For instance, [Bellemare al. (2016) propose density model to measure the agent's uncertainty. Pseudo-counts are derived from the density model which give rise to an exploration bonus encouraging assessment rarely visited states. Inspired by BBllemare et al. (2016), Ostrovski et al. (2017) discussed neural density model, to estimate the pscudo count, and Tang et al. (2017) use hash function to estimate the count.
Besides count-based approaches, meta-policy gradient Xu et al. (2018) uses the actor policy's im- provement as the reward to train an exploration policy. The resulting exploration policy differs from the actor policy, and enables more global exploration. Stadie et al. (2066) propose exploration strategy based on assigning an exploration bonus from a concurrently learned environment model. Lee al. 2020 cast exploration state marginal matching (SMM) problem and aim learn
8

---

Under review as a conference paper at ICLR 2021
6h8z sparse
6h8z dense
Oul
Oct
0.4
0.5
Saxcess Rate
0.3
0.4
Success
0.2
0.2
6.3
6.3
0.6
0.0
04
Environment Steps
1c7
Enviromment Steps
167
Figure 6: Results of our approach and MAVEN on 6h_vs_ 82-sparre (super hard) and th_ 8z-dense (super hard).
a policy for which the state marginal distribution matches a uniform distribution. Other related works on exploration include curiosity-driven exploration Pathak et al. (2017), diversity-driven ex- ploration Hong et al. (2018), GEP-PG Colas et al. (2018), EX* Fu et al. (2017). and bootstrap DQN Osband et al. (2016). In contrast to approach, all the techniques mentioned above target single-agent deep reinforcement learning.
Multi-agent Reinforcement Learning: MADDPG Lowe et al. (017)) uses central critic that considers other agents' action policies to handle the non non-stationary environment issues in the multi- agent setting. DIAL et al. (2016) uses an end-to-end differentiable architecture that allows agents to learn to communicate. Diang & Lu (2018) propose an attentional communication model that learns when communication helpful for cooperative setting. Foerster et al. (2017) add 'fingerprint' to each transition tuple in the replay memory to track the age of the transition tuple and stabilize training.
Self-Other-Modeeling (SOM) Raileanu et (2018) an agent uses own policy to predict others agents' behavior and states.
While inter-agent communication Lowe et al. (2017): Jiang & Lu (2018); Foerster et al. (2016); Rashid et al.) (2018) Omidshatiii et al. (2017 ain et al. (2019) has been considered, for expl oxation multi-agent approaches rely on classical noise-based exploration. As discussed in Sec. a noise- based approach prevents the agents from sharing their understanding of the environment. A team of cooperative agents with a noise-based exploration policy can only explore local regions that are close to their individual actor policy, which contrasts the approach from the proposed method.
Recently, approaches that consider coordinated exploration have been proposed. Multi-agent varia- tional exploration (MAVEN) (Mahajan et al. (0199) introduces latent space for hierarchical control. Agents condition their behavior on the latent variable to perform committed exploration. Influenced- based exploration (Wang et al., 2020) captures the influence of one agent's behavior on others. Agents are encouraged to visit iinteraction points' that will change other agents' behaviour.
Concurrent Reinforcement Learning: Diiakkopulou & Roy (018) study coordinated explo- ration in concurrent reinforcement learning, maintaining an environment model and extending pos- terior sampling such that agents explore in coordinated fashion. Parisotto et (2019) proposed concurrent meta reinforcement learning (CMRL) which permits set of parallel agents to communi- cate with each other and find efficient exploration strategies. The concurrent setting fundamentally differs from the multi-agent setting of our approach. In a concurrent setting, agents operate in differ- ent instances of an environment, i.e., one agent's action has no effect on the observation and rewards received by other agents. In contrast, in the multi-agen setting, agents use the same instance of an environment, An agent's action changes observations and rewards observed by other agents.
CONCLUSION
We propose coordinated multi-agent exploration (CMAE). It defines shared goals and learns coor- dinated exploration policies. We studied subspace selection which helps to find a goal for efficient exploration. Empirically, we demonstrate that CMAE increases exploration efficiency significantly. Compared to of-te-o-thhe-rrd art baselines, CMAE needs only 5% of the data to achieve similar or better results on various sparse-reward tasks. We hope this is first step toward efficient coordinated MARL exploration. Going forward we will study more complicated subspace selection techniques and scale to more agents.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ana L. C. Bazzan, Opportunities for multiagent systems and multiagent reinforcement learning in traffic control. Proc. AAMAS, 2008.
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi
Munos. Unifying count-based exploration and intrinsic motivation. In Proc. NeurlPS, 2016.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In Proc. ICIR, 2019.
Cédric Colas, Olivier Sigaud, and Pierre Yves Oudeyer. GEP-PG: Decoupling exploration and exploitation in deep reinforcement learning algorithms. In Proc. ICML, 2018.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley- Ieley-nnterccience, 1991.
Maria Dimakopoulou and Benjamin Van Roy. Coordinated exploration in concurrent reinforcement learning. In Proc. ICML, 2018.
Jakob Foerster, Nantas Nardelli, Gregory Farquhar, Triantafyllos Afouras, Philip H. S. Torr, Push- meet Kohli, and Shimon Whiteson. Stabilising experience replay for deep multi-agent reinforce- ment learning. In Proc. ICML, 2017.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proc. AAAI, 2018.
Jakob N. Foerster, Yannis M. Assael, Nando de Freitas, and Shimon Whiteson. Learning com- municate with deep multi-agent reinforcement learning. In Proc. ICML, 2016.
Justin Fu, John D. Co-Reyes, and Sergey Levine. Ex2: Exploration with exemplar models for deep reinforcement learning. In Proc. NeurlPS, 2017.
Zhang-Wo Wei Hong, Tzu- Yun Shann, Shih- Yang Su, Yi-Hsiang Chang, and Chun-Y Yi Lee. Diversity-
driven exploration strategy for deep reinforcement learning. In Proc. NeurlPS, 2018.
Maximilian Hüttenrauch, Adrian Šošić, and Gerhard Neumann. Deep reinforcement learning for swarm systems. JMLR, 2019.
Unnat Jain, Luca Weihs, Eric Kolve, Mohammad Rastegari, Svetlana Lazebnik, Ali Farhadi, Alexan- der Schwing, and Aniruddha Kembhavi. Two body problem: Collaborative visual task comple- tion. In Proc. CVPR, 2019.
Jiechuan Jiang and Zongging Lu. Learning attentional communication for multi-agent cooperation. In Proc. NeurlPS, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. Proc. ICLR, 2015.
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhut- dinov. Efficient exploration via state marginal matching. In arXiv. 2020.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compettivee environments. In Proc. NeurIPS, 2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. MAVEN: multi-agent variational exploration. In Proc. NeurIPS, 2019.
Laetitia Matignon, Guillaume j. Laurent, and Nadine Le fort piat. Independent reinforcement learn- ers in cooperative markov games: survey regarding coordination problems. The Knowledge Engineering Review, 2012.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. In NeurIPS Deep Learning Workshop, 2013.
10

---

Under review as a conference paper at ICLR 2021
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonogiou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane I Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 2015.
Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan How, and John Vian. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In Proc. ICMI., 2017.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. In Proc. NeurIPS, 2016.
Georg Ostrovski, Marc G. Bellemare, Aaron den Oord, and Remi Munos. Count-based explo- ration with neural density models. In Proc. ICML, 2017.
Emilio Parisotto, Soham Ghosh, Sai Bhargav Yalamanchi, Varsha Chinnaobireddy, Yuhuai Wu, and Ruslan Salakhutdinov. Concurrent meta reinforcement learning. In arXiv., 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In Proc. NeurIPS, 2017.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proc. ICML, 2017.
Roberta Raileanu, Emily Denton, Arthur Szlam, and Rob Fergus. Modeling others using oneself in multi-agent reinforcement learning. In Proc. ICML, 2018.
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. In Proc. ICML, 2018.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. J. Rudner, Chia-Man Hung, Philip H. Torr, Jakob Foerster, and Shimon White- son. The starcraft multi-agent challenge. In arxiv. 2019.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Proc. ICML, 2019.
Bradly C. Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. In Proc. ICLR, 2016.
Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojeiech Marian Czareekki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, and Thore Graepel. Value- decomposition networks for cooperative multi-agent learning based team reward. In Proc. AAMAS, 2018.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 2018.
Gokul Swamy, Siddharth Reddy, Sergey Levine, and Anca D. Dragan. Scaled autonomy: Enabling human operators to control robot fleets. In Proc. ICRA, 2020.
Adrien Ali Taiga, William Fedus, Marlos C. Machado, Aaron Courville, and Marc G. Bellemare. On bonus based exploration methods in the arcade learning environment. In Proc. ICLR, 2020.
Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning. In arxiv, 2015.
Ming Tan. Multiagent reinforcement learning independent vs cooperative agents. In Proc. ICML, 1993.
11

---

Under review as a conference paper at ICLR 2021
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Exploration: A study of count-based exploration for deep reinforcement learning. In Proc. NeurlPS, 2017.
George E. Uhlenbeck and Leonard S. Ornstein. On the theory of the brownian motion. Physical Review, 1930.
Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang. Influence-based multi-agent explo- ration. Proc. ICLR, 2020.
Tianbing Xu, Qiang Liu, Liang Zhao, and Jian Peng. Learning to explore via meta-policy gradient. In Proc. ICML, 2018
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In Proc. ICML, 2018.
12


Reviews:
[{"review_id": "Za0xr7LSuO3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "## Overview\n\nThis paper proposes an exploration method for collaborative multi agent RL similar to count-based approaches in single-agent RL. It then provide some experimental analysis of the method in two kinds of environments (Starcraft and multi-agent particle-based environments)\n\nOverall, the exposition of the method lacks clarity, and the experimental results suffer some limitations. Therefore, I am not recommending this paper for acceptation at ICLR 2021.\n\n## Method\n\nThe algorithm considers all the variables of the problem $V_1,\\cdots,V_M$, which can sometimes be grouped when they correspond to the same agents (eg there are two variables for the x,y coordinates of a given agent).\nAt the core, a counter is incremented when a given subset $\\mathcal{S}_k$ (\"a low dimensional subspace\") of the variables reach a given \"configuration\", which is then used to identify subsets of variables that have rarely been attained. An intrinsic reward is then used to train a policy to reach these rare configurations.\nSeveral things are unclear to me:\n* The exploration are trained at the end of episode, and since the counts have changed since the last episode the target configuration (thus the reward) will change too. However it is not clear if the exploration policy is retrained from scratch or simply fine-tuned from the previous iteration\n* It is not clear what a \"configuration $s_k\\in\\mathcal{S_k}$\" is. According to section 2.1, the variables $V_i$ are assumed to be in $\\mathbb{R}$, thus finding the exact same configuration several times over the course of training seems unlikely. I assume there is some kind of discretization applied, but more details are required here. In particular, the exact way a configuraton is defined determines how many configurations are being tracked and thus the complexity of the algorithm (both in space and time), which is not discussed.\n\n\nSection 3.2 describes how the subset of variables are being selected. Essentially, the sets are designed such that the variables of a given entity are always in the same subset, and then only subsets of entities of a limited size (l) are being considered.\nIn practice, the exact value of $l$ doesn't seem to be specified in the paper. Also lacking is the actual number of subspaces that the choice of $l$ incurs in each of the considered environments, and how the choice of $l$ influences the performance the performance of the algorithm (both in terms of final reward and runtime/memory)\n\nTowards the end of section 3.2, one can read:\n\n> In addition, we also consider level 0, where the component set of each subspace has only one element. Empirically, we found that level 0 subspace leads to very efficient exploration in some tasks\n\nI don't quite understand what this level 0 corresponds to. Is it simply a subspace per variable (as opposed to a subspace per entity set, which in my understanding would be level 1) ?\nAs for the empirical claim, it doesn't seem to be backed by any experiments of the experimental section. We note that at one variable per variable, the algorithm would reduce to a standard count-based (single agent) exploration scheme. If such scheme are found to be efficient, they should be benchmarked in the experiments, which they currently aren't.\n\n\n## Experiments\n\nThe authors provide experiments on two domains: some discrete multi-agent particle world environments and some starcraft scenarios (from SMAC). Overall, the experimental results suffer some limitations that undermine the strength of the claim.\n\n### Particle environments\n\nThe environments are introduced in [1], and the authors directly compare to the results of the corresponding paper.\nThe proposed exploration method is applied on top of different base learning algorithms (sometimes vanilla tabular Q-learning, sometimes DQN). This inconsistency isn't discussed and make comparison between algorithms quite challenging since it adds a moving part.\n\nThe authors provide comparison with the methods proposed from [1], EDTI and EITI. However the comparison doesn't seem entirely fair. In [1], the authors reported (and presumably optimized for) the number of environment steps, while this papers reports the number of environment steps. These are two distinct metrics, and it is reasonable to believe that small adjustments would make EDTI and EITI much more competitive in terms of environment frames. For example, in [1] they used returns of length 2048 (at it is the default in PPO2), but based on ppo2 performance in environments like Atari, a much more conservative return length (say 128 or 256) could have sufficed, thereby drastically improving the sample complexity. Similarly, reducing the batch-size could improve the sample complexity as well. As it stands, the claim \" Specifically, EITI and EDTI need 64,000 environment steps between each update, which makes them less sample efficient\" isn't backed by any experimental evidence.\nIt is not clear how the number of environment-steps that are reported in table 1 are obtained. In particular, despite the fact that the experiments were run multiple times, the table doesn't reflect any kind of confidence interval. This is problematic because the environment \"Island\", for example, exhibits quite a high variance in Figure 1. While table 1 claims that 50% success rate is achieved at 13.9M steps, Figure1 shows that, on average, the success rates dips below 50% after 17M, which raises question on the stability of the learnt policy.\n\n### Starcraft\n\nThe paper presents the results on the two easiest Starcraft environments of the SMAC set, either with sparse rewards (+1 for victory, -1 for defeat) or with dense rewards.\nContrary to the other environments, the authors don't provide a comparison with EDTI and EITI, which is unfortunate as they appear to be the strongest available baseline to date.\nAmongst the reported baselines, CMAE is the only methods achieving decent win-rate on the sparse environments, and it appears to match the performance of the baselines on the dense counter-part, which is encouraging.\nIt has to be noted that, according to the training curves in appendix, it appears that the baselines learnt a fleeing strategy (ie never engaging the enemy, thus never \"solving\" the task), which, while clearly sub-optimal, is a local optimum. Perhaps a table reporting the average returns of each method could paint a more accurate picture.\n\nFinally, it's unfortunate that the paper sticks to these two easy environments. Understanding the failure modes in the easiest environment that can't be solved by this method would yield significantly more insights on the methods than near-perfect scores on easy tasks. In particular, in the MAVEN paper [2], results on harder (dense) starcraft tasks were reported, and it would be valuable to see how the proposed method performs on those.\n\n\n[1] Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang. Influence-based multi-agent explo-ration. InProc. ICLR, 2020\n[2] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. MAVEN: multi-agentvariational exploration. InProc. NeurIPS, 2019\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AFPeknCI_oT", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposes to improve the exponential sample complexity of finding a coordinated multi-agent strategy by learning an exploration policy for each agent that conditions on a shared goal. The exploration policy is mixed with the normal RL policy according to a parameter alpha, which is scaled down over time. The shared goal that agents pursue is selected by using an explicit counter mechanism over objects in the environment. \n\nStrengths:\n- The paper is well written.\n- The reduction in sample complexity due to this technique is very large.\n- Algorithms 1 and 2 are clear.\n\nWeaknesses:\n- The proposed counter mechanism relies on being able to manually identify entities in the environment, such as the box in the push-box environment. This has limited applicability to real-world problems with large-dimensional or visual state spaces, in which entities are not obvious a priori. Being able to explicitly count the number of times an agent has experienced an entity in a specific configuration is not a realistic expectation for interesting, real-world problems. Therefore, it is unclear how this method can be applied beyond simple tabular settings and video games.\n- Similarly, it seems that deciding which subspaces are equivalent requires a significant amount of domain knowledge into each problem, and does not seem to be generally applicable. \n- Why not benchmark against QMIX + RND, since both are tested independently? \n\nOther suggestions:\n- Typo on p. 3 \"tuple is then store in a replay memory\" -> stored\n- Why was the number of steps between updates for EITI and EDTI held constant at 64,000? How many steps between updates were used for the proposed technique? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "4O1aLIyii_R", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "---Post rebuttal---\n\nThank you for the detailed response. My main concern was regarding the scalability of the method to larger environments, e.g. w/ visual state space. I agree with the other reviewers regarding limited applicability of the method, and maintain my original score (Weak Reject).\n\n---\n\nThe paper introduces a coordinated multi-agent exploration method that selects goals based on normalized entropy from multiple projected state spaces. The method greatly outperforms other algorithms on sparse-reward environments.\n\nWeaknesses:\n\n1. The process of selecting subspaces in the CMAE algorithm (Section 3.2) is not scalable to larger environments. I’d be willing to raise my score if, in more complex environments, using level 0 subspace still results in improved performance over existing work.\n\n2. The related works section seems incomplete. It discusses single-agent exploration, concurrent RL, and multi-agent noise-based exploration (p.8), but these categories do not cover the following papers:\n[1] Concurrent Meta Reinforcement Learning (Parisotto et al., 2019): Parallel multi-agent exploration in the same environment using shared memory and communication.\n[2] Efficient Exploration via State Marginal Matching (Lee et al., 2019): Multi-task/multi-agent exploration that learns multiple “skills” (or “agents”) in the same environment, that together match some target state density.\n\nMinor typo:\n- “The resulting experience tuple is then stored* in a replay memory” (p.3)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2aaWYWg1sLF", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary of paper:\nThe paper introduces an exploration bonus tailored to multi-agent learning in the CTDE (centralized training, decentralizing execution) setting. The bonus works by: 1) dividing up the observation space into subspaces (in this case, corresponding to the entities, pairs of entities, triplets of entities, etc), 2) maintaining running counters within each subspace of every possible configuration within that subspace, 3) identifying the lowest entropy subspace, 4) sampling the replay buffer to find a rarely occurring (but importantly, reachable) “goal” state within the lowest entropy subspace, and finally, 5) rewarding the exploration policy for visiting the goal state. The authors test their method in two domains: 1) a series of coordinated multi-agent exploration challenges in grid worlds, and 2) the Starcraft Multi-Agent Challenge (SMAC). They demonstrate much faster learning over a series of baselines.\n\nPros:\nThe paper is generally well-written. The paper uses interesting tasks, and the experiments are generally well-structured. The experiments include modern baselines, and the sample efficiency over the baselines is impressive (at least at first glance).\n\nCons:\n1) I don’t think the authors adequately convinced me that there is a new problem to solve here that couldn’t be tackled with straightforward applications of single-agent exploration methods in the multi-agent setting. I assume their IDQ + RND baseline applies the RND bonus independently to each agent (i.e. each agent has a separate target network to predict)? That is a useful baseline for sure, but its not exactly very strong. Why not use a single RND bonus for the *group* observations to induce correlated exploration? Since this is the CTDE setting, single-agent exploration bonuses can be applied somewhat straightforwardly to the group. Even simpler, why not include a simple count-based bonus on the group observations (i.e. r(s)=1/sqrt(c(s)), where c(s) is the count of the group observation s)? The authors’ method is more or less a group count-based exploration bonus that also takes advantage of structured observations, so this baseline is both possible and relevant.\n2) The authors’ method seems to me to build in a lot more hand-crafted knowledge than they let on (and more than any of their baselines, as far as I can tell). Their method requires structured knowledge of the agent’s observations (e.g. these variables correspond to these entities), which is not always available (e.g. from pixels). Can the authors comment on the fairness of comparing their method to the baselines they use, as well as the scalability to less structured observation spaces?\n3) Additionally, it looks to me like their method would be fooled by a large number of unreachable states for one entity - in this case, Hmax would be large, so the normalized entropy would be small, and the agent would keep exploring a particular entity set of variables, without progress. For example, imagine a world with two boxes, one which is movable, and one which is not, but imagine the agent does not know in advance that one is unmovable. CMAE would focus on the unmovable box forever (granting a fixed useless exploration bonus for the single state the box has ever and will ever occupy). Can the authors comment on this?\n\nQuestions:\n1) I understand how counting observations works in the grid worlds, but isn’t SMAC a continuous state space? How does counting work there? More generally, can you comment on how the method would work in continuous state spaces (e.g. binning, neural density models, etc)?\n2) Maybe I missed it, but how many subspaces (K) are there in these experiments? The authors state that 2^M is “clearly intractable” (where M is the number of component subspaces) but seem to imply that 2^N is tractable (where N is the number of entity subspaces). However, M and N are not obviously very different numbers, depending on the number of components per entity.\n3) Deterministically focussing exploration on the lowest entropy subspace seems potentially unstable (e.g. in presence of many unreachable states - see comment above). Did the authors consider probabilistic subspace selection, in which the subspace is chosen from, say, a softmax distribution over the subspace entropies?\n4) In the discussion of “Exploration for Reinforcement Learning”, the authors state “In contrast to our approach, all the techniques mentioned above target single-agent deep reinforcement learning.” Strictly speaking, this is true, but can’t most (if not all) single-agent exploration techniques be applied to multi-agent in the CTDE setting by treating the group as the agent?\n\nTypos/formatting:\n1) Figure 3 legends are nearly impossible to read. Find space to increase their size.\n2) Figure 2 legends are a) too small and b) the same across all 4 subplots, so just use one large legend on the right.\n3) In paragraph under Figure 3: “SMAC achieves similar performance…” -> “CMAE achieves similar performance…”\n4) In the Multi-Agent RL part of Related Work, there are some citep<->citet mishaps.\n5) Conclusion: “increase” -> “increases”\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an approach to multi-agent coordination using goal-driven exploration on subspaces of the observation space.

The results of the paper show that the authors' approach performs baselines on grid worlds and two tasks from the StartCraft Multi-agent Challenge. While the rebuttal clarified many points raised by the reviewers, there was an agreement that the paper should be more convincing regarding the applicability of the approach. The reviewers were concerned with the scalability of the approach to larger environment, as well as the amount of hand-crafting/domain knowledge required to apply the approach. Overall, while the paper contributes interesting results showing that such domain knowledge can help when properly leveraged, it feels like the approach needs be validated on more challenging environments before acceptance.

Decision: Reject