POPULATION-GUIDED PARALLEL POLICY SEARCH FOR REINFORCEMENT LEARNING
Year: 2020

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.

heading: 1 INTRODUCTION
text: 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,
∗Corresponding author
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 allN 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.

heading: 2 BACKGROUND AND RELATED WORKS
text: 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.

heading: 3 POPULATION-GUIDED PARALLEL POLICY SEARCH
text: The overall structure of the proposed P3S scheme is described in Fig. 1. We haveN 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 ait to its environment copy E i by using its own policy πφi , stores its experience (sit, 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 ofN 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 Er 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:
L̃(φi) = L(φi) + 1{i 6=b}βEs∼D [ D(πφi , πφb) ] (1)
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 π′.

heading: 3.1 THEORETICAL GUARANTEE OF MONOTONE IMPROVEMENT OF EXPECTED CUMULATIVE RETURN
text: 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) = Es∼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) = Es∼D,a∼πφi (·|s) [ −Qπ old φi (s, a) ] + βEs∼D[KL(πφi(·|s)||πφb(·|s))] (2)
= Es∼D [ Ea∼πφi (·|s) [ −Qπ old φi (s, a) + β log πφi(a|s) πφb(a|s) ]] (3)
Let πnewφi be a solution that minimizes the augmented loss function eq. (3). We assume the following conditions. Assumption 1. For all s,
Ea∼π φb (·|s)
[ Q πold φi (s, a) ] ≥ Ea∼π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) + βEst+1:s∞∼πφb [ ∞∑ k=t+1 γk−t∆(sk) ] ︸ ︷︷ ︸
Improvement gap
(b) ≥ Qπφb (s, a) ∀(s, a), ∀i 6= b.
(4) where
∆(s) = KL ( πnewφi (·|s)||πφb(·|s) ) −max { ρmax s′ KL ( πnewφi (·|s′)||πoldφi (·|s′) ) , d } . (5)
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.

heading: 3.2 IMPLEMENTATION
text: 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 Er episodic rewards of each learner. The key point in implementation is adaptation of β so that the improvement gap βEst+1:s∞∼πb [∑∞ k=t+1 γ k−t∆(sk) ] in (4) becomes non-negative and is maximized for given ρ and d. The gradient of the improvement gap with respect to β is given by ∆̄ := Est+1:s∞∼πb [∑∞ k=t+1 γ k−t∆(sk) ] , and ∆̄ is the average (with forgetting) of ∆(sk) by using samples from πb. Hence, if ∆̄ > 0, i.e.,
KL ( πnewφi (·|s)||πφb(·|s) ) > max { ρmaxs′ 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:
β = { β ← 2β if D̂spread > max{ρD̂change, dmin} × 1.5 β ← β/2 if D̂spread < max{ρD̂change, dmin}/1.5 . (6)
Here, D̂spread = 1N−1 ∑ i∈I−b Es∼D [ D(πnewφi , πφb) ] is the estimated distance between πnewφi and
πφb , and D̂change = 1N−1 ∑ i∈I−b Es∼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 dmin and ρ are predetermined hyperparameters. D̂spread and max{ρD̂change, dmin} 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)).
The 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 dsearch = max{ρD̂change, dmin} and this implements Assumption 2 with equality. Hence, the proposed P3S scheme searches a spread area with rough radius dsearch around the best policy in the policy space, as illustrated in Fig. 2. The search radius dsearch 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 dmin to encourage escaping out of local optima.
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)) = 12 ‖π(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 Tinitial 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.

heading: 4 EXPERIMENTS

heading: 4.1 COMPARISON TO BASELINES
text: In 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 Er = 10 was used to determine the best learner b. For the search range, we used the parameter ρ = 2, and tuned dmin among dmin = {0.02, 0.05} for all environments. Details on dmin for each environment is shown in Appendix I. The time steps for initial exploration Tinitial is set as 250 for Hopper-v1 and Walker2dv1 and as 2500 for HalfCheetah-v1 and Ant-v1.
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 Reval = 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.
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.

heading: 4.2 COMPARISON WITH OTHER PARALLEL LEARNING SCHEMES AND ABLATION STUDY
text: 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:
1. Original Algorithm The original algorithm (TD3) with one learner
2. Distributed RL (DRL) N actors obtain samples from N environment copies. The common policy and the experience replay buffer are shared by all N actors.
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: DRLTD3, ESO-TD3 and Re-TD3 except the case that ESO-TD3 or Re-TD3 slightly outperforms P3STD3 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.
Performance on Delayed MuJoCo environments Sparse reward environments especially require more search to obtain a good policy. To see the performance of P3S in sparse reward environments, we performed experiments on Delayed MuJoCo environments. Delayed MuJoCo environments are reward-sparsified versions of MuJoCo environments and used in Zheng et al. (2018). Delayed MuJoCo environments give non-zero rewards periodically with frequency freward 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 freward = 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 dmin, as seen in Fig. 5b. Fig. 5c shows the performance of P3S with dmin = 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 dmin due to too large statistics discrepancy among samples from different learners’ policies.

heading: 5 CONCLUSION
text: 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.

heading: ACKNOWLEDGMENTS
text: This work was supported in part by the ICT R&D program of MSIP/IITP (2016-0-00563, Research on Adaptive Machine Learning Technology Development for Intelligent Autonomous Digital Companion) and in part by the National Research Foundation of Korea(NRF) grant funded by the Korea government(Ministry of Science and ICT) (NRF2017R1E1A1A03070788).

heading: APPENDIX A. PROOF OF THEOREM 1
text: 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
L(πφi) = Es∼D,a∼πφi (·|s) [ −Qπoldφi (s, a) ] . (7)
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 Es∼D,a∼π′(·|s) [−Qπold(s, a) + log π′(a|s)] over π′. TD3 updates its policy by minimizing Es∼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
L̃(πφi) = Es∼D,a∼πφi (·|s) [ −Qπ old φi (s, a) ] + βEs∼D[KL(πφi(·|s)||πφb(·|s))] (8)
= Es∼D [ Ea∼πφi (·|s) [ −Qπ old φi (s, a) + β log πφi(a|s) πφb(a|s) ]] (9)
Let πnewφi be a solution that minimizes the augmented loss function eq. (9).
Assumption 1. For all s,
Ea∼π φb (·|s)
[ Q πold φi (s, a) ] ≥ Ea∼πold
φi (·|s)
[ Q πold φi (s, a) ] . (10)
Assumption 2. For some ρ, d > 0, KL ( πnewφi (·|s)||πφb(·|s) ) ≥ max { ρmax s′ KL ( πnewφi (·|s′)||πoldφi (·|s′) ) , d } , ∀s. (11)
For simplicity of notations, we use the following notations from here on.
• πi for πφi • πiold for πoldφi • πinew for πnewφi • πb for πφb .
• KLmax ( πinew||πiold ) for maxs′ KL ( πnewφi (·|s′)||πoldφi (·|s′) ) A.1. A PRELIMINARY STEP
Lemma 1. Let πinew be the solution of the augmented loss function eq. (9). Then, with Assumption 1, we have the following:
Ea∼πinew(·|s) [ Qπ i old(s, a) ] ≥ Ea∼πiold(·|s) [ Qπ i old(s, a) ] (12)
for all s.
Proof. For all s, Ea∼πiold(·|s) [ −Qπiold(s, a) ] ≥ (a) Ea∼πb(·|s) [ −Qπiold(s, a) ] (13)
= Ea∼πb(·|s) [ −Qπiold(s, a) + β log π
b(a|s) πb(a|s)
] (14)
≥ (b)
Ea∼πinew(·|s) [ −Qπiold(s, a) + β log π i new(a|s) πb(a|s) ] (15)
≥ (c)
Ea∼πinew(·|s) [ −Qπiold(s, a) ] , (16)
where Step (a) holds by Assumption 1, (b) holds by the definition of πinew, 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:
Qπ i new(s, a) ≥ Qπiold(s, a). (17)
Proof of Proposition 1. For arbitrary st and at,
Qπ i old(st, at) = r(st, at) + γEst+1∼p(·|st,at) [ Eat+1∼πiold [ Qπ i old(st+1, at+1) ]] (18)
≤ (a)
r(st, at) + γEst+1∼p(·|st,at) [ Eat+1∼πinew [ Qπ i old(st+1, at+1) ]] (19)
= Est+1:st+2∼πinew [ r(st, at) + γr(st+1, at+1) + γ 2Eat+2∼πiold [ Qπ i old(st+2, at+2) ]] (20)
≤ (b)
Est+1:st+2∼πinew [ r(st, at) + γr(st+1, at+1) + γ 2Eat+2∼πinew [ Qπ i old(st+2, at+2) ]] (21)
≤ . . . (22)
≤ Est+1:s∞∼πinew [ ∞∑ k=t γk−tr(sk, ak) ] (23)
= Qπ i new(st, at), (24)
where p(·|st, at) in eq. (18) is the environment transition probability, and st+1 : st+2 ∼ πinew in eq. (20) means that the trajectory from st+1 to st+2 is generated by πinew together with the environment transition probability p(·|st, at). (Since the use of p(·|st, at) is obvious, we omitted p(·|st, at) 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 πinew with the augmented loss function yields better performance than its previous policy πiold, but Theorem 1 states that for a nonbest learner i, the updated policy πinew 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 6= a′) ≤ α, (a, a′) ∼ (π(·|s), π′(·|s)) for all s. Lemma 2 (From Schulman et al. (2015)). Given α-coupled policies π and π′, for all s,
|Ea∼π′ [Aπ(s, a)]| ≤ 2αmax s,a |Aπ(s, a)|, (25)
where Aπ(s, a) is the advantage function.
Proof. (From Schulman et al. (2015))
|Ea∼π′ [Aπ(s, a)]| = (a) |Ea′∼π′ [Aπ(s, a′)]− Ea∼π [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 6= a′)E(a,a′)∼(π,π′)|a6=a′ [Aπ(s, a′)−Aπ(s, a)] | (28) = Pr(a 6= a′)|E(a,a′)∼(π,π′)|a 6=a′ [Aπ(s, a′)−Aπ(s, a)] | (29) ≤ 2αmax
s,a |Aπ(s, a)| , (30)
where Step (a) holds since Ea∼π[Aπ(s, a)] = 0 for all s by the property of an 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 s0 and a0:
Qπ ′ (s0, a0) = Q π(s0, a0) + γEτ∼π′ [ ∞∑ t=1 γt−1Aπ(st, at) ] , (31)
where Eτ∼π′ is expectation over trajectory τ which start from a state s1 drawn from the transition probability p(·|s0, a0) of the environment.
Proof. Note that
Qπ(s0, a0) = r0 + γEs1∼p(·|s0,a0) [V π(s1)] (32)
Qπ ′ (s0, a0) = r0 + γEs1∼p(·|s0,a0) [ V π ′ (s1) ] (33)
Hence, it is sufficient to show the following equality: Eτ∼π′ [ ∞∑ t=1 γt−1Aπ(st, at) ] = Es1∼p(·|s0,a0) [ V π ′ (s1) ] − Es1∼p(·|s0,a0) [V π(s1)] (34)
Note that Aπ(st, at) = Est+1∼p(·|st,at) [rt + γV
π(st+1)− V π(st)] (35) Then, substituting eq. (35) into the LHS of eq. (34), we have
Eτ∼π′ [ ∞∑ t=1 γt−1Aπ(st, at) ] = Eτ∼π′ [ ∞∑ t=1 γt−1 (rt + γV π(st+1)− V π(st)) ] (36)
= Eτ∼π′ [ ∞∑ t=1 γt−1rt ] − Es1∼p(·|s0,a0) [V π(s1)] (37)
= Es1∼p(·|s0,a0) [ V π ′ (s1) ] − Es1∼p(·|s0,a0) [V π(s1)] , (38)
where eq. (37) is valid since Eτ∼π′ [∑∞ t=1 γ t−1 (γV π(st+1)− V π(st)) ] = −Es1∼p(·|s0,a0) [V π(s1)]. 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,∣∣∣Qπ(s, a)−Qπ′(s, a)∣∣∣ ≤ 2 γ 1− γ max { Cα2, 1/C } , (39)
where = maxs,a |Aπ(s, a)| and C > 0
Proof. From Lemma 3, we have
Qπ ′ (s0, a0)−Qπ(s0, a0) = γEτ∼π′ [ ∞∑ t=1 γt−1Aπ(st, at) ] . (40)
Then, from eq. (40) we have∣∣∣Qπ′(s0, a0)−Qπ(s0, a0)∣∣∣ = ∣∣∣∣∣γEτ∼π′ [ ∞∑ t=1 γt−1Aπ(st, at) ]∣∣∣∣∣ (41) ≤ γ
∞∑ t=1 γt−1 |Est,at∼π′ [Aπ(st, at)]| (42)
≤ γ ∞∑ t=1 γt−12αmax s,a |Aπ(s, a)| (43) = γ
1− γ 2α (44)
≤ γ 1− γ
( Cα2 + 1/C ) (45)
≤ γ 1− γ 2 max
{ Cα2, 1/C } , (46)
where = maxs,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 ( α− 1C )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 maxsDTV (π(·|s)||π′(·|s)) between π(·|s) and π′(·|s), then the two policies are α-coupled with the α value of α = maxsDTV (π(·|s)||π′(·|s)). Applying the above facts, we have the following result regarding πinew and π i old: Lemma 5. For some constants ρ, d > 0,
Qπ i new(s, a) ≤ Qπiold(s, a) + βmax { ρKLmax ( πinew||πiold ) , d }
(47)
for all s and a, where KLmax (π||π′) = maxs KL (π(·|s)||π′(·|s)).
Proof. For πinew and π i old, take α as the maximum of the total variation divergence between π i new and πiold, i.e., α = maxsDTV (π i new(·|s)||πiold(·|s)). Let this α value be denoted by α̂. Then, by the result of Schulman et al. (2015) mentioned in the above, πinew and π i old are α̂-coupled with α̂ = maxsDTV (π i new(·|s)||πiold(·|s)). Since DTV (π i new(·|s)||πiold(·|s))2 ≤ KL(πinew(·|s)||πiold(·|s)), (48)
by the relationship between the total variation divergence and the KL divergence, we have
α̂2 ≤ max s KL(πinew(·|s)||πiold(·|s)). (49)
Now, substituting π = πinew, π ′ = πiold and α = α̂ into eq. (39) and applying eq. (49), we have∣∣∣Qπinew(s, a)−Qπiold(s, a)∣∣∣ ≤ βmax{ρKLmax (πinew||πiold) , d} (50)
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πinew(s, a)−Qπiold(s, a)∣∣∣ in the LHS of eq. (50) becomes ∣∣∣Qπinew(s, a)−Qπiold(s, a)∣∣∣ =
Qπ i new(s, a) − Qπiold(s, a). Hence, from this fact and eq. (50), we have eq. (47). This concludes proof.
Proposition 2. With Assumption 1, we have Ea∼πinew(·|s) [ Qπ i new(s, a) ] ≥ Ea∼πb(·|s) [ Qπ i new(s, a) ] + β∆(s). (51)
where ∆(s) = [ KL ( πinew(·|s)||πb(·|s) ) −max { ρKLmax ( πinew||πiold ) , d }]
(52)
Proof. Ea∼πb(·|s) [ −Qπinew(s, a) ] (53)
≥ (a)
Ea∼πb(·|s) [ −Qπiold(s, a) ] − βmax { ρKLmax ( πinew||πiold ) , d }
(54)
= Ea∼πb(·|s) [ −Qπiold(s, a) + β log π
b(a|s) πb(a|s)
] − βmax { ρKLmax ( πinew||πiold ) , d }
(55)
≥ (b)
Ea∼πinew(·|s) [ −Qπold(s, a) + β log π i new(a|s) πb(a|s) ] − βmax { ρKLmax ( πinew||πiold ) , d }
(56)
= Ea∼πinew(·|s) [−Q πold(s, a)] + βKL ( πinew(·|s)||πb(·|s) ) − βmax { ρKLmax ( πinew||πiold ) , d }
(57) = Ea∼πinew(·|s) [ −Qπiold(s, a) ] + β [ KL ( πinew(·|s)||πb(·|s) ) −max { ρKLmax ( πinew||πiold ) , d }]
(58) = Ea∼πinew(·|s) [ −Qπiold(s, a) ] + β∆(s) (59)
≥ (c)
Ea∼πinew(·|s) [ −Qπinew(s, a) ] + β∆(s), (60)
where step (a) is valid due to Lemma 5, step (b) is valid due to the definition of πinew, 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:
Qπ i new(s, a) ≥ Qπb(s, a) + βEst+1:s∞∼πb [ ∞∑ k=t+1 γk−t∆(sk) ] ≥ Qπb(s, a), ∀(s, a),∀i 6= b.
(61) where ∆(s) = [ KL ( πinew(·|s)||πb(·|s) ) −max { ρKLmax ( πinew||πiold ) , d }] (62)
Proof of Theorem 1: Proof of Theorem 1 is by recursive application of Proposition 2. For arbitrary st and at,
Qπ i new(st, at) = r(st, at) + γEst+1∼p(·|st,at) [ Eat+1∼πinew [ Qπ i new(st+1, at+1) ]] (63)
≥ (a)
r(st, at) + γEst+1∼p(·|st,at) [ Eat+1∼πb [ Qπ i new(st+1, at+1) ] + β∆(st+1) ] (64)
= Est+1:st+2∼πb [ r(st, at) + γr(st+1, at+1) + γ 2Eat+2∼πinew [ Qπ i new(st+2, at+2) ]] + βEst+1:st+2∼πb [γ∆(st+1)] (65)
≥ (b)
Est+1:st+2∼πb [ r(st, at) + γr(st+1, at+1) + γ 2Eat+2∼πb [ Qπ i new(st+2, at+2) ] + βγ2∆(st+2) ] + βEst+1:st+2∼πb [γ∆(st+1)] (66)
≥ . . . ≥ Est+1:s∞∼πb [ ∞∑ k=t γk−tr(sk, ak) ] + βEst+1:s∞∼πb [ ∞∑ k=t+1 γk−t∆(sk) ] (67)
= Qπ b
(st, at) + βEst+1:s∞∼πb [ ∞∑ k=t+1 γk−t∆(sk) ] (68)
where steps (a) and (b) hold because of Proposition 2. Assumption 2 ensures ∆(s) = [ KL ( πinew(·|s)||πb(·|s) ) −max { ρKLmax ( πinew||πiold ) , d }] ≥ 0, ∀s. (69)
Hence, the second term in (68) is non-negative. Therefore, we have
Qπ i new(st, at) ≥ Qπ b (st, at) + βEst+1:s∞∼πb [ ∞∑ k=t+1 γk−t∆(sk) ] (70)
≥ Qπb(st, at) (71)
APPENDIX B. INTUITION OF THE IMPLEMENTATION OF β ADAPTATION
Due to Theorem 1, we have
Qπ i new(st, at) ≥ Qπ b (st, at) + βEst+1:s∞∼πb [ ∞∑ k=t+1 γk−t∆(sk) ] ︸ ︷︷ ︸
Improvement gap
(72)
where ∆(s) = [ KL ( πinew(·|s)||πb(·|s) ) −max { ρKLmax ( πinew||πiold ) , d }] ≥ 0, ∀s. (73)
In deriving eqs. (72) and (73), we only used Assumption 1. When we have Assumption 2, the improvement gap term in (72) becomes non-negative and we have
Qπ i new(st, at) ≥ Qπ b (st, at) (74)
as desired. However, in practice, Assumption 2 should be implemented so that the improvement gap term becomes non-negative and we have the desired result (74). The implementation of the condition is through adaptation of β. We adapt β to maximize the improvement gap βEst+1:s∞∼πb [∑∞ k=t+1 γ k−t∆(sk) ]
in (72) for given ρ and d. Let us denote Est+1:s∞∼πb [∑∞ k=t+1 γ k−t∆(sk) ]
by ∆̄. Then, the improvement gap is given by β∆̄. Note that ∆̄ is the average (with forgetting) of ∆(sk) by using samples from πb. The gradient of the improvement gap with respect to β is given by ∇β(β∆̄) = ∆̄. (75) Thus, if ∆̄ > 0, i.e., KL ( πinew(·|s)||πb(·|s) ) > max { ρKLmax ( πinew||πiold ) , d }
on average, then β should be increased to maximize the performance gain. On the other hand, if ∆̄ < 0, i.e., KL ( πinew(·|s)||πb(·|s) ) ≤ max { ρKLmax ( πinew||πiold ) , d }
on average, then β should be decreased. Therefore, we adapt β as follows:
β = { β ← 2β if D̂spread > max{ρD̂change, dmin} × 1.5 β ← β/2 if D̂spread < max{ρD̂change, dmin}/1.5 . (76)
where D̂spread and D̂change are implementations of KL ( πinew(·|s)||πb(·|s) ) and
KLmax ( πinew||πiold ) , respectively.

heading: APPENDIX C. COMPARISON TO BASELINES ON DELAYED MUJOCO ENVIRONMENTS
text: In this section, we provide the learning curves of the state-of-the-art single-learner baselines on delayed MuJoCo environments. Fig. 6 shows the learning curves of P3S-TD3 algorithm and the single-learner baselines on the four delayed MuJoCo environments: Delayed Hopper-v1, Delayed Walker2d-v1, Delayed HalfCheetah-v1, and Delayed Ant-v1. It is observed that in the delayed Antv1 environment, ACKTR outperforms the P3S-TD3 algorithm. It is also observed that P3S-TD3 significantly outperforms all baselines on all other environments than the delayed Ant-v1 environment.

heading: APPENDIX D. COMPARISON TO CEM-TD3
text: 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 expe-
riences 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.

heading: APPENDIX E. COMPARISON TO METHOD USING CENTER POLICY
text: In this section, we consider a variant of the proposed P3S-TD3 algorithm, named Center-TD3. This variant uses a center policy like in Distral (Teh et al. (2017)) and Divide-and-Conquer (Ghosh et al. (2018)). Center-TD3 has N policies and a center policy πc in addition. The value and policy parameter update procedure is the same as the original TD3 algorithm but the loss functions are newly defined. That is, the Q function loss is the same as the original TD3 algorithm, but the parameters of the N policies are updated based on the following loss:
L̃(φi) = Ês∼D [ −Qθi1(s, πφi(s)) + β
2 ∥∥πφi(s)− πφc(s)∥∥22] . (77) The parameter loss function of Center-TD3 is obtained by replacing the best policy with the center policy in the parameter loss function of P3S-TD3. The center policy is updated in every M time steps to the direction of minimizing the following loss
L̃(φc) = Ês∼D
[ β
2 N∑ i=1 ∥∥πφi(s)− πφc(s)∥∥22 ] . (78)
Center-TD3 follows the spirit of Distral (Teh et al. (2017)) and Divide-and-Conquer (Ghosh et al. (2018)) algorithms.
We tuned and selected the hyper-parameters for Center-TD3 from the sets β ∈ {1, 10} and M ∈ {2, 20, 40, 100, 200, 500}. We then measured the performance of Center-TD3 by using the selected hyper-parameter β = 1, M = 40. Fig. 8 in the next page and Table 2 show the learning curves and the steady-state performance on MuJoCo and delayed MuJoCo environments, respectively. It is seen that P3S-TD3 outperforms Center-TD3 on all environments except Delayed HalfCheetah-v1.

heading: APPENDIX F. RESULT ON SWIMMER-V1
text: Khadka & Tumer (2018); Pourchot & Sigaud (2019) noticed that most deep RL methods suffer from a deceptive gradient problem on the Swimmer-v1 task, and most RL methods could not learn effectively on the Swimmer-v1 task. Unfortunately, we observed that the proposed P3S-TD3 algorithm could not solve the deceptive gradient problem in the Swimmer-v1 task either. Fig. 9 shows the learning curves of P3S-TD3 and TD3 algorithm. In Khadka & Tumer (2018), the authors proposed an effective evolutionary algorithm named ERL to solve the deceptive gradient problem on the Swimmer-v1 task, yielding the good performance on Swimmer-v1, as shown in Fig. 9. P3S-TD3 falls short of the performance of ERL on Swimmer-v1. However, it is known that CEM-TD3 discussed in Appendix D outperforms ERL on other tasks (Pourchot & Sigaud (2019)). Furthermore, we observed that P3S-TD3 outperforms CEM-TD3 on most environments in Appendix D.

heading: APPENDIX G. THE TWIN DELAYED DEEP DETERMINISTIC POLICY GRADIENT (TD3) ALGORITHM
text: The TD3 algorithm is a current state-of-the-art off-policy algorithm and is a variant of the deep deterministic policy gradient (DDPG) algorithm (Lillicrap et al. (2015)). The TD3 algorithm tries to resolve two problems in typical actor-critic algorithms: 1) overestimation bias and 2) high variance in the approximation of the Q-function. In order to reduce the bias, the TD3 considers two Q-functions and uses the minimum of the two Q-function values to compute the target value, while in order to reduce the variance in the gradient, the policy is updated less frequently than the Qfunctions. Specifically, letQθ1 ,Qθ2 and πφ be two current Q-functions and the current deterministic policy, respectively, and let Qθ′1 , Qθ′2 and πφ′ be the target networks of Qθ1 , Qθ2 and πφ, respectively. The target networks are initialized by the same networks as the current networks. At time step t, the TD3 algorithm takes an action at with exploration noise : at = πφ(st) + , where is zero-mean Gaussian noise with variance σ2, i.e., ∼ N (0, σ2). Then, the environment returns reward rt and the state is switched to st+1. The TD3 algorithm stores the experience (st, at, rt, st+1) at the experience replay buffer D. After storing the experience, the Q-function parameters θ1 and θ2 are updated by gradient descent of the following loss functions:
L(θj) = Ê(s,a,r,s′)∼D [ (y −Qθj (s, a))2 ] , j = 1, 2 (79)
where Ê(s,a,r,s′)∼D denotes the sample expectation with an uniform random mini-batch of size B drawn from the replay buffer D, and the target value y is given by
y = r + γ min j=1,2
Qθ′j (s ′, πφ′(s ′) + ), ∼ clip(N (0, σ̃2),−c, c). (80)
Here, for the computation of the target value, the minimum of the two target Q-functions is used to reduce the bias. The procedure of action taking and gradient descent for θ1 and θ2 are repeated for d times (d = 2), and then the policy and target networks are updated. The policy parameter φ is updated by gradient descent by minimizing the loss function for φ:
L(φ) = −Ês∼D [Qθ1(s, πφ(s))] , (81) and the target network parameters θ′j and φ ′ are updated as
θ′j ← (1− τ)θ′j + τθj φ′ ← (1− τ)φ′ + τφ. (82) The networks are trained until the number of time steps reaches a predefined maximum.

heading: APPENDIX H. PSEUDOCODE OF THE P3S-TD3 ALGORITHM
text: Algorithm 1 The Population-Guided Parallel Policy Search TD3 (P3S-TD3) Algorithm Require: N : number of learners, Tinitial: initial exploration time steps, T : maximum time steps,
M : the best-policy update period,B: size of mini-batch, d: update interval for policy and target networks.
1: Initialize φ1 = · · · = φN = φb, θ1j = · · · = θNj , j = 1, 2, randomly. 2: Initialize β = 1, t = 0 3: while t < T do 4: t← t+ 1 (one time step) 5: for i = 1, 2, · · · , N in parallel do 6: if t < Tinitial then 7: Take a uniform random action ait to environment copy E i 8: else 9: Take an action ait = π i ( sit )
+ , ∼ N (0, σ2) to environment copy E i 10: end if 11: Store experience (sit, a i t, r i t, s i t+1) to the shared common experience replay D 12: end for 13: if t < Tinitial then 14: continue (i.e., go to the beginning of the while loop) 15: end if 16: for i = 1, 2, · · · , N in parallel do 17: Sample a mini-batch B = {(stl , atl , rtl , stl+1)}l=1,...,B from D 18: Update θij , j = 1, 2, by gradient descent for minimizing L̃(θ i j) in (83) with B 19: if t ≡ 0(mod d) then 20: Update φi by gradient descent for minimizing L̃(φi) in (84) with B 21: Update the target networks: (θij)
′ ← (1− τ)(θij)′ + τθij , (φi)′ ← (1− τ)(φi)′ + τφi 22: end if 23: end for 24: if t ≡ 0(mod M) then 25: Select the best learner b 26: Adapt β 27: end if 28: end while
In P3S-TD3, the i-th learner has its own parameters θi1, θ i 2, and φ i for its two Q-functions and policy. Furthermore, it has (θi1) ′, (θi2) ′, and (φi)′ which are the parameters of the corresponding target networks. For the distance measure between two policies, we use the mean square difference, given by D(π(s), π̃(s)) = 12 ‖π(s)− π̃(s)‖ 2 2. For the i-th learner, as in TD3, the parameters θ i j , j = 1, 2 are updated every time step by minimizing
L̃(θij) = Ê(s,a,r,s′)∼D [ (y −Qθij (s, a)) 2 ]
(83)
where y = r + γminj=1,2Q(θij)′(s ′, π(φi)′(s ′) + ), ∼ clip(N (0, σ̃2),−c, c). The parameter φi is updated every d time steps by minimizing the following augmented loss function:
L̃(φi) = Ês∼D [ −Qθi1(s, πφi(s)) + 1{i 6=b} β
2 ∥∥πφi(s)− πφb(s)∥∥22] . (84) For the first Tinitial time steps for initial exploration we use a random policy and do not update all policies over the initial exploration period. With these loss functions, the reference policy, and the initial exploration policy, all procedure is the same as the general P3S procedure described in Section 3. The pseudocode of the P3S-TD3 algorithm is shown above.
APPENDIX I. HYPER-PARAMETERS
TD3 The networks for two Q-functions and the policy have 2 hidden layers. The first and second layers have sizes 400 and 300, respectively. The non-linearity function of the hidden layers is ReLU, and the activation functions of the last layers of the Q-functions and the policy are linear and hyperbolic tangent, respectively. We used the Adam optimizer with learning rate 10−3, discount factor γ = 0.99, target smoothing factor τ = 5 × 10−3, the period d = 2 for updating the policy. The experience replay buffer size is 106, and the mini-batch size B is 100. The standard deviation for exploration noise σ and target noise σ̃ are 0.1 and 0.2, respectively, and the noise clipping factor c is 0.5.
P3S-TD3 In addition to the hyper-parameters for TD3, we used N = 4 learners, the period M = 250 of updating the best policy and β, the number of recent episodes Er = 10 for determining the best learner b. The parameter dmin was chosen among {0.02, 0.05} for each environment, and the chosen parameter was 0.02 (Walker2d-v1, Ant-v1, Delayed Hopper-v1, Delayed Walker2d-v1, Delayed HalfCheetah-v1), and 0.05 (Hopper-v1, HalfCheetah-v1, Delayed Ant-v1). The parameter ρ for the exploration range was 2 for all environments. The time steps for initial exploration Tinitial was set as 250 for Hopper-v1 and Walker2d-v1 and as 2500 for HalfCheetah-v1 and Ant-v1.
Re-TD3 The period M ′ was chosen among {2000, 5000, 10000} (MuJoCo environments) and {10000, 20000, 50000} (Delayed MuJoCo environments) by tuning for each environment. The chosen period M ′ was 2000 (Ant-v1), 5000 (Hopper-v1, Walker2d-v1, HalfCheetah-v1), 10000 (Delayed HalfCheetah-v1, Delayed Ant-v1), and 20000 (Delayed Hopper-v1, Delayed Walker2d-v1).

Review summaries:
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.

This work presents a distributed framework for off-policy RL consisting of multiple agents that are trained in parallel while also being regularized to be similar to the current best policy. Maintaining a population of agents can help mitigate issues due to convergences to local optima. The method is evaluated on standard continuous control tasks, and shows some performance improvements over methods that train just a single agent. Ablation experiments are also conducted to evaluate the effects of different design decisions.