Evolving Populations of Diverse RL Agents with MAP-Elites
Authors: Thomas PIERROT
Arthur Flajolet
Venue: ICLR 2023 poster (2023)

Abstract: Quality Diversity (QD) has emerged as a powerful alternative optimization paradigm that aims at generating large and diverse collections of solutions, notably with its flagship algorithm MAP-ELITES (ME) which evolves solutions through mutations and crossovers. While very effective for some unstructured problems, early ME implementations relied exclusively on random search to evolve the population of solutions, rendering them notoriously sample-inefficient for high-dimensional problems, such as when evolving neural networks. Follow-up works considered exploiting gradient information to guide the search in order to address these shortcomings through techniques borrowed from either Black-Box Optimization (BBO) or Reinforcement Learning (RL). While mixing RL techniques with ME unlocked state-of-the-art performance for robotics control problems that require a good amount of exploration, it also plagued these ME variants with limitations common among RL algorithms that ME was free of, such as hyperparameter sensitivity, high stochasticity as well as training instability, including when the population size increases as some components are shared across the population in recent approaches. Furthermore, existing approaches mixing ME with RL tend to be tied to a specific RL algorithm, which effectively prevents their use on problems where the corresponding RL algorithm fails. To address these shortcomings, we introduce a flexible framework that allows the use of any RL algorithm and alleviates the aforementioned limitations by evolving populations of agents (whose definition include hyperparameters and all learnable parameters) instead of just policies. We demonstrate the benefits brought about by our framework through extensive numerical experiments on a number of robotics control problems, some of which with deceptive rewards, taken from the QD-RL literature. We open source an efficient JAX-based implementation of our algorithm in the QDax library. 

Published as a conference paper at ICLR 2023
EVOLVING POPULATIONS OF DIVERSE RL AGENTS WITH MAP-ELITES
Thomas Pierrot
Arthur Flajolet InstaDeep
InstaDeep
t. t-pierrot@ i Instadeep.com
fla jolet www.aeeeinstttep.....
ABSTRACT
Quality Diversity (QD) has emerged as powerful alternative optimization paradigm that aims at generating large and diverse collections of solutions, notably with its flagship algorithm MAP-ELITES (ME) which evolves solutions through mutations and crossovers. While very effective for some unstructured problems, early MR implementations relied exclusively on random search to evolve the population of solutions, rendering them notoriously sample-ineffiient for high- dimensional problems, such when evolving neural networks. Follow-up works considered exploiting gradient information to guide the search in order to address these shortcomings through techniques borrowed from either Black-Box Opti- mization (BBO) or Reinforcement Learning (RL). While mixing RL techniques with ME unlocked state-of-ie the-art performance for robotics control problems that require good amount of exploration, it also plagued these ME variants with limi- tations common among RL algorithms that ME free of, such hyperparame- ter sensitivity, high stochasticity as well as training instability, including when the population size increases as some components are shared across the population recent approaches. Furthermore, existing approaches mixing ME with RI. tend to be tied to specific RI. algorithm, which effectively prevents their use on prob- lems where the corresponding RL algorithm fails. To address these shortcomings, we introduce a flexible framework that allows the use of any RL algorithm and al- leviates the aforementioned limitations by evolving populations of agents (whose definition include hyperparameters and all learnable parameters) instead of just policies. We demonstrate the benefits brought about by framework through extensive numerical experiments on a number of robotics control problems, some of which with deceptive rewards, taken from the QD-RI literature. We open source an efficient JAX JAX-based implementation of our algorithm in the QDax library [
INTRODUCTION
Drawing inspiration from natural evolution's ability produce living organisms that are both di- verse and high-performing through competition in different niches, Quality Diversity (QD) methods evolve populations of diverse solutions to solve an optimization problem. In contrast to traditional Optimization Theory, where the goal is to find one solution maximizing given scoring function, QD methods explicitly use a mapping from solutions to a vector space, referred to as a behavior descriptor space, to characterize solutions and maintain a data structure, referred to repertoire, filled with gishhperffrming solutions that cover this space as much as possible, a process com- monly referred to as illumination. This new paradigm has led to breakthroughs over the past decade in many domains ranging from robotics control to engineering design and games generation (Gaier) al. 2018 Sarkar & Cooper 2021 Gravina al. 2019 Cully & Demiris 2018). There are num- ber of advantages to QD methods over standard optimization ones. Actively seeking and maintaining diversity population of solutions has proved be an effective exploration strategy, by reaching regions through a series of stepping stones, when the fitness function has no partic- ular structure (Gaier al., 2019). Additionally, having disposal diverse set of high high-performing solutions can be greatly beneficial to a decision maker (Lehman et al.) 2020), for instance because the scoring function may fail to model accurately the reality (Cully et al. 2015)
https:: http://ggtttuuuuc www.:ht.....aaacc...o.oo adapt intel liiiinent--- robot cs c

---

Published as a conference paper at ICLR 2023
MAP-ELITES (Mouret& & Clune 2015 has emerged one of the most widely used algorithm in the QD community for its simplicity and efficacy. It divides the behavior descriptor space into a discrete mesh of cells and strives to populate them all with solutions with matching behavior descriptors that maximize the fitness function as much as possible. This algorithm has been used in many applica- tions with great success, such as developing controllers for hexapod robots that can adapt damage in real time (Cully et al.) 2015). However, just like many evolutionary algorithms, it struggles on problems with high-dimensional search spaces, such as when evolving controllers parametrized by neural networks, as it uses random mutations and crossovers to evolve the population.
The breakthroughs of Deep Reinforcement Learning in sequential decision making problems prompted new line of work in the QD field to make the algorithms capable of dealing with deep neural network parametrizations. These new methods borrow techniques from either Black-Box Op- timization (BBO) or Reinforcement Learning (RI.) in order to exploit gradient information to guide the search. Methods based on BBO techniques (Colas et al.) 2020, Conti et al., 2018) follow the ap- proaches from earlier works scaling evolutionary algorithms to neuro-evolution, such as (allmann ct al. (017); Stanley & Miikkulainen (2002), and empirically evaluate gradients w.r.t. the parame- ters by stochastically perturbing them by small values number of times. Methods borrowing tools from RL, such as Nilssonn & Cully (2021); Pierrot et al. (2022). exploit the Markov- Deee--DDeiiin--Pieeeee structure of the problem and adapt off-policy RL algorithms, such as TD3 (Fujimoto et al.) 2018), to evolve the population. This often entails adding additional components to the evolutionary al- gorithm (e.g. a replay buffer, critic networks, hyperparameters of the RL agent, ...) and methods differ along the way these components are managed. RL-based MAP-ELITES approaches have out- performed other MAP-ELITES variants, and even sfate-of-the art RL methods, on a variety of robotics control problems that require a substantial amount of exploration due to deceptive or sparse rewards. However, the introduction of RL components MAP-ELITES has come with a number of downsides: (i) high sensibility to hyperparameters (Khadka et al.) 2019 Zhang et al., 2021), (ii) training instabil- ity, (iii) high variability in performance, and perhaps most importantly (iv) limited parallelizability of the methods due to the fact that many components are shared in these methods for improved sample-efficiency. Furthermore, existing RL-based MAP-ELITES approaches are inflexibly tied to a specific RI. algorithm, which effectively prevents their use on problems where the latter fails.
downsides are particularly problematic as they are some of the main advan- tages offered by evolutionary methods that are responsible for their widespread use. These methods are notoriously trivial to parallelize and there is almost a linear scaling between the convergence speed and the amount of computational power available, as shown in Lim et al. (2022) for MAP- ELITES. This is all the more relevant with the advent of modern libraries, such as JAX (Bradbury al. 2018), that seamlessly enable not only distribute the computations, including computations taking place in the physics engine with BRAX (Freeman et al., (021). over multiple accelcrators but also to fully leverage their parallelization capabilities through automated vectorization primi- tives, see Lim et al. | (2022), Flajolet et al. (2022); Tang et al. (202)). Evolutionary methods are also notoriously robust to the exact choice of hyperparameters, see Khadka et al. (2019), which makes them suited to tackle new problems. This is in stark contrast with RL algorithms that tend to require problem-specific hyperparameter tuning to perform well (Khadka et al., 2019; Zhang et al., 202T).
These
see|Lim
In order to overcome the aforementioned limitations of RI.-based MAP-ELITES approaches, we de- velop a new MAP-ELITES framework that 1. can be generically and seamlessly compounded with any RL agent, 2. is robust to the exact choice of hyperparameters by embedding meta- leaanilg loop within MAP-ELITES, 3. is trivial to scale to large population sizes, which helps alleviating stochas- ticity and training stability issues, without entering offline RL regimes priori by independently evolving populations of entire agents (including all of their components, such as replay buffers) in- stead of evolving policies only and sharing the other components across the population. Our method, dubbed PBT-MAP -LLIIES,, ELITES, builds on MAP-ELITES and combines standard isoline operators with pol-
icy gradient updates to get the best of both worlds. We evaluate PBT-MAP- -AP-ELITES when used with the SAC (Haarnoja et al. 2018) and TD3 (Fujimoto et al., 2018) agents on a set of five standard robotics control problems taken from the QD literature and show that it either yields performance on par with or outperforms state-of-the-ar MAP-ELITES approaches, in some cases by a strong mar- gin, while not being provided with hyperparameters tuned beforchand for these problems. Finally, open source an efficient JAX- -Ax-based implementation of our algorithm that combines the efficient implementation of PBT from Flajolet et al. (2022) with that of
from Lim et al. (2022). We refer to these two prior works for speed up data points compared to alternative implementations..
2

---

Published as a conference paper at ICLR 2023
2 BACKGROUND
Problem Definition. We consider the problem of generating repertoire of neural policies that are all nigh-performing for a given task while maximizing the diversity of policies stored in the reper- toire. More formally, we consider a finite-horizon Markov Decision Process (MDP) (S, A A, 7), where A is the action space, S is the state space, R: : A + R is the reward signal, T : A + S the transition function, and T is the episode length. neural policy corresponds to a neural net- work To S + ((A) where & E ④ denotes the weights of the neural network and D(A) is the space of distributions over the action space. At each time step, we feed the current environment state to the neural network and we sample an action from the returned distribution, which we subsequently take. Once the action is carried out in the environment, we receive a reward and the environment transitions to a new state. The fitness F (((T)) of policy TTe is defined the expected value of the sum of rewards thus collected during an episode. We denote the space of trajectories thus followed in the environment by 7 E S2. In the QD literature, diversity is not directly measured in the parameter space O, but rather in another space D, referred to as the behavior descriptor space or sometimes simply descriptor space, which is defined indirectly through a pre-specified and problem-dependent mapping & : Ω - D. A policy Te is thus characterized by rolling it out in the environment and feed- ing the trajectory to 4. With a slight abuse of notation, we denote by ((TT) the behavior descriptor of the policy Te. Diversity of repertoire of policies is measured differently across QD approaches.
MAP-Elites. MAP-ELITES uses a tesselation technique to divide the descriptor space into a finite number of cells, which collectively define a discrete repertoire. In this work, we use the Centroidal Voronoi Tessellation (CVT) technique (Vassiliades et al.. (201)) for all considered methods as has been shown to be general and easy to use in practice (Vassiliades et al.) 2017, Pierrot et al.) 2022). MAP-ELITES starts by randomly initializing a set of M policies. Each of these policies is then independently evaluated in the environment and they sequentially inserted into the repertoire according to the following rule. If the cell corresponding to the descriptor of the policy at hand is empty, the policy is copied into this cell. In the opposite situation, the policy replaces the current incumbent only if it has a greater fitness and is dropped otherwise. During each subsequent iteration, policies are randomly sampled from the repertoire, copied, and perturbed to obtain a new set of M policies which are then tentatively inserted into the repertoire following the aforementioned rule. Implementations of MAP-ELITES often differ along the exact recipe used to perturb the policies. The original MAP-ELITES algorithm (Mouret & Clune 2015) relies on random perturbations. In this work, we use the isoline variation operator (Vassiliades & Mouret 2018) that, given two parent policies, say policies 0₁ and 02, adds Gaussian noise N (0,
(0, 0n) to 02 and offsets the results along the line 02 - 01 by a magnitude randomly sampled from a zero-mean Gaussian distribution with variance (O 02) ). This strategy has proved to be particularly effective to evolve neural networks (Rakicevic ctt al. 202I.. Pseudocode for MAP-ELITES is provided in the Appendix.
BBO-based QD. To improve sample efficiency and asymptotic performance, methods such as ME- ES (Colas et al., 2020) use first-order updates to perturb the policies with the objective of both increasing the fitness of the policies in the repertoire and improving the coverage of the repertoire (i.e. the number of non-empty cells). To generate the updates, ME-ES use the Evolution Strategy from Salimans et al. (017). Specifically, after selecting a policy from the repertoire, its neural network parameters are perturbed stochastically with a small amount of Gaussian noise a number of times and the resulting policies are rolled out in the environment for a full episode. All of the collected samples are then used to empirically estimate gradients for a smoothed version around the starting policy of either (I) the fitness function, (2) a novelty function which is defined as the average Euclidean distance between the starting policy's ' behavior descriptor and its k nearest neighbors among all previously computed behavior descriptors, or (3) alternatively the fitness function and the novelty function to increase both quality and diversity, which is the version we use in this work (see the Appendix for the pseudocode). Note that similar strategies using the NS-ES family of algorithms exist, such as Conti et al. 22018), but these methods are outperformed by ME-ES (Colas al. 2020).
RL-ba QD. Using evolution strategies to guide the search with first-order updates improves upon random search but remains doomed to low sample-efficienee due to the need of rolling out signif- icant number of policies over entire trajectories to get reasonably accurate gradient estimates. More recent techniques, such QD-PG (Pierrot et al.; 2022) and REA-MAP-ELITER (Nilsson & Cully) 202I]. exploit the MDP structure of the problem and leverage policy-gradient techniques from RL as well as off-policy extensions for improved sample efficiency and better asymptotic convergence.
3

---

Published as a conference paper at ICLR 2023
Both QD-PG and PGA-MAP-ELITES build on the TD3 agent (Fujimoto et al. 2018 ELITES combines random mutations derived through the isoline variation operator with mutations obtained through policy gradient computations. QD-PG introduces the notion of a diversity reward, a signal defined at the timestep-level to drive policies towards unexplored regions of the behavior descriptor space, which makes it possible to leverage the RI. machinery to compute policy gradients to increase the diversity of the population, referred to as diversity policy gradients, in addition to the standard policy gradients to increase the fitness of the policies, referred to quality policy gradi- ents. At each MAP-ELITES iteration, half of the selected policies are updated using quality policy gradients and the other half are updated using diversity policy gradients. In contrast to PGA- MAP- ELITES, QD-PG does not relies on random search updates. Both QD-PG and PGA-MAP-ELITE, use single shared replay buffer where all the transitions collected when evaluating the agents are stored and from which batches are sampled to compute policy gradients.
PGA-MAP-
Critic networks are managed differently by each algorithm. QD-PG uses two different sets of critic parameters, one for quality rewards and one for diversity rewards, that are shared across the popu- lation and both are updated any time a policy gradient is computed. PGA-MAP-ELITES maintains a greedy policy and its associated critic which are updated independently of the rest of the repertoire. The greedy policy is regularly inserted in the repertoire and the critic is used to compute policy gradients updates for all other policies but is only updated using the greedy policy.
These precise design choices not only make PGA-MAP-ELITES and QD-PG difficult to distribute efficiently but they also harm the flexibility of these methods. For instance, if one would like to replace TD3 by another popular off-policy algorithm such as SAC, which is known to perform better for some environments, numerous new design choices arise. For instance for SAC, one would have to decide how to handle the temperature parameter and the entropy target within the population. Furthermore, while sharing critic parameters and using a single replay buffer was motivated by a desire for greater sample efficiency, this introduces new issues when scaling these methods. For instance, as the number of policies updated concurrently at each iteration increases we get closer to an offline RI. setting, which is known to harm performance, since all policies share the same replay buffer. Conversely, as the size of the repertoire increases, any single policy stored in the repertoire is updated all the less frequently than the critic which may cause them to significantly lag behind over time. Finally, both QD-PG and provided for TD3 while it is known that tuning these values for the problem at hand is necessary to get good performance. This effectively puts the burden on the user to tune hyperparameters for TD3 as a preliminary step, which limits the usability of such methods in new settings. Pseudocodes for QD-PG and DEEA-MPPELLTI are provided in the Appendix.
assume that good hyperparameters
METHOD
In order to overcome the limitations of RL-based QD methods identified in the last section, we revisit the neuro-evolution problem defined in Section (and introduce new algorithm, dubbed PBT-MAP- ELITES, that evolves populations of agents as opposed to populations of policies. An agent is defined by a tuple (0, d, h) where 0 denotes the policy parameters, á denotes all other learnable parameters of the agent (c.g. critic parameters and target critic parameters), and h denotes its hyperparameters (e.g. learning rates and magnitude of the exploration noise). As in the original formulation, we assume that the fitness and behavior descriptor functions depend only on the policy, i.c. on 0. The learnable parameters and the hyperparameters are only used when agents are updated, PBT-MAP- ELITES internally uses a policy-search- based RL algorithm which can be selected freely by the user. In particular, it may be on-policy or off-policy.
PET-MAP-ELITES maintains a MAP-ELITES repertoire as well as a population of P agents. The population randomly initialized (including the hyperparameters), evaluated, copied and inserted into the repertoire. We also initialize P replay buffers if the underlying RL algorithm makes use of them. Additionally, a batch of agents is sampled from the repertoire and a variation operator is applied to obtain M offspring that are also evaluated and inserted into the repertoire as part of the initialization phase. Then, the algorithm proceeds in iterations, each of which consists of two consecutive steps: 1. population update and 2. MAP-ELITES repertoire update.
Population Update. To update the population of agents, we use the following strategy inspired from Jaderberg et al. (017). We first rank all agents in the population by fitness based on the evaluation
4

---

Published as a conference paper at ICLR 2023
Irontion Rapartion
Environments
Population
Elice Repertlre
Hyperporondtors
Wright
Walker-Uni
Arbiii
Holtzheeta-Uii
Sumppiing In thike nop oratin
Repertaire
Art-Thepp
Hamaneld Thap
Random Varlations
Figure 1: Left Panel. The set of QD-RL environments used evaluate all methods. All vironments are implemented using the BRAX simulator and are available in the QDAX suite. In WALKER2D- UNI, ANT-UNI, and HALFCHEETAH-UNG the goal is to learn control the correspond- ing robot to run as fast as possible with gaits that are as diverse as possible. In ANT-TRAP and HUMANOID-TRAP, the robot should travel as far as possible along the x-axis direction, which en- tails sidestepping the trap get the highest possible return thus putting the exploration capabiliiiess of considered methods to test. Right panel. Illustration of the PET-MAP-ELITES algorithm. PBT- MAP-ELITES maintains a population of agents (policy parameters, other learnable parameters as well as hyperparameters) and MAP-ELITES repertoire agents. The repertoire update, generating more diversity, and the population update, improving the fitness of the policies, are intertwined.
that took place at the end of the last iteration. Agents that are in the bottom p% of the population replaced by agents sampled uniformly from the top n% of the population, with 0 < p < n < 1. We also randomly select A% of the agents in the population among the ones that top n% nor in the bottom p% and we replace them by agents randomly sampled from the current MAP-ELITES repertoire. All other agents remain unchanged. This mechanism allows potentially lower-performing, but more diverse, individuals from the repertoire to enter the population while maintaining high-performing agents alive. When agents are replaced, new hyperparameter values are sampled uniformly from specifee ranges. The agents' policy parameters as well as all other learnable parameters are subsequently trained for S steps, using the user-selected RL algorithm. If needed, the collected experience is stored inside the replay buffers. In contrast to PGA-MAP- ELITES and QD-PG, we closely follow the general recipe followed by most RI. algorithms and only add the experience collected during training. in exploration mode, to the replay buffers while the experience collected during evaluation, exploitation mode, is discarded. Additionnaly, note that the agents are trained independently from one another, which makes it trivial to parallelize the most computationally intensive part of this step. This is in stark contrast with other MAP-ELITES- RL methods that share some parameters across the population, e.g. the critic parameters for QD-PG and SAA-MAP-ELITES, which are typically updated concurrently by all agents.
neither in the
Repertoire Update. Once the agents in the population have been trained, they evaluated and inserted into the repertoire. Then, just like during the initialization phase, a batch of agents is randomly sampled from the repertoire and undergoes a variation operator obtain A offspring which are evaluated and inserted into the grid. As in PGA-MAP-ELITES, the variation operator is meant increase the descriptor space coverage but we have also observed that this process stabilizes the algorithm as whole. In order to define variation operator that can be used with agents, as opposed policies, we deal with variations over the policy and learnable parameters separately from variations over the hyperparameters. Specifically, an isoline operator is applied to policy and other learnable parameters while the offspring simply inherit the hyperparameters of one of their parents. While more sophisticated strategies could be investigated, we have observed that this simple mechanism works well in practice in our experiments.
Observe that optimization of the quality well as the diversity of the policies happens at two dif- ferent levels in PET-MAP-ELITES Quality is encouraged through both the elitist population update and the repertoire insertion mechanism. Diversity is induced through both the addition of agents from the repertoire to the population and the use random variation operators at each iteration. The pseudocode of the algorithm is provided in the Appendix.
5

---

Published as a conference paper at ICLR 2023
4 LITERATURE REVIEW
Quality Diversity. QD methods aim to simultaneously maximize diversity and performance. Among existing options, MAP-ELITES and Novelty Search with Local Competition (NSLC) are two of the most popular QD algorithms. NSLC builds on the Novelty Search algorithm (Lehman & Stanley) 2011] and maintains an unstructured archive of solutions selected for their high performance rela- tive to other solutions in their neighborhoods while MAP-ELITES relies tesselation technique to discretize the descriptor space into cells. Both algorithmss rely extensively on Genetic Algorithms (GA) to evolve solutions. As a result, they struggle when the dimension of the search space in- creases, which limits their applicability. These approaches have since been extended using tools from Evolution Strategies (ES) improve sample efficiency and asymptotic performance over the original implementations based on GA (Salimans et al.) 2017). CMA-MAP-ELITES (Fontaine et al.) 2020 relies on Covariance Matrix Adaptation (CMA) to speed up the illumination of the descriptor space. NSRA-ES and NSR-ES (Conti et al. 2018) build on recent ES tools to improve QD meth- ods' exploration capabilities on deep RL problems with deceptive or sparse rewards. ME-ES (Colas) it al. 2020) introduces alternate ES updates for quality and diversity in order to solve deep RL problems with continuous action spaces that require a good amount of exploration. While Essbased approaches improve over GA-based ones, they are still relatively sample-ineffciient due to the fact that they need to roll out a large of number of policies over entire trajectories to empirically estimate gradients with reasonable accuracy. Several recent methods propose to exploit analytical gradients when this is possible instead of estimating them empirically. DQD (Fontaine & Nikolaidis, (202T) builds mutation operator that first computes gradients of the fitness and behavior descriptor func- tions at the current solution and carry out a first-order step by summing the gradients with random coefficients. Tjjnaka al. (2022) applies the same technique deep RL problems with continuous action spaces. PGA-MAP-ELITH
(Nilsson & Cully) (02T) and QD-PG (Pierrot et al.) (022) exploit the MDP structure of the problems to compute policy gradients using the TD3 algorithm, outper- forming all QD competitors for deep RL problems with continuous actions. However, both methods are tied single RI. algorithm and are highly sensitive to the choice of TD3 hyperparameters.
Population Based Reinforcement Learning. Our work has different motivations than classical RL algorithms as we do not aim to find policy than achieves the best possible return but rather to illu- minate a target descriptor space. However, we share common techniques with Population-Baseer RL (PBRI.) algorithms.
this field, the closest method to ours the Population- Based-Trainingg Training (PBT) algorithm (Jaderberg et al.) 2017) which uses genetic algorithm to learn the hyperparameters of population RL agents concurrently to training them. While PBT-MAP-ELITH
ilar strategies to update the population of agents, PBT only seeks the ELITES and PBT use sim- agent by extracting the best one from the final population while EET-MAP-LLITES aims to find a diverse col- lection of high-performing agents. Several methods such as CERL, ERL, and CEM-RL (Pourchot & Sigaud 2019: Khadka & Tumer] [0188: Khadka et al.] 2019) combine ES algorithms with PBRL methods to improve the asymptotic performance and sample efficiency of standard RL methods. Other methods, such as DvD (Parker-Holder et al., (020) and P3S-TD3 (Jung et al.) 2020), train pop- ulations of agents and add terms in their loss functions encourage the agents to explore different regions of the sate-aaciinn space but always with the end goal of maximizing the performance of the best agent in the population. Flajolett et al. (2022) show how to vectorize computations across the population to run PBRL. algorithms as efficiently as possible on accelerators through the use of the JAX library. Lim et al. (2022) introduced similar techniques to accelerate MAP-ELITES through the evaluation of thousands of solutions in parallel with JAX. In this study, we build on both of these works and implement MAT--AP-ELITESS in the JAX framework to make it fast and scalable.
5 EXPERIMENTS
Environments. We use five robotics environments that fall into two categories:
1. IALFCHEETAII-NNI WALKER2D-UNI and ANT-UNI are environments widely used in the QD community to evaluate algorithm's 's ability to illuminate complex descriptor space, see for in- stance Cully et al. (2015): Nilsson& & Cully (22TI: Tjanaka et al. (0022). In these environments, the goal is to make a legged robot run as fast as possible along the forward direction while optimizing for diversity w.r.t. the robot's 's gaits, indirectly characterized as the mean frequencies of contacts between the robots' legs and the ground. This last quantity defines the behavior descriptor for these environ-

---

Published as a conference paper at ICLR 2023
Na#CCheeta-Uni
Waller26-0ni
Antirap
Hananddrrpp
0277
4002
6330
6000
5300
4302
5060
3000
2005
3002
12.00
2303
2000
1000
1000
1000
1060
03
14
13
20
43
160303
2.
0.6
1.3
0.5
03
03
6.
6.5
16
6.5
1/2
13
1.3
Sietonmentstaps
Enviromment Staps
Ervironmntt stoas
Enirumment SUaS
PGIMAA-Eiitss
PBT-MAP-Eites (SAC)
PBT-MOP-Elites (1D3)
QDPG
Performance comparison of PBT-MAP-ELITES with baselines on the basis of standard metrics from the QD literature for five environments from the QDAX suite (which is based on the BRAX engine). We benchmark two variants of PBT-MAP- and one where it is composed with TD3. All methods trained with total budget of N 1.5e8 environment timesteps. Experiments are repeated over 5 runs with different random seeds and the medians (resp. first and third quartile intervals) are depicted with full lines (resp. shaded areas).
Figure 2:
one where it is composed with SAC
ments while the reward at each timestep is the velocity of the robot's center of gravity projected onto the forward direction.
ANT-TRAP and HUMANOID TRAP are environments with deceptive reward signals used in the QD-RI. literature evaluate algorithm's 'ss ability solve complex continuous control problems that require a good amount of exploration, see see [Colas et al. (2020); Conti et al. (2018): Pierrot et al.) (2022). In these environments, the goal also make the legged robot run as as possible in the forward direction, though with the additional difficulty that the robot is initially facing a trap. As result, following the reward signal in greedy fashion leads the robot into the trap. The robot must explore the environment and learn to go around the trap, even though this is temporarily suboptimal, these environments. the behavior descriptor is defined as the
order to obtain higher returns. position of the robot's s center of gravity at the end of an episode. All of these environments are based on the BRAX simulator (Freeman et al. 2021) and are available in the QDAX suite (Lim al., 2022).
methods, namely MAP-ELITES, ME-ES, PGA-MAP-ELITES as well as QD-PG. For these experiments, we benchmark two variants of PBT-MAP-ELITES: one where it is composed with SAC and one where it is composed with TD3. For the sake of faimeess, we use the same values for parameters that are used by multi- ple methods. In particular, all MAP-ELITES-basee use CVT with the same parametrization to discretize the behavior descriptor space into 1024 cells. Similarly, when variation operator needed, we always the isoline operator with the same pa-
Setup. We compare PBT-MAP-ELITE ELITES to state-of-the-art MAP-ELITES-bane
methods maintain repertoire of 1024 cells and

---

Published as a conference paper at ICLR 2023
ritrees Grld 40me0d stape!
Fitraen 77 megs)
Fimmze shepo!
Pitrass D 2.0 stspal
Exploration Molee Gnd L8, 10e-ds stape)
Explaration Nost one 16 (2.20 caeps
Expioration Horee ond Joade (tep
Expleratios heion and (Jab stepel
Figure 3: Visualizations of the performance and hyperparameters of the agents stored in the MAP- ELITES repertoire of PBT-MAP-ELITES (TD3) at different time points during training on the ANT- TRAP environment. The first row corresponds to the fitnesses of the agents. The second row corre- sponds to the exploration noise added by the agents to the actions returned by their policies when collecting experience in exploration mode. The third row corresponds to the discount factor y used by the agents. Snapshots of the repertoire are taken at uniformly-spacee intervals during training.
rameters 01 0.005 and 02 0.05. All policy and critic networks are implemented by two MLPS layers with 256 hidden neurons per layer. For methods relying on the TD3 agent, the hyperparam- eters used are the ones introduced in the original paper for MuJoCo environments. Pseudocodes and parameter values for all algorithms under study are provided in the Appendix.
Additionally, we compare PBT-MAP-ELITES to the PBT algorithm (Jaderberg et al., 2017) (pseu- docode provided in the Appendix) when it is used to optimize populations of SAC agents. Both PET-MAP-ELITES and PBT evolve populations of 80 agents and use the same ranges for the hyper-
parameters. All policy and critic networks are implemented by two-layer MLPs with 256 hidden and QD-PG. Furthermore, the parameters
neurons per layer, just like for TD3 for of all agents in the population are identically initialized. For PBT-MAP-ELITES (resp. PBT), agents in the bottom p = 0.2 (resp. p = 0.4) fraction the population (in terms of fitness) are replaced by agents sampled from the top k = 0.4 of the agents that are neither in the bottom 20% nor in the top 10% of the population are replaced by agents randomly sampled from the MAP-ELITES repertoire. All other parameters and design choices are identical for these two methods.
0.1 fraction of the population. For PBT-MAP-ELITES,
fraction
Metrics and fair comparisons. Following standard practice in the QD literature, we monitor three metrics used to evaluate the performance of collection of policies during training. 1. We measure the maximum fitness, defined as the maximum expected return across policies in the collection. 2. We measure the coverage over the descriptor space, computed as the number of cells that have been filled. 3. We measure the QD-score, computed as the sum of fitnesses attained by the policies stored in the repertoire. For this last metric to be meaningful, we assume that fitnesses are all non-negative. If not, a positive value is added to all fitnesses to enforce it. In any case, this value is the same for all methods for fairness. Since some of the metries require repertoire to be properly defined, we introduce a passive repertoire for PBT to be able to evaluate on the same basis as the other methods. Specifically, at the end of each PBT iteration, the population of agents generated by PBT is evaluated and inserted into a repertoire. For each method, we report the evolution of these metrics w.r.t. the total number of interactions with the environment. Note that while the evaluation of an agent contributes to the total number of interactions for MAP-ELITES-DE -base methods, this is not the case for PBT as the evaluations are only used to estimate the metries for this method.
RESULTS AND DISCUSSION
Statistics QD metrics are reported for all environments and methods on Figure 2
8

---

Published as a conference paper at ICLR 2023
Performance comparison to other MAP-ELITES-based methods. We observe that PBT-MAP- ELITES (SAC) is the only method able to solve HUMANOID-TRA. within the allocated timestep budget, outperforming all the other methods by a significant margin. HUMANOID-TRAP is chal- lenging environment as obtaining high returns requires not only to get the humanoid robot to run, which is a challenging continuous problem in itself, but also to learn sidestep the trap in spite of a deceptive reward signal. This environment, introduced in Colas et al. (2018). has remained out of reach for MAP-ELITES-baSee methods, setting aside ME-ES which solves it with a timestep budget two orders of magnitude higher. Interestingly, the maximum fitness remains below 2000 for TD3- based methods, which means they were not able to get the humanoid robot to run all. This is a testament to the difficulty of the problem. Recall that TD3 was not able to solve the MuJoCO-based version of the Humanoid environment the original paper that introduced this algorithm (Fuji) moto et al. 2018). A careful tuning of the algorithm design choices and hyperparameters, carried out in a later study, was required to get TD3 to perform well on this environment. Setting aside the WALKER2D-UN. environment, note that PBT- a significant margin for the maximum fitness metric, or performs on par with MAP-ELITES-basse methods. Interestingly, the SAC variant of PET-MAP-ELITES often performs better than the TD3 variant, but not always. On a side note, we also observe that ME-ES surprisingly gets outperformed by all MAP-ELITES competitors, including the original MAP-ELITES algorithm, in all environments. This can be explained by the fact that ME-ES uses 1000 evaluations (i.e. 1e6 timesteps) to update a single policy. As a result, for a repertoire consisted of 1024 cells and with budget of 1.5e8 timesteps, the maximum coverage that can be reached by ME-ES is 15% only. In the original study, methods with a budget of 1e10 timesteps.
(SAC) either outperforms, often by
ME-RS manages to outperform other MAP-EL
Performance comparison to PBT. We observe that PBT outperforms the SAC variant of PBT-MAP- ELITES in terms of maximum fitness on HALFCHEETAH and ANT- This is expected as: (1) these environments do not require significant amount of exploration, (2) PBT only aims to maxi- mize the maximum fitness, and (3) PBT-MAP-ELITES aims to maximize both the maximum fitness and the policies' diversity. However, we observe the opposite trend on ANT-TRAP and HUMANOID- TRAP where significant cxploration is required to achieve high returns given the deceptive nature of the reward signal. We conclude that optimizing for diversity turns out to play crucial role for these two environments. As expected, PBT-MAP-EE -A--LLL-EE outperforms PBT in terms of coverage and QD-score in all environments, setting aside HUMANOID-TRAP. The seemingly unexpected results observed on JUMANNODD-TRAP stem from the fact that covering the behavior descriptor directly correlates with exploration of the (I, space, which is required achieve high returns in this environment due to the presence of the trap.
Repertoire interpretation. By visualizing the evolution of the fitnesses and hyperparameters of the agents stored in PET-MAP-ELITES' repertoire at different time points during training, see Figure we observe that PBT-MAP-ELITES evolves locally-coherent (w.r.t. the descriptor space) maps of hyperparameters that change significantly during training. In particular, we remark that PBT-MAP ELITES dynamically increases the amount of exploration noise of the TD3 agents to boost exploration when needed to go around the trap and decreases this parameter once the trap has been sidestepped to focus on getting high returns. This mechanism gives a significant advantage to PBT-MAP-ELITED over QD-PG and PGA- MAP-ELITES, for which this parameter is set to a constant value.
7 CONCLUSION
In this work, revisit the standard formulation of the QD neuro-evolution problem by evolving repertoires of full agents (including hyperparameters among other things) as opposed to only poli- cies. This extension brings flexibility compared to existing frameworks it allows to combine any RL algorithm with MAP-ELITES in a generic and scalalable fashion. This formulation also al- lows us dynamically learn the hyperparameters of the underlying RL agent as part of the regular training process, which removes significant burden from the user. Surprisingly, we observe that learning the hyperparameters improves both the asymptotic performance and the sample efficiency in practice for most of the environments considered in this work. Our method is the first to solve the HUMANOID-TRE TRAP environment with less than one billion interactions with the simulator, to be com- pared with tens of billions of interactions for state-of-the-art QD methods. We hope that this work constitutes one more step towards bridging the gap between Neuro-Evolution and Reinforcement Learning, combining the best of both worlds in simple framework.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
James Bradbury. Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Miin MMnne,, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. wtw.bl/leemo/ogoeeececoo
Cédric Colas, Olivier Sigaud, and Pierre-Yve Oudeyer. GEP-PG: decoupling exploration and ex- ploitation in deep reinforcement learning algorithms. In Proceedings of the International Confer- ence on Machine Learning, volume 80, pp. 1038-1047, 2018.
Cédric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune. Scaling map-elites to deep neu- roevolution. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 67-75, 2020.
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via pop- ulation of novelty-seeking agents. In Advances in Neural Information Processing Systems, pp. 5027-5038, 2018.
Antoine Cully and Yiannis Demiris. Hierarchical behavioral repertoires with unsupervised descrip- tors. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 69-76, 2018.
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that adapt like animals. Nature, 521(7553):503-507 2015.
Arthur Flajolet, Claire Bizon Monroc, Karim Beguir, and Thomas Pierrot. Fast population-based reinforcement learning on a single machine. In Proceedings of the International Conference on Machine Learming, pp. 6533-6547, 2022.
Matthew Fontaine and Stefanos Nikolaidis. Differentiable quality diversity, In Advances in Neural Information Processing Systems, volume 34, pp. 10040-10052, 2021.
Matthew C Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K Hoover. Covariance ma- trix adaptation for the rapid illumination of behavior space. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 94-102, 2020.
Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem. Brax-a differentiable physics engine for large scale rigid body simulation. arXiv preprint arXiv:2106.15 13281, 2021.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. Proceedings of the International Conference on Machine Learning, pp. 1587- 1596, 2018.
Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. Data-efficient design exploration through surrogate-assisted illumination. Evolutionary computation, 26(3):381-410, 2018.
Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. Are quality diversity algorithms better at generating stepping stones than objective-based search? Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 115-116, 2019.
Daniele Gravina, Ahmed Khalifa, Antonios Liapis. Julian Togelius, and Georgios N Yannakakis. Procedural content generation through quality diversity. In 2019 IEEE Conference Games (CoG), pp. 1-8, 2019.
Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta. Pieter Abbeel, et al. Soft actor-critic algorithms and appli- cations. arXiv preprint arXiv:1812.05500 2018.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojeiech M Czamecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population- train- ing of neural networks. arXiv preprint 171 2017.
10

---

Published as a conference paper at ICLR 2023
Whiyoung Jung, Giseung Park, and Youngchul Sung. Population gigiiattionnuiedd parallel policy search for reinforcement learning. In Proceedings of the International Conference on Learning Representa- tions, 2020.
Shauharda Khadka and Kagan Tumer. Evolution-guicee policy gradient in reinforcement learning. In Neural Information Processing Systems, volume 31, 2018.
Shauharda Khadka, Somdeb Majumdar, Tarek Nassar, Zach Dwiel, Evren Tumer, Santiago Miret, Yinyin Liu, and Kagan Tumer. Collaborative evolutionary reinforcement learning. In Proceedings of the International Conference on Machine Learning, pp. 3341-3350, 2019.
Joel Lehman and Kenneth O Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary computation, 19(2):189-223, 2011.
Joel Lehman, Jeff Clune, Dusan Misevic, Christoph Adami, Lee Altenberg, Julie Beaulieu, Peter J Bentley, Samuel Bernard, Guillaume Beslon, David M Bryson, et al. The surprising creativity of digital evolution: A collection of anecdotes from the evolutionary computation and artificial life research communities. Artificial life, 26(2):274-306, 2020.
Bryan Lim, Maxime Allard, Luca Grillotti, and Antoine Cully. Accelerated quality-diverse for robotics through massive parallelism. arXiv preprint arXiv:2202.01258 2022.
Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04999, 2015.
Olle Nilsson and Antoine Cully. Policy gradient assisted map-elites. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 866-875, 2021.
Jack Parker-Holder, Aldo Pacchiano, Krzysztof Choromanski, and Stephen Roberts. Effective di- versity in population-based reinforcement learning. In Neural Information Processing Systems, volume 33, pp. 18050-18066 18062, 2020.
Thomas Pierrot, Valentin Macé, Félix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Be- guir, Antoine Cully, Olivier Sigaud, and Nicolas Perrin-Gilbert. Diversity policy gradient for sample efficient quality-diversie optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1075-1083, 2022.
Aloïs Pourchot and Olivier Sigaud. CEM-RL: combining evolutionary and gradient-based methods for policy search. In Proceedings of the International Conference on Learning Representationss 2019.
Nemanja Rakicevic, Antoine Cully, and Petar Kormushev. Policy manifold search: Exploring the manifold hypothesis for diversity- neuroevolution. In Proceedings of the Genetic and Evo- lutionary Computation Conference, pp. 901-909, 2021.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv: 03864, 2017.
Anurag Sarkar and Seth Cooper. Generating and blending game levels via quality-diverse in the latent space of a variational autoencoder. Proceedings of the International Conference on the Foundations of Digital Games, pp. 1-11. 2021.
Kenneth Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topolo- gies. Evolutionary computation,, 10(2)99--277, 2002.
Yujin Tang, Yingtao Tian, and David Ha. Evojax: Hardware--ccellratte neuroevolution. In Pro- ceedings the Genetic and Evolutionary Computation Conference Companion, pp. 308-311, 2022.
Bryon Tjanaka, Matthew C Fontaine, Julian Togelius, and Stefanos Nikolaidis. Approximating gradients for differentiable quality diversity in reinforcement learning. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1102-1111, 2022.

---

Published as a conference paper at ICLR 2023
Vassiiis Vassiliades and Jean- Mouret. Discovering the elite hypervolume by leveraging in- terspecies correlation. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 149-156, 2018.
Vassilis Vassiliades, Konstantinos Chatzilygeroudds, and Jean-Baptiste Mouret. Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Transactions on Evolutionary Computation, 22(():623 630, 2017.
Baohe Zhang, Raghu Rajan, Luis Pineda, Nathan Lambert, André Biedenkapp. Kurtland Chua, Frank Hutter, and Roberto Calandra. On the importance of hyperparameter optimization for model-based reinforcement learning. International Conference on Artificial Intelligence and Statistics, pp. 4015 2021.
12

---

Published as a conference paper at ICLR 2023
A
PSEUDOCODES FOR ALL ALGORITHMS
Algorithm 1: PBT- MAP-ELITES
Given:
M: MAP-ELITES repertoire
N No: maximum number of environment steps
M E N": number of isoline-variation offsprings per iteration
N": size of the population of RL agents
S E N number of training steps per iteration agent
p, k n ]0,
PBT proportions
an RL agent template
F()): fitness function
(-): hehavior descriptor function
// ialiizaiinon Randomly initialize P + MM agents following the chosen RL template ((TT, di. h: 1ssssss
Run one episode in the environment using each of (IT, IsisPPM to evaluate (F D)sssP4M and (Ib(TT, Sigggp4M.
Insert (( Pc, b.))ssigP+M M based on (F(Te, )) ssssp4 and (#(me) (((m)))) ))sigr
Initialize P replay buffers (B.)s using the data collected respectively by each agent during the initial evaluations (if replay buffers are used by the RL agent).
Main lcep
Initialize Thepps: total number environment interactions carried out so far, to O.
while nares S N do
// Pepulation Update
Re-order the agents i= 1,... P in increasing order of their fitnesses (F(TTe ))
Update agents 1, .pP by copying andomly-sample agents from i n)P.- -.p,,,., P
copy the replay buffers accordingly (if replay buffers are used by the RL agent). Sample new hyperparametens for agents i 1, ... .pP.
Sample &P indices (4; (f))ısiger uniformly without replacement from {pP +1 1,... ,( n) P - 1}. 3,, j S kP by agents Train agents i 1, independently for steps using agent template, sampling data from the replay buffers if they are used by the RL agent.
Replace agents
(osioomom-uiooomly) sampled from M.
// Repertcire Update
Run one episode the environment using each of (Ie, diSiSP to evaluate (F(To, Disige and ( ))gsis..
Insert ([TT,, Øs, sis) in Mi based on (F(TT, Digig and (f(T))))sis) Sample uniformly 2M agents from M.
Copy them and apply isoline variation obtain M offsprings ((mo, di, h:)) Run one episode the environment using each of (me, Pee))p to evaluate (F (Pe)))
and (#(T,,) (((Te))) )) Insert ((To,, Øs, Ps)g) in M based on (F(rs, P<igg) and (<(SP.))
Update Taseps.
end
13

---

Published as a conference paper at ICLR 2023
Algorithm 2: MAP-ELITES
Given:
M: MAP-ELITES repertoire
N": maximum number of environment steps
M E N': number of offsprings per iteration
F()): fitness function
(()): behavior descriptor function
// Initiall illiziiion
Randomly initialize M policies (mo,)
Run episode in the environment using each of (ITe, IisiS evaluate (F(mo,))ssss) and (TTT ))SsMM.-
Insert (Te. JSsEgM in based on Sisg and (T(TT,)) Sissa..
// Main loop
Initialize Mexeps the total number of environment interactions carried far, O.
while napps N
Randomly sample 2M policies from M.
Copy them and apply isoline variations to obtain M new policies (To.)SSiMM.
Run one episode the environment using each of (se,, S evaluate (F Sesegar and (1( MM
Insert (me,))sss M in based on (Ssss and (#( sMs.
Update Rasaps-
end
14

---

Published as a conference paper at ICLR 2023
Algorithm 3: PGA-MAP-ELITES
Given:
M: MAP-ELITES repertoire
N": maximum number of environment steps
M E N": number of offssrings per iteration
Sc E N number of TD3 training steps used to update the shared critic per iteration
Sp E N number of TD3 policy update steps per iteration per policy
TD3 hyperparameters
P(-): fitness function
((): behavior deseriptor function
Initialization
Initialize a replay buffer
Randomly initialize M policies (mo,) JIsEMM
Run one episode in the environment using each of (me, JisigM to evaluate (F(oo))ssssM and (Ib(TO,)) )M Insert (Te, J Mr based (F'(Te, M and (9(T )isssM.
Update with transition data collected during the initial evaluations.
Initialize the critic Qs. the target critic Qør the greedy policy wa. and the target greedy policy me.
Main ccop
Initialize nespps total number of environment interactions carried out so far, to O.
while Narpp S N do
// Update the shared critic alengside the greedy policy
Carry out S. TD3 training steps update Qs Qo', and ma (sampling batches of data from B).
// Generate new offspri ngs using the isoline variation operator Randomly sample M policies from M. Copy them and apply isoline variations obtain M/2 policies (To.)
// Generate new offsprings using TD3 policy-gradient updates Randomly sample M/2 - policies from M (T=)a//24VMM Carry out Sp TD3 policy gradient steps for each of them independently (sampling batches of data from BB)
// Update the repertoire
Assign T0 Ty-
Run one episode in the environment using each of (mT, )isigM a to evaluate (F(ro.)) and (1b(T,))) MM Insert (Ne, )isss M based (F(mee SssssM Mr and (#(m,, sas.
Update with transition data collected during the evaluations of all M new policies.
Update nacpss
end
15

---

Published as a conference paper at ICLR 2023
Algorithm 4: ME-ES
Given:
M: MAP-ELITES repertoire
N": maximum number of environment steps
S N": number of consecutive gradient steps for given policy
Ngrad E N number of evaluations for gradient approximations
Nunt E N number of randomly-initialin policies used to initialize M
σ > O: standard deviation of the normal distribution used to perturb parameters for gradient
approximations
?) 0: learning
A: archive of behavior descriptors
N(.-): novelty function that takes input a behavior descriptor as first argument and second argument
F()): fitness function
((): behavior descriptor function
// Initialization
Randomly initialize Num policies (To, )ussss Nuu
Run one episode the environment using each of (TT, Disis to evaluate (F(TT, (ISTs,))sssNn... and (Ib(T,,) )lisigNua
Insert (Ne, (1sss Mink in M based (F(To, (1ss))) and (#( Sases
Add (#(Te)) 1515s Nan to
// Main 1oop
Initialize Maspps the total number of environment interactions carried out far, to 0.
Initialize Ryrds, the total number of gradient steps carried so far,
use novelty true
while Narps S N do
if Rynd = 0 mod S then
// Decide if should omtimize for novelty litness.
Set use_novelty
with probability 0.5 and to false otherwise.
// Sample high-performing policy from M
if use novelly then
Sample policy wo M uniformly from the set of five policies with the highest novelty A)
else
Sample, with probability 0.5, policy ma E M from the set of two policies with the highest fitness ((TT)) or from the last five updated policies.
end
end
Update the current policy using & gradient approximation Sample (0.) Navd (0((0 small perturbations of the current policy's parameters. Run one episode in the environment using each of the corresponding policies (Ta, N to
evaluate (F((T) s and (1((TT,) ((TTT,)))ss S)ssI
if use useenovelty then
Compute the gradient approximation V0 else
Nynio E
Nard N(D(TTO,) A) P
Compute gradient approximation 00- end
good ((mo,) Pu-8
Update 0 = 0
77- V8.
Run one episode the environment using compute & and F(TT).
Insert me M based on & (TT) and F (TTs).
Add (TTW) to A.
Update Ressps-
Igraad
7ggrdd
end
16

---

Published as a conference paper at ICLR 2023
Algorithm 5: QD-PG
Given:
M: MAP-ELITES repertoire
N": maximum number of environment steps
P E N": size of the population of RL agents
S E N number of TD3 training steps per iteration per agent
TD3 hyperparameters
N-): novelty reward function
P()): fitness function
((): behavior deseriptor function
Initialization
Initialize a replay buffer
Randomly initialize P policies (To, (rss)...r....
Run one episode in the environment using each of (me, Jisirr to evaluate (F(Te)))ssss and (Ib(TO,)) )issir--
Insert (me, S M based on (Fr SSSSPP ( Sss..
Update with transition data collected during the initial evaluations.
Initialize the quality (resp. diversity) critic Q (resp. Q.) and the corresponding target Q (resp. Q
// Main loop
Initialize Thoepss the total number of environment interactions carried out far, while naxess $ N
Sample uniformly P' policies (To, Ssse from M.
// Update the quality critic alongside the first half of the policics
for = 1 to do
Sample P/2 batches of transitions from TB.
Carry out, using one hatch of transition agent, one TD3 training step for each of the agents
(8 Q 1)s in parallel, averaging gradients over the agents for the shared critic parameters.
end
// Update the diversity critic alongside the second half of the policies
for = 1 to S do
Sample P/2 batches of transitions from B.
Overwrite the rewards using novelty reward function (-).
Carry out, using one batch of transition per agent, one TD3 training step for each of the agents ((TT,, Q 2))/kees in parallel, averaging gradients over the agents for the shared critic parameters.
end
// Update the repertoire
Run one episode the environment using each of (me, D to evaluate (ssss and (4(TT,) )isssp.
Insert (we, s in Ml based (F'(ma,) s)pP and (œ( S)
Update with transition data collected during the evaluations of all P new policies.
Update Meseps-
end
17

---

Published as a conference paper at ICLR 2023
Algorithm 6: PBT
Given:
N No: maximum number of environment steps
E N": size the population of RL agents
S No: number of training steps per iteration per agent
p. n [o, 1[: PBT proportions
RL agent templatc
P()): fitness function
// Anitializati Randomly initialize agents following the chosen RI. template ((Fo.: Pi, hisss Initialize P replay huffers (B,)igigr (only if replay buffers are used by the RI. agent).
// Main loop
Initialize Thsepa. total number environment interactions carried out far, to 0.
while napps S N
Train agents i = 1,... P independently for S steps using the RL agent template and the replay buffers (only if replay buffers are used by the RI. agent), interacting with the environment many times dictated the RI. agent.
Run one episode the environment using each of (me, Sisip to evaluate (F(Te, Disigr.
Re-order the agents = 1,... IP in increasing order of their fitnesses (F((TT) )) Update agents i = 1, ... pP by copying
mandomll-sampller agents from i (1 n P Pand
copy the replay buffers accordingly (only if replay buffers used by the RL agent). Sample new hyperparameters for agents 1,.-* .PP.
Update naapps
end
B EXPERIMENTAL DETAILS
In this section, detail the parameters used for all algorithms. In particular, we that the same values used in the original studies for all MAP-ELITES-based algorithms other than the one introduced in this paper, namely MAP-ELITES, PGA-MAP- --A-ELLTESES, QD-PG, and ME-ES. Additionally, we run the implementations of these algorithms provided in the QDAX library Lim et al. (2022) for our experiments. All MAP-ELITES based algorithms use grid with 1024 cells initialized using with 50,000 initial random points.
Table 1: PBT parameters
Parameter
Value
Population size Proportion of worst agents Proportion of best agents Number of training steps per iteration per agent S
80
0,4
0.1
5000
Replay buffer size
100000
18

---

Published as a conference paper at ICLR 2023
Table 2: PRT-MAP-ELITES parameters
Parameter
Value
Number of vsoiiae-variatio Size of the population of RL agents P
variation offsprings per iteration M
240
80
Proportion worst agents p
0.2
Proportion of agents sample from the repertoire k
0.4
Proportion of best agents n
0.1
Number of training steps per iteration per agent S
5000
Replay buffers size Isoline
100000
0.005
Isoline
0.05
Table MAP-ELITES parameters.
Parameter
Value
Number of offsprings per iteration M
1000
Isoline d1
0.005
Isoline
0.05
Table ME-ES parameters. Parameter
Value
Number consecutive gradient steps for a given policy
10
Number of evaluations for gradient approximations Ngrad Number of randomly-initializzed policies used to initialize the repertoire Ninit Std of the normal distribution perturb parameters for gradient approximations Learning rate
1000
0.2
0.01
Table 5: PGA-MAP-ELITES parameters.
Parameter
Value
Number of offsprings per iteration M
100
Number of TD3 training steps used to update the shared critic per iteration S,
300
Number of 'TD3 policy update steps per iteration per policy Sp
100
Discount factor ?
0.99
Policy learning rate
3e-4
Critic learning rate
3e-4
Noise clipping
0.5
Policy noise
0.2
Exploration noise
0.0
Soft update tau
0.005
Batch size
256
Replay buffer size
100000
19

---

Published as a conference paper at ICLR 2023
Table 6: QD-PG parameters.
Parameter
Value
Size of the population of RL agents P
100
Number of TD3 training steps per iteration per agent S
100
Discount factor y Policy learning rate
0.99
3e-4
Critic learning rate
3e-4
Noise clipping
0.5
Policy noise
0.2
Exploration noise
0.0
Soft update tau
0.005
Batch size
256
Replay buffer size
100000
Table 7: SAC hyperparameters' ranges (or values if the hyperparameter does not change during training) that PBT and PBT-MAP-ELITES sample from.
Parameter
Range / Value
Discount factor
[0.9, 1.0]
Policy learning rate
[3e-5, 3e-3]
Critic learning rate
[3e-5, 3e-3]
Alpha learning rate
[3e-5, 3e-3]
Reward scaling factor
[0.1, 10]
Soft update tau
0.005
Alpha initial value
1.0
Batch size
256
Table 8: TD3 hyperparameters' ranges (or values the hyperparameter does not change during training) that PBT and PBT- MAP-ELIIEEEE sample from.
Parameter
Range Value
Discount factor 7 Policy learning rate
[0.9, 1.0]
[3e-5, 3e-3]
Critic learning rate
[3e-5, 3e-3]
Noise clipping
[0.0, 1.0]
Policy noise
[0.0, 1.0]
Exploration noise
[0.0, 0.2]
Soft update tau
0.005
Batch size
256
20


Reviews:
[{"review_id": "l5wtAl3T4C", "reviewer": "Reviewer_Y8Hf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a quality-diversity algorithm for reinforcement learning that enables both the RL optimization step and population repertoire update step to make changes to agent parameters. The proposed algorithm allows updates to agent hyperparameters to reduce the sensitivity of the approach to hyperparameter choice of the underlying RL algorithm. Scaling is achieved by allowing parallel evolution of agent populations and a JAX implementation for high performance. Results show strong performance (matching competitive alternatives) on robotic control tasks, particularly in terms of deceptive environments and when evaluated not only on final performance but also coverage of strategies.", "summary_of_the_review": "The technical novelty of the paper is modifying MAP-Elites to use a PBT-like structure for the agent population. This provides the benefit of generality to RL implementation and automatic tuning of hyperparameters (inherited from PBT). This is certainly new, though incremental in the sense that both PBT and MAP-Elites have been thoroughly explored in the past. There is substantial benefit to be had from further investigation of this kind of combination of RL meta-algorithms (like PBT and self-play) with evolutionary approaches, particularly from quality diversity.\n\nEmpirical results show some strong results in the set of tasks the algorithms are tailored to: deceptive domains. Most tasks show competitive performance with alternatives. All results are in relatively simple robotic control tasks (compared to controlling robotic manipulators or real robot locomotion), leaving plenty of room for stronger tests of the algorithm capabilities. No empirical results examine the speedup claims of the JAX implementation or the scalability claims for the algorithm, though both seem very plausible.\n\nTaken together the work makes a step forward for quality-diversity approaches to RL in deceptive continuous control tasks. Whether this approach has wider value remains an open question.", "strength_and_weaknesses": "## Strengths\n\n1. Comparable performance to existing algorithms while being able to solve hard exploration tasks (HumanoidTrap, AntTrap) fast (in terms of environment steps).\n2. Generality. The approach presented can readily be coupled with many RL algorithms and directly addresses hyperparameter sensitivity issues in those algorithms. It would be interesting to see results showing how this helps compared to baselines on other RL tasks.\n\n\n## Weaknesses\n\n1. Few major performance improvements over alternatives. The results would be stronger if there were clear environments that previous algorithms simply failed to solve that PBT-MAP-Elites solves. The closest result is the HumanoidTrap result. This is not a major weakness.\n2. No data on scaling. One of the main benefits of the approach is that it \"3) can scale to large population sizes\", but this is never tested. Adding experiments showing this scaling and how it compares to alternatives would greatly benefit the paper.\n3. No data on (wallclock) speedup. Can the speedup of running experiments in JAX be quantified? The JAX implementation is claimed as being efficient, but no empirical evidence backs this claim compared to other simulators.\n\n\n## Feedback & Questions\n- Figure 2: The colors for ME-ES and PBT are hard to distinguish, particularly when shaded areas overlap the medians. Consider slightly different colors for readability. Also it would help to order the columns to have all \"*Uni\" columns and \"*Trap\" columns grouped together.\n- Figure 3: The axis text is too small to read. Please make it larger.\n- Note: At least two references are duplicated: Pierrot 2022a & 2022b, Lim 2022a & 2022b.\n- What is the speedup of using the JAX implementation compared to alternatives?\n- The introduction and related work are both quite lengthy and cover overlapping material. Consider condensing the introduction to highlight the main contributions and novelty, with the related work discussing the particular limitations of past efforts. This can help keep the narrative clear for readers and focus attention on the specific novelty of the work reported.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VZWX1220PR", "reviewer": "Reviewer_bFfK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a framework that allows using any reinforcement learning (RL) algorithm within a population of agents. The contribution is to use quality diversity methods to evolve populations and maintain their diversity. The most commonly used method is MAP-ELITES, but MAP-ELITES does not work well on high-dimensional search spaces. The contribution of the paper is the development of a version of MAP-ELITES, called PBT-MAP-ELITES, that does not depend on a specific RL agent, is robust to hyperparameter choices, and scales to large population sizes.  Some experimental results are included for an example problem.", "summary_of_the_review": "The paper presents an algorithm that is a new variation of MAP-ELITES. It evolves a population of agents, scales well to large population sizes, and is robust to hyperparameter choices. The experimental results that are included in the paper show good performance compared to other algorithms, but they are described in a succinct way, making it very hard to replicate the results.", "strength_and_weaknesses": "Strengths: \nThe changes made to MAP-ELITES are simple but seem to be effective.\nWeaknesses: \n- the PBT-MAP-ELITES algorithm is a variation of PGA-MAP-ELITES, which seems quite simple even though it appears to be effective. \n- There are many variations of MAP-ELITES that are used in the experiments but for which there is no explanation in the paper. \n- The experimental results included are relatively limited and are not described with enough details to be reproducible. \n- The paper assumes familiarity with all the specific robotics problems used to test the algorithm.  \n- The figure with the experimental results (Fig.2) is hard to read.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3dn1FoaCNbP", "reviewer": "Reviewer_XjfY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the limitations of reinforcement learning (RL) based MAP-ELITES approaches, an approach to quality diversity (QD) optimization. The authors highlight the following four problems with existing approaches: (i) high sensibility to hyperparameters; (ii) training instability; (iii) high variability in performance; and (iv) limited parallelizability. \n\nTo overcome these limitations, the authors propose a population-based RL-based MAP-EILTES approach. Each agent in the population encodes the policy parameters, the hyper-parameters for the training, and some other internal parameters used during the training. The proposed framework is a generic framework in that one can easily replace the RL baseline to train each agent. \n\nThe proposed approach is compared with other MAP-Elites variants with SAC and TD3 as their RL baselines on five robotics environments that are often used in QD-RL literature. Superior performance, in particular on environments with deceptive reward signals, are observed.", "summary_of_the_review": "I see the advantages of the proposed approach. However, because of the lack of the discussion of the algorithm validity and (empirical) analysis of the algorithmic behavior, I think that the claims are not sufficiently supported in the paper. ", "strength_and_weaknesses": "# Strength\n\nApproach: The approach is relatively simple. The RL baseline can be easily replaced. And it is parallel implementation friendly. \n\nEvaluation: The advantages of the proposed approach over existing MAP-ELITES approaches have been demonstrated on robotics environments in terms of the best fitness, coverage, and QD score. In particular, the advantage is pronounced on environment with deceptive reward signals is reported.\n\n# Weaknesses\n\nClarity: The algorithm is described thoroughly by natural language in the main text. It is not easy to precisely understand, in particular, for those who are not familiar with MAP-ELITES. The algorithm is provided in the appendix, but the details are not given there. Moreover, because of a different symbol used in the algorithm and in the main text (M vs N), it was hard to fully understand. \n\nAlgorithm validity: The authors say that the meta-learning mechanism for the hyper-parameter is included in the algorithm. However, as far as I understand, the hyper-parameter is only randomly sampled uniformly over the domain. whenever an agent in the population is replaced. It does not look like optimizing the hyper-parameter values.\n\nMotivation and Algorithm Design and Experimental Evaluation: The authors highlighted four difficulties (written in the summary part) and proposed the approach to address these difficulties. However, it was not clear from the paper how they are addressed. Item (i) seems to be addressed by the meta-learning of the hyper-parameter. However, as I wrote above, it was not clear why this makes sense. I couldn't find discussion related to Item (ii) and (iii). The experiments are not designed to evaluate these points. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster