Proximal Policy Gradient Arborescence for Quality Diversity Reinforcement Learning
Authors: Sumeet Batra
Bryon Tjanaka
Matthew Christopher Fontaine
Aleksei Petrenko
Stefanos Nikolaidis
Gaurav S. Sukhatme
Venue: ICLR 2024 spotlight (2024)
Keywords: Reinforcement Learning
Quality Diversity
Robotics
Machine Learning
Evolution Strategies
Primary area: reinforcement learning
TL;DR: We present a novel QD-RL method that leverages on-policy RL and Differentiable Quality Diversity to discover a variety of high performing locomtion gaits on the challenging mujoco environment, including, for the first time in QD-RL, humanoid.

Abstract: Training generally capable agents that thoroughly explore their environment and
learn new and diverse skills is a long-term goal of robot learning. Quality Diversity
Reinforcement Learning (QD-RL) is an emerging research area that blends the
best aspects of both fields – Quality Diversity (QD) provides a principled form
of exploration and produces collections of behaviorally diverse agents, while
Reinforcement Learning (RL) provides a powerful performance improvement
operator enabling generalization across tasks and dynamic environments. Existing
QD-RL approaches have been constrained to sample efficient, deterministic off-
policy RL algorithms and/or evolution strategies and struggle with highly stochastic
environments. In this work, we, for the first time, adapt on-policy RL, specifically
Proximal Policy Optimization (PPO), to the Differentiable Quality Diversity (DQD)
framework and propose several changes that enable efficient optimization and
discovery of novel skills on high-dimensional, stochastic robotics tasks. Our new
algorithm, Proximal Policy Gradient Arborescence (PPGA), achieves state-of-
the-art results, including a 4x improvement in best reward over baselines on the
challenging humanoid domain.

PROXIMAL POLICY GRADIENT ARBORESCENCE FOR QUALITY DIVERSITY REINFORCEMENT LEARNING
Sumeet Batra
Bryon Tjanaka
University of Southern California Los Angeles, CA 90089
University of Southern California Los Angeles, CA 90089
ssbatra@usc.edi
t jjanaaaQusc.dd
Matthew C. Fontaine
Aleksei Petrenko
University of Southern California Los Angeles, CA 90089
University of Southern California Los Angeles, CA 90089
mf mfootainnusc.edi
petrenkoousc.edu
Stefanos Nikolaidis
Gaurav S. Sukhatme
University of Southern California Los Angeles, CA 90089
University of Southern California Los Angeles, CA 90089
nikolaid@use.co
gauraveusc.edu
ABSTRACT
Training generally capable agents that thoroughly explore their environment and learn new and diverse skills a long-term goal of robot learning. Quality Diversity Reinforcement Learning (QD-RI.) is an emerging research area that blends the best aspects of both fields - Quality Diversity (QD) provides principled form of exploration and produces collections of behaviorally diverse agents, while Reinforcement Learning (RL) provides a powerful performance improvement operator enabling generalization across tasks and dynamic environments. Existing QD-RL approaches have been constrained to sample efficient, deterministic off- policy RL algoritmms and/or evolution strategies, and struggle with highly stochastic environments. In this work, we, for the first time, adapt on-policy RL, specifically Proximal Policy Optimization (PPO), to the Differentiable Quality Diversity (DQD) framework and propose additional improvements over prior work that enable efficient optimization and discovery of novel skills on challenging locomotion tasks. Our new algorithm, Proximal Policy Gradient Arborescence (PPGA), achieves state-of-the-arr results, including a 4x improvement best reward over baselines the challenging humanoid domain.
INTRODUCTION
Quality Diversity (QD) algorithms enable the exploration and discovery of diverse skills in a behavior space. For example, a QD algorithm can train different locomotion gaits for a walker (Cully et al.) 2015), discover different grasping trajectories for manipulator (Morel al. 2022), or generate diverse range of human faces (Fontaine & Nikolaidis) (02T). However, since these algorithms are generally oriented towards solving exploration problems, they struggle to find performant policies in high- nigh-diimessioal robot learning tasks. QD-RL is an emerging field that attempts to combine the principled exploration capabilities of QD with the powerful performance improvement capabilities of RL. Prior methods have leveraged off-policy RL, specifically TD3, to estimate the gradient of performance, and either Evolution Strategies (ES) or TD3 to estimate the gradient of diversity in order to search for diverse, high-quality policies. They have shown success in exploration problems and certain robot locomotion tasks (Nilsson& & Cully 2021 Pierrot et al. 2022) Tjanaka et al. 2022b). Nonetheless, there remains gap in performance between QD-RL and standard RL algorithms on continuous control tasks. Furthermore, off- policy RL algorithms were not designed with massive parallelization in mind, and there is little literature that explores how to leverage modern massively-

---

parallelized simulators with these algorithms, whereas there are numerous works exploring on-policy
RL in these regimes (Makoviychuk et al. 2021 Rudin et al. 2021 Handa et al. 2002 Batra et al.
2021 Huang et al. 2022).
Archive
Walking (in (0.02,0.55)
Galloping (ma my) (0.44,
m9q
Jamping
Limping
(0.30 (0.30,0.22)
10,
Figure 1: PPGA finds diverse archive of fighhppeffrming locomotion behaviors for humanoid agent by combining PPO gradient approximations with Differentiable Quality Diversity algorithms. The archive's dimensions correspond to the measures m and m2, i.c., the proportion of time that the left and right feet contact the ground. The color each cell shows the objective value, i.e., how fast the humanoid moves. For instance, jumping moves the humanoid forward quickly, with the left and right feet individually contacting the ground 30% and 22% of the time, respectively.
From our investigation of prior methods, simply combining cxisting QD methods with an RL algorithm tends not scale well to high-dimensional, highly dynamical systems such Humanoid. For example, all QD-RL algorithms for locomotion to date use non-Markovian measures of behavioral diversity, which in many policy parameter mutation, which struggles to scale well with deep neural networks. Prior methods that investigated combining Differentiable Quality Diversity and off-policy RL (Tjanaka et al.) 2022b) achieved similar results as other baselines. However, given the gap in performance between standard RL and QD-RL algorithms in terms of best- perf-performing policy, we believe that DQD algorithms, under different formulation more synergistic with its underlying mechanisms, can close this gap. To this end, we leverage Proximal Policy Optimization (PPO) (Schulman et al.) al. 2017), a popular on-policy RL algorithm, with Differentiable Quality Diversity (DQD) (Fontaine & Nikolaidis, (02T) because of the already present synergy. Specifically, DQD algorithms CMA-MEGA (Fontaine Nikolaidis/ 2021), and its more recent variation CMA-MABGA (Fontaine & Nikolaidis 2023), maintain single search point (or policy in the case RL) that moves through the behavior space and fills new, unexplored regions with offspring policies constructed via gradient information collected from online data. It is through this high level view that we see the emergent synergy between PPO and DQD, in that PPO can be used collect gradient estimates from online data when both of the objective and measure functions are Markovian and non-diffcrentiable.
prevents direct RL-optimization. Most algorithms instead opt for
We make several key changes CMA-MAEGA and PPO to maximally leverage their synergy. Our new algorithm, Proximal Policy Gradient Arborescence (PPGA), to the best of our knowledge, is the first QD-RL algorithm not only achieve 4x performance in best reward on the humanoid domain, but achieve the same level of performance as PPO without sacrificing any of the diversity in the discovered policies. Specifically, we make the following contributions:
(1) We propose vectorized implementation of PPO, VPPO, that jointly computes the objective and measure gradients with little overhead and without running separate PPO instances for each task (2) We generalize prior CMM-based DQD algorithms as instances of Natural Evolution Strategies (NES) and show that contemporary NES methods, specifically xNES, enable better training stability and performance for DQD algorithms (3) We introduce the notion of Markovian Measure Proxies (MMPs), which makes the typically non- Mn-Maarkviian measure functions used in QD-RL amenable to RL-optimization (4) We propose new method to move the current search point, hereon referred to as the "search policy", to unexplored regions of the archive by iteratively "walking" it using collected online data and RL optimization of novel multi-objective reward function.
2

---

2
BACKGROUND
2.1 DEEP REINFORCEMENT LEARNING
Reinforcement Learning algorithms search for policy, mapping of states to actions, that maxi- mizes cumulative reward in an environment. RL assumes the discrete-time time Markov Decision Process (MDP) formalism (S, .. R. P,7) where S and A are the state and action spaces respectively, R(s, a) the reward function, P(s'|s,, (,,), defines state transition probabilities, and y is the discount factor.
The RL objective
maximize the discounted episodic return of policy E Ek=o 7 R(sk= ax)
where T is episode length. Deep Reinforcement Learning solves the RL problem by finding policy (a (t) parameterized by a deep neural network that represents a state-action mapping.
On-policy Deep RL methods directly learn the policy xo using experience collected by that policy or a recent version thereof. Contemporary methods (Mnih et al. 2016) fit the value function Vo(s)) to
discounted returns and estimate the advantage A, = 7 R(sk. ag) (st), which corresponds to the value of an action over the current policy (Schulman al. 2016). From here, the gradient of
the objective w.r.t. or policy gradient, can be estimated as E, V Velogro(ae(ss))ol and the policy Tg is trained using mini-batch gradient descent.
Trust region policy gradient Deep RL methods constrain the policy updates to maintain the proximity of my to the behavior policy Té.id that was used to collect the experience. TRPO (Schulman et al.) 2015) takes the largest policy improvement step that satisfies the striet KL-divergence constraint. Proximal Policy Optimization (PPO) (Schulman et al.
2017) approximates the trust region by "ip Mel (8c) is the importance sampling ratio: Keara (arls.)
optimizing clipped surrogate objective where r0)
L(O) = É..
Off-policy Deep RL algorithms learn parameterized state-action value functions (s(s, az) that estimate the value of taking action in state Then, actions are taken with greedy policy arg max, (s az), or an e-greedy variation thereof. Q-functions can be learned from experience collected by recent or past versions of the policy or another policy altogether.
In continuous control problems, can difficult to find a" = arg max, Qo(se: ar) due to an infinite number of possible actions. To work around this issue, off-policy methods such as DDPG (Lilli) crap et al. 2016) and TD3 (Fujimoto et al. 2018) learn a deterministic policy (*)) ) by solving maars(Cer St. (s:)) using gradient ascent. Other off-policy methods, such soft actor-critic (SAC) Haarnoja et al. (2018), maintain an explicit policy Ty. but similarly derive the policy gradient from the critic, allowing them to learn from off- off-policy data well.
2.2 QUALITY DIVERSITY OPTIMIZATION
Unlike single-objective optimization methods such as RL, Quality Diversity algorithms search for an archive of nigh-performing, diverse policies. An optimal archive essentially answers the question, "how does performance change with behavior?" by mapping out the optimization landscape of pre-defined behavior space. The QD problem (Chatzilygeroudis et al.) 2021 assumes objective function f()) that quantifies the agent's performance and measure functions m (-)....+(() that characterize the agent's behavior. The measure functions, represented jointly m(.), define an embedding the QD algorithm should span with diverse policies. The QD objective is to find a policy that maximizes f for every possible output of m. However, the embedding formed by is continuous, so the embedding space is discretized into tessellation of M cells. The QD objective then becomes to maximize / where 0, is policy whose measures m (0,) fall in cell i of the tessclation.
QD algorithms originated with NSLC (Lehman Stanley 201 by and MAP-Elites (Mouret & Clune 2015 Cully et al. 2015). While these early QD algorithms built genetic algorithms,
modern QD algorithms incorporate optimization techniques like evolution strategies (Fontaine et al. 2020; Conti et al.] 2018) Colas et 20.0). gradient ascent (Fontaine & Nikolaidis/ 2021] (023). and differential evolution (Choi & Togelius 202T). Several works have applied QD optimization
generative design (Hagg al. 2020) Gaier al. 2018), procedural content generation (Gravinal
3

---

et al. 2019 Earle et al., 2022 Khalifa et al. 2018), robot manipulation (Morrison et al. 2020), and
reinforcement learning Nilsson & Cully 2021 Janaaka et al. 20022b Pierrot & Flajolet 2023).
2.3
DIFFERENTIABLE QUALITY DIVERSITY
The Differentiable Quality Diversity (DQD) (Fontaine & Nikolaidis 2021 algorithm Covariance Matrix Adaptation Map Elites via Gradient Arborescence (CMA MMMA considers the first-order QD problem where the objective and measure functions are differentiable, with gradients w.r.t. policy CMA-MEGA maintains search policy тe, in policy parameter space (0,, y E K corresponding to some cell in the archive given by the measures < mi (Tez),..., My (me_)) >, and search distribution in objective-measure gradient coefficient space maintained by CMA-ES (Hansen 2016), a zeroth-order optimizer that optimizes the coefficient distribution to produce coefficient vectors that point in the direction of greatest archive improvement. At a high level, CMA-MEGA branches off policies from the search policy in order to locally fill the archive, and then steps the search policy to new, unexplored regions of the archive. During the branching step, the gradients < V. Vm 20, and À gradient coefficient vectors < CO .... Ck P1...., < Co. ..., Ck >A sampled from the CMA-ES search distribution e2 ~ ~NN(p, 2) e IR++1 are combined via the dot product i.e. < Vf. Vm >8, -C,... to produce local gradients Vi,... VA around the search policy. Applying the gradients to the search policy gives us X branched policies To,, n... The new policies can then be ranked by how much they improve the archive, ie.. [ - (TT..a) i [1, AJ. where Tre is the incumbent policy in the archive corresponding to the same cell as ne,- Branched policies that map to new, unexplored cells in the archive have / (To.a) set to some minimum threshold. This implicitly biases the ranking towards the exploration of new, unvisited cells. This ranking is given to CMA-ES, which internally performs an update that steps the search distribution in the direction of the natural gradient w.r.t. greatest archive improvement. CMA- ES returns weights wi,..., W/ such that V step =< W1, ..... WA > < v,.... V > is the natural gradient in parameter space. This weighted linear recombination of the branching gradients is then used to step the search policy in the direction of greatest archive improvement 02, + 02 + a. step.
parameters represented as ff 0f and Vm @mm
dmag
80 .... 0e
The current state-of-the-arr DQD algorithm, Covariance Matrix Adaptation Map Annealing via Gradient Arborescence (CMA-MAEGA) (Fontaine & Nikolaidis, 2023), introduced the concept of soft archives to CMA-MEGA. Instead of maintaining the best policy in each cell, the archive maintains threshold te and updates the threshold by te f (1 at)t + a when a new policy To. crosses the threshold of its cell e. The hyperparameter S a I 1, referred to as the archive learning rate, controls how much time is spent optimizing region of the archive before exploring a new region. Soft archives have many theoretical and practical benefits discussed in prior work (oontaine & Nikolaidis 2023). Our proposed PPGA algorithm builds directly on CMA-MAEGA.
2.4 QUALITY DIVERSITY REINFORCEMENT LEARNING
Unlike the standard DQD formulation in which the analytical gradients of ff and m can be computed, the QD-RL setting considers MDPs in which these functions are non-differentiable and must be approximated with model-free RL. The gradient approximations of f and m can be used to improve the performance and diversity of agents an archive. QD-RL methods can be roughly divided into two subgroups. The first set of approaches directly optimizes over the entire archive by sampling existing policies in the archive and applying operations to the policies' parameters that either improve their performance or diversity. For example, PGA-ME (Nilsson & Cully) 2021) collects experience from evaluated agents into a replay buffer and uses TD3 to derive a policy gradient that improves the performance of randomly sampled agents from the archive, while using genetic variation (Vassiliades) Mourei 2018) on the same set of agents to improve diversity and fill new, unexplored cells. Similarly, QDPG (Pierrot et al., (022) derives policy and diversity gradient using TD3 and applies these operators to randomly sampled agents in the archive.
Whereas the first family of QD-RL algorithms simultaneously search the behavioral embedding in many different regions at once, the second family uses the DQD formulation i.c., maintains a single search policy that explores new local regions at time using objective- measure gradient approximations. In prior work (Tjanaka et al.) (022b), the authors considered objective gradient approximations via TD3 and OpenAl-ES, while approximating the measure function gradients with
4

---

OpenAI-ES. In this work, notice the unique on policy nature of DQD algorithms and present novel formulation that exploits their synergy with PPO.
3 PROPOSED METHOD: THE PROXIMAL POLICY GRADIENT ARBORESCENCE ALGORITHM
We begin with the DQD algorithm CMA- MAEGA as our foundation. The algorithm can be roughly divided into three phases: (1) com- puting the objective-measure gradients for the branching phase, (2) providing the relative rank- ing of each branched policy w.r.t. the QD objec- tive to CMA-ES, and (3) stepping the search pol- icy in the direction of greatest archive improve- ment. Sections 3.1 and 3.2 focus enabling RL optimization for phase one, 3.3 explores the connection between CMA-ES and NES and how this can improve training stability in phase two, and section 3.4 describes our method for walk- ing the search policy with PPO in phase three.
Sumple woeiTicienis c. Wia
Branch solutions To,
Evalunte expected reward & behavior +
Apprximati
( Vm( mm)
with PPO
Walk solution point with PPO
Adape E with xNES
Insert solutions into archive
Figure 2: PPGA estimates V,, Vm with PPO. We randomly sample gradient coefficients e and perform weighted linear recombination of the objective-measure gradients with as the weights. This produces a population of gradients that, in turn, result in population of branched policies. The policies are evaluated and inserted into the archive. xNES adapts the gradient coefficient dis- tribution based on these insertions towards maxi-
3.1 MARKOVIAN MEASURE PROXIES
QD problems often contain Mar-Markovian mea- sure functions. For robot locomotion tasks, the standard measure function is the proportional foot contact time with the ground (0) =
mal archive improvement. The new mean of the coefficient distribution is used to walk the search policy towards new, potentially unexplored re- gion of the archive.
1 E. (st) for each leg i, L...k, where the Kronecker delta (*e) indicates whether the i'th leg is in contact with the ground not in state st. and 7 is the episode length. However, this measure function is defined on trajec- tory (i.e., the whole episode), making it non- Markovian and thus preventing us from using RL to estimate its gradient. To solve this issue, we introduce the notion of Markovian Measure Proxy (MMP), which is a surrogate function that obeys the Markov property and has a positive correlation with the original measure function. For locomotion tasks, we can construct an MMP by simply removing the dependency on the trajectory and making the original measure function dete-depend,nt, i.c., setting it to be (st)). We can then use the exact same MDP as the standard RL formulation and replace the reward function with ó, (st).
3.2 POLICY GRADIENTS FOR DIFFERENTIABLE QUALITY DIVERSITY OPTIMIZATION
PPO is an attractive choice as our objective- measure gradient estimator because of ability to scale with additional parallel environments. Being approximate trust region method, the constrained policy update step provides some robustness to noisy and non-stationary objectives. This is particu- larly important in the QD-RL setting, where the QD-objective is highly non-stationary that is, the QD-objective changes with the state of the archive, which is updated on each QD iteration.
We treat the RL objective and k MMPs, each one optimized by an actor-critic pair, reward functions to optimize. Rather than spawning a new PPO instance with a separate actor and critic network for the RL objective f and each MMP 5 (sx) independently, we start with single actor no, (a]s) parameterized by the policy parameters f,2 of the current search policy, and l + value functions Voy, Vos, .... Vos. The actor replicated k ++1 times, each one paired with a corresponding value function. The actors are combined into single vectorized policy π Teog....o/ (a|s) that jointly optimizes f, 61 (st)),..., ..., ó1 (s.) > for N₁ iterations, where N1 is configurable hyperparameter. We additionally modify the computation the policy gradient into a batched policy gradient method, where intermediate gradient estimates of each function w.r.t. policy params only flow back to
5

---

the parameters corresponding to respective individual policies during minibatch gradient descent. After N1 iterations, we separate the vectorized policy, giving a set of subpolicies with optimized parameters To, (als), .... R0,, (a|s) that perform better w.r.t. their objectives. In the case of measure functions where m²(+) is the proportion foot contact time of the i'th leg, mi(TTe,...)) > mm( i.e. the resulting policy will have higher proportion foot contact time over the starting policy after optimization. Subtracting the initial parameters (0μ) from each resulting policy gives us the desired
objective-measut Jacobian to branch policies from pp.
01 A6 20
05g which can be linearly recombined in various ways 20,
20 ..
In addition to the VPPO implementation, we introduce the option to make the learnable action standard deviation parameter static. the typical case, PPO decays this parameter over time in order to converge to quasi-deterministic optimal policy at the expense of further exploration. In some environments, narrowing the action distribution can indeed help promote consistent optimal performance. In other environments, this effect can hinder the QD algorithm's 's ability to branch policies into new cells, given that the outer QD optimization loop relies on gradient estimates produced by PPO to discover unexplored regions of the archive. In environments where we observe this negative effect, we disable gradient flow to the action standard deviation parameter.
Finally, in order to address environmental uncertainty, insert new policies based on their per- formance and behavior averaged over 10 parallel environments. We leverage GPU acceleration to quickly batch process many parallel environments over a population of branched policies.
3.3 CONNECTION TO NATURAL EVOLUTION STRATEGIES
We replace CMA-ES with a Natural Evolution Strategy (NES) to increase the stability and perfor- mance of CMA-MAEGA on noisy RL environments. CMA-based variants of PPGA diverged during training. Prior work (Müller& & Glasmachers 2018) showed that CMA-ES struggled to evolve deep neural network controllers with dimensionality FST on stochastic RL environments, However. CMA- MAEGA uses CMA-ES to maintain search distribution in objective-measuee gradient coefficient space R++11 << Rdd, where + 1 can be as small as three dimensions, implying that CMA-ES should still be effective in this low-dimensional space. It was then puzzling to find consistent divergence during the training of our CMA-based algorithm. We hypothesize that the culprit is the cumulative step-size adaptation (CSA) mechanism employed by CMA-ES. CMA-ES uses evolution paths ((a) to adapt the step size (99) between successive generations (g). The mechanisms by which (9)) are updated assume fairly non-noisy and stationary objective f. However, the application of CMA-ES to QD optimization on stochastic RL environments presumes the exact opposite. That is, the RL objective fRI. is very noisy, and the QD-objective fąr = g(fRr())), which is a function of the RL objective, is highly non-stationary, since the state of the archive A changes the direction of greatest archive improvement on every iteration. To address the training divergence, we propose using exponential evolution strategies (xNES) Glasmachers et al. (210),, a more recent and theoretically well-motivated method, as a drop in replacement for CMA-ES. Prior works have shown strong links between xNES and CMA-ES, and generalize both methods instances of natural evolution strategies (Akimoto et al.) 2010; Glasmachers et al.) 2010). In fact, the update step in xNES is equivalent to CMA-ES up the use of evolution paths. We refer these prior works for an in-depth comparison. More generally, we believe any natural evolution strategy can be used to maintain and update the search distribution over gradient coefficients in this and any prior CMA-based DQD method.
3.4 WALKING THE SEARCH POLICY
In standard DQD, V step is computed via weighted linear recombination to produce a gradient vector that steps the search policy in the least explored direction of the archive. However, the resulting gradient vector is a linearized approximation around the current search policy 0, and thus cannot be reused to take multiple gradient steps in a non-convex optimization problem. It would be remiss not to leverage the perll--prallelizeed VPPO implementation to "walk" the search policy over many steps in the direction of greatest archive improvement. We make the key observation that the mean gradient coefficient vector e, of the updated search distribution maintained by xNES points in the direction of greatest archive improvement for the next iteration of the QD algorithm. Thus, we construct a new multi-objective reward function for VPPO to optimize by taking the dot product between the gradient

---

coefficient vector and the objective and measure proxies Cpas.... Cuz+: Optimizing this function with VPPO allows us to walk the search policy f₂ in the direction greatest archive improvement by iteratively taking conservative steps, where the magnitude of the movement controllable by hyperparameter No. This objective is stationary for all N₂ steps, and only updated after the subsequent QD iteration. We provide pseudocode in Appendix
f101; .... >.
4 EXPERIMENTS
We evaluate our algorithm on four different continuous-control locomotion tasks derived from the original Mujoco environments (Todorov et al. 2012): Ant, Walker2d, Half-Cheetah, and Humanoid. The standard objective in each task is maximize forward progress and robot stability while minimizing energy consumption. We use the Brax simulator to leverage GPU accelcration and massive parallelization of the environments. The observation space sizes for these environments 87, 17, 18, and 227, respectively, and the action space sizes are 8, 6, 6, and 17, respectively. The standard Brax environments are augmented with wrappers that determine the measures an agent in any given rollout as implemented in QDax (Lim et al. 2022), where the number of measures of an agent is equivalent to the number of legs. The measure function is the number of times a leg contacts the ground divided by the length of the trajectory. We implement PPGA in pyribs (Tjanaka et al. 2023), with our VPPO implementation based on CleanRL's implementation of PPO (Huang et al. 2022). Most experiments were run on SLURM cluster where each job had access to an NVIDIA RTX 2080Ti GPUs, 4 cores from Intel(R) Xeon(R) Gold 6154 3.00GHz CPU, and 108GB of RAM. Some additional experiments and ablations were on local workstations with access an NVIDIA RTX 3090, AMD Ryzen 7900x core CPU, and 64GB of RAM.
4.1 COMPARISONS
We compare our results to current state-of-the-art QD-RL algorithms: Policy Gradient Assisted MAP-Elites (PGA-ME) Quality Diversity Policy Gradient (QDPG) implemented in QDax (Lim) et al. 2022), and CMA-MAEGA(TD3, ES) implemented in pyribs (Tjanaka et al. (023). We also compare against the state-of-the-ar ES-based QD-RL algorithm, separable CMA-MAE (sep-CMA- MAE) (Tanaka et al. 2022a), which allows evolutionary QD techniques to scale up to larger neural networks. Finally, in order to verify our hypothesis on the emergent synergy between PPO and DQD, we provide ablation where TD3 is used drop-in replacement for PPO in PPGA, which we will refer to as TD3GA going forward. Details on the TD3GA design choices and additional ablations, such comparing against standard PPO, can be found in the appendix. The same archive resolutions and network architectures are used for all baselines. A full list of shared hyperparameters Appendix B We use an archive learning rate of 0.1. 0.15, 0.1, and 1.0 on Humanoid, Walker2d. Ant, and CheefCh respectively. Adaptive standard deviation is enabled for Ant and Humanoid. We reset the action distribution standard deviation to 1.0 on each iteration in all other environments.
1.0
10
E
Figure 3: 2D Archive visualizations of PPGA compared the current state-of-the-art QD-RL algorithm PGA-ME, We use 50x50 archives to show detail.
A comparison Humanoid to PBT-ME (SAC), recent QD-RL method, can be found in Appendix H PBT-ME (SAC) was trained with Google TPUs. Due to computational constraints, we were only able to provide comparison on task.
7

---

fumanedd
helrtwenh
5000
6993
5002
Dec
0000
2000
2330
400002
200000
400080
200000
402000
220000
147
420000
200000
220000
300000
200030
4600072
200000 400030
0.2g
200000 433000
100
302
Oheagge 088
Num
Exils
14mm
Num Evils
100
302
300
30
Ulyostive
Dtyoutrec
Olecclive
PPCA
PGA-M
20PG
CHW.MAGNNTTS, (S)
Figure 4: QD metrics and cumulative distributions for archives of PPGA and the baselines. The CCDF plots in the last row indicate the percentage of archive policies above a certain objective threshold. All plots show the mean over four seeds with a 95% bootstrapped confidence interval.
We conduct our experiments using the following criteria: QD-score, which is the sum of scores of all nonempty cells the archive, and coverage, which is the percentage of nonempty cells in the archive, have been historically used by QD algorithms to measure performance and diversity respectively, and so we include them as metries. However, these metrics have a number of edge cases that make them imperfect measures of performance and diversity. For example, algorithm that fills 100% of the archive with low-performing policies can have a higher QD-score and coverage than a QD algorithm that fills fewer cells with high-performing policies. To more accurately represent the performance and diversity of a given algorithm, we additionally include plots of the Complementary Cumulative Distribution Function (CCDF), originally presented in (Vassiliades al.] 2016), which shows what percentage of policies in the archive achieve a reward of It or greater for all possible values of I on the a-axis. The CCDF attempts to capture notions of quality of policies in the archive and diversity, while also shedding light on how the policies are distributed w.r.t. performance. Finally, we include the best reward metric, denoting the fighest-performing policy the algorithm was able discover.
Figures 3 and show that PPGA outperforms baselines in best reward and QD-score, achieving comparable coverage scores on all tasks except Ant, and generating much more illuminated archive heatmaps with a diverse range of higher performing policies than the current state of the art, PGA-ME. Notably, PPGA is the only algorithm that solves Humanoid, achieving over 4x improvement in best- performing policy and QD score compared to baselines. More important than QD-Score and Coverage are the CCDF plots. x = 0, all policies the archive are included, i.e., x encapsulates coverage score. CCDF plots provide better representation of "quality" than QD-score, since can see how the policies the archive are distributed, Except for Ant, PPGA produces distributions where more of the mass is distributed the right where the high- terf-performing policies lie.
In Figure 5 we find evidence that PPO has an important synergy with DQD that is perhaps missing in other RL algorithms. TD3GA fails to find high performing policies Humanoid. Achieving 100% coverage is indicative of the step size a in xNES exploding and producing highly stochastic policies that, by chance, land in far away cells. This typically occurs when xNES cannot fit covariance matrix to the data, which in this case are weighted linear combinations of V., Vm produced by TD3.
4.2 POST-HoC ARCHIVE ANALYSIS
QD algorithms are known to struggle with reproducing performance and behavior in stochastic environments. To determine the replicability of our agents, follow the guidelines in |Flageat et al.
8

---

420000
10000
100
300000
Best Rowardl
1500
Coverage tSal
80
200000
60
100000
7520
88
203000 459200
602000
220200 405050 $00200
200050 400500 605020 Nim Evels
N.m Ever
Num Exhls
Figure 5: PPGA TD3GA Humanoid the standard QD metrics. All plots averaged over 4 seeds. The shaded regions are the 95% bootstrapped confidence intervals.
Humanoid
Walker2d
Halfcheetah
Archire CCDF
75
75
PGA
QOPG
50
50
CMA,
CNA/MAEGA/TD, ES)
25
10000
Objective
Objective
Ofjective
Objective
Humanoid
Walker2d
Halfcheetah
Ani
QD Score
Cov
Best
QD Score
Cov
Best
QD Score
Cuv
Best
QD
Score
Cov
Best
PPGA
1.02 105
0.52
8324
1.06
10
0.39
4702
7.26
105
0.58
8919
1.53 x 107
0.34
7328
PGA-ME
1.08 x 10
0,39
446
6.53
10"
0.38
1621
3.31
x 102
0.31
4644
1.79
107
0.37
4571
sqp-CMA-MAB
1.27 10a
1.84
10
0.64
2326
6.03
10
0.61
228
1.16
10"
0.30
1629
QDPG
6.53 x 10a
0.26
412
6.59
104
0.35
1490
2.53 x 109
0.28
359
3.03 x 109
0.25
78
CMA MABGA
4.10 x 10a
0,21
352
3.48
10
0.33
1025
5.70 x
0.56
2438
3.08 x 10
0.12
1020
(TD3, ES)
Figure 6: Corrected CCDFs and Corrected QD metrics: QD-Score, Coverage, Best Reward. Results are averaged over four seeds with error bars showing a 95% bootstrapped confidence interval.
(2033). We re-evaluate each agent in the archive 50 times and average its performance and measures to construct Corrected Archive and use this to produce Corrected QD metrics such as QD-Score and Coverage. Fig. 6 shows the corrected QD metrics and the corrected CCDFs, respectively. After re-evaluation, PPGA maintains the lead in best reward on all tasks, QD-score on Humanoid and Ant, and Coverage on Humanoid. The CCDF plots of the Corrected Archives show PPGA producing better distributions of policies on all tasks but Ant, suggesting PPGA's policies robust to stochasticity.
DISCUSSION AND LIMITATIONS
We present new method, PPGA, which is one of the first QD-RL methods to leverage on-policy RL, the first to solve the challenging Humanoid task, and the first to achieve equivalent performance in best reward compared to standard RL on all domains. We show that DQD algorithms and on-policy RL have emergent synergies that make them work particularly well with each other. However, instead of simply combining DQD and on-policy RL as is, we re-examine the fundamental assumptions and mechanisms of each component and implement changes that maximize their synergies. There are some caveats with this approach. On-policy RL algorithms such PPO quite sample-inefficient and require many parallel environments per agent in order to compute the stochastic policy gradient. Although GPU acceleration and massive parallelism improve wall-clock convergence over off- off-policy RL, this makes our approach less sample-efficien than other off-policy QD-RL methods. Secondly, enabling PPO's s adaptive standard deviation parameter (which is true by default for PPO) can have detrimental effects on PPGA's exploration capabilities, made evident by the coverage score on Ant. This is mainly due to the fact that PPO favors collapsing the standard deviation to achieve higher average returns. In the future, we will investigate modifying the standard deviation parameter such that it dynamically shrinks or increases the standard deviation value based on the OD-optimization interested to see how this method scales to
landscape opposed to the RL one. Finally, more data-rich regimes such as distributed settings, as well as its application to harder problems such real robotics tasks. We leave these as potential avenues of future research.

---

REPRODUCIBILITY
In the supplemental material, we provide the source code and training scripts used to produce our results. In the README, we include documentation for setting up Conda environment, running our training scripts, and visualizing our results, In addition, we provide pre-trained archives whose results were presented in this work. Detailed pseudocode and a list of relevant hyperparameters can be found in Appendices A and B
REFERENCES
Youhei Akimoto, Yuichi Nagata, Isao Ono, and Shigenobu Kobayashi. Bidirectional relation between cma evolution strategies and natural evolution strategies. In Robert Schaefer, Carlos Cotta, Joanna Kolodziej, and Günter Rudolph (eds.), Parallel Problem Solving from Nature, PPSN XI, pp. 154-163, Berlin, Heidelberg. 2010. Springer Berlin Heidelberg. ISBN 978-3-642-15844555
Sumeet Batra, Zhehui Huang. Aleksei Petrenko, Tushar Kumar, Artem Molchanov, and Gaurav S. Sukhatme. Decentralized control of quadrotor swarms with end-to-end deep reinforcement learning. In Aleksandra Faust, David Hsu, and Gerhard Neumann (eds.), Conference Robot Learning, 8-11 November 2021, London, UK, volume 164 of Proceedings of Machine Learning Research, pp. 576- 586. PMLR, 2021. URL https: http:tttttoseeeiiiiiii //tpceediicccccccggocooo. mlr press / vv 716 54.544/aataaaa html
Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean-Baptiste Mouret. Quality-Dversity Optimization: A Novel Branch of Stochastic Optimization, pp. 109-135. Springer International Publishing. Cham, 2021. ISBN 978-3-030-66515-9, doi: 10.1007/
0---33006665--9- URL sttps:///oii 00tp:///000.0110100000000--0-0-0
1007
Tae Jong Choi and Julian Togelius. Self-referential quality diversity through differential map-clites, In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '21, pp. 502-509, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383509, doi:
10.1145/3449699.444 344493383.9 URL //dpttts:///o..... http:dii..r.....111111.111 /tt///.....0r0001114433444333339
Cédric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune. Scaling map-elites to deep neuroevolution. Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO '20, pp. 67-75, New York, NY, USA, 2020, Association for Computing Machinery. doi: 10.1144/33779330339900
ISBN 9781450371255 285. 3377930. 3390217
URL/ttps: http:::://ddoioooo http://ddooooo...1111
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via population of novelty-sekking agents. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa -isaaBBanchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems 31, pp. 5027-5038. Curran Associates, Inc., 2018. URL puttt::/ppapeee nips cttpippscccppppppeeeeeeeeepeeeee on- in-innvvv in to-.:oossttttttiiiseooo--oooooo wwr.foorreeeeeeerrnoo..o orcement-learming
7750
pdf
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that can adapt like animals. Nat., 521(7553::003-507, 2015. doi: 10.1038/nature 14422. URL https::/ /ooi
org szg/10.00 100.1008//0000 1tt.//1...11/aaaaa 1110///a/a/ue11222222
Sam Earle, Justin Snider, Matthew C. Fontaine, Stefanos Nikolaidis, and Julian Togelius. Illumi- nating diverse neural cellular automata for level generation. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '22. pp. 68-76, New York. NY. USA. 2022. Association for Computing Machinery, ISBN 9781450392372. doi: 10.1145/3512290.5557773 http:/ttts///...... http::///ooooooo1.1111111 w1wp///.....1111111111
3528754
Manon Flageat, Felix Chalumeau, and Antoine Cully. Empirical analysis of pga-map-elites for neuroevolution in uncertain domains. ACM Trans. Evol. Learn. Optim., Jan 2023. ISSN 2688-299X. doi: 10.1 10.1145/3577203. URL Rtthttts:: //doi. www.oo.g./0... 111///..111333772210 Just Accepted.
Matthew Fontaine and Stefanos Nikolaidis. Covariance matrix adaptation map-annealing. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '23, pp. 456-465,
10

---

New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701191 doi: 11144//3388111.3503338
http:////...........11....0 11t.////...1111///1111 30044/3/58133 3583131 .51.5/333355333.333333333333 3590389
Matthew C. Fontaine and Stefanos Nikolaidis. Differentiable quality diversity. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pp. 10040-10052, 2021. URL http:tttt/tto/ccc/iiiito/// neurips wwtpcccpppppppcccc.ccc / html
Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K. Hoover. Covariance matrix adaptation for the rapid illumination of behavior space. In Carlos Artemio Coello Coello (ed.), GECCO '20: Genetic and Evolutionary Computation Conference, Cancún Mexico, July 8- 12, 2020, pp. 94-102. ACM, 2020. doi: 10.14553377933.3390022. 4145/337792 3390232
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of proceedings of machine learning research, pp. 1587-1596, pmlr, 10-15 jul 2018. URL 1m8/fouimotoo11800 html
mlr press/
Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. Data-Efficient Design Exploration through Surrogate- Assisted Illumination. Evolutionary Computation, 26(3):381-41) 09 2018. ISSN 1063-6560. doi: 10. 162/evco 00231. hRLps:ts:://dii org. wttp://0....../..../o..... 1162/vcco 00231
a
Tobias Glasmachers, Tom Schaul, Yi Sun, Daan Wierstra, and Jürgen Schmidhuber. Exponential natural evolution strategies. In Martin Pelikan and Jürgen Branke (eds.), Genetic and Evolutionary Computation Conference, GECCO 2010, Proceedings, Portland, Oregon, USA, July 7-11, 2010, pp. 393-400, ACM, 2010. 1830483 18305557
doi: 011144/5//3448.1833333
UtL/httss: http://..........11..1......
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. IEBE, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmäässan, Stockhoim, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 1856-1865. PMLR, 2018. URL htttp::/proceeedingg 18b. html
m1 www.presssvve. v80 htteess/vd//aaanooooo jalaarrnojaalbb
Alexander Hagg, Dominik Wilde, Alexander Asteroth, and Thomas Bäck. Designing air flow with surrogate-aseee assisted phenotypic niching. In International Conference on Parallel Problem Solving from Nature, pp. 140-153. Springer, 2020.
Ankur Handa, Arthur Allshire, Viktor Makoviychuk, Aleksei Petrenko, Ritvik Singh, Jingzhou Liu, Denys Makovïcchuk, Karl Van Wyk. Alexander Zhurkevich, Balakumar Sundaralingam, Yashraj Narang, http://w..or//b////....000
Lafleche, Dieter Fox, and Gavriel State. Dextreme: Transfer of agile in-hand manipulation from simulation to reality. arXiv, 2022.
Nikolaus Hansen. The CMA evolution strategy: A tutorial. CoRR, abs/1604.00772,, 2016. URL
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga. Dipam Chakraborty, Kinal Mehta, and João G.M. Araújo. Cleanrl: High-quality single-file implementations of deep rein- forcement learning algorithms. Journal of Machine Learning Research, 23(274):1-18, 2022. URL
http:// wttp:rrrrppppppaa////...
html
11

---

Ahmed Khalifa, Scott Lee, Andy Nealen, and Julian Togelius. Talakat: Bullet hell generation through constrained map-elites. Proceedings of The Genetic and Evolutionary Computation Conference, pp. 1047-1054, 2018.
Joel Lehman and Kenneth O. Stanley, Abandoning Objectives: Evolution Through the Search for Novelty Alone. Evolutionary Computation, 19(2):189-222 223, 06 2011a. ISSN 1063-6560. doi: 10. 10.1162/EVO___00002
htt.htts:://doo orgg 1262 Lar_/o___000_01
Joel Lehman and Kenneth O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th Annual Conference Genetic and Evolationary Computation, GECCO '11, pp. 211-218, New York, NY. USA, lb. Association doi: 10.1145/000156..20011
for Computing Machinery. ISBN 9781 9781450305570.
URL
https:: //d/1//o... .org/o...c....... 100...115555 145/14000555
2001606
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL
attp::/aartte org/ abs 1509 02971
Bryan Lim, Maxime Allard. Luca Grillotti, and Antoine Cully. Accelerated quality-diversity for robotics through massive parallelism. arXiv preprint arXiv:2202.01258, 2022.
Viktor Makoviychuk, Lukasz Wawrzyniak, Yunrong Guo, Michelle Lu, Kier Storey, Miles Macklin, David Hoeller, Nikita Rudin, Arthur Allshire, Ankur Handa, and Gavriel State. Isaac gym: High performance GPU based physics simulation for robot learning. In Joaquin Vanschoren and Kit Yeung (eds.). , Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks I, NeurlPS Datasets and Benchmarks 2021, December 2021, virtual, 2021. URL
pttp:ppppccpppppe2//2222 Gath:/2dddcc75556222622222222222 -tw.:e0000000odeedarrreee Abst
round2. - html
Volodymyr Mnih, Adrià Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Maria-Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pp. 1928-1933 JMLR.org. 2016. URL htt::t///roeoeeiigggg mlr wwtpp//ewsss.apaaa/eee
html
Aurélien Morel, Yakumo Kunimoto, Alex Coninx, and Stéphane Doncieux. Automatic acquisition of a repertoire of diverse grasping trajectories through behavior shaping and novelty search. In 2022 International Conference on Robotics and Automation (ICRA), pp. 755-761, 2022. doi: 10.1 N0.1109//CRA46660 20....9022229900 1837..
Douglas Morrison, Peter Corke, and Jürgen Leitner. Egad! evolved grasping analysis dataset for diversity and reproducibility in robotic manipulation. IEEE Robotics and Automation Letters, 5(3): 4368-4375, 2020. doi: 10. (09/LRRA.000029992119
Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. CoRR, abs/1504.04999, 2015. URL BRLphhtp:///axtt http://wwww..rr/////////5000..0/ 04909
Nils Müller and Tobias Glasmachers. Challenges in high-dimensional reinforcement learning with evolution strategies. In Anne Auger, Carlos M. Fonseca, Nuno Lourenço, Penousal Machado, Luis Paquete, and L. Darrell Whitley (eds.), Parallel Problem Solving from Nature PPSN XV- 15th International Conference, Coimbra, Portugal, September 8-12, 2018, Proceedings, Part II, volume 11102 of Lecture Notes in Computer Science, pp. 41 423. Springer, 2018. doi: 10. 1007/ 978-3-3194 01--31999999999 33. URL /ttp:p///ooo..oog/00000011113331
33
Olle Nilsson and Antoine Cully. Policy gradient assisted map-elites. In Proceedings of the Genetic and Evolutionary Computation Conference. GECCO '21, pp. 866-875, New York, NY. USA, 2021. Association for Computing Machinery. ISBN 9781450383509,
doi: 00.1145/344969934459300
URL httpt:::////m. :/d::///oo wwt.bo..rrg/...00 httpg/....//344955333/
3459304
12

---

Thomas Pierrot and Arthur Flajolet. Evolving populations of diverse RL agents with map-elites. In The Eleventh International Conference on Learning Representations. ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL httttss//ppeereiieeee netppdffeeeep
CU=CBfYffL.qwbb
Thomas Pierrot, Valentin Macé, Felix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Be- guir, Antoine Cully, Olivier Sigaud, and Nicolas Perrin-Gilbert. Diversity policy gradient for sample efficient quality-diversity optimization. In Proceedings of the Genetic and Evolutionary Computation Conference. GECCO '22, pp. 1075- 1083, New York, NY. USA, 2022. Associa- doi: 10.1145/3512290.3558844 URL
tion for Computing Machinery. ISBN 4781150392372.
https: /ttt:s://doi. wwwg/0.0.... 11w.1115/5550 001145/35129900 3528845
Nikita Rudin, David Hoeller, Philipp Reist, and Marco Hutter. Learning to walk in minutes using massively parallel deep reinforcement learning. In Aleksandra Faust, David Hsu, and Gerhard Neumann (eds.), Conference on Robot Learning, 8-11 November 2021, London, UK, volume 164 of Proceedings of Machine Learning Research, pp. 91-100. PMLR, 2021. URL |RLhttps: //proceedings. mir wwwpppwwle/eeeeeee.e..eeeeeeeeee hww.144//udn222..hia html
John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz. Trust region policy optimization. In Francis R. Bach and David M. Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pp. 1889-1897. JMLR.org, 2015. .mlr. wtw.snngs......rs////... hwwp:////cchummannn3mmmm html
URL pattt::/proceediing
John Schulman, Philipp Moritz, Sergey Levine, Michael I. Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. In Yoshua Bengio and Yann LeCun (eds.), 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http:/ http///axvvvv... org/
02438
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, Abs/1707.0633 2017. URL http:://axiiv org /bs/
1707. 06347
Bryon Tjanaka, Matthew C. Fontaine, Aniruddha Kalkar, and Stefanos Nikolaidis. Training diverse high-dimensional controllers by scaling covariance matrix adaptation map-annealing, 2022a.
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, GECCO '22, pp. 1102-1111, New York, NY, USA, 2022b. Association for Computing Machinery. ISBN 978 450392377. doi: 10.1145/ 35522700. URL httt:tttss://ddo .rgg 10 1145 000445/5551290 3528705
Bryon Tjanaka, Matthew C Fontaine, David H Lee, Yulun Zhang. Nivedit Reddy Balam, Nathaniel Dennler, Sujay S Garlanka, Nikitas Dimitri Klapsis, and Stefanos Nikolaidis. Pyribs: A bare-bones python library for quality diversity optimization. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '23, pp. 220-229, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701191. 191. doi: 10.1145/3583131 35900377 URL
11....115/58383 35503337
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, IEEE, 2012. doi: 10. 1.91100/R.00013 2.636619.
Vassilis Vassiliades and Jean- Baptiste Mouret. Discovering the elite hypervolume by leveraging interspecies correlation. Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 18, pp. 149-156, New York, NY, USA, 2018. Association for Computing Machinery, ISBN 978 4503561833.. doi: 041144/3225455.320555 3205455. 3205602
URl.httts:://do
Vassilis Vassiliades, Konstantinos Chatzilygeroudis, and Jean- Saan-Bapiiste Mouret. Using centroidal voronoi tessellations scale up the multidimensional archive of phenotypic elites algorithm. 22:623
IEEE Transactions on Evolutionary Computation, 22:623-630, -300, 2016. URL https: ://api
semant www.occr..ooooooooooooooooo... htw.shhc.a....ooo/ooooaaaat13333
13

---

A PPGA PSEUDOCODE
Algorithm Proximal Policy Gradient Arborescence
Initial policy 8g VPPO instance to approximate V. Vm and move the search policy, number of QD iterations No. number of VPPO iterations estimate the objective-measure functions and gradients N1, number of VPPO iterations to move the search policy N2, branching population size X, and initial step size for xNES Cg
Input:
Initialize the search policy 0, 06. Initialize NES parameters μl, 0g1
for iter t- to N do
f. f.. m. Vm + VVPO..cmm www.cottteaccoiiiaiiie f(-), N1) ff - normalize(Vf1) ff,,), Vm +- normalize (Vm)
- update [.
for i 4- to À do c c~ (M, 2) // sample gradient coefficients
V. + co Vf Σ cy
8 t 0g V
*, ml rollout(()) (8))
A, + update__aaaeeeee archive (0,, fl, m²)
end for rank gradient coefficients V, by archive improvement A;
Adapt xNES parameters μ = n², Σ = Σ' based on improvement ranking A;
my where C,. y // construct multi-objective reward function 0g VPPO.train (0:: N2) // standard PPO training procedure
(0() Cy.os
if there is no change in the archive then Tg.
Restart xNES with μ
Set 0, to randomly selected existing cell 0, from the archive end if end for
Algorithm 2 Update Archive
Input: Solution 0 insert, episodic reward measures mi,... my archive A, archive
learning rate a Oine fine A[m] if A[m] nonempty else None, 0 incumbent policy A; = 0
if fine then insert into cell A(m]
fine & (1 - a) fine + af
A = finc
end
return A;
14

---

Algorithm 3 Vectorized-PPO (VPPO)
Input: Initial search policy *o,, objective functions to optimize f fi()), fx((), number of VPPO iterations N, number of parallel environments E, rollout length L
Initialize the vectorized agent म. vectorized (ectoriized_aeenn(Taa) x + 1)) for iter <- to N1 do rollout( agent, E, L, f) Note that S {Si, Sk. etc advantage A. returns G <- batch calculate (e A, R, f)
(S, A, S*)
0 batch gradient_deseennee
7t) // using the stochastic policy gradient
8
end for
Vf + 7o' H0,
return Vf
B HYPERPARAMETERS
Table 1: List of relevant hyperparameters for PPGA shared across all environments.
HYPERPARAMETER
VALUE
ACTOR NETWORK
[128, 128, ACTION DIM]
CRITIC NETWORK
[256, 256, 1]
N1
10
N2
10
PPO NUM MINIBATCHES
8
PPO NUM EPOCHS
4
OBSERVATION NORMALIZATION
TRUE
REWARD NORMALIZATION
TRUE
ROLLOUT LENGTH
128
C ABLATION AGAINST CMA-MAEGA
PPGA makes two key changes compared standard DQD algorithms such CMA-MAEGA: Walking the search policy with VPPO vs. weighted linear recombination of the gradients and replacing xNES. We compare walking the search policy with VPPO to using gradient recombination in the original formulation of CMA-MEGA. In addition, we ran an ablation using xNES as the outer-loop optimizer compared CMA-ES, However, the step-size adaptation parameter quickly diverges with CMA-ES and destabilizes training, and thus were unable to provide plots for this ablation. Fig. shows the comparison of walking the search policy with VPPO versus using weighted linear recombination of the gradients. We believe that the large gap in performance is due to the fact that we can take multiple steps with VPPO via N₂ hyperparameter. Weighted recombination results in single gradient step where the updated search policy may land too close to the previous search policy's cell. When we branch from the updated search policy, many-brancher agents will fall into overlapping cells, resulting in small archive improvement, which can lead to the emitter prematurely leaving a high-performing region of the search space.
D TD3GA IMPLEMENTATION DETAILS
As part of our ablation study, we implemented TD3GA, which differs from PPGA by replacing all PPO mechanisms with TD3 (Fujimoto al.) 2018). This implementation required several algorithmic decisions, as PPGA was originally designed to integrate with an on on-policy method like PPO rather than an off-police policy method like TD3, In this section, describe these decisions. In general, intend our decisions to make TD3GA operate as closely as possible to PPGA, and we leave it to future work explore whether variations of these decisions will further improve performance.
15

---

100
10000
400000
Best Reward
Coverage (18)
QD Scare
5000
200000
namee
2500
100000
20
PKSA-RECOMI
00
250000
S00000
250000 Num Evals
500000
2500C0
500000
Num Evals
Num Evals
Figure Ablation of walking the search policy with VPPO vs gradient recombination done in CMA-MEGACCM-MMAGA on the Humanoid environment.
Background: TD3 is off-policy actor-critic method designed for single-objective RL tasks. TD3 maintains an actor (i.c., a policy) that takes actions the environment and a critic that estimates the action-value funetion. TD3 also maintains replay buffer that stores experiences collected by the actor. Over time, the actor trained to optimize the critic. Simultaneously, based on experience in the replay buffer, the critic learns to better predict the aation-value function.
Design Decisions:
1. Number of crities: In TD3GA, we maintain TD3 critic for the objective function and one for each the measure functions. We also create separate critic for the weighted objective that is used when walking the search policy. We refer to these critics as the objective critic, measure critics, and walking critic.
2. Choice of actor for critic training: When training the critic, TD3 requires an actor that generates actions for states sampled from the replay buffer. Prior QD-RL methods that estimate objective gradients with TD3, e.g., PGA-ME (Nilsson & Cully 2021) and CMA- MEGA (TD3, ES) (Tjanaka al. 2022b), fulfill this role with a dedicated actor. This actor is referred to greedy actor since its primary purpose is optimize its performance with respect to the critic.
In theory, since TD3 is off-policy method, any actor, including greedy actor, can be used to train the critic. However, make TD3GA closer to PPGA, we instead use copy of the current search policy to train the critic. This decision provides TD3 instances with an on-policy nature that mirrors the PPO mechanisms found PPGA.
3. When to train crities: Similar to the PPO value functions in PPGA, we maintain all critics throughout the entire training run, updating them on every iteration.
4. Experience collection: This decision concerns which experience collected in the environ- ment should be inserted into the replay buffer. With the settings in paper. PPGA (and TD3GA) samples 300 policies per iteration, and each policy is evaluated for 10 episodes, with each episode having up 1,000 timesteps of experience; in total, these policies generate 3 million timesteps per iteration. The typical replay buffer size (Fujimoto et al. (018) in TD3 is million, meaning the buffer would be filled three times over if we inserted all of this experience, i.c., the critic would never be trained with the experience from two-thirds of all policies.
To ensure that we collect experience from many policies across many iterations, we make decisions. First, we only collect one episode of experience from each agent this already cuts down experience collected on each iteration to 300,000 timesteps. Second, we increase the replay buffer size million store experience across more iterations.
Note that there is no analog to the replay buffer in PPGA since PPO is an on-policy method. Instead, PPO regresses the value function based on experience collected while evaluating the policy.
5. Gradient computation: We begin by describing how prior method estimates the objective gradient with TD3. To estimate the objective gradient of a policy, CMA-MEGA (TD3, ES) samples batch of experience and passes the batch through the corresponding actor. The actions outputted by the actor are then inputted to the critic. Backgpropagating through the critic and the actor then provides the objective gradient.
16

---

Roughly, the above procedure corresponds to taking single step of TD3. However, in PPGA, the gradient is computed by taking the difference after multiple steps of PPO (the number of steps is determined by the hyperparameters N1 and N2. The straightforward approach to mirror this behavior in TD3GA is to also output a gradient after several steps of TD3. Thus, when training each critic, we also track the final state of the actor (recall that the actor used in critic training is a copy of the search policy), At the end of critic training, our gradient then the difference between the final actor and the original search policy.
For example, to compute the objective gradient, we train the objective critic with an actor that is copy of the search policy. While training the critic, the actor is updated that it maximizes the objective critic. After N1 steps, we compute the objective gradient as the difference between the actor and the original search policy.
6. Actor target networks: One TD3 mechanism that improved stability and performance was target networks, which are slowly updating versions of the actor and critic parameters. In TD3GA, it is straightforward apply this mechanism to the critic parameters.
However, since the actor is reset to the current search policy every iteration, it is difficult to maintain a single target network. Thus, on every iteration, the target network for the actor is simply reset the current search policy's ' parameters before the gradient computation.
Algorithm 4 shows the process for computing an objective gradient in TD3GA. The same process applies to computing measure gradients. The process for walking the search policy also similar, except that the reward a weighted combination the objective and measures (the weights come from the mean μ of the emitter's s coefficient distribution). Furthermore, when walking the search policy, we return the final actor instead a gradient.
Pseudocode:
Hyperparameters: TD3GA inherits all relevant hyperparameters from PPGA (Table TT. It also inherits TD3 hyperparameters from prior QD-RL works that incorporate TD3 Tjaaaka et al. 2022b Nilsson & Cully 202I), except for having larger replay buffer. We also increase the batch size used during critic training to mimic the batch size used by PPO to regress the value function. Table S lists hyperparameters shared across all environments. Note that the archive learning rate depends on the environment but is identical to that used in PPGA.
Table 2: List of hyperparameters used in TD3GA, shared across all environments.
HYPERPARAMETER
VALUE
ACTOR NETWORK
[128, 128, ACTION DIM]
CRITIC NETWORK
[256, 256, 1]
TRAINING STEPS FOR OBJECTIVE AND MEASURES (N))
10
TRAINING STEPS FOR WALKING (N2)
10
OPTIMIZER
ADAM
ADAM LEARNING RATE
3 10-1
TARGET NETWORK UPDATE RATE (T)
0.005
TARGET NETWORK UPDATE FREQUENCY (d)
2
SMOOTHING NOISE STANDARD DEVIATION (σp)
0.2
SMOOTHING NOISE CLIP (c)
0.5
DISCOUNT FACTOR (7)
0.99
REPLAY BUFFER SIZE
5,000,000
BATCH SIZE (Abttch)
48,000
17

---

Algorithm 4 TD3 Gradient Computation for the Objective. Adapted from TD3 (Fujimoto al. 2018)
Input: Current search policy params On. current TD3 critic networks Q and Q parameterized by ti and t2 respectively, current critic targets vi and Vi replay buffer B Hyperparameters: Training steps N1 or N2. target network update rate target network update frequency d, smoothing noise standard deviation pp, smoothing noise clip c, discount factor 7
batch size Abotch
Initialize actor Φ Opr actor target ø² Op
[Either for gradient computation for walking the search policy) for iter + to N1 do fr is replaced with the measures for measure gradients, weighted combination of the reward and measures for walking the search policy)
Sample mini-batch of Thatch transitions (8, a, from B
Train the crities)
à t -T + e,
y g+r min;=1,2 Q (s',a)
[This update is performed with Adam)
Update crities v; arg ming 인 >v (s)
if mod d then \Update & by the deterministic policy gradient with Adam) Σ VaQui (s, a) a)lm=ssls)) (o)
V (Ø)
(Update target networks:)
o/ - Tth + 7)2
② - TO
T)
end if
end for
(Note that 1h 12 Vi and 1//2 are maintained across calls to this function)
[When walking the search policy, we just return the new policy params Φ)
ff & By return V
E HYPERPARAMETER STUDY
We investigate the effects of changing the Nj and N2 hyperparameters on the performance of PPGA in the Humanoid domain. We run 4 seeds of PPGA on the following combinations of N₁ and Ng: (10, 5), (5, 10), and (1, 1), and compare against the baseline (10, 10). With these experiments, we wish address the following questions
1. How few PPO steps on both the objective- objective-measur measure Jacobian calculation and walking the current search policy can we take before noticing performance degradation?
2. How do asymmetric choices for N1 and N2 (i.e. more Jacobian calculation steps than walking steps and vice versa) affect performance?
(5, 10) achieves the most consistent results while achieving the same performance as the baseline, while (10, 5) results in very high run-to-run variance and lower coverage. This suggests that spending more computation on walking the current search policy is more important than approximating the objective-measure Jacobian. Nonetheless, setting, PPGA could be tuned to perform fewer N1 and N2 steps while still maintaining good performance. Finally, (1, 1) performs the worst, achieving slightly more than 50% of the baseline's performance, implying that there is significant performance degradation when too few Jacobian- calculation and walking steps are taken.
conclude that in more computationally constrained
18

---

1e5
1e4
1e2
(N1, N2) (10. 10)
1.00
(N1. N2) 15. 10)
QD Score
Reward
0.75
Coverage ((%)
0.8
(N1, (1.
(N1, N2) (10. 5)
0.4
0.25
0.2
0
0.00
0
6
2
2
Num Evals
1e5
Num Evals
1e5
Num Evals
1e5
Figure 8: Study of the effect different hyperparameter choices for N₁ and 22. N1 is the number of PPO steps used to calculate the objective-mennt Jacobian, and N2 is the number of PPO steps used to walk the search policy. All plots are averaged over 4 seeds. The shaded region is the 95% boostrapped confidence interval.
F PPO ABLATIONS
We perform ablations against standard PPO Humanoid, the most challenging of all domains, in order to compare PPGA's relative performance against standard RI. We first ablate how the measure functions affect performance. The algorithm "PPGA (No Measure)" performs exactly standard PPGA but with no measure functions. In this case, PPGA computes gradients for the RL objective when branching and deciding where in the archive move next. Unsurprisingly, PPGA (No Measures) achieves the same best reward as PPGA, but with less than half the archive coverage.
In the second ablation, we run vanilla PPO and store the intermediate policies in between mini-bater gradient descent steps in an archive. The algorithm, dubbed "PPO + Archive". achieves the same best reward as PPGA, but with less than 1 % archive coverage. Note that PPGA (No Measures) still performing an outer-loop optimization step of the QD-objective, thus achieving better coverage than PPO + Archive, whereas PPO Archive only optimizes for the RL objective.
Algorithm
QD-Score
Coverage
Best Reward
PPGA
3.59 x 105
98.67%
9677
PPGA (No Measures)
8.24 x 104
32.06%
9653
PPO Archive
3.30 103
0.08%
9651
Table 3: Ablation study of PPGA with various components on Humanoid. PPGA (No Measures) functions exactly PPGA, but only computes objective gradients and walks the search policy with respect to f. PPO + Archive runs standard PPO and stores the intermediate policy updates as policies into archive. Archives 10x 10.
19

---

G SCALING EXPERIMENTS
6000
Bed Rawward
4003
5000
2003
200000
400000
200000
400000
200000
200000
420000
1.0
0D Score
200000
400000
200000
100000
200000
100000
200000
400000
100
Coveroge
50
50
50
200000
400000
200000
400000
0
200000
400000
200000
400000
Num Evels
Num Evals
Num Evels
Num Evals
100
100
1000
75
50
25
25
5000 Oojective
10000
2000
4000
5000
2000
4000
6000
Objective
Objective
Objective
CMA-MEEATT
Figure 9: QD-Score, Coverage, Best Reward, and CCDF plots for PPGA and haselines, with 50x50 archives for all tasks except for Ant. Ant retains the same 10 archive resolution, as this is already sufficiently large.
We test the scalability of PPGA along axes the ability scale to larger archives and the ability to learn with more data. To test for the first property. we scale up the archive resolution to 50x50 for locomotion tasks with measures i.c. Humanoid, Walker2D, and Halfcheetah and compare against baselines. PPGA retains the same performance across tasks, with slight reductions in coverage. This due to PPGA being an entirely gradient-bart method, using gradients for branching and walking the search policy, whereas prior methods that employ ES can get lucky and randomly mutate policies into far away cells.
1e7
10000
100
Score
1.0
Best Rewarr
8000
Coverage (1%)
Avg. Performance
PGA.ME
60
4000
00
0.5
4000
2000
2000
20
0.0
1.0
0.0
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Num Evais
le6
Num Evals
le5
Num Evals
le6
Num Evals
le6
Figure 10: QD Metrics for 50x50 archives PPGA and PGA-ME trained to 1.2 million evaluations. Results are averaged over seeds. The additional "average performance" metric is presented to show how performance over all policies in the archive changes with additional training.
20

---

algorithm 50x50 archive with 1.2 million evaluations, more than twice long as the main experiments, of both PPGA and the state the art baseline PGA-ME, on Humanoid. We report additional metric, the average performance of the archive, which is the sum of scores of all policies divided by the total number of policies in the archive. This can also be interpreted as the normalized QD score. We find that PPGA continues to improve this metric, indicating that the episodic returns and thus performance of many policies in the archive continues to improve with additional training. We observe this effect much lesser extent with PGA-ME.
Finally,
H COMPARING TO PBT-ME (SAC)
400000
100
PAGA PBT-ME
10000
QD Score
300000
Best Roward
Coverage (1%)
200000
6000
4000
100000
2000
20
200000
400003
200000
400000
200000 400000
Num
Num Evals
Figure 11: Comparison to PBT-ME (SAC) on Humanoid, which uses Soft Actor-Critic (Haarnoja al. 2018 to compute the policy gradient when improving the agents.
Population- Based Training MAP-Elites (PBT-ME) (Pierrot & Flajolet 2023) is a recent QD-RL algorithm that alleviates hyperparameter sensitivity in QD-RL algorithms by evolving populations of agents and their hyperparameters, while also using the policy gradient formulation to improve the agents' performance. The evolved and optimized policies MAP-Eliter formulation. PBT-ME was run with Google TPUs - due to computational constraints, we were only able make comparisons against PBT-ME the Humanoid domain, which present here. Specifically, we compare to the PBT-ME (SAC) variant.
added to archive following the
21


Reviews:
[{"review_id": "0S5DuMiOdP", "reviewer": "Reviewer_RPaL", "summary": "The authors propose Proximal Policy Gradient Arborescence (PPGA), a new QD-RL algorithm that builds on a DQD algorithm, specifically CMA-MAEGA, with an on-policy RL algorithm, specifically PPO, as the gradient estimator. To make this integration more stable, the authors propose multiple changes: 1) replace the CMA-ES in CMA-MAEGA with a more contemporary xNES algorithm to update the distributions, as a solution to accommodate the noisy RL objective, 2) use PPO with weighted rewards to walk the search point to avoid gradient staleness. The authors also implement a vectorized PPO for efficient gradient estimation.\n\nEmpirically, the author demonstrates that PPGA achieves much higher quality solutions compared with previous QD-RL baselines with matching coverage rates in multiple Mujoco locomotion domains.", "questions": "I don't have more questions apart from the ones in the weaknesses section.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well-written and easy to follow.\n- The proposed techniques to accommodate the integration issues of PPO are all logically and empirically justified.\n- There are substantial empirical improvements over previous baselines, especially in terms of solution qualities. As a side note, I do find the introduction of the Complementary Cumulative Distribution Function provides a very intuitive way of evaluating the solution quality and diversity.", "weaknesses": "- At the beginning of Sec 3.2, the authors claim \"Being an approximate trust region method, it provides some formal guarantees on the quality of the gradient estimates\". Could the authors expand on this and more formally establish this claim? This claim is an important reason of choosing PPO since there are other parallelizable RL algorithm choices such as IMPALA[1].\n- I have a slight concern that all the ablation studies show a dramatic decrease in performance. Could finding a better set of hyperparameters instead of inheriting the PPGA hyperparameters help?\n\n[1] Espeholt, Lasse et al. \"IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures.\" Proceedings of the International Conference on Machine Learning (ICML). 2018.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YtWtrxY6qJ", "reviewer": "Reviewer_1LjB", "summary": "A RL policy can learn to maximize cumulative reward in an environment by discovering an optimal policy. This paper shows that there are potentially many different sets of behaviors that could achieve optimal or near optimal performance. For example the authors highlight that in the humanoid walker environment different strategies can be discovered that all perform well: jumping, galloping, walking... These strategies can all be characterized by some measurements that are computed on trajectories. Figure 1 demonstrates this concept quite well. It plots two different measures with a heatmap of how well the policy at each point fulfilled the main objective (locomotion)\n\nThere are already prior works which establish this idea of characterizing policies with measures and attempting to maximize diversity in measure space. There are works that focus on differentiable measures and works that use non differentiable measures. This paper considers non-differentiable measures and approximates them using the bellman equation.\n\nSeveral value functions are learned which each approximate the instantaneous measure functions (deltas) and the overall objective function f. ***Each measure function is the average of the instantaneous measurement (delta) in each state.***\n\nSince all value functions are differentiable then a gradient of policy parameters with respect to a linear combination of these value functions can be obtained. Different weights can be assigned to each value function to cause the actor update to move in a different direction in the archive / measure space.", "questions": "CMA-ES is introduced but not really elaborated upon. It seems to be very important in sampling different policy parameters. how is branching the policy parameters in different directions in measure space done?\n\nlooks like Section 3.3 contains unnecessary formalism which is not used elsewhere in the paper. why is it provided?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Overall this is an interesting work. Massive (4x) performance gain compared to baselines.\nNice interpretability of archive exploration. The archives produced by PPGA seem more\ninteresting to look at. There are more distinct peaks shown in Fig 3 than the baseline.", "weaknesses": "I would suggest the authors make the explanation of the policy sampling more clear since that is what confused me the most.\n\nThe notation for the gradient of the measures (\\nabla m) is not clear. Is it the gradient of the measure with respect to the policy parameters? (this is explained only later in the paper)\n\nI suggest moving pseudocode Algorithm 1 to the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5Rq8vl3Vzs", "reviewer": "Reviewer_2hvw", "summary": "This paper presents Proximal Policy Gradient Arborescence (PPGA), a novel algorithm that combines PPO with Differentiable Quality Diversity to improve the performance of QD-RL in challenging locomotion tasks. The authors propose several key changes to existing methods, including a vectorized implementation of PPO, generalizing CMA-based DQD algorithms using Natural Evolution Strategies, introducing Markovian Measure Proxies, and a new method for moving the search point in the archive. The experiment results show that PPGA achieves state-of-the-art results, with a 4x improvement in best reward over baselines on the challenging humanoid domain.", "questions": "1. Can you provide more insight into why PPO was specifically chosen over other RL algorithms for this work?\n2. How does the proposed PPGA algorithm perform in other domains and tasks beyond locomotion?\n3. Can you discuss the scalability of the proposed algorithm, especially in comparison to existing methods?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses a significant gap in performance between QD-RL and standard RL algorithms on continuous control tasks. The results demonstrate state-of-the-art performance of PPGA, which combines the strengths of PPO and DQD, on challenging locomotion tasks, with a 4x improvement in best reward over baselines.\n2. The paper provides a clear and well-structured presentation of the proposed algorithm and its components.", "weaknesses": "1. The paper could benefit from a more detailed comparison with other QD-RL methods and an explanation of why PPO was specifically chosen over other RL algorithms.\n2. The generalizability of the proposed algorithm to other domains and tasks beyond locomotion is not discussed.\n3. It would be better to see some discussion about the scalability of the proposed algorithm, especially in comparison to existing methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Uw4GnZ11gI", "reviewer": "Reviewer_vTCA", "summary": "The authors propose PPGA, a QDRL algorithm where the RL part is based on PPO, an on-policy RL algorithm, whereas all existing QDRL algorithms use the off-policy PPO. This change makes it possible to benefit from the good parallelization capabilities of PPO, and the authors claim that there are also other interesting synergies between PPO and their QD approach. The authors show that PPGA outperforms previous SOTA QDRL algorithms in four locomotion benchmarks.\n\nAfter the authors rebuttal and given their revised version, I change my evaluation to \"accept\".", "questions": "To be fully transparent, this is the third time I'm reviewing this paper, after ICML23 and NeurIPS23. Each time I was in favor of accepting the paper because I believe the proposed algorithm is truly interesting, but each time the authors failed to convince some reviewers, mostly due to some writing issues and insufficient focus on the comparison between TD3GA and PPGA. I hope this time could be the right time with a further writing effort that I will try to contribute to below. So my review will mostly focus on writing aspects, but keep in mind that the TD3GA vs PPGA comparison is crucial and not even mentioned in the main paper.\n\nAbstract: \n\n- \"Existing QD-RL approaches have been constrained to sample efficient, deterministic off-policy RL algorithms and/or evolution strategies, *and struggle with highly stochastic environments*.\" -> the rest of the abstract makes it clear that you switch to on-policy RL, but it does not make clear that you will solve the highly stochastic environments issue. Do you really need to mention that? If yes, you need to mention how you will solve it.\n\n- \"propose several changes\" -> changes wrt what? It is a weird formulation, you have a new algorithm, you propose new things, no need to mention that...\n\nIntroduction:\n\nparag 1 is OK (maybe a ref at the end of the sentence finishing with \"high-quality solutions\" or merge the sentence with the next ones, where the references are).\n\nparag 2 has several issues:\n\n- \"For example, all QD-RL algorithms for locomotion to date use non-differentiable measure functions, which in most cases prevents direct RL optimization.\"\n\n-> At this point, the standard ML reader does not know what a measure function is, \n\n-> I don't agree that having non-differentiable measure functions prevents direct RL optimization. RL methods are precisely good at approximating some gradients when they are not available. Even if you want to discuss this with me, this sentence is ill-placed, as the standard reader cannot get its meaning.\n\n- \"Prior methods that investigated combining DQD\". You should re-explain the acronym, doing it once in the abstract is not enough.\n\n- \"However, given the gap in performance between standard RL and QD-RL algorithms in terms of best-performing policy, we believe that DQD algorithms, under a different formulation more synergistic with its underlying mechanisms, can close this gap. We instead believe that one or both of existing DQD and RL methods must be adapted to each other in order to maximally exploit their synergy.\"\n\n-> Both sentences say more or less the same thing, I suspect this is a last-minute-no-reread edition issue.\n\n- \"maintain a single search point within the archive that\" -> at this point, the standard ML reader does not know what the search point is, and what the archive is.\n\n- \"The question we aim to answer becomes clear through this high-level view – can we better adapt DQD algorithms to challenging RL domains by exploiting its synergy with PPO?\" -> the third time you mention exploiting this synergy in the same paragraph...\n\nI afraid that, with all the points above, you have already lost the standard reader, who won't read your paper any further. Instead, you must give a high-level view of PPGA from the RL viewpoint, with the RL vocabulary (a search point is a policy, etc.).\n\n- As contribution (1), you propose an implementation ... : I see no link to a source code in the paper, so you should not mention such a contribution [EDIT: OK, the source code is in the supplementary, forget this comment]\n\n- What a \"non-stationary QDRL task\"? \n\n- Contrib (4) sould be reformulated with the RL vocabulary. Otherwise, rather submit your paper to GECCO, as I already advised you twice...\n\n- where T is (the) episode length\n\n- the deep neural network represents *a* state-action mapping, not necessarily the optimal one.\n\n### Deep RL background:\n\n- About your Deep RL background, it is close to good (there is no major mistake), but it is still confusing for the non-expert and you can do a better job.\n- I think the point you want to make is that PPO is on-policy. In the current classification, it is not in the \"on-policy\" part, but in the \"trust region\" part\n- Mentioning actor-critic in the on-policy part the way you do brings confusion. It is true that A2C and A3C are actor-critic and on-policy, but DDPG, TD3, SAC and others are actor-critic too and they are off-policy.\n- I think what you need is the distinction between policy-based methods (Reinforce, A2C, TRPO, PPO) which derive their gradient from the policy and are on-policy, and value-based methods (DQN, DDPG, TD3, SAC, ...) which derive their gradient from the critic and are off-policy.\n\nSee e.g. Nachum, O., Norouzi, M., Xu, K., & Schuurmans, D. (2017). Bridging the gap between value and policy based reinforcement learning. Advances in neural information processing systems, 30.\n\n### Other points\n\n- the equation with L(theta) should finish with a dot.\n\n- In the QD optimization section, don't you want to mention QDRL in the last parag?\n\n- \"gradients around the search point ∇ 1 , ..., ∇ λ\" -> gradients ∇ 1 , ..., ∇ λ around the search point. \n\n- Again, why not call the search point \"the current policy\"? The same for \"solutions\", they are policies.\n\n- \"some minimum threshold\". Why call this a minimum threshold? Threshold for what? I rather see it as an exploration bonus...\n\n- \"in the direction of the archive that is least\" -> doesn't this also take performance into account?\n\n- In 2.4: \"In prior work (ref) ... In this work\" -> You should not write this in a way that let us know who you are. *Your paper could be desk-rejected for that. Actually, this is transparent given the (too) many self-references, but you have to follow the rules*.\n\n- In 3.2, I'm afraid the claim that trust region methods provide formal guarantees on the quality of the gradient estimates is wrong. The proof in TRPO comes with unrealistic assumptions that are always violated in experimental RL work.\n\n- You use the MMPs as rewards to optimize. So it means that your algorithm is looking for as much leg contact as possible. Shouldn't it be looking for as much \"leg contact diversity\" as possible instead? This is unclear. Could you clarify?\n\n- \"We additionally modify the computation of the policy gradient into a batched policy gradient method, where intermediate gradient estimates of each function w.r.t. policy params only flow back to the parameters corresponding to respective individual policies during minibatch gradient descent.\" -> This part is very unclear to me, a small diagram or equations would probably help.\n\n- jacobian -> Jacobian\n\n- There are many considerations about using constant variance or not. Actually in the literature, there are 3 options: using a constant variance, using a tunable variance which is not a function of states, and using a tunable state-dependent variance where the NN outputs a mean and a variance for each state. The second one is used e.g. in the TRPO paper, see Fig. 3 here: https://proceedings.mlr.press/v37/schulman15.pdf\nI think you need to further study this point, your work is not convincing in that respect. The fact that you \"disable gradient flow\" to the variance parameter or not depending on the environment is not satisfactory at all.\n\n- About Section 3.3, I think the first paragraph which establishes that xNES is a better option that CMA-ES in your context could be moved in an appendix together with the corresponding sutdy, as this is not central to your story. You could make profit of the earned space to add a paragraph about the comparison between TD3GA and PPGA (with selected results), which is much more important.\n\n- At the end of 3.4, you mention the outer optimization loop, but the inner/outer loop distinction has not been made explicit in the main paper.\n\n- \"We use an archive learning rate of 0.1, 0.15, 0.1, and 1.0...\" -> The fact that there is such a learning rate is not explained before.\n\n- All experimental figures and tables make a poor use of space. By reworking this aspect you can both save more space and make your results more readable and explicit.\n\n- In Fig. 4, using +/- one std as variance information is a bad practice in RL, where the variance is generally not Gaussian. See \nPatterson, A., Neumann, S., White, M., & White, A. (2020). Draft: Empirical Design in Reinforcement Learning. Journal of Artificial Intelligence Research, 1. and Agarwal, R., Schwarzer, M., Castro, P. S., Courville, A. C., & Bellemare, M. (2021). Deep reinforcement learning at the edge of the statistical precipice. Advances in neural information processing systems, 34, 29304-29320, the latter comes with a useful visualization library.\n\n- Figure 4 is cited before fig 3, you should reorder\n\n- \"We present a new method, PPGA, which is one of the first QD-RL methods to leverage on-policy RL,\" -> one of the first, so what are the others?\n\n- \"We show that DQD algorithms and on-policy RL have emergent synergies that make them work particularly well with each other.\" -> I'm sorry but this point does not emerge clearly from reading the paper. You should have somewhere a paragraph about the investigations of these synergies.\n\n- Your paper needs slightly more than 9 pages. Again, *it could have been desk-rejected for that*. Please follow the rules.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The proposed PPGA algorithm is novel and interesting. It outperforms relevant previous SOTA baselines. To me, this should be sufficient to warrant publication.\n\n- The experimental study looks correct.", "weaknesses": "- The paper (still) needs improvements in the presentation to make it more interesting to a large machine learning audience.\n\n- The claim about the synergies between DQD and PPO looks insufficiently backed-up. In particular, the main paper does not even mention the TD3GA algorithm, while the study of combining DQD with TD3 is crucial to understand these synergies. More generally, your central claim is that using on-policy RL better fits the DQD framework, so the comparison to TD3GA should be central.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)