Title: POPULATION-GUIDED PARALLEL POLICY SEARCH FOR REINFORCEMENT LEARNING

Abstract: In this paper, a new population-guided parallel learning scheme is proposed to enhance the performance of off-policy reinforcement learning (RL). In the proposed scheme, multiple identical learners with their own value-functions and policies share a common experience replay buffer, and search a good policy in collaboration with the guidance of the best policy information. The key point is that the information of the best policy is fused in a soft manner by constructing an augmented loss function for policy update to enlarge the overall search region by the multiple learners. The guidance by the previous best policy and the enlarged range enable faster and better policy search. Monotone improvement of the expected cumulative return by the proposed scheme is proved theoretically. Working algorithms are constructed by applying the proposed scheme to the twin delayed deep deterministic (TD3) policy gradient algorithm. Numerical results show that the constructed algorithm outperforms most of the current state-of-the-art RL algorithms, and the gain is significant in the case of sparse reward environment.

1. INTRODUCTION:

RL is an active research field and has been applied successfully to games, simulations, and actual environments. With the success of RL in relatively easy tasks, more challenging tasks such as sparse reward environments (Oh et al. (2018) ; Zheng et al. (2018) ; Burda et al. (2019) ) are emerging, and developing good RL algorithms for such challenging tasks is of great importance from both theoretical and practical perspectives. In this paper, we consider parallel learning, which is an important line of RL research to enhance the learning performance by having multiple learners for the same environment. Parallelism in learning has been investigated widely in distributed RL (Nair et al. (2015) ; Mnih et al. (2016) ; Horgan et al. (2018) ; Barth-Maron et al. (2018) ; Espeholt et al. (2018) ), evolutionary algorithms (Salimans et al. (2017) ; Choromanski et al. (2018) ; Khadka & Tumer (2018) ; Pourchot & Sigaud (2019) ), concurrent RL (Silver et al. (2013) ; Guo & Brunskill (2015) ; Dimakopoulou & Van Roy (2018) ; Dimakopoulou et al. (2018) ) and population-based training (PBT) (Jaderberg et al. (2017; 2018) ; Conti et al. (2018) ). In this paper, in order to enhance the learning performance, we apply parallelism to RL based on a population of policies, but the usage is different from the previous methods.

One of the advantages of using a population is the capability to evaluate policies in the population. Once all policies in the population are evaluated, we can use information of the best policy to enhance the performance. One simple way to exploit the best policy information is that we reset the policy parameter of each learner with that of the best learner at the beginning of the next M time steps; make each learner perform learning from this initial point for the next M time steps; select the best learner again at the end of the next M time steps; and repeat this procedure every M time steps in a similar way that PBT does (Jaderberg et al. (2017) ). We will refer to this method as the resetting method in this paper. However, this resetting method has the problem that the search area covered by all N policies in the population collapses to one point at the time of parameter copying and thus the search area can be narrow around the previous best policy point. To overcome such disadvantage, instead of resetting the policy parameter with the best policy parameter periodically, we propose using the best policy information in a soft manner. In the proposed scheme, the shared best policy information is used only to guide other learners' policies for searching a better policy. The chief periodically determines the best policy among all learners and distributes the best policy parameter to all learners so that the learners search for better policies with the guidance of the previous best policy. The chief also enforces that the N policies are spread in the policy space with a given distance from the previous best policy point so that the search area by all N learners maintains a wide area and does not collapse into a narrow region.

The proposed Population-guided Parallel Policy Search (P3S) learning method can be applied to any off-policy RL algorithms and implementation is easy. Furthermore, monotone improvement of the expected cumulative return by the P3S scheme is theoretically proved. We apply our P3S scheme to the TD3 algorithm, which is a state-of-the-art off-policy algorithm, as our base algorithm. Numerical result shows that the P3S-TD3 algorithm outperforms the baseline algorithms both in the speed of convergence and in the final steady-state performance.

2. BACKGROUND AND RELATED WORKS:

Distributed RL Distributed RL is an efficient way of taking advantage of parallelism to achieve fast training for large complex tasks (Nair et al. (2015) ). Most of the works in distributed RL assume a common structure composed of multiple actors interacting with multiple copies of the same environment and a central system which stores and optimizes the common Q-function parameter or the policy parameter shared by all actors. The focus of distributed RL is to optimize the Q-function parameter or the policy parameter fast by generating more samples for the same wall clock time with multiple actors. For this goal, researchers investigated various techniques for distributed RL, e.g., asynchronous update of parameters (Mnih et al. (2016) ; Babaeizadeh et al. (2017) ), sharing an experience replay buffer (Horgan et al. (2018) ), GPU-based parallel computation (Babaeizadeh et al. (2017) ; Clemente et al. (2017) ), GPU-based simulation (Liang et al. (2018) ) and V-trace in case of on-policy algorithms (Espeholt et al. (2018) ). Distributed RL yields performance improvement in terms of the wall clock time but it does not consider the possible enhancement by interaction among a population of policies of all learners like in PBT or our P3S. The proposed P3S uses a similar structure to that in (Nair et al. (2015) ; Espeholt et al. (2018) ): that is, P3S is composed of multiple learners and a chief. The difference is that each learner in P3S has its own Q or value function parameter and policy parameter, and optimizes the parameters in parallel to search in the policy space.

Population-Based Training:

Parallelism is also exploited in finding optimal parameters and hyperparameters of training algorithms in PBT (Jaderberg et al. (2017; 2018) ; Conti et al. (2018) ). PBT trains neural networks, using a population with different parameters and hyper-parameters in parallel at multiple learners. During the training, in order to take advantage of the population, it evaluates the performance of networks with parameters and hyper-parameters in the population periodically. Then, PBT selects the best hyper-parameters, distributes the best hyper-parameters and the corresponding parameters to other learners, and continues the training of neural networks. Recently, PBT is applied to competitive multi-agent RL (Jaderberg et al. (2018) ) and novelty search algorithms (Conti et al. (2018) ). The proposed P3S uses a population to search a better policy by exploiting the best policy information similarly to PBT, but the way of using the best policy information is different. In P3S, the parameter of the best learner is not copied but used in a soft manner to guide the population for better search in the policy space.

Guided Policy Search Our P3S method is also related to guided policy search (Levine & Koltun (2013) ; Levine et al. (2016) ; Teh et al. (2017) ; Ghosh et al. (2018) ). Teh et al. (2017) proposed a guided policy search method for joint training of multiple tasks in which a common policy is used to guide local policies and the common policy is distilled from the local policies. Here, the local policies' parameters are updated to maximize the performance and minimize the KL divergence between the local policies and the common distilled policy. The proposed P3S is related to guided policy search in the sense that multiple policies are guided by a common policy. However, the difference is that the goal of P3S is not learning multiple tasks but learning optimal parameter for a common task as in PBT. Hence, the guiding policy is not distilled from multiple local policies but chosen as the best performing policy among multiple learners.

Exploiting Best Information Exploiting best information has been considered in the previous works (White & Sofge (1992) ; Oh et al. (2018) ; Gangwani et al. (2019) ). In particular, Oh et al. (2018) ; Gangwani et al. (2019) exploited past good experiences to obtain a better policy, whereas P3S exploits the current good policy among multiple policies to obtain a better policy. The overall structure of the proposed P3S scheme is described in Fig. 1 . We have N identical parallel learners with a shared common experience replay buffer D, and all N identical learners employ a common base algorithm which can be any off-policy RL algorithm. The execution is in parallel. The i-th learner has its own environment E i , which is a copy of the common environment E, and has its own value function (e.g., Q-function) parameter θ i and policy parameter φ i . The i-th learner interacts with the environment copy E i with additional interaction with the chief, as shown in Fig. 1 . At each time step, the i-th learner performs an action a i t to its environment copy E i by using its own policy π φ i , stores its experience (s i t , a i t , r i t , s i t+1 ) to the shared common replay buffer D for all i = 1, 2, • • • , N . Then, each learner updates its value function parameter and policy parameter once by drawing a mini-batch of size B from the shared common replay buffer D by minimizing its own value loss function and policy loss function, respectively.

Due to parallel update of parameters, the policies of all learners compose a population of N different policies. In order to take advantage of this population, we exploit the policy information from the best learner periodically during the training like in PBT (Jaderberg et al. (2017) ). Suppose that the Q-function parameter and policy parameter of each learner are initialized and learning is performed as described above for M time steps. At the end of the M time steps, we determine who is the best learner based on the average of the most recent E r episodic rewards for each learner. Let the index of the best learner be b. Then, the policy parameter information φ b of the best learner can be used to enhance the learning of other learners for the next M time steps. Instead of copying φ b to other learners like in PBT, we propose using the information φ b in a soft manner. That is, during the next M time steps, while we set the loss function L(θ i ) for the Q-function to be the same as the loss L(θ i ) of the base algorithm, we set the loss function L(φ i ) for the policy parameter φ i of the i-th learner as the following augmented version:

EQUATION

where L(φ i ) is the policy loss function of the base algorithm, 1 {•} denotes the indicator function, β(> 0) is a weighting factor, D(π, π ) be some distance measure between two policies π and π .

3.1. THEORETICAL GUARANTEE OF MONOTONE IMPROVEMENT OF EXPECTED CUMULATIVE RETURN:

In this section, we analyze the performance of the proposed soft-fusion approach theoretically and show the effectiveness of the proposed soft-fusion approach. Consider the current update period and its previous update period. Let π old φ i be the policy of the i-th learner at the end of the previous update period and let π φ b be the best policy among all policies π old φ i , i = 1, • • • , N . Now, consider any learner i who is not the best in the previous update period. Let the policy of learner i in the current update period be denoted by π φ i , and let the policy loss function of the base algorithm be denoted as L(π φ i ). In order to analyze the performance, we consider L(π φ i ) in the form of

L(π φ i ) = E s∼D,a∼π φ i (•|s) -Q π old φ i (s, a)

. The reason behind this choice is that most of actorcritic methods update the value (or Q-)function and the policy iteratively. That is, for given π old φ i , the Q-function is first updated to approximate Q π old φ i . Then, with the approximation Q π old φ i , the policy is updated to yield an updated policy π new φ i . This procedure is repeated iteratively. Such loss function is used in many RL algorithms such as SAC and TD3 (Haarnoja et al. (2018); Fujimoto et al. (2018) ). For the distance measure D(π, π ) between two policies π and π , we consider the KL divergence KL(π||π ) for analysis. Then, by eq. ( 1) the augmented loss function for non-best learner i at the current update period is expressed as

L(π φ i ) = E s∼D,a∼π φ i (•|s) -Q π old φ i (s, a) + βE s∼D [KL(π φ i (•|s)||π φ b (•|s))]

(2)

EQUATION

Let π new φ i be a solution that minimizes the augmented loss function eq. ( 3). We assume the following conditions. Assumption 1. For all s,

E a∼π φ b (•|s) Q π old φ i (s, a) ≥ E a∼π old φ i (•|s) Q π old φ i (s, a) . (A1)

Assumption 2. For some ρ, d > 0,

KL π new φ i (•|s)||π φ b (•|s) ≥ max ρ max s KL π new φ i (•|s )||π old φ i (•|s ) , d , ∀s. (A2)

Assumption 1 means that if we draw the first time step action a from π φ b and the following actions from π old φ i , then this yields better performance on average than the case that we draw all actions including the first time step action from π old φ i . This makes sense because of the definition of π φ b . Assumption 2 is about the distance relationship among the policies to ensure a certain level of spreading of the policies for the proposed soft-fusion approach. With the two assumptions above, we have the following theorem regarding the proposed soft-fusion parallel learning scheme: Theorem 1. Under Assumptions 1 and 2, the following inequality holds:

Q π new φ i (s, a) (a) ≥ Q π φ b (s, a) + βE st+1:s∞∼π φ b ∞ k=t+1 γ k-t ∆(s k ) Improvement gap (b) ≥ Q π φ b (s, a) ∀(s, a), ∀i = b.

(4) where

EQUATION

Here, inequality (a) requires Assumption 1 only and inequality (b) requires Assumption 2.

Proof. See Appendix A.

Theorem 1 states that the new solution π new φ i

for the current update period with the augmented loss function yields better performance (in the expected reward sense) than the best policy π φ b of the previous update period for any non-best learner i of the previous update period. Hence, the proposed parallel learning scheme yields monotone improvement of expected cumulative return.

3.2. IMPLEMENTATION:

The proposed P3S method can be applied to any off-policy base RL algorithms whether the base RL algorithms have discrete or continuous actions. For implementation, we assume that the best policy update period consists of M time steps. We determine the best learner at the end of each update period based on the average of the most recent E r episodic rewards of each learner. The key point in implementation is adaptation of β so that the improvement gap 4) becomes non-negative and is maximized for given ρ and d. The gradient of the improvement gap with respect to β is given by ∆  and ∆ is the average (with forgetting) of ∆(s k ) by using samples from

βE st+1:s∞∼π b ∞ k=t+1 γ k-t ∆(s k ) in (

:= E st+1:s∞∼π b ∞ k=t+1 γ k-t ∆(s k ) ,

π b . Hence, if ∆ > 0, i.e., KL π new φ i (•|s)||π φ b (•|s) > max ρ max s KL π new φ i (•|s )||π old φ i (•|s

) , d on average, then β should be increased to maximize the performance gain. Otherwise, β should be decreased. Therefore, we adopt the following adaptation rule for β which is common for all non-best learners:

EQUATION

Here,

D spread = 1 N -1 i∈I -b E s∼D D(π new φ i , π φ b ) is the estimated distance between π new φ i

and π φ b , and

D change = 1 N -1 i∈I -b E s∼D D(π new φ i , π old φ i ) is the estimated distance between π new φ i

and π old φ i averaged over all N -1 non-best learners, where d min and ρ are predetermined hyperparameters. D spread and max{ρ D change , d min } are our practical implementations of the left-hand side (LHS) and the right-hand side (RHS) of eq. (A2), respectively. This adaptation method is similar to that used in PPO (Schulman et al. (2017) ). We applied P3S to TD3 as the base algorithm. The constructed algorithm is named P3S-TD3. The details of TD3 is explained in Appendix G. We used the mean square difference given by D(π(s), π (s)) = 1 2 π(s)π (s) 2 2 as the distance measure between two policies for P3S-TD3. Note that if we consider two deterministic policies as two stochastic policies with same standard deviation, the KL divergence between the two stochastic policies is the same as the mean square difference. For initial exploration P3S-TD3 uses a uniform random policy and does not update all policies over the first T initial time steps. The pseudocode of the P3S-TD3 is given in Appendix H. The implementation code for P3S-TD3 is available at https://github.com/wyjung0625/ p3s. Evaluation method Fig. 3 shows the learning curves over one million time steps for several MuJoCo tasks: Hopper-v1, Walker2d-v1, HalfCheetah-v1, and Ant-v1. In order to have sample-wise fair comparison among the considered algorithms, the time steps in the x-axis in Fig. 3 for P3S-TD3 is the sum of time steps of all N users. For example, in the case that N = 4 and each learner performs 100 time steps in P3S-TD3, the corresponding x-axis value is 400 time steps. Since each learner performs parameter update once with one interaction with environment per each time step in P3S-TD3, the total number of parameter updates at the same x-axis value in Fig. 3 is the same for all algorithms including P3S-TD3, and the total number of interactions with environment at the same x-axis value in Fig. 3 is also the same for all algorithms including P3S-TD3. Here, the performance is obtained through the evaluation method which is similar to those in Haarnoja et al. (2018) ; Fujimoto et al. (2018) . Evaluation of the policies is conducted every R eval = 4000 time steps for all algorithms. At each evaluation instant, the agent (or learner) fixes its policy as the one at the evaluation instant, and interacts with the same environment separate for the evaluation purpose with the fixed policy to obtain 10 episodic rewards. The average of these 10 episodic rewards is the performance at the evaluation instant. In the case of P3S-TD3 and other parallel learning schemes, each of the N learners fixes its policy as the one at the evaluation instant, and interacts with the environment with the fixed policy to obtain 10 episodic rewards. First, the 10 episodic rewards are averaged for each learner and then the maximum of the 10-episode-average rewards of the N learners is taken as the performance at that evaluation instant. We performed this operation for five different random seeds, and the mean and variance of the learning curve are obtained from these five simulations. The policies used for evaluation are stochastic for PPO and ACKTR, and deterministic for the others.

• • • π φ b π φ 1 π φ 2 π φ 3 π φ N d search

Performance on MuJoCo environments In Fig. 3 , it is observed that all baseline algorithms is similar to that in the original papers (Schulman et al. (2017) ; Haarnoja et al. (2018); Fujimoto et al. (2018) ). With this verification, we proceed to compare P3S-TD3 with the baseline algorithms. It is seen that the P3S-TD3 algorithm outperforms the state-of-the-art RL algorithms in terms of both the speed of convergence with respect to time steps and the final steady-state performance (except in Walker2d-v1, the initial convergence is a bit slower than TD3.) Especially, in the cases of Hopper-v1 and Ant-v1, TD3 has large variance and this implies that the performance of TD3 is quite dependent on the initialization and it is not easy for TD3 to escape out of bad local minima resulting from bad initialization in certain environments. However, it is seen that P3S-TD3 yields much smaller variance than TD3. This implies that the wide area search by P3S in the policy space helps the learners escape out of bad local optima.

4.2. COMPARISON WITH OTHER PARALLEL LEARNING SCHEMES AND ABLATION STUDY:

In the previous subsection, we observed that P3S enhances the performance and reduces dependence on initialization as compared to the single learner case with the same complexity. In fact, this should be accomplished by any properly-designed parallel learning scheme. Now, in order to demonstrate the true advantage of P3S, we compare P3S with other parallel learning schemes. P3S has several components to improve the performance based on parallelism: 1) sharing experiences from multiple policies, 2) using the best policy information, and 3) soft fusion of the best policy information for wide search area. We investigated the impact of each component on the performance improvement.

For comparison we considered the following parallel policy search methods gradually incorporating more techniques: 3. Experience-Sharing-Only (ESO) N learners interact with N environment copies and update their own policies using experiences drawn from the shared experience replay buffer.

4. Resetting (Re) At every M time steps, the best policy is determined and all policies are initialized as the best policy, i.e., the best learner's policy parameter is copied to all other learners. The rest of the procedure is the same as experience-sharing-only algorithm.

5. P3S At every M time steps, the best policy information is determined and this policy is used in a soft manner based on the augmented loss function.

Note that the resetting method also exploits the best policy information from N learners. The main difference between P3S and the resetting method is the way the best learner's policy parameter is used. The resetting method initializes all policies with the best policy parameter every M time steps like in PBT (Jaderberg et al. (2017) ), whereas P3S algorithm uses the best learner's policy parameter information determined every M time steps to construct an augmented loss function. For fair comparison, M and M are determined independently and optimally for P3S and Resetting, respectively, since the optimal period can be different for the two methods. We tuned M among {2000, 5000, 10000} (MuJoCo environments) and {10000, 20000, 50000} (Delayed MuJoCo environments) for Re-TD3, whereas M = 250 was used for P3S-TD3. The specific parameters used for Re-TD3 are in Appendix I. Since all N policies collapse to one point in the resetting method at the beginning of each period, we expect that a larger period is required for resetting to have sufficiently spread policies at the end of each best policy selection period. We compared the performance of the aforementioned parallel learning methods combined with TD3 on two classes of tasks; MuJoCo environments, and Delayed sparse reward MuJoCo environments.

Performance on MuJoCo environments:

The upper part of Fig. 4 shows the learning curves of the considered parallel learning methods combined with TD3 for the four tasks (Hopper-v1, Walkerd-v1, HalfCheetah-v1 and Ant v1). It is seen that P3S-TD3 outperforms other parallel methods: DRL-TD3, ESO-TD3 and Re-TD3 except the case that ESO-TD3 or Re-TD3 slightly outperforms P3S-TD3 in Hopper-v1 and Walker2d-v1. In the case of Hopper-v1 and Walker2d-v1, ESO-TD3 has better final (steady-state) performance than all other parallel methods. Note that ESO-TD3 obtains most diverse experiences since the N learners shares the experience replay buffer but there is no interaction among the N learners until the end of training. So, it seems that this diverse experience is beneficial to Hopper-v1 and Walker2d-v1. 2018). Delayed Mu-JoCo environments give non-zero rewards periodically with frequency f reward or only at the end of episodes. That is, in a delayed MuJoCo environment, the environment accumulates rewards given by the corresponding MuJoCo environment while providing zero reward to the agent, and gives the accumulated reward to the agent. We evaluated the performance on the four delayed environments with f reward = 20: Delayed Hopper-v1, Delayed Walker2d-v1, Delayed HalfCheetah-v1 and Delayed Ant-v1.

The lower part of Fig. 4 shows the learning curves of the different parallel learning methods for the four delayed MuJoCo environments. It is seen that P3S outperforms all other considered parallel learning schemes on all environments except on delayed Hopper-v1. It seems that the enforced wide-area policy search with the soft-fusion approach in P3S is beneficial to improve performance in sparse reward environments.

Benifits of P3S Delayed Ant-v1 is a case of sparse reward environment in which P3S shows significant improvement as compared to other parallel schemes. As shown in Fig. 4h , the performance of TD3 drops below zero initially and converges to zero as time goes. Similar behavior is shown for other parallel methods except P3S. This is because in Delayed Ant-v1 with zero padding rewards between actual rewards, initial random actions do not generate significant positive speed to a forward direction, so it does not receive positive rewards but receives negative actual rewards due to the control cost. Once its performance less than 0, learners start learning doing nothing to reach zero reward (no positive reward and no negative reward due to no control cost). Learning beyond this seems difficult without any direction information for parameter update. This is the interpretation of the behavior of other algorithms in Fig. 4h . However, it seems that P3S escapes from this local optimum by following the best policy. This is evident in Fig. 5a , showing that after few time steps, β is increased to follow the best policy more. Note that at the early stage of learning, the performance difference among the learners is large as seen in the large D spread values in Fig. 5b . As time elapses, all learners continue learning, the performance improves, and the spreadness among the learners' policies shrinks. However, the spreadness among the learners' policies is kept at a certain level for wide policy search by d min , as seen in Fig. 5b . Fig. 5c shows the performance of P3S with d min = 0.05 and 0.02. It shows that a wide area policy search is beneficial as compared to a narrow area policy search. However, it may be detrimental to set too large a value for d min due to too large statistics discrepancy among samples from different learners' policies.

5. CONCLUSION:

In this paper, we have proposed a new population-guided parallel learning scheme, P3S, to enhance the performance of off-policy RL. In the proposed P3S scheme, multiple identical learners with their own value-functions and policies sharing a common experience replay buffer search a good policy with the guidance of the best policy information in the previous search interval. The information of the best policy parameter of the previous search interval is fused in a soft manner by constructing an augmented loss function for policy update to enlarge the overall search region by the multiple learners. The guidance by the previous best policy and the enlarged search region by P3S enables faster and better search in the policy space, and monotone improvement of expected cumulative return by P3S is theoretically proved. The P3S-TD3 algorithm constructed by applying the proposed P3S scheme to TD3 outperforms most of the current state-of-the-art RL algorithms. Furthermore, the performance gain by P3S over other parallel learning schemes is significant on harder environments especially on sparse reward environments by searching wide range in policy space.

APPENDIX A. PROOF OF THEOREM 1:

In this section, we prove Theorem 1. Let π old φ i be the policy of the i-th learner at the end of the previous update period and let π φ b be the best policy among all policies π old φ i , i = 1, • • • , N . Now, consider any learner i who is not the best in the previous update period. Let the policy of learner i in the current update period be denoted by π φ i , and let the policy loss function of the base algorithm be denoted as L(π φ i ), given in the form of

EQUATION

The reason behind this choice is that most of actor-critic methods update the value (or Q-)function and the policy iteratively. That is, for given π old φ i , the Q-function is first updated so as to approximate Q π old φ i . Then, with the approximation Q π old φ i the policy is updated to yield an updated policy π new φ i , and this procedure is repeated iteratively. Such loss function is used in many RL algorithms such as SAC and TD3 (Haarnoja et al. (2018); Fujimoto et al. (2018) ). SAC updates its policy by minimizing E s∼D,a∼π (•|s) [-Q π old (s, a) + log π (a|s)] over π . TD3 updates its policy by minimizing

E s∼D,a=π (s) [-Q π old (s, a)].

With the loss function eq. ( 7) and the KL divergence KL(π||π ) as the distance measure D(π, π ) between two policies π and π as stated in the main paper, the augmented loss function for non-best learner i at the current update period is expressed as

EQUATION

EQUATION

Let π new φ i be a solution that minimizes the augmented loss function eq. ( 9).

Assumption 1. For all s,

EQUATION

Assumption 2. For some ρ, d > 0,

EQUATION

For simplicity of notations, we use the following notations from here on.

• π i for π φ i • π i old for π old φ i • π i new for π new φ i • π b for π φ b . • KL max π i new ||π i old for max s KL π new φ i (•|s )||π old φ i (•|s )

A.1. A PRELIMINARY STEP Lemma 1. Let π i new be the solution of the augmented loss function eq. ( 9). Then, with Assumption 1, we have the following:

EQUATION

for all s.

Proof. For all s,

EQUATION

EQUATION

EQUATION

where

Step (a) holds by Assumption 1, (b) holds by the definition of π i new , and (c) holds since KL divergence is always non-negative.

With Lemma 1, we prove the following preliminary result before Theorem 1: Proposition 1. With Assumption 1, the following inequality holds for all s and a:

EQUATION

Proof of Proposition 1. For arbitrary s t and a t ,

EQUATION

EQUATION

EQUATION

EQUATION

≤ . . .

EQUATION

where p(•|s t , a t ) in eq. ( 18) is the environment transition probability, and s t+1 : s t+2 ∼ π i new in eq. ( 20) means that the trajectory from s t+1 to s t+2 is generated by π i new together with the environment transition probability p(•|s t , a t ). (Since the use of p(•|s t , a t ) is obvious, we omitted p(•|s t , a t ) for notational simplicity.) Steps (a) and (b) hold due to Lemma 1.

A.2. PROOF OF THEOREM 1:

Proposition 1 states that for a non-best learner i, the updated policy π i new with the augmented loss function yields better performance than its previous policy π i old , but Theorem 1 states that for a nonbest learner i, the updated policy π i new with the augmented loss function yields better performance than even the previous best policy π b .

To prove Theorem 1, we need further lemmas: We take Definition 1 and Lemma 2 directly from reference (Schulman et al. (2015) ). Definition 1 (From Schulman et al. (2015) ). Consider two policies π and π . The two policies π and π are α-coupled if Pr(a = a ) ≤ α, (a, a ) ∼ (π(•|s), π (•|s)) for all s. Lemma 2 (From Schulman et al. (2015) ). Given α-coupled policies π and π , for all s,

EQUATION

where A π (s, a) is the advantage function. By modifying the result on the state value function in Schulman et al. (2015) , we have the following lemma on the Q-function: Lemma 3. Given two policies π and π , the following equality holds for arbitrary s 0 and a 0 :

EQUATION

where E τ ∼π is expectation over trajectory τ which start from a state s 1 drawn from the transition probability p(•|s 0 , a 0 ) of the environment.

Proof. Note that

EQUATION

EQUATION

Hence, it is sufficient to show the following equality:

EQUATION

) Then, substituting eq. ( 35) into the LHS of eq. ( 34), we have

EQUATION

where eq. ( 37) is valid since

E τ ∼π ∞ t=1 γ t-1 (γV π (s t+1 ) -V π (s t )) = -E s1∼p(•|s0,a0) [V π (s 1 )].

Since the RHS of eq. ( 38) is the same as the RHS of eq. ( 34), the claim holds.

Then, we can prove the following lemma regarding the difference between the Q-functions of two α-coupled policies π and π : Lemma 4. Let π and π be α-coupled policies. Then,

EQUATION

where = max s,a |A π (s, a)| and C > 0

Proof. From Lemma 3, we have

EQUATION

Then, from eq. ( 40) we have

EQUATION

where = max s,a |A π (s, a)| and C > 0. Here, eq. ( 43) is valid due to Lemma 2, eq. ( 45) is valid since Cα

2 + 1/C -2α = C α -1 C

2 ≥ 0, and eq. ( 46) is valid since the sum of two terms is less than or equal to two times the maximum of the two terms.

Up to now, we considered some results valid for given two α-coupled policies π and π . On the other hand, it is shown in Schulman et al. (2015) that for arbitrary policies π and π , if we take α as the maximum (over s) of the total variation divergence max Applying the above facts, we have the following result regarding π i new and π i old : Lemma 5. For some constants ρ, d > 0,

EQUATION

for all s and a, where KL max (π||π ) = max s KL (π(•|s)||π (•|s)).

Proof. For π i new and π i old , take α as the maximum of the total variation divergence between π i new and π i old , i.e., α = max s D T V (π 

EQUATION

by the relationship between the total variation divergence and the KL divergence, we have

EQUATION

Now, substituting π = π i new , π = π i old and α = α into eq. ( 39) and applying eq. ( 49), we have

EQUATION

for some ρ, d > 0. Here, proper scaling due to the introduction of β is absorbed into ρ and d. That is, ρ can be set as 2 γC β(1-γ) and d can be set as

2 γ β(1-γ)C . Then, by Proposition 1, Q π i new (s, a) -Q π i old (s, a) in the LHS of eq. (50) becomes Q π i new (s, a) -Q π i old (s, a) = Q π i new (s, a) -Q π i old (s, a)

. Hence, from this fact and eq. ( 50), we have eq. ( 47). This concludes proof.

Proposition 2. With Assumption 1, we have

EQUATION

where

EQUATION

Proof.

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

EQUATION

where step (a) is valid due to Lemma 5, step (b) is valid due to the definition of π i new , and step (c) is valid due to Proposition 1.

Finally, we prove Theorem 1. Theorem 1. Under Assumptions 1 and 2, the following inequality holds: 

EQUATION

Hence, the second term in ( 68) is non-negative. Therefore, we have

EQUATION

APPENDIX D. COMPARISON TO CEM-TD3

In this section, we compare the performance of TD3 and P3S-TD3 with CEM-TD3 (Pourchot & Sigaud (2019) ), which is a state-of-the-art evolutionary algorithm. CEM-TD3 uses a population to search a better policy as other evolutionary algorithms do. The operation of CEM-TD3 is described as follows:

1. It first samples N policies by drawing policy parameters from a Gaussian distribution.

2. It randomly selects a half of the population. The selected policies and a common Q function are updated based on minibatches drawn from a common replay buffer.

3. Both the updated selected policies and the unselected policies are evaluated and the experiences during the evaluation are stored in the common replay buffer.

4. After evaluation of all N policies, it takes the best N/2 policies and updates the mean and variance of the policy parameter distribution as the mean and variance of the parameters of the best N/2 policies.

5.:

Steps 1 to 4 are iterated until the time steps reach maximum.

For the performance comparision, we used the implementation of CEM-TD3 in the original paper (Pourchot & Sigaud (2019) )1 with the hyper-parameters provided therein. Table 1 shows the steady state performance on MuJoCo and delayed MuJoCo environments. Fig. 7 in the next page shows the learning curves on MuJoCo and delayed MuJoCo environments. It is seen that P3S-TD3 outperforms CEM-TD3 on all environments except delayed HalfCheetah-v1. Notice that P3S-TD3 significantly outperforms CEM-TD3 on delayed Walker2d-v1 and delayed Ant-v1. 

:

EXPERIMENTS4.1 COMPARISON TO BASELINESIn this section, we provide numerical results on performance comparison between the proposed P3S-TD3 algorithm and current state-of-the-art on-policy and off-policy baseline algorithms on several MuJoCo environments(Todorov et al. (2012)). The baseline algorithms are Proximal Policy Optimization (PPO)(Schulman et al. (2017)), Actor Critic using Kronecker-Factored Trust Region (ACKTR)(Wu et al. (2017)), Soft Q-learning (SQL)(Haarnoja et al. (2017)), (clipped double Q) Soft Actor-Critic (SAC)(Haarnoja et al. (2018)), and TD3(Fujimoto et al. (2018)).Hyper-parameter setting All hyper-parameters we used for evaluation are the same as those in the original papers(Schulman et al. (2017);Wu et al. (2017);Haarnoja et al. (2017; 2018);Fujimoto et al. (2018)). Here, we provide the hyper-parameters of the P3S-TD3 algorithm only, while details of the hyper-parameters for TD3 are provided in Appendix I. On top of the hyper-parameters for the base algorithm TD3, we used N = 4 learners for P3S-TD3. To update the best policy and β, the period M = 250 is used. The number of recent episodes E r = 10 was used to determine the best learner b. For the search range, we used the parameter ρ = 2, and tuned d min among d min = {0.02, 0.05} for all environments. Details on d min for each environment is shown in Appendix I. The time steps for initial exploration T initial is set as 250 for Hopper-v1 and Walker2d-v1 and as 2500 for HalfCheetah-v1 and Ant-v1.

The code is available at https://github.com/apourchot/CEM-RL.

Figures and Tables:

Figure 1: The overall structure of P3S

Figure 2: The conceptual search coverage in the policy space by parallel learnersThe update (6) of β is done every M time steps and the updated β is used for the next M time steps. As time steps elapse, β is settled down so that D spread is around d search = max{ρ D change , d min } and this implements Assumption 2 with equality. Hence, the proposed P3S scheme searches a spread area with rough radius d search around the best policy in the policy space, as illustrated in Fig.2. The search radius d search is determined proportionally to D change that represents the speed of change in each learner's policy. In the case of being stuck in local optima, the change D change can be small, making the search area narrow. Hence, we set a minimum search radius d min to encourage escaping out of local optima.

Figure 3: Performance for PPO (red), ACKTR (purple), SQL (brown), (clipped double Q) SAC (orange), TD3 (green), and P3S-TD3 (proposed method, blue) on MuJoCo tasks.

Figure 4: Performance of different parallel learning methods on MuJoCo environments (up), on delayed MuJoCo environments (down)

Figure 5: Ablation study of P3S-TD3 on Delayed Ant-v1: (a) Performance and β (1 seed) with d min = 0.05, (b) Distance measures with d min = 0.05, and (c) Comparison with different d min = 0.02, 0.05

Proof.(From Schulman et al. (2015))|E a∼π [A π (s, a)]| = (a) |E a ∼π [A π (s, a )] -E a∼π [A π (s, a)]| (26) = E (a,a )∼(π,π ) [A π (s, a ) -A π (s, a)] (27) = |Pr(a = a )E (a,a )∼(π,π )|a=a [A π (s, a ) -A π (s, a)] + Pr(a = a )E (a,a )∼(π,π )|a =a [A π (s, a ) -A π (s, a)] |(28) = Pr(a = a )|E (a,a )∼(π,π )|a =a [A π (s, a ) -A π (s, a)] | a) holds since E a∼π [A π (s, a)] = 0 for all s by the property of an advantage function.

s D T V (π(•|s)||π (•|s)) between π(•|s) and π (•|s), then the two policies are α-coupled with the α value of α = max s D T V (π(•|s)||π (•|s)).

a) and (b) hold because of Proposition 2. Assumption 2 ensures ∆(s) = KL π i new (•|s)||π b (•|s)max ρKL max π i new ||π i old , d ≥ 0, ∀s.

Figure 7: Performance of P3S-TD3, CEM-TD3, and TD3

Then, by the result ofSchulman et al. (2015) mentioned in the above, π i new and π i old are α-coupled with α

Table content: <table/>

Proof of Theorem 1: Proof of Theorem 1 is by recursive application of Proposition 2. For arbitrary s t and a t ,Q π i new (s t , a t ) = r(s t , a t ) + γE st+1∼p(•|st,at) E at+1∼π i (s t , a t ) + γE st+1∼p(•|st,at) E at+1∼π b Q π i new (s t+1 , a t+1 ) + β∆(s t+1 ) (64) = E st+1:st+2∼π b r(s t , a t ) + γr(s t+1 , a t+1 ) + γ 2 E at+2∼π i E st+1:st+2∼π b r(s t , a t ) + γr(s t+1 , a t+1 ) + γ 2 E at+2∼π b Q π i new (s t+2 , a t+2 ) + βγ 2 ∆(s t+2 ) + βE st+1:st+2∼π b [γ∆(s t+1 )](66)≥ . . .≥ E st+1:s∞∼π b ∞ k=t γ k-t r(s k , a k ) + βE st+1:s∞∼π b = Q π b (s t , a t ) + βE st+1:s∞∼π b

Table content: <table><tr><td/><td>∞</td><td/></tr><tr><td/><td/><td>γ k-t ∆(s k )</td><td>(67)</td></tr><tr><td/><td>k=t+1</td><td/></tr><tr><td/><td/><td/><td>61)</td></tr><tr><td>where</td><td/><td/></tr><tr><td colspan="3">∆(s) = KL π i new (•|s)||π b (•|s) -max ρKL max π i new ||π i old , d</td><td>(62)</td></tr><tr><td>new</td><td colspan="2">Q π i new (s t+1 , a t+1 )</td><td>(63)</td></tr><tr><td>≥ (a)</td><td/><td/></tr><tr><td/><td>new</td><td>Q π i new (s t+2 , a t+2 )</td></tr><tr><td>+ βE st+1:st+2∼π b [γ∆(s t+1 )]</td><td/><td/><td>(65)</td></tr><tr><td>≥ (b)</td><td/><td/></tr></table>

Steady state performance of P3S-TD3, CEM-TD3, and TD3

Table content: <table><tr><td>Environment</td><td colspan="2">P3S-TD3 CEM-TD3</td><td>TD3</td></tr><tr><td>Hopper-v1</td><td>3705.92</td><td colspan="2">3686.08 2555.85</td></tr><tr><td>Walker2d-v1</td><td>4953.00</td><td colspan="2">4819.40 4455.51</td></tr><tr><td>HalfCheetah-v1</td><td>11961.44</td><td colspan="2">11417.73 9695.92</td></tr><tr><td>Ant-v1</td><td>5339.66</td><td colspan="2">4379.73 3760.50</td></tr><tr><td>Delayed Hopper-v1</td><td>3355.53</td><td colspan="2">3117.20 1866.02</td></tr><tr><td>Delayed Walker2d-v1</td><td>4058.85</td><td colspan="2">1925.63 2016.48</td></tr><tr><td>Delayed HalfCheetah-v1</td><td>5754.80</td><td colspan="2">6389.40 3684.28</td></tr><tr><td>Delayed Ant-v1</td><td>724.50</td><td>70.44</td><td>-7.45</td></tr></table>

Peer review (iclr2020):
The authors propose another method of doing population-based training of RL policies. During the training process, there are N workers running in N copies of the environment, each with different parameter settings for the policies and value networks. Each worker pushes data to a shared replay buffer of experience. The paper claims that a natural approach is to have a chief job periodically poll for the best worker, then replace the weights of each worker with the best one. Whenever this occurs, this reduces the diversity within the population. In its place, the authors propose a soft-update in the chief. At every merging cycle, the chief queries which worker performs best. If that worker is worker B, it emits pi_B*s parameters to each of the other workers. Instead of replacing the parameters exactly, worker i*s loss is then augmented by beta * D(pi_i, pi_B), where D is some distance measure that is measured over states sampled from the replay buffer. The *soft* update encourages individual workers to match pi_B without directly replacing their parameters, which maintains diversity in the population. In this work, pi is always represented by a deterministic policy and D is the mean-squared-error in action space (this is argued as equivalent to the KL divergence between the two policies if the policies were represented by Gaussian with the same, constant standard deviation). The beta parameter is updated online using heuristics based on how D(pi_i, pi_B) compares to D(pi_i, old_pi_i). Using TD3 as a base algorithm, the population-based version performs better, and there are ablations for various parts of the population algorithm. I thought this paper was interesting, but thought it was strange that there were very few comparisons to other population / ensemble-based training methods. In particular they mention the copying problem as a downside of population-based training (PBT), but do not compare against PBT at all. Additionally, my understanding of PBT is that when they replace bad agents with the best agent, they only replace the worst performing agents (not all of them), and they additionally add some random perturbations to their hyperparameter settings. This goes counter to the claim that they collapse the population to a single point- by my reading the exploration step avoids this collapse. An experiment I*d like to see is trying PBT, where different workers do in fact use different hyperparameters. My understanding is that in P3S-TD3 there is a single hyperparameter setting shared across all workers (plus some hyperparameters deciding the soft update). I*d also like to see ablations for the Resetting variant (Re-TD3), where only the bottom half or 2/3rds of the workers are reset. This would give empirical evidence for the *population collapse* intuition - we should expect to see some improvements if we avoid totally collapsing the population, while still copying enough to partially exploit the current best setting. Many inequalities in the paper are argued by compare the expectation of negative Q of one policy to the negative Q of another - I believe the derivations would be much easier to follow if the authors simply multiplied all sides by -1 and adjusted inequalities accordingly. It is much easier to think about Q-value-1 > Q-value-2 rather than -Q-value-1 < -Q-value-2 when trying to interpret what the equation is saying. For related work, papers on evolutionary strategies and the various self-play-in-a-population papers seem relevant, since these often take the form of having each worker i do a different perturbation that is later merged by a chief. In Figure 4 it feels weird that results are the regular Mujoco envs for 2 problems and the delayed envs for the other 2 problems. When looking at the appendix, it*s rather clearly cherry picked to show the best results in favor of PS3-TD3. I would prefer the Delayed MuJoCo experiments be in a separate figure, or to include the TD3/SAC/ACKTR/PPO/etc. results for the delayed envs as well (these don*t appear to be in the appendix) On the theoretical results: the 1st assumption seems very strong. The first assumption argues that pi_B is always 1-step better than pi_old for every state. That assumption already takes you very far towards arguing *updating pi_old to pi_B is good*. The 2nd assumption is more reasonable but I*m confused how rho and d play into the theoretical results. Do they play any role in how much the policy is expected to improve, or do the constants just need to exist? The last comment on the theory side is that I still don*t understand the intuition for why we want to learn beta such that KL(pi_new || pi_b) = max {rho * KL_max(pi_new || pi_old), d} In the practical algorithm, beta is updated online to increase / decrease the importance of the *match pi_B* term if the ratio between the two strays too far from 1 (with the threshold set to [1/1.5, 1.5] in a manner similar to PPO*s approach). But why should it be important for the two values to be close to one another? Let me write out the derivation continuing from Eqn (57) in the appendix. With a substitution that doesn*t use (c) to drop the beta * (KL - KL) term, we get E_{pi_b}[-Q_new] >= E_{pi_new}[-Q_new] + beta * (KL - KL) --> E_{pi_new}[Q_new] >= E_{pi_b}[Q_new] + beta * (KL - KL) Then, in Theorem 1, we recursively apply this inequality, accumulating a number of beta * (KL - KL) terms. In the end we get Q_new >= (discounted sum rewards from pi_b) + (discounted sum of beta * (KL - KL) with expectation over states from pi_b) = Q_pi_b + (sum of beta *(KL - KL) terms) By my reading, shouldn*t this mean we want KL(pi_new || pi_b) - max {rho * KL_max(pi_new || pi_old), d} to be as large as possible, rather than 0? The more positive this term is, the more improvement we get between Q_new and Q_pi_b. -------------------------- Overall, this feels like a good paper, but I*m not too familiar with prior empirical results for population-based RL methods. The ablations suggested that pretty much any reasonable population-based method outperformed using a single worker, and because of this it seems especially important to have ablations to other population-based prior work, rather than just variants of its own method. I would be okay with this paper as-is despite some of its flaws, but think it could be better pending rebuttal. Edit: I have read the author reply and other reviews. I do not plan to change my rating but do think the paper is improved by the added baselines and better explanation of what the beta adaptation rule is doing. I would ask the authors to make sure this description is as clear as possible, as the argued improvement gap seems central to the work.