Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

This paper is addressing the problem of hard exploration / escaping local minima in continuous control, by optimizing a population of agents for both environment reward and diversity, using both off-policy RL and Quality-Diversity (QD) optimization. Each agent is individually optimized using off-policy RL for either environment reward or diversity, and at a population level, individuals are selected using a QD method such as Map-Elites. On a hard exploration problem, Ant-Maze (Colas et al 2020), the proposed method is shown to be significantly more data-efficient compared to several other SOTA ES methods (ME-ES (Colas et al, 2020), NS-ES (Conti et al 2018), NSR-ES (Conti et al 2020)).   

Reasons for score:

The Ant-Maze results are promising and the paper is clear and well written. However, there weren't enough comparisons to relevant baselines, while a number of important algorithmic choices weren't sufficiently justified and explored. I'll expand on these points in the following paragraphs.

The experiments on Ant-Maze are the only comparison of the proposed method (QD-RL) to other baselines meant to address difficult exploration problems. The inclusion of the following comparisons and experiments would make the paper much stronger:
(1) comparison of several baselines in several different hard-exploration environments (such as Point Maze and Ant-Trap used in ablation experiments), 
(2) comparisons to PBT and RL with exploration bonuses.
I hope the authors will have such comparisons for the rebuttal phase, or if these comparisons are not suitable, I'd be interested to hear out their arguments.  

Some important algorithmic choices in the population mutation part of the algorithm, do not seem well justified or sufficiently empirically explored:
(3) The use of a single quality and diversity critic for all agents in the population does not make much sense from the RL perspective. What was the reasoning there, why not maintain a separate critic for each agent? 
(4) Why are the individual agents optimized for either quality or diversity, why not optimize for a mixture of both objectives? What determines whether an agent is optimized for quality vs diversity?  
Separately: 
(5) The choice of behavior descriptors (BD) is quite important. All the experiments in this paper involve one such function (agent xy coordinates and position increments). How sensitive is the performance wrt the choice of BDs? What about performance on non-navigation tasks?  

Questions:
- to clarify, is the novelty score reward computed as the mean distance between the state's bd_t and the closest bd_t in entire training history, current episode or experience buffer? 

Other comments:
- "Besides, evolutionary methods are very valuable when nothing is known about the function to optimize." --> can you be more precise?
- in Table 1 and 2, can you report the results and stds to two decimal points? Please also report the standard deviation for steps

-----------------------------------

UPDATE: The authors did a very good job at answering my questions and the new experimental results are very much welcomed, hence I'm updating my score from 4 to 6.

Given that this is a highly empirical paper with relatively little novelty in the key idea, more comparisons would be necessary to justify increasing the score further. While I sympathize with the lack of computational resources and access to implementations, taking some extra time to implement and run those comparisons can be done. The code for RL methods with exploration bonuses (e.g. pseudocounts, RND) is accessible and these methods are not too costly to run. Methods like PBT (whose results are typically reported using large computational resources), could be implemented and compared in a regime with much more constrained resources.
review_title: Promising, but needs more experimental comparisons and better justification for the used mutation operator

final_score: rating: 3: Clear rejection
review_content: The authors describe a QD-RL algorithm to solve continuous control problems with neural controllers. The authors state that  they maximize diversity within the population and ” the return of each individual agent”. Furthermore, the authors state that QD-RL selects agents from a Pareto front or from a Map-Elites grid. This paper is weak in estimating its performance in a clear way. The overall structure in Section 4 is not well defined and difficult to follow. Descriptions of the methods and technical details of the proposed study are incomplete. Furthermore, literature review simply lists studies without presenting a coherent and systematic introduction or critical evaluation. Overall, the contribution of the paper is not significant. 
review_title: The significance and novelty of the paper's contributions is not sufficient. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: The paper introduces QD-RL, a population-based algorithm that combines off-policy RL with Quality-Diversity based techniques for continuous control problems. The core novelty is the decoupling and concurrent optimization of diversity and performance leveraging a population-based approach. Experiments in continuous control domains demonstrate that the proposed method is able to outperform prior evolutionary methods.

Technical Quality and Clarity: The paper is well written and easy to follow. An extensive review of related literature is included that is extremely helpful in situating the work amongst the broader field. The paper makes good use of visualizations and flowcharts to communicate the ideas clearly and succinctly. The proposed method also seems technically sound and coherent. 

Novelty: The novelty of the proposed method seems marginal. Broadly, the proposed algorithm integrates diversity seeking optimizers based on archival behavior characterization (Quality Diversity / Map-Elites) within a hybrid framework that combine off-policy RL with an evolutionary population via a shared replay buffer (ERL / GEP-PG / CERL). The method then dedicates sub-populations within the evolutionary population towards co-optimizing diversity and performance - an idea similar to multiobjective speciation used widely in evolutionary literature. 

Significance: I can see the value the proposed method could bring to the field by integrating ideas from multiple fronts towards a performant solution However, a number of questions remain towards appraising this value proposition:

Both mutation operators (diversity and performance seeking) used for QD-RL seem to be based on gradients computed from the off-policy RL update, unlike evolutionary methods that have some sense of randomness to it. While this assuredly would contribute in sample-efficiency, would the loss of a random mutation operator make it more likely to get stuck in local minima that greedy gradient-based methods are known to be prone to?

On the same note, how does the computational cost (related to backpropagation) scale with the population size as each individual’s parameter update relies on computing a policy gradient with subject to its parameters? Further, it also needs to access the same replay buffer to compute its update? How does this affect computational and memory complexity? 
While tertiary to the idea, these are practical concerns essential to deployment in the real-world operation. Further, these are some key advantages of a gradient-free EA that the method is being compared to. Computing the diversity criterion using a nearest neighbour from a (large) archive also elicits a similar query.

The choice of baselines used to conduct the comparative study is very uniform. NS-ES, NSR-ES and NSRA-ES all originate in the same paper while ME-ES is a closely related method that builds on these very ideas. All these baselines are QD-methods that use ES as its optimizer. Without comparisons to a more representative sample of methods outside this family, it is difficult to quantify the significance of the results presented in the paper. 
For example, the core differential in performance in the paper is in terms of sample efficiency (Table 2). However, the central technology that enables sample efficiency is the shared replay buffer that allows the gradient-based learner to leverage the same data (transition) multiple times across varying policy parameter distributions. This is a core tenet behind hybrid methods like ERL, GEP-PG, CERL, CEM-RL to name a few. At least one representative from this family should be included if the comparative claims hinges on sample efficiency.  
Further, adding a general state-of-the-art technique for Mujoco-based continuous control like SAC, ARAC, PEARL would greatly strengthen the paper’s claims. 

Overall, the paper presents an interesting method. My primary reservation lies in the marginal novelty of the idea, computational concerns, and the rather uniform set of baselines used. A satisfying response that addresses these concerns will influence my views on the paper. 

########################### Post Rebuttal ##################
I have read the other reviews and the author's responses. I thank the authors for conducting the additional experiments and integrating the feedback from the reviews. Accordingly, I am raising my score. 
Overall, I agree with the authors that combining QD with pg operators is novel - however, I am still not fully convinced that it is significant enough for a full paper at ICLR. This remains my primary reservation that prevented a higher score for the paper from my end.

review_title: Extremely well-written and compelling paper - reservations exist in terms of novelty, and uniformity of baselines

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary
-------
The paper proposes a way to use off-policy reinforcement learning (RL) in the population mutation step of the quality-diversity (QD) framework. To the best of my knowledge (which is not too extensive in the realm of QD literature) the idea to use two critics, one for quality, one for diversity and use them to mutate the populations of agents these two directions, is novel and looks interesting.


Strengths
---------
* The general flow of the paper is clear and is easy to follow.
* Related work gives a good overview of diversity-seeking approaches.
* The idea to use off-policy RL for mutations in two different directions is interesting and intuitively should indeed result in sample complexity reduction as stated in the title of the paper.


Weaknesses and questions
------------------------
1) As someone relatively new to QD I would benefit from references (somewhere early on, in the introduction) to core research of these methods. Each of the first three sentences in the second paragraph of the introduction begs for references to support the statements that are being made: "The QD literature generally builds on black-box optimization approaches such as evolutionary algorithms to optimize a population of solutions [REF]. These algorithms often rely on random mutations and/or crossover to explore small search spaces but struggle when confronted to higher-dimensional problems [REF]. As a result, QD methods often scale poorly to large sequential decision problems with continuous state and action spaces [REF]".

2) Why diversity is measured in terms of BD and not directly in the parameter space or state space? What makes it preferable? If this is something that generally done in QD literature an explanation why this is the way would do good. If this is a novelty introduced in this paper, it warrants a full and detailed justification.

3) I would like it to be more clearly stated what was the prior work on combining QD with RL, or whether your work is first such attempt. While QD was attempted with other methods, this paper claims "QD-RL is the first algorithm optimizing both diversity and performance in the solution and in the state space, using a sample efficient deep RL method for the latter". The use of RL is alluded to in the second paragraph of section 3, but, taking into account that combination of RL and QD is the core claim of this paper this combination in other works deserves better description and not just a mention. For example was the core idea of using off-policy RL with two critics used in some prior work? Maybe applied to another space or part of the optimization process? If so, this should be mentioned.

4) How is diversity calculated? The "problem statement" section explains that "The measure of diversity relies on the definition of a DB", but is not clearly defined.

5) [ CRITICAL ] The core claim of the paper (that QD-RL is more sample efficient) comes from the results presented on the Figure 2b and it said that the experimental environment is an exact copy of the environment used in Colas et al. (2020) and the results reported in that paper are taken as the point of comparison. I would like to clarify a couple of points stemming from this.

5.1) Why the "Deceptive Humanoid" was not evaluated in this paper? Would the sample complexity reduction be seen in this environment as well if tested? (I can see that "Deceptive Humanoid" was replaced by "Ant Trap" but since Ant Trap was not evaluated in the referenced paper it does not allow for comparison)

5.2) On Figure 6a in Colas et al. (2020) [https://arxiv.org/pdf/2003.01825.pdf] the reported performance of NSRA-ES is -10, while in this work it is shown to be -2. How did this difference occur? Same applied to ME-ES Explore, which is -12 in the original paper and reported as -6 in this work. Similar discrepancy seems to affect other method as well.

5.3) In the original paper sample complexity is shown as the number of generations, while in this work it is shows in numbers of steps. Is there a fixed mapping between the two and is it same for all algorithms?


6) [ CRITICAL ] While there seems to be an abundance of other QD-based methods that were tried on similar environments, these experimental results, most importantly their sample complexities, are not reported in this work and not compared with the proposed method.

7) In the ablation study summarized in Table 1, the candidate algorithm (QD-TD3) is the only one that was tested with MAP-Elites selection mechanism. What would be the performance of the competitor methods ("D-TD3" and "Q-TD3") if MAP-Elites would be used with them as selection mechanism?


Recommendation and justification
--------------------------------
I like the idea presented in this paper and my intuition regarding the benefit or using off-policy RL is aligned with the authors' in that it should lead to higher sample efficiency due to the use of a replay buffer and direct access of the policy gradient. However the experimental results compare the performance with only one other study and with only one task within that study (using "Ant Maze", but skipping "Deceptive Humanoid"). This begs the question how the sample complexity of QD-RL compares to other methods that apply QD to similar tasks and environments. 

Without such a wider comparison that would confirm the main claim of the paper it is hard for me to recommend this paper for acceptance as the experimental evidence for the main claim is not sufficient in my opinion.


Additional remarks
------------------
It was not clear to me the role of the "Ratio to QD-TD3" column in Table 2. Maybe a brief explanation of its significance in the table caption would help.


-------------------- UPDATE Nov 30 --------------------
---------------------------------------------------------------

I find the additional experimental work that was carried out for the revised version of the manuscript to be a step in the right direction which has provided more confidence in the claim of the paper.

The presentation of results is a bit hard to follow... it's a bit hard to put finger on what is exactly the issue. One thing I would suggest is making the names of the methods a bit more telling, deeper into the paper it becomes hard to track which abbreviation stands for which method. It also messy when some methods are reffed to by a particular RL algorithm name "QD-TD3" some by just mentioning RL "CEM-RL" some just as "SAC" and this naming convention breaks when evolutionary methods are mentioned. Maybe for someone who works with these methods a lot it is easy to keep track, but not for a reader not directly involved with the QD field.

Why in Table 2 the third column was changed from "Step to -5" to "Steps to -10"? How this number was picked?

Figure 3, which is the main evidence for the main claim of the paper only appear in Discussion, leaving an impression that this figure is not that important and is a bit of a side-note.

I sympathize with the lack of computational resources, which makes it very hard to compete, but if a 1-to-1 comparison with competitors if at all feasible, it would be worth it. If your methods is as strong as it seems it is, then it will beat the competition across the board in term of sample complexity and send a clean and powerful message that utilizing RL with QD is the way to go.

At this point it might be that the main issue with this work not receiving higher scores lies not in the idea or experimental work, but in presentation. Try taking a couple of you colleagues who are not familiar with their work and observe how they read it, notice the moment when they start loosing focus. Your text jumps from one message to another making the overall narrative not as streamlined as it could. This might be reason for reviews like R3's, where, it seems, the reader gets lost and comes out without clear understanding of the outcomes of your experiments and how these support your claims.

To summarize I still find the idea clever and with the new evidence I am more confident that the claim of the paper might hold in general. Since experimental evidence was my main concern and now there is more of it, I am upping my score from 4 to 6 - "Marginally above acceptance threshold".


review_title: A promising idea that is lacking sufficient experimental evidence

Meta-review: Although originally all reviewers were leaning towards rejection, the authors have done a very good job at addressing their concerns, significantly strenghtening the paper. There is now a consensus towards weak acceptance, with the exception of R3. However, I have decided to ignore R3's review for the following reasons:
- The original review was way too short and uninformative
- R3 did not reply to the authors' request for more constructive feedback
- R3 did not reply to my own request (private email)

That being said, even if other reviewers decided to increase their score after the rebuttal and discussion period, none of them was particularly enthusiastic about it: this remains a borderline paper combining ideas that, although promising, are not particularly original. At this time it falls slightly short off meeting the bar for an ICLR publication. I do believe that combining ideas from the RL and evolutionary research communities is a promising research direction, and I encourage the authors to take into account the reviewers' remaining comments to polish their paper (in particular, adding even stronger empirical results, and ensuring the key take-aways are clearly communicated).
Decision: Reject