# Proximal Policy Gradient Arborescence for
Quality Diversity Reinforcement Learning

Sumeet Batra
University of Southern California
Los Angeles, CA 90089
<EMAIL_ADDRESS>
&Bryon Tjanaka
University of Southern California
Los Angeles, CA 90089
<EMAIL_ADDRESS>&Matthew C. Fontaine
University of Southern California
Los Angeles, CA 90089
<EMAIL_ADDRESS>
&Aleksei Petrenko
University of Southern California
Los Angeles, CA 90089
<EMAIL_ADDRESS>
&Stefanos Nikolaidis
University of Southern California
Los Angeles, CA 90089
<EMAIL_ADDRESS>
&Gaurav Sukhatme
University of Southern California
Los Angeles, CA 90089
<EMAIL_ADDRESS>

###### Abstract

Training generally capable agents that perform well in unseen dynamic
environments is a long-term goal of robot learning. Quality Diversity
Reinforcement Learning (QD-RL) is an emerging class of reinforcement learning
(RL) algorithms that blend insights from Quality Diversity (QD) and RL to
produce a collection of high performing and behaviorally diverse policies with
respect to a behavioral embedding. Existing QD-RL approaches have thus far
taken advantage of sample-efficient off-policy RL algorithms. However, recent
advances in high-throughput, massively parallelized robotic simulators have
opened the door for algorithms that can take advantage of such parallelism,
and it is unclear how to scale existing off-policy QD-RL methods to these new
data-rich regimes. In this work, we take the first steps to combine on-policy
RL methods, specifically Proximal Policy Optimization (PPO), that can leverage
massive parallelism, with QD, and propose a new QD-RL method with these high-
throughput simulators and on-policy training in mind. Our proposed Proximal
Policy Gradient Arborescence (PPGA) algorithm yields a 4x improvement over
baselines on the challenging humanoid domain.

##  1 Introduction

Quality Diversity (QD) optimization is a class of algorithms that offers a
principled way to combine exploitation with exploration in order to produce a
collection of high performing and behaviorally diverse solutions. For example,
a practitioner may want many policies that produce high-performing gaits, but
vary in how they walk, skip, run, or limp to achieve that gait. The QD problem
[4] considers an objective function $f(\cdot)$ to maximize and $k$ measure
functions $m_{1}(\cdot)...m_{k}(\cdot)$, which characterize the agent’s
behavior. A QD algorithm aims to output a collection of solutions that
maximize $f(\cdot)$ while being diverse w.r.t. these measure functions.
Quality Diversity Reinforcement Learning (QD-RL) exploits the sequential
decision making markov structure in the problem formulation to leverage RL to
estimate gradients with respect to performance and diversity. QD-RL algorithms
empower practitioners to select from several high-performing policies for
deployment after training, rather than being stuck with the final converged
policy in traditional RL.

Figure 1: PPGA finds a diverse archive of high-performing locomotion behaviors
for a humanoid agent by combining PPO gradient approximations with
Differentiable Quality Diversity algorithms. The archive’s dimensions
correspond to the measures $m_{1}$ and $m_{2}$, i.e., the proportion of time
that the left and right feet contact the ground. The color of 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.

Current state-of-the-art QD-RL methods leverage off-policy RL, specifically
TD3, and/or evolutionary strategies, to estimate the objective and measure
gradients. These approaches reuse previously collected data to be sample
efficient and make continuous improvements to the policies in the archive, and
have shown great success in robotic locomotion and exploration tasks [37, 39,
48]. They are particularly useful in computationally constrained settings and
benefit from faster sequential sampling. However, recent advances in GPU-
Accelerated, high-throughput simulation [32, 17, 38] have led to a new
paradigm for on-policy RL methods to take advantage of massive parallelism for
high quality gradient estimates and faster wall-clock time convergence at the
expense of sample-efficiency. Specifically, algorithms such as PPO [45] have
shown great success in leveraging massive parallelism to solve increasingly
more difficult simulated and real robotics tasks [40, 24, 2]. It is not clear
how to bring existing QD-RL methods into this new training paradigm.

To date, there are no existing QD-RL methods that take advantage of this new
data-rich regime, nor have there been attempts to combine on-policy RL methods
with QD-RL to compare to existing off-policy QD-RL methods. In the QD-RL
setting, not only is it important to provide high-quality performance and
measure gradients for the algorithm to perform effectively, it is also
important to leverage as much compute as is available since we wish to find a
collection of high performing policies, as opposed to a single policy in the
traditional RL setting. Therefore, we believe that the field of QD-RL would
benefit from a method that leverages a highly parallelizable, on-policy RL
algorithm to perform QD-RL optimization.

We observe that recent works in differentiable quality diversity (DQD) [12]
algorithms – solving the first-order form of QD optimization – function in a
manner highly synergistic with on-policy RL. State-of-the-art DQD algorithms
maintain a single search point that explores one region of the behavioral
embedding at a time. This local search is similar to how on-policy RL methods
update from only local on-policy data. Prior methods [48] have attempted to
combine off-policy RL with DQD. However, this ignores the local search nature
of the DQD algorithm and does not scale to data-rich regimes. Thus, we
hypothesize that on-policy RL, specifically PPO, will greatly outperform prior
work that combines DQD algorithms with off-policy RL, due to the local search
synergy.

Our key insight is to leverage parallel PPO implementations to accurately
estimate on-policy objective and measure gradients. By leveraging massive
parallelism to compute accurate gradients for a single search point, the DQD
algorithm can then branch many nearby policies for parallel evaluation. The
search forms a gradient arborescence that efficiently fills the behavioral
embedding with diverse policies that each maximize their reward by amortizing
the cost of the gradient approximation across many branched policies.
Specifically, our work makes the following contributions:

  1. 1.

We introduce the Proximal Policy Gradient Arborescence (PPGA) algorithm that
leverages a modified, vectorized form Proximal Policy Optimization we call
VPPO (Sec. 3) to estimate the objective and measure gradients, as well as,
walk the policy in each ascending step of the gradient arborescence.

  2. 2.

We view prior covariance matrix adaptation-based DQD algorithms (in
particular, CMA-ES-based) as instantiations of Natural Evolution Strategies
(NES)-based methods and we propose combining DQD with an alternative evolution
strategy, xNES, that is more robust to the noise scale and non-stationarity
typical of QD-RL tasks (Sec. 3).

  3. 3.

We evaluate PPGA on four Quality Diversity locomotion domains built in Brax.
In addition to achieving state-of-the-art results on all four domains, PPGA
achieves a 4x improvement in performance in the high-dimensional humanoid
domain (Sec. 4).

##  2 Prior Work

###  2.1 Deep Reinforcement Learning

Reinforcement Learning algorithms search for policies, a mapping of states to
actions, that maximize cumulative reward in an environment. RL typically
assumes the discrete-time Markov Decision Process formalism
$(\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\gamma)$ where $\mathcal{S}$
and $\mathcal{A}$ are the state and action spaces respectively,
$\mathcal{R}(s,a)$ is the reward function, $\mathcal{P}(s^{\prime}|s,a)$
defines state transition probabilities, and $\gamma$ is the discount factor.
The RL objective is to maximize the discounted episodic return of a policy
$\mathbb{E}\left[\sum_{k=0}^{T-1}\gamma^{k}R(s_{k},a_{k})\right]$ where $T$ is
episode length. Deep Reinforcement Learning solves the RL problem by finding a
policy $\pi_{\theta}(a_{t}|s_{t})$ parameterized by a deep neural network
$\theta$ that represents the optimal state-action mapping.

On-policy Deep RL methods directly learn the policy $\pi_{\theta}$ using
experience collected by that policy or a recent version thereof. Contemporary
Actor-Critic methods [33] fit the value function $V_{\phi}(s_{t})$ to
discounted returns and estimate the advantage
$\hat{A}_{t}=\sum_{k=t}^{T-1}\gamma^{k}R(s_{k},a_{k})-V_{\phi}(s_{t})$, which
corresponds to the value of an action over the current policy [44]. From here,
the gradient of the objective w.r.t. $\theta$, or policy gradient, can be
estimated as
$\hat{\mathbb{E}}_{t}\left[\nabla_{\theta}\text{log}\pi_{\theta}(a_{t}|s_{t})\hat{A}_{t}\right]$,
and the policy $\pi_{\theta}$ is trained using mini-batch gradient descent.

Trust region policy gradient Deep RL methods constrain the policy updates to
maintain the proximity of $\pi_{\theta}$ to the behavior policy
$\pi_{\theta_{old}}$ which was used to collect the experience. TRPO [43] takes
the largest policy improvement step that satisfies the strict KL-divergence
constraint. Proximal Policy Optimization (PPO) [45] approximates the trust
region approach by optimizing the clipped surrogate objective where
$r_{t}(\theta)=\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}$
is the importance sampling ratio:

$L(\theta)=\hat{\mathbb{E}}_{\pi_{\theta}}\left[\text{min}(r_{t}(\theta)\hat{A}_{t}),\text{clip}(r_{t}(\theta),1-\epsilon,1+\epsilon)\hat{A}_{t}\right]$

Off-policy Deep RL algorithms learn parameterized state-action value functions
$Q_{\theta}(s_{t},a_{t})$ that estimate the value of taking action $a_{t}$
given state $s_{t}$. Greedy policy
$\operatorname*{argmax}_{a}Q_{\theta}(s_{t},a_{t})$, or an
$\varepsilon$-greedy variation thereof, generates actions. Q-functions can be
learned from experience collected by recent or past versions of the policy or
another policy altogether, hence the off-policy classification.

In continuous control problems, it can be difficult to find
$a^{*}=\operatorname*{argmax}_{a}Q_{\theta}(s_{t},a_{t})$ due to an infinite
number of possible actions. To work around this issue, off-policy methods such
as DDPG [30] and TD3 [18] learn a deterministic policy $\mu_{\phi}(s_{t})$ by
solving $max_{\phi}(Q_{\theta}(s_{t},u_{\phi}(s_{t}))$ using gradient ascent.

###  2.2 Quality Diversity Optimization

Quality Diversity problems provide an objective function $f(\cdot)$ and $k$
measure functions $m_{1}(\cdot)...m_{k}(\cdot)$, represented jointly as
$\textbf{m}(\cdot)$ [12], which defines an embedding the QD algorithm should
span with diverse solutions. The QD objective is to find a solution which
maximizes $f$ for every possible output of m. However, the embedding formed by
m is continuous, so the embedding space is discretized into a tessellation of
$M$ cells. The QD objective then becomes to maximize
$\sum_{i=1}^{M}f(\theta_{i})$, where $\theta_{i}$ is a solution whose measures
$\textbf{m}(\theta_{i})$ fall in cell $i$ of the tesselation. Differentiable
Quality Diversity (DQD) [12] considers the first-order QD problem where the
objective and measure functions are differentiable, with provided gradients
represented as $\nabla f(\cdot)$ and $\nabla\textbf{m}(\cdot)$.

QD algorithms originated with the NSLC [28, 29] and MAP-Elites [35, 8]
algorithms. While these early QD algorithms were genetic algorithms, modern QD
algorithms incorporate modern optimization techniques such as Bayesian
optimization [26], evolution strategies [15, 7, 6], gradient ascent [12, 13],
surrogate models [51, 3, 19], and differential evolution [5]. Several works
have applied QD optimization to generative design [23, 20, 19], procedural
content generation [22, 16, 9, 27, 46, 42, 41], human-robot interaction [11,
14], and robot manipulation [34].

Figure 2:  PPGA estimates $\nabla f,\nabla\textbf{m}$ with PPO. We randomly
sample gradient coefficients c and perform weighted linear recombination of
the objective-measure gradients with c as the weights. This produces a
population of gradients that in turn result in a population of branched
policies. The policies are evaluated and inserted into the archive. xNES
adapts the gradient coefficient distribution based on these insertions towards
maximal archive improvement. The new mean of the coefficient distribution is
used to walk the search policy towards a new, potentially unexplored region of
the archive.

###  2.3 Quality Diversity Reinforcement Learning

QD-RL focuses on the problem of producing a collection of high-performing and
diverse policies by framing the sequential, decision making RL task as a QD
optimization problem. Efficient methods for solving QD-RL problems approximate
the gradients of both a policy’s performance and behavior via measure
functions that map to a low dimensional behavioral embedding. These gradients
are then combined with ideas from quality diversity optimization that maintain
a diverse collection of solutions and drive the search towards discovering
novel policies.

QD-RL methods can be roughly divided into two subgroups. The first set of
approaches directly optimize 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 [37]
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 [50] on the same set of
agents to improve diversity and fill new, unexplored cells. Similarly, QDPG
[39] derives a 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
maintains a single search policy that explores new local regions one at a
time. To efficiently populate the archive of diverse policies, the algorithm
branches many policies from the current search policy by sampling different
combinations of objective and measure gradients. A DQD algorithm then moves
the search policy in the combination of objective and measure gradients that
yielded the largest archive improvement according to the branched polices. In
prior work [48], the authors considered objective gradient approximations via
TD3 and OpenAI-ES, while approximating the measure function gradients with
OpenAI-ES.

We note that the DQD formulation is closely aligned with the concept of on-
policy RL. DQD algorithms maintain a single search policy from which new
policies are branched, and moves this policy through the archive via gradient
ascent towards underexplored regions, using only online data collected from
the current search policy. Yet, none of the existing DQD-based QD-RL methods
exploit this property. CMA-MAEGA(TD3, ES) uses off-policy RL despite the fact
that old experience is used only to improve a single policy at a time, making
it less efficient than PGA-ME. Furthermore, both CMA-MAEGA(TD3, ES) and
separable CMA-MAE use evolutionary strategies to approximate either the
objective and/or measure gradients, ignoring the Markov structure inherent in
QD-RL problems. Finally, it is unclear how to scale either of the QD-RL method
subgroups to highly parallelized, GPU-accelerated simulators given that all
current methods use TD3, which is designed to be efficient for sequential RL.
We aim to improve the the performance of DQD-based QD-RL methods by
integrating techniques from the on-policy RL literature that work well in
these parallelized and data-rich regimes.

##  3 Proposed Method: The Proximal Policy Gradient Arborescence Algorithm

###  3.1 CMA-MAEGA

Our proposed PPGA algorithm builds off of the concept of a gradient
arborescence first proposed by the DQD algorithm CMA-MEGA. Given a gradient
basis matrix in objective-measure space, one can branch off policies in
arbitrary directions in behavior embedding by weighting and linearly combining
the gradient vectors in different ways. CMA-ES can then be applied to optimize
for the optimal distribution of gradient coefficients, rather than the much
higher dimensional policy parameter distribution. The arborescence is directed
by ascending the QD objective in each search step determined by the
distriubtion of gradient coefficients given by CMA-ES.

CMA-MEGA maintains a MAP-Elites archive that divides the $k$-dimensional
embedding space into equally sized cells. To optimize for new candidate
solutions, CMA-MEGA maintains a solution point in parameter space
$\theta_{\mu}\in\mathbb{R}^{N}$ whose behaviors
$m_{1}(\theta_{\mu})...m_{k}(\theta_{\mu})$ correspond to a position in the
embedding. A DQD algorithm assumes access to gradients of the objective and
measure functions. However, the optimal search direction depends on the state
of the archive. To resolve this, CMA-MEGA maintains a CMA-ES instance that
optimizes gradient coefficients for the objective and measure functions by
maintaining a mean $\mu$ and covariance matrix $\Sigma$ in the low dimensional
embedding space $\mathbb{R}^{k+1}\ll\mathbb{R}^{N}$. In each step, we sample
$\lambda$ gradient coefficient vectors $\textbf{c}\in\mathbb{R}^{k+1}$ to
compute branching gradient steps. We linearly combine the objective and
measure gradients to form each branching step: $\textbf{c}\nabla g=c_{0}\nabla
f+c_{1}\nabla m_{1}+...+c_{k}\nabla m_{k}$. Each set of coefficients forms new
candidate search positions:
$\theta^{{}^{\prime}}=\theta_{\mu}+\textbf{c}\nabla g$. From one set of
objective and measure gradients, we sample $\lambda$ new solutions for
evaluation that vary in their objective and embedding position. We evaluate
each solution $\theta^{{}^{\prime}}$ and compute the embedding
$m_{1}(\theta^{{}^{\prime}}),...,m_{k}(\theta^{{}^{\prime}})$, which
corresponds to some archive cell with an incumbent solution
$\theta_{old},f(\theta_{old})$ or a new unexplored cell whose
$f(\theta_{old})$ is set to a minimum threshold. We rank the branched
solutions according to the improvement on the objective
$f(\theta^{{}^{\prime}})-f(\theta_{old})$, and CMA-ES steps $\mu,\Sigma$ in
the direction of the natural gradient of the QD objective with respect to the
gradient coefficients. CMA-MEGA steps the solution point $\theta_{\mu}$ based
on the log-likelihoods of the solutions with respect to the improvement
ranking.

The state-of-the-art DQD algorithm CMA-MAEGA [13] introduced the concept of
soft archives to CMA-MEGA. Instead of maintaining the best solution in each
cell, the archive maintains a threshold $t_{e}$ and updates the threshold by
$t_{e}\leftarrow(1-\alpha)t_{e}+\alpha f(\theta{{}^{\prime}})$ when a new
solution $\theta{{}^{\prime}}$ crosses the threshold of its cell $e$. The
hyperparameter $0\leq\alpha\leq 1$ controls how quickly the soft archive
changes. Soft archives have many theoretical and practical benefits discussed
in prior work. Our proposed PPGA algorithm builds directly off the CMA-MAEGA
algorithm.

###  3.2 Replacing CMA-ES with a Natural Evolution Strategy

Next, we motivate replacing CMA-ES with a Natural Evolution Strategy (NES) in
PPGA. NES methods maintain a distribution in search space, parameterized by a
Gaussian distribution. On each iteration, we sample search directions from the
distribution $\phi=(\mu,\Sigma)$. Given an expected objective
$J(\phi)\approx\frac{1}{n}\sum_{i=1}^{n}f(x_{i})p(x_{i}|\phi)$, we compute the
natural gradient $\nabla_{\phi}\mathbf{F}^{-1}(\phi)J(\phi)$ with respect to
$\phi$ and step $\mu$ in the direction of the natural gradient and update
$\Sigma$ according to the observed curvature.

Prior works [21, 1] show that CMA-ES belongs in the NES family by constructing
a bidirectional mapping between CMA-ES and NES updates. As both methods are
natural gradient optimizers with invariance to order preserving
transformations of $f$, we view CMA-MEGA and CMA-MAEGA as a instantiations of
a general class of Natural Evolution Strategy DQD algorithms.

In this paper, we propose replacing CMA-ES with the Exponential Natural
Evolution Strategy (xNES) [21], which makes several improvements over prior
NES algorithms. Prior work [36] shows that CMA-ES’s cummulative step-size
adaptation (CSA) mechanism is unstable in noisy and non-stationary RL domains.
When developing the PPGA algorithm, we observed similar exploding step-size
($\sigma$) updates, which over time produced numerical errors and destabilized
training. We followed the recommendation of prior work [36] that showed the
natural gradient step-size adaptation
($\nabla_{\sigma}=tr(\nabla_{\Sigma})/d,\Sigma\in\mathbb{R}^{d\times d}$) of
xNES avoids such issues in RL domains.

###  3.3 Policy Gradients for Differentiable Quality Diversity Optimization

Unlike the standard DQD formulation in which the analytical gradients of $f$
and m can be computed, the QD-RL setting considers the case in which these
functions are non-differentiable and must be approximated with model-free RL.
We formulate the control problem as a finite-horizon Markov Decision Process
(MDP) over discrete time
$(\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{P},\gamma)$ and optimize the
policy gradient objective
$\nabla_{\theta}J(\theta)=\hat{\mathbb{E}}_{t}\left[\nabla_{\theta}\text{log}\pi_{\theta}(a_{t}|s_{t})\hat{A}_{t}\right]$.

PPO is an attractive choice as our gradient estimator because of its ability
to scale with additional parallel environments, and it being an approximate
trust region method provides some formal guarantees on the quality of the
gradient estimates. This is particularly important in the QD-RL setting where
the QD-objective is highly non-stationary. We utilize PPO to 1. estimate the
gradients of the objective and measures $\nabla f,\nabla\textbf{m}$ and 2.
move the search policy after $\mu,\Sigma$ have been adapted (we study the
effect of this decision via ablation Sec. 4.3). We make several nontrivial
modifications to the original PPO algorithm in order to adapt it to the DQD
setting, resulting in a new algorithm we call vectorized-PPO (VPPO). The
details of this implementation, including how VPPO computes the objective-
measure jacobian, are described in Appendix B. Of particularly importance is
making use of a fixed standard deviation parameter versus adaptive standard
deviation. PPO employs a learned standard deviation parameter that
parameterizes the action distribution on all agents, which decays over time
and reduces the algorithm’s ability to explore in favor of converging more
quickly to the optimal policy. In some environments, narrowing the action
distribution can help with agent performance, whereas in others, it can hinder
exploration and negatively impact our algorithm’s overall performance. To this
end, we make adapting the standard deviation a configurable hyperparameter.

It is often the case that QD problems contain non-Markovian measure functions.
For robot locomotion tasks, the standard measure function is the proportional
foot contact time with the ground
$m_{i}(\theta)=\frac{1}{T}\sum_{t=0}^{T}\delta_{i}(t)$ for each leg
$i,i=1...k$. However, this measure function is defined on a trajectory (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 a
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 state-
dependent, i.e., $m_{i}(s_{t},a_{t}|\pi_{\theta})=\delta_{i}(t)$, where the
Kronecker delta $\delta_{i}(t)$ indicates whether the $i$’th leg is in contact
with the ground or not at time $t$. We can then use the exact same MDP as the
standard RL formulation and replace the reward function with
$m_{i}(s_{t},a_{t}|\pi_{\theta})$.

Finally, instead of performing weighted recombination, we leverage the large
quantities of on-policy data available to us in this data-rich regime to walk
the search policy in the direction of greatest archive improvement using
$N_{2}$ iterations of VPPO, where $N_{2}$ is a configurable hyperpameter. This
choice is ablated in Sec. 4.3. Recall that the xNES update step produces a new
mean and covariance matrix $\mu^{\prime},\Sigma^{\prime}$ in objective-measure
gradient coefficient space. The updated mean gradient coefficients
$\mu^{\prime}$ describe a movement vector in the archive that will result in
the greatest archive improvement. We use these coefficients to parameterize a
new multi-objective reward function
$R^{\prime}(s_{t},a_{t}|\pi_{\theta})=c_{0}R_{RL}(s_{t},a_{t}|\pi_{\theta})+\sum_{j=1}^{k}c_{i}m_{i}(s_{t},a_{t}|\pi_{\theta})$.
Optimizing this function with VPPO allows us to walk the search policy
$\theta_{\mu}$ in the direction of greatest archive improvement by iteratively
taking conservative steps, where the magnitude of the movement is controllable
by $N_{2}$. We provide the full pseudocode in Algorithm 1.

Algorithm 1 Proximal Policy Gradient Arborescence (PPGA)

Input: Initial solution $\theta_{0}$, VPPO instance to approximate $\nabla
f,\nabla\textbf{m}$ and move the search policy, number of QD iterations
$N_{Q}$, number of VPPO iterations to estimate the objective-measure functions
and gradients $N_{1}$, number of VPPO iterations to move the search policy
$N_{2}$, branching population size $\lambda$, and an initial step size for
xNES $\sigma_{g}$

Initialize the search policy $\theta_{\mu}=\theta_{0}$. Initialize NES
parameters $\mu,\Sigma=\sigma_{g}I$

for iter $\leftarrow$ 1 to $N$ do

$f,\nabla
f,\textbf{{m}},\nabla\textbf{{m}}\leftarrow\text{VPPO}(\theta_{\mu},f,\mathbf{m},N_{1})$

$\nabla f\leftarrow\text{normalize}(\nabla
f),\nabla\textbf{{m}}\leftarrow\text{normalize}(\nabla\textbf{{m}})$

update _archive($\theta_{\mu},f,\textbf{{m}}$)

for $i\leftarrow 1\;\textbf{to}\;\lambda$ do

$c\sim\mathcal{N}(\mu,\Sigma)$

$\nabla_{i}\leftarrow c_{0}\nabla f+\sum_{j=1}^{k}c_{j}\nabla m_{j}$

$\theta_{i}^{{}^{\prime}}\leftarrow\theta_{\mu}+\nabla_{i}$

$f^{\prime},*,m^{\prime},*\leftarrow\text{rollout}(\theta^{\prime}_{i})$

$\Delta_{i}\leftarrow\text{update}$_$\text{archive}(\theta_{i}^{{}^{\prime}},f^{\prime},\textbf{{m'}})$

end for

rank $\nabla_{i}$ by $\Delta_{i}$

Adapt xNES parameters $\mu=\mu^{\prime},\Sigma=\Sigma^{\prime}$ based on
improvement ranking $\Delta_{i}$

$f^{\prime}(\theta_{\mu})=c_{\mu,0}f+\sum_{j=1}^{k}c_{\mu,j}m_{j}$, where
$\textbf{c}_{\mu}=\mu^{\prime}$

$\theta_{\mu}^{\prime}=\text{VPPO}(\theta_{\mu},f^{\prime},N_{2})$

if there is no change in the archive then

Restart xNES with $\mu=0,\Sigma=\sigma_{g}I$

Set $\theta_{\mu}$ to a randomly selected existing cell $\theta_{i}$ from the
archive

end if

end for

##  4 Experiments

We evaluate our algorithm on four different continuous-control locomotion
tasks derived from the original Mujoco environments [49]: Ant, Walker2d, Half-
Cheetah, and Humanoid. The standard objective in each task is to maximize
forward progress and robot stability while minimizing energy consumption. We
use the Brax simulator to leverage GPU-acceleration and massive
parallelization of the environments. The observation space sizes for these
environments are 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 of an agent in any given
rollout as implemented in QDax [31], 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 with the ground divided by the length of the trajectory.
Our VPPO implementation used in PPGA is based on CleanRL’s implementation of
PPO [25]. Most experiments were run on a SLURM cluster where each job had
access to an NVIDIA RTX 2080Ti GPUs, 4 cores from a Intel(R) Xeon(R) Gold 6154
3.00GHz CPU, and 108GB of RAM. Some additional experiments and ablations were
run on local workstations with access to an NVIDIA RTX 3090, AMD Ryzen 7900x
12 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) and Quality Diversity Policy Gradient
(QDPG) implemented in QDax, and CMA-MAEGA(TD3, ES) implemented in pyribs. We
also compare against the state-of-the-art ES-based QD-RL algorithm, separable
CMA-MAE (sep-CMA-MAE) [47], which allows evolutionary QD techniques to scale
up to larger neural networks. We use a standard grid archive with dimensions
[10, 10, 10, 10] for Ant and [50, 50] for Walker2d, Half-Cheetah, and
Humanoid. The same archive resolutions and network architectures are used for
all baselines. A full list of shared hyperparameters is in Appendix A. We use
an archive learning rate of 0.1, 0.15, 0.1, and 1.0 on Humanoid, Walker2d,
Ant, and Half-Cheetah, respectively. Adaptive standard deviation is enabled
for Ant as agents in this environment otherwise have trouble minimizing
control cost. We reset the action distribution standard deviation to 1.0 on
each iteration in all other environments.

Figure 3: QD metrics and cumulative distributions for archives from PPGA
compared to baselines. The CDF plots indicate the percentage of archive
solutions that fall above a certain objective threshold. All plots are
averaged over four seeds, and the shaded region represents +/- one standard
deviation from the mean.

PPGA consistently finds higher best-performing policies on all tasks. We
completely outperform baselines on the Humanoid task on all metrics except
coverage, achieving a 4x improvement over baselines on best reward. In all
other tasks except ant, PPGA produces a policy distribution where most of the
density lies in high performing regions of the archive as shown by the CDF
plots. While PPGA does not achieve the highest QD scores and Coverage on every
task, we argue that these metrics by themselves can be misleading, because one
can fill all cells in the archive with low performing policies and achieve
high scores for both metrics. The CDF plots encompasses both of these metrics,
and provide insight into how the collection of policies is distributed w.r.t.
performance. In all tasks but Ant, we achieve superior performance on this
metric. PPGA struggles with high control cost penalties on Ant due to it using
four legs to locomote, thus prompting us to enable adaptive standard deviation
for this environment. Enabling adaptive standard deviation can result in worse
performance as training progresses, since the action distribution converges
and PPGA is no longer able to branch policies into new cells in the archive.
This results in the lower coverage and QD-score as seen in Fig. 3. However, we
are still able to find higher best-performing policies than the baselines.

Figure 4: Corrected cumulative distributions, with +/- one standard deviation
represented by the shaded regions.

All baselines generally outperform PPGA in coverage, with the exception of
sep-CMA-MAE and CMA-MAEGA(TD3, ES) on Ant. Excluding QDPG, all baselines use
some form of a genetic variation operator to improve diversity. We believe
that this allows these algorithms to find cells in the archive that cannot be
reached by following the gradients alone. However, it is often the case that
agents produced by parameter space noise can get lucky and land in far-away
cells, but these agents do not replicate, as we show in Sec. 4.2. Finally,
QDPG has an explicit diversity operator, which allows it to be competitive
with PPGA in terms of coverage, but is generally outperformed by PPGA on all
other metrics.

###  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, we
follow the guidelines laid out in [10]. That is, we re-evaluate each agent in
the archive 50 times and average its performance and measures to construct a
Corrected Archive, and use this to produce Corrected QD metrics such as
Corrected QD-Score and Corrected coverage. Table 1 and Fig. 4 show the
corrected QD metrics and the corrected CDFs, respectively. After re-evaluating
the archives, we find that the coverage gap significantly narrows, with PPGA
even outperforming certain baselines such as PGA-ME in archive coverage on
Half Cheetah. PPGA maintains overall higher performance, as indicated by the
corrected CDF plots, and higher QD-Score, as indicated by the table, after re-
evaluation on all tasks with the exception of Ant.

Figure 5: Ablation of walking the search policy with VPPO vs gradient
recombination done in CMA-MEGA/CMA-MAEGA on the Humanoid environment.

###  4.3 Ablations

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 of
using xNES as the outer-loop optimizer compared to 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. 5
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 the $N_{2}$ hyperparameter. Weighted recombination results in a 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 branched 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.

Table 1: Corrected QD metrics

Algorithm | Exp. | QD-Score | Coverage | Best Reward
---|---|---|---|---
PPGA | Humanoid | $\mathbf{4.11\times 10^{6}}$ | 34.49 % | 9725
Walker2d | $2.68\times 10^{6}$ | 35.81 % | 4681
Half Cheetah | $\mathbf{1.51\times 10^{7}}$ | 49.55 % | 8781
Ant | $1.47\times 10^{7}$ | 33.55 % | 7023
PGA-ME | Humanoid | $5.93\times 10^{5}$ | 50.16 % | 714
Walker2d | $2.14\times 10^{6}$ | 37.51 % | 2037
Half Cheetah | $1.06\times 10^{7}$ | 40.66 % | 4867
Ant | $\mathbf{1.81\times 10^{7}}$ |  37.62 % | 4582
sep-CMA-MAE | Humanoid | $7.37\times 10^{5}$ |  62.1 % | 688
Walker2d | $\mathbf{3.88\times 10^{6}}$ |  54.21% | 2489
Half Cheetah | $1.4\times 10^{7}$ |  55.67% | 2808
Ant | $1.15\times 10^{7}$ | 29.83 % | 1618
QDPG | Humanoid | $5.91\times 10^{5}$ | 49.9 % | 715
Walker2d | $2.14\times 10^{6}$ | 37.51 % | 2038
Half Cheetah | $7.26\times 10^{5}$ | 40.66 % | 285
Ant | $3.05\times 10^{6}$ | 25.21 % | 789
CMA-MAEGA(TD3, ES) | Humanoid | $1.94\times 10^{5}$ | 33.57 % | 467
Walker2d | $2.85\times 10^{5}$ | 20.92 % | 1057
Half Cheetah | $1.03\times 10^{7}$ | 42.50 % | 2773
Ant | $2.20\times 10^{6}$ | 10.22 % | 999

##  5 Discussion and Limitations

We present a new method Proximal Policy Gradient Arborescence (PPGA) in which,
for the first time, on-policy RL is applied to the DQD and QD-RL settings. We
show that by leveraging an on policy RL algorithm that benefits from massive
parallelsim in GPU-accelerated simulators, we can achieve significant
performance gains over baselines, most notably on Humanoid, a challenging,
high-dimensional locomotion task. We generalize DQD algorithms that use
covariance matrix adaptation as instantiations of Natural Evolution
Strategies-based DQD methods and we propose using xNES as the outer-loop
optimizer over gradient coefficient space, leading to significantly greater
training stability. One caveat of using this approach is the sample
complexity. Although parallelism allows for faster wall-clock time
convergence, it does so at the expense of the algorithm’s sample efficiency.
In data-constrained settings where not many parallel environments are
available, PPGA’s wall-clock time performance degrades as well. Nonetheless,
we are excited to add this approach to the QD-RL family of algorithms. We are
interested to see how this method scales to even more data-rich regimes such
as distributed settings, as well as its application to harder problems such as
real robotics tasks. We leave these as potential avenues of future research.

## References

  * Akimoto et al. [2010] 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 Kołodziej, and Günter Rudolph, editors, _Parallel Problem Solving from Nature, PPSN XI_ , pages 154–163, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.  ISBN 978-3-642-15844-5.
  * Batra et al. [2021] 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, editors, _Conference on Robot Learning, 8-11 November 2021, London, UK_ , volume 164 of _Proceedings of Machine Learning Research_ , pages 576–586. PMLR, 2021.  URL https://proceedings.mlr.press/v164/batra22a.html.
  * Bhatt et al. [2022] Varun Bhatt, Bryon Tjanaka, Matthew Fontaine, and Stefanos Nikolaidis.  Deep surrogate assisted generation of environments.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 37762–37777. Curran Associates, Inc., 2022.  URL https://proceedings.neurips.cc/paper_files/paper/2022/file/f649556471416b35e60ae0de7c1e3619-Paper-Conference.pdf.
  * Chatzilygeroudis et al. [2021] Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean-Baptiste Mouret.  _Quality-Diversity Optimization: A Novel Branch of Stochastic Optimization_ , pages 109–135.  Springer International Publishing, Cham, 2021.  ISBN 978-3-030-66515-9.  doi: 10.1007/978-3-030-66515-9_4.  URL https://doi.org/10.1007/978-3-030-66515-9_4.
  * Choi and Togelius [2021] Tae Jong Choi and Julian Togelius.  Self-referential quality diversity through differential map-elites.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , GECCO ’21, page 502–509, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450383509.  doi: 10.1145/3449639.3459383.  URL https://doi.org/10.1145/3449639.3459383.
  * Colas et al. [2020] Cédric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune.  Scaling map-elites to deep neuroevolution.  In _Proceedings of the 2020 Genetic and Evolutionary Computation Conference_ , GECCO ’20, page 67–75, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450371285.  doi: 10.1145/3377930.3390217.  URL https://doi.org/10.1145/3377930.3390217.
  * Conti et al. [2018] Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune.  Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 5027–5038. Curran Associates, Inc., 2018.  URL http://papers.nips.cc/paper/7750-improving-exploration-in-evolution-strategies-for-deep-reinforcement-learning-via-a-population-of-novelty-seeking-agents.pdf.
  * Cully et al. [2015] Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret.  Robots that can adapt like animals.  _Nat._ , 521(7553):503–507, 2015.  doi: 10.1038/nature14422.  URL https://doi.org/10.1038/nature14422.
  * Earle et al. [2022] Sam Earle, Justin Snider, Matthew C. Fontaine, Stefanos Nikolaidis, and Julian Togelius.  Illuminating diverse neural cellular automata for level generation.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , GECCO ’22, page 68–76, New York, NY, USA, 2022. Association for Computing Machinery.  ISBN 9781450392372.  doi: 10.1145/3512290.3528754.  URL https://doi.org/10.1145/3512290.3528754.
  * Flageat et al. [2023] 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.1145/3577203.  URL https://doi.org/10.1145/3577203.  Just Accepted.
  * Fontaine et al. [2021a] Matthew Fontaine, Ya-Chuan Hsu, Yulun Zhang, Bryon Tjanaka, and Stefanos Nikolaidis.  On the Importance of Environments in Human-Robot Coordination.  In _Proceedings of Robotics: Science and Systems_ , Virtual, July 2021a.  doi: 10.15607/RSS.2021.XVII.038.
  * Fontaine and Nikolaidis [2021] Matthew C. Fontaine and Stefanos Nikolaidis.  Differentiable quality diversity.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, _Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual_ , pages 10040–10052, 2021.  URL https://proceedings.neurips.cc/paper/2021/hash/532923f11ac97d3e7cb0130315b067dc-Abstract.html.
  * Fontaine and Nikolaidis [2022a] Matthew C. Fontaine and Stefanos Nikolaidis.  Covariance matrix adaptation map-annealing.  _CoRR_ , abs/2205.10752, 2022a.  doi: 10.48550/arXiv.2205.10752.  URL https://doi.org/10.48550/arXiv.2205.10752.
  * Fontaine and Nikolaidis [2022b] Matthew C. Fontaine and Stefanos Nikolaidis.  Evaluating human–robot interaction algorithms in shared autonomy via quality diversity scenario generation.  _J. Hum.-Robot Interact._ , 11(3), sep 2022b.  doi: 10.1145/3476412.  URL https://doi.org/10.1145/3476412.
  * Fontaine et al. [2020] 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, editor, _GECCO ’20: Genetic and Evolutionary Computation Conference, Cancún Mexico, July 8-12, 2020_ , pages 94–102. ACM, 2020.  doi: 10.1145/3377930.3390232.  URL https://doi.org/10.1145/3377930.3390232.
  * Fontaine et al. [2021b] Matthew C. Fontaine, Ruilin Liu, Ahmed Khalifa, Jignesh Modi, Julian Togelius, Amy K. Hoover, and Stefanos Nikolaidis.  Illuminating mario scenes in the latent space of a generative adversarial network.  _AAAI Conference on Artificial Intelligence_ , 35, February 2021b.  URL https://ojs.aaai.org/index.php/AAAI/article/view/16740.
  * Freeman et al. [2021] C. Daniel Freeman, Erik Frey, Anton Raichuk, Sertan Girgin, Igor Mordatch, and Olivier Bachem.  Brax - a differentiable physics engine for large scale rigid body simulation, 2021.  URL http://github.com/google/brax.
  * Fujimoto et al. [2018] Scott Fujimoto, Herke van Hoof, and David Meger.  Addressing function approximation error in actor-critic methods.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _proceedings of machine learning research_ , pages 1587–1596. pmlr, 10–15 jul 2018.  URL http://proceedings.mlr.press/v80/fujimoto18a.html.
  * Gaier et al. [2018] Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret.  Data-Efficient Design Exploration through Surrogate-Assisted Illumination.  _Evolutionary Computation_ , 26(3):381–410, 09 2018.  ISSN 1063-6560.  doi: 10.1162/evco_a_00231.  URL https://doi.org/10.1162/evco_a_00231.
  * Gaier et al. [2020] Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret.  Discovering representations for black-box optimization.  In _Proceedings of the 2020 Genetic and Evolutionary Computation Conference_ , GECCO ’20, page 103–111, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450371285.  doi: 10.1145/3377930.3390221.  URL https://doi.org/10.1145/3377930.3390221.
  * Glasmachers et al. [2010] Tobias Glasmachers, Tom Schaul, Yi Sun, Daan Wierstra, and Jürgen Schmidhuber.  Exponential natural evolution strategies.  In Martin Pelikan and Jürgen Branke, editors, _Genetic and Evolutionary Computation Conference, GECCO 2010, Proceedings, Portland, Oregon, USA, July 7-11, 2010_ , pages 393–400. ACM, 2010.  doi: 10.1145/1830483.1830557.  URL https://doi.org/10.1145/1830483.1830557.
  * Gravina et al. [2019] Daniele Gravina, Ahmed Khalifa, Antonios Liapis, Julian Togelius, and Georgios N Yannakakis.  Procedural content generation through quality diversity.  In _2019 IEEE Conference on Games (CoG)_ , pages 1–8. IEEE, 2019\.
  * Hagg et al. [2020] Alexander Hagg, Dominik Wilde, Alexander Asteroth, and Thomas Bäck.  Designing air flow with surrogate-assisted phenotypic niching.  In _International Conference on Parallel Problem Solving from Nature_ , pages 140–153. Springer, 2020.
  * Handa et al. [2022] Ankur Handa, Arthur Allshire, Viktor Makoviychuk, Aleksei Petrenko, Ritvik Singh, Jingzhou Liu, Denys Makoviichuk, Karl Van Wyk, Alexander Zhurkevich, Balakumar Sundaralingam, Yashraj Narang, Jean-Francois Lafleche, Dieter Fox, and Gavriel State.  Dextreme: Transfer of agile in-hand manipulation from simulation to reality.  _arXiv_ , 2022.
  * Huang et al. [2022] 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 reinforcement learning algorithms.  _Journal of Machine Learning Research_ , 23(274):1–18, 2022.  URL http://jmlr.org/papers/v23/21-1342.html.
  * Kent and Branke [2020] Paul Kent and Juergen Branke.  Bop-elites, a bayesian optimisation algorithm for quality-diversity search, 2020.  URL https://arxiv.org/abs/2005.04320.
  * Khalifa et al. [2018] Ahmed Khalifa, Scott Lee, Andy Nealen, and Julian Togelius.  Talakat: Bullet hell generation through constrained map-elites.  In _Proceedings of The Genetic and Evolutionary Computation Conference_ , pages 1047–1054, 2018.
  * Lehman and Stanley [2011a] Joel Lehman and Kenneth O. Stanley.  Abandoning Objectives: Evolution Through the Search for Novelty Alone.  _Evolutionary Computation_ , 19(2):189–223, 06 2011a.  ISSN 1063-6560.  doi: 10.1162/EVCO_a_00025.  URL https://doi.org/10.1162/EVCO_a_00025.
  * Lehman and Stanley [2011b] 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 on Genetic and Evolutionary Computation_ , GECCO ’11, page 211–218, New York, NY, USA, 2011b. Association for Computing Machinery.  ISBN 9781450305570.  doi: 10.1145/2001576.2001606.  URL https://doi.org/10.1145/2001576.2001606.
  * Lillicrap et al. [2016] 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, editors, _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.  URL http://arxiv.org/abs/1509.02971.
  * Lim et al. [2022] Bryan Lim, Maxime Allard, Luca Grillotti, and Antoine Cully.  Accelerated quality-diversity for robotics through massive parallelism.  _arXiv preprint arXiv:2202.01258_ , 2022.
  * Makoviychuk et al. [2021] 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 Sai-Kit Yeung, editors, _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual_ , 2021.  URL https://datasets-benchmarks-proceedings.neurips.cc/paper/2021/hash/28dd2c7955ce926456240b2ff0100bde-Abstract-round2.html.
  * Mnih et al. [2016] Volodymyr Mnih, Adrià Puigdomènech 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, editors, _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_ , pages 1928–1937. JMLR.org, 2016.  URL http://proceedings.mlr.press/v48/mniha16.html.
  * Morrison et al. [2020] Douglas Morrison, Peter Corke, and Jürgen Leitner.  Egad! an evolved grasping analysis dataset for diversity and reproducibility in robotic manipulation.  _IEEE Robotics and Automation Letters_ , 5(3):4368–4375, 2020.  doi: 10.1109/LRA.2020.2992195.
  * Mouret and Clune [2015] Jean-Baptiste Mouret and Jeff Clune.  Illuminating search spaces by mapping elites.  _CoRR_ , abs/1504.04909, 2015.  URL http://arxiv.org/abs/1504.04909.
  * Müller and Glasmachers [2018] 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, Luís Paquete, and L. Darrell Whitley, editors, _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_ , pages 411–423. Springer, 2018\.  doi: 10.1007/978-3-319-99259-4\\_33.  URL https://doi.org/10.1007/978-3-319-99259-4_33.
  * Nilsson and Cully [2021] Olle Nilsson and Antoine Cully.  Policy gradient assisted map-elites.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , GECCO ’21, page 866–875, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450383509.  doi: 10.1145/3449639.3459304.  URL https://doi.org/10.1145/3449639.3459304.
  * Petrenko et al. [2020] Aleksei Petrenko, Zhehui Huang, Tushar Kumar, Gaurav S. Sukhatme, and Vladlen Koltun.  Sample factory: Egocentric 3d control from pixels at 100000 FPS with asynchronous reinforcement learning.  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 7652–7662. PMLR, 2020\.  URL http://proceedings.mlr.press/v119/petrenko20a.html.
  * Pierrot et al. [2022] Thomas Pierrot, Valentin Macé, Felix Chalumeau, Arthur Flajolet, Geoffrey Cideron, Karim Beguir, 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, page 1075–1083, New York, NY, USA, 2022. Association for Computing Machinery.  ISBN 9781450392372.  doi: 10.1145/3512290.3528845.  URL https://doi.org/10.1145/3512290.3528845.
  * Rudin et al. [2021] 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, editors, _Conference on Robot Learning, 8-11 November 2021, London, UK_ , volume 164 of _Proceedings of Machine Learning Research_ , pages 91–100. PMLR, 2021.  URL https://proceedings.mlr.press/v164/rudin22a.html.
  * Sarkar and Cooper [2021] Anurag Sarkar and Seth Cooper.  Generating and blending game levels via quality-diversity in the latent space of a variational autoencoder.  _arXiv preprint arXiv:2102.12463_ , 2021.
  * Schrum et al. [2020] Jacob Schrum, Vanessa Volz, and Sebastian Risi.  Cppn2gan: Combining compositional pattern producing networks and gans for large-scale pattern generation.  In _Proceedings of the 2020 Genetic and Evolutionary Computation Conference_ , pages 139–147, 2020.
  * Schulman et al. [2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael I. Jordan, and Philipp Moritz.  Trust region policy optimization.  In Francis R. Bach and David M. Blei, editors, _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_ , pages 1889–1897. JMLR.org, 2015.  URL http://proceedings.mlr.press/v37/schulman15.html.
  * Schulman et al. [2016] 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, editors, _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.  URL http://arxiv.org/abs/1506.02438.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  _CoRR_ , abs/1707.06347, 2017.  URL http://arxiv.org/abs/1707.06347.
  * Steckel and Schrum [2021] Kirby Steckel and Jacob Schrum.  Illuminating the space of beatable lode runner levels produced by various generative adversarial networks.  In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ , GECCO ’21, page 111–112, New York, NY, USA, 2021. Association for Computing Machinery.  ISBN 9781450383516.  doi: 10.1145/3449726.3459440.  URL https://doi.org/10.1145/3449726.3459440.
  * Tjanaka et al. [2022a] Bryon Tjanaka, Matthew C. Fontaine, Aniruddha Kalkar, and Stefanos Nikolaidis.  Training diverse high-dimensional controllers by scaling covariance matrix adaptation map-annealing, 2022a.
  * Tjanaka et al. [2022b] 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, page 1102–1111, New York, NY, USA, 2022b. Association for Computing Machinery.  ISBN 9781450392372.  doi: 10.1145/3512290.3528705.  URL https://doi.org/10.1145/3512290.3528705.
  * Todorov et al. [2012] Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In _2012 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 5026–5033. IEEE, 2012.  doi: 10.1109/IROS.2012.6386109.
  * Vassiliades and Mouret [2018] Vassilis Vassiliades and Jean-Baptiste Mouret.  Discovering the elite hypervolume by leveraging interspecies correlation.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , GECCO ’18, page 149–156, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450356183.  doi: 10.1145/3205455.3205602.  URL https://doi.org/10.1145/3205455.3205602.
  * Zhang et al. [2022] Yulun Zhang, Matthew C. Fontaine, Amy K. Hoover, and Stefanos Nikolaidis.  Deep surrogate assisted map-elites for automated hearthstone deckbuilding.  In _Proceedings of the Genetic and Evolutionary Computation Conference_ , GECCO ’22, page 158–167, New York, NY, USA, 2022. Association for Computing Machinery.  ISBN 9781450392372.  doi: 10.1145/3512290.3528718.  URL https://doi.org/10.1145/3512290.3528718.

##  Appendix A Hyperparameters

Table 2: List of relevant hyperparameters for PPGA shared across all
environments.
Hyperparameter | Value
---|---
Actor Network | [128, 128, Action Dim]
Critic Network | [256, 256, 1]
$N_{1}$ | 10
$N_{2}$ | 10
PPO Num Minibatches | 8
PPO Num Epochs | 4
Observation Normalization | True
Reward Normalization | True
Rollout Length | 128

##  Appendix B Vectorized-PPO Details

There are several key modifications to the original PPO implementation that
were necessary to run PPO in an efficient manner within PPGA. Specifically,
when computing the objective-measure Jacobian, $<\nabla
f(\cdot)\in\mathbb{R},\mathbf{\nabla m(\cdot)\in\mathbb{R}^{k}>}$, the RL
objective $f$ and each measure function $m$ are treated as separate single-
objective optimization instances, where PPO optimizes each function one at a
time. However, doing this sequentially would increase the runtime complexity
by a factor of $k+1$. To alleviate this issue, we designed a vectorized
version of PPO, or VPPO. VPPO takes the current state of the agent, replicates
it $k+1$ times, and stores this in a VectorizedActor agent-class, which we
will denote $\mathbf{\vv{\pi}_{\theta}}$. Since PPO is an actor-critic method,
we must also initialize $k+1$ value functions $V_{\phi_{1}}...V_{\phi_{k+1}}$,
one for each sub-actor in the vectorized agent. There is an additional value
function $V_{\phi_{\mu}}$ used when walking the mean solution point
$\pi_{\theta_{\mu}}$ that is independent of the Vectorized Actor. Thus, there
are in total $k+2$ value functions maintained over the lifetime of the
program.

During the Jacobian computation phase, $\mathbf{\vv{\pi}_{\theta}}$ is used to
collect batched-rollouts over all $N$ environments, where statistics such as
advantage and return are computed only within $k+1$ subgroups corresponding to
the $k+1$ subpolicies in the vectorized agent. VPPO then performs batch
gradient descent to produce $\nabla f(\cdot),\nabla m_{1}(\cdot),...,\nabla
m_{k+1}(\cdot)$, which are implicitly backpropagated to each subpolicy in
$\mathbf{\vv{\pi}_{\theta}}$ in a vectorized manner. This process is repeated
for $N_{1}$ VPPO iterations, producing an updated vectorized actor
$\mathbf{\vv{\pi}_{\theta}}^{\prime}$. Then, the matrix
$\mathbf{\vv{\pi}_{\theta}}^{\prime}-\mathbf{\vv{\pi}_{\theta}}$ i.e.

$\displaystyle\begin{bmatrix}\pi_{\theta_{1}}^{\prime}-\pi_{\theta_{1}}\\\
\pi_{\theta_{2}}^{\prime}-\pi_{\theta_{2}}\\\ ...\\\
\pi_{\theta_{k+1}}^{\prime}-\pi_{\theta_{k+1}}\end{bmatrix}$

is the objective-measure Jacobian. The individual gradient vectors are
normalized to be unit length before being used to branch new solutions off of
the search policy.

When providing only a single objective to optimize such as when walking the
mean solution point, VPPO simplifies and performs exactly as vanilla PPO.

Algorithm 2 Vectorized-PPO (VPPO)

Input: Initial solution point $\pi_{\theta_{i}}$, objective functions to
optimize $\mathbf{f}=f_{1}(\cdot),...,f_{k}(\cdot)$, number of VPPO iterations
$N$, number of parallel environments $E$, rollout length $L$

Initialize the vectorized agent $\mathbf{\vv{\pi}_{\theta_{i}}}$ =
vectorized_agent($[\pi_{\theta}]\times(k+1)$)

for iter $\leftarrow$ 1 to $N_{1}$ do

$\textbf{(S, A, R, S')}\leftarrow$ rollout(vectorized_agent, $E$, $L$,
$\mathbf{f}$) // Note that S = $\\{S_{1},...,S_{k}\\}$, etc

advantage $\mathbb{A}$, returns $\mathcal{G}$ $\leftarrow$
batch_calculate_rewards(S, A, R, S’, $\mathbf{f}$)

$\mathbf{\vv{\pi}_{\theta}}^{\prime}$ $\leftarrow$
batch_gradient_descent($\mathbb{A},\mathcal{G},\mathbf{\vv{\pi}_{\theta}}$) //
using the stochastic policy gradient

$\mathbf{\vv{\pi}_{\theta}}\leftarrow\mathbf{\vv{\pi}_{\theta}}^{\prime}$

end for

$\mathbf{\nabla f}\leftarrow$
$\mathbf{\vv{\pi}_{\theta}}^{\prime}-\mathbf{\vv{\pi}_{\theta_{i}}}$

return $\mathbf{\nabla f}$

##  Appendix C TD3GA Implementation Details

As part of our ablation study, we implemented TD3GA, which differs from PPGA
by replacing all PPO mechanisms with TD3 Fujimoto et al. [2018]. This
implementation required several algorithmic decisions, as PPGA was originally
designed to integrate with an on-policy method like PPO rather than an off-
policy method like TD3, In this section, we describe these decisions. In
general, we intend our decisions to make TD3GA operate as closely as possible
to PPGA, and we leave it to future work to explore whether variations of these
decisions will further improve performance.

Background: TD3 is an off-policy actor-critic method designed for single-
objective RL tasks. TD3 maintains an actor (i.e., a policy) that takes actions
in the environment, and a critic that estimates the action-value function. TD3
also maintains a replay buffer that stores experience collected by the actor.
Over time, the actor is trained to optimize the critic. Simultaneously, based
on experience in the replay buffer, the critic learns to better predict the
action-value function.

Design Decisions:

  1. 1.

Number of critics: In TD3GA, we maintain a TD3 critic for the objective
function and one for each of the measure functions. We also create a separate
critic for the weighted objective that is used when walking the solution
point. We refer to these critics as the objective critic, measure critics, and
walking critic.

  2. 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
and Cully [2021] and CMA-MEGA (TD3, ES) Tjanaka et al. [2022b], fulfill this
role with a dedicated actor. This actor is referred to as a greedy actor since
its primary purpose is to optimize its performance with respect to the critic.

In theory, since TD3 is an off-policy method, any actor, including a greedy
actor, can be used to train the critic. However, to make TD3GA closer to PPGA,
we instead use a copy of the current search policy to train the critic. This
decision provides our TD3 instances with an on-policy nature that mirrors the
PPO mechanisms found in PPGA.

  3. 3.

When to train critics: Similar to the PPO value functions in PPGA, we maintain
all critics throughout the entire training run, updating them on every
iteration.

  4. 4.

Experience collection: This decision concerns which experience collected in
the environment should be inserted into the replay buffer. With the settings
in our paper, PPGA (and TD3GA) samples 300 solutions per iteration, and each
solution is evaluated for 10 episodes, with each episode having up to 1,000
timesteps of experience; in total, these solutions generate 3 million
timesteps per iteration. The typical replay buffer size Fujimoto et al. [2018]
in TD3 is 1 million, meaning the buffer would be filled three times over if we
inserted all of this experience, i.e., the critic would never be trained with
the experience from two-thirds of all solutions.

To ensure that we collect experience from many solutions across many
iterations, we make two 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 to 5 million to store experience across more iterations.

Note that there is no analogue 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 solution point.

  5. 5.

Gradient computation: We begin by describing how a prior method estimates the
objective gradient with TD3. To estimate the objective gradient of a solution
point, CMA-MEGA (TD3, ES) samples a 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.

Roughly, the above procedure corresponds to taking a 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 $N_{1}$ and $N_{2}$. 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 is 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 a copy of the search policy. While training the critic,
the actor is updated so that it maximizes the objective critic. After $N_{1}$
steps, we compute the objective gradient as the difference between the actor
and the original search policy.

  6. 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 to apply this
mechanism to the critic parameters.

However, since the actor is reset to the current search policy on every
iteration, it is difficult to maintain a single target network. Thus, on every
iteration, the target network for the actor is simply reset to the current
search policy’s parameters before the gradient computation.

Pseudocode: Algorithm 3 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 is also similar, except that the reward is a
weighted combination of the objective and measures (the weights come from the
mean $\mu$ of the emitter’s coefficient distribution). Furthermore, when
walking the search policy, we return the final actor instead of a gradient.

Algorithm 3 TD3 Gradient Computation for the Objective. Adapted from TD3
Fujimoto et al. [2018]

Input: Current search policy params $\theta_{\mu}$, current TD3 critic
networks $Q_{\psi_{1}}$ and $Q_{\psi_{2}}$ parameterized by $\psi_{1}$ and
$\psi_{2}$ respectively, current critic targets $\psi^{\prime}_{1}$ and
$\psi^{\prime}_{2}$, replay buffer $B$

Hyperparameters: Training steps $N_{1}$ or $N_{2}$, target network update rate
$\tau$, target network update frequency $d$, smoothing noise standard
deviation $\sigma_{p}$, smoothing noise clip $c$, discount factor $\gamma$,
batch size $n_{batch}$

Initialize actor $\phi=\theta_{\mu}$, actor target
$\phi^{\prime}=\theta_{\mu}$

{Either $N_{1}$ for gradient computation or $N_{2}$ for walking the search
policy}

for iter $\leftarrow$ 1 to $N_{1}$ do

{$r$ is replaced with the measures for measure gradients, or a weighted
combination of the reward and measures for walking the search policy}

Sample mini-batch of $n_{batch}$ transitions $(s,a,r,s^{\prime})$ from $B$

{Train the critics}

$\tilde{a}\leftarrow\pi_{\phi^{\prime}}(s^{\prime})+\epsilon$,
$\epsilon\sim\text{clip}(\mathcal{N}(0,\sigma_{p}),-c,c)$

$y\leftarrow r+\gamma\min_{i=1,2}Q_{\psi^{\prime}_{i}}(s^{\prime},\tilde{a})$

{This update is performed with Adam}

Update critics
$\psi_{i}\leftarrow\operatorname*{argmin}_{\psi_{i}}\frac{1}{N}\sum(y-Q_{\psi_{i}}(s,a))^{2}$

if $t\mod d$ then

{Update $\phi$ by the deterministic policy gradient with Adam}

$\nabla_{\phi}J(\phi)=\frac{1}{n_{batch}}\sum\nabla_{a}Q_{\psi_{1}}(s,a)|_{a=\pi_{\phi}(s)}\nabla_{\phi}\pi_{\phi}(s)$

{Update target networks:}

$\psi^{\prime}_{i}\leftarrow\tau\psi_{i}+(1-\tau)\psi^{\prime}_{i}$

$\phi^{\prime}\leftarrow\tau\phi+(1-\tau)\phi^{\prime}$

end if

end for

{Note that $\psi_{1}$, $\psi_{2}$, $\psi^{\prime}_{1}$, and
$\psi^{\prime}_{2}$ are maintained across calls to this function}

{When walking the search policy, we just return the new policy params $\phi$}

$\nabla f\leftarrow\phi-\theta_{\mu}$

return $\nabla f$

Hyperparameters: TD3GA inherits all relevant hyperparameters from PPGA (Table
2). It also inherits TD3 hyperparameters from prior QD-RL works that
incorporate TD3 Tjanaka et al. [2022b], Nilsson and Cully [2021], except for
having a 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 3 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 3: 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_{1}$) | 10
Training Steps for Walking ($N_{2}$) | 10
Optimizer | Adam
Adam Learning Rate | $3\times 10^{-4}$
Target Network Update Rate ($\tau$) | 0.005
Target Network Update Frequency ($d$) | 2
Smoothing Noise Standard Deviation ($\sigma_{p}$) | 0.2
Smoothing Noise Clip ($c$) | 0.5
Discount Factor ($\gamma$) | 0.99
Replay Buffer Size | 5,000,000
Batch Size ($n_{batch}$) | 48,000
Figure 6: PPGA vs TD3GA on Humanoid. All plots are averaged over 4 seeds. The
shaded region represents one standard deviation away from the mean.

##  Appendix D Hyperparameter Study

We investigate the effects of changing the $N_{1}$ and $N_{2}$ hyperparameters
on the performance of PPGA in the Humanoid domain. We run 4 seeds of PPGA on
the following combinations of $N_{1}$ and $N_{2}$: (10, 5), (5, 10), (5, 5),
(1, 1) and compare against the baseline (10, 10). With these experiments, we
wish to address the following questions

  1. 1.

how few PPO steps on both the objective-measure jacobian calculation and
walking the current search policy can we take before noticing performance
degradation?

  2. 2.

how do asymmetric choices for $N_{1}$ and $N_{2}$ (i.e. more jacobian
calculation steps than walking steps and vice versa) affect performance?

Figure 7: Study of the effect of different hyperparameter choices for $N_{1}$
and $N_{2}$. $N_{1}$ is the number of PPO steps used to calculate the
objective-measure jacobian, and $N_{2}$ is the number of PPO steps used to
walk the search policy. All plots are averaged over 4 seeds. The shaded region
indicates one standard deviation away from the mean.

(10, 5) achieves the most consistent results while achieving the same
performance as the baseline, while (5, 10) results in very high run-to-run
variance. This suggests that spending more compute on approximating the
objective-measure jacobian is more important than walking the current search
policy. (5, 5) achieves approximately 75% of the performance with half the
computational expenditure when compared against the baseline. Thus, in a more
computationally constrained setting, PPGA could be tuned to perform fewer
$N_{1}$ and $N_{2}$ steps while still maintaining good performance. Finally,
(1, 1) performs the worst, achieving only 25% of the baseline’s performance,
implying that there is significant performance degradation when too few
jacobian-calculation and walking steps are taken.