Benchmarking Quality-Diversity Algorithms on Neuroevolution for Reinforcement Learning

We present a Quality-Diversity benchmark suite for Deep Neuroevolution in Reinforcement Learning domains for robot control. The suite includes the definition of tasks, environments, behavioral descriptors, and fitness. We specify different benchmarks based on the complexity of both the task and the agent controlled by a deep neural network. The benchmark uses standard Quality-Diversity metrics, including coverage, QD-score, maximum fitness, and an archive profile metric to quantify the relation between coverage and fitness. We also present how to quantify the robustness of the solutions with respect to environmental stochasticity by introducing corrected versions of the same metrics. We believe that our benchmark is a valuable tool for the community to compare and improve their findings. The source code is available online: https://github.com/adaptive-intelligent-robotics/QDax


INTRODUCTION
Quality-Diversity (QD) algorithms [3,7,25] can be used to generate a collection of diverse and high-performing solutions. They have been used across many different domains such as robotics [6,8], video game design [14], aerodynamic design [16] and many others [10,13]. Recent multiple works have considered applying QD algorithms to deep neuroevolution in Deep Reinforcement Learning (DRL) settings and showed competitive results [5,10,22,24,30]. DRL methods conventionally rely on gradient-based optimization methods to search for optimal parameters of Deep Neural Networks (DNNs). Conversely, the field of deep neuroevolution studies evolving DNNs with evolutionary methods where the genotypes are the parameters of the neural network [26][27][28].
However, two key challenges arise when using QD algorithms for deep neuroevolution in RL domains; (i) the large number of parameters of DNNs making optimization in this high-dimensional searchspace challenging, especially with conventional genetic mutations [5,17,22], and (ii) the stochasticity of these environments [5,11,22].  Table 1: Summary of two tasks across six environments of different complexity, proposed to benchmark QD algorithms applied to neuroevolution for RL domains. In the last line, the notation gives the number of cells in the corresponding MAP-Elites archive, where corresponds to the BD dimensionality and to the number of sub-divisions of each BD dimension.
DRL domains commonly consist of stochastic environments where initial states are sampled from distributions, and transitions between states may be non-deterministic. Furthermore, due to the use of closed-loop DNN policies, the stochasticity of the environments will result in deviations from states originally encountered and experienced by the policy. These deviations cause the policy to take different actions which result in varying behavioural descriptors and fitnesses for a single policy, making this another key challenge for QD algorithms in this context [11,18].
The lack of standardised environments and tasks in QD for deep neuroevolution in RL domains makes quantifying scientific progress of the algorithms difficult. While not perfect, benchmarks have been critical to progress in machine learning. The lack of benchmarks has been most evident in fields such as computer vision [1,9,20] and speech recognition [23]. Deep RL also has benefited from benchmarking environments and platforms such as OpenAI Gym [2] and Deepmind Control Suite [29]. In this paper, we propose a benchmark composed of two tasks for neuroevolution in RL domains across six different environments of varying complexity. We also formalize existing evaluation procedures and metrics from the literature to account for the two key challenges when evaluating algorithms in these domains: high-dimensional search-space and stochasticity.

TASKS
The benchmark we propose contains two tasks across six robot control environments, which are already included in the Brax physics simulator [15] except for the Hexapod environment. We propose several levels of difficulty of tasks based on the different morphologies of the robots (see Fig. 1). 2-dimensional planar robots like the Hopper, Walker and Half-Cheetah have fewer degrees of freedom and a smaller state space making them easier to control. More complex 3-dimensional robots like the Ant and the Humanoid have a larger number of degrees of freedom and larger state-space. In the case of the Humanoid, it is also unstable in its standing position. The unstable dynamics require some degree of balance control on top of the locomotion control, thus making the task more difficult. We also use a simulated hexapod that corresponds to a real robot, similar to an open-sourced 18 DoF Hexapod 2 and previously used in the QD literature [4,6]. Environments like this provide further opportunities for policies to be transferred into real-world 2 https://github.com/adaptive-intelligent-robotics/Hexapod_Design_V2 systems, which could uncover further challenges and limitations of QD algorithms.
We propose two types of tasks: a uni-directional and an omnidirectional locomotion task. The uni-directional task was first introduced in Cully et al. [6] while the omni-directional task was introduced in the BR-Evolution algorithm [8]. These tasks have been extended to different continuous control systems that were part of the OpenAI Gym [2] RL benchmark in QDGym [5,22]. Both tasks are important for the benchmark since previous works have demonstrated that algorithms behave different in their abilities to explore the behavioural space and finding high-performing solutions [22,24]. A summary of all the proposed benchmarks tasks and environments can be found in Table 1. For all experiments we use QDax [19], an accelerated QD library 3 that utilizes the Brax [15] simulator for the environment implementations.

Uni-directional tasks
The goal of uni-directional locomotion tasks is to find diverse gaits for walking forward as fast as possible. The behavioral descriptor for this task is the average time each foot is in contact with the ground. This descriptor promotes diversity in locomotion gaits that are useful for adaptation to mechanical damage [6]. The contact of each foot with the ground is a good estimate of how much each leg contributes to the locomotion. The fitness function is a sum of the -displacement ( ), a survival bonus ( ) and the negative sum of the torques (− ) at each time-step.
, where is the number of feet. (1)

Omni-directional tasks
In the omni-directional locomotion task, the goal is to move efficiently in every direction. This task requires policies that result in diverse final positions of the centre of mass (CoM) of the robot. The behavioral descriptor is then defined as the final cartesian coordinate of the CoM at the end of the episode: The fitness function is identical to without the displacement term .

METRICS
We consider metrics to evaluate (1) the efficiency of QD algorithms, (2) the properties of the returned archives, and (3) the robustness of the archives w.r.t. stochastic environments.

Evaluating the Efficiency of QD Algorithms
In this section, we consider a QD algorithm that uses a MAP-Elites grid or an unstructured archive, as most previously introduced QD approaches [3,7]. Such algorithms are usually compared based on three core archive properties: • Coverage: the number A of individuals in an archive A (or the number of filled cells when the container is a grid). It estimates the diversity present in A: The above metrics are often considered w.r.t. the number of evaluations. However, this comparison may not highlight the difference in time-complexity between the algorithms. Recent works on accelerating QD algorithms [19] have raised awareness of the importance of real-time-efficiency in QD optimization. Thus, we emphasize the importance of reporting each metric w.r.t time or the full execution time of each algorithm.

Studying Archive Properties
While the metrics defined above can be used to analyze the evolution of the archive performance, they only give a partial view of the content of the archive. For instance, two algorithms might generate archives with similar QD Scores, while one will have a different Coverage or a higher Max Fitness. To simplify the comparison of these different metrics in a single figure, we consider a plot that we call the Archive Profile. Archive Profiles have been used in prior work [12] to analyze QD archives. They represent on the -axis a threshold fitness value threshold , and on the -axis the coverage obtained when filtering out individuals whose score is lower than The function represented in an Archive Profile (see Fig. 2) expresses several properties and relationships with the three metrics from Section 3.1. First of all, this function is monotonically decreasing and there is a fitness threshold * such that: for all ≥ * , ArchiveProfile( ) = 0. That fitness threshold * is the Max Fitness of the archive; and the highest value of ArchiveProfile corresponds to the Coverage of the archive. Moreover, the area under the archive profile curve is proportional to the QD Score (see Appendix for proof). That means the archive profile captures more information than the QD Score: archives having different QD Scores will exhibit different archive profiles, but two different archive profiles can have same QD Score (illustrated in Figure 2).

Studying the Robustness to Stochasticity
Stochasticity is a key challenge when applying QD to deep neuroevolution. Each solution kept by a QD algorithm is evaluated once during the optimisation process to compute its fitness and BD, but this unique estimation is subject to stochasticity and might be inaccurate. Hence, the metrics defined in Section 3.1 and 3.2 also rely on this single estimation, subjecting them to the same inaccuracies. Here, we propose an expected fitness and expected BD for each solution kept by the algorithm as the average over a fixed number of reevaluations : Note that the algorithms do not have access to these expected values during the optimization process. These reevaluations are only used for the computation of metrics and do not count toward the evaluation budget of the algorithms. Most previous works considered = 50 [11,18]. We place the reevaluated solutions in a "Corrected archive" A based on these estimations and following the usual archive-addition rules. The metrics characterizing this  Corrected archive A constitute better estimations of the actual quality and diversity of the final collection. We refer to them as Corrected Coverage, Corrected QD Score, Corrected Max Fitness and Corrected Archive profile.
To further quantify the impact of stochasticity on the performance of QD algorithms in stochastic contexts, we also propose to study the loss induced by the reevaluation process: Loss MaxFitness (A) = MaxFitness(A) − MaxFitness(A) MaxFitness(A) A high-loss value indicates that the algorithm produces archives of individuals whose performance is not robust to stochasticity. These quantities should thus be minimized. We refer to these metrics as Coverage Loss, QD Score Loss and Max Fitness Loss. Figure 3 shows an example plot of all the metrics discussed in Section 3 for the Omni-directional Ant task defined in Section 2. We study the performance of two well-established QD algorithms: MAP-Elites [21] and CVT-MAP-Elites [31], and we also consider Random Search as an additional baseline for comparison purposes. Each experiment is replicated 10 times and we use 50 reevaluations to compute the Corrected metrics. All baselines and replications use the same machine to make time comparisons fair. The two QD baselines perform similarly according to the usual QD metrics (Section 3.1), and both outperform Random-Search, which is expected. However, the time-comparison indicates that CVT-MAP-Elites require additional time to reach similar performance, which is expected as the CVT mechanism require more computation time to determine the cell of an individual based on its bd. While the difference, in this case, stays minimal, this emphasizes the importance of considering real-time to compare QD algorithms. These two baselines also have similar Archive profiles, significantly better than the one of Random-search.

RESULTS AND DISCUSSION
The Corrected metrics (Section 3.3) show that MAP-Elites and CVT-MAP-Elites both produce archives of individuals whose performance is not robust to stochasticity. The values of the Loss metrics are high for these two algorithms, reaching 80% loss in both Coverage and QD Score. Interestingly, the few solutions discovered by Random search are more robust according to the Corrected and Loss metrics. An important problem in stochastic environments is what we refer to as "lucky" solutions: solutions that have been evaluated with a score higher than the average score they can expect to get in this environment. Random search has no mechanism to favor promising individuals, thus it does not favor individuals that have been lucky. On the contrary, MAP-Elites and CVT-MAP-Elites tend to maintain such individuals, which migh indirectly enforce lucky individuals over truly high-performing ones. Finally, the Corrected Max Fitness plots show that this metric has higher variations than the other Corrected metrics. The Max Fitness is computed on one-solution only, while the QD Score and Coverage rely on all solutions in the archive, which explains this higher variance. These results demonstrate that stochasticity remains a key challenge for QD algorithms applied to neuroevolution in RL domains.
These first results illustrate the challenges of our proposed benchmark. They also demonstrate the importance of the full range of metrics introduced to evaluate algorithms performance on these tasks. Still, an interesting direction of extension for this benchmark would be to broaden its focus by adding other types of environments such as manipulation tasks.

ACKNOWLEDGMENTS
This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) grant EP/V006673/1 project REcoVER.

A RELATIONSHIP BETWEEN QD SCORE AND THE AREA UNDER ARCHIVE PROFILE
We consider an archive A with a finite number of individuals A . We write ( ) 1≤ ≤ , all the distinct fitness scores of individuals present in A, sorted in ascending order: is a fixed interval including all fitness scores obtained by all individuals from all variants.
For all , we write ( ) the number of individuals whose fitness is equal to . Finally, ≥ ( ) denotes the number of grid cells, whose fitness is greater or equal to . Thus: In other words, ≥ ( ) is the coverage obtained if we only consider individuals whose fitness is higher or equal to .
The area under the archive profile curve can then be written: We now consider the normalised fitness scores , commonly used to compute the QD Score [7,25]: Then, we obtain the following identity: Thus, the area the under the archive profile curve can be expressed as follows: QD Score which shows that the area is proportional to the QD Score.