Sample-Efficient Quality-Diversity by Cooperative Coevolution

Thanks for your comments. Below please find our responses.

Q1 This work is not the first time of applying cooperative coevolution to reinforcement learning. Contribution is limited.

Thank you for bringing up the paper [1], which is an interesting work proposing an efficient method called Cooperative Coevolutionary Negatively Correlated Search (CCNCS) that utilizes CC to solve large-scale optimization problems in RL.

We would like to clarify that our main contribution is not the initial application of CC to RL, but rather the incorporation of CC principles into QD, along with the introduction of a sample-efficient CCQD framework.

Apart from the motivation and application tasks, the differences in the method between our work and [1] are significant, which are explained as follows:

1. Decomposition strategy. Inspired by recent advancements in representation learning, CCQD employs a layer-based decomposition strategy and divides the policy network into two parts with different functions. CCNCS utilizes the random grouping strategy, which is commonly used in CCEA.

2. Population size and shared components. CCQD not only employs a layer-based decomposition strategy but also maintains fewer representation parts. This means that the population sizes for the two sub-problems in CCQD are different, which distinguishes it from many traditional CC approaches, including [1]. This unique characteristic of CCQD is derived from a specific observation of the QD task: maintaining smaller numbers of representation parts and sharing them further serves our goal of simplifying the optimization problem. CCNCS does not share the same part due to its parallel exploration behaviors.

We have included a discussion about this work in our main paper. Thank you.

Q2 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?

We consider the problem of QDRL and optimize the parameters of the policy network by sampling from the environment. Therefore, the number of samples used can be viewed as the number of evaluations in a typical optimization problem. In the case of a large-scale optimization problem, if the search space can be appropriately reduced, a smaller number of evaluations can be used to find satisfactory solutions. CCQD achieves this by decomposing the problem and using shared representation, effectively reducing the optimization space. Additionally, through cooperative coevolution, the collaboration between the representation part and the decision part promotes exploration and enhances the ability to find diverse policies. As a result, CCQD improves the optimization efficiency, i.e., the sample efficiency of QD.

[1] Evolutionary reinforcement learning via cooperative coevolutionary negatively correlated search. Swarm and Evolutionary Computation, 2022.

We hope that our response has addressed your concerns, but if we missed anything please let us know.

Thank you for your appreciation. Below please find our response.

Q1 Asymptotic performance

Thanks for your suggestion. We have revised to increase the timesteps of each environment by three times, i.e., from 5e7 to 1.5e8, to show the asymptotic performance. The results (in Table 1, Figure 2, and Table 8) indicate that CCQD remains the best-performing algorithm across various metrics, e.g., QD-Score AUC and Max Fitness.

Q2 Description of the diversity criteria

Thanks for your suggestion. We have revised the description of the QD algorithm in Appendix A according to your suggestion. Specifically, we add a detailed process of survivor selection of QD to make it clearer.

Q3 Motivation of using both an evolutionary operator as well as learned actor critic update?

The RL operator focuses on optimizing quality. To promote diversity optimization, it is necessary to simultaneously use evolutionary operators. This is a common approach in many QDRL works [1-3]. Thanks to your comment, we have revised to add some explanation. Furthermore, we analyzed the effectiveness of the evolutionary operator in Figure 10 of Appendix C.7. We can observe that as the optimization proceeds, the proportion of RL solutions (i.e., solutions generated by the RL operator) surviving into the archive in each generation tends to decrease, i.e., the proportion of surviving solutions generated by evolutionary operator tends to increase, which demonstrate its effectiveness.

Q4 Structured way to decompose the NN.

Thanks for your valuable comments. Our proposed layer-based decomposition strategy can be seen as an initial step towards this. As you suggested, there may be some structured ways to decompose the neural network. We will study it in our future work.

Q5 Are the decision policies more robust to noise because they are trained on a variety of representations?

Yes, we agree with you. Some studies in zero-shot coordination and robust training [4-6] have shown that training with diverse partners can lead to robust coordination abilities, which is similar to the situation described here. Therefore, we believe that the decision policies trained in this manner are more robust. We will explore this further in our future work. Thank you.

[1] Policy gradient assisted MAP-Elites. GECCO, 2021.

[2] Empirical analysis of PGA-MAP-Elites for neuroevolution in uncertain domains. ACM TELO, 2022.

[3] Evolving populations of diverse RL agents with MAP-Elites. ICLR, 2023.

[4] Trajectory diversity for zero-shot coordination. ICML, 2021.

[5] Learning zero-shot cooperation with humans, assuming humans are biased. ICLR, 2023.

[6] Robust multi-agent coordination via evolutionary generation of auxiliary adversarial attackers. AAAI, 2023.

We hope that our response has addressed your concerns, but if we missed anything please let us know.

Q3 Performance Gain by coevolution

Thanks for your comments. We believe the performance gain by coevolution is significant. The reasons are as follows.

1. The main difference between CCQD and DQN-ME in the context of Atari-Pong is the utilization of coevolution, where CCQD does not use other techniques such as PeVFA. We can find from Figure 4(c) that the performance of CCQD is significantly better than DQN-ME in Atari-Pong, which thus validates the effectiveness of the coevolution strategy. We have made revisions to the paper to enhance the clarity of this point. Thank you for your feedback.

2. We conducted ablation studies on the number of critics and using of PeVFA, as shown in Appendix C.6 and C.7, respectively. The results show that using only one critic or not employing PeVFA does not decrease the performance significantly. Moreover, the performance remains significantly superior to the PGA-ME baseline, highlighting the effectiveness of coevolution.

Q4 Missing one related work

Thanks for pointing this out. We have revised to add some discussion in the new version.

In the Related Work part: "The Quality-Diversity Transformer (QDT) [6] compresses an entire archive into a single behavior-conditioning policy, which can be used for many downstream applications."

In the Conclusion part: "Additionally, the shared representation components in CCQD offer the potential for reducing the storage cost of QD algorithms. In some computationally-constrained application tasks, combining the CCQD framework with archive distillation techniques [6] can further reduce the storage cost and achieve a sample and storage-efficient QD algorithm, which is an aspect we will investigate in future research."

Q5 More discussions about the co-evolution

According to your suggestion, we have revised to move some technical details that are common to QDRL in Section 2.3 to the appendix and add more discussions about the co-evolution. We hope it is clearer now. Thank you.

[1] Neuroevolution is a competitive alternative to reinforcement learning for skill discovery. ICLR, 2023.

[2] QDax: A library for quality-diversity and population-based algorithms with hardware acceleration. arXiv, 2023.

[3] https://qdax.readthedocs.io/en/latest/examples/pgame/

[4] Evolving populations of diverse RL agents with MAP-Elites. ICLR, 2023.

[5] https://qdax.readthedocs.io/en/latest/examples/me_sac_pbt/

[6] The quality-diversity transformer: Generating behavior-conditioned trajectories with decision transformers.

We hope that our response has addressed your concerns, but if we missed anything please let us know.

Thank you for your constructive and valuable comments. Below please find our response.

Q1 Longer length and inconsistent with previous works

Thanks for your suggestion. As this work is more concerned with the sample efficiency, we originally trained over 5e7 timesteps. According to your suggestion, we have revised to run all the methods longer to show their asymptotic performance. As shown in Table 1, Figure 2, and Table 8, our main conclusion still holds. The average ranks of the methods do not change a lot, where the ranks of QD-PG and PBT-ME get better slightly, and those of others get worse slightly. CCQD still has the best average rank (i.e., 1.12 and 1.88, respectively) on QD-Score AUC and Max Fitness.

Thanks to your suggestion, we have checked the reason for the roughly 4-times difference (e.g., 1500 vs. 6000) in Max Fitness that you mentioned. We find that the difference is not due to the lack of convergence, but to the different settings of the environments. We used episode length 250 in our initial experiments, which is consistent with previous works [1-2] and the default setting of QDax [3], while the maximum episode length is 1000 in [4]. The fitness of the environments is mainly determined by the total distance the robot moves, and a longer episode length allows the robot to move farther. Thus, the 4-times maximum episode length of the environments results in approximately 4-times Max Fitness. The similar results with our paper in these environments can be found in previous works [1-2].

To further illustrate this, we additionally re-run all the methods in the environments with episode length 1000, which is consistent with the setting in [4]. As shown in Table 7, Table 9 and Figure 11, the Max Fitness of the methods in these environments now is about 4 times as high as our original environments, and is consistent with the results in the previous work that use 1000 as the episode length, such as [4]. In this setting, CCQD still has the best average rank (i.e., 1.75 and 1.38, respectively) on QD-Score AUC and Max Fitness.

From these updated and newly added empirical results, we can also find that the performance rank of PBT-ME with previous methods is mostly consistent with that reported in the original paper of PBT-ME [4]. For example, in Figure 11, the QD-Scores of PBT-ME are better than those of PGA-ME and QD-PG in Ant Uni and HalfCheetah Uni, and worse than those in Walker2D Uni; in Tables 8-9 (which give the comparison of the Max Fitness of different methods and are added to the revised paper due to your suggestion) in Appendix C, PBT-ME achieves the highest average rank of Max Fitness except CCQD in both environmental settings.

We put the added results of using the episode length 1000 in the appendix. But if you think that it would be beneficial to present the results of using the episode length 1000 rather than 250 in the main paper, please feel free to let us know.

Q2 Different performance of PBT-ME

The implementation of PBT-ME is based on its official implementation in QDax [5]. In our initial experiments, we kept the common hyperparameters consistent (e.g., population size and variation operators) to ensure a fair comparison. Thanks to your comment, we have revised to utilize the setting from the original paper to re-run PBT-ME. Here is the PBT-ME's performance comparison between our setting and the original setting:

We find that the results of PBT-ME under the two settings are quite similar. Under our setting, the Max Fitness is slightly higher, while under the original setting, the QD-Score is slightly higher. Note that we have not re-run PBT-ME in the two humanoid-based environments due to the limitation of device; we will do it and update the results in the final version.