Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ---Post rebuttal---

Thank 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).

---

The 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.

Weaknesses:

1. 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.

2. 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:
[1] Concurrent Meta Reinforcement Learning (Parisotto et al., 2019): Parallel multi-agent exploration in the same environment using shared memory and communication.
[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.

Minor typo:
- “The resulting experience tuple is then stored* in a replay memory” (p.3)

review_title: The proposed method outperforms prior work, but does not seem scalable to larger environments

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

Strengths:
- The paper is well written.
- The reduction in sample complexity due to this technique is very large.
- Algorithms 1 and 2 are clear.

Weaknesses:
- 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.
- 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. 
- Why not benchmark against QMIX + RND, since both are tested independently? 

Other suggestions:
- Typo on p. 3 "tuple is then store in a replay memory" -> stored
- 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? 
review_title: Proposed technique has limited applicability 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary of paper:
The 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.

Pros:
The 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).

Cons:
1) 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.
2) 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?
3) 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?

Questions:
1) 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)?
2) 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.
3) 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?
4) 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?

Typos/formatting:
1) Figure 3 legends are nearly impossible to read. Find space to increase their size.
2) Figure 2 legends are a) too small and b) the same across all 4 subplots, so just use one large legend on the right.
3) In paragraph under Figure 3: “SMAC achieves similar performance…” -> “CMAE achieves similar performance…”
4) In the Multi-Agent RL part of Related Work, there are some citep<->citet mishaps.
5) Conclusion: “increase” -> “increases”

review_title: Unconvinced that single-agent exploration bonuses applied to the group aren't enough in the CTDE setting

final_score: rating: 4: Ok but not good enough - rejection
review_content: ## Overview

This 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)

Overall, 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.

## Method

The 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).
At 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.
Several things are unclear to me:
* 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
* 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.


Section 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.
In 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)

Towards the end of section 3.2, one can read:

> 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

I 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) ?
As 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.


## Experiments

The 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.

### Particle environments

The environments are introduced in [1], and the authors directly compare to the results of the corresponding paper.
The 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.

The 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.
It 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.

### Starcraft

The 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.
Contrary 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.
Amongst 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.
It 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.

Finally, 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.


[1] Tonghan Wang, Jianhao Wang, Yi Wu, and Chongjie Zhang. Influence-based multi-agent explo-ration. InProc. ICLR, 2020
[2] Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. MAVEN: multi-agentvariational exploration. InProc. NeurIPS, 2019

review_title: Lack of clarity

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