Year: 2018

Abstract:
Current deep neuroevolution models are usually trained in a large parameter search space for complex learning tasks, e.g. playing video games, which needs billions of samples and thousands of search steps to obtain significant performance. This raises a question of whether we can make use of sequential data generated during evolution, encode input samples, and evolve in low dimensional parameter space with latent state input in a fast and efficient manner. Here we give an affirmative answer: we train a VAE to encode input samples, then an RNN to model environment dynamics and handle temporal information, and last evolve our low dimensional policy network in latent space. We demonstrate that this approach is surprisingly efficient: our experiments on Atari games show that within 10M frames and 30 evolution steps of training, our algorithm could achieve competitive result compared with ES, A3C, and DQN which need billions of frames.

heading: 1 INTRODUCTION
text: Training an agent that can handle difficult tasks in complex environment is always challenging for artificial intelligence. Most works for solving such problems are using reinforcement learning algorithms, e.g. learning a value function (Watkins & Dayan, 1992), or a policy function (Kakade, 2002), or both (Sutton et al., 2000). Combined with deep neural networks, the so-called deep reinforcement learning achieved great success in playing Atari games (Mnih et al., 2015), operating robots (Yahya et al., 2017), and winning human experts in challenging competitions like Go and Dota (Silver et al., 2016; OpenAI, 2018). Recently, a portion of works are trying to combine deep neural networks with evolution strategies to solve similar problems. This approach, called deep neuroevolution, achieved competitive results compared to deep reinforcement learning on Atari Games and Mujoco tasks as well in much shorter training time due to its outstanding scalability and feasibility for parallelization (Salimans et al., 2017; Such et al., 2017).
However, large-scale deep neuroevolution is both data and computation inefficient: it consumes thousands of CPU cores and needs billions of frames and thousands of generations to obtain significant results. In this work, we introduce a novel way to improve its efficiency: we train a variational autoencoder (VAE) to encode samples, and a recurrent neural network to model environment dynamics and handle temporal information; afterward, we train a two layer policy network with latent state vectors using covariance matrix adaption evolution strategy (CMA-ES).
We evaluate our sample efficient deep neuroevolution algorithm, or in short SEDN, on 50 Atari Games from OpenAI Gym (Brockman et al., 2016), experiment shows that our approach surpassed DQN (Mnih et al., 2013), A3C (Mnih et al., 2016), and ES (Salimans et al., 2017) methods in several Atari games within much fewer state frames, shown in Table 1. Our key findings are listed below:
• Evolution goes faster with latent state input. SEDN takes less than 30 evolution steps with only 32 children to surpass ES (Salimans et al., 2017) in several games: the latter needs thousands of children and generations.
• Training is more data efficient. Compared to ES and asynchronous RL methods which needs billions of frames to train, SEDN takes less than 10 million frames to achieve targets.
• Training is more computation efficient. On a workstation of one Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz and one Titan X Pascal GPU, SEDN takes less than 4 hours to finish the evolution, compared to ES which needs a cluster to finish.

heading: 2 METHOD
text: Many real world decision making problems could be modeled as Markov Decision Process (MDP). Since proposed by Bellman (1957), it has been applied in many disciplines, e.g. robotics, economics and game playing. A Markov decision process is defined by: a set of states S, a set of actions A, transition probabilities defining probability over next state given current state and action P : S × A × S → [0, 1], a initial state distribution d : S → [0, 1], and a reward function that maps states and actions into a scalar R : S × A → R. A finite time horizon episode τ of T steps is a sequence of state-action-reward tuples: (s0, a0, r0), (s1, a1, r1), . . . , (st, at, rt), . . . (sT , ∅, ∅) called trajectory, where st ∈ S, at ∈ A, rt = R(st, at), st+1 ∼ P (st, at), s0 ∼ d0(s) where sT is called terminal state.
For a finite time horizon MDP, reinforcement learning (RL) algorithms learn a parameterized policy that defining probability of actions to be taken given current states πθ : S × A → [0, 1], and maximize episodic reward: ∑T−1 i=0 ri, or formally:
maximize θ E T∑ i=0 R(st, at) (1)
where s0 ∼ d(s),at ∼ πθ(st), st+1 ∼ P (st, at) (2)
Above objective function takes the expectation over episodic rewards, which could be approximated by sampling N trajectories from policy π and environment dynamics P and d. We misuse notations such that r(τ) donates episodic reward and p(τ) represents trajectory probability, then we have below reformulation:
maximize θ L(θ) = N∑ i=1 r(τi)p(τi) (3)
where p(τ) = d(s0) T−1∏ t=0 πθ(st, at)p(st, at, st+1), r(τ) = T−1∑ t=0 ri (4)
Vanilla policy gradient (PG) methods optimize L(πθ) by taking its gradient:
∇θL ≈ 1
N N∑ i=1 r(τi)∇θ log pθ(τi) (5)
= 1
N N∑ i=1 r(τi) Ti−1∑ t=0 ∇θ log πθ(st, at) (6)
and updates policy πθ to maximize expected episodic reward. Variants of policy gradient methods achieved great success in recent years, e.g. TRPO (Schulman et al., 2015) and PPO Schulman et al. (2017).
Evolution strategies (ES), instead, take another approach to solve above optimization problem without any differentiation: it approximates the gradient by sampling, shown in Equation 7.
∇θL ≈ 1
σ2 Eθ̂∼N (0,σ2)(L(θ + θ̂)θ̂) (7)
Vanilla ES solves MDP problems iteratively shown in Algorithm 1: firstly, it samples Gaussian noise from a normal distribution; secondly, it injects noise into current policy, and evaluates it in environment, obtaining episodic rewards; thirdly, it updates current policy parameters by the product of episode reward and noise injected. ES and PG are interpreted as two faces of Gaussian smoothing on policy: ES is on parameter space smoothing and PG is on action space smoothing (Salimans et al., 2017).
Algorithm 1 Evolution Strategies Input: Learning rate η, noise standard derivation σ, initial policy parameter θ
1: for t = 0, 1, . . . do 2: Sample N parameter noise: θ̂i ∼ N (0, σ2I) for i = 1, . . . , N 3: Execute perturbated deterministic policies πθi : at = arg maxa πθi(st) to produce trajectory τi, where θi = θ + θ̂i for i = 1, . . . , N 4: Update policy parameter θ ← θ + α/(Nσ2) ∑N i=1 r(τi)θ̂i 5: end for
ES enjoys several advantages over PG. Firstly, it is a black-box optimization method that does not need gradients. In problems where gradients are not available, or state encoding is not feasible, or gradient is blocked by some operations in neural networks, ES exhibits its wider range of applications over PG. Secondly, in low dimensional optimization problems like Mujoco tasks, ES has competitive performance with PG (Salimans et al., 2017), but is less sensitive to hyperparameters (Heidrich-Meisner & Igel, 2008). Thirdly, the exploration-exploitation trade-off needs to be balanced in RL here is integrated: policy parameter perturbation ensures different behaviors during evaluation, whereas RL has to use a stochastic policy to explore. Lastly, ES is highly scalable therefore can be trained faster by a group of workers in parallel.
However, in n-dimensional search space where n is large, the exploration directionsO(2n) increases in orders with n, therefore random sampling for gradient approximation would be very inefficient. For video games like Atari, high dimensional pixel state space induces more parameters of policy to be optimized, hence less efficient for ES. Surprisingly, Salimans et al. (2017) shows that even natural evolution strategies (NES) can beat common RL algorithms in several Atari games. Among the class of evolution strategies, the covariance matrix adaption evolution strategy (Hansen & Ostermeier, 2001) is the most successful one in solving low dimensional optimization problems. Would covariance matrix adaption evolution strategy (CMA-ES) perform better or faster over NES for high dimensional tasks? To answer this question, one problem has to be solved, that the application of CMA-ES on high dimensional space is infeasible since it needs to compute a large covariance matrix of size O(n2). Recently advances in deep learning show promises to encode high dimensional spatial-temporal information into low dimensional latent vectors (Oh et al., 2015; Pathak et al., 2018; Ha & Schmidhuber, 2018) by modeling environment dynamics. In this case, we can convert high dimensional RL tasks into low dimensional tasks, where CMA-ES can take its advantage.

heading: 2.1 COVARIANCE MATRIX ADAPTION EVOLUTION STRATEGY
text: CMA-ES improves ES in two ways. Firstly, vanilla ES samples noise from a fixed Gaussian distribution N (0, σ2I) of only one degree of freedom σ, the step size; whereas CMA-ES, samples noise from N (0,C) where covariance matrix C has n(n+ 1)/2 degree of freedom. Secondly, CMA-ES updates sampling parameters σ,C by rank based method, rather than updating policy parameter by approximating its gradients.
We now explain rank-based ES. Rank-based ES is a selection-recombination process. Let f donates the objective function, λ be population size, µ be parent population size, {wi|w1 > w2 > · · · > wµ > 0, ∑µ i=1 wµ = 1, i = 1, . . . , µ} be weight coefficient for recombination. Firstly, Rankbased ES first samples λ points from Gaussian distribution xi ∼ m + σNi(0,C) for i = 1, . . . , λ. Next, it evaluates sampled points on the objective function, and sort according to the cost such that f(x1) < f(x2) < · · · < f(xλ). In the following, it recombines to get new mean and covariance matrix m ← ∑µ i=1 wixi, C ← ∑µ i=1 wi(xi − m)(xi − m)T . This procedure repeats for G generations.
Similar to gradient based optimization methods, CMA-ES further uses momentum, step size control and path accumulation for more stable optimization. Let y(g+1)i ∼ N (0,C(g)), i = 1, . . . , λ be sampled noise to be injected, xi = m + σyi, suppose {yi|i = 1, . . . , µ} are sorted such that f(x1) < f(x2) < · · · < f(xλ), updating of covariance matrix with momentum gives:
C(g+1) = (1− cµ)C(g) + cµ µ∑ i=1 wiy (g+1) i y (g+1)T i (8)
where g is the number of generation and cµ is momentum constant. In favor to generate best point from the current generation, it further adds the best point’s covariance term into Equation 8:
C(g+1) = (1− cµ − c1)C(g) + c1y(g+1)1 y (g+1)T 1 + cµ µ∑ i=1 wiy (g+1) i y (g+1)T i (9)
In practice, exponential smoothing over parents’ mean path, or evolution path, is used:
p(g+1)c = (1− cc)p(g)c + cc(m(g+1) −m(g))/σ(g) (10)
C(g+1) = (1− cµ − c1)C(g) + c1p(g+1)c p(g+1)Tc + cµ µ∑ i=1 wiy (g+1) i y (g+1)T i (11)
Next, we explain how to control the step size σ. The step size is related to the evolution path: it should be decreased if the path is short and increased if the path is long. In contrast to evolution path pc, here we need to correct its directions by taking conjugate evolution path pσ:
p(g+1)σ = (1− cσ)p(g)σ + cσC(g),− 1 2 (m(g+1) −m(g))/σ(g) (12)
To update step size, we compare conjugate evolution path with the expectation of length of vectors sampled from normal distribution N (0, I):
lnσ(g+1) = lnσ(g) + cσ dσ ( ‖pσ‖ E‖N (0,1)‖ − 1) (13)
Hansen (2016) suggests default hyperparameters for CMA-ES, we summarize complete CMA-ES in Algorithm 2.
Algorithm 2 CMA-ES Input: m ∈ Rn, σ ∈ R+, λ, µ ∈ N, µ < λ,C = I,pc = 0,pσ = 0
wi such that µw = 1/ ∑µ i=1 w 2 i ≈ 0.3λ,w1 ≥ · · · ≥ wµ > 0, ∑µ i=1 wi = 1
cc,≈ 4/n, cσ ≈ 4/n, c1 ≈ 2/n2, cµ ≈ µw/n2, c1 + cµ ≤ 1, dσ ≈ 1 + √ µw/n
1: for each generation step do 2: Sampling: yi ∼ Ni(0,C),xi = m + σyi for i = 1, . . . , λ 3: Evaluation: obtain f(xi), sort {xi|i = 1, . . . , λ} points such that f(x1) ≤ · · · ≤ f(xλ) 4: Mean update: m← ∑µ i=1 wixi, yw = ∑µ i=1 wiyi
5: Evolution path update: pc ← (1− cc)pc + yw √ 1− (1− cc)2 √ µw
6: Conjugate evolution path update: pσ ← (1− cσ)pσ + C−1yw √ 1− (1− cσ)2 √ µw
7: Covariance matrix update: C← (1− c1 − cµ)C + c1pcpcT + cµ ∑µ i=1 wiyiy T i 8: Step size update: σ ← σ exp( cσdσ ( ‖pσ‖
E‖N (0,1)‖ − 1)) 9: end for
CMA-ES addresses typical problems in non-linear optimization problems like ill-conditioning and ruggedness. The covariance matrix approximates the inverse Hessian matrix, and the updates approximate natural gradient by adapting the search metric into a sphere, hence increasing performance by orders of magnitude. Rank based selection ensures its invariance against translation and rotation in search space. The step size control facilitates fast convergence. However, it is not applicable to deep neural networks used in DRL which has millions of parameters and induces O(n2) order of the size of the covariance matrix. This leads to an intuitive approach by encoding frames into small latent vectors to model the dynamics of the game environment, and evolve with a lower dimensional policy parameter space.

heading: 2.2 ENVIRONMENT DYNAMICS MODELING FOR EPISODIC DATA ENCODING
text: How to learn a model that can encode episode data τ : s0, a0, s1, a1, . . . sT , aT ? We develop a method by modeling environment dynamics. Perhaps the earliest work on building predictive model for vision based RL tasks was introduced by Schmidhuber & Huber (1991), which proposed using neural networks to predict attention region given previous frames and actions. After the success of deep learning, Oh et al. (2015) proposed an Encoding-Transformation-Decoding framework for action conditional video prediction, and applied on Atari games. More recently, Pathak et al. (2018) learns forward and inverse model dynamics to imitate expert’s behavior given only image sequences. Ha & Schmidhuber (2018) also learned forward model dynamics using random policy demonstrations, and train a controller totally inside the dream.
In this work, we take similar approach to encode episodic data. Specifically, we first train a Variational Autoencoder (VAE) that encode spatial information; then train an recurrent neural network (RNN) to encode temporal information by learning model dynamics. Let φe : S → Rn, φd : Rn → S donates our encoder and decoder network where n is our latent space dimension, f : Rn × A → Rn be the our RNN, and c : Rn × Rm → A be our policy network where m is the dimension of our RNN’s hidden state. The encoder φe encodes state frame st into a latent vector zt:
µ(st), σ(st) = φe(st) (14) zt ∼ N (µ(xt), σ(xt)) (15)
The decoder φd decodes latent vector back to state frame ŝt. VAE is trained to minimize the reconstruction loss between st, ŝt, and KL-divergence between latent vector and N (0, I):
ŝt = φd(zt) (16)
Lvae = ‖st − ŝt‖2 +KL[N (µ(st), σ(st))‖N (0, I)] (17)
LSTM f models the environment dynamics in latent state space, and encode temporal information:
µ(ŝt+1), σ(ŝt+1) = f(zt, at) (18) ẑt+1 ∼ N (µ(ŝt+1), σ(ŝt+1)) (19)
LSTM is trained to minimize the KL-divergence between actual latent state from vae’s encoder and predicted latent state:
µ(st+1), σ(st+1) = φe(st+1) (20) Lrnn = KL[N (µ(ŝt+1), σ(ŝt+1))‖N (µ(st+1), σ(st+1))] (21)
The policy network takes the latent vector of the current state, and previous timestep’s hidden state of RNN, we use deterministic policy in this work:
at ∼ c(zt, ht−1)
We illustrate our model in Figure 1.

heading: 3 EXPERIMENTS
text: Our complete training pipeline is summarized in Algorithm 3. We use OpenMPI’s master-slave mode (Scarabello & Clipp, 2018) for parallel training of policy network during evolution steps, Hansen (2018) for CMA-ES optimizer, and Pytorch (Paszke et al., 2017) deep learning platform to train VAE and RNN. We train the three modules separately. Firstly, we collect episode data during training the policy network using CMA-ES. Secondly, we extract all video frames from collected data and train our variational autoencoder. Thirdly, we convert all state frames into latent state vectors using VAE trained. Lastly, we train our LSTM using the converted episode data. This training cycle iterates till the end.
During the training, we set our training data buffer to be a FIFO queue of size 1M : this will ensure the safety of workstation memory. The training process will stop when the maximum number of frames is reached or the maximum evolution step is reached, whichever is earlier. Our parallel training adopts a task-queue master-slave mode: the master node immediately distributes remaining tasks once there is any slave node available, and slave node requests new task right after it finishes a previous task. Unlike Salimans et al. (2017), our master-slave communication frequency is so low that it only takes a small percentage of time compared to episode data sampling steps.
We conduct experiments on 50 Atari 2600 games in OpenAI Gym (Brockman et al., 2016). We choose a larger encoder convolutional network compared to Vanilla DQN (Mnih et al., 2013) for better VAE performance: our experiment shows poor decoding performance if following Vanilla DQN’s convolutional network. Our data pre-possessing is also different from Vanilla DQN: we resize image frames directly without frame stack, grayscale conversion or frame skip. We tried to stack latent state vector as input for policy network but found performance drop: the reason may be that increased dimension required for policy network slows down the evolution process for CMA-ES optimizer.
Our encoder network consists of 4 convolutional layers with 32, 64, 128, 256 channels followed by a flatten layer and a linear layer of 128 units. The convolutional layers use 4 × 4, 4 × 4, 3 × 3, 3 × 3 filter size and strides of 2, 2, 1, 1. Our decoder network reverses the operations except the last deconvolutional layer uses 6 × 6 filter size. Each convolutional and deconvolutional layer uses rectified activation, except that last convolutional layer uses tanh activation. Image frames are resized into (84, 84, 3) to feed into our network. We set our latent state dimension to be 128. We use one layer LSTM of 128 hidden size to model environment dynamics, therefore our input dimension of policy network is 256. Our policy network is a two-layer MLP of size 256− 32− na, where na is the action space dimension.
The training of VAE and RNN is triggered every 8 evolution step. Each child policy is evaluated for 16 episodes, and the average episode reward is returned for CMA-ES optimizer to update. To visualize the training process of policy network, we make a boxplot of average episode reward distribution of Frostbite, shown in Figure 2 The maximum reward performance among policy networks increases significantly right after the training of VAE and RNN triggered at 8th, 16th generations. This agrees with our assumption that VAE and RNN encode spatial-temporal information from past experience and provides good feature representation for policy to evolve. It is worth to notice that for some game, e.g. Private Eye, policy performance increases significantly even without updating VAE and RNN; this observation agrees with Blundell et al. (2016) where features are extracted from random matrix projection.
However, we also notice that for some games, policy networks performance drops significantly right after updating of VAE and RNN, e.g Atlantis shown in Figure 3. We find that the cause may be the poor encoding performance of VAE. Shown in Figure 4, we compare VAE’s encoding-decoding on Frostbite and Atlantis. We find that image decoded from VAE will ignore tiny moving objects, leaving only a static background; this issue occurs especially in rare frames far from episode starts; similar phenomenon was found in games like Kangaroo, Gravitar and Breakout.
Experiment result is summarized in Table 1. Our SEDN surpasses ES, DQN, and A3C in 7 of 50 Atari games, but with only 10M frames, whereas DQN using 200M frames, and ES and A3C using 1B frames. Due to the limitation of time and resources, we did not conduct hyperparameter tuning on SEDN. We believe better encoding techniques to address above issues will give a boost of performance on SEDN. We left this as an open direction in future works.

heading: 4 DISCUSSION
text: Whereas traditional reinforcement learning algorithms need to balance between exploration and exploitation (Sutton et al., 1998), and even add perturbation on parameters to ensure good exploration (Plappert et al., 2017); evolution strategy directly drives exploration by sampling from optimizer’s distribution parameters (Salimans et al., 2017) during evolution: it integrates exploration and exploitation. This is what makes it so efficient especially in some low dimensional control tasks like CartPole. By encoding spatial-temporal information from high dimensional pixel space into low dimensional latent space, a challenging RL task could hence be converted into a simpler task where evolution strategies have advantages over deep reinforcement learning methods.
Similar to what Salimans et al. (2017) are facing: ES does not perform well on some easy games like Enduro and Breakout. One possible reason is that ES’s optimized policy is close to where it is randomly initialized due to evolution path control under ES, whereas optimal policy for dense reward games like Breakout are far away from where it is randomly initialized. Another reason is that, long episodic time horizon games like Enduro are very inefficient for ES to solve: given limited number of frames, a longer episode will result in less number of episodes, hence less and slower updates for ES. In addition, episode rewards ignore temporal reward information over time steps. This issue is critical in games like Enduro. Enduro is a car racing game, in which agent obtain rewards after passing other cars and penalty if it is passed by other cars, final ranking will be accounted as the episodic reward after a long episode. A random policy will always obtain a zero episodic reward under this case, hence ES learns nothing from such games. These two issues limit the application of vanilla ES and its variants, remaining to be resolved in future works. A possible direction is a mixture of ES and RL, e.g. using ES as a warm start of RL policy.

heading: 5 CONCLUSION
text: Our work introduces a fast and efficient evolution algorithm that trains deep neural networks to play Atari games. Our experiment shows that encoding spatial-temporal information from high dimensional pixel space into low dimensional latent space makes ES fast, effective and efficient: SEDN outperforms DQN, A3C, and ES in 30 evolution steps with 10M frames experience in several Atari games. We conclude SEDN is a competitive approach to solving challenging RL tasks.
In future works, we plan to address issues discussed in section 4 by applying state of the art computer vision techniques like self-attention maps for better information encoding; we would also like to apply information encoding with RL to understand feature importance for RL.
Algorithm 3 Complete Training Pipeline Input: VAE encoder φenc : xt → zt, VAE decoder φdec : zt → xt
RNN f : (zt, at)→ zt+1, Policy p : (zt, ht−1)→ at and CMA-ES optimizer: g 1: for each iteration do 2: training data buffer X = {} // Train policy network and collect data 3: for each evolution step do 4: sample λ children {c1, . . . , cλ} from CMA-ES optimizer g 5: for child i from 1 to λ do 6: contrust policy pi from ci 7: for each episode j from 1 to N do 8: sample episode data Yij = (s0, a0, . . . , sT , aT ) and episode reward Rij with VAE, RNN and Policy:φenc, f, pi 9: append episode data to training data X ← X ∪ {Yij}
10: end for 11: Calculate average return for child i: R̄i = ∑N j=1Rij/N 12: end for 13: Update CMA-ES optimizer g ← g(c1, R̄1, c2, R̄2, . . . , cλ, R̄λ) 14: end for // Train VAE and extract frames 15: Training image frames I = {} 16: for each Y in X do 17: (s1, a1, . . . , sT , aT )← Y 18: I ← I ∪ {s1, s2, . . . , sT } 19: end for 20: Train and update VAE φenc, φdec with I 21: Extracted episode data S = {} 22: for each Y in X do 23: (s1, a1, . . . , sT , aT )← Y 24: S ← S ∪ {φenc(s1), a1, . . . , φenc(sT ), aT } 25: end for // Train RNN 26: for each Y in S do 27: (φenc(s1), a1, . . . , φenc(sT ), aT )← Y 28: µ1:T , σ1:T = φenc(s1:T ), z1:T ∼ N (µ1:T , σ1:T ) 29: µ̂2:T , σ̂2:T = f(z1:T−1, a1:T−1) 30: Calculate KL-divergence Loss L = KL[N (µ(ŝt+1), σ(ŝt+1))‖N (µ(st+1), σ(st+1))] 31: Backward NLL loss and update RNN f 32: end for 33: end for 34: Construct final policy pf from CMA-ES optimizer’s favorite solution 35: return φdec, φenc, f, pf

Review summaries:
They propose "Sample Efficient Deep Neuroevolution" (SEDN) model and experiment on Atari games. In this model, they use a Variational Encoder (VAE) to encode state frames into a latent vector, and use an LSTM to encode the current latent vector and action to predict the next latent space. A policy network (trained using CMA-ES) takes the latent space, and hidden state of the RNN as an input, and outputs an action to execute.

The main difficulty of neuroevolution---requiring a huge number of simulations for high dimensional problem---is addressed in this paper by introducing VAE to reduce the state space dimensionality and using a rather shallow controller network. This idea itself is very promising, however, it has been introduced in (Ha and Schmidhuber, 2018).  Still, there seems to be differences in how to gather histories and how to use them. Nevertheless, the differences are not well described in the text. The effect of the modification is not evaluated on experiments.