Proximal Distilled Evolutionary Reinforcement Learning

Reinforcement Learning (RL) has recently achieved tremendous success due to the partnership with Deep Neural Networks (DNNs). Genetic Algorithms (GAs), often seen as a competing approach to RL, have run out of favour due to their inability to scale up to the DNNs required to solve the most complex environments. Contrary to this dichotomic view, in the physical world, evolution and learning are complementary processes that continuously interact. The recently proposed Evolutionary Reinforcement Learning (ERL) framework has demonstrated the capacity of the two methods to enhance each other. However, ERL has not fully addressed the scalability problem of GAs. In this paper, we argue that this problem is rooted in an unfortunate combination of a simple genetic encoding for DNNs and the use of traditional biologically-inspired variation operators. When applied to these encodings, the standard operators are destructive and cause catastrophic forgetting of the traits the networks acquired. We propose a novel algorithm called Proximal Distilled Evolutionary Reinforcement Learning (PDERL) that is characterised by a hierarchical integration between evolution and learning. The main innovation of PDERL is the use of learning-based variation operators that compensate for the simplicity of the genetic representation. Unlike the traditional operators, the ones we propose meet their functional requirements. We evaluate PDERL in five robot locomotion environments from the OpenAI gym. Our method outperforms ERL, as well as two state of the art RL algorithms, PPO and TD3, in all the environments.


Introduction
The field of Reinforcement Learning (RL) has recently achieved great success by producing artificial agents that can master the game of Go (Silver et al. 2017), play Atari games (Mnih et al. 2015) or control robots to perform complex tasks such as grasping objects (Andrychowicz et al. 2017) or running (Lillicrap et al. 2015). Most of this success is caused by the partnership with Deep Learning (Goodfellow, Bengio, and Courville 2016), generically called Deep Reinforcement Learning (DRL).
At the same time, Genetic Algorithms (GAs), usually seen as a competing approach to RL, have run out of favour due Copyright c 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
to their inability to scale up for evolving Deep Neural Networks (DNNs). As the recent progress in RL has shown, DNNs are required to solve complex environments. However, GAs are particularly suitable for optimisation problems where the dimensionality of the search space is small because of their substantial computational requirements. Therefore, they are unable to cope with the explosion in the number of parameters that DNNs brought.
Contrary to this dichotomic view of RL and GAs, in the physical world, evolution and learning are complementary processes that continuously interact. Perhaps, the most famous result of this interaction is the Baldwin effect (Simp- son 1953), which explains how the genotype can assimilate learnt behaviours over the course of many generations. A more spectacular by-product of this interplay, which has received more attention in recent years, is the epigenetic inheritance of learnt traits (Dias and Ressler 2013).
Despite these exciting intricacies of learning and evolution, the two have almost always received separate treatment in the field of AI. Even though they have been analysed in computational simulations multiple times (Belew and Mitchell 1996), (Ackley and Littman 1992), (Suzuki and Arita 2004), they have rarely been combined to produce novel algorithms with direct applicability. This is surprising given that nature has always been a great source of inspiration for AI (Floreano and Mattiussi 2008).
For the first time, Khadka and Tumer (2018) have recently demonstrated on robot locomotion tasks the practical benefits of merging the two approaches in their Evolutionary Reinforcement Learning (ERL) framework. ERL uses a reinforcement learning-based agent alongside a genetically evolved population, with a transfer of information between the two. However, ERL has not fully addressed the scalability problem of GAs. While the gradient information from the RL agent can significantly speed up the evolutionary search, the population of ERL is evolved using the same variation operators that have been used by previous methods. Paired with directly encoded DNNs, which is the most common genetic representation in use, these operators are destructive.
This paper brings the following contributions: • Demonstrates the negative side-effects in RL of the traditional genetic operators when applied to directly encoded arXiv:1906.09807v1 [cs.
• Proposes two novel genetic operators that are based on backpropagation. These operators do not cause catastrophic forgetting in combination with simple DNN representations.
• Integrates these operators as part of a novel framework called Proximal Distilled Evolutionary Reinforcement Learning (PDERL) that uses a hierarchy of interactions between evolution and learning.

Background
This section introduces the Evolutionary Reinforcement Learning (ERL) algorithm and the genetic operators it uses.

Evolutionary Reinforcement Learning
The proposed methods build upon the ERL framework proposed by Khadka and Tumer (2018). In this framework, a population of policies is evolved using GAs. The fitness of the policies in the population is based on the cumulative total reward obtained over a given number of evaluation rounds. Alongside the population, an actor-critic agent based on DDPG (Lillicrap et al. 2015) is trained via RL. The RL agent and the population synchronise periodically to establish a bidirectional transfer of information.
The first type of synchronisation in ERL, from the RL agent to the genetic population, is meant to speed up the evolutionary search process by inserting the policy gradient information into the population to guide the genetic search. This information is inserted by cloning the actor of the RL agent into the population every few generations. The synchronisation period, ω, is a hyperparameter that controls the amount of information flowing from the RL agent to the population.
The second type of synchronisation consists of a reverse information flow coming from the population to the RL agent. The actors in the population can be seen as experience collectors from which the RL agent can learn offpolicy. All the transitions coming from rollouts in the population are added to the replay buffer of the DDPG agent. The population experiences can be seen as being generated by evolution-guided parameter space noise (Plappert et al. 2018).

Genetic encoding and variation operators
The policies in the ERL population are represented by neural networks with a direct encoding. In this genetic representation, all the weights of a network are stored in a list of real numbers in an arbitrary order. The traditional variation operators are based on simple stochastic modifications of this list. As the number of parameters increases, it is becoming increasingly unlikely that these random weight changes produce better policies.
In the physical world, mutations and crossovers rarely have catastrophic phenotype effects because the phenotype is protected by the complex biological and chemical processes that translate the DNA. In a direct genetic encoding, this protective layer is lacking because of the trivial representation that is used. The biologically inspired variation operators commonly used in the literature, including ERL, do not have the desired functionality when paired with a direct encoding. Ideally, crossovers should combine the best behaviours of the two parents, while mutations should produce a slight variation in the behaviour of the parent.
However, because DNNs are sensitive to random modifications of the weights (genes), these operators typically cause catastrophic forgetting of the acquired behaviours and do not meet their functional requirements. ERL evolves the population using two variation operators commonly used for representations consisting of a list of real numbers: n-point crossovers and Gaussian mutations (Eiben and Smith 2015). Both of these operators can have devastating effects on the behaviour of a directly encoded neural network.
n-point crossovers produce an offspring policy by randomly exchanging segments of the lists of weights of the two parents, where n endpoints determine the segments. ERL uses a custom version of this operator where the segments are the rows of the dense layer matrices. The resulting child policy contains a mix of rows coming from the matrices of the parents. These two types of weights can destructively interfere with each other, and the behaviour of the child policy can diverge from that of the parents.
Similarly, the damaging effects of adding Gaussian noise to the parameters of a DNN have been discussed at great length by Lehman et al. (2018). To limit them, a common approach, which is also employed by ERL, is to mutate only a fraction of the weights. Nonetheless, even with this trick, these mutations are still destructive. Furthermore, evolving just a small part of the weights can slow down the evolutionary search for better policies.

Method
This section introduces our proposed learning-based genetic operators and describes how they are integrated with ERL.

The genetic memory
A significant problem of the population from ERL is that it does not exploit all the individual experiences of the members of the population directly. The only way the population benefits from them is indirect, through the RL agent, which uses them to learn and improve. The individual experiences of the agents are an essential aspect of the new operators, and, therefore, the agents also need a place to store them.
The first modification we perform to ERL is to equip the members of the population and the RL agent with a small personal replay buffer containing their most recent experiences and, depending on the size of the buffer, experiences of their ancestors. Because these experiences span over multiple generations, we refer to this personal replay buffer of each agent as the genetic memory. When the policies are evaluated, they not only store their experiences in DDPG's replay buffer, but also their genetic memory.
As a usual replay buffer, the buffer evicts the oldest experiences when it becomes full. At the same time, the buffer is entirely inherited during mutations and partially during crossovers. Therefore, the size of this buffer determines how much the memories span in the genetic tree. A smaller buffer would usually contain only the memories of the current agent, whereas a larger buffer would also contain ancestral experiences.

Q-Filtered distillation crossovers
In this section, we proposed a knowledge distillation-based crossover to selectively merge the behaviour of two parent policies into a child policy. The proposed algorithm radically differs from the previous approaches that perform the crossovers in the parameter space.  Figure 1: Q-filtered distillation crossover compared to npoint crossover. The contour plots represent the state visitation distributions of the agents. The Q-filtered distillation crossover selectively merges the behaviours of the two parents, whereas the modes of the state visitation distribution obtained by the traditional crossover are disjoint from the modes of the parent distributions.
For a pair of parent agents from the population, the crossover operation works as follows. A new agent with an initially empty associated genetic memory is created. The genetic memory is filled in equal proportions with the latest transitions coming from the genetic memories of the two parents. The weights of the child DNN are initialised with the weights of one of the parents. The child agent is then trained via a form of Imitation Learning (Attia and Dayan 2018) to selectively imitate the actions the parents would take in the states from the newly created genetic memory.
Equivalently, this process can also be seen as a more general type of policy distillation (Rusu et al. 2016) process since it aims to "distil" the knowledge of the parents into the child policy. Unlike the conventional policy distillation proposed by Rusu et al. (2016), two parent networks are involved, not one. This introduces the problem of divergent behaviours. The two parent policies can take radically different actions in identical or similar states. The main problem is how the child policy should decide whom to imitate in each state.
The key observation of the proposed method is that the critic of the RL agent already knows the values of certain states and actions, and therefore it can be used to select which actions should be followed in a principled and globally consistent manner. Thus, we propose the Q-Filtered behaviour cloning loss from Equation 1, where the sum is taken over a batch of size N C sampled from the genetic memory of the agent. µ x and µ y represent the deterministic parent policies, while µ z is the deterministic policy of the child agent.
The indicator functions use the Q-Network of the RL agent to decide which parent takes the best action in each state. The child policy is trained to imitate those actions by minimising the first two terms. The final term is an L 2 regularisation that ensures that the child policy does not overfit in capturing the behaviour of the parents. Figure 1 contains a diagram comparing this new crossover with the ERL n-point crossover. We refer to ERL with the distillation crossover as Distilled Evolutionary Reinforcement Learning (DERL).

Parent selection mechanism
An interesting question is how parents should be selected for this crossover. A general approach is to define a mating score function m : Π × Π → R that takes as input two policies and provides a score. The pairs with higher scores are more likely to be selected. Two ways of computing this score can be distinguished: greedy and distance-based.
can be greedily determined by the sum of the fitness of the two parents. This type of selection generally increases the stability of the population and makes it unlikely that good individuals are not selected.
Distance based. The score m(µ x , µ y ) = d Π (µ x , µ y ) can be computed using a distance metric in the space of all possible policies. "Different" policies are more likely to be selected for mating. The exact notion of "different" depends on the precise form of the distance metric d Π . While previous approaches generally compute distances between individuals in the parameter space (Eiben and Smith 2015), here we propose a novel distance between behaviours. This distance metric takes the form from Equation 2, where ρ x and ρ y are the state-visitation distributions of the two agents: This distance metric measures the expected difference in the actions taken by the two parent policies over states coming from a mixture of their state visitation distributions. This expectation is in practice stochastically approximated by sampling a large batch from the genetic memories of the two agents. While this strategy does indeed introduce more novel behaviours into the population, it also makes the population more unstable by increasing the probability that fit individuals are not selected. We note that a linear combination of the two methods could also be performed with m(µ to exploit the benefits of both methods. In the beginning, α could be set to zero to encourage more exploratory behaviour, and as the training approaches the end, α could be increased towards one to shift the population towards exploitation. We leave this possible improvement for future work.

Proximal mutations
As showed by Lehman et al. (2018), Gaussian mutations can have catastrophic consequences on the behaviour of an agent. In fact, the stability of the policy update is a problem even for gradient descent approaches, where an inappropriate step size can have unpredictable consequences in the performance landscape. Methods like PPO (Schulman et al. 2017) are remarkably stable by minimising an auxiliary KL divergence term that keeps the behaviour of the new policy close to the old one. This section introduces a stable mutation operator with the same incentive of preventing a significant divergence from the behaviour of the parent.
Ideally, one would like to compute numerically how much the visitation distribution changes with tiny variations in each of the parameters. In the absence of a differentiable model of the environment, this is not possible. A proxy for this measurement is the expected absolute gradient of the actions with respect to the weights as in Equation 3, where |A| is the size of the action space, and ρ µ is the visitation distribution of the policy µ θ . This equation quantifies the sensitivity of the actions to parameter variations.
This expression is effectively approximated by sampling states from the genetic memory of the agent. This measure can be used to scale the magnitude of the mutations as in Equation 4. Thus, parameters with high sensitivity are scaled down, and the effective mutation size is reduced. The scaling has an opposite effect on parameters with low sensitivity.
With the absolute value removed, s can be computed efficiently at the cost of cancelling opposing signs in the sum over the states. The use of a sum instead of an expected value empirically helps reduce the effect of these cancellations. This approximation works well in practice.
This mutation produces child policies that are in the proximity of their parent's behaviour. Therefore, we refer to this operator as a proximal mutation (Figure 2), and the version of ERL using it as Proximal Evolutionary Reinforcement Learning (PERL). While the proximal mutations do not explicitly use learning, they rely on the capacity of the policies to learn, or in other words, to be differentiable. Without this property, these behaviour sensitivities on the parameters cannot be computed.

Integration
To obtain the full benefits of the newly introduced operators, they should be used together. The Q-Filtered distillation crossover increases the stability of the population and drives the agents towards regions of the state-action space with higher Q-values. The proximal mutations improve the exploration of the population and its ability to discover better policies. As will be seen in the evaluation section, the two operators complement each other. We refer to their integration with ERL as Proximal Distilled Evolutionary Reinforcement Learning (PDERL). Ultimately, PDERL contains a hierarchy of interactions between learning and evolution. A high-level interaction is realised through the information exchange between the population and the RL agent. The newly introduced operators add a low-level layer of interaction, at the level of the genetic operators. A diagram of PDERL is given by Figure 3.

Evaluation
This section evaluates the performance of the proposed methods, and also takes a closer look at the behaviour of the proposed operators.

Experimental setup
The architecture of the policy and critic networks is identical to ERL. The full list of hyperparameters in given in the Appendix. Those hyperparameters that are shared with ERL are identical to those used by Khadka and Tumer (2018), with a few exceptions that are also detailed in the Appendix.
The PDERL specific hyperparameters were set as follows. The distillation crossover batch size is N C = 128. The proximal mutation batch size is N M = 256. The genetic memory contains 8000 experiences. The learning rate for the distillation crossover is 1e −3 , and the child policy is trained for 12 epochs. All the training procedures use the Adam optimiser. Greedy parent selection is used unless otherwise indicated. As in ERL, the population is formed of k = 10 policies.
When reporting the results, we use the official implementations for ERL 1 and TD3 2 , and the OpenAI Baselines 3 implementation for PPO.

Performance evaluation
This section evaluates the mean reward obtained by the newly proposed methods as a function of the number of environment frames experienced. The results are reported across five random seeds. Figure 4 shows the mean reward and the standard deviation obtained by all algorithms on five MuJoCo environments.
While PERL and DERL bring improvements across multiple environments, they do not perform well across all of them. PERL is effective in stable environments like HalfCheetah and Hopper, where the total reward has low variance over multiple rollouts. At the same time, DERL is more useful in unstable environments like Walker2d and Ant since it drives the population towards regions with higher Q values. In contrast, PDERL performs consistently well across all environments, demonstrating that the newly introduced operators are complementary. PDERL significantly outperforms ERL and PPO across all environments. Despite being generally less sample efficient than TD3, PDERL catches up with it eventually. PDERL significantly outperforms TD3 on Swimmer, HalfCheetah and Ant, and marginally on Hopper and Walker2d. Table 1 reports the final reward statistics for all the tested models and environments. Side by side videos of ERL and PDERL running on simulated robots can be found at the following link: https://youtu.be/7OGDom1y2YM. The following subsections take a closer look at the newly introduced operators and offer a justification for the improvements achieved by PDERL.

Crossover evaluation
A good indicator for the quality of a crossover operator is the fitness of the offsprings compared to that of the parents. Figure 5 plots this metric for ten randomly chosen pairs of parents in the Ant environment. Each group of bars gives the fitness of the two parents and the policies obtained by the two types of crossovers. All these values are normalised by the fitness of the first parent. The performance of the child obtained via an n-point crossover regularly falls below 40% the fitness of the best parent. At the same time, the fitness of the policies obtained by distillation is generally at least as good as that of the parents.  The state visitation distributions of the parents and children offer a clearer picture of the two operators. Figure 6 shows these distributions for a sample crossover in the Ant environment. The n-point crossover produces a behaviour that diverges from that of the parents. In contrast, the Qfiltered distillation crossover generates a policy whose behaviour contains the best traits of the parent behaviours. The new operator implicitly drives each new generation in the population towards regions with higher Q values. Figure 7 shows the fitness of the children obtained by the two types of mutation for ten randomly selected parents  Figure 8: As before, the blue contours represent the state visitation distribution of the parent, whereas the red ones represent the difference. The child obtained by proximal mutation inherits the behaviour of the parent to a large degree and obtains a 600 fitness boost. The behaviour obtained by Gaussian mutation is entirely different from that of the parent. The KL divergence between the parent and child distributions (0.03 and 0.53) quantitatively confirm this .

Mutation evaluation
As in the previous section, the analysis of the state visitation distribution of the policies reveals the destructive behaviour of the Gaussian mutations. The contours of these distributions for a sample mutation are given in Figure  8. The policy mutated by additive Gaussian noise completely diverge from the behaviour of the parent. This sudden change in behaviour causes catastrophic forgetting, and the new offspring falls in performance to a total reward of −187. In contrast, the proximal mutation generates only a subtle change in the state visitation distribution. The offspring thus obtained inherits to a great extent the behaviour of the parent, and achieves a significantly higher total reward of 5496.
Another benefit of the proximal mutations is that the size of the change in the behaviour can be directly adjusted by tuning the magnitude of the mutations. Figure 9 shows how increasing the mutation magnitude gradually induces a more significant change in the behaviour of the child policy. This is not the case for the Gaussian mutations where a given mutation size can be unpredictably large and non-linearly related to the behaviour changes. The red contours show how the differences from the parent distribution increase as the mutation magnitude becomes higher. This is also confirmed by the KL divergence between the parent and child distributions that strictly increases with the mutation magnitude.

Related work
This paper is part of an emerging direction of research attempting to merge Evolutionary Algorithms and Deep Reinforcement Learning: Khadka and Tumer (2018), Pourchot and Sigaud (2019), Gangwani and Peng (2018), Khadka et al. (2019). The closest to this work remain the papers of Lehman et al. (2018) and Gangwani and Peng (2018). Both papers address the destructive behaviours of classic variation operators. Lehman et al. (2018) focus exclusively on safe mutations, and one of their proposed operators is directly employed in the proximal mutations. However, their paper is lacking a treatment of crossovers and a tighter integration with learning.
At the same time, the methods of Gangwani and Peng (2018) are focused exclusively on safe operators for stochastic policies, while the methods proposed in this work could be applied to stochastic and deterministic policies alike. The closest aspect of their work is that they propose a crossover operator with the same goal of merging the behaviour of two agents. Their solution reduces the problem to the classic single parent distillation using a maximum-likelihood approach to combine the behaviours of the two parents. They also propose a mutation operator based on gradient ascent using policy gradient methods. However, this deprives their method of the benefits of derivative-free optimisation such as the robustness to local optimums.

Conclusion
The ERL algorithm has demonstrated how genetic algorithms can be scaled to DNNs using an integration with learning. In this paper, we propose the PDERL algorithm that achieves a new scalability level through a tighter, hierarchical integration of learning and evolution. While PDERL maintains the bi-directional transfer of information between the population and the RL agent, it also uses learning at the level of the genetic operators. Unlike the traditional operators, the learning-based ones have the desired functionality and do not cause catastrophic forgetting when applied to directly encoded DNNs. Finally, we show that PDERL outperforms ERL, PPO and TD3 in all the tested environments.
The hyperparameters that are shared with ERL have the same values as those reported by Khadka and Tumer (2018), with a few exceptions. For Walker2D, the synchronisation rate ω was decreased from 10 to 1 to allow a higher information flow from the RL agent to the population. In the same environment, the number of evaluations ξ was increased from 3 to 5 because of the high variance of the total reward across episodes. Another modification is that the fraction of elites in the Hopper and Ant environments was reduced from 0.3 to 0.2. Generally, a higher number of elites increases the stability of the population, but the stability gained through the new operators makes higher values of this parameter unnecessary. Table 2 includes the hyperparameters that where kept constant across all environments.

Interactions between learning and evolution
One of the motifs of this work is the interaction between learning and evolution. In PDERL, this can be quantitatively analysed by looking at the number of times the RL agent was selected, discarded or became an elite in the population. Figure 10 shows how these numbers evolve during training and reveals that each environment has its own unique underlying interaction pattern.
Swimmer. Swimmer is an environment where the genetic population drives the progress of the agent almost entirely. The RL agent rarely becomes good enough to be selected or become an elite.  HalfCheetah. HalfCheetah is at the other end of the spectrum from Swimmer. In this environment, the RL agent becomes an elite after over 90% of the synchronisations early in training. As the population reaches the high-reward areas, genetic evolution becomes slightly more important for discovering better policies.
Hopper. On Hopper, the RL agent drives the population in the first stages of training, but the population obtains superior total rewards beyond 1.5 million frames. Therefore, evolution has a greater contribution to the late stages of training.
Walker2d. In this environment, the dynamics between learning and evolution are very stable. The selection rates do not change significantly during the training process. This is surprising, given the instability of Walker2d. Overall, evolution has a much higher contribution than learning.
Ant. Unlike in the other environments, in the Ant environment, the interactions between learning and evolution are more balanced. The curves converge towards a 40% probability of being discarded, and a 60% probability of becoming an elite or being selected. Table 4 shows the final mean selection rates and their standard deviations side by side with the ones reported by ERL. This comparison indicates how the dynamics between evolution and learning changed after adding the new crossovers and mutations. The general pattern that can be seen across all environments is that the probability that the RL agent becomes an elite decrease. That probability mass is mainly moved towards the cases when the RL agent is discarded. This comes as another confirmation that the newly introduced variation operators improve the performance of the population and the RL agent is much less often at the same level of fitness as the population policies.

Parent selection mechanism
The previous experiments used the greedy parent selection mechanism for choosing the policies involved in the crossovers. This section offers a comparative view between this greedy selection and the newly proposed distance-based selection.
The mechanisms are compared in Figure 11 on Hopper and Walker2d. On a relatively unstable environment like Walker2d, the distance-based DERL and PDERL perform significantly worse than their fitness-based equivalents. However, on Hopper, which is more stable than Walker2d, the distance-based PDERL surpasses the fitness-based one, (b) Walker2d-v2 Figure 11: A comparison between the greedy (fitness-based) parent selection mechanism and the distance-based parent selection. The distance-based selection works better in stable environments like Hopper, but worse in environments with high variance across different episodes like Walker2d.
while also having very low variance. The fact that the distance-based selection performs better in the early stages of training for both environments further supports the idea of using a convex combination of the two selections.