Evolutionary Diversity Optimization with Clustering-based Selection for Reinforcement Learning
Authors: Yutong Wang
Ke Xue
Chao Qian
Venue: ICLR 2022 Poster (2022)
Keywords: Reinforcement learning
Quality-Diversity
Evolutionary algorithms

Abstract: Reinforcement Learning (RL) has achieved significant successes, which aims to obtain a single policy maximizing the expected cumulative rewards for a given task. However, in many real-world scenarios, e.g., navigating in complex environments and controlling robots, one may need to find a set of policies having both high rewards and diverse behaviors, which can bring better exploration and robust few-shot adaptation. Recently, some methods have been developed by using evolutionary techniques, including iterative reproduction and selection of policies. However, due to the inefficient selection mechanisms, these methods cannot fully guarantee both high quality and diversity. In this paper, we propose EDO-CS, a new Evolutionary Diversity Optimization algorithm with Clustering-based Selection. In each iteration, the policies are divided into several clusters based on their behaviors, and a high-quality policy is selected from each cluster for reproduction. EDO-CS also adaptively balances the importance between quality and diversity in the reproduction process. Experiments on various (i.e., deceptive and multi-modal) continuous control tasks, show the superior performance of EDO-CS over previous methods, i.e., EDO-CS can achieve a set of policies with both high quality and diversity efficiently while previous methods cannot.

Published as conference paper ICLR 2022
EVOLUTIONARY DIVERSITY OPTIMIZATION WITH CLUSTERING-BASED SELECTION FOR REINFORCEMENT LEARNING
Yutong Wang", Ke Xue and Chao Qian
State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China {wangyt, xuek, qianc}
elmdda Lamda.
ju. edu. en
ABSTRACT
Reinforcement Learning (RL) has achieved significant successes, which aims to obtain single policy maximizing the expected cumulative rewards for given task. However, in many real-world scenarios, e.g., navigating in complex environments and controlling robots, one may need find set of policies having both high rewards and diverse behav- iors, which can bring better exploration and robust few-shot adaptation. Recently, some methods have been developed by using evolutionary techniques, including iterative repro- duction and selection of policies. However, due to the inefficient selection mechanisms, these methods cannot fully guarantee both high quality and diversity. In this paper, we propose EDO-CS, new Evolutionary Diversity Optimization algorithm with Clustering- based Selection. In each iteration, the policies are divided into several clusters based on their behaviors, and high-quality policy is selected from each cluster for reproduction. EDO-CS also adaptively balances the importance between quality and diversity the reproduction process. Experiments ous control tasks, show the superior performance of EDO-CS over previous methods, i.e., EDO-CS achieve set of policies with both high quality and diversity efficiently while previous methods cannot.
various (i.e., deceptive and
continu-
INTRODUCTION
Reinforcement Learning (RL) is an effective method for training agents to make decisions in given envi- ronment, which is often obtain policy maximizing the expected cumulative rewards (Li 2017 Sutton & Barto 2018). As RL is applied to more real-world scenarios, training a single policy is insufficient to handle complex problems, and we may need to find set of policies with both high quality (i.e., rewards) and diverse behaviors. For example, when navigating in complex environments (Zhu et al., (irowskl jet al. 2017), there are usually deceptive rewards trapping single policy into the local optima. Maintaining a set of policies allows data to be collected with diverse behaviors and may lead to better exploration in these environments. When controlling robots, is fragile to have one single policy (Cully et al. [0055). In contrast, maintaining set of policies can improve robustness, e.g., enable real robots to recover quickly from joint damage (Cully et al. 2015), and also helpful for few-shot adaption when facing unseen tasks (Kumar et al.) 2020). General deep RL algorithms mostly focus achieving high rewards, restricting their ability to generate diverse behaviors.
"Equal contribution
I Corresppnning author

---

Published as a conference paper at ICLR 2022
Evolutionary Algorithms (EAs) are general-purpose heuristic optimization algorithms that maintain a pop- ulation (i.e., a set of solutions), and simulate the natural evolution process with iterative reproduction and selection (Bäck, 1996). Quality-Diversiit (QD) algorithms (Pugh et al.) 2016; Cully & Demiris, (018) are a specific type of EAs that aim to return a set of high-quality solutions with diverse behaviors in single run. They have been naturally applied to RL in complex environments, generating the corresponding RL algo- rithms NSR-ES (Conti et al. (0188), ME-ES (Colas et al.] 2020), DvD-ES (Parker-Holder et al. 2020) and
QD-RL (Cideron et al. 2020). Note that classical QD algorithms like NSLC (Lehman & Stanley 201 or MAP-Elites (Mouret & Clune 2015 Cully et al., 2015) often employ Genetic Algorithm (GA) the
derlying optimizer. However, as RL tasks are often nigh-dimensional, these methods have replaced GA with Evolution Strategies (ES) presented by [Salimans al. (2017), which has achieved performance comparable to state-of-the-art deep RL algorithms on high-dimensional control tasks.
NSR-ES (Conti et al. 2018) maintains population of ES agents and introduces Novelty Search (NS) [Lehman& & Stanley] 201 1b) to improve the performance on RL tasks with sparse or deceptive rewards. That is, it adds a novelty term (representing behavior diversity) to the objective function of ES agents. In each iteration, NSR-ES selects a policy from the population for reproduction, where the probability of selecting a particular policy proportional its novelty score.
In contrast to NSR-ES (Conti et al. 2018), DvD-ES [Parker-Holder et al., 2020) optimizes all policies of a population simultaneously. by maximizing the sum of their rewards and a population- wide diversity criterion (i.e., the volume between the behaviors of the policies). Though DvD-ES can maintain diverse population, it ignores the previously generated policies, leading to "cycling" (i.e., a phenomenon where the population keeps moving alternatively between two areas) and thus inefficient performance.
It has been shown (Cully & Demiris 2018) that keeping an additional archive (i.e., a subset of policies generated-so-fat -o-) and selecting policies from the archive instead of the population for reproduction can be beneficial. There are different ways to select policies from the archive. ME-ES (Colas et al. 2020) uses an alternating selection mechanism, which selects several policies with the best quality in iteration and with the best diversity in the next iteration. QD-RL (Cideron et al., (020)) uses Pareto- based selection (Deb) al. 2002) by considering both quality and diversity in one iteration, and achieves better performance. That is, the Pareto front is first calculated with respect to quality and diversity, and then the policies are selected from the Pareto front based on the crowding distance.
Although Pareto-based selection can guarantee the selected policies uniformly distributed over the Pareto front, these policies may be still similar in the behavior space, limiting the performance of QD-RL. For example. Figure ((a) shows the heat map of a synthetic function f(z 3) in the behavior space, where the color corresponds to the function value, which we call quality here. The goal to find the four optimal solutions distributed in the center of four regions of the behavior space. The points represent the solutions in the current archive, from which we need to select some solutions for reproduction. QD-RL first calculates the diversity of each solution (i.e., the average Euclidean distance between this solution and its k-nearest neighbors) in the archive, and then gets the Pareto front with respect to quality and diversity, as shown in Figure [(b) By Pareto-based selection, the blue points together with the red star will be selected, which are uniformly distributed over the Pareto front, but concentrated in the lower right corner of the behavior space.
In this paper, we propose Evolutionary Diversity Optimization algorithm with Clustering- Selection (EDO-CS). In each iteration, the policies in the archive are divided into several clusters based on their behaviors, and high-quality policy is selected from each cluster for reproduction. This selection mechanism can naturally guarantee the diversity of the selected policies in the behavior space. For example, the red points and red star in Figure T(a] will be selected by clustering- selection, which are distributed in the four different areas of the behavioral space.
To examine the performance of EDO-CS, we conduct experiments on a variety of continuous control tasks from OpenAl Gym library (Brockman et al. 2016). Firstly, we show that EDO-CS can solve navigating
2

---

Published as conference paper ICLR 2022
0
1.0
5
Pareto selected
0.9
Chaotriig
Buth aclocted
Diversity
0.8
15
0.7
25
0.5
33
0.2
0.3
0.4
0.5
0.7
0.8
40
Quality
(a) Behavior space
(b) Objective space
The selected solutions by Pareto-based selection and clustering- based selection synthetic problem. Fig- ure [[a) shows the behavior space, where color of heat map shows the quality the solution. Figure I(b) shows the quality and diversity of each solution.
Figure 1:
problems in environments with deceptive rewards. Then, we test it in multi-modal tasks, showing that EDO- CS can efficiently find optimal policies with diverse behaviors. In the standard MuJoCo environments that do not require much diversity, show that EDO-CS can achieve even better performance than Vanilla ES that focuses on the quality. We also test the influence of the hyper-parameters EDO-CS in these environments.
The remainder of this paper is organized as follows. We first introduce some definitions and notations used our paper in Section [ After that, we propose our method in Section 3 The results and analyses of experiments shown in Section 4 Finally, conclude this work in Section
2 BACKGROUND
We consider the setting of fully observable Markov Decision Process (MDP) described tuple A, P, R, 7), where is the state space, A is the action space, P(s++1|85 ae) gives the probability of transiting state 81+1 after taking action a at state 8t, Ft R(se, Ot, 8t41) ) is the reward obtained by transiting to state 8141 after taking action at state 8;, and y is the discount factor.
A policy me S + A is mapping from state space S action space A, paremeterized by 0, which be either deterministic or randomized. The goal of general RL algorithms is to optimize the parameters 0 such that maximizes the expectation of the cumulative rewards R(r) = Σie T'r,, where is the trajectory over horizon T. The objective function can be written as J(0) E2 EE [(()))
To make better exploration and have more robustness, QD algorithms seek to find set of policies with both high rewards and diverse behaviors (Pugh et al. 2016 Cully Demiris 2018). The behavior characteriza- tion ((Ta) of a policy To is usually domain-dependent. For example, can be the coordinates of the final location (z, y) of the robot in the robot locomotion problem. and the corresponding behavior space is R2. high-dimensional behavior space. Given an archive of policies, the diversity of a particular policy mo computed as the average Fuclidean distance between b(TT)) and A' bookk the set of k-nearest neighbors of no in the archive A. That is:
also be defined as the actions taken by policies, leading
Div
1
Σ
(I(TT) b(=()) 1|2-
(1)
Th E 1g
3

---

Published as a conference paper ICLR 2022
Then, the objective function be maximized can be expressed as:
)()) = (1 - A) EErwao [R([T]] + X- Div(O),
(2)
where À controls the trade-off between the quality (i.e., rewards) and diversity.
3 THE EDO-CS ALGORITHM
In this section, we introduce the proposed algorithm, Evolutionary Diversity Optimization with Clustering- based Selection (EDO-CS). We first give an overview of EDO-CS in Section [.]] Then, we introduce the selection and reproduction mechanisms in Sections 3.2 and 3.3 respectively. Section 3.4 shows how balance the quality and diversity. Finally, we compare El DO-CS with other QD algorithms in Section 3.5
3.1 OVERVIEW
A general flow of EDO-CS is shown in Algorithm I first initializes an archive A with a maximum capacity of 1, which contains the policies generated-so-fat together with their corresponding cumulative rewards and behaviors; and a bandit B, which used to sample the weight of diversity (i.e., reproduction process. Then, it adds / randomly generated policies into the archive A (lines I-5), and tries to improve the policies in A iteratively (lines 7-20). In each iteration, EDO-CS employs K-means (Lloyd, 1982 to partition the policies in the archive into K clusters based on their behaviors (line 8), and selects one specific policy from each cluster (line 9). After getting K policies, EDO-CS samples the value of À in the objective function for each policy from the bandit B, and uses the ES optimizer to update the selected policies in parallel for T" iterations (lines 11-15). The archive and bandit are updated in line 18 after evaluating all the generated offspring policies. To maintain the diversity of the archive, we avoid adding policies with similar behaviors (Cully & Mouret| (0013). To be specific, whenever we want to add new policy into the archive, we first select the policy with the most similar behavior from the archive. If their behavior distance is greater than a threshold, we add the new policy into the archive. Otherwise, we compare their rewards and keep the policy with higher reward. Note that if the archive size exceeds the capacity I after adding a new policy, the oldest policy in the archive will be deleted. EDO-CS repeats the above process until the number of iterations reaches
Eq. (2) during the
3.2 CLUSTERING-BASED SELECTION
The selection process in each iteration of EDO-CS tries select set of high-quality policies with diverse behaviors from the archive. Here, we employ a natural and efficient way, i.e., clustering based selection, which first clusters the policies in the archive and then selects high-quality policy from each cluster. Clustering is an unsupervised algorithm for finding natural groups of a data set, such that the data in the same group (i.e., a cluster) are similar while those in different groups are not similar. For a given data set D = [Z1, D2, Vi + j.C, nc, 0 and D k C... K-means (Lloyd [982) is one of the most popular clustering algorithms, which aims to minimize within-cluster variances, I.e.,
). clustering algorithm divides D into K clusters C' = {C1, C2,,.. .-. OK) } where
K
arg min
||
11:1
(3)
DEC
where la is the mean of points in C.,
In the selection process, we first K-means cluster the policies in the archive based their behaviors, which means æ = b(TT) in Eq. (3). Then, we select one specific policy ne, from each cluster Cj- More specifically, we first select the policy with the highest quality from the archive, and the corresponding cluster
4

---

Published as conference paper ICLR 2022
Algorithm 1: EDO-CS
Input: number K of selected policies, number 7 of total iterations, number 7 of updating iterations, behavior characterization b(TT)), archive size archive A, bandit B
Output: archive A
// Warm up
for 1
2
Randomly generate policy T
3 Get cumulative rewards and behavior b(To,) by evaluating the policy Te,;
4
Add (To, R, b(TT,)) )) into archive A
5 end 0:
while do
// Selection
Use K-means to divide the policies in archive A into K clusters {C& ] Select K policies {T // Reproduction for k 1 K do
J J each one from cluster;
// Update in parallel Sample A from the bandit B; for io T do
12
Set the objective function v(O)) (1 As) [R(T)] Dio(:::)
14
Use ES to update 0g as Eq.
end
Get cumulative rewards R and behavior b(To;)) by evaluating the updated policy mo,
end
Update archive and bandit B; t T"
end
is denoted as Cp., Then, for each other cluster C₁ * C-+, we find its M highest-quality policies and select one uniformly at random. Policies in the same cluster have similar behaviors, and each selected policy can be viewed as representative its cluster, which has the potential to reproduce a high-quality policy with this type of behavior. Thus, by this clustering- -based selection process, can select good policies from different areas of the behavior space for reproduction.
Note that some previous works (Vassiliades al. 2017 2018) have also introduced clustering into QD algorithms to ensure diversity. But the usages are quite different. Previous works use the grid-based container and employ clustering to partition a high-dimensional behavior space into well-spread geometric regions before running the iterative evolutionary process, while our EDO-CS employs clustering to select set of high-quality solutions with diverse behaviors from the archive in each iteration.
3.3 ES-BASED REPRODUCTION
To reproduce offspring solutions from the selected solutions, we use ES as the optimizer. Inspired by natural evolution, ES is broad class of population-based black-box optimization algorithms, while here the version introduced in Salimans et al. (2017). which has achieved performance comparable to state-of-thh-aa deep RL algorithms on high-dimensional control tasks. ES represents population of parameters 0 by
5

---

Published as conference paper ICLR 2022
distribution Ps (o) parameterized by Ø, and seeks to optimize the expected objective value Ea-rs [J(O)]. where (()) is an objective function to measure the goodness of parameters 9. Given the population distri- bution P parameters 0f ~ (N (2)) are sampled and evaluated. Using the log-likelihood trick, O, is updated using estimation of the gradient of expected reward:
Valo~pa [J(O)] Σ J(O) log (0)).
(4)
where n is the number of samples evaluated per generation. In practice, any 0j can be decomposed as 0: 0, + oe', where o > 0 and E' ~ NN(00)) Thus, the gradient estimation in Eq. (4) becomes
1 - na
Σ J(O))c'
Vo [] + ac)]
1=
(5)
Based on the above gradient estimation, the parameter 0g will be updated
0 02 - E. J(O))E',
(6)
no
where 7) the learning rate of the ES optimizer. In this paper, we set J(0) Eq. (2). i.e. a weighted sum
of quality and diversity. But different values of the hyper-parameter À in Eq. (2) may be required for
different tasks as well as different stages of the same task, we self-adjust based on multi-armed bandit, which will be presented in the next subsection.
3.4 ADAPTIVE BALANCE BETWEEN QUALITY AND DIVERSITY
In Eq. 2), the reward and diversity correspond to exploitation and exploration, respectively, implying that the hyper-parametter À controls the trade-off between exploitation and exploration. Here, model the problem of setting an appropriate À as a multi-armed bandit problem /Vermorel & Mohri (0055) by treating each alternative À as an arm of the bandit. Let A = (X(), ( {mm) denote the set of alternative arms. For each arm (+), the gain of rewards after updating a policy with ( used as reward. Note that to use the multi-armed bandit model, we have made stationary assumption, i.e., disregarding the change of the reward distribution of each arm in the process of optimization.
The Upper Confidence Bound (UCB) algorithm Auer 2002 is used to select specific arm in each iteration.
That is, the arm A in iteration is chosen as
Int
A = arg max ma (1 + +oV (a(A)))
X
where >> O, (2()) is the estimated mean reward of arm ( and N₂ (A(1) is the number of times we have selected ( Note that (x(((() reflects the current knowledge of the algorithm in condensed form and guides further exploitation, while V N.(A(9) (i.e., the width of the confidence bound) reflects the uncertainty of the algorithm's 's knowledge and guides further exploration. The ablation study of the effectiveness of multi-armed bandit can be found in Appendix A.2
Inf
3.5 COMPARISON OF QD ALGORIHTM
Finally, we compare EDO-CS with other related QD algorithms from the perspective of EAs, as shown in T The second column gives the selection strategies, and the third column shows whether the quality diversity is considered in the objective function for reproducing offspring solutions. In the column of "EAs type", the algorithm maintains μ solutions in the population, and generates À offspring solutions in each iteration, where (j + X) and (n, 2) denote that the parent solutions will and will not selected, respectively. The last column indicates whether the algorithm selects the solutions from the archive.
6

---

Published as a conference paper ICLR 2022
Table 1: review of QD algorithms from the perspective of EAs.
Method
Selection
Reproduction
EAs type
From archive
Vanilla ES
The only parent solution Probabilistic selection
Quality
(1.1)
NSR-ES
Quality and diversity
(K, 1)
CVT-ES
Uniform selection
Quality and diversity
(K + K)
ME-ES
Biased selection
Quality diversity
(K + +K)
V
DvD-ES
All parent solutions
Quality and diversity
(K, K)
X
QD-RL
Pareto-based selection
Quality or diversity
(K + KK)
V
EDO-CS
Clustering- selection
Quality and diversity
(K + K)
V
4 EXPERIMENT
To examine the performance of EDO-CS, we conduct experiments on variety of continuous control tasks from the OpenAl Gym library (Brockman et al.) 2016), including deceptive, multi multi-modes -ooal and standard Mu- JoCo environments. We compare EDO-CS against Vanilla ES (Salimans et al., (0177). NSR-ES (Conti et al.) 2018).
CVT-MAP-Elic (Vassiliades et al.] 2018), ME-ES (Colas et al. 2020p. DvD-ES (Parker-Holder 2020 and QD-RL (Cideron al. 2020). For fair comparison,
the ES optimizer with the is denoted as CVT-ES accordingly. The pop- ulation size K of these algorithms is always to 5. For EDO-CS, the number M of candidates for selection each cluster is set 2, and the arms of the bandit are (X(1) 0, (2) 0.5). Other parameter settings be found in Appendix A. To have a sample-wise fair comparison, each algorithm uses the same number (i.e., 3000) of generations of ES optimizer. Note that each of the 600 iterations in the æ--axis of all figures corresponds to five generations. Thus, for Vanilla ES and NSR-ES which reproduce only one policy in each iteration, one unit in the æ-axis actually corresponds their five iterations. Other algorithms reproduce five policies in each iteration, and thus one unit in the r-axis just corresponds to their one iteration. We report the mean and standard deviations across six identical seeds (2016 2021) for all algorithms and all tasks.
al.
same syper-parameters in all algorithms, and CVT-MAP-ENNE
4.1 DECEPTIVE ENVIRONMENTS
First, consider an environment with deceptive rewards, which is modified from the standard Ant-v2 environment. As shown in Figure 2(a] a U-shape wall is in front of the ant, separating the ant from the target, i.e., green cuboid. The reward is mixture of distance away from the target and costs for joint torques, encouraging the ant to walk to the target as fast as possible. Obviously, following the gradient of only the expected cumulative rewards will make the ant walk forward directly and get trapped by the wall. Here we use the final location (z, y) of the ant as the behavior characterization.
Figure 2(b) shows the rewards of the best- perttrrfffrmiggggg policy in the current archive in each iteration. As expected, both Vanilla ES and DvD-ES fail to get past the wall, because they do not use an archive to record previously explored policies, and thus cannot ensure diversity, leading bad exploration under deceptive environments. NSR-ES can converge fast, but will finally get trapped into a local optimum. This is because NSR-ES reproduces only one policy in each iteration, and may update the same policy for several iterations, which can cause rapid improvement of a particular policy but may also lead to a sub-optimal policy due to the lack considering the whole behavior space. Among the previous algorithms we have compared, only QD-RL can finally obtain the optimal policy, but its convergence speed is slow. We observe that our proposed algorithm EDO-CS can converge to the optimal policy much faster, showing the advantage of clustering- based selection.
7

---

Published as conference paper ICLR 2022
AntWall-vO
500
750
-1000
Reward
-1250
-1500
NSR-ES
CNT-US
1750
2000
(U-RL
100
200
300
400
500
600
Iterations
(a) Wall-OO- environment
(b) Performance of different algorithms
Figure 2: The AntWall-vO environment and the performance of different algorithms.
4.2 MULTI-MODAL ENVIRONMENTS
Next, we create two multi-modal environments to explicitly examine whether EDO-CS can efficiently find high-quality policies with diverse behaviors. The created HalfCheetahFwdBwd and AntFwdBwa environ- ments are based on HalfCheetah-v2 and Aut-v2, respectively. In the HalfCheetahFwddWwd environment, instead of rewarding the agent for walking forward only, we assign rewards for both walking forward and backward, implying that there are two modals in this environment, i.e., walking forward and walking back- ward. We train policies this multi-modal environment, but test them in the single-modal environments HalfCheetahFFd and HalfCheetahBwd. The best-performing policies for these two modals are reported, respectively. We use the final location (z, y) the agent as the behavior characterization. The AntFwdBwd environment is created similarly.
To compare different algorithms more clearly, we organize the experimental results into tabular form. Table reports the cumulative rewards, together with the average performance rankings of all algorithms in the four environments. We can observe that Vanilla ES which maintains one policy can only learn a single modal, i.e., walking backward in HalfCheetah wd and walking forward in And.wdBwd. As expected, all the other algorithms maintain population of policies, and thus can achieve better performance than Vanilla ES in the multi-modal environments. DvD-ES learn both modals ArtFwdBwdd but single modal in HalfCheetahFwddWi environments, but the quality of each modal is less satisfactory due their inefficient selection mechanisms. We can observe that EDO-CS can learn any modal, and always achieves the highest quality in each modal, validating that EDO-CS can find a set of high-quality policies with diverse behaviors.
NSR-ES, ME-ES, CVT-ES and QD-RL can learn both modals in both
Table 2: Rewards obtained by different algorithms in multi-modal environments.
Environment
EDO-CS
QD-RL
ME-ES
DvD-ES
CVT-ES
NSR-ES
Vanilla ES
Fwl
4284
2930
2700
-3419
3219
1346
-5543
HalfCheetahBwd
6548
6013
5953
6353
4672
5366
3911
AntFwd
4617
4291
4316
4507
3856
1737
1911
AntBwd
4697
4164
4123
3498
2958
3961
-851
Performance Ranking
3
3.5
3.75
4.75
5.25
6.75
8

---

Published as a conference paper ICLR 2022
4.3 SINGLE-MODAL ENVIRONMENTS
To examine the performance of EDO-CS for solving tasks that do not require much diversity, we conduct experiments in standard MuJoCo environments. Here we adopt the action-based behavior characterization, which was also used in (Parker-Holder et al. 2020). The behavior characterization b(TT)) of particular deterministic policy Te is represented in a vectorized form: b(TT)) = (= where S the state space, and x 8) corresponds to the action taken in state under policy up. Since the state space can be infinitely large, we randomly sample 20 states instead of all. We compare all algorithms used before, except ME-ES, which requires discretization of the behavior space and is hard to be applied to high dimensional behavior space. Figure shows the results of different algorithms on four standard MuJoCo tasks. We can observe that EDO-CS can always achieve the best final performance. Although Vanilla ES and NSR-ES can sometimes converge faster at the early stage of optimization, e.g., in the Humanoid-v2 environment, their final performance is limited. The performance of DVD-ES and QD-RL is dominated by that of EDO-CS, because their curves are always below that of EDO-CS.
EDO-CS
Vanilla ES
NSR-ES
DvD-ES
QD-RL
Hopper-s2
Walker2d-2
Ant-22
Hunsmodd-12
1000
Reword
Ri-vorrd
Revard
200
1807
Iterations
Iteratioss
Iterations
Iterations
Figure 3: Performance different algorithms four standard MuJoCo environments.
By visualizing the clusters in different iterations of EDO-CS, we find that a set of diverse policies can be indeed selected from the archive through clustering- based selection. By the comparison with fixed X, we also validate the effectiveness of self-adjusting À in Eq. (2) using multi-armed bandit modeling. The influence of the hyper-parameters (including clustering algorithm, number T" of updating iterations, population size K and archive size I) on the performance of EDO-CS is investigated as well. Due to space limitation, these experimental results are provided in Appendix
5 CONCLUSION
QD algorithms aim to help RL to find set of high gugh-quality policies with diverse behaviors in complex envi- ronments. However, existing algorithms cannot fully guarantee both quality and diversity, mainly because of their inefficient selection mechanisms. In this paper, we propose the algorithm EDO-CS using clustering- based selection, and demonstrate its superiority by experiments on various control tasks.
We have used ES as the optimizer. In fact, EDO-CS can also be equipped with the sample-efficient policy optimizer (Liu et al. 2020) Nilsson & Cully 202T), which may further improve the performance. The mechanism of self-adjusting À by multi-armed bandit modeling can be replaced by state-of-the-art online- learning algorithms, which may better balance the importance of quality and diversity. In addition, how decide the population size automatically is also matter of interest. One possible approach is to let the clustering algorithm determine the number of clusters by itself. Other interesting future works include combining EDO-CS with representation
manifold learning (Vassiliades & Mouret, 2018 Gaier al. 2020 Rakicevic et al., 2021) in the parameter space or behavior space, and analyzing the performance of EDO-CS theoretically (Gao et al. 2015 Doncieux al. 2019.

---

Published as a conference paper ICLR 2022
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their insightful and valuable comments. We thank Feiyu Liu, Lei Yuan, Ziniu Li. Tian Xu, Haopu Shang, and Xucyao Zhang for reading the manuscript and providing helpful comments. This work was supported by the NSFC (62022039), the Jiangsu NSF (BK20201247), and the CAAl-Huawei MindSpore Open Fund.
REFERENCES
P. Auer. Using confidence bounds for exploitation-exploratio trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
Bäck. Evolutionary algorithms in theory and practice: Evolution Strategies, evolutionary programming, genetic algorithms. Oxford University Press, 1996.
G. Brockman, Cheung, L. Pettersson, Schneider, Schulman, Tang, and W. Zaremba. OpenAl Gym. CoRR abs/1606.01 2016.
Efficient mixing of quality and diversity G. Cideron, T. Pierrot, N. Perrin, K. Beguir, and O. Sigaud. Efficent in reinforcement learning. CoRR abs/2006.08505 2020.
C. Colas, V. Madhavan, J. Huizinga, and J. Clune. Scaling map-elites to deep neuroevolution. In Proceedings of the 22nd Genetic and Evolutionary Computation Conference (GECCO), pp. 67-75, Cancán, Mexico, 2020.
Conti, V. Madhavan, F. Such, J. Lehman, K. O. Stanley, and J. Clune. Improving exploration in evolu- tion strategies for deep reinforcement learning via a population of novelty-secking agents. In Advances in Neural Information Processing Systems 32 (NeurIPS), pp. 5032-5043, Montréal, Canada, 2018
A. Cully and Y. Demiris. Quality and diversity optimization: A unifying modular framework. IEEE Trans- actions on Evolutionary Computation, 22(2):245-259, 2018.
A. Cully and J.-B. Mouret. Behavioral repertoire learning in robotics. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO), pp. 175-182, Amsterdam, The Nether- lands, 2013.
A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret. Robots that can adapt like animals. Nature, 521(7553): 503-507, 2015.
K. Deb, A. Pratap. S. Agarwal, and T. Meyarivan. A fast and clitist multiobjective genetic algorithm: NSGA-IL. IEEE Transactions on Evolutionary Computation, 6(2):182-197, 2002
S. Doncieux, A. Laflaquière, and A. Coninx. Novelty search: A theoretical perspective. In Proceedings of the 21st Genetic and Evolutionary Computation Conference (GECCO), pp. 99-106, Prague, Czech Republic, 2019.
A. Gaier, A. Asteroth, and J.-B. Mouret. Discovering representations for black-box optimization. Pro- ceeding the 22nd Genetic and Evolutionary Computation Conference (GECCO), pp. 103-111, Cancún, Mexico, 2020.
W. Gao, M. Pourhassan, and F. Neumann. Runtime analysis of evolutionary diversity optimization and the vertex cover problem. In Proceedings of the 17th Genetic and Evolutionary Computation Conference (GECCO) Companion, pp. 1395-1396, Madrid, Spain, 2015.
10

---

Published as conference paper ICLR 2022
S. Kumar, A. Kumar, S. Levine, and C. Finn. One solution is all you need: Few-shot extrapolation via structured MaxEnt RL. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp- 8198-86 8210, Vancouver, Canada, 2020.
J. Lehman and K. O. Stanley. competition. In Proceedings of the 13th Genetic and Evolutionary Computation Conference (GECCO), pp. 211-218, Dublin, Ireland, 2011a.
Evolving a diversity of virtual creatures through novelty search and local
J. Lehman and K. O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2):189-22 2011b.
Li. Deep reinforcement learning: An overview. CoRR abs/1701.07274, 2017.
F. Liu, Z. Li, and C. Qian. Self-guided evolution strategies with historical estimated gradients. In Pro- ceedings of the 29th International Joint Conference Artificial Intelligence (IJCAT), pp. 1474-1480, Yokohama, Japan, 2020.
S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129-337, 1982.
P. Mirowski, R. Pascanu, Viola, H. Soyer, A. Ballard, A. Banino, M. Denil, Goroshin, L.. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell. Learning to navigate in complex environments. In Pro- ceedings of the 5th International Conference on Learning Representations (ICLR), Toulon, France, 2017.
J.BB. Mouret and J. Clune. Illuminating search spaces by mapping clites. CoRR abs/1504.04909, 2015.
F. Murtagh and P. Legendre. Ward's hierarchical agglomerative clustering method: which algorithms imple- ward's criterion? Journal of classification, 31:274-295, 2014.
O. Nilsson and A. Cully. Policy gradient assisted map-elites. In Proceedings of the 23th Genetic and Evolutionary Computation Conference (GECCO), pp. 866 875, Lille, France, 2021.
J. Polker-Holder, A. Pacchiano, K. M. Choromanski, and S. J. Roberts. Effective diversity in population based reinforcement learning. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp- 18050-18062, Vancouver, Canada, 2020.
J. K. Pugh, L. B. Soros, and K. O. Stanley. Quality diversity: new frontier for evolutionary computation. Frontiers in Robotics and AI, 3:40, 2016.
N. Rakicevic, A. Cully, and P. Kormushev. Policy manifold search: Exploring the manifold hypothesis for diversity-based neuroevolution. In Proceeding of the 23th Genetic and Evolutionary Computation Conference (GECCO), pp. 901-909, Lille, France, 2021.
T. Salimans, J. Ho, X. Chen, S. Sidor. and I. Sutskever. Evolution strategies as scalable alternative to reinforcement learning. CoRR htd//7003.3388 2017.
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT Press, 2018.
V. Vassiliades and J.-B. Mouret. Discovering the elite hypervolume by leveraging interspecies correlation. In Proceedings of the 20th Genetic and Evolutionary Computation Conference (GECCO), pp. 149-156, Kyoto, Japan, 2018
V. Vassiliades, K. I. Chatzilygeroudis, and J.-B. Mouret. A comparison of illumination algorithms in bounded spaces. In Proceeding of the 19th Genetic and Evolutionary Computation Conference Compan- ion (GECCO), pp. 1578-155 1581, Berlin, Germany, 2017.

---

Published as conference paper ICLR 2022
Vassiliades, K. Chatzilygerouddss and J.-B. Mouret. Using centroidal voronoi tessellations scale up the multidimensional archive of phenotypic elites algorithm. IEEE Transactions on Evolutionary Computation, 22(4):623-633 6360233330,--2 2018.
J. Vermorel and M. Mohri. Multi-armed bandit algorithms and empirical evaluation. In Proceedings of the 16th European Conference Machine Learning (ECML), pp. 437-448, Porto, Portugal, 2005.
U. Von Luxburg. A tutorial spectral clustering. Statistics and computing, 17(4):395 2007.
T. Zhang, R. Ramakrishnan, and M. Livny, Birch: efficient data clustering method for very large databases. ACM sigmod record, 25(2):103-114, 1996.
Y. Zhu, R. Mottaghi, E. Kolve, J. J. Lim, A. Gupta, F.-F. Li, and A. Farhadi. Target-driven visual navigation indoor scenes using deep reinforcement learning. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp. 3357-3364, Singapore, 2017.
12

---

Published as conference paper ICLR 2022
A APPENDIX
A.1 HYPER-PARAMETER
This section will introduce the hyper-ppanee parameters used in our experiments. For fair comparison, all the hyper- parameters of different algorithms be same in each environment.
Table 3: Hlyper-aaameeters for deceptive and multi modal environments.
Hyper- Hyper-paramen parameter
AntWall-vO
WalsCheetahFwdBww
AntFwdBwd
Population size Archive size [
5
20
100
100
Number T of updating iterations in ES in ES
10
5
10
0.025
0.03
0.025
0.015
0.02
0.015
Table 4: Hyper-parameters for single- modal environments.
Hyper-parameter
Hopper-v2
Walker2d-v2
Ant-v2
Humanoid-v2
Population size Archive size I Number T' of updating iterations in ES in ES
5
5
30
30
30
20
10
10
0.025
0.025
0.025
0.0075
0.02
0.03
0.015
0.02
A.2 ADDITIONAL EXPERIMENTAL RESULTS
Visualization of clusters. We visualize the clusters in different iterations of EDO-CS for the experiments under An/Wall-vO environment. Figure shows the behavior space, where the points represent the so- lutions in the current archive, and the different colors represent the different clusters. Throughout the op- timization process, we can observe that the solutions in archive can always partitioned into clusters with different behaviors, validating the effectiveness of clustering based selection. As the optimization goes, the clusters can spread different regions of the behavior space better, also implying that EDO-CS can indeed find set of diverse policies.
Figure Visualization of clusters different iterations of EDO-CS under the An/Wall-vO environment.
Adaptive X. EDO-CS self-adjusts the hyper-parameter À in Eq. 2 by multi-armed bandit modeling.
larger À implies larger weight of diversity when doing reproduction with ES. We have used (X(1)
13

---

Published as a conference paper ICLR 2022
0, A2) 0.5) as the two arms in the experiments. To examine the effectiveness of this adaptive mechanism, we compare it with fixed À E {0, 0.5} in deceptive and multi-modal environments. The results in Table show that the adaptive setting of always leads to the best performance.
Table 5: Performance of EDO-C CS under different settings of A.
Setting of À
An/Wall-vO
HaljCheetahFwd
HaljCheetahBwd
AntEwd
AntBwd
Adaptive X
-529
4284
6548
4617
4697
X 0
-650
3856
5931
4340
4426
= 0.5
-850
3877
6077
2800
3093
Direct optimization. The selection process in each iteration of EDO-CS is to select a set of high-quality policies with diverse behaviors from the archive. One direct way to optimize the weighted sum of the quality (i.e., rewards) and an explicit diversity metric, which is, however, quite difficult. First, it is hard balance the weights of quality and diversity in the objective function. Second, this is actually a pseudo- Boolean optimization problem with the search space size (k),, where is the archive size and the number of selected policies. Besides, this optimization problem requires an efficient optimization algorithm, which is, however, not easy to design. Here, we empirically compare our clustering- selection strategy with the direct-opiimizzaionn-iee based selection strategy.
For the direct optimization procedure, a set of high-quality policies with diverse behaviors is selected from the archive in each iteration, by directly optimizing the weighted sum of quality and diversity. The quality is defined as the sum of rewards of the selected policies. We consider two diversity measures. One is the sum of the pairwise distances between all the policies in the selected set. The other the determinant of the similarity matrix II of the policies in the selected set, where IT is the similarity between the i-th and j-th selected policies, and the main diagonal are all 1. The similarity matrix II is also used in DvD-ES (Parker- Holder et al.) 2020 The two corresponding objective functions are denoted as fpair and fdet. respectively, shown in Eqs. and
K
fpair (1 - w)
E no
[R(T)]
[l((TT.) b(TTT))) )112
(8)
1=1
1=1 jæ
K
fdet= = (1 w)
Σ
E ETnno: [R(T)] + w (II
(9)
The weight w in Eqs. (8) and 99 is set to 1/2 in the experiments, i.e., the quality and diversity are treated equally important. Note that both the quality and diversity have been normalized to be in [0. 1J. For the optimizer, we employ a genetic algorithm which maintains 100 solutions (i.c., the population size is 100) and generates 100 offspring solutions in each generation. To optimize fpair and fäet, we run the genetic algorithm for 200 generations.
The results shown in the following two tables. EDO-CS is the proposed algorithm with the clustering- based selection strategy, while EDO-DOSpair and EDO-DOS denote the algorithms with the direct- optimization-base selection strategy, where the objective functions are fpair and Sáct, respectively. Table shows the reward of the best policy found by each algorithm, from which we can observe that the EDO-CS algorithm performs better in most cases. Table 7 shows the time required to run the selection process once, and the clustering- based selection strategy is significantly faster than the dirrec-optimizztioonbeo strategy. Thus, our clustering-bast selection method can be better and faster.
selection
14

---

Published as conference paper ICLR 2022
Table 6: Performance EDO-CS and algorithms direct-optimizztioon-bann selection strategy.
Method
AnrWall-vO
HalfCheetahFwd
HalfCheetahBwd
AntFwd
AntBwd
EDO-CS
-529
4284
6548
4617
4697
EDO-DOSpare
-706
4188
5847
5013
4392
EDO-DOS det
-536
-5591
6529
-530
2417
Table 7: Time required to run the selection process once of EDO-CS and the algorithms with the direct-optimization- based selection strategy.
Method EDO-CS
AntWall-vO
HalfCheetahFwwdBdd
AntFwdBwd
0.015
0.021
0.023
EDO-DOS pair
9.570
9.802
9.807
EDO-DOSdet
8,900
9.266
9.567
Clustering algorithm. An essential step of EDO-CS to cluster policies in the behavior space. We have adopted the K-means clustering algorithm because of its popularity. However, it is interesting examine whether the choice of clustering algorithm will affect the performance of EDO-CS largely. Thus, we conduct experiments over various clustering algorithms, including Hierarchical Agglomerative Clustering (HAC) (Murtagh & Legendre| 2014), K K-means (Lloyd 1982). Balanced Iterative Reducing Clustering using Hierarchies (BIRCH) (Zhang al. 1996), and Spectral Clustering (Von Luxburg 2007). Figure(JJshwss that these clustering algorithms except BIRCH can lead to the similar performance of EDO-CS in most cases. BIRCH is suitable for large number of samples, while the number of policies in the archive relatively small. Thus, we may not get good clustering results by BIRCH, degrading the performance.
AntWall-vO
HallCheetahFwd
HallCheetshBwd
1000
750-
4000
60000
Reward
Reward
3000
Reward
10000
-1259
2000
1000
HAC
-1350
M-Moaa SIRCH
BIRCH
K-htzrn
Saccual Clanaii
Speciall Ulavioi
Speceel Cluicing
100
200
300
400
500
600
100
200
300
410
2/01
690
0
100
300
4000
500
600
Iterations
Iterations
Iterations
Walker2d.v2
Hopper-v2
4000
3386
Rewarr
2000
BAE KiMees
Special Chatake
Special Chacadag
114
200
2011
40D
210
60
190
200
300
2101
540
000
Iterations
lterations
Figure 5: Performance of EDO-CS equipped with different clustering algorithms.
15

---

Published as conference paper ICLR 2022
Number 7" of updating iterations. We also study the influence of the number T" of updating iterations, i.e., the number of iterations for which we use ES to update the policy (in lines 12-15 of Algorithm I after selecting from the archive. We have tested T' {5, 10, 15, 20) under various environments. The results in Table 8 show that the performance of EDO-CS is not very sensitive to T". Note that we have also tried to update the selected policy for only one iteration (i.e., set T 1), but it fails. the number of updating iterations is too small, the difference between solutions will be insignificant, leading to ineffective selection.
Table 8: Performance of EDO-CS under different numbers T" of updating iterations.
Environment
T'
7' 10
7 = 15
7
20
HalfCheetahFwd
4462
4216
4911
4926
HalfCheetahBwd
6407
6527
6285
6203
Walker2d-v2
2830
4870
4362
4676
Hopper-v2
3301
3566
3578
3559
Population size K. The population size K refers to the number of policies select from the archive each iteration. If the population size is too small, we may not be able to find all optimal policies with diverse behaviors. If the population size is too large, some policies with similar behavior will be selected and updated, harming the efficiency of EDO-CS. Thus, it is important to select a proper population size K.
Table 9 shows the performance of EDO-CS under different population sizes. For sample-wis fair com- parison, we report the results under the same number interactions with the environment rather than under the same number of iterations. It can be observed that the default population size of K 5 is appropriate in most environments.
Table 9: Rewards obtained by EDO-CS with different population sizes K, given the same number of interactions with the environment.
Environment
k=3
K =
==7
K = 9
Ant Wall-vO
-852
-618
-1082
-970
HwdfCheetahFwdBWdl
9101
10274
10221
10242
Walker2d-v2
1840
2453
3062
3558
Hopper-v2 2688
3164
2781
2856
Figure ( shows the performance of EDO-CS with different population sizes, given the same number of iter- ations. As expected, a larger population size implies a greater number interactions with the environment, and thus results in a better performance of EDO-CS.
Archive size 1. The archive used to record the high-quality policies with diverse behaviors generated- so-far. It is crucial for EDO-CS, as the parent policies for reproduction in each iteration are selected from the archive. the archive size is too small, some useful information may be lost. If is too large, the archive will contain lots of low-quality policies encountered before, the selection of which for reproduction will lower the efficiency. Figure 7 shows the results under different archive sizes. It would be interesting to investigate how adaptively set the archive size of QD algorithms.
16

---

Published as conference paper ICLR 2022
AntWall-vo
HallCheetahFwd
HallCheetahBWd
-500
6000
Reward
1030
Reward
Reward
1000
3000
2000
1991
2000
1000
-209
200
400
600
340
Iterations
Walker2d-12
Hopper-v2
5080
3000
Reward
2000
100
200
300
100
300
200
Iterations
Iterttions
Figure 6: Performance of EDO-CS with different population sizes given the number of iterations.
AntWall-vO
HallChectahFwd
HalfChectahBwd
1000
-150
4000
5000
Reward
Reward
Reward
-2250
1500
1000
-2033
190
110
100
(001
160
200
450
500
603
100
360
360
400
500
600
lterations
Iterations
lteratioons
Walker2d-v2
1lopper-22
4000
3080
100
700
301
100
(00
100
700
300
400
900
600
Iterations
Iterations
Figure Performance of EDO-CS under different archive sizes.
17


Reviews:
[{"review_id": "ofVVz75hAD", "reviewer": "Reviewer_5sru", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The experimental evaluation demonstrates the benefits of the proposed methods on a variety of domains showing different numbers of modalities and complexity of the behavioural space. Multiple existing algorithms are used as baselines, which is great. \n\nOverall the paper is very clear and easy to read and understand. It is well structured and nicely illustrated. \n\nUnfortunately, while it is a great paper, it misses some key references in the literature which are making the novelty claims less obvious and inviting additional experiments.\n\nFirst of all, the concept of dividing the behaviour space into cells and only selecting the best solutions is exactly the purpose of the grid-based archive in MAP-Elites algorithms[1], probably the most famous QD algorithm in the literature. Combining MAP-Elites with a K-mean to automatically partition the behaviour space was firstly introduced in CVT-MAP-Elites [2] and its extension Cluster-Elites [3]. Biasing the cell/cluster selection based on the reward/fitness was first studied in [4] (without really demonstrating improvement over a uniform selection, when quality and diversity of the archive is considered). \nMoreover, the comparison between selection from the archive, or from a separate population or a Pareto-front, was also studied in [4] reaching the same conclusion as in the proposed paper: archive-based selection outperforms population or Pareto-front ones.\n\nIt is important to come back on the fact that the grid of MAP-Elites already performs a form of clustering and filtering to keep only the best policies in each cell of the grid. Given that ME-ES (which stand for MAP-Elites-ES) uses such a grid, I found the statement \"only selecting one policy in each iteration [used by ME-ES], may cause only a specific behaviour to be well optimized and can not return a set of high-quality policies with diverse behaviours.\" confusing as the grid is designed to maintain a diversity of behaviour and improving them in parallel. \n\nIn my opinion, the proposed selection mechanism is not novel and directly linked to the archive management introduced in MAP-Elites and its extensions. \n\nThe paper should also consider PGA-MAP-Elites[5], which combines CVT-MAP-Elites with policy gradient (TD3) for the evolution of NN policies and outperforming the best baseline (QD-RL) presented in this paper. Given that PGA-MAP-Elites uses a selection mechanism that is linked to the one proposed in this paper and shows better performance than QD-RL and other baselines, I think it is an important baseline to consider. \n\nAdditionally, it seems that the authors of the QD-RL paper are still trying to publish the paper and made several updates to the paper. https://openreview.net/pdf?id=8FRw857AYba\nOne of them is the use of the grid from MAP-Elites. This change was most likely made because the authors found similar findings to the one presented here. I do not think it is fair to request the authors of this paper to be aware and to consider a paper that is still under review somewhere else. Therefore, I am not considering this part in my assessment of the paper. Yet, I thought it is important to point the authors to this new version of the paper so that the claims made here will not be outdated in a few months. \n\nOther, smaller comments: \nThe use of the best reward makes sense from a deep-RL point of view. However, the sum of the reward of all the policies in the collection (also, called QD-score) is more frequently adopted in the QD literature. It would be good to add a few sentences justifying this decision and how it can affect the baselines' performance. \nIn the multi-modal environment, how is computed the Mean rewards? Is it the mean reward of the two best policies (one per modality), or something else?\n\"Figure 6: Archive size\" does not seem to report archive size. \n\n[1] Mouret, J. B., & Clune, J. (2015). Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909.\n\n[2] Vassiliades, V., Chatzilygeroudis, K., & Mouret, J. B. (2017). Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Transactions on Evolutionary Computation, 22(4), 623-630.\n\n[3] Vassiliades, V., Chatzilygeroudis, K., & Mouret, J. B. (2017, July). A comparison of illumination algorithms in unbounded spaces. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (pp. 1578-1581).\n\n[4] Cully, A., & Demiris, Y. (2017). Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation, 22(2), 245-259.\n\n[5] Nilsson, O., & Cully, A. (2021). Policy gradient assisted MAP-Elites. In Proceedings of the Genetic and Evolutionary Computation Conference Companion.", "summary_of_the_paper": "In the paper \"Evolutionary Diversity Optimization With Clustering-Based Selection For Reinforcement Learning\", the authors introduce a new selection mechanism for Quality-Diversity based algorithms. This new selection mechanism is based on the K-Means algorithm, to cluster the behaviour space into cells and then select only the best policies within each cell. The paper also uses a linear combination of the reward and novelty score when performing the policy updates. The weights the of the linear combination are automatically adjusted using a bandit algorithm so that the best reward is obtained. ", "summary_of_the_review": "Overall the paper is very clear and easy to read and understand. It is well structured and nicely illustrated. \nUnfortunately, while it is a great paper, it misses some key references in the literature which are making the novelty claims less obvious and inviting additional experiments.\n\n---- \nUpdated score after discussion below. \n----", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KmIgWFoFLPK", "reviewer": "Reviewer_RfKF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper gives clear motivation to the problem of optimising for quality and diversity in reinforcement learning and clearly defines relevant terminology throughout. It is easy to follow and the conclusion are well supported by the results. \n\nMore specifically to the method presented, the authors investigate the applicability to clustering methods for selection of policies in evolutionary strategies. This is an interesting area of study and the authors present a convincing method that performs well on several toy problems. There has been some application of evolutionary strategies for selection of policies in the field but this is the first application of K-means clustering to my knowledge. One of my initial criticisms when reading was the impact of hyper-parameters (cluster size, clustering algorithm, archive size, etc) but was pleased to see that the authors have considered this in detail and presented relevant results on this within the appendices. \n\nThe central comment I have on this paper is it would be interesting to see how their method navigates between clusters and how representative these clusters are of behavioural strategies. Evolutionary algorithms are well known for falling into local minima given poor selection of mutation rates and population size. As I understand the paper, the clustering aspect addresses this by ensuring a wider range of policy-space is sampled. Is it possible to quantify/comment on whether the authors method is achieving this? Similarly, I naively assume that cluster separation will be arbitrary where the number of clusters is larger than the number of distinct behaviours. I would be interested to see how well the clustering algorithm performs at identifying behaviours – for example, a demonstration that policies sampled from the clusters do indeed lead to diverse behaviours when examining those policies that were ranked highly but distinct. \n\nFinally, there are some minor recommended typographic edits. In several places, method initials are given without prior statement (for example, ME-NS and ES). The colour and size of points in Figure 1 is also not extremely clear, especially when trying to identify Pareto/Clustering/Both/None in Fig.1b. \n", "summary_of_the_paper": "The authors present a new method for finding robust policies in reinforcement learning, those policies which give high rewards but also come from a diversity of behaviours. The authors accomplish this by using a clustering algorithm to first divide policies into relevant clusters and then use evolutionary algorithms to optimise policy choice. The result is an algorithm that performs well over several representative benchmarks, achieving SOTA performance with high convergence rates. ", "summary_of_the_review": "Overall, an interesting and well thought through investigation into the role of clustering when selecting in evolutionary strategies for reinforcement learning. The results give a clear indication that clustering can greatly improve results under certain settings, with good attention given to the impact on changes method parameters such as clustering algorithm and size. However, more needs to be done to show explicitly that those selected policies do end up being more diverse in behaviours. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Gi1qtBFdOeP", "reviewer": "Reviewer_SvUL", "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": "\nStrengths:\n* Experiments are quite comprehensive, having performed comparisons over many different diversity algorithms. The results show that EDO-CS achieves better performance over all other baselines. The environments used are also quite diverse, ranging from AntWall, to multi-modal environments, and finally single-modal environments.\n* Multiple ablation studies are performed over the method, including varying components such as the clustering algorithm used, number of ES update iterations, population size, and archive size. This should give practitioners better idea of how to tune the method.\n\n\nWeaknesses:\n\n* Some presentation issues throughout the paper. \n  * In Figure 1(a), the dots should be made bigger and colors should be more visible and contrasting, or there should be a way to denote the region highlighted by e.g. blue or red dots. This will allow the conclusion to be much more obvious that Pareto/Clustering-selected points allow more multiobjective dominance / higher rewards, as currently it is fairly straining to the eyes. Similar issue occurs in Figure 1(b), where I had trouble understanding what is going on. What does \"quality\" (the heatmap metric) mean here? What should I be looking at? It may help to define these terms like \"quality\" first, which means it might be best to move Figure 1 after notation has been established in Section 2. \n  * Could you explain why we're using a bandit approach for $\\lambda$? If I'm not mistaken, normally multi-arm bandit scenarios involve a stochastic reward function defined by a probability distribution. Can you explain, what is the \"reward function\" for $\\lambda$? If it's $J(\\theta)$, isn't $\\theta$ moving and thus \"$\\lambda$'s reward is nonstationary?\" I'm fairly confused about the involvement of bandits in this scenario. \n  * Slightly awkward English that could also be cleaner and more precise with the use of mathematical notation. For instance, Section 3.2: \"Then, we select one specific policy from each cluster. More specifically, from the cluster where the best quality policy locates, we just select this policy.\" This sentence could be made more precise by using the notation defined previously (e.g. cluster $C_{i}$, policy $\\pi_{\\theta_{i}}$). This was an issue throughout the paper, where there were too many ambiguous references. \n  * A less important issue is in formatting, where there is a gap in space at the bottom of each page that should be fixed. Grammar, spacing, and \\citep vs \\cite issues should be fixed throughout.\n\n* Somewhat shaky motivation for the clustering heuristic. \n  * The real end goal of the clustering procedure, is to really find $K$ policies which are behaviorally different from each other. The rest of the clustering doesn't ever actually get used (please correct me if I'm wrong). If this is the case, why is clustering the best way to find $K$ diverse policies? Normally, clustering algorithms use an entire cluster for some purpose (e.g. see applications in [1]). Why not optimize an explicit diversity metric that measures the behavioral difference between the $K$ policies? I admit, I have seen a variant of the clustering approach (termed speciation) in NEAT [2], but it would significantly strengthen this paper if there was a better motivation + explanation for the use of the clustering heuristic. \n  * Another way to explain this better is to perhaps visualize the clusters in terms of behaviors, throughout optimization, on a 2-d plot (since some of the Mujoco benchmarks conveniently define $b(\\cdot)$ in terms of xy-locations).\n\n\n[1] https://en.wikipedia.org/wiki/K-means_clustering\n\n[2] Evolving Neural Networks Through Augmenting Topologies (2002)", "summary_of_the_paper": "This paper performs research in the area of diversity/novelty-seeking agents under evolutionary optimization approaches. The core idea in this area is to optimize a weighted combination between raw environment reward and diversity during training (even though evaluation is still on the raw environment reward only). The diversity acts as a \"regularizer\" in order to achieve better exploration, which can lead to higher rewards.\n\nThe specific approach (EDO-CS) by the paper suggests using a pool/\"archive\" $A$ of previous policies, which are then clustered via K-means according to the distance metric defined by the behavior function $b(\\cdot)$. Each cluster then produces a new policy (and thus there are a total of $K$ new policies), which are then updated via ES over a regularized reward (via diversity metric, along with an adaptive weighting $\\lambda$), and put back into the archive. \n\nExperiments are performed over various continuous control benchmarks for testing exploration, and results show that EDO-CS achieves SOTA.", "summary_of_the_review": "While the paper produces experimentally strong results, it lacks motivation (especially for the clustering heuristic) as well as certain components such as the use of multi-armed bandits for adaptively tuning $\\lambda$. One danger to this lack of motivation is the introduction to potential confounding factors (e.g. what if the clustering heuristic is implicitly optimizing an ideal diversity objective, and it's better to optimize this ideal diversity objective instead?). \n\nThere is also a nontrivial amount of presentation issues (not just small grammar mistakes or typos) that affect the paper's scientific quality as well.\n\nI am willing to increase my score if the authors fixed the core issues outlined above.\n\nEDIT: I have increased my score to a 6 as well as my confidence scores. The authors have addressed my questions and concerns.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5vbv1soGwl0", "reviewer": "Reviewer_oa8b", "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": "\nThe paper is well-written with a clear goal developing a method that optimises for diversity in addition to fitness. The main contributions include sampling policies and a novel approach to adapting the optimisation function.\n\nHowever, I have several concerns:\n\n* The definition of a behaviour is not clear from the beginning and should be defined earlier. There seems to be a misalignment between the use of behaviour diversity in the proposed approach (mostly for exploration) w.r.t. the approaches in the literature (to maintain a diverse collection of policy behaviours). It would be useful to discuss how the proposed approach relates/differs from the two main approaches in QD:\n\n  - Joel Lehman and Kenneth O Stanley. Evolving a diversity of virtual creatures through novelty search and\nlocal competition, GECCO, 2011 \n  - Jean-Baptiste Mouret and Jeff Clune. 2015. Illuminating search spaces by mapping elites. ArXiv, 2015\n  - Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that can adapt like animals. Nature, 2015\n\n* If I understand correctly, the clustering is done in the policy parameter space rather than in the behaviour space. This leads to the diversity in policy parameterisation but not necessarily to behaviour diversity. This then also raises a question what is the point of maintaining these clusters as opposed to sampling based on distance. Another drawback I see is that there is no explicit maintenance of diversity within the archive, and thus no way of sampling diverse behaviours.\nOn this note, it would be beneficial to provide some additional reasoning behind this. Moreover, there are several recent works that discuss using learned representations or manifolds in order to obtain a more grounded notion of distance in the policy parameter space, which might be useful in this work:\n  - Nemanja Rakicevic, Antoine Cully, and Petar Kormushev. Policy manifold search: Exploring the manifold hypothesis for diversity-based neuroevolution. GECCO, 2021\n  - Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. Discovering Representations for Black-box Optimization. GECCO, 2020\n  - Vassilis Vassiliades and Jean-Baptiste Mouret. Discovering the elite hypervolume by leveraging interspecies\ncorrelation. GECCO, 2018\n\n* I think an ablation study to show the contribution of the MAB selection of  $\\lambda$ would be beneficial, as this seems to be an important contribution. This ablation would further strengthen the point made about optimising for diversity.\n\n\n### Some questions:\n* What are the results that are reported, of the best performing policy in each iteration?\n\n* The total number of iterations in the deceptive task is 600, does this mean the total number of policies evaluated in the environment?\nSection 4.3 distinguishes number of interactions with the environment vs number of iterations. This is not clear from Algorithm 1, and would be useful to clarify. The presented number of evaluations is significantly less than what is usually needed for ES-based approaches.\n\n\n### Minor comments:\n\n* It is not clear what does \"EAs type\" in Table 1 mean exactly. In the text it says “how many parents and offspring the algorithm will maintain in the population” but I find it not clear what this means.\n\n", "summary_of_the_paper": "The authors present EDO-CS an approach to multi-objective optimisation that ensures the high quality and diversity of generated RL policies. Instead of uniformly sampling solutions from the Pareto front, sampling policies from learned clusters is introduced, as a selection mechanism within the ES optimisation. The quality and diversity are further achieved by modifying the objective function of the ES algorithm so it includes both the fitness and behaviour-diversity terms, balanced with a hyperparameter $\\lambda$. This hyperparameter is set using a multi-arm bandit approach, which is adapted during the training. \nThe performance of the proposed approach is evaluated on several MuJoCo continuous control tasks, as well as compared to state-of-the-art QD benchmarks.\n", "summary_of_the_review": "- Interesting approach to maintaining the policy clusters and adapting the objective function\n- Needs to improve the context in the literature, w.r.t. the use of diversity of behaviours\n- An ablation study to show the contribution of the MAB for objective function adaptation, would be beneficial\n\nEDIT: I have increased my Empirical Novelty And Significance score, and conditioned on the additional results added to the camera ready I would be willing to increase my recommendation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a novel quality-diversity algorithm, "Evolutionary Diversity Optimization with Clustering-based Selection (EDO-CS)", and applies it to reinforcement learning. A bandit approach (UCB) is used to select which cluster to sample parents from. The QD algorithm can be evaluated on its own, outside of the RL context, and if so it should be compared to the several approaches to niching and other standard diversity preservation approaches in evolutionary computation that rely on clustering. (And the authors should make an effort to connect to the niching literature in particular.) However, the use of the algorithm for RL makes it possible to use behavioral features as the space in which to cluster, separating it from standard diversity preservation methods. The resulting algorithm is relatively simple and the empirical results are good.

Some of the main concerns for reviewers included the bibliography, which the authors promptly acted on by citing several suggested papers and comparing their approach where relevant. There was also discussion about the exact novelty of the paper, for example as compared to the CVT-MAP-Elites algorithm, but this was clarified by the authors. Reviewers agree that the paper is easily to follow and well-written.

Based on this, it seems that the paper makes a clear contribution to QD methods for RL, and is worth accepting.
Decision: Accept (Poster)