Sample efficient Quality Diversity for neural continuous control
Authors: Thomas PIERROT
Valentin Macé
Geoffrey Cideron
Nicolas Perrin
Karim Beguir
Olivier Sigaud
Venue:  (2021)
Keywords: Deep Neuroevolution
Quality Diversity
Reinforcement Learning

Abstract: We propose a novel Deep Neuroevolution algorithm, QD-RL, that combines the strengths of off-policy reinforcement learning (RL) algorithms and Quality Diversity (QD) approaches to solve continuous control problems with neural controllers. The QD part contributes structural biases by decoupling the search for diversity from the search for high return, resulting in efficient management of the exploration-exploitation trade-off. The RL part contributes sample efficiency by relying on off-policy gradient-based updates of the agents. More precisely, we train a population of off-policy deep RL agents to simultaneously maximize diversity within the population and the return of each individual agent. QD-RL selects agents interchangeably from a Pareto front or from a Map-Elites grid, resulting in stable and efficient population updates. Our experiments in the Ant-Maze and Ant-Trap environments show that QD-RL can solve challenging exploration and control problems with deceptive rewards while being two orders of magnitude more sample efficient than the evolutionary counterpart.

Under review as a conference paper at ICLR 2021
SAMPLE EFFICIENT QUALITY DIVERSITY FOR NEURAL CONTINUOUS CONTROL
Anonymous authors Paper under double-blind review
ABSTRACT
We propose novel Deep Neuroevolution algorithm, QD-RI, that combines the strengths of off-policy reinforcement learning (RL) algorithms and Quality Di- versity (QD) approaches
solve continuous control problems with neural con- trollers. The QD part contributes structural biases by decoupling the search for diversity from the search for high return, resulting in efficient management of the ieporation-eplloitation trade-off. The RL part contributes sample efficiency by relying on off-policy gradient-based updates of the agents. More precisely, we train population of off-policy deep RI. agents to simultaneously maximize diver- sity within the population and the return each individual agent. QD-RL selects agents interchangeably from a Pareto front or from Map-Elites grid, resulting in stable and efficient population updates. Our experiments in the ANT-MAZE and ANT-TRAP environments show that QD-RL can solve challenging exploration and control problems with deceptive rewards while being two orders of magnitude more sample efficient than the evolutionary counterpart.
INTRODUCTION
Natural evolution has the fascinating ability to produce organisms that are all high-performing in their respective niche. Inspired by this ability to produce a tremendous diversity of living sys- tems within one run, Quality-Diversit (QD) is new family of optimization algorithms that aim at searching for a collection of both diverse and high-performing solutions (Pugh et al., 2016). While classic optimization methods focus on finding single efficient solution, the role of QD optimization to cover the range of possible solution types and to return the best solution for each type. This process is sometimes referred as "illumination" in opposition to optimization, the goal of these algorithms is to reveal (or illuminate) a search space of interest (Mouret & Clune 2015).
QD approaches generally build on black-box optimization methods such evolutionary algorithms to optimize a population of solutions (Cully & Demiris 2017). These algorithms often rely on ran- dom mutations to explore small search spaces but struggle when confronted to nigher-dimensionn problems. As a result, QD approaches often scale poorly in large and continuous sequential decision problems, where using controllers with many parameters such deep neural networks is mandatory Colas et al. 2020). Besides, while evolutionary methods are the most valuable when the policy gradient cannot be applied safely (Cully al. 2015), in policy search problem that can be formal- ized as a Markov Decision Process (MDP). Policy Gradient (PG) methods can exploit the analytical structure of neural networks to more efficiently optimize their parameters. Therefore, it makes sense to exploit these properties when the Markov assumption holds and the controller is a neural network.
From the deep reinforcement learning (RL) perspective, the focus on sparse or deceptive rewards led to realize that maximizing diversity independently from rewards might be good exploration strategy (Lehman Stanley] 201 aa Colas et al., 2018), [Eysenbach et al., 2018). More recently, was established that if one define small behavior space outcome space corresponding to what matters to determine success, maximizing diversity in this space might be the optimal strategy to find sparse reward (Doncieux et al. 2019).
In this work, we are the first to combine QD methods with PG methods. From one side, our aim is to strongly improve the sample efficiency of QD methods get neural controllers solving continuous action space MDPs. From the other side, it is to strongly improve the exploration capabilities of deep RL methods in the context of sparse rewards deceptive gradients problems, such as avoid traps

---

Under review as a conference paper at ICLR 2021
and dead-ends in navigation tasks. We build on off- PG methods to propose mutation operator that takes into account the Markovian nature of the problem and analytically exploits the known structure of the neural controller. Our QD-RL algorithm falls within the QD framework described by Cully & Demiris (017) and takes advantage of its powerful exploration capabilities, but also demonstrates remarkable sample efficiency brought by off- off-policy RI methods. We compare QD-RL to several recent algorithms that also combine diversity objective and a return maximization method, namely the NS-ES family (Conti al. 2018 and the ME-ES algorithm (Colas et al. 2020 and show that QD-RL RL is two orders of magnitude more sample efficient.
2 PROBLEM STATEMENT
We consider the general context of a fully observable Markov Decision Problem (MDP) (S, A, , R, Y: Po) where S is the state space, A is the action space, T S x A - S is the transition function, R: S.x x A + E is the reward function, y is a discount factor and po is the initial state distribution. We aim to find a set of parameters 0 of parameterized policy те S + A so as to maximize the objective function J(0)- E, E, 7'r where T is trajectory obtained from my starting from state
Po and r; is the reward obtained along this trajectory at time t. We define the Q-value for policy ग, Q* S x A + I as (= a) = E, ""r,,, where T is a trajectory obtained from Ta starting from and performing initial action
QD aims at evolving a set of solutions that are both diverse and high performing. To measure di- versity, we first define a Behavior Descriptor (BD) space, which characterizes solutions in functional terms, in addition to their score [0). We note bdg the BD of a solution 0. The solution BD space is often designed using relevant features of the task. For instance, in robot navigation, relevant BD is the final position of the robot. In robot locomotion, it may rather be the position and/or velocity of the robot center of gravity at specific times. From BDs, we define the diversity (or novelty) of solution as measuring the difference between its BD and those of the solutions obtained so far.
Additionally, we define state Behavior Descriptor, or state BD, noted bdz- It is set of relevant features extracted from a state. From state BDs, we define the BD of a solution @ as a function of all state BDs encountered by policy κe when interacting with the environment, as illustrated in Figure Ia More formally, we note bdg- = EE, and fod is an aggregation function. For instance, fbd can average over state BDs or return only the last state BD of the trajectory. If we consider again robot navigation, a state BD bd, may represent the position of the robot time t and the solution BD bdg may be the final position of the robot. With state BDs, we measure the novelty of a state relatively to all other seen states.
bdt H}, where 7 is the trajectory length
The way we compute diversity at the solution and the state levels is explained in Section
3 RELATED WORK
A distinguishing feature of our approach is that we combine diversity seeking at the level of trajecto- ries using solution BDs bdg and diversity seeking in the state space using state BDs bd, The former is used to select agents from the archive in the QD part of the architecture, whereas the latter is used during policy gradient steps the RL part, see Figure [b We organize the literature review below according to this split between two types of diversity seeking mechanisms.
Besides, some families of methods are related to our work in a lesser extent. This is the case of algorithms combining evolutionary approaches and deep RL such as CEM-RL (Pourchot & Sigaud, 2018), ERL (Khadka & Tumer 2018) and CERL (Khadka et al. 2019). algorithms maintaining a population of RL agents for exploration without an explicit diversity criterion (Jaderberg et al. 2017) or algorithms explicitly looking for diversity but in the action space rather than in the state space like ARAC (Doan al. 2019), P3S-TD3 (Jung al. 2020) and DvD (Parker Holder et al. 2020).
We include FI. as one of our baselines.
Seeking for diversity and performance in the space of solutions Simultaneously maximizing diversity and performance is the central goal of QD methods (Pugh et al., 2016; Cully & Demiris 2017). Among the various possible combinations offered by the QD framework, Novelty Search with Local Competition (NSLC) (Lehman & Stanley 2011b) and MAP-Elites (ME) (Mouret &
2

---

Under review as a conference paper at ICLR 2021
are the two most popular algorithms. In ME, the BD space is discretized into grid of solution bins. Each bin is a niche of the BD space and the selection mechanism samples individuals uniformly from all bins. On the other hand, NSLC builds on the Novelty Search (NS) algorithm [Lehman & Stanley, 1 and maintains an unstructured archive of solutions selected for their local performance. Cully & Mouret (2013) augment the NSL.C archive by replacing solutions when they outperform the already stored ones. In QD-RL, we build on the standard ME approach and on an augmented version of the NSLC algorithm where the population is selected from global quaeity-diversity Pareto front inspired from Cully & Demiris (017). Relying on these components, algorithms such as QD-ES and NSR-ES ES have been applied to challenging continuous control environ- ments in Conti et al. (2018). But, as outlined in [nloas et al. (2020), these approaches are not sample efficient and the diversity and environment reward functions could mixed in more efficient way. In that respect, the most closely related work w.r.t. ours is Colas et al. (2020). The ME-ES algorithm also optimizes both quality and diversity, using an archive, two ES populations and the MAP-ELITES approach. Using such distributional ES methods has been shown to be critically more efficient than population-basee GA algorithms (Salimans et al. 2017). but our results show that they are still less sample efficient than off off-policy deep RL methods they do not leverage the policy gradient.
Clune 2015)
Finally, similarly to us, the authors of Shi et al. (2020) try to combine novelty search and deep RL by defining behavior descriptors and using an NS part on top of deep RL part in their architecture. In contrast with our work, the transfer from novel behaviors to reward efficient behaviors is obtained through goal-conditioned policies, where the RL part uses goals corresponding outcomes found by the most novel agents in the population. But the deep RL part does not contain a diversity seeking mechanism in the state space.
Seeking for diversity and performance in the state space Seeking for diversity in the space of states or actions is generally framed into the RI. framework. An exception is |Stanton & Clune (016)) who define a notion of intra-life novelty that is similar our state novelty described in Section 2 But their novelty relies on skills rather than states. Our work is also related to algorithms using RL mechanisms
al. (2018); Pong et al. 2019 Lee et al. (2019); Islam et al. (0019) These methods have proven useful in the sparse reward case, but they are inherently limited when the reward signal can orient exploration, as they ignore it. Other works sequentially combine diversity seeking and RL. The GEP-PG algorithm (oolass
search for diversity only, such as [Eyenbbach
et al. 2018) combines a diversity seeking component, namely Goal Exploration Processes (Forestier et al. 2017) and the DDPG deep RI. algorithm (Lillicrap et al.) 2015). This sequential combination of exploration pngloratoonthhenexxloitett then-exploitation is also present in Go-EXPLORE (Ecoffet et al.) 2019) and in PBCS Matheron et al. 2020). Again, this approach is limited when the reward signal can help orienting the exploration process towards a satisfactory solution. These sequential approaches first look for diversity in the space of trajectories, then optimize performance in the state action space, whereas we do so simultaneously in the space of trajectories and in the state space.
Thus, as far we know, QD-RL is the first algorithm optimizing both diversity and performance in the solution and in the state space, using a sample efficient off-policy deep RL. method for the latter.
4 METHODS
QD-RL evolves a population of N neural policies (01...., ON) so as to maximise their expected return as well as the diversity within the population. It relies on an archive storing all candidate solutions for selection and on shared replay buffer storing all transitions (St, dt, rt, bde) collected when training all agents. As illustrated in Figure Tb] one iteration consists of three successive phases: population selection among the solutions in the archive, mutation of the population, and evaluation of the newly obtained solutions. These phases are repeated until a maximum computational budget is reached until convergence.
Solution archive and selection mechanism. In this study, we consider two different QD contigura- tions for archive management and selection mechanism. While they rely on different assumptions, we show in Section 3 that QD-RL manages to solve the tasks efficiently in both cases.
In the PARETO setting, maintain an unstructured archive of solutions 0 found far as well as their behavior descriptors bdg. The archive is a limited size FIFO list. Furthermore, we implement insertion rules inspired from Cully & Mouret (003)) prevent adding too close solutions in the BI)
3

---

Under review as a conference paper at ICLR 2021
Solutions Archivee
Evaluaaion
In b6))
Replay Buffer
Population
Hall of the solutiorr
Asply Geadlants
Quality
Population Selection
Critic
Undate Orficc
the sabetinn divaraity
Asply Geadiants
Diversity Critic
Py. by
Update Crtis
12
(a)
(b)
Figure 1: (a): The RL part of QD-RL operates over time steps while QD part operates at the controller level, considering the MDP black box. (b) One QD-RL iteration consists of three phases: 1) A new population of solutions is sampled from the QD Pareto Front or from the Map- Elites grid. 2) These solutions
mutated by an off-policy RL agent: half of the solutions optimized for quality and the other half for diversity. The RI. agent leverages one shared critic for each objective. 3) The newly obtained solutions evaluated the environment. Transitions stored in a replay buffer while final scores and BDs of solutions are stored in the QD archive.
space, unless they offer better performance (see Appendix B for more details). To select solutions from the archive, we compute QD Pareto front of the solutions and sample the new population from this front. We use the (()) objective function as the quality criterion, the diversity criterion is computed as the average Euclidean distance between bdg and its nearest neighbors in the archive.
In the ME setting, the behavior descriptor space is discretized into a Cartesian grid that constitutes the archive. We use the standard insertion criterion: when adding solution 9 into the grid, compute its BDs and find the corresponding bin. If the bin is empty, we insert the solution. Otherwise, we add the solution only if its quality score is greater than the one of the contained solution. To select
population, sample solutions uniformly from the grid.
Population mutation. During one iteration, we mutate each solution in the population to optimize its quality with respect to the objective function, but also optimize the population diversity. To de- couple exploration from exploitation, we introduce two mutation operators optimizing respectively for quality and diversity. Both operators rely dients w.r.t. their respective criterion so as to to guide mutations towards improvement. While any off- off-policy algorithm supporting continuous action could be used, we rely Twin Delayed Deep Deterministic Policy Gradient (TD3) (Fujimoto et al. 2018). To homogenize notations, we note r? for the novelty score and r for the environment reward. The novelty of state at time step t computed as the mean Euclidean distance between its bd, and its nearest neighbors among BDs seen so far. More formally,
off-policy deep RL algorithm to compute gra-
1 = Σ d (bd,,
where d is the Euclidean distance, & the number of nearest neighbors, and Neigh( A, Idd, i) the i-th nearest neighbor of state BD bx,, in an archive of state BDs. This archive is filled with all states BDs collected by the population during training. As for the solutions archive, use the insertion rules inspired from Cully & Mouret (2013). Technically, as this archive used by the RL part of the algorithm, it is implemented as sub-component of the experience replay buffer that receives the same state BDs but filters them with the insertion rules.
We introduce two critic networks Q2 and QP that shared the population and used by TD3 to optimize solutions respectively for quality and diversity. Some reasons for sharing a critic among the population given in Pourchot & Sigaud| (2018). In our context, additional reasons come
4

---

Under review as a conference paper at ICLR 2021
from the fact that diversity is not stationary, as it depends on the current population. If each agent had its own diversity critic, since an agent may not be selected for a large number of generations before being selected again, its critic would evaluate it based on an outdated picture of the evolving diversity. We tried this solution and it failed. Besides, as diversity is relative to the population and not an individual, it is more natural to have it centralized. A side benefit is that both shared critics become accurate faster as they combine the experience of all agents.
At each iteration, QD-RL mutates half the population to maximise quality and the other half to maximise diversity. As Colas et al. (2020), we use a 0.5 ratio to avoid biasing the algorithm towards exploration or exploitation. We leave for further study the automatic adjustment of this ratio, but we found that in practice QD-RL -RL adequately balances both criteria during training.
To mutate a solution 0, we sample batch of transitions from the replay buffer and use stochastic gradient descent (SGD) where the gradient is computed as the TD3 policy gradient, see Equation (I) We respectively use the reward r when optimizing for quality, the reward rf when optimizing for diversity, and their corresponding critics. Note that while the r.? value is the one observed in the environment, the r?. value changes across training time as new states are encountered. To deal with this non-stationary reward, recompute fresh score rt from the observed bic every time a batch is sampled. The gradient computation over solutions is performed in parallel. Every time a policy gradient is computed, we also update the critics Q and Q. The critic gradients are computed in parallel and then averaged across the population. The global population update can be written as
0, 0, V v
Σ ( Te, (s:)), vis 8/2
budch
0. - 8 + a Vo: Σ
To (s))) Vi 8/2
w.
2 V Σ
(0) (1? 70 (stt1, ne, (sc+1))))
hatch 1=1
w w
Σ
Σ (Q ai) - (r. + M/2+1
(s(4)))))
where w' parameters of target critic networks. To keep notations simple, updates of the extra critic networks introduced in TD3, which serve to reduce the value estimation bias, do not appear in (1) although we use them in practice.
Evaluation. Once mutated, solutions are evaluated. To do so, each new solution 0 performs trajec- tories with the resulting controller No in the environment. All encountered transitions stored in the replay buffer and we use the score I(0) and behavior descriptor bdg to place new solutions in the unstructured archive in the MAP-Elites grid.
More details about the QD-RL algorithm and a pseudo-code are available in Appendices B and D
5 EXPERIMENTS
In this section, we demonstrate the capability of QD-RL solve challenging exploration prob- lems. We implement with TD3 and refer to this configuration as the QD-TD3 algorithm. Hyper- parameters are described in Appendix We first analyse each component of QD-TD3 and demon- strate their usefulness on a simple example. Then, we show that QD-TD3 solves a more challenging control and exploration problem such navigating the MuJoCo Ant in large maze with bet- ter sample complexity than its evolutionary competitors. Finally, we demonstrate that QD-TD3 can solve control problems when the behavior descriptor space is not aligned with the task.
5.1 POINT-MAZE AND POINT-MAZE- MOVE A POINT IN A MAZE
We first consider the POINT-MAZE environment in which 2D material point agent must exit from the maze depicted in Figure 2n In this environment, BDs are defined as the agent coordinates (Ie, Y1) at time t and action corresponds to position increments along the and y axis.
In order to exit the maze, the agent must find the right balance between exploitation and exploration. Although this environment may look simple due its low dimensionality, it remains very challeng-
5

---

Under review as a conference paper at ICLR 2021
3
(a) POINT-MAZE
(b) ANT-MAZE
(c) ANT-TRAP
Figure 2: Evaluation environments. Though they may look similar, the state and action spaces in POINT-MAZE are two-dimensional, whereas they are 29 x 8 in ANT-MAZE.
ing for standard deep RL agents such TD3, Figure 4b POINT-MAZE-INERTI in which the point has momentum. In this case, BDs are unchanged but the state contains velocities in addition to positions, and the action force (Fa, Fy). Despite the additional complexity, we observe equivalent performance.
We also consider identical task,
We leverage these environments to perform an ablation study. First, we compare performance of the PARETO and the ME settings. Then, we measure performance when maximizing quality only. We call the resulting agent Q-TD3, but this is simply multi-actor TD3. We also evaluate the agent performance when looking for solutions to maximize diversity only. We call the resulting agent D-TD3. Finally, we consider a D-TD3 PARETO algorithm optimizing only for diversity but performing agent selection from the archive with Pareto front. That is, it selects solutions for the next generation based on both their quality and diversity, but without optimizing the former. Table summarises all the results and more figures are shown in Appendix C.3
Table 1: Ablations and their performance in POINT-MAZE.
Algorithm
Opt. Q
Opt. D
Selection mechanism
Episode return
QD-TD3 + ME
MAP-ELITES
24 (=0)
QD-TD3 + PARETO
PARETO
-27 (+1)
D-TD3 + PARETO
X
PARETO
-37 (1:3
D-TD3
X
None
-111 (=53)
Q-TD3 + PARETO
X
PARETO
-128 (#0)
Q-TD3
X
None
-130 (+2)
5.2 ANT-MAZE: CONTROL AN ARTICULATED ANT TO SOLVE A MAZE
ANT-MAZE is modified from ANT-V2 of OpenAI Gym (Brockman et al. 2016) and is also used in Colas et al. ) Frans et al. (0118) In ANT-MAZE, four-legged ant has to reach goal zone located in the lower right part of the maze (colored in green in Figure 2b). Its initial position is sampled from small circle around the initial point located in the extreme bottom left of the maze. Maze walls are organized so that following the gradient of distance to the goal drives the ant into dead-end. As in POINT-MAZE, the reward expressed minus the Euclidean distance between the center of gravity of the ant and the center of the goal zone, thus leading to a strongly deceptive gradient. Note that in healthy and contact terms which are present in the reward function of ANT-V2 and help define an implicit curriculum that facilitates learning. The environment is considered solved when an agent obtains a score superior to - 10, corresponding to reaching the goal zone. Since the agent must learn to control a body with 8 degrees of freedom in all directions to explore the maze and solve it, is nigher-dimennionall than POINT-MAZE and more complex than the standard ANT-V2 where the ant should only go forward. The state contains the positions, angles, velocities and angular velocities of most ant articulations and center of gravity, and has 29 dimensions. An action specifies 8 continuous torque intensities applied to the 8 ant articulations. Episodes last 3000 time steps and the solution BD is the final position (zr yf) of the center of gravity of the ant, as in POINT-MAZE.
the reward function does not contain the additional control,

---

Under review as a conference paper at ICLR 2021
We compare QD-TD3 to five oftt-o--tthh-tttt evolutionary methods with diversity seeking compo- nent: NSR-ES, ASRA-ES, NS-ES, ME-ES. While NS-ES and D-ME D-ME-ES optimize only for diversity, and Q-ME-ES optimizes only for quality, NSR-ES, NSRA-ES and QD-ME-ES optimize for both. To ensure fair comparison, we do not implement our own versions of these algorithms but reuse results from the MR-FS paper (Colas et al., (020) and we make sure that our environment is rigorously the same. We also use as baselines SAC and TD3, two state-of-the-ar RL methods for continuous control, and CEM-RL, an algorithm combining evolutionary methods and RL but without diversity seeking mechanisms. We chose CEM-RL as it shows state-of-the- art performance on standard MuJoCo benchmarks (Pourchot Sigaud 2018).
Table 2: Summary of compared algorithms ANT-MAZE. The Final Perf. is the minimum distance to the goal at the end of an episode over the population.
Algorithm
Final Perf. (+ std)
Steps -10
Ratio to QD-TD3
QD-TD3 PARETO
4 (+:3
1.15e8
QD-TD3 ME
-7(7
1.15e8
QD-TD3-SUM
2.5c8
2
D-TD3
-2 (=0)
3.5e8
3
Q-TD3
-26 (EE))
oc
00
SAC
-59 (+1)
0c
00
CEM-RL
26 (+0)
0c
00
NS-ES
-4(00)
2.4e10
209
NSR-FS
-2 (+0)
0C
00
NSRA-ES
-2 (=1)
2.1e10
182
QD-ME-ES
-5 (+1)
2.4c10
209
D-ME-ES ES
55 (+0)
1.9e10
165
Q-ME-ES
26 (+))
0
00
5.3 ANT-TRAP: CONTROL AN ARTICULATED ANT TO AVOID A TRAP
ANT-TRAP also derives from V and is inspired from Colas et al. (2020). In ANT-TRAP, the four-legged ant initially appears in front of trap and must avoid it in order to run as fast as possible in the forward direction along the r-axis. The trap consists of three walls that form a dead-end directly front of the ant, leading to a strongly deceptive gradient. As in previous environments, the behavior space is defined as the final position (/) of the center of gravity of the ant. The peculiarity of this environment compared to the others is that here, the reward is expressed as the ant's forward velocity and is thus not fully aligned with the BDs. In contrast to ANT-MAZE here the reward function is the same as the one used in V it contain the additional features that facilitate training. We can thus test the coverage capacity of our method in the case of partial alignment. The action and state spaces are the same as in ANT-MAZE and the episodes last 1000 time steps. In this benchmark, we compare QD-TD3 to SAC, TD3, CEM-RL and QD-TD3-SUM. We could not compare it to the ME-ES family as these algorithms require 1000 CPUs.
6 DISCUSSION
Ablation study. The ablation study in Table I shows that: 1) When maximising quality only, Q- TD3 with or without a selection mechanism fails due to the deceptive nature of the reward. Figure 4 When maximising diversity only, D-TD3 fails without selection mechanism but adding PARETO or ME selection is enough to exit the maze. 3) When optimizing quality and diversity, the agent finds a more optimal trajectory to the maze exit, resulting in higher returns. 4) While ME has slightly less variance, both QD methods solve the problem with high returns. This study validates the usefulness of the QD-RA RL. components: 1) optimizing for diversity is required to overcome the deceptive nature of the reward; 2) a proper population selection mechanism is required to ensure proper convergence, and adding quality optimization provides better asymptotic performance.
also shows the poor BD space coverage resulting from the lack of diversity component.
Comparison to neuroevolution with a diversity seeking component competitors in Ant-Maze. Table 2 compares QD in terms of sample efficiency to Deep Neuroevolution algorithms with
7

---

Under review as a conference paper at ICLR 2021
-1000
1900
-1200
1400
13300
1200
1500
1600
1000
-1700
CD-TD3 MAP-Eites
G-TD3 Pareto
CEM-R
QD TD3 Pereto
QTD3
SAC
-1800
Pareto
G-TD3
900
QD TD3 SUM
3.0
0.2
0
0.6
0.8
1.0
0.0
0-4
6.b
1.0
Number steps
108
(a) POINT-MAZE-INERTIA
(b) ANT-TRAP
-10
-20
-20
1.3
300
-40
-50
-50
QC-TD3 Parato
D-ME-ES NSRA-ES
NS-ES
QD-TD3 Poreto
Q-TD3
QD-ME ES
CEM-RL
QD-TC3-SUM
SAC
2.0
9.4
0.
1.0
Number of steps
10.0
Number of steps
160
(c) ANT-MAZE: Comparison Evo methods
(d) ANT-MAZES Comparison to PG methods
Figure 3: Learning curves of QD-TD3 versus ablations and baselines. In POINT-MAZE and ANT- TRAP, the performance the highest return. In ANT-MAZE, minus the highest distance the goal. In 3a and 3b all results are averaged over 5 seeds. In 3C and 3d curves show the best 2 seeds of for all algorithms.
diversity seeking component ANT-MAZE, QD-RL is run on 10 CPU cores during 2 days while its competitors used several hundreds of CPU cores for the same duration. Nonetheless, QD-RI RL matches the asymptotic performance of ME-ES using two orders of magnitude less samples, thus explaining the lower resource requirements. We see three reasons for the improved sample efficiency of QD-RI:: 1) QD-RI. leverages a replay buffer and can re-use each sample several times. 2) QD-RI. leverages notion of novelty defined at the state level and thus can exploit all collected transitions to maximize both quality and diversity. For example, in ANT-MAZE, a trajectory brings 3000 samples to QD-RL while standard QD methods would consider it unique sample. 3) RL exploits the analytical gradient between the neural network weights and the resulting policy action distribution and thus estimates only the impact of the distribution the return, whereas standard QD methods estimate directly the impact of the weights onto the return.
Performance assessment when BDs not fully aligned with the task in Ant- Ant-Trap. Finally, evaluated QD-RL in the ANT-TRAP environment. The difference from previous environments is that reward is computed the forward velocity at time and not as an Euclidean distance a target. As the BD remains the ant center of gravity, it is not directly aligned with the task. Nonetheless, we observe Figure 4c that optimizing only for quality results in sub-optimal performance while QD-RL finds the optimal strategy by avoiding the trap and running beyond.
Mixing quality and diversity updates. To validate our design choices, we also introduce a variant of QD-TD3 called QD-TD3-SUM, where unique critic Q.. is updated considering at every time step the sum of the quality reward and the diversity reward: r + rP. We tested QD-TD3-SUM on ANT-MAZE and ANT-TRAP. QD-TD3-8
completely fails to learn anything in ANT-TRAP. manages to solve the task in ANT-MAZE but requires
samples than QD-TD3. In fact, the quality and diversity rewards may give rise to gradients pointing to opposite directions. For instance, at the beginning of training in ANT-TRAP, the quality reward drives the ant forward whereas the diversity
8

---

Under review as a conference paper at ICLR 2021
reward drives it backward rewards may often anneal each other, preventing any learning. This situation, while rarer, also happens in the ANT-MAZE environment and reduces sample efficiency.
escape the trap and explore the environment. Therefore, both
Comparison to sample efficient methods without a diversity seeking component. We compared QD-TD3 to TD3 and SAC and CEM-RL in both ANT-MAZE and ANT-TRAP benchmarks. As expected, TD3 converges quickly to the local minimum of performance resulting from being attracted in the dead-end by the deceptive gradient in both environments. While may expect SAC to demon- strate better exploration properties as it regularizes entropy, it also converges to that same local minimum in TRA- Surprisingly, SAC with the standard hyper-paramette benchmarks does not learn in ANT-MAZE. It may come from the lack of the additional features in the reward function. CEM-RI. combines RI. for sample efficiency and cross-entropy methods for better exploration in the parameter space. Indeed, CEM-RI. was shown to outperform RI. algorithms in standard MuJoCo environments. Despite this additional exploration mechanism, CEM-RL. also quickly converges to the dead-end in both benchmarks, thus confirming the need for dedicated diversity seeking component.
used for MuJoCo
(a) Color map: oldest actors are blue while the newest are purple
(b) POINT-MAZE
(c) ANT-TRAP
Figure 4: Coverage maps of Q-TD3 (left) and QD-TD3 (right) in POINT-MAZE and ANT-TRAP.
CONCLUSION
In this paper, we proposed a novel way deal with the ing a quality-seeking component, diiverstt-sseeking component and selection component inspired from the Quality-Divent timized with off-policy reinforcement learning algorithms, resulting in significantly better sample efficiency. We showed experimentally the effectiveness of the resulting QD-RL framework, which solve, in two days using 10 CPUS, problems that were previously out of reach without much larger infrastructure. Key components of QD-RL RL are selection through a Pareto front or a Map- Elites grid and the search for diversity in a behavior descriptor space. Admittedly, this behavior descriptor space is hand designed. There are attempts to automatically obtain it through unsupervised learn- ing methods (Péré al. 2018 Paolo al., 2019). but defining this space is often trivial design choice that can alleviate the need to carefully shape reward functions. In the future, we intend to extend this approach to problems where the reward function can be decomposed into several loosely dependent components, such as standing, moving forward and manipulating objects for a humanoid agent, to aulti-agent reinforcement learning problems. In such environments, we could replace the maximization of the sum of reward contributions with multi-criteria selection from Pareto front, where diversity would be only one of the considered criteria. Additionally, we would like to make profit of the diversity of the solutions we obtain to build repertoires of behaviors, as it is one of the main features of the Quality-Divert Diieersty methods.
trade-off by combin-
literature. Crucially, we showed that quality and diversity could be op-
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: met.i16666011440, 2016.
Cédric Colas, Olivier Sigaud, and Pierre-Yve Yves Oudeyer. GEP-PG:
Decoupling exploration and exploitation in deep reinforcement learning algorithms. arXiv preprint arXiv:1802. 180..00052,0 2018.
Cédric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune. Scaling map-elites to deep neu- roevolution. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 67-75, 2020.
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via a pop- ulation of novelty-secking agents. In Advances in neural information processing systems, pp. 5027-5038, 2018.
Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular frame- work. IEEE Transactions on Evolutionary Computation, 22(2):245-255 2017.
Antoine Cully and Jean-Baptise Mouret. Behavioral repertoire learning in robotics. In Proceedings of the 15th annual conference on Genetic and evolutionary computation, pp. 175-182, 2013.
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that can adapt like animals. Nature, 5210555):50335077, 2015.
Thang Doan, Bogdan Mazoure, Audrey Durand, Joelle Pineau, and R Devon Hjelm. Attraction-repulsion actor-critic for continuous control reinforcement learning. arXiv preprint 1rXiv:1909.07543 2019.
Stephane Doncieux, Alban Laftaquière, and Alexandre Coninx. Novelty search: a theoretical per- spective. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 99-106, 2019.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth Stanley, and Jeff Clune. Go-explore: a new approach for hard-exploration problems. arXiv preprint arXiv:1901.100 10995, 2019.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv:1802.06074 2018.
Sébastien Forestier, Yoan Mollard, and Pierre-Yves Oudeyer. Intrinsically motivated goal explo- ration processes with automatic curriculum learning. arXiv preprint arXiv:1708.02199. 2017.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. Proc. of ICLR, 2018.
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. arXiv preprint arXiv: www.i.002..000 090070 2018.
Riashat Islam, Zafarali Ahmed, and Doina Precup. Marginalized state distribution entropy regular- ization in policy optimization. arXiv preprint arXiv: 2019.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech M Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population- based train- ing of neural networks. arXiv preprini
2017.
Whiyoung Jung, Giseung Park, and Youngchul Sung. Population-guidee parallel policy search for reinforcement learning. In International Conference on Learning Representations, 2020.
Shauharda Khadka and Kagan Tumer. Evolution-gune -uided policy gradient in reinforcement learning. In Neural Information Processing Systems, 2018.
Shauharda Khadka, Somdeb Majumdar, Santiago Miret, Evren Tumer, Tarek Nassar, Zach Dwiel, Yinyin Liu, and Kagan Tumer. Collaborative evolutionary reinforcement learning. arXiv preprint arXiv: 1995000976 2019.
10

---

Under review as a conference paper at ICLR 2021
Lisa Lee, Benjamin Eysenbach, Emilio Parisotto, Eric Xing, Sergey Levine, and Ruslan Salakhutdi- nov. Efficient exploration via state marginal matching. arXiv preprint arXiv: 09294.4444, 2019.
Joel Lehman and Kenneth O Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation, 19(2):19-2223, 201 la.
Joel Lehman and Kenneth Stanley. Evolving diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pp- 21 211. 2011b.
Timothy Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint
2015.
Guillaume Matheron, Nicolas Perrin, and Olivier Sigaud. PBCS:
Efficient exploration and ex- ploitation using synergy between reinforcement learning and motion planning. arXiv preprint arXiv:2004.11667, 2020.
Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint 1xXi.:/504.04900 2015.
Giuseppe Paolo,
Alban Laftaquiere, Alexandre Coninx, and Stephane Doncieux. Unsupervised learning and exploration of reachable outcome space. algorithms, 24:25, 2019.
Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective di- versity in population-based reinforcement learning. In Neural Information Processing Systems, 2020.
Alexandre Péré, Sébastien Forestier, Olivier Sigaud, and Fierre-Yves Oudeyer. Unsupervised learn- ing of goal spaces for intrinsically motivated goal exploration. arXiv preprint 2018.
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew- fit: State-covering self-supervised reinforcement learning. arXiv preprint TrXiv:1903.03693 2019.
Alois Pourchot and Olivier Sigaud. Cem-rl: Combining evolutionary and gradient-based methods for policy search. arXiv preprint arXiv: 1810.0/222, 2018.
Justin K Pugh, Lisa B Soros, and Kenneth O. Stanley. Quality diversity: A new frontier for evolu- tionary computation. Frontiers in Robotics and AI, 3:40, 2016.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv:/703.03330 2017.
Longxiang Shi, Shijian Li, Qian Zheng, Min Yao, and Gang Pan. Efficient novelty search through deep reinforcement learning. IEEE Access, 1128809-188811 2020.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Proceedings of the 30th International Conference in Machine Learning, 2014.
Christopher Stanton and Jeff Clune. Curiosity search: producing generalists by encouraging individ- uals to continually explore and acquire skills throughout their lifetime. PloS one, 110)):00162235, 2016.
11

---

Under review as a conference paper at ICLR 2021
APPENDICES
A
THE TD3 AGENT
The Twin Delayed Deep Deterministic (TD3) agent Fujimoto et al. (2018) builds upon the Deep Deterministic Policy Gradient (DDPG) agent Lillicrap et al. (2015). trains deterministic actor To S + AA directly mapping observations to continuous actions and critic Qo S x A + I taking a state and an action a and estimating the average return from selecting action a in state and then following policy T.. As DDPG, TD3 alternates policy evaluation and policy improvement operations so as to maximise the average discounted return. In DDPG, the critic is updated to mini- mize temporal difference error during the policy evaluation step which induces an overestimation bias. TD3 corrects for this bias by introducing two critics Qa, and Qoz- TD3 plays one step in the environment using its deterministic policy and then stores the observed transition (s,, ag Pt, $(+1) into a replay buffer B. Then, samples a batch of transitions from and updates the critic networks. Half the time it also samples another batch of transitions update the actor network.
Both critics are updated so as to minimize a loss function which is expressed as a mean squared error between their predictions and a target:
L critic (01,02) = Σ (00, - u1)² + (Qu, (8c, (s)),a)) - y/.)
(2)
batch
where the common target yı is computed as:
= rz + min Qo (8e+1. (o(+411) + e), N(,
(3)
1m1
The Q-value estimation used to compute target Yt is taken as minimum between both critic pre- dictions thus reducing the overestimation bias. TD3 also adds small perturbation the action (8(+))1) so as to smooth the value estimate by bootstrapping similar state-action value estimates.
Every crities updates, the actor T is updated using the deterministic policy gradient also used in DDPG Silver et al. (2014). For a state s, DDPG updates the actor so as to maximise the critic estimation for this state and the action TD3, the authors suggest to take the first critic as an arbitrary choice. Thus, the actor is updated by
(s) selected by the actor. As there are two crities in
minimizing the following loss function:
I, Tactor (x) =-
Σ Qo, (St, (x))))
batch
Policy evaluation and policy improvement steps are repeated until convergence. TD3 demonstrates state of the art performance several MuJoCo benchmarks. In this study, we use it to update the population actors for both quality and diversity.
B QD-RL ADDITIONAL PRACTICAL DETAILS
B.1 COMPUTATIONAL DETAILS
We consider populations of N = 4 actors for both POINT-MAZE and POINT-MAZE-INERTI envi- ronments and N' 10 actors for ANT-MAZE and ANT-TRAP. We use CPU thread per actor and parallelization is implemented with the Message Passing Interface (MPI) library. Our experiments were run on a standard computer with CPU cores and 100 GB of RAM although the maximum RAM consumption per experiment at any time never exceeds 10GB due to efficient and cen- tralized management of the archive that stores all solutions. An experiment on POINT-MAZE or POINT-MAZE- INERTIA typically takes between 2 and 3 hours while experiment ANT-MAZE or ANT-TRAP takes about 2 days. Note that these durations can vary significantly depending on the type of CPU used. We did not any GPUs.
12

---

Under review as a conference paper at ICLR 2021
B.2 QD IMPLEMENTATION DETAILS
We consider two settings for the Quality Diversity part of our algorithm.
In the PARETO setting, we rely on FIFO archive of solutions. We chose maximum archive size of 10.000 for all environments. When a new solution 0 is obtained after the mutation phase, we compute the mean distance between its BD bdg and the BDs its K nearest neighbors in the archive. We used K = 10 for all environments. We also used an Euclidean distance for all environments. We add the new solution in the archive if the computed distance is superior to a threshold of acceptance. See Table 3 for the different values of this threshold depending on the environment. During the selection phase, we compute a QD Pareto front of all solutions contained in the archive and sample the new population from the front. If the Pareto front contains less than N actors, we select them all, remove them, compute the Pareto front over the remaining actors and sample again from it, and so until we get N actors.
In the ME setting, we use a Map Elites (ME) grid as archive of solutions. We assume that the BD space is bounded and can be discretized in an Cartesian grid. We discretize each dimension into m meshes, see Table 3 for the value of m depending on the environment. Thus the number of bins in the ME grid equals m times the number of dimensions of the BDs. When new solution @ is obtained after the mutation phase, we seek for the bin that corresponds its BD bdg. If the bin is empty, we add the solution in it, otherwise we replace the solution already contained by the new one if its score I (0) is greater than the one of the already contained solution. During selection, we sample solutions uniformly from the ME grid. The ME archive management and selection mechanism tends to store less solutions than the PARETO method and does not need to compute a Pareto Front which makes QD-RL ME less computation and memory costly than QD-RL PARETO.
B.3 DIVERSITY REWARD COMPUTATION
The RL part of QD-RL RL optimizes solutions for quality but also for diversity at the state level. As the QD part stores solutions and performs population selection based on solution BDs bdg, the RL part optimizes the solutions as encourage them to visit states with novel state BDs. The novelty of a state BD bd, is expressed through a diversity reward r!. In practice, we maintain in parallel of the replay buffer a FIFO storage of the states BDs encountered of this storage is never reached. However its maximum theoretical size is chosen to be the same as the solutions archive. When a transition (st, ae bd,, Tt, St+1) sampled and stored in the Replay Buffer, we also add bd, in this storage. For the archive of solutions presented in the PARETO setting, we add state BD this storage only if its mean Fuclidean distance to its K nearest neighbors in the storage is greater than an acceptance threshold. The values of K and of the threshold are given in Table 3 This mechanism ensures that we do not keep too close state BDs and thus controls this storage size. When a batch of transitions (St, ae, bdz, Tı, St++1) 1) is collected during the mutation phase, we recompute fresh diversity rewards r?" as the mean Euclidean distance between the sampled states BDs bd, and their K nearest neighbors in the states BDs storage. The value of K is the same the one used for the insertion rule.
far. In practice, the maximum size
B.4 COMPUTATIONAL COST AND PARALLEL IMPLEMENTATION
The main costs of the algorithm come from backpropagation during the update of each agent, and to the interaction between agents and the environment. These costs scale linearly with the population size but, as many other population-ban based methods, the structure of QD-RL lends itself very well to parallelization. We leverage this property and parallelize our implementation so as to assign one agent per CPU core. Memory consumption also scales linearly with the number of agents. To reduce this consumption, we centralize the solution archive master worker and distribute data among workers when needed. With these implementation choices, QD-RL only needs a very accessible computational budget for all experiments.
13

---

Under review as a conference paper at ICLR 2021
B.5 PAREE-PARAMETERS
Table 3 summarizes all hyper-parameters used in experiments (see Figure parameters values are the original ones from the TD3 algorithm.
Most of these hyper-
Table 3: QD-TD3 Hyper-parameters
Parameter
Point Maze
Ant Maze
Ant Trap
TD3
Optimizer
Adam
Adam
Adam
Learning
6.10-3
3.10-1
3.10-1
Discount factor
0.99
0.99
0.99
Replay buffer size
106
5.105
5.10
Hidden layers size
64/32
256/256
256/256
Activations
ReLU
ReLU
ReLU
Minibatch size
256
256
256
Target smoothing coefficient
0.005
0.005
0.005
Delay policy update
2
Target update interval
1
Gradient steps ratio
4
0.1
0.1
Quality-Diversse
Archive size
10000
10000
10000
Threshold of acceptance
0.0001
0.1
0.1
K-nearest neighbors
10
10
10
MAP-Elites
Number of bins per dimension
7
C ENVIRONMENTS ANALYSIS
In this section, we propose a more thorough analysis of the proposed environments. We highlight why these environments are hard to solve for classical deep RL agents without diversity mechanism and show the impact of the different components of our algorithm.
C.I ENVIRONMENTS DETAILS
In POINT-MAZE, the observation and state BD are the agent coordinates (Iz, yt) at time t. The actions features (őar, 5y) position increments along the and y axes. The solution BD is the final position (Iy, Uf) of the agent, as Conti et al. (2018). The initial position of the agent is sampled from small zone at the bottom of the maze. The exit area is a square located the top left of the maze, the episode ends once this exit square is reached or after 200 time steps. The reward computed as minus the Euclidean distance between the agent position and the maze exit. This reward leads to a deceptive gradient signal: following it would lead the agent to stay stuck by the second wall in the maze, as shown in Figure of Appendix C In POINT-MAZE- AAEEI--AA---I-III,A... the BD space remains the same however the point velocity (Uy, vy)) is appended to the state to preserve the Markov property and action corresponds forces (Fz, F2))
In POINT-MAZE and DOINT-MAZ--INERTEI the dimensions of the observation spaces are equal to 2 and 4 respectively, and the dimensions of the action spaces are both equal to 2. Both environments very similar with low-dimensional state and action spaces, and only differ by the fact that POINT- MAZE-INERTIA moves a ball subject to inertia. By contrast, in ANT-MAZE and ANT-TRAP, the dimensions of the observation spaces respectively 29 and 1 113 while the action spaces dimensions are both equal to 8, making these two environments much more challenging as they require larger controllers.
14

---

Under review as a conference paper at ICLR 2021
The ANT-TRAP environment also differs from mazes as it is open-ended, i.e., the space be explored by the agent is unlimited, in contrast to other environments where this space restricted by the maze walls. In this case, the state BD corresponds to the ant position that is clipped to remain in given range. On the y-axis, this range is defined so as to leave a space corresponding to the width of the trap both trap sides. On the r-axis, this range begins slightly behind the starting position of the ant and is large enough to let accelerate along this axis. Figure S proposes a visual representation of the BD space in ANT-TRAP.
C.2 DECEPTIVE GRADIENTS
FigureSJhighe Shighlights the deceptive nature of the POINT-MAZE and the ANT-MAZE objective functions by depicting gradient fields both environments. Similarly, POINT-MAZE-INERTO and ANT-TRAP also present strongly deceptive gradients.
(a) Gradient field in POINT-MAZE
(b) Gradient field in ANT-MAZE
Figure 5: Gradients maps on POINT-MAZE and ANT-MAZE. The black lines represent the maze walls, the arrows depict gradient fields and the square indicates the maze exit. Both settings present highly deceptive gradients: naively following them leads into a wall.
C.3 EXPLORATION IN POINT-MAZE FOR ALL ABLATIONS
Figure 6/ summarizes the coverage maps of the POINT-MAZE environment by the different algorithms presented in the ablation study (see Table D. A dot in the figure corresponds to the final position of an agent after an episode. The color spectrum highlights the course of training: agents evaluated early in training are blue while newer ones represented in purple. Figure corresponds the map coverage for one seed, we chose a representative seed.
QD-TD3 (PARETO andME) and D-TD3+PARETT almost cover the whole BD space including the objective. D-TD3 also finds the objective but is not constant through all seeds and does not uniformly cover the BD space. Unsurprisingly, PARDTO and Q-TD3 present very poor coverage maps, both algorithms optimize only for quality and the Pareto selection mechanism does not contribute anything in this setting. Interestingly. all algorithms optimizing for diversity find the maze exit. However, as shown in Table [ algorithms that also optimize for quality (QD-TD3) or that present structural pressure toward quality (D-TD3+PARETO) are able to refine their trajectory through the maze and obtain significantly better performance.
Figure 7 summarizes the coverage maps of the ANT-TRAP environment by QD-TD3+ME, QD- TD3+PARETO and TD3. Interestingly, the pattern of QD-TD3+ME differs from that of QD- TD3+PARETO. We hypothesize that this behavior reflects the grid structure of the ME archive.
15

---

Under review as a conference paper at ICLR 2021
Color map: the oldest blue while the in purple
QU-TDE MAP-Blles
(b) QD-TD3 Pareto
(c) D-TD3 Pareto
(6) D-TDS
Q-TD3
Partto
Q-TD
Figure 6: Coverage map of the POINT-MAZE environment for all ablations. Each dot corresponds to the position of agent the end of episode. Dots corresponding to the oldest actors are in blue while the newest are in purple.
Color map: the oldest actors in blue while the newest are in purple
(b) QD-TD3
Figure 7: Coverage map of the ANT-TRAP environment. Each dot corresponds to the position of an agent the end of episode. Dots corresponding to the oldest agents in blue while the newest are in purple.
16

---

Under review as a conference paper at ICLR 2021
D QD-RL PSEUDO CODE
Algorithm 1: QD-RL
Given: N. steps gradient ratio.
Initialize: Archive A, Replay Buffer B, N actors f he crities QoD and Que, BD Storage
total total_steps, actor actor_stepsseteeee = 0,0 Step counters
// Parallel evaluation of the initial population
for 6- to do
Play one episode with actor me, and store all transitions in B episode length T. discounted return and state BDs (bd1,..., bdr} S
Store BDs [bd1...., b,r....,,rrrr
Compute bdg = fba((hd1... [bd1,.... bdr}) and add the tuple (R, bdo, 02) in the archive A actor steps +- actor steps +
end
// Aigorithm main doop while total_steps mar_steps do
// Select new generation
Get N actors Te, E fl,..., NY....,N N from the Pareto front or from the MAP-Elites grid gradient steps = int(actor _stes x gradient.steps stepssraaioo actor steps 0
// Perferm in parallel population update and evaluation for j - No do
// Update the population for i + 1 to gtadientt_teeps de Sample batch of (8t, az, 81-1, bd:) from
// First half is updated to maximise diversity j SN//2 then
Compute novelty reward as re from bel and S Update na, for diversity
Compute novelty critic gradient locally
Average between threads novelty critic gradients
Update novelty critic Q
end
// Second half is updated to maximise quality
Update Te, for quality
Compute quality critic gradient locally
Average between threads quality critic gradients
Update quality critic Q
end
end
// Evaluate the updated actors
Play episode with actor ne, and store all transitions in B Get episode length T. discounted return R and state BDs {bd1,.... bdr}
Store BDs (bdı,..., bdr } in S
Compute bdg Soa((((aa [bd],.... .., bdr3) and add the tuple (R, bdg. 03) in the archive A actor actor-steps 4- actor steps +
end
total -ttel_steps +- total steps actor actor-steps/ // Update total time steps
end
17


Reviews:
[{"review_id": "MY_-c81ZKx", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper 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)).   \n\nReasons for score:\n\nThe 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.\n\nThe 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:\n(1) comparison of several baselines in several different hard-exploration environments (such as Point Maze and Ant-Trap used in ablation experiments), \n(2) comparisons to PBT and RL with exploration bonuses.\nI 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.  \n\nSome important algorithmic choices in the population mutation part of the algorithm, do not seem well justified or sufficiently empirically explored:\n(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? \n(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?  \nSeparately: \n(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?  \n\nQuestions:\n- 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? \n\nOther comments:\n- \"Besides, evolutionary methods are very valuable when nothing is known about the function to optimize.\" --> can you be more precise?\n- in Table 1 and 2, can you report the results and stds to two decimal points? Please also report the standard deviation for steps\n\n-----------------------------------\n\nUPDATE: 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.\n\nGiven 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "E7yOwHdW4MN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors 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. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "9Tum8qCuiIr", "reviewer": "AnonReviewer1", "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: 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.\n\nTechnical 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. \n\nNovelty: 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. \n\nSignificance: 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:\n\nBoth 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?\n\nOn 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? \nWhile 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.\n\nThe 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. \nFor 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.  \nFurther, adding a general state-of-the-art technique for Mujoco-based continuous control like SAC, ARAC, PEARL would greatly strengthen the paper’s claims. \n\nOverall, 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. \n\n########################### Post Rebuttal ##################\nI 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. \nOverall, 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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "-abvqL5GkyD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------\nThe 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.\n\n\nStrengths\n---------\n* The general flow of the paper is clear and is easy to follow.\n* Related work gives a good overview of diversity-seeking approaches.\n* 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.\n\n\nWeaknesses and questions\n------------------------\n1) 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]\".\n\n2) 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.\n\n3) 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.\n\n4) 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.\n\n5) [ 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.\n\n5.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)\n\n5.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.\n\n5.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?\n\n\n6) [ 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.\n\n7) 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?\n\n\nRecommendation and justification\n--------------------------------\nI 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. \n\nWithout 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.\n\n\nAdditional remarks\n------------------\nIt 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.\n\n\n-------------------- UPDATE Nov 30 --------------------\n---------------------------------------------------------------\n\nI 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.\n\nThe 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.\n\nWhy in Table 2 the third column was changed from \"Step to -5\" to \"Steps to -10\"? How this number was picked?\n\nFigure 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.\n\nI 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.\n\nAt 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.\n\nTo 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\".\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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