Title: SEERL: SAMPLE EFFICIENT ENSEMBLE REINFORCE-MENT LEARNING

Abstract: Ensemble learning is a very prevalent method employed in machine learning. The relative success of ensemble methods is attributed to its ability to tackle a wide range of instances and complex problems that require different low-level approaches. However, ensemble methods are relatively less popular in reinforcement learning owing to the high sample complexity and computational expense involved. We present a new training and evaluation framework for model-free algorithms that use ensembles of policies obtained from a single training instance. These policies are diverse in nature and are learned through directed perturbation of the model parameters at regular intervals. We show that learning an adequately diverse set of policies is required for a good ensemble while extreme diversity can prove detrimental to overall performance. We evaluate our approach to challenging discrete and continuous control tasks and also discuss various ensembling strategies. Our framework is substantially sample efficient, computationally inexpensive and is seen to outperform various baseline methods, including other ensemble approaches.

1. INTRODUCTION:

Deep reinforcement learning over the years has made considerable advancements with applications across a variety of domains -from learning to play Atari 2600 suite from raw visual inputs (Mnih et al. (2015) ), mastering the game of Go (Silver et al. (2017) ), learning locomotion skills for robotics (Schulman et al. (2015b; a) ; Lillicrap et al. (2017) ) and most recently, the development of Alpha Fold (Evans et al. (2018) ) to predict the 3D structure of a protein solely based on its genetic sequence. However, creating a single agent that performs well, is sample efficient and robust, is a challenging task. To improve the performance on a task, one requires more samples which leads to reduced sample efficiency. On the other hand, increasing robustness is associated with reducing the variance in performance, which is difficult owing to the lack of repeatability when using deep neural networks. However, without deep neural networks, the required performance and generalization on many tasks cannot be achieved. We look towards ensemble learning as a method to overcome the above problems. We exploit the well-known concept of ensemble learning and adapt it for reinforcement learning in a novel way. Traditionally, the idea of using ensembles in reinforcement learning settings is associated with combining multiple value functions or policies from different models. These models could be the same algorithm trained across different hyper-parameter settings or different algorithms altogether. Training multiple such models is an approach that cannot be used in practice owing to high sample complexity and computational expense. We tackle the problem by creating sufficiently diverse policies from a single training instance. These policies are obtained by directed perturbation of the model parameters at regular intervals. The directed perturbation is induced by sudden and sharp variations in the learning rate, and for doing so, we employ cyclical learning rates (Loshchilov & Hutter (2016) ). When the model parameters are perturbed using more significant learning rates, the directed motion along the gradient direction prevents the optimizer from settling in any sharp basins. It tends to move into the general vicinity of the local minima. Lowering the learning rates at such a time leads the optimizer to converge to some final local minima. We leverage the diversity of the policies learned at these different local minima for the ensemble. We show through experimentation that directed perturbation and not ran-dom perturbation is necessary for obtaining diverse policies. We outperform SOTA in a number of environments, as shown in Figure 1(b) .

Additionally, we develop a framework that selects the best subset of policies for including in the ensemble. Again, our approach does not require additional samples to find this subset. Since we use models from a single training instance instead of training M different models independently from scratch, we refer to our approach as Sample Efficient Ensemble Reinforcement Learning (SEERL) To summarize, our main contributions are:

• A novel sample efficient framework for learning M diverse models from a single training instance with little to no additional cost.

• An optimization framework to select the best policies, from a diverse set, for ensemble

• Evaluation of various ensemble strategies for discrete and continuous action spaces.

2. RELATED WORK:

There has recently been a small body of work on using ensembles for reinforcement learning which is associated with ensembles during the training phase to reduce the variance and improve robustness of the policy. 

3. PRELIMINARIES:

Reinforcement learning is associated with sequential decision making and involves the interaction of an agent with an environment. In this paper, we consider a discrete-time finite-horizon Markov Decision Process(MDP) defined by (S, A, P , ρ t , r, γ), where S denotes the set of states, A denotes the set of actions, P : S × A → S' the transition function, ρ t , the probability distribution over the initial states, r : S × S × A → R, the reward function and γ the discount factor. Policy dictates the behavior of an agent at a particular state in an environment. More formally, a policy is defined by π(s) : S → P (A) where P (A) denotes the probability distribution over actions a A in a state s S. The objective of the agent is to maximize the discounted return R t = Σ T i=t γ i-t r(s i ,a i ,s i+1 ), where r(s i ,a i ,s i+1 ) is the reward function. Our approach saves policies during training at periodic intervals when the learning rate anneals to a small value. It is then used as an ensemble during the evaluation phase.

4.1. LEARNING POLICIES:

To learn multiple policies from a single training instance, we perturb the parameters of the model at regular intervals. Instead of random perturbations, we employ directed perturbation in the direction of the gradient steps. We use cosine cyclical annealing learning rate schedule (Loshchilov & Hutter (2016) ) to introduce these directed perturbations, as shown in Figure 1 . Depending on the number of time-steps needed to train the agent, and the number of models needed for the ensemble, the learning rate schedule can be calculated.

As the learning rate anneals to a small value, the model converges to a local minimum, and we obtain the first policy. By increasing the learning rate, the model is perturbed along the gradient direction and dislodged from its local minima. In other words, if M models are required, we split the training process into M different training cycles wherein each cycle the model starts at a high learning rate and anneals to a small value. The high learning rate is significant as it provides energy to the policy to escape the local minima and the small learning rate traps it into a well behaved local minima. The formulation is as follows:

α(t) = α 0 2 cos π mod (t -1, T /M ) T /M + 1 (1)

where α 0 is the initial learning rate, t is the time-step, and T is the total number of time steps for which the agent is trained, and M is the number of models.

4.2. POLICY SELECTION:

The policies obtained during training are diverse and of different performance capabilities. Ideally, the best m policies should be selected for the ensemble to avoid bias from the poorer policies. At the same time, the policies also need to be diverse so as to obtain good performance in different parts of the state space when used in an ensemble. Near identical policies would not yield much improvement in an ensemble.

We propose an optimization framework to select the best subset of policies. The formulation has two parts, a model error term and a KL divergence term indicative of diversity. Only optimizing for the model error term would result in the selection of policies with good performance. The addition of the KL divergence term helps balance the requirements of performance and diversity. We have a hyper-parameter β ∈ [1, 2), that balances between diversity and performance. The KL divergence is calculated based on the action distribution between the two polices over the sampled states. The formulation is as follows :

J(w) = s∈S P (s)   m∈M w m   a∈A L(s, a) - β M -1 k∈M,k =m KL(π m (a|s)||π k (a|s))     2 (2)

with the following constraints m∈M w m = 1, w m ≥ 0 ∀m. S is the set of states and P (s) is the probability of observing a particular state. L(s, a) is the weighted error associated with the model and is indicative of the performance of the model. We weigh the loss in a manner that we give more weight when the loss is above a certain threshold value, and the action taken by the model, a, matches the action taken by the ensemble a e . We formalize L(s, a) as follows :

EQUATION

L (s, a) is the total error for a particular state action pair. T err is the threshold value that is used to distinguish the good actions from the bad. If L (s, a) is above the threshold error and the actions match, then we would like to consider that action from the policy as a bad one. For example, in the case of A2C, the total error for a state action pair is the weighted sum of the policy gradient loss and the value function loss. Let V m (s) be the value function at state s obtained by using model m.

From the Markov chain, we can obtain the reward, r(s, a, s ) after taking action a at that state and transitioning to s .

V loss (s) = r(s, a, s ) + γV (s ) -V m (s) (4) π loss (a|s) = ∇log(π(a|s)A(s) (5) L (s, a) = π loss (a|s) + V loss (s) * C v (6)

γ is the discount factor, C v is the coefficient used for weighting the value function.

In a discrete action space, it is relatively easy to determine if the action taken by the model and ensemble are the same. However, in continuous action space, the final ensemble action and the action taken by the policy might never coincide. Therefore, we introduce a bound on the ensembled action. If the action from the model is within a distance from the ensembled action, we consider it as a match. ranges between 0.005 to 0.01, depending on the environment. We use a squared loss formulation to capture the inter-dependencies among the policies. Instead, if the degree were 1, the objective function would be the weighted sum of the loss, and the one with the lowest error would be the best policy. By having a higher degree, we are capturing the dependencies among the policies. By minimizing this objective function, we obtain the values of w m , the Lagrange multipliers to this optimization framework. To choose the best ensemble set, we arrange the values of w m in decreasing order and select the top m values.

In order to run this optimization, we select multiple trajectories from the training samples and use the states from them. It is much more efficient reuse of data in comparison to evaluating the policies directly in the environment. This is also more efficient than searching through all possible combination of selecting m policies.

4.3. ENSEMBLE TECHNIQUES:

Once we choose the m policies, selecting the optimal ensemble strategy is a challenging task. Depending on the complexity of the action space, discrete or continuous, there are multiple strategies to ensemble the actions in the environment. When building ensembles, all m policies are loaded in parallel and provided with an observation from the environment. Based on the observation, every policy outputs an action. The ensemble strategy decides which action to select based on the available set of actions. We divide the ensemble strategy into two categories, based on the complexity of the action space, into strategies for discrete and continuous action spaces. Calculate the learning rate, based on the inputs to the cosine annealing learning rate schedule f 3:

α(t) = f (α 0 , t, T, M ) 4:

Train the agent and optimize using α(t) Collect actions from the m policies, a 1 , a 2 . . . , a m for environment state s t 5:

Find the optimal action, a * using E 6:

Perform action a * on the environment 7:

Obtain cumulative reward for the episode, r t and the next state s t+1 8: end while 9: return Average reward obtained during evaluation

4.3.1. ENSEMBLE IN DISCRETE ACTION SPACES:

In discrete action spaces, we consider majority voting as a good solution. Due to different fixed point convergences of value functions of algorithms trained independently, it is not possible to compare actions by their Q values.

EQUATION

where N m (s, a) is one if the agent m takes action a in state s, else zero. It the case of a tie, random action is chosen among the set of actions having the tie.

4.3.2. ENSEMBLE IN CONTINUOUS ACTION SPACES:

In continuous action spaces, (Duell & Udluft (2013) ) proposes multiple strategies to find the optimal action. However, the performance comparison of the strategies is not provided and environments considered are too simple. The different strategies are as follows:

• Averaging: We take the average of all the actions as part of the ensemble. This strategy could fail in settings where one or more of the actions are extremely biased and thereby shifts the calculated value away from the true mean value.

• Binning: This is the equivalent of majority voting in a continuous action space setting. We discretize the action space into multiple bins of equal size and average the bin with the most number of actions. The average value obtained is the optimal action to take. Through this method, we have discretized the action space, sorted the bins based on its bin-count, and calculated the mean of the bin with the highest bin-count. The only parameter to be specified here is the number of bins to be specified. We use five bins in our experiments

• Density-based Selection(DBS): This approach tries to search for the action with the highest density in the action space. Given M action vectors, a, each of k dimensions to be ensem-bled, we calculate the density of each action vector using Parzen windows as follows:

d i = M j=1 exp- k l=1 (a il -a jl ) 2 r 2 (8)

The action with the highest density, d i , is selected as the final action. The only parameter to be specified is r, and we have chosen r = 0.0001 in our experiments.

• Selection through Elimination(STE): This approach eliminates action based on the Euclidean distance. We calculate the mean of the action vectors and compute the euclidean distance to each action from the mean. The action with the largest euclidean distance is eliminated, and the mean is re-computed. The process is repeated until two actions remain.

The final action is chosen as the average of the two actions.

5. EXPERIMENTS:

We consider the environments from the Atari 2600 game suite and the robotic environments from Mujoco (Todorov et al. (2012) ). The Atari 2600 is considered for its discrete state and action space, whereas Mujoco is used for its continuous state and action space. We conduct our experiments on the following algorithms, A2C (Mnih et al. (2016) ), ACER (Wang et al. (2016) ), ACTKR (Wu et al. ( We use three baseline models to compare with SEERL during the ensemble. The first baseline, B1, ensembles policies that are trained independently from one algorithm, Eg. Five models of A2C, each of which has been trained for 20 million time steps. The second, B2, ensembles policies that are trained independently from different algorithms, Eg. two models of A2C, two models of ACER and one model from ACKTR, each of which has been trained for 20 million time-steps. The third and final baseline, B3, uses policies generated from random perturbation of model parameters at regular intervals. Eg. Five models of A2C, each of which has been obtained by perturbing at regular intervals and saving the parameters. We provide more details regarding the experiments and ablation studies in the Appendix.

Through our experiments, we answer the following questions:

• How does SEERL compare against traditional ensembles in terms of sample complexity and final performance?

• How the diversity among policies contributes to the final performance?

• How are the policies obtained from SEERL any different from those obtained through random perturbation?

5.1. TRAINING AND EVALUATION:

We train both SEERL and single-agent models with the same hyper-parameter configurations. The ambiguity that SEERL will lead to poor convergence as a result of shifting from zero to the maximum learning rate multiple times is mitigated through our results. SEERL performance during training is at least at par or better than the baseline, as shown in Figure 2 . We train the models across different values of M ranging from 3 to 9. The baseline models are trained using the set of hyper-parameters seen in their original implementation. In order to create diverse baseline models, we train the models on five different seeds with different learning rates and learning rate schedules. We consider two learning rate schedules, constant and linearly decreasing. Using our policy selection framework, we then select m policies for the ensemble. For the majority of our experiments, we consider m = 5. Details regarding the training parameters for different algorithms can be found in the Appendix We perform evaluation of SEERL in comparison with our three baseline models. It is observed that SEERL outperforms all the baselines and in some environments, it outperforms the state of the art score. Each of the methods is evaluated in the true environment for 100 episodes and the mean average reward is shown in Figure 3 

(f) (a) (b) (c) (d)

5.2. ANALYSIS:

We try to understand why and how SEERL gives such superior performance in comparison to baselines. We analyze the individual performance of the SEERL policies, the dominance among policies in the ensemble, the diversity among the policies, and finally, the comparison between a randomly perturbed model and SEERL.

5.2.1. PERFORMANCE OF INDIVIDUAL POLICIES:

The analysis of the individual policies helps us to understand if the perturbations degrade the model during training. If the perturbations tend to harm the model, the performance of the individual policies should decrease as training progresses. We see in Figure 3 (d) that the performance of the policies does not degrade during training and that new policies may be better than others. However, for the baseline model, the individual policies which have been trained independently, show different performance levels. This could indicate that some policies might have converged to bad local minima while others were able to settle in good ones. The performance of the individually trained models have high variance with respect to each other and supports our motivation of using ensembles instead of a single model. 

5.2.2. DOMINANCE OF POLICIES IN SEERL:

In order to understand if any particular policy is dominating in the ensemble of SEERL, we calculate the number of times the action taken by a policy matches the action taken by the ensemble. We do this evaluation for 500000 samples and observe that no particular policy is dominating in the ensemble, as shown in Figure 3 (b). All of the policies contribute almost equally to the ensemble.

5.2.3. RANDOM PERTURBATION VS. SEERL:

To emphasize that any perturbing the parameters of the model will not lead to better models, we show the comparison between SEERL and a randomly perturbed model in Figure 5 (c). This model has been perturbed with random values at regular intervals similarly to SEERL. The perturbation is done by backpropagating from random values of gradients instead of the true values. We see that doing a single perturbation or, multiple ones sequentially for a small period, does not lead to better performance. With this, we can establish that just perturbation is not sufficient, but directed perturbation along the gradient direction is necessary to obtain a better model. In this experiment, all the hyper-parameters have been kept identical to that used in SEERL and baselines.

5.2.4. DIVERSITY OF POLICIES:

The performance of SEERL depends on the diversity of the individual policies being learned. We have shown earlier, the performance of the individual policies being learned and the diverse nature in their performance. We hope to establish more concretely the diversity of the individual policies by understanding the action distribution across states for each policy. We compute the KL divergence between the policies based on the action distribution across a diverse number of states. The greater the KL divergence between the policies, the more diverse the policies are. From Figure 4 (b), we can observe that the SEERL policies are diverse, and diversity continues to exist as new models are formed. Conversely, for the baseline models (Figure 4 (a) and Figure 4 (c)), the KL divergence between the policies is substantial. This observation can be used to explain why the baseline ensembles failed to perform. The policies did not have much overlap in the action space, and hence ensemble techniques such as majority voting were unable to find a good action. We can, therefore, conclude that SEERL can generate policies with sufficient diversity for a good ensemble.

6. CONCLUSION AND FUTURE WORK:

In this paper, we introduce SEERL, a framework to ensemble multiple policies obtained from a single training instance. Through our experiments, we show that the policies learned at the different local minima are diverse in their performance and hence are well suited for the ensemble. SEERL outperforms three baseline methods in complex environments having discrete and continuous action spaces. We show our results using various reinforcement learning algorithms and therefore show that it is not limited to its performance in any particular setting. Future work will explore how to combine the learned policies during training time as a growing ensemble to stabilize training and increase diversity. The performance of SEERL is affected by the selection of M . For a fixed training budget, if the value of M chosen to be is very large, the performance is seen to degrade. With larger M , the training cycle for each policy is reduced, thereby reducing the chance for the policy to settle to a good local minimum before it is perturbed again. In practice, we find that setting the value of M between 3 to 7 works reasonably well. The maximum leaning rate value influences the performance of the policies and therefore affects the performance of SEERL. It directly impacts the perturbation of the local minima and hence, the diversity of the policies being learned. In practice, we have seen that having a more significant value tends to perform better, owing to the strong perturbation it causes at different local minima leading to reasonably different policies. We have used values ranging between 0.01 to 0.001 throughout our experiments. In order to evaluate the scalability of our framework, we test it across 40 Atari games and analyze the performance. Each environment is trained for 20 million time-steps and evaluated for 100 episodes. The baselines are trained using the hyper-parameters from the original implementation. SEERL is also trained using the same hyper-parameters, but the maximum learning rate chosen is three to seven times the baseline value depending on environments. We outperform all the three baselines across 35 environments and also outperform the state of the art scores in 10 environments. 

:



Figures and Tables:

Figure 1: (a) Cyclical cosine annealing learning rate schedule. α 0 is set at 0.05, number of models M = 5 and training timesteps T = 1000000 (b) State of the art (SOTA) results in SEERL. A-Breakout, B-Skiing,C-Amidar,D-Solaris, E-Pong, F-Freeway,G-Robotank, H-Tutankham, I-Asteroids, J-berzerk, K-centipede, L-crazy climber

)),(DDPG Lillicrap et al. (2017)), (SAC Schulman et al. (2017)) and TRPO(Schulman et al.  (2015a))

Figure 2: Comparison of training performance between SEERL and Baseline. (a) A2C on Breakout (b) DDPG on Half Cheetah (c) TRPO on Half Cheetah (d) SAC on Half Cheetah

Figure 4: (a) Divergence between independently trained policies used in the baseline, B1, for Breakout using A2C. (b) : Divergence between SEERL policies for Breakout using A2C. (c) : Divergence between policies obtained using random perturbations for Breakout using A2C.

Figure 5: (a) Training performance of SEERL as M varies between 3 to 9. (b) Training performance of SEERL as maximum learning rate α 0 varies. (c) Training performance between SEERL and randomly perturbed model, with multiple perturbations in a sequence

Figure 4(d) compares the performance of SEERL with varying M values between 3 and 9 A.1.2 EFFECT OF VARYING MAXIMUM LEARNING RATE VALUE

Figure 4(e) compares the performance of SEERL with different values of α 0 with M = 5 A.2 TRAINING RESULTS ON ATARI ENVIRONMENTS USING A2C

Figure 6: Training performance of SEERL across different Atari games using A2C

Algorithm 1 SEERL Input: Initialize a policy π θ , training timesteps T ,evaluation timesteps T , number of policies M , maximum learning rate α 0 , number of policies to ensemble m, ensemble strategy E, D to store the policies Output: Average reward during evaluation Training

Table content: <table/>

Peer review (iclr2020):
Summary: This paper proposed an ensemble method (SEERL) for model-free RL algorithms. The main advantage of the SEERL is that the training cost is small compared to other ensemble methods with multiple neural networks. SEERL proposed a dynamic learning rate schedule to generate multiple variants of policies during the training of a single instance. The proposed method is applicable to both discrete action space tasks and continuous action space tasks. Detailed comments: *Methodology: It is not clear whether Eq 2 represents the training loss of the proposed method. Eq 3 is an indicator function, which has zero gradients almost everywhere. The only useful term is the KL divergence term if the policies are trained with Eq 2. Does the author mean L(s, a) = L*(s, a) if the *total error* is greater than the threshold? The motivation of using Eq 2 as training loss is not clearly justified or empirically demonstrated in the ablation study. What is the reason for using a threshold to select which policy to train? Is this loss shown to be more effective than just training the policies with the typical actor-critic loss? One of the contributions claimed is the optimization framework for selecting the best policy. However, the ensemble approaches for both discrete action space (Sec 4.3.1) and continuous action space (Sec 4.3.2) are heuristic approaches. It is not clear how to justify those ensemble approaches are optimizing any objectives. Theoretically, the actor-critic/policy gradient approach is an on-policy algorithm, which means the sampled trajectory via behavior policy cannot be readily used for training current learning policy, without using techniques such as importance sampling. It is compatible with SAC since off-policy training can be directly applied, while the discussion on this issue has not been discussed. *Experiments: According to the reported results, the performance of SEERL is volatile. It fluctuates a lot comparing to the baseline approach. The reported results do not seem to be sufficient to support the effectiveness of the proposed method. The baselines such as DDPG/TRPO/A2C are not state-of-the-art in terms of sample-efficiency. The comparison with SAC is valid. *Minor: Eq 5. The definition of advantage function, missing a bracket, etc. Paragraph 1, Section 5, citations of the baselines.