Proximal Policy Gradient Arborescence for Quality Diversity Reinforcement Learning

We appreciate the incredibly in-depth feedback. Points on writing brought up by the reviewer that require no discussion (including the reviewer's main concern on making the TD3GA comparison central) have been directly implemented in the paper, and we have updated the pdf accordingly. For points that require discussion, we respond to them individually:

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.

PPGA inserts policies into the archive based on their average performance and behavior over 10 parallel environments. We find empirical evidence that this indeed improves robustness to uncertainty. We have added this point to the end of section 3.2. Section 4.2 also investigates PPGA's robustness to uncertainty.

"propose several changes" -> changes wrt what?

We wish to convey other changes, such as replacing CMA-ES with xNES, etc., that are subtle improvements over existing work that have large implications for our method (ex. CMA-ES destabilizing training). To improve clarity, we changed this to read "propose additional improvements over prior work".

At this point, the standard ML reader does not know what a measure function is...

I don't agree that having non-differentiable measure functions prevents direct RL optimization...

Per the reviewer's suggestions, we have changed this to read "For example, all QD-RL algorithms for locomotion to date use non-markovian measures of behavioral diversity, which in many cases prevents direct RL-optimization."

the third time you mention exploiting this synergy in the same paragraph...

We changed this to read "It is through this high level view that we see the emergent synergy between PPO and DQD, in that PPO can be used to collect gradient estimates from online data when one or both of the objective and measure functions are markovian and non-differentiable." We have also removed redundant uses of the word "synergy" from the manuscript.

What a "non-stationary QDRL task"

We have expanded on this definition at the beginning of section 3.2.

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

We wish to make both points i.e. the on-policy classification is synergistic with DQD, and that the approximate trust region is a nice property to have when the reward function is non-stationary.

Mentioning actor-critic in the on-policy part the way you do brings confusion...

We have updated the DeepRL background section according to the reviewer's suggestions.

why not call the search point "the current policy"? The same for "solutions", they are policies.

We have removed the term "solution" and replaced it with "policy" throughout the manuscript to avoid unnecessary confusion.

"some minimum threshold". Why call this a minimum threshold? Threshold for what? I rather see it as an exploration bonus...

In some cases, if the threshold value is set too low, the algorithm can initially fill the archive with very poor performing policies from which gradient arborescence cannot recover the true optimal policies. Intuitively, this can be thought of as seeding the archive with policies too far from the manifold and then attempting to perform search nowhere near the manifold. This min-threshold value prevents too poorly performing policies from entering the archive in the first place.

"in the direction of the archive that is least" -> doesn't this also take performance into account?

You are correct, although the ranking implicitly favors policies that land in new cells over those that improve on known ones. We have rephrased this to say "in the direction of greatest archive improvement"

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.

We have done a pass through the introduction and related works sections of the paper and re-balanced the citations.

In 3.2, I'm afraid the claim that trust region methods provide formal guarantees on the quality of the gradient estimates is wrong.

While we agree that papers often make unrealistic assumptions to formalize proofs, this theory-practice gap is ubiquitous in nature, and present in other areas of AI and robotics research such as in robot safety, multi-agent planning and collision avoidance, etc. Rather than saying the proof of TRPO formally holds in the QD-RL setting, we wish to convey the idea that constrained optimization of the policy, especially in settings with non-stationary objective functions, is a nice property to have rather than not. We have softened the language in the manuscript to better convey this. "Being an approximate trust region method, the constrained policy update step provides some robustness to noisy and non-stationary objectives."

Thank you for your feedback. We will respond to each concern individually:

Can you provide more insight into why PPO was specifically chosen over other RL algorithms for this work?

Regarding other QD-RL methods, we selected recent methods that have demonstrated high performance and have accessible open-source implementations. In particular, we chose PGA-ME, the current state-of-the-art, as well as QD-PG, separable CMA-MAE, and CMA-MAEGA (TD3, ES), all of which have shown competitive performance in prior work. Appendix H also includes a comparison to PBT-ME (SAC), which we only ran on Humanoid due to computational expense. We believe these baselines are representative of the current state of the QD-RL field.

Regarding PPO, we believe PPO is an ideal choice for integration into QD-RL algorithms for several reasons. First, PPO can leverage the high parallelization of GPU-accelerated simulators such as Brax to significantly accelerate learning. Current QD-RL methods rely on off-policy RL algorithms such as TD3 and SAC, which are designed to be sample-efficient and benefit from faster sequential execution. In other words, these off-policy methods operate with minimal amounts of data. We are interested in the other end of this spectrum -- that is, when large amounts of data are available, what kind of methods benefit the most? There is a large body of evidence that shows PPO continues to be competitive in these regimes even on contemporary robot learning problems [1, 2, 3]. This was a significant factor when choosing which RL algorithm to investigate.

Finally, regarding our choice of PPO over other on-policy methods such as IMPALA, PPO's use of an approximate trust region to constrain the policy update empirically provides robustness to noisy and even non-stationary objectives. This is especially important in the QD-RL setting, where the branching phase and walking the search policy require optimizing non-stationary objectives.

[1] Rudin, Nikita, et al. "Learning to walk in minutes using massively parallel deep reinforcement learning." Conference on Robot Learning. PMLR, 2022.

[2] Handa, Ankur, et al. "DeXtreme: Transfer of Agile In-hand Manipulation from Simulation to Reality." arXiv preprint arXiv:2210.13702 (2022).

[3] Batra, Sumeet, et al. "Decentralized control of quadrotor swarms with end-to-end deep reinforcement learning." Conference on Robot Learning. PMLR, 2022.

How does the proposed PPGA algorithm perform in other domains and tasks beyond locomotion?

For this paper, we focused on comparing the algorithmic design choices of PPGA and the resulting performance differences against prior SOTA QD-RL algorithms. As such, we ran PPGA on benchmarks that were introduced in [1] and have become standard in the field for a majority of QD-RL methods. However, we are interested in applying PPGA to non-standard QD tasks with discrete action spaces such as Atari. Given the prior success of PPO in a wide variety of tasks with discrete and continuous actions spaces, we believe PPGA has a good chance of succeeding in these tasks.

[1] Olle Nilsson and Antoine Cully. 2021. Policy gradient assisted MAP-Elites. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '21). Association for Computing Machinery, New York, NY, USA, 866–875. https://doi.org/10.1145/3449639.3459304

Can you discuss the scalability of the proposed algorithm, especially in comparison to existing methods?

We found empirical evidence of scalability of our method from two perspectives: scaling to larger archives and learning from more data. We present results in scaling to larger 50x50 archives and compare to baselines in Appendix G. PPGA scales well and maintains state of the art performance over baselines when archives of thousands of policies are concerned. We believe this is a direct result of the fact that, like prior DQD-based algorithms, PPGA explicitly estimates the gradient of greatest archive improvement via gradient arborescence. That is, the information on what new cells were discovered during the branching phase is utilized by xNES to compute the natural gradient w.r.t. archive improvement. Critically, the higher resolution the archive i.e. the more cells there are, the better this gradient estimate is, and so PPGA may in fact favor larger archives.

Finally, we demonstrate PPGA's ability to continually learn with more data by running an additional experiment where PPGA and the current state of the art baseline PGA-ME were run for 1.2 million evaluations, or twice as long as the experiments in the main paper, on larger 50x50 archives. The results have been added to Appendix G. We notice that the average performance of the archive, i.e., the average performance across all policies in the archive, continues to increase, suggesting that PPGA continuously optimizes for performance after the initial discovery phase. We observe this effect to a much lesser extent with PGA-ME.

Thank you for your feedback and questions. We will respond to each point individually:

I would suggest the authors make the explanation of the policy sampling more clear since that is what confused me the most.

Our sampling method builds upon that of CMA-MAEGA described in Sec. 2.3. In summary, CMA-MAEGA branches off new policies from the current one by sampling gradient coefficients, linearly combining them with the objective-measure gradients in various ways, and applying these gradients to the current policy. A single gradient arborescence starts at the current policy $\pi_{\theta_\mu}$ and adds a linear combination of objective and measure gradients to parameters $\theta_\mu$. Formally, this linear combination is $c_0 \nabla f + \sum_{j=1}^k c_j \nabla m_j$, where $**c** = c_{0..k}$ are the sampled gradient coefficients. In CMA-MAEGA, multiple vectors of coefficients are sampled simultaneously, resulting in multiple branches. The gradient coefficients are sampled from a gaussian search distribution with mean $\mu$ and covariance $\Sigma$; $\mu$ and $\Sigma$ are updated by CMA-ES in the case of CMA-MAEGA, and xNES in the case of PPGA. Intuitively, sampling many coefficients produces multiple branched policies, increasing the likelihood of discovering new and higher performing behaviors. $\mu, \Sigma$ biases the branching in the direction that is most likely to lead to exploring new parts of the archive. We have updated the language in section 2.3 to use terms more familiar to the standard machine learning audience and hope that this brings additional clarity to the sampling procedure.

The 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)

That is correct. By measure gradient, we specifically mean $\frac{\partial m_i}{\partial \theta}$ i.e. the gradient of the i'th measure w.r.t. policy params, since there can be multiple measure functions. We have added this clarification to the beginning of section 2.3.

I suggest moving pseudocode Algorithm 1 to the main text.

We agree that moving Algorithm 1 to the main text would improve clarity; however, our main obstacle is fitting it within the page limit. For the final version, we will attempt to trim content and insert Algorithm 1, but it may not be possible (the final version also has 9 pages, identical to the submission version).

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?

We would like to clarify that CMA-ES is only employed by our predecessor method CMA-MAEGA, and is replaced by xNES in PPGA, a functionally equivalent method with more theoretically grounded components discussed in Section 3.3. CMA-ES is a natural evolution strategy that has traditionally been used as a black-box optimizer of solution parameters for non-differentiable objective functions. In DQD papers such as CMA-MAEGA, it instead is employed to maintain and update a search distribution in objective-measure gradient coefficient space such that the solutions created during the branching phase have the highest likelihood of achieving novel and high performing behaviors. In PPGA, CMA-ES was replaced with another natural evolution strategy, xNES, due to the training instabilities induced by CMA-ES on high dimensional RL domains. We refer the reader to [1] for a detailed review on the challenges of employing CMA-ES on RL tasks, and to the answer above on the specific details of branching in measure space.

[1] Müller, Nils, and Tobias Glasmachers. "Challenges in high-dimensional reinforcement learning with evolution strategies." Parallel Problem Solving from Nature–PPSN XV: 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part II 15. Springer International Publishing, 2018.

looks like Section 3.3 contains unnecessary formalism which is not used elsewhere in the paper. why is it provided?

We will assume the reviewer is referring to the description of natural evolution strategies in the second paragraph of Sec. 3.3. We initially added this formalism to help describe how natural evolution strategies operate, but we agree that it is not necessary for providing insight. We have removed the unncessary formalism and simplified this section into a single paragraph.

Thank you for your comments. We will respond to each of the reviewer's concerns individually:

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.

PPO and IMPALA both indeed have similar derivations in that they use importance sampling (IS) when computing the policy update objective: $r_t(\theta) = \left[ \frac{\pi_{\theta}(a|s)}{\pi_{\theta_{old}}(a|s)} \hat{A}_t \right]$,

where $\pi_{\theta_{old}}$ is some behavior policy $\pi_w$ in the case of IMPALA. Critically, the constrained update of $r_t(\theta)$ between $1 - \epsilon$ and $1 + \epsilon$ in PPO that IMPALA omits matters in two locations of the PPGA algorithm: (1) when we are estimating the objective-measure Jacobian during the branching phase, and (2) when we are walking the current search policy according to the multi-objective reward function. This is mainly due to the fact that the objectives are non-stationary in both cases. Consider, for example, two subsequent QD iterations $i-1, i$. On iteration $i$, during the later phase of walking the current policy, we optimize $\pi_{\theta}^{i-1}(a|s), V^{i-1}_{\phi}$

according to the multi-objective reward function $r^i_{multi} = <c^i_{\mu_0}, ..., c^i_{\mu_k}> \cdot <f, \delta_0, ..., \delta_k>$ for $N_2$ steps, giving us $\pi_{\theta}^{i}(a|s), V^{i}_{\phi}$.

In the canonical RL training paradigm, we optimize towards a single objective $r_{static}$ such that the MDP is ergodic and the state visitation distribution $p(s)$ is stationary. In this setting, a case can be made for unconstrained optimization of the (IS) objective. However, consider the adversarial case in PPGA when the multi-objective reward coefficients between subsequent iterations are orthogonal $<c_{\mu_1}, ..., c_{\mu_k}>^{i-1} \cdot <c_{\mu_1}, ..., c_{\mu_k}>^{i} = 0$, for example when the least explored direction is to the left on iteration $i-1$ and then up on iteration $i$ in a 2D archive. Then, $p(s)$ becomes highly non-stationary, and unconstrained updates to $\pi_{\theta}$ can lead to visiting very new states $s'$ in which $V_{\phi}$ makes poor predictions, resulting in oscillations and destabilizing training. Trust region methods such as PPO prevent us from making too large updates on the policy too quickly, allowing $V_{\phi}$ to ingest new states slowly and provide stable advantage estimates for the policy update step.

As reviewer vTCA pointed out, many formal guarantees made by the TRPO paper make assumptions that are often violated in practice, and this is certainly the case in the QD-RL setting. As such, we have softened the language to instead read "Being an approximate trust region method, the constrained policy update step provides some robustness to noisy and non-stationary objectives". We still maintain the belief that constrained optimization is a property worth having in this setting rather than not.

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?

In the xNES vs CMA-ES ablation, we made two attempts using two separate, highly-tuned and optimized reference implementations of CMA-ES inside PPGA provided by [1] and [2]. We noticed the training divergence in both instances across multiple seeds.

Regarding the TD3GA ablation, we use a reference TD3 implementation used by other off-policy QD-RL papers such as PGA-ME for QD-RL tasks. Admittedly, certain hyperparameters such as the optimal size and update schedule of the replay buffer in high-throughput regimes remains an open question that could be further optimized. However, given that using TD3 as a drop-in replacement for PPO in PPGA leads to a fundamentally different learning paradigm, we argue that this algorithm and an involved hyperparameter search warrants its own proper investigation as a separate line of work.

[1] Tjanaka, Bryon, et al. "pyribs: A bare-bones Python library for quality diversity optimization." arXiv preprint arXiv:2303.00191 (2023).

[2] Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. CMA-ES/pycma on Github. Zenodo, DOI:10.5281/zenodo.2559634, February 2019.