Sample-Efficient Quality-Diversity by Cooperative Coevolution
Authors: Ke Xue
Ren-Jian Wang
Pengyi Li
Dong Li
Jianye HAO
Chao Qian
Venue: ICLR 2024 spotlight (2024)
Keywords: Quality-Diversity
Reinforcement Learning
Evolutionary Algorithms
Primary area: reinforcement learning

Abstract: Quality-Diversity (QD) algorithms, as a subset of evolutionary algorithms, have emerged as a powerful optimization paradigm with the aim of generating a set of high-quality and diverse solutions. Although QD has demonstrated competitive performance in reinforcement learning, its low sample efficiency remains a significant impediment for real-world applications. Recent research has primarily focused on augmenting sample efficiency by refining selection and variation operators of QD. However, one of the less considered yet crucial factors is the inherently large-scale issue of the QD optimization problem. In this paper, we propose a novel Cooperative Coevolution QD (CCQD) framework, which decomposes a policy network naturally into two types of layers, corresponding to representation and decision respectively, and thus simplifies the problem significantly. The resulting two (representation and decision) subpopulations are coevolved cooperatively. CCQD can be implemented with different selection and variation operators. Experiments on several popular tasks within the QDAX suite demonstrate that an instantiation of CCQD achieves approximately a 200% improvement in sample efficiency.

Published as a conference paper at ICLR 2024
SAMPLE-EFFICIENT QUALITY-DIVERSITY BY COOPERATIVE COEVOLUTION
Ke Xue!.a Ren-Jian Wang 1 Pengyi Li,, Dong Li Jianye Hao Chao Qian 1.2f
1 National Key Laboratory for Novel Software Technology, Nanjing University, China
2 School of Artificial Intelligence, Nanjing University, China
3 School of Computing and Intelligence, Tianjin University, China
4 Huawei Noah's ' Ark Lab, China
ABSTRACT
Quality-Divern (QD) algorithms, as subset of evolutionary algorithms,, have emerged as a powerful optimization paradigm with the aim of generating a of high-quality and diverse solutions. Although QD has demonstrated competitive per- formance in reinforcement learning, its low sample efficiency remains a significant impediment for real-world applications. Recent research has primarily focused on augmenting sample efficiency by refining the selection and variation operators of QD. However, one of the less considered yet crucial factors is the inherently large-scale issue of the QD optimization problem. In this paper, we propose novel Cooperative Coevolution QD (CCQD) framework, which decomposes a policy network naturally into two types of layers, corresponding to representation and de- cision respectively, and thus simplifies the problem significantly. The resulting two (representation and decision) sub-populations are coevolved cooperatively. CCQD can be implemented with different selection and variation operators. Experiments on several popular tasks within the QDax suite demonstrate that an instantiation of CCQD achieves approximately a 200% improvement in sample efficiency. Our code is available at antttps:: // thub. com http//amaaa-aa bbo/CCCD
INTRODUCTION
Generating a diverse and high-quality set of solutions is of paramount importance across wide
range of tasks, including Reinforcement Learning (RL) (Conti et al. 2018
Eysenbach et al. 2018
Parker-Holder et al., 2020). combinatorial optimization (Do et al. 2022
Nikfarjam et al. (022).
robotics (Cully et al. 2015) Salehi et al., 2022), and human-Al coordination (Lupu et al. 2021
Cui et al. [..11)
Diveist-iiversity (QD) algorithms (Cully & Demiris,
2018 Chatzilygeroudis
| which are a subset of Evolutionary Algorithms (EAs) (Back 1996), have emerged as
a potent optimization paradigm for this challenging task. Specifically, QD algorithm maintains solution set (i.e., archive), and iteratively performs the following procedure: selecting subset of parent solutions from the archive, applying variation operators (c.g., crossover and mutation) to produce offspring solutions, and finally using these offspring solutions update the archive. The impressive performance of QD) algorithms has been showcased in various RL. tasks, such as
exploration (Ecoffet et al.) 202T Miao et al.) 2022), robust training (Kumar et al.) 2020 Tylkin et al.)
2021 Yuan et al. 2023b). environment generation (Fontaine et al.) 2021 Bhatt et al.
2022|
al. 2023), open-ended learning (Standish 2003 Soros & Stanley 2014 Yuan et al.
2023a) elc.
Though able to achieve a diverse set of high-quality solutions, the sample efficiency of QD algorithms not satisfactory (Chalumeau et al., 2023a). This issue can be alleviated by their high parallelization capabilities (Lim et al. 2023a), but remains a significant drawback, especially for applications with expensive evaluation. For example, each evaluation entails a substantial computational cost in environment generation (Dennis et al.) 2020): Parker- et al., 2022), making that the QD algorithm must resort to techniques such as surrogate models (Bhatt et al. [0222] Lim et al.) 2022
Bhatt et al. 2023) to curtail computational costs. Recent research has tried to improve sample
Equal contribution
Corresponnence Chao Qian <qqinc@nju.edu.ccom

---

Published as a conference paper at ICLR 2024
efficiency from the algorithmic perspective of QD, such as refining selection (Cully & Demiris 2018
Sfikas et a 2021; Wang et al. 2022; 2023a) and variation (Nilsson & Cully, 2021 1 Tjanaka et al.
2022
Pierrot et al. 2022a Faldor et a. 2023 Batra et al. 2024) operators.
The optimization problem of QD is indeed challenging. Typically, QD requires obtaining many solutions (e.g.. 1024), and it is desirable for these solutions to be of high quality and diverse. What is even more challenging is that the dimensionality of solutions is usually very high. For example, when QD is applied to RL tasks (i.e.. QD-RL, which what we considered in this paper), solution (e.g., three-layer policy network) can involve tens of thousands of parameters (Chalumeau et al. 2023a]. In this paper, we emphasize that one reason for the low sample efficiency of QD algorithm is the excessively large optimization space: optimizing complex single solution while simultaneously maintaining thousands of such solutions. If we can simplify the optimization problem of QD, its sample efficiency will be improved.
Fortunately, we observe that the solutions of QD problem do not need be completely different to achieve diversity. In QD-RL, if we can decompose the policy network and share some parts, then some common and useful knowledge can be shared, thus the optimization problem of QD will be greatly simplified. However, it is non-trivial to achieve this. Firstly, How to decompose the policy network is an important question. Besides, sharing too many parts (i.c., too many solutions share too many layers) can hinder diversity, which deviates from the goal of QD. Thus, another critical question is How to balance the problem simplification and diversity maintenance?
To address the issues raised above, we propose novel framework called Cooperative Coevolution QD (CCQD), which is based on Cooperative Coevolution (Potter & Jong 2000) and follows the divide- and-conquer approach. To the best of our knowledge, though many CCEAs have been proposed before (Ma et al., (019). how to apply CC to simplify the optimization problem of QD has not been fully explored. particularly the design of decomposition strategy, which plays a critical role in CC (Omidvar et al. [0)44]b). Thanks to recent research, which has demonstrated the distinct functions of different layers of neural networks (Chung et al., 2019; Dabney et al., [00T Zhou 2021 Hao et al. 2023 Li et al., 2023): the front layers are used for state representation, while the following layers are used for decision-making. For example, ERL-Re² (Hao et al. 2023) achieves efficient knowledge sharing within the population by decomposing the policy network into shared state representations and independent linear representations. Building on this observation, CCQD decomposes each policy network in the population into two types of layers, a representation part and a decision part, resulting in two corresponding sub-populations, which are then coevolved cooperatively. Compared with the decision part, which is required to have diverse behaviors in the context of QD, the representation part contains a significant amount of common and shareable knowledge (Hao et al., 2023). Thus, we employ representation population size that is much smaller than the decision population size, e.g., 20 vs. 1024, in our experiments. This will yield two benefits: 1) it further simplifies the problem while still maintaining a certain degree of diversity, and 2) the representation population can naturally contain more critics (as opposed to single critiq employed in many studies (Nilsson & Cully [02T]] Flageat et al., 2023a| Pierrot et al., 2022a] Tajaaka et al., 2022)). thus alleviating the bias in off- updating. Additionally, Policy-extended Value Function Approximator (PeVFA) (Tang et al. 2022) is used as the critic, which can provide better value function approximation.
Our proposed framework CCQD is general, which can be implemented with different parent selection, variation, and survivor selection operators. We provide an instantiation of CCQD using uniform parent selection, IsoLineDD and policy gradient variation, and vanilla archive-based survivor selection. We mainly conduct experiments on the popular QDax suite (Lim et al. 2023a] Chalumeau et al. 2023b), including unidirectional, ommidirectional, and mazee-type environments. These tasks are commonly used in QD-RL research (Tjanaka al., 2022 Chalumeau et al. 2023a) and provide challenging benchmark for evaluating the performance of CCQD. The results demonstrate that CCQD outperforms
the bascline method (Mouret & Clune| 2015) and several state-of -ote----th-errr the-art methods (Nilsson & Cully 2021 Tjanaka et al.) |022) Pierrot et al. 2022a Pierrot & Flajolet| (202)) in terms of many important QD metries (c.g., QD-Score). We also demonstrate the versatility of CCQD by the experiments on Atari Pong (Bellemare et al. (013). The effectiveness of CCQD is further verified by ablation studies, hyper-parameter sensitivity analysis, and the illustration of the archive.
In our paper, for the sake of convenience, we group all the critic networks of a policy gradient algorithm (such the four critic networks in TD3) together and refer to them a single critic.
2

---

Published as a conference paper at ICLR 2024
2 BACKGROUND
2.1 QUALITY-DIVERSITY
QD algorithms (Cully & Demiris 2018 Chatzilygeroudis et al., 2021) aim to discover diverse set of high-quality solutions for a given problem. Let X represent the solution space, and S f R denote the k-dimensional descriptor space. The objective of QD algorithms is to maximize fitness (quality) function f X - IR while exploring the k-dimensional descriptor space S using a behavior descriptor function m: X S. Taking the widely recognized QD algorithm, MAP-Elites (ME) (Cully et al., 2013 Mouret & Clune 2015). as an example, it maintains an archive by discretizing the descriptor space into M cells } and storing at most one solution in each cell. The main steps of ME involve selecting parent solutions from the archive, generating offspring solutions through variation operators, evaluating the offspring solutions, and updating the archive (i.e., survivor selection). A detailed algorithmic description of ME can be found in Appendix A ME aims to fill the cells with high-qualing solutions, thereby formalizing the objective as maximizing the QD-Score, denoted as En fxzz), where z; represents the solution contained within the cell S, i.c., m(x;;) E S. If a cell S; does not contain solution æ; then / (2:; is considered as O. For simplicity, the fitness value f()) is assumed (or converted) to be non-negative to prevent the QD-Score from decreasing.
Recently, many works investigate the use of QD in complex scenarios, broadening the application scenario of QD algorithms. Uncertain QD (Grillotii et al. 2023 Flageat & Cully] 2023] Flageat et al. 20236 takes the uncertainty of the evaluation process into account and improves the reproducibility of the archive. The Quality-Diversiti Transformer (QDT) (Macé et al.) (023) compresses an entire archive into a single behavior- conevioo-coddiiioinng policy, which can be used for many downstream applica- tions. Multi- Multi-OOjective QD (MOQD) (Pierrot et al., (022b) extends QD to solve the multi-objective optimization problems that need diversity. Quality- -Smmilr Diversity (QSD) (Wu et al.) 2023) consid- ers generating set of diverse policies at multiple quality levels, which can be used for curriculum learning (Narvekar et al. 2020) where the environment gradually increases curriculum levels from simple to complex. Recent studies (Wang et al.) 2023b Ding al., 2023) learn the behaviors from human feedback, addressing the difficulty of diversity definition in many applications.
2.2 REINFORCHMENT LEARNING
Consider a Markov decision process (MDP), defined by a tuple (S,A,P,R. 7; 7). At each time-step t, the agent uses a policy To to select an action a, ~ Te (5t) E A according to the state s, S, the environment transits to the next state 8++1 according to transition function P(st, at), and the agent receives a reward r, = R(s,, a.). The return is defined as the discounted cumulative reward, denoted by Rr = E. 7*T, where E [0, 1) is the discount factor and T is the maximum episode horizon. The goal of RL is learn optimal policy nr that maximizes the expected return. Meanwhile, in many complex RL. tasks such as robust training (Kumar et al.) 2020) Tylkin et al.) (202)), the goal is more challenging, requiring to find set of diverse policies with high expected returns. QD has been successfully applied to these tasks, where the solution æ and fitness f in QD correspond to the policy To and episode return Rr in RL, respectively.
Among different policy optimization algorithms, Deep Deterministic Policy Gradient (DDPG) Lilli crap et al. (016)) is representative off- off-policy Actor-Critic algorithm, consisting of policy to (i.e.. the actor) and a state-action value function approximation QΦ (i.c., the critic), with the parameters and &b respectively. The critic optimized with the temporal difference loss (Sutton Barto 2018), and the actor is updated by maximizing the estimated Q value. The loss functions are defined as: [(v) = Ep [r + 2 Te (s')) - 2w (s, a))²] and L(0) = - [ (s, (T)s))], where the experiences (s, a, r.s') are sampled from the replay buffer D. ob' and 0' are the parameters of the target networks. Twin Delayed DDPG (TD3) (Fujimoto et al. 2018)) improves DDPG by addressing overestimation issue mainly by clipped double-Q learning, leading to significant improvement as
variation operator in QD-RL (Nilsson& & Cully] 2021: Flageat et al. 2023a Wang et al. 2022 Lim
et al. 2023b Pierrot et al. 2022a Pierrot & Flajolet 2023 ?).
3

---

Published as a conference paper at ICLR 2024
2.3 SAMPLE- EFFIICEET QD
One drawback of QD is the low sample efficiency (Chalumeau et al. 2023a; Li et al. 2024). Here, we briefly introduce the recent works on improving the sample efficiency of QD, which be mainly divided into two categories according to the improved components of QD (Cully & Demiris 2018):
how to select parent solutions from the archive (i.e., parent selection) (Cully & Deminis 2018 Sfikas
et al. 2021 Wang ct al., 2022, 2023a). and how to update them (i.c., variation) (Colas et al. 2020
Fontaine et al. [020] Nilsson & Cully) 2021 Tjanaka al. 2022 Pierrot et al. 2022a Flageat et 2023a). A detailed related work is provided in Appendix A.2 due to space limitation.
2.4 COOPERATIVE CORVOLUTION
Cooperative coevolution (CC) (Potter& Jong 2000 has been shown suitable for large-scale optimiza- tion (Ma et al., (019). It uses divide-and-conque approach to decompose a large-scale problem into several small-scale sub-components and evolves these sub-components cooperatively. Each sub-component corresponds to sub-population in the coevolutionary process. The key factor of cooperative coevolution is the decomposition strategy, which decides how to decompose a solution of the problem to be solved, and will largely influence the performance. Cooperative cocvolution has been successfully applied to multiple complex tasks, e.g., POET (Wang et al. 2019 (2020) coevolves the agents and the environments, MAZE (Xue et al.) 2022) coevolves the agents and the partners in zero-shot human-Al coordination, CCEP (Shang et al. (022), coevolves the filters for network pruning, and CCNCS (Yang et al.] 2022 coevolves different agents by random grouping. The problem to be solved by QD is usually large-scale, c.g., the number of parameters of a three-layer policy network in RL can be tens of thousands (Chalumeau et al. 2023a] Tjanaka al., 2022). In this work, we apply CC to simplify the optimization problem of QD for the first time, and employ natural and efficient layer- based decomposition strategy. Different from CCNCS, CCQD considers the characteristics of QD and policy networks, using layer-based decomposition strategy to divide the policy network into two parts with different functions, and maintains fewer representation parts.
CCQD METHOD
In this section, we introduce the proposed CCQD framework. We first give an overview of CCQD. Then, we introduce the decomposition strategy and the coevolution process of CCQD in Section 3.1 and Section 3.2. respectively. As shown in Figure 3 CCQD follows the main process of QD: parent selection, variation, evaluation, and survivor selection. The main difference between CCQD and QD algorithms is that CCQD decomposes each policy into two parts representation part and decision part- - and maintains two sub-populations that are cooperatively coevolved. The detailed algorithm process of CCQD is provided in Appendix A
3.1 DECOMPOSITION
The main idea behind CCQD is to apply the divide-and-comd -onuucuuuuurr technique of cooperative coevolution to QD. Although cooperative coevolution has achieved impressive success in large-scale optimization, it has been reported that it may lead to poor performance in non-separable problems an appropriate decomposition strategy is not employed (Ma et al. 2019). CCQD utilizes the specific characteristics of the policy network for the non-trivial separation issue of cooperative coevolution. Considering the observation that different layers of the neural network have different functions (Chung al. 2019) Dabney et al. 202T: Zhou 2021 Hao et al., 2023), a natural decomposition strategy is to decompose the search space of policy network by layer. In particular, a policy network divided into two parts, where several front layers of the policy network are considered as the representation part, while the following layers are used as the decision part. For each part to be optimized, CCQD maintains one sub- -oppouuattion. Each solution in sub-population represents the corresponding part of a policy network. The two sub-populations are cooperatively coevolved through parent selection, variation, evaluation, and survivor selection, which will be explained in detail in Section 3.2
To achieve a diverse set of quglity solutions, a large population size is usually required. However, considering that the representation part contains significant amount of common and shareable information compared to the decision part (Zhou) 2021 Hao et al. 2023). which requires diverse be- haviors, a large size for both sub-populations is not necessary. Thus, CCQD employs a representation
4

---

Published as a conference paper at ICLR 2024
Survivor Selection
Representation Archive
Decision Archive
Logoo
o
Parent Selection
Lvaluation
Variation
Policy
Policy Gradient
Assistant
Critic
Replay buffer
N,
Figure 1: Illustration of the CCQD method, where CCQD decomposes a policy network into the representation and decision parts, and coevolves the two corresponding sub-poptn populatiulln through four sub-processes, i.e., parent selection, variation, evaluation, and survivor selection.
cub-population whose size is much smaller than that of decision sub- cobb-poulation, e.g., 20 vs. 1024 our experiments. Using small representation sub-population further simplifies the optimization problem of QD, which also allows CCQD to use more critics naturally and thus alleviates the bias in off-policy updating. This will be further explained in the Variation part of Section 3.2
3.2 COEVOLUTION
The two cob-populations of CCQD have two different types of archives: a list-based archive for the representation part and grid-based archive for the decision part. In the following, we will give concrete implementation of CCQD by adopting specific parent selection, variation and survivor selection mechanisms, which is sufficient to achieve superior performance, as will be demonstrated in Section 4 But the CCQD framework itself is versatile, which can be combined with various existing QD techniques. Improving certain components of our implementation may lead to better performance, which will be studied in our future work.
Parent Selection. At each generation, employ the uniform random selection strategy commonly used in QD, to choose set of suitable parts (solutions) from the decision archive. Then, each selected decision part randomly selects representation part from the representation archive obtain a complete policy. Note that different decision parts may select the same representation part due to the reduced representation population size. This process ensures that the representation and decision parts are combined in a diverse manner.
Variation. We use the variation operator in PGA-ME (Nilsson & Cully) 2021 Flageat et al. 2023a) as our basic variation operator, i.e., one-half the parent solutions updated with the traditional evolutionary operator IsoLineDDD and the other half is updated with TD3. The TD3 operator focuses on optimizing quality, while the IsoLineDD operator used to promote diversity. Note that there two key differences in the usage of TD3 between CCQD and PGA-ME. I) Each representation part CCQD has its own critic, while PGA-ME only employs a single critic for all the policies in the population, leading to imprecise value function approximation and ultimately hindering sample efficiency (Hao et al. 2023). Thanks to the population size for the representation part being relatively naturally maintain critic for each representation part,
small (e.g., 20 in experiment),

---

Published as a conference paper at ICLR 2024
which allows to alleviate the bias in off-policy updating and improve sample efficiency. 2) We use PeVFA (Tang et al. 2022) as our critic, which preserves the values of multiple policies. Concretely, given some representation embedding X of policy input additionally, i.e., Q (8. Xx, Through the explicit policy representation Xx. PeVFA provides better value generalization among policies, making it suitable for CCQD, where each representation part will be combined with multiple decision parts.
PeVFA parameterized by &b takes Xx as
Survivor Selection. After generating and evaluating the offspring policies. CCQD updates the representation archive and decision archive by survivor selection. We use the survivor selection strategy of vanilla QD (Mouret & Clune 2013) for the decision archive. That is, each offspring solution (decision part) is placed in its corresponding cell in the behavior space according to its behavior. If the cell is empty, the solution is kept directly; otherwise, the one with a higher quality between this solution and the solution occupying the cell is kept. Note that the complete policy network is saved in the decision archive, but only its decision part is selected by parent selection. When CCQD terminates, the output is directly the decision archive.
For the survivor selection of the representation archive, we use the simplest approach, which directly replaces a representation part that has been selected in parent selection by the updated one. After that, we check each part in the representation archive. If no solutions in the current decision archive associated with a particular representation part, we replace that representation part with the one that is associated with the most solutions in the decision archive.
4 EXPERIMENT
To examine the performance of CCQD, we conduct experiments on the popular QDax suite" [im ct al., 2023a Chalumeau al., 2023b), including unidirectional tasks (i.e., Uni), omnidirectional tasks (i.e., Omni), and Maze-type environments. The Uni tasks aim to generate a set of policies that move forward as fast as possible and are diverse in the frequency of the usage of each foot, where the reward is mainly determined by the forward speed of the robot, and the behavior descriptor is defined as the fraction of time each foot touches the ground. The Omni tasks aim to generate a set of policies that move to different directions while consuming as few energy as possible, where the reward defined as the opposite of the energy consumption, and the descriptor is defined as the final position of the robot. The Maze tasks aim to train the point robot to reach specific target position in a maze, where the reward is defined as the opposite of the distance between the current position and the target position, and the behavior descriptor is defined as the final position of the agents. We mainly consider the following evaluation metrics: 1) QD-Score: The total sum of fitness values across all solutions in the archive. It reflects both the quality and diversity of the solutions, and is the most important metric to evaluate a QD algorithm (Pugh et al.) 2016 Cully & Demiris) 2018); 2) Coverage: The total number of solutions in the archive. It can measure the exploration ability of QD algorithm; 3) Max Fitness: The largest fitness value of solutions in the archive. It can measure the exploitation ability of QD algorithm; 4) QD-Score AUC (Tjanaka al. (022): The area under the QD-Score curve. It measures the optimization efficiency of a QD algorithm.
To evaluate the effectiveness of CCQD, we compare it against the baseline method ME (Mouret & Clune) 2015), as well as four state-of-ud of-the-araaaa art approaches: PGA-ME (Nilsson & Cully 2021 Flageat et al. (023a)), QD-PG (Pierrot et al., 2022a), OMG-MEGA (Tjanaka et al., 2022). and PBT-
ME (Pierrot & Flajolet 2023). Detailed explanations of these methods are provided in Appendix B. We use the CVT-ME archive /Vassiliades et al.) 2018) to store solutions, which surpasses the vanilla grid-based ME approach on numerous tasks, particularly in the context of nigh-diimnsional behavior space (Pierrot et al. 2022a Pierrot & Flajolet 2023). In our experiments, a policy is represented by a three-layer neural network, and CCQD uses the first layer as the representation part and the remaining two layers as the decision part. The size of representation archive is 20, and the decision archive CVT-ME with size 1024. The representation embedding Xxr of PeVTA used by CCQD relies on the parameter vector of the last layer of the decision part. All the methods are trained with a total budget of 1.5e8 environment time-steps. The episode length is 250, which is consistent with previous works (Chalumeau et al. 2023a b). The number of cells in the archive is 1024, and the number of generated offspring solutions each generation is 100, except for PBT-ME, whose number is 320
httpps://gii http:///gttttubboo
ve- ioree-nnneei inte iiginntttnnn iegentrrrotttt /Qnax

---

Published as a conference paper at ICLR 2024
Table I: QD-Score AUC (x1012) of different methods on eight environments with episode length 250 and total timesteps 1.5e8. The symbols '+', '-', and 'Re' indicate that the result is significantly superior to, inferior to, and almost equivalent to CCQD, respectively, according to the Wilcoxon rank-sum with significance level 0.05. Bold and underline texts respectively denote the best and runner-up up algorithms.
Environment
ME
QD-PG
PGA-ME
OMG-MEGA
PBT-ME
CCQD
Hopper Uni
84.17
75.20
93.25
91.47
81.32
96.75
Walker2D Uni
102.73
103.36
109.56
110.23
85.20
116.83
HalfCheetah Uni
343.79
323.44
388.24
392.61
425.16 =
432.83
Ant Uni
121.16
131.10
131.90
135.98
121.89
141.27
Humanoid Uni
119.36
125.09
116.36
117.43
97.61
132.51
Humanoid Omni
0.90
1.45
1.40
1.07
1.22
2.65
Point Maze
43.90
42.74
35.09
34.63
35.01
52.73
Ant Maze
105.90
164.94
141.64
146.46
132.47 - 157.03
+/-/~ Average Rank
0/8/0
0/7/1
0/8/0
0/7/1
0/7/1
4.62
3.50
3.50
3.50
4.75
1.12
to be consistent with the original paper. For a fair comparison, all the methods use uniform parent selection. We report the median and the first and third quartile intervals across five identical seeds (1000, 2000, .... 5000) for all algorithms Maze, we use ten seeds (1000, 2000, 10000) because of the high randommess and difficulties in these environments. Detailed settings of experiments provided in Appendix B.2
most tasks. For Hopper Uni Humanoid Onni, and Ant
QD-Score AUC.
We first use the QD- AUC to compare the optimization efficiency of different methods, as shown in Table I By the Wilcoxon rank-sum test with significance level 0.05, CCQD significantly better than almost any other methods on any of the eight environments, and has the best average rank. The three state-of-the-art methods, i.e., QD-PG, PGA-ME, and OMG-MEGA, outperform ME and PBT-ME (in average rank), and perform the runner-up multiple times.
Other metrics. We then plot the QD-Scores, Coverage, and Max Fitness curves for different algorithms, allowing for a more comprehensive evaluation. As shown in Figure 2 CCQD has the best QD-Score across all environments except for Ant Maze. PBT-ME achieves the highest Max Fitness on Ant Uni and Ant Maze, but its poor Coverage results in low QD-Score in these two environments. CCQD also exhibits advantages in both Max Fitness and Coverage in most environments, demonstrating its excellent performance. We also compare the average rank of Max Fitness. As shown in Table 9 CCQD achieves the highest average rank, and PBT-ME the runner-up. In addition, we also compare the methods in the environments with episode length 1000. which is also a common setting QDRI., as shown in Table
g Table TO and Figure TT In this setting, CCQD) still has the best average rank on QD-Score AUC and Max Fitness. We also consider archive profile and corrected metrics (Flageat et al. 2023b), as shown in Appendix C.2 and C.3
respectively.
Ablation Studies. We first examine the setting of our decomposition strategy, i.c., how many front layers are used as the representation part. We use a three-layer policy network, and thus have two options: 1 and 2, denoted as (1+2) and (2+1), respectively. Figure (3 shows that different settings can both significantly improve the sample efficiency, thereby validating the robustness of our decomposition strategy. However, for some complex problems, may be necessary to allocate the proportion of representation and decision makinn carefully. We also test CCQD with fixed paring in parent selection and that without checking in survivor selection of the representation archive. Note that our CCQD implementation uses random paring and also checks whether representation part is associated with some decision part in the decision archive. Figure 3(b) shows the effectiveness of these employed strategies. Additional studies number of representation population size, number C.5 and C.6) respectively.
of critics, and VFA are provided in Appendix C.4
Archive Visualization. An interesting question concerning CCQD is whether different representa- tion parts truly distinguish different behaviors. To investigate this question, plot the representation
7

---

Published as a conference paper at ICLR 2024
105
Hopper
1d5
166
105
3.3
0L5
2.5
0.6
Time Stope
Thnx Stepe
Time Stepe
Time Stope
50
50-
20
25-
Titee Supe
Tiae Sxpss
Titx Supo
Tiane Suge
2.0
1.0
Max D1500
1.5
1.5
0.5
1.0
0.5
0.5
0.4
0.5
Steps
Supe
Stepe
Stope
ME
QD-PG
PGA-ME
OMGGMGGA
PATME
0C0D
1.05
1lamanoid
164
1lumanoid
165
Leb
3.0
1.5
Tixe Sups
Tax Stepa
Tine Siggr
Time Sage
75
42
50
25-
Time Staps
Steps
Steps
Stope
1.5
1.0
-0.5
0.6
-1.0
0.6
1.5
0.4
-2.0
1.5
105
165
Lel
MB
09.NN
PCA
CMG MEGGA
PRIME
COOD
Figure 2: Performance comparison of CCQD with other methods in terms of QD-Score, Coverage, and Max Fitness on eight environments with episode length 250 and total timesteps 1.5e8. The medians and the first and third quartile intervals are depicted with curves and shaded areas, respectively.
part associated with each solution in the decision archive, where different representation parts are displayed using distinct colors. As illustrated Figure (a)-(b), solutions associated with the same representation part tend have similar behavior descriptor values and often located in nearby cells the decision archive. Note that the colors in (a) represent the quality, while the colors in (b) represent the different representation parts. This finding suggests that different representation parts can recognize diverse state representations and discover various behaviors, which may explain the effectiveness of CCQD, Additional visualization results are provided in Appendix C.7
Experiments on Atari Pong. To investigate the versatility of our framework, we conduct an experiment on video game Atari Pong (Bellemare et al. 2013), which is widely used benchmark. The state space is an image space whose dimension is about 100 times larger than that of QDax environments. We use DQN as variation operator and the corresponding variant of PGA-ME is DQN- ME. The policy network is changed to a DQN with three convolutional layers and two fully connected layers. We still
layer-based decomposition strategies. We consider that the representation
8

---

Published as a conference paper at ICLR 2024
1.5
105
Peint
165
Time Stepa
1:7
Time Supp
1e
Time Stepe
18
11me Stepe
167
(a) Decomposition strategy
Parent selection and survivor selection
Figure 3: (a) Analysis of decomposition strategy, where (I+2) denotes the representation part and decision part have and 2 layers, respectively. (b) Ablation studies on parent and survivor selection.
ld
00.5.00
60
Thme Stege
3d7
DON-ME CCQO
COOD: (3+2)
(+3)
COOD (+
(b) Representation part in the decision archive.
(d) GradCAM Visualization
(a) Decision archive
(c) Atari Pong
Figure (a) The decision archive in Humanoid Uni. (b) The representation parts associated with each decision part in the decision archive in Humanoid Uni. (c) Performance comparison Atari Pong- (d) GradCAM analysis of the representation part.
part has and 4 layers, denoted as (2+3), (3+2), and (4+1), respectively. The detailed settings are provided in Appendix [.]]] As depicted in Figure various configurations of CCQD consistently outperform DQN-ME, illustrating the versatility of the CCQD framework and its applicability to diverse tasks and network structures. Note that the number of parameters of Atari Pong (1.6 million) much larger than that of Humanoid Uni (0.1 million). On this difficult task, our CCQD significantly outperforms QD. Furthermore, the representation part learn in this video task, as shown in Figure (d). We can find that the
GradCAM (Selvaraju et al. 2017) to investigate what does
representation part focuses the position of the ball and agents, which helpful to finish the task.
5 CONCLUSION
This paper introduces the CCQD framework, which addresses the inherent large-scale challenge of QD by leveraging cooperative coevolution for the first time. Notably, CCQD is compatible with and can be combined with various existing QD techniques, such as parent selection, variation, and survivor selection. The simple implementation of CCQD presented in this paper has demonstrated impressive performance in multiple tasks, significantly improving sample efficiency. Exploring and employing better components could potentially lead further improvements. and would be an interesting avenue for future work. Additionally, the shared representation components in CCQD offer the potential for reducing the storage overhead of QD algorithms. In some computationallyyccnstter application tasks, combining the CCQD framework with archive distillation techniques (Macé et al.) 2023) can reduce computational costs and achieve a sample and storage-efficient QD algorithm, which is an aspect we will investigate in future research. It would also interesting to investigate the trained decision policies can be used as a robust sub-policy and be applied into other tasks, because they trained on variety of representations. One limitation of this paper is that only demonstrate the effectiveness of CCQD through empirical studies, without delving into its properties from theoretical perspective (Panait al. 2008 Qian al. 2024), which is also crucial.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We thank the anonymous reviewers for their insightful and valuable comments. We thank Li-He Li for helping drawing the workflow figure. This work was supported by the National Science and Technology Major Project 20222D0116600 and National Science Foundation of China (62276124).
REFERENCES
Thomas Bäck. Evolutionary Algorithus in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, 1996.
Sumeet Batra, Bryon Tjanaka, Matthew Christopher Fontaine, Aleksei Petrenko, Stefanos Nikolaidis, and Gaurav S. Sukhatme. Proximal policy gradient arborescence for quality diversity reinforcement learning. In The 12th International Conference Learning Representations (ICLR), Vienna, Austria, 2024.
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013.
Varun Bhatt, Bryon Tjanaka, Matthew C. Fontaine, and Stefanos Nikolaidis. Deep surrogate assisted generation of environments. In Advances in Neural Information P Processing Systems 35 (NeurIPS), New Orleans. LA, 2022.
Varun Bhatt, Heramb Nemlekar, Matthew C. Hsu, and Stefanos Nikolaidis. Surrogate assisted generation of human-robot interaction scenarios. DrXiv:2304.13758 2023.
Fontaine, Bryon Tjanaka, Hejia Zhang, Ya-Chuan
Felix Chalumeau, Raphael Boige, Bryan Lim, Valentin Macé, Maxime Allard, Arthur Flajolet, Antoine Cully, and Thomas Pierrot. Neuroevolution is competitive alternative to reinforcement learning for skill discovery. In The 11th International Conference on Learning Representations (ICLR), Kigali, Rwanda, 2023a.
Felix Chalumeau, Bryan Lim, Raphael Boige, Maxime Allard, Luca Grillotti, Manon Flageat, Valentin Macé, Arthur Flajolet, Thomas Pierrot, and Antoine Cully. QDax: A library for quality-diversity and population-based algorithms with hardware acceleration. arXiv:2308.. 03665, 2023b.
Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean-Baptiste Mouret. Quality-diversity optimization: A novel branch of stochastic optimization. In Black Box Op- timization, Machine Learming, and No-Free Lunch Theorems, pp. 109-135. Springer, 2021.
Wesley Chung, Somjit Nath, Ajin Joseph, and Martha White. Two-timescale networks for nonlinear value function approximation. In The 7th International Conference on Learning Representations (ICLR), New Orleans, LA, 2019.
Cédric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune. Scaling MAP-Elites to deep neu- roevolution. In Proceedings of the 22th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 67-75, Cancún, Mexico, 2020.
Edoardo Conti, Vashisht Madhavan, Felipe P. Such, Lehman, Kenneth O. Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via population of novelty-seeking agents. In Advances in Neural Information Processing Systems 32 (NeurIPS), pp. 4032-5043. Montréal, Canada, 2018.
Brandon Cui, Hengyuan Hu, Luis Pineda, and Jakob Foerster. K-level reasoning for zero-shot coordination in hanabi. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 8215-8228, Virtual, 2021.
Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular framework. JEEE Transactions on Evolutionary Computation, 22(2):245-259, 2018.
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean- Baptitttttt Mouret. Robots that can adapt like animals. Nature, 52155533)5003-577,, 2015.
10

---

Published as a conference paper at ICLR 2024
Will Dabney, André Barreto, Mark Rowland, Robert Dadashi, John Quan, Mare G Bellemare, and David Silver. The improveeete path: Towards better representations for reinforcement learning. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 7160-7168, Virtual, 2021.
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 13049-13061, Virtual, 2020.
Li Ding, Jenny Zhang, Jeff Clune, Lee Spector, and Joel Lehman. Quality diversity through human feedback. arXiv:2310.12100 2023.
Anh Do. Mingyu Guo, Aneta Neumann, and Frank Neumann. Analysis of evolutionary diver- sity optimization for permutation problems. ACM Transactions on Evolutionary Learning and Optimization, 2(3):1-27, 2022.
Adrien Ecoffet, Joost Huizinga. Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7844):580-5586, 2021.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without reward function. In The 6th International Conference Learning Representations (ICLR), Vancouver, Canada, 2018
Maxence Faldor, Félix Chalumeau, Manon Flageat, and Antoine Cully. MAP-Elites with descriptor- conditioned gradients and archive distillation into a single policy. arXiv:2303.03822 2023.
Manon Flageat and Antoine Cully. Uncertain quality-diversity Evaluation methodology and new methods for quality-diversity in uncertain domains. IEEE Transactions on Evolutionary Computa- tion, 2023.
Manon Flageat, Bryan Lim, Luca Grillotti, Maxime Allard, Simón C Smith, and Antoine Cully. Benchmarking quality- diversy algorithms on neuroevolution for reinforcement learn- ing. arXiv:2211.02193, 2022.
Manon Flageat, Felix Chalumeau, and Antoine Cully. Empirical analysis of PGA-MAP-Elites for neurocvolution in uncertain domains. ACM Transactions on Evolutionary Learning and Optimization, 3(1):1-32, 2023a.
Manon Flageat, Grillotti Luca, and Cully Antoine. Benchmark tasks for quality-diversity applied to uncertain domains. arXiv:2304.12454 2023b.
Matthew C. Fontaine and Stefanos Nikolaidis. Differentiable quality diversity. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 10040-10052, Virtual, 2021.
Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K. Hoover. Covariance matrix adaptation for the rapid illumination of behavior space. In Proceedings of the 22th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 94-102, Cancún, Mexico, 2020.
Matthew C. Fontaine, Ruilin Liu, Ahmed Khalifa, Jignesh Modi, Julian Togelius, Amy K. Hoover, and Stefanos Nikolaidis. Illuminating mario scenes in the latent space of generative adversarial network. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5922 5922-5930, Virtual, 2021.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 1582-1591, Stockholm, Sweden, 2018
Luca Grillotti and Antoine Cully. Unsupervised behavior discovery with quality- optimiza- tion. IEEE Transactions Evolutionary Computation, 26(6):1539-152, 2022.
Luca Grillotti, Manon Flageat, Bryan Lim, and Antoine Cully. Don't 't bet luck alone: Enhancing behavioral reproducibility of quality-diversity solutions in uncertain domains. arXiv:2304.03672.
2023.
11

---

Published as a conference paper at ICLR 2024
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 9(2):199-1955 195, 2001.
Jianye Hao, Pengyi Li, Hongyao Tang, Yan Zheng, Xian Fu, and Zhaopeng Meng. ERL-Re2: Efficient evolutionary reinforcement learning with shared state representation and individual policy representation. In The 11th International Conference on Learning Representations (ICLR), Kigali, Rwanda, 2023.
Saurabh Kumar, Aviral Kumar, Sergey Levine, and Chelsea Finn. One solution is not all you need: Few-shot extrapolation via structured MaxEnt RL. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. $198-8210, Vancouver, Canada, 2020.
Joel Lehman and Kenneth O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 211-218, Dublin, Ireland, 2011.
Pengyi Li, Jianye Hao, Hongyao Tang, Yan Zheng, and Xian Fu. RACE: Improve multi-agent reinforcement learning with representation asymmetry and collaborative evolution. In Proceedings of the 40th International Conference on Machine Learning (ICML), pp. 19490-19503, Honolulu, HI, 2023.
Pengyi Li, Jianye Hao, Hongyao Tang. Xian Fu, Yan Zheng, and Ke Tang. Bridging evolutionary algorithms and reinforcement learning: A comprehensive survey. arXiv:2401.11963, 2024.
Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Frez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In The 4th International Conference on Learning Representations (ICLR), San Juan, PR, 2016.
Bryan Lim, Manon Flageat, and Antoine Cully. Efficient exploration using model-based quality- diversity with gradients. arXiv:2211.126110 2022.
Bryan Lim, Maxime Allard, Luca Grillotti, and Antoine Cully. Accelerated quality-diversity through massive parallelism. Transactions on Machine Learning Research, 2023a.
Bryan Lim, Manon Flageat, and Antoine Cully. Understanding the synergies between and deep reinforcement learning. arXiv:2303.06164 2023b.
Andrei Lupu, Hengyuan Hu, and Jakob Foerster. Trajectory diversity for zero-shot coordination. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 7204-7213 Virtual, 2021.
Xiaoliang Ma, Xiaodong Li, Qingfu Zhang, Ke Tang, Zhengping Liang, Weixin Xie, and Zexuan Zhu. A survey cooperative co-evolutionary algorithms. IEEE Transactions Evolutionary Computation, (263):421-441 2019.
Valentin Macé, Raphaël Boige, Felix Chalumeau, Thomas Pierrot, Guillaume Richard, and Nicolas Perrin-Gilbert The quality-diversity transformer: Generating behavior-come calavioor-oonitionedd trajectories with decision transformers. In Proceedings of the 25th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 1 1229, Lisbon, Portugal, 2023.
Jiay Miao, Tianze Zhou, Kun Shao, Ming Zhou, Weinan Zhang, Jianye Hao, Yong Yu, and Jun Wang. Promoting quality and diversity in population- based reinforcement learning via hierarchical trajectory space exploration. In Proceedings of the 39th IEEE International Conference on Robotics and Automation (ICRA), pp. 7544-7550, Philadelphia, PA, 2022.
Jean -aa-tBa Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv:1504.04909, 2015.
Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. Journal of Machine Learning Research, 21 21(1):7322-7431 2020.
12

---

Published as a conference paper at ICLR 2024
Adel Nikfarjam, Amirhossein Moosavi, Aneta Neumann, and Frank Neumann. Computing high- quality solutions for the patient admission scheduling problem using evolutionary diversity opti- misation. In Proceedings of the 17th International Conference Parallel Problem Solving from Nature (PPSN), pp. 250-264, Dortmund, Germany, 2022.
Olle Nilsson and Antoine Cully. Policy gradient assisted MAP-Elites. In Proceedings of the 23th ACM Genetic and Evolationary Computation Conference (GECCO), pp. 866-875, Lille, France, 2021.
Mohammad Nabi Omidvar, Xiaodong Li, Yi Mei, and Xin Yao. Cooperative co-evolution with differential grouping for large scale optimization. IEEE Transactions on Evolutionary Computation, 18(3):378-38) -033778833--11 2014a.
Mohammad Nabi Omidvar, Yi Mei, and Xiaodong Li. Effective decomposition of large-scale separable continuous functions for cooperative co-evolutionary algorithms. IEEE Congress on Evolutionary Computation (CEC), pp. 1305-1312, Beijing, China, 2014b.
Liviu Panait, Karl Tuyls, and Sean Luke. Theoretical advantages of lenient learners: An evolutionary game theoretic perspective. Journal of Machine Learning Research, 9:423-457, 2008.
Jack Parker-Holder, Aldo Pacchiano, Krzysztof M. Choromanski, and Stephen J. Roberts. Effective diversity in population based reinforcement learning. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 12.1800 18050-18062, Vancouver, Canada, 2020.
Jack Parker-Holder, Minqi Jiang, Michael Dennis, Mikayel Samvelyan. Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Evolving curricula with regret-based environment design. In Proceedings of the 39th International Conference on Machine Learning (ICML), pp. 17473-17498, Baltimore, MD, 2022.
Thomas Pierrot and Arthur Flajolet. Evolving populations of diverse RL agents with MAP-elites. In The 11th International Conference on Learning Representations (ICLR), Kigali, Rwanda, 2023.
Thomas Pierrot, Valentin Macé, Felix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Beguir, Antoine Cully, Olivier Sigaud, and Nicolas Perrin-Gilbers Diversity policy gradient for sample efficient quality-diversity optimization. In Proceedings of the 24th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 1075-1083, Boston, MA, 2022a.
Thomas Pierrot, Guillaume Richard, Karim Beguir, and Antoine Cully. Multi-objective quality diversity optimization. In Proceedings of the 24th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 139-147, Boston, MA, 2022b.
Mitchell A. Potter and Kenneth A. De Jong. Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation, 8(1):1-29) 2000.
Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality Diversity: A new frontier for evolutionary computation. Frontiers Robotics AI, 3:40, 2016.
Chao Qian, Ke Xue, and Ren-Jian Wang. Quality-diversity algorithms can provably be helpful for optimization. arXiv:2401.1033) 2024.
Achkan Salchi, Alexandre Coninx, and Stephane Doncieux. Few-shot quality-diversity optimization. IEEE Robotics and Automation Letters, 7(2):4424 2022.
Tim Salimans, Jonathan Ho, Xi Chen, and llya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. arXiv: net:::0033000.0 2017.
Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-CAM: Visual explanations from deep networks via gradient-based local- ization. In IEEE International Conference on Computer Vision (ICCV), pp. 118-626, Venice, Italy, 2017.
Konstantinos Sfikas, Antonios Liapis, and Georgios N. Yannakakis. Monte carlo elites: quality- diversity selection as a multi-armed bandit problem. In Proceedings of the 23th Genetic and Evolutionary Computation Conference (GECCO), pp. 180-188, Lille, France, 2021.
13

---

Published as a conference paper at ICLR 2024
Haopu Shang, Jia-Liang Wu, Wenjing Hong, and Chao Qian. Neural network pruning by cooperative coevolution. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp. 4814-4820, Vienna, Austria, 2022.
Lisa Soros and Kenneth Stanley. Identifying necessary conditions for open-ended evolution through the artificial life world of chromaria. In Proceedings of Artificial Life Conference, pp. 793-800, 2014.
Russell K. Standish. Open-ended artificial evolution. International Journal of Computational Intelligence and Applications, 3(2):167-175, 2003.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
Hongyao Tang, Zhaopeng Meng, Jianye Hao, Chen Chen, Daniel Graves, Dong Li, Changmin Yu, Hangyu Mao, Wulong Liu, Yaodong Yang, et al. What about inputting policy in value function: Policy representation and policy--xtendee value function approximator. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 8441-8449, Virtual, 2022.
Bryon Tjanaka, Matthew C. Fontaine, Julian Togelius, and Stefanos Nikolaidis. Approximating gradients for differentiable quality diversity in reinforcement learning. In Proceedings of the 24th ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 1102-1111, Boston, MA, 2022.
Paul Tylkin, Goran Radanovic, and David C. Parkes. Learning robust helpful behaviors in two-player cooperative atari environments. In Frank Dignum, Alessio Lomuscio, Ulle Endriss, and Ann Nowé (eds.), Proceedings of the20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Virtual, pp. 1686-1688, Virtual, 2021.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Dale Schuurmans and Michael P. Wellman (eds.), Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp.
Phoenix, AZ, 2016.
Vassiis Vassiliades and Jean- Cann-Bapiiste Mouret. Discovering the clite hypervolume by leveraging interspecies correlation. In Proceedings of the 20th Genetic and Evolutionary Computation Conference (GECCO), pp. 149 155, Kyoto, Japan, 2018
Vassilis Vassiliades, Konstantinos I. Chatzilyyerouddis, and lean-Baptiste Mouret. Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEFE Transactions on Evolutionary Computation, 22(4):623-630, 2018
Ren-Jian Wang, Ke Xue, Haopu Shang, Chao Qian, Haobo Fu, and Qiang Fu. Multi-objective optinization-based selection for quality-diversity by non-surrounded-domine sorting. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp- 4335 4345, Macao, SAR, China, 2023a.
Ren-Jian Wang, Ke Xue, Yutong Wang, Peng Yang, Haobo Fu, Qiang Fu, and Chao Qian. Diversity from human feedback. 1rXiv:2310..00 06648, 2023b.
Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O. Stanley. POET: Open-ended coevolution of environments and their optimized solutions. In Proceedings of the 21st ACM Genetic and Evolutionary Computation Conference (GECCO), pp. 142-151, Prague, Czech Republic, 2019.
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeff Clune, and Kenneth O. Stanley. Enhanced POET: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. In Proceedings of the 37th International Conference on Machine Learning (ICML). pp.
Vienna, Austria, 2020.
Yutong Wang. Ke Xue, and Chao Qian. Evolutionary diversity optimization with clustering based selection for reinforcement learning. In The 10th International Conference on Learning Represen- tations (ICLR), Virtual, 2022.
Jayy Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Dubureq, Minghao Zhang, Yi Su, Hang Su. and Jun Zhu. Tianshou: A highly modularized deep reinforcement learning library. Journal of Machine Learning Research, 23:267:1-267.1 2022.
14

---

Published as a conference paper at ICLR 2024
Shuang Wu, Jian Yao, Haobo Fu, Ye Tian, Chao Qian, Yaodong Yang. QIANG FU, and Yang Wei. Quality-similaa diversity via population based reinforcement learning. In The 11th International Conference Learning Representations (ICLR), 2023.
Ke Xue, Yutong Wang, Lei Yuan, Cong Guan, Chao Qian, and Yang Yu. Heterogeneous multi-agent zero-shot coordination by coevolution. 1rXiv:2208.04957 2022.
Peng Yang, Hu Zhang, Yanglong Yu, Mingjia Li, and Ke Tang. Evolutionary reinforcement learning via cooperative coevolutionary negatively correlated search. Swarm and Evolutionary Computation, 68:100974, 2022.
Lei Yuan, Ziqian Zhang. Lihe Li, Cong Guan, and Yang Yu. A survey of progress cooperative multi-agent reinforcement learning in open environment. arXiv:2312.01058, 2023a.
Lei Yuan, Ziqian Zhang, Ke Xue, Hao Yin. Feng Chen, Cong Guan, Lihe Li, Chao Qian, and Yang Yu. Robust multi-agent coordination via evolutionary generation of auxiliary adversarial attackers. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), Washington, DC, 2023b.
Yulun Zhang, Matthew C. Fontaine, Varun Bhatt, Stefanos Nikolaidis, and Jiaoyang Li. Multi- robot coordination and layout design for automated warchousing. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (ICCAI), pp. 5503-5511, Macao, SAR, China, 2023.
Zhi-Hua Zhou. Why over-paramtterizzaioonn of deep neural networks does overfit? Science China Information Sciences, 64:1-3, 2021.
15

---

Published as a conference paper at ICLR 2024
A
DETAILS OF QD ALGORITHMS
A.1
QD
ME. A detailed algorithm process of ME is provided in Algorithm The main procedure of ME is to iteratively select parent solutions from the archive (i.e., line 6). generate offspring solutions by variation operators (i.e., line 7), evaluate the offspring solutions (i.e., line 9), and update the archive (i.e., survivor selection, line 10).
Algorithm MAP-Elites
Input: number T of total generations, number of selected solutions in each generation
Output: archive A
1: Let A < 1;
2: while t < ' do
3: if { + ---Radolly_Generattttololl/
then
4:
5: else
6:
[ t Parent_Sellectonn(A N); =
7:
[T + Variation((x))))
8:
end if
9:
Evaluation(f#))
10:
A Survivor_Selectionll (-))))
t ++
12: end while
return A
Algorithm 2 Survivor Selection of ME
Input: archive A, solutions {m/) Output: updated archive A
1: for i = 1 N do
2:
j + G-GeeCCelll (eee__Cel__nndee(m(())) Ind)xxm((z)):
3:
if A, is empty or f(A,) < f(T)) then
4:
A x
5:
end if
6:
end for
7: return A
CCQD. The proposed CCQD is a general framework that can be implemented with different components. In this paper, we provide an implementation using the components of PGA-ME, as shown Algorithm At the beginning, the decision archive and the replay buffer are created as empty sets in line 1, and N initial solutions { along with the corresponding N,. representation parts {nā (TR) NN and N, greedy actors {
N- i==1 are randomly generated in line 4. After that, in each generation / (where > 1), CCQD first trains N, critics (Q+) (each parameterized with 0) with TD loss line 6 and the greedy actors (n Fi=1 with policy gradient in line 7. Note that during the process of training crities in line 6, N decision parts { are randomly selected from the archive A in each iteration to calculate the TD loss. Then, N decision parts [mP],N Ji=1
N.
selected from the archive in line 8, and each of them is combined with a representation part in the representation RyN
archive (Λ. T==1- leading to N complete policies in line 9. The two parts are updated with their corresponding variation operators line 10 and line 11, respectively. After evaluating the generated N
offspring solutions { in line 13, we get the fitness and behavior of each solution. In line 14,
the representation archive { Ji=1 and the decision archive A are updated by survivor selection according to the fitness f and the behavior descriptor vector in line 15.
N
16

---

Published as a conference paper at ICLR 2024
Algorithm 3 CCQD
Parameter: number I of total generations, representation population size N,, number N of generated
solutions in each generation
Output: decision archive A with the associated representation part
Let <- B
l;
2: while t < T do
3: i = then
4:
(mR) (m, (
Randomly_.enneratcttooM....
5: else
[Qa] [rabh__crrtticcc((0))) ( Ai)
6:
7:
{m (, + -Taaih_Greed///Rtooo>(((//)>/ (Q0)
8:
[mP]a] + Seleet_JecissoonPPttt(d...}};;;
9:
[Ti + Camp:nnewwtttaapprrssettriiererr Ny,
R) Ji=ls [
10:
[T + variacciooDeeciisooooorotooaaard
11:
[m + Ker.atticneepprentttttoooaaaaaaa (())
end if
13:
Eva Evaluationn(=))1
14:
(T
Survivor__eleeciinnAA ( (T))))
15:
t-++1
16: end while
17: return A with the associated representation part
A.2 SAMPLE-EFFICIEN QD
One drawback of QD is the low sample efficiency. Here, we briefly introduce the recent works on improving the sample efficiency of QD, which can be mainly divided into two categories according to the improved components of QD (Cully & Demiris) 2018): how to select parent solutions from the archive (i.e., parent selection), and how to update them (i.e., variation).
Parent Selection. Parent selection methods aim to select appropriate solutions to generate offspring solutions. Uniform random selection, i.e., selecting parent solutions from the archive uniformly
random, is one of the simplest selection methods and has been widely used in QD algorithms such
as (Cully al., 22015] Nilsson & Cully 202I Fontaine & Nikolaidis, 2021] Tjanaka al.) (2022). Novelty search with local competition (Lchman & Stanley] (201T) considers both the novelty score and local quality score (i.e., the number of neighbors that a solution outperforms), and selects parent solutions from the corresponding Pareto front. Curiosity (Cully & Demiris, 2018) calculates the curiosity score based on the history information (i.e., increases the score if the offspring solution improves the QD-Score; otherwise, decreases it), and selects the solutions with higher curiosity scores. EDO-CS (Wang et al. 2022) used a clustering- based selection method, which divides archive into several clusters first and then selects good parent solutions from each cluster. NSS (Wang cct al., 2023a) introduces a objtii-bbecctiv optimization-be based selection method based on surrounded dominance, and selects the solutions from the top-ranked fronts.
Variation. Vanilla ME the basic evolutionary operator, i.e., crossover and mutation, as the variation operator, which is sample-inefficient, especially in high-dimensional optimization problems. ME with Evolution Strategies (ME-ES) (Colas | 2020) and Covariance Matrix Adaptation ME (CMA-ME) (Fontaine et al. 2020) use ES (Salimans et al. 2017) and CMA-ES (Hansen & Ostermeier 200Tb, respectively, to make vanilla ME scalable. Policy Gradient Assisted-ME (PGA-ME) (Nilsson) & Cully 2021 Flageat et al. (2023)) employs policy gradient-assisted variation, which significantly improves sample efficiency compared to using only evolutionary operators. Objective and Measure Gradient ME via Gradient Arborescence (OMG-MEGA) (Fontaine & Nikolaidis, 2021 augments
QD with explicit gradient information. QD-PG (Pierrot et al. 2022a) exploits information at the time-step level to promote QD search. Descriptor- Conditoond Gradients- Meti (DCG-ME) (Faldor (et al. 2023) improves policy gradient variation operator with a descriptor-condition critic that improves the archive across the entire descriptor space. Proximal Policy Gradient Arborescence
17

---

Published as a conference paper at ICLR 2024
(PPGA) (Batra et al. 2024) adapts PPO to the DQD framework and enables efficient optimization and discovery of novel behaviors.
B DETAILS OF EXPERIMENTAL SETTINGS
B. METHODS
We compare our implementation of CCQD with several baselines and state-of-the-art methods. For a fair comparison, we unify the common hyperparameters of these methods on all the eight environments. The other hyperparameters of each method set as the corresponding original paper.
We represent a policy as a fully connected neural network with two 256-dimensional hidden layers, which is the same (Chalumeau et al. 2023a) and can be represented as follows:
MLP((25) + tanh MLP tanh - MLP((AA) - tanh -> where s is the state, is the action, |A| is the dimension of the action space A, and MLP(n) is fully-com colleccondected layer with output size of n. All of the activation functions of the fully connected layers are tanh.
Then, we introduce the two types of variation operators used in our experiments.
DDD IsoLineDD (Vassiliades & Mouret 2018) a popular evolutionary operator used in several QD algorithms (Nilsson & Cully] Grillorllott et al., [023 Chalumeau et al. [2023a] Lim al. 2023a). Considering two parent solutions æ; and æ2, the offspring solution x' generated by isoL.neDD operator is sampled as follows:
x' æ1 + (0.1) 02 x (0 1).
where σ 0.005 and Ø2 0.05 in this paper, denotes the identity matrix, (0,, 1) and (O, I) denote a random number and random vector sampled from the standard Gaussian distribution, respectively.
Policy Gradient Operators. The policy gradient operator maintains critic and greedy actor in many QD algorithms (Nilsson & Cully] 2021, Pierrot al. 2022a Tjanaka et al.] 2022; Chalumeau et al. 2023a Lim et al. (023a)) and we adopt this setting well. At the start of each generation, the critic is trained with TD loss, while the greedy actor is simultaneously trained with policy gradient. Subsequently, the parent solutions updated with policy gradient, using the critic in the variation
process. We employed the policy gradient method TD3, whose hyperparameters are presented in Table 2
Table 2: The hyperparameters of TD3.
Hyperparameter
Value
Critic hidden layer size
[256, 256]
Policy learning rate
10-3
Critic learning rate
10-4
Replay buffer size
10s
Training batch size
256
Policy training steps
100
Critie training steps
300
Reward scaling
1.0
Discount
0.99
Policy noise
0.2
Policy clip
0.5
Detailed Settings of Methods.
The settings of the methods are summarized as follows.
ME (Mouret & Clune 2015) uses the IsoLineDD operator in the variation process, which is the same (Chalumeau al. 2023a
18

---

Published as a conference paper at ICLR 2024
QD-PG (Pierrot al. 2022a uses the IsoLineDD operator, the policy gradient, and the diversity gradient in the variation process. The proportion of the offspring solutions generated by these three operators all 1/3.
PGA-ME (Nilsson & Cully, 2021 Flageat et al. 2023a) uses the IsoLineDD operator, and the policy gradient in the variation process. The proportion of the offspring solutions generated by the two operators are both 0.5, which is the same as (Nilsson & Cully 2021
Lim al. 2023a).
OMG-MEGA (Fontaine & Nikolaidis
2021] Tjanaka et al. 2022) uses the IsoLineDD and
gradient ascent in the variation process. The gradient in OMG-MEGA is random weighted sum of the normalized gradients the fitness and the descriptor. In order to improve the sample efficiency of OMG-MEGA, proportion of the offisring solutions generated by the two operators are both 0.5, which is the same PGA-ME.
use TD3 to provide both of the gradients. The
PBT-ME (Pierrot & Flajolet 2023) evolves a population of agents instead of policies. In this paper, we use the SAC version of PBT-ME, which performs better than the TD3 version in the original paper.
CCQD uses the variation operator as the same as PGA-ME. The representation population size N, is 20. We used (I+2) decomposition strategy in the experiments.
Settings Atari Pong. For the Atari Pong (Bellemare al. 2013) task with high-dimensional visual observation space and discrete action space, we change to use DQN with three convolutional layers and fully connected layers as our policy network, which is the same as (van Hasselt et al.) 2016 Weng et al. 2022). All the other settings of CCQD and DQN-ME remain the same for fair comparison, and the only one difference between CCQD and DQN-ME the using of coevolution.
B.2 DETAILS THE ENVIRONMENTS
The experiments of this paper are conducted on QDa (Chalumeau et al. 2023b), popular imple- mentation of QD algorithms based on JAX which contains several algorithms and environments (Lim) et al. 2023a). The details of the environments are shown in Table where [S] is the dimension of the state space S, |.A] the dimension of the action space A, the dimension of the descriptor space, |.Y| is the number of parameters of the policy network, and #seeds is the number of random seeds used in each environment.
Table 3: The settings the environments.
Environments
[8]
k
|
#seeds
Hopper Uni
11
3
69, 635
10
Walker2D Uni
17
6
2
71,942
5
HalfCheetah Uni
18
6
2
72, 198
Ant Uni
87
8
4
90, 376
5
Humanoid Uni
227
17
2
128, 529
5
Humanoid Omni
227
17
2
128, 529
10
Point Maze
2
2
2
67,074 074
5
Ant Maze
101
8
93, 960 2
10
B.3 COMPUTATIONAL RESOURCES
The experiments are conducted on an NVIDIA RTX 3090 GPU (24 GB) with an AMD Ryzen 3950X CPU (16 Cores), except for PBT-ME, which is conducted on an NVIDIA RTX A6000 GPU (48 GB) with an AMD EPYC 7763 CPU (64 Cores).
ligent-robottttoee /ss/
http://ttthbbb..om/gggg/////////
19

---

Published as a conference paper at ICLR 2024
C ADDITIONAL RESULTS
C.I QD-SCORE TABLE
QD-Score focuses more on the overall quality the final obtained archive, rather than on the efficiency of algorithm as in the case of QD-Score AUC. As shown in Table CCQD achieves the best QD-Scores across all environments and has the highest rank. Besides, CCQD is significantly better than all the other algorithms in seven experimental environments, while its performance Ant Maze is almost equivalent to that of QD-PG and PGA-ME. Compared to QD-Score AUC (i.c., Table DD. the overall rankings are consistent, except for an exchange in the ranking order QD-PG and OMG-MEGA.
Table QD-Score of different methods on eight environments with episode length 250 and total timesteps 5e7. The symbols '+', '-', and '>' indicate that the result is significantly superior to, inferior to, and almost equivalent to CCQD, respectively, according to the Wilcoxon rank-sum test with significance level 0.05. Bold and underline texts respectively denote the best and runner-up algorithms.
Environment
ME
QD-PG
PGA-ME
OMG-MEGA
PBT-ME
CCQD
Hopper Uni
559415.3
507988.9
616474.4
607255.4
521933.1
646739.6
Walker2D Uni
683905.
189118.9
7413240
740915.6
518859.5
783199.7
HolfCheetah Uni
2274903.9
2188888.8
2580297.8
2625036.0
2734491.6
2865478.6
Ant Uni
804234.5
862769.3
868586.4
894949.9
671408.9
931191.1
Humanoid Uni
791793.6
825267.3 3
751922.0
746152.3
606250.8
877268.5
Humanoid Omni
5886.8
8618.0
7813.4
7022.7
7031.5
15063.2
Point Maze
263770.7
278524.3
233201.7
232718.3
176060.9
377520.2
Ant Maze
695519.4
1023962.7
972198.9
972772.0
788371.8
1038160.7
+/-/ Average Rank
0/8/0
0/7/1
0/7/1
0/8/0
0/8/0
4.62
3.50
3.25
3.62
5.00
1.00
C.2 ARCHIVE PROFILE
Archive Profile (Flageat et al. 2022) denotes the number of solutions in the archive whose quality better than a threshold. can measure the quality of the final obtained archive. We additionally plot the archive profile (Flageat et al. 2022) to evaluate the quality of the final archives of different methods, as shown Figure 5 The archive profile shows the number solutions in the archive whose quality is better than threshold. As the threshold increases, CCQD exhibits the slowest decay the number solutions across multiple environments. This highlights the superior quality of CCQD's final archive.
C.3 CORRECTED METRICS
The metrics in the noisy (or uncertain) setting important for downstream tasks. Here, considered the noisy setting, by reevaluating the solution of each cell in the archive for 50 times and filling archive called "Corrected Archive" (Grillotti al. 2023 Flageat et al. 2023b Flageat & Cully 2023) according to the average fitness and behavior descriptors. We use the corresponding QD) metrics of the Corrected Archive, i.c., Corrected QD-Score, Corrected Coverage, and Corrected Max Fitness, which are popular for measuring the performance of QD algorithms in the noisy environments. As shown in Table 5. CCQD still outperforms PGA-ME all environments.
C.4 NUMBER OF REPRESENTATION POPULATION SIZE.
T gives the QD-Score obtained by PGA-ME as well as CCQD with different representation population size N,. We test N, = 1, 10, 20, 50. The last row also shows the average sample efficiency improvement of CCQD over PGA-ME, when reaching the QD-Score PGA-ME, on the eight environments. We observe that equipped with different values of N,, CCQD is always better than PGA-ME and can improve the sample efficiency significantly. However, choosing an inappropriate value for N, will also decrease the improvement. If N, is too small, it will oversimplify
20

---

Published as a conference paper at ICLR 2024
Hopper
8030
10030
Nunber Selarkee
600
520
430
400
410
400
200
201
210
100
251
-1000
Thacohold
Finger Throheli
Finos Thealii
MB
Q8
PG
POA-ME
03G MBGA
PBTNE
COOD
Hormmooid Unii
Firmnnid Omnii
Print Mare
Ani Mare
460
Suzba Seleion
605
630
1003
1302
600
501
1000
-420
-200
-13020
-3000
-0003
-005
Panaar Threstoldd
Fimaz Theabeld
Pincn Tampaad
Fianzrr Thresblld
MI
MIDIA
PITT MI
Figure 5: The archive profile of different methods eight environments with episode length 250 and total timesteps 5e7. The medians and the first and third quartile intervals are depicted with lines and shaded areas, respectively.
Table 5: Corrected QD-Score, Corrected Coverage, and Corrected Max Fitness of PGA-ME and CCQD on different environments with episode length 250 and total timesteps 5e7. Bold text respectively denote the better algorithm.
Corrected QD-Score
Corrected Coverage
Corrected Max Fitness
PGA-ME
CCQD
PGA-ME
CCQD
PGA-ME
CCQD
HalfCheetah Uni
876170.00
1233301.75
34.38
43.85
1162.18
1361.92
Ant Uni
330165.94
403013.94
28.12
32.23
985,80
1151.37
Humanoid Uni
245687.56
337272.06
51.37
52.83
807.86
1625.46
Point Maze
140449.19
221739.34
40.92
58.50
-156.55
-24.52
Table 6: QD-Score of PGA-ME and CCQD with different representation population sizes on eight environments with episode length 250 and total timesteps 5e7. The last row indicates the average percentage of sample efficiency improvement achieved by various variants of CCQD, when reaching the QD-Score PGA-ME.
Environment
PGA-ME
CCQD-1
CCQD-10
CCQD-20
CCQD-50
Hopper Uni Walker2D Uni
616474.4
658986.5
656077.2
646739.6 6
631475.0
741324.0
7261
775977.0
783199.7
783983.6
HalfCheetah Uni
2580297.8
2619269.3
2764638.6
2863478.6
2711417.7
Ant Uni
868586.4 4
869856.9
913514.0
931191.1
892193.8
Humanoid Uni
751922.0
899925.4
895138.7
877268.5
941327.0 0
Hunanoid Omni
7813.4
14450.3
15678.7
15063.2
19328.3
Point Maze Ant Maze
233201.7
253359.4
318775.7
377520.2
27416-1.5
972198.9
828489.4
980763.7
1038160.7
97903-L6
Average Rank
4.75
3.62
2.25
2.00
2.38
Average % of Improvements
165.3
230.0
246.6
217.0
the problem, while a too large value will fail to fully demonstrate the advantage of CCQD. Therefore, recommend using moderate value for N,, such 10 20. We used 20 in experiments.
21

---

Published as a conference paper at ICLR 2024
C.5 NUMBER OF CRITICS
We conduct an ablation study on the number of crities, including CCQD (single TD3 critic), and CCQD (single PeVFA critic). As shown in Figure 6 CCQD we used is the best, validating the effectiveness of maintaining multiple PeVFAs. Besides, CCQD (single TD3 critic) and CCQD (single PeVFA) both outperform PGA-ME, indicating that they are still sample-efficient and can be used in some scenarios that have limited memory resources.
HalfCboctah Uni
Ant Uni
2.75
2.50
2.25
2.00
2
Steps
Time Steps
PGA-ME
CCQD (single PoVFA)
COQD
CCQD (single TDS critic)
CCQD (TDS critis)
Figure 6: The ablation study on the number of critics.
C.6 ABLATION STUDY ON PEVFA
In our implementation of CCQD, we utilized PeVFA as our critic. Here, we conduct an ablation study to compare its performance with the implementation without PeVFA, i.e., using the critic of TD3. As shown in Figure 7 both CCQD and CCQD (without PeVFA) exhibit significantly better performance than PGA-ME. Moreover, using PeVFA as the critic may result in relatively higher performance.
Hoyper
HalfCherthh Uni
Ant Uni
1et
Homanoid Uni
1.0
3.6
00.3.r
0.0
3.6
3.4
3
35
2
2
Time Stepe
167
Time Stge
Tire Stere
167
Time Steps
107
PCA ME
CTQP (ottie (VVRA)
Figure 7: The ablation study on PeVFA.
C.7 VISUALIZATION
Final archive. To clearly show the (decision) archive quality, we visualize the archives obtained by ME, PGA-ME, and CCQD. As shown in Figure 8 (c), the qualities of the solutions in the archive obtained by CCQD are much higher than ME and PGA-ME, and CCQD also covers more regions of the archive. In addition, we want to know if the representation archive really diverse. For each decision part in the final decision archive, we combine it with all the representation parts in the representation archive, evaluate them, and calculate the standard derivation of the fitness, as shown in Figure & d). We can observe that the standard deviations in many regions are large, reflecting the good abilities of the representation parts in recognizing diverse state representations.
Running process of Point Maze. Point Maze is maze environment that involves walking from the green start point in the lower right corner to the red end point in the upper left corner, as shown in Figure (a). The reward is related to the distance from the end point, and the closer to the end point the higher the reward. We can observe from Figure b)-(e) that the algorithm bypasses the wall in the middle of the training process; thus, it comes closer to the end point and quickly explores the neighborhood, making all the metrics jump significantly.
22

---

Published as a conference paper at ICLR 2024
120
354
11
(d) Fitness std. of each
(a) ME
(b) PGA-ME
(c) CCQD
decision part
Figure 8: (a)-(c): Visualization of the archives obtained by ME, PGA-ME, and CCQD on HalfCheetak Uni, where the 2-dimensional behavior space is discretized into cells. (d): Standard derivation of fitness each decision part, when combined with different representation parts, of CCQD on HalfCheetah Uni. Note that colors represent the quality in (a)-(c), and standard deviation in (d).
Illustration
(b) 25% of total time-steps
(c) 50% of total time-steps
(d) 75% of total time-steps
(c) 100% of total time-steps
environment
Figure 9: (a): Illustration of Point Maze environment (Chalumeau et al. 2023a). The green dot represents the starting position, and the red dot represents the target position. (b)- Visualization of the archives on Point Maze in the different stages the training process, where the 2-dimensional behavior space discretized into cells, and the colors represent the fitness.
Internal dynamics of decision population. We ana- lyze the proportion of surviving IsoLineDD solutions and surviving RL solutions to all surviving solutions in each generation. We plot the curves of the proportion of RL solutions on Hopper Uni and Walker2D Uni in Figure [O] and smooth them for better presentation. Note that the proportion of IsoLineDD solutions (1 proportion of RL solutions). We can observe that as the optimization proceeds, the proportion of RL solutions tends to decrease, which is consistent with the results of PGA-ME (see Fig- ure 10 in (Flageat et al. 2023a)). This may be because the IsoLineDD operator can find diverse solutions throughout the whole process, due to its strong capability of global exploration.
Sointis
0.3
0.2
Time Stups
Le7
Hopper Uni
Walker2D Uni
Figure 10: The fraction of the solutions reproduced by the RL operator among the surviving offspring.
C.8 OTHER SETTINGS
AURORA
We also compare CCQD and PGA by adopt-
ing AURORA (Grillotti & Cully 2022), denoted as CCQD-
AURORA and PGA-AURORA, As shown in Table 7 CCQD-AURORA archives better OD-Scores across all environments, demonstrating the generalization of CCOD.
Longer Episode length We also compare all the methods the environments with episode length 1000, which is consistent with the setting in Pierrot & Flajolet (2023). As shown in Table S and Figure II the Max Fitness of the methods these environments now is about times as high as the environments with episode length 250, and is consistent with the results in the previous work that use 1000 as the episode length, such as Pierrot Flajolct (2023). In this setting, CCQD still has the best average rank QD-Score AUC.
23

---

Published as a conference paper at ICLR 2024
Table 7:
QD-Score, Coverage, and Max Fitness of different methods environments with episode length 250 and total timesteps 2e7. Bold texts respectively denote the best algorithms.
QD-Score
Coverage
Max Fitness
PGA-AUR.
CCQD-AUR.
PGA-AUR.
CCQD-AUR.
PGA-AUR.
CCQD-AUR.
Hopper Uni
122789.1 154533.4
135967.8
37.9
48,5
642.9 655.6
529.0
Walker2D Uni
181841.0
38.7
45.0
775.2
Table 8: QD-Score AUC (x (10)2) different methods on eight environments with episode length 1000 and total timesteps 1.5c8. The symbols '+', '_', and "z² indicate that the result is significantly superior to, inferior to, and almost equivalent to CCQD, respectively, according to the Wilcoxon rank-sum with significance level 0.05. Bold and underline texts respectively denote the best and runner-up algorithmms
Environment
ME
QD-PG
PGA-ME
OMG-MEGA
PBT-ME
CCQD
Hopper Uni Walker2D Uni
224.65
178.45
253.63
244.79
226.14
264.03
248.72
289.76
313.38
314.58
234.59
387.04
HalfCheetah Uni
1252.82
1104.65
1304.95
1329.01
1624.75 +
1484.76
Ant Uni
374.50
423.53
426.05
439.96
477.42
468.45 48
Humanoid Uni
117.43
156.25 RM
127.73
131.78
108.48
170.81
Humanoid Omni
0.90
4.68 R2
11.05
12.59
1.42
20.32
Point Maze
127.83 RM
125.45 RM
121.72
117.95
131.42
130.88
Ant Maze
1038.69 RV
1015.63 RM
1018.56 R
961.73 PJ
940.29 P3
988.62
+/ /
0/6/2
0/4/4 4.25
0/5/3 3.38
0/6/2 3.38
1/4/3
/
Average Rank
4.50
3.75
1.75
Table Max Fitness of different methods on eight environments with episode length 250 and total timesteps 1.5e8. The symbols '+', "-', and 'z' indicate that the result is significantly superior to, inferior to, and almost equivalent to CCQD, respectively, according to the Wilcoxon rank-sum test with significance level 0.05. Bold and underline texts respectively denote the best and runner-up algorithms.
Environment
ME
QD-PG
PGA-ME ME
OMG-MEGA
PBT-ME
CCQD
Hopper Uni
697.9
634.8
820.5 ~
806.8 2J
702.1
788.1
Walker2D Uni
788,5
842.3
902.9
920.9
692.3
1003.8
HalfCheetak
723.2
584.9
1830.7 RM
1801.4 R
1767.9
1920.4
Ant Uni
618.6
1427.2
1458.3
1492.5
1752.0 &
1688.6
Humanoid Uni
1284.2
1293.0
1397.7
1548.2
1563.6 P
1796.3
Humanoid Omni
1096.0
1006.8
998.4
955.9
1133.4 +
999.9
Point Maze
-55.8
766.7
-153.2
-156.6
-105.0
-23.6
Ant Maze
5643.3
4835.2
4822.9
4776.0
-3932.8
4572.0
+/-/ /
1/7/0
0/6/2
0/5/3
0/5/3
2/4/2
Average Rank
4.62
4.62
3.50
3.50
2.88
1.88
Max Fitness Tables
Max Fitness can measure the exploitation ability a QD algorithm. As shown in Table 9 10 CCQD has the best average rank in both environment settings, and PBT-ME is the runner-up.
24

---

Published as a conference paper at ICLR 2024
Hopper
Walker2D
HaliChocish
Uni
Time Stepe
Troe Steps
Time Steps
Thone Steps
75
50-
20-
Staps
Time Steza
14t
Tiae Steps
148
Tixe Stepe
164
Tiae Steps
140
MB
Q8 PQ
PCA-ME
0300 MEGA
PET
cogo
Humtsoid Lini
Hamazoid Onni
Point Maze
Aut Mase
1.5
1.0
1.0
0.5
Stpe
1.00
100
80
50
60
25
43
1.55
105
114
7.5
-2.
2.5
-7.
0.0
0.5
1.0
1.5
0.0
0.0
810
0.5
15
Timee Stepo
Tixe Steps
Time Siggr
Time Sage
QD
POA-ME
MEGA
COOD
Figure 11: Performance comparison of CCQD with other methods in terms of QD-SQore Coverage, and Max Fitness eight environments with episode length 1000 and total timesteps 1.5e8. The me- dians and the first and third quartile intervals are depicted with curves and shaded areas, respectively.
25

---

Published as a conference paper at ICLR 2024
Table 10: Max Fitness of different methods eight environments with episode length 1000 and total timesteps 1.5e8. The symbols '+', and 'se' indicate that the result is significantly superior to, inferior and almost equivalent to CCQD, respectively, according the Wilcoxon rank-sum test with significance level 0.05. Bold and underline texts respectively denote the best and runner-up algorithms.
Environment
ME
QD-PG
PGA-ME
OMG-MEGA
PBT-ME
CCQD
Hopper Uni
1376.4
1222.9
1673.9
1644.8
1752.8
1878.2
Walker2D Uni
1657.6
2132.0
2763.2
2509.0
1639.8
4534.7
HalfCheetah Uni
1008.3
828.8
5033.9
5933.9
6225.1
6643.0
Ant Uni
1888.2
4880.4
4935.4
4611.3
5795.6
5741.0
Hunanoid Uni
1724.2
3689.9
5268.3
5355.2
4553.4
7858.2
Humanoid Omni
1310.4
3146.0 R3
3241.1
2441.7 =
2054.4
3278.2
Point Maze
582.7
-3014 R
-88.22
-606.7
-130.1 A
-16844
Ant Maze
19220.2
-18119.1
17769.6
117620.9
-15260.7 =
15538. 1
0/8/0
0/6/2
0/7/1
0/6/2
0/3/5
Average Rank
5.38
4.50
3.25
3.75
2.75
1.38
26


Reviews:
[{"review_id": "mc5ZDoR88k", "reviewer": "Reviewer_zwMj", "summary": "**Problem Setting**\n\nThis work aims to tackle the methods of quality diversity, where we desire to find a diverse set of solutions to an optimization problem. Specifically, we try to make QD methods more computationally efficient.\n\n**Novel Idea**\n\nThe idea is to factor the population space of all neural network parameters into two spaces, the first layers and the later layers. These correspond to a representation layer and a decision layer.\n\nThe representation part has a smaller population and is implemented as a list. The decision portion contains a much larger population and is impllemented as a grid.\n\nParent selection is performed uniformly. Parts are selected independently from the decision and representation portions, then evaluted jointly. The mutation operator is implemented through a combination of an evolutionary operator and direct optimization through a critic. There is a unique critic for each representation part. Survivors are selected through the vanilla MAP Elites style approach where parts are first segmented into cells, and then chosen based on fitness.\n\nExperiments are presented on the QDax suite. Comparisons are presented against map elites, along with modern versions. Experiments show strong results and CCQD consistently outperforms the prior methodology.", "questions": "What is the motivation between using both an evolutionary operator as well as a learned actor critic update?\n\nIt would be interesting to see if there is a structured way to decompose the neural network into factors to be used for QD. It would also be informative to see the affect of QD on the parameters themselves, i.e. are decision policies trained via QD more robust to noisy inputs because they are trained on a variety of representations?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper presents a simple method to reduce the sample complexity of quality diversity methods applied to neural networks. The idea is to partition the parameter space into a representation layer, which consists of the first neural network layers, and the decision layer, which is the later laters. This is a clean formulation and is communicated in an understandable manner. The significance of this work is in its further exploration as a method to factorize evolutionary methods over neural networks.\n\nAblations provide answers to questions such as what the qualitative impact of the representation vs the decision parts are.", "weaknesses": "The setting provided places an emphasis on sample complexity, without considering the asymptotic performance of the methods. It would be strengthening to confirm that the CCQD method reaches the same or better asymptotic performance as the other methods. \n\nIn addition, a description of the diversity criteria used to separate the symbols in the QD algorithm would improve clarity.", "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": "", "extra_scores": {}}, {"review_id": "AIvFYASkHS", "reviewer": "Reviewer_CbDL", "summary": "In that paper, the authors introduce Cooperative Coevolution QD (CCQD), a novel method to evolve populations of diverse and high-performing RL agents, the so-called QDRL problem. The paper aims to improve the sample efficiency of current methods by disentangling the feature extraction learning, also called representation learning part and the decision learning part of the policies during training. This done by introducing two separate populations that are co-evolved with the representation population being much smaller than the decision one. This is motivated by the intuition that most of the representation knowledge can be re-used by all the agents while the diversity and performance is more likely to emerge from the decision parts. The authors propose to split the policy networks layers to define these populations where the first group of layer and the last group of layers would respectively define the representation and decision populations. \n\nThe framework is general and most of the design choices used by the authors are common in that literature including the type of archives and variation operators. The authors introduced two changes compared to others such as PGA-MAP-Elites in the way the critics are handled.\n\nTheir method is then benchmarked on the QDax suite against several state-of-the-art methods (PGA-ME, QDPG, ME and PBT-ME (SAC)).", "questions": "**Minor points**:\n\n- (manon et al.) ---> (flageat et al.) page 7\n\n- It might be interesting to cite \"The Quality-Diversity Transformer: Generating Behavior-Conditioned Trajectories with Decision Transformers\" as the work is recent and was published at GECCO and here is also this idea of compressing the feature extraction within a single model, even though both works share different final motivations.\n\n- I would have liked to see more discussion about the co-evolution aspect of the method, the different existing strategies and the motivation behind the design choices (e.g. the split of the policy layers). Maybe it would be worth it to move part of the other technical details that are common to most QDRL works to the supplementary to focus more in the main core on the aspects that make this work unique.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Overall I find that this paper addresses an interesting topic in the QDRL literature which is well motivated. The approach is sound and I share the same intuition that these methods would strongly benefit from different treatments of the representation learning and decision learning parts. Using co-evolution to do so is novel and I find it also elegant.\n\nThe paper is overall well written and does a good job at setting up the context, the problem and presents a good overview of the literature on this topic. The technical aspects are also well explained and I found it easy to understand how the algorithm works and is implemented.\n\nRegarding the experimental section, I find the ablation study informative and I like the introduction of the Atari Pong environment which is not very common in that field but I think very useful to show the versatility of the approaches.", "weaknesses": "However, I have strong doubts about the larger benchmark where CCQD is compared on the QDax suite to QDRL competitors. While I appreciate that the authors considered a large number of environments and repeated each experiment five times, I have serious doubts about the showed result as they don't match the ones reported in recent works such as PBT-ME (ICLR last year) produced on the exact same benchmark and for which the code is available. \n\n- My main concern is the number of time steps considered and the maximum fitness obtained in several environments.  For instance in Ant-Uni, the authors show training evolution over 5e7 time steps for a maximum fitness reached of 1500. This fitness corresponds to the robot barely moving at low speed. In that environment, asymptotic fitnesses are more in the scale of 6000-7000, see for instance PBT-ME, which corresponds to the ant robot actually running. Same observation in HalfCheetah where the authors report asymptotic performance of 1500 while usual values are around 6000-7000 too. It is even worse in Walker2d-Uni where reported performance is 800 compared to 4000 in state-of-the-art works. This indicates that the shown results correspond to very early stages of training, before actual convergence, and thus cannot allow to draw any meaningful conclusion.\n\n- The authors claim \"PBT-ME is capable of adjusting the algorithm’s hyperparameters while optimizing, resulting in the need of a significant amount of computational resources\" while of the main point and contribution of the paper is to show that tuning the hyperparameters can be done with the same budget, and even in some cases improve the efficiency. The reported conclusions and performance ranking to other methods are not in the line with the one published while both the code and benchmark are open. I think this might come from the fact that all the runs were stopped too early and I would expect the authors to find back the original paper claim if they wait long enough to see the beginning of training convergence. \n\n- Moreover, despite these limitations, in most cases the sample efficiency gain that is shown remains limited and I would expect more from an efficient representation/decision decoupling. In that context it is also hard to say if the small obtained gains compared to PGA-ME for instance are due to the co-evolution strategy being proposed or to some other minor changes like the PeVFA update of the critic or the fact that the population critic has been replaced by one critic per agent.\n\nAll in all, I am happy to see such works submitted at ICLR and hope there will be more in the future as I believe QDRL is a very exciting field and might play an important role in the future of AI methods. I also like the motivation and find the method original. The paper is also pleasant to read. However, as per my points above, I think that the main experiments of the paper show strong weaknesses which makes it unconvincing. I would be happy if the authors could mitigate these points by notably running all methods longer, until observing the beginning of asymptotic convergence, and also by confirming findings of previous works. In case the authors find different results of previous works, I would expect a strong discussion about what in their opinion could trigger these changes. If the authors were able to strengthen their experimental setup I would be happy to see this work published at ICLR but in the current state I think the work is not ready.", "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": "", "extra_scores": {}}, {"review_id": "24aLWJYwqc", "reviewer": "Reviewer_VT9L", "summary": "This paper proposes the cooperative coevolution for QD methods on reinforcement learning problems. The major contribution is claimed to be the first time use of cooperative coevolution, and this can help improve the sample efficiency.", "questions": "What is the relationship between large-scale search space and the sample efficiency? Why address the large-scale space with cooperative coevolution can help improve the sample efficiency of QD?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The experiment setup is considerate, and the results are promising. The main idea of using cooperative coevolution into reinforcement learning is easy to understand for addressing large-scale search space.", "weaknesses": "This work is not the first time of applying cooperative coevolution to reinforcement learning, even restricted in the quality-diversity like evolutionary algorithms, see the following reference:\n[1] Evolutionary reinforcement learning via cooperative coevolutionary negatively correlated search.\nSo the related claims should be revised.\nGiven the above work, the contribution of this work may be limited.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)