Year: 2021

Abstract:
By introducing randomness on environment parameters that fundamentally affect the dynamics, domain randomization (DR) imposes diversity to the policy trained by deep reinforcement learning, and thus improves its capability of generalization. The randomization of environments, however, introduces another source of variability for the estimate of policy gradients, in addition to the already high variance due to trajectory sampling. Therefore, with standard state-dependent baselines, the policy gradient methods may still suffer high variance, causing low sample efficiency during the training of DR. In this paper, we theoretically derive a bias-free and state/environment-dependent optimal baseline for DR, and analytically show its ability to achieve further variance reduction over the standard constant and state-dependent baselines for DR. We further propose a variance reduced domain randomization (VRDR) approach for policy gradient methods, to strike a tradeoff between the variance reduction and computational complexity in practice. By dividing the entire space of environments into some subspaces and estimating the state/subspace-dependent baseline, VRDR enjoys a theoretical guarantee of faster convergence than the state-dependent baseline. We conduct empirical evaluations on six robot control tasks with randomized dynamics. The results demonstrate that VRDR can consistently accelerate the convergence of policy training in all tasks, and achieve even higher rewards in some specific tasks.

heading: 1 INTRODUCTION
text: Deep reinforcement learning (DRL) has achieved an impressive success on complex sequential decision-making tasks, such as playing video games at top human-level (Ye et al., 2020), continuous robot manipulation (Agarwal et al., 2021) and traffic signal control (Egeaa et al., 2021). For an extensive exploration, DRL requires a massive amount of samples to train the policy, which is usually done in a simulator constructed for the task. Due to the lack of diversity, however, policy trained by DRL tends to overfit to a specific training environment (Cobbe et al., 2019), causing possibly a severe performance degradation (i.e., reality gap) when the policy learned in simulator is transferred to the real deployment (Peng et al., 2018; Kang et al., 2019). To close this gap, domain randomization (DR) has been proposed to randomize the environment parameters that may vary the dynamics and observation in simulator, imposing diversity on the trained policy (Tobin et al., 2017; Jiang et al., 2021). Recent success in robot control has shown that DR enables the trained policy to generalize in real deployment, even with presence of fundamental modeling errors in the simulator (Muratore et al., 2021; Xie et al., 2020). DR has also demonstrated its capability of robustness to contend with extremely rare environments (Muratore et al., 2021).
Direct applications of DR on policy gradient methods can be thought as policy optimization on multiple randomly generated environments, which incurs additional variability of the observed data. Therefore, a critical challenge is the low sample efficiency due to the extremely high variance of the gradient estimator, where the variability not only stems from the gradient approximation of expected return from a batch of sampled trajectories (Greensmith et al., 2004), but is also imposed by the randomization of environment parameters. In standard DRL, a commonly used method to reduce variance is to construct a bias-free and action-independent baseline that is subtracted from the expected return (Sutton & Barto, 2018). For example, a typical choice of baseline is the state value function of a policy. When directly applied to DR, as proposed by Andrychowicz et al. (2020), it is equivalent to learning a state value function that predicts the expected return over all possible
environments. Though remaining unbiased, such a state-dependent baseline may be a poor choice in DR, since the additional variability of randomized environments is not taken into account.
In this paper, we aim to address the high variance issue of policy gradient methods for domain randomization, with a particular focus on reducing the additional variance imposed by randomization of environments. Our key insight is that the additional information on varying environments can be incorporated into the baseline to further reduce this variance. Theoretically, we derive the optimal state/environment-dependent baseline, and demonstrate that it improves consistently the variance reduction over baselines that is constant or uses state information only. In order for the practical implementation to strike the tradeoff between the variance reduction performance and computational complexity for maintaining the state/environment-dependent baselines, we propose a variance reduced domain randomization (VRDR) approach for policy gradient methods, which can improve the sample efficiency while maintaining a reasonable number of baselines associated with a set of specifically designed environment subspaces. Our main contributions can be summarized as follows.
• Theoretically optimal state/environment-dependent baseline for DR. For the policy gradient in a variety of environments that differ in dynamics, we derive theoretically an optimal baseline that depends on both the states and environments. We further quantify the variance reduction improvement achieved by the proposed state/environment-dependent baseline over two common choices of baselines for DR, i.e., the constant and state-dependent baselines.
• Criterion for constructing practical state/subspace-dependent baseline. Since the accurate estimation of state/environment-dependent baseline for each possible environment is infeasible during practical implementation of RL, we propose to alternatively divide the entire space of environment parameters into a limited number of subspaces, and estimate instead the optimal baseline for every pair of state and environment subspace. We further show that the clustering of environments into subspaces should follow the policy’s expected returns on these environments, which can guarantee an improvement of variance reduction over the state-dependent baseline.
• Variance reduced domain randomization (VRDR) with empirical evaluation. To strike the tradeoff between the variance reduction performance and computational complexity for maintaining optimal baselines, we develop a variance reduced domain randomization (VRDR) approach for policy gradient methods. Specifically, VRDR learns an acceptable number of baselines for each pair of state and environment subspace, where the environment subspaces are determined based on the above criterion. We then conduct experiments on six robot control tasks with their fundamental physical parameters randomized, demonstrating that VRDR can accelerate the convergence of policy training in DR settings, as compared to the standard state-dependent baselines. In some specific tasks, VRDR can even achieve a higher reward.

heading: 2 BACKGROUND
text: Notation. Under the standard reinforcement learning (RL) setting, the environment is modeled as a Markov decision process (MDP) defined by a tuple < S,A, Tp,Φ >, where S and A denote the state and action spaces, respectively. For the convenience of derivation, we assume that they are finite. Tp : S × A × S → [0, 1] is the environment transition model that is essentially determined by environment parameter p ∈ P , with P denoting the space of environment parameters. In robot control, for example, environment parameter p can be a vector containing the rolling friction of each joint and the mass of torso and arms. Throughout the rest of this paper, by environment p we mean that the environment has dynamics determined by parameter p. Φ : S × A → R is the reward function. At each time step t, the agent observes its state st ∈ S and takes an action at ∈ A under the guidance of policy πθ(at|st) parameterized by θ. It will then receive a reward rt = Φ(st, at), while the environment shifts to the next state st+1 with probability T (st+1|st, at, p). The goal of standard RL is to search for a policy π that maximizes the expected discounted return η(π, p) = Eτ [R(τ)] over all possible trajectories τ = {st, at, rt, st+1}∞t=0 of states and actions, where R(τ) = ∑∞ t=0 γ
trt and γ ∈ [0, 1] is the discount factor. We can then define the state value function as Vπ(s, p) = E [∑∞ k=0 γ krt+k|st = s ] , the
action value function asQπ(s, a, p) = E [∑∞ k=0 γ krt+k|st = s, at = a ] , and the advantage function as Aπ(s, a, p) = Qπ(s, a, p)− Vπ(s, p). Policy gradient methods for DR. In DR, the environment parameter p is a random variable that follows the probability distribution P over P . For the convenience of derivation, we assume a finite en-
vironment parameter space P with cardinality |P|. By introducing DR, the goal of policy optimization is to maximize the expected return over all possible environment parameters: Ep∼P [η(π, p)]. The policy gradient with action-independent baseline (Sutton & Barto, 2018) can be formulated as:
∇θEp∼P [η(π, p)] = EP [ Eµpπ,π [ ∇θ log πθ(a|s) [Qπ(s, a, p)− b] ]] , (1)
where we define µpπ(s) = ∑∞ t=0 γ
tPπ(st = s|p) as the discounted state visitation frequency, with Pπ(st = s|p) denoting the probability of shifting from the initial state s0 to state s after t steps under policy π in environment p. For convenience, we further denote g(θ, s, a, p) , ∇θ log πθ(a|s)[Qπ(s, a, p) − b], which is the gradient estimator for the state-action pair under environment p. As long as the baseline b is action-independent, we have Ea[∇θ log πθ(a|s)b] = ∇θEa[b] = 0 and thus EP,µpπ,π[g] = EP,µpπ,π [∇θ log πθ(a|s)Qπ(s, a, p)] , E[g], where the subscript is dropped for convenience. Therefore, by subtracting this action-independent baseline b, the variance of gradient estimator V ar(g) = E[gTg] − E[g]TE[g] can be reduced without introducing any bias (Greensmith et al., 2004).

heading: 3 OPTIMAL BASELINES FOR DOMAIN RANDOMIZATION
text: To derive the optimal baselines for DR, we formulate the following optimization problem that aims to minimize the variance of gradient estimate w.r.t. the baseline b (Greensmith et al., 2004):
min b
E [ G(a, s) [ Qπ(s, a, p)− b ]2︸ ︷︷ ︸ gTg ] − E[g]TE[g]⇔ min b EP,µpπ,π [ G(a, s) [ Qπ(s, a, p)− b ]2] (2)
where we denote G(a, s) , ∇θ log πθ(a|s)T∇θ log πθ(a|s). Due to its independence of b, the second term E[g]TE[g] does not affect the minimizer, and is thus omitted on RHS of Eq. (2). In the following, we first derive for DR two common choices of baselines that are constant or depend on the state only. We then propose the optimal state/environment-dependent baseline, and show its ability to further reduce the variance incurred by the randominzation of environment parameters.

heading: 3.1 TWO COMMON CHOICES OF ACTION-INDEPENDENT BASELINES
text: Optimal constant baseline. We first consider a constant baseline bc that depends neither on the action nor on the state. The optimization problem in Eq. (2) then becomes minimizing the expectation of a quadratic function, which can be proved to be convex. Referring to the detailed derivation in Appendix A.1, the optimal constant baseline b∗c for DR-based policy gradient methods is:
b∗c = EP,µpπ,π
[ G(a, s)Qπ(s, a, p) ] EP,µpπ,π [ G(a, s) ] = EP,µpπ[V ′(s, p)]. (3) This optimal baseline b∗c can be understood as the expected state value function V
′(s, p) over all states and possible environments, where the state value function V ′(s, p) is computed as the weighted average of the action value function: V ′(s, p) = Eπ [ G(a,s)
EP,µpπ,π [G(a,s)] Qπ(s, a, p)
] .
Optimal state-dependent baseline. As in the standard RL, the utilization of state-dependent baseline in the DR setting can be considered as an expected value function b(s) = EP [ Eπ[Qπ(s, a, p)] ] for each state over all possible environments, which predicts the expected return over the distribution of dynamics caused by the variation of environment parameters. Still referring to Appendix A.1, the optimal state-dependent baseline for DR is given as follow:
b∗(s) = EP (p|s)Eπ[G(a, s)[Qπ(s, a, p)]]
Eπ[G(a, s)] . (4)

heading: 3.2 OPTIMAL STATE/ENVIRONMENT-DEPENDENT BASELINE
text: In DR, the randomization of environment parameters imposes additional variability for the estimate of gradients, which aggravates the instability of RL training process. In the following subsections,
we show that this variance can be effectively reduced by further incorporating into the baseline the information about varying environments. To this end, we propose a state/environment-dependent baseline b(s,P) = {b(s, pi)}|P|i=1 for DR, and rewrite the variance minimization in Eq. (2) as:
min b(s,P)
Ep∼P,µpπ [ Eπ [ G(a, s) [ Qπ(s, a, p)− b(s, p) ]2]] . (5)
In Appendix A.1, following the similar deduction as in (Greensmith et al., 2004), the optimal state/environment baseline can be derived as:
b∗(s,P) = {b∗(s, pi)}|P|i=1,where b ∗(s, pi) =
Eπ [ G(a, s)Qπ(s, a, pi) ] Eπ [ G(a, s)
] , (6) which indicates requirements of maintaining a specific baseline for each environment to incorporate the environment-specific information. Note that if environment parameter pi is time-varying along episodes and considered as stochastic input process that partially affects the dynamics, this optimal baseline b∗(s,P) is equivalent to the optimal input-driven baseline as derived by Mao et al. (2018).
3.3 VARIANCE REDUCTION IMPROVEMENT OF b∗(s,P)
Theorem 1. Let V arb(s)(g) and V arb ∗(s,P)(g) denote the variance of gradient estimator by incorporating an arbitrary state-dependent baseline b(s) and the optimal state/environment-dependent baseline b∗(s,P), respectively. Compared to the state-dependent baseline b(s), the variance can be further reduced by b∗(s,P), with the following improvement:
V arb(s)(g)− V arb ∗(s,P)(g) = EP,µpπ √Eπ[G(a, s)]b(s)− Eπ[G(a, s)Qπ(s, a, p)]√ Eπ [ G(a, s) ] 2 . (7)
Proof. See Appendix A.2.
Guided by Theorem 1, we can then quantify the variance improvement achieved by the optimal state/environment-dependent baseline b∗(s,P) over the optimal state-dependent baseline b∗(s) by letting b(s) = b∗(s), as shown in the following corollary.
Corollary 1. Let V arb ∗(s)(g) denote the variance of gradient estimator with the optimal statedependent baseline b∗(s). The variance reduction improvement of b∗(s,P) over b∗(s) is:
V arb ∗(s)(g)− V arb ∗(s,P)(g) = EP,µpπ  ( EP (p|s) [ Eπ[G(a, s)Qπ(s, a, p)] ] − Eπ [ G(a, s)Qπ(s, a, p) ])2 Eπ [ G(a, s) ]  .
(8)
Since the optimal constant baseline b∗c can be thought as letting b(s) = b ∗ c for each state s ∈ S , we show in Appendix A.3 that further variance reduction is achieved by b∗(s,P) over b∗c . Therefore, we analytically justify that by incorporating the additional information about environments, the optimal state/environment-dependent baseline b∗(s,P) can obtain the minimum variance for DR within the baselines that consider both state and environment parameters.

heading: 4 VARIANCE REDUCED DOMAIN RANDOMIZATION
text: For the single environment case in standard RL, the theoretically optimal state-dependent baseline is rarely used in practice due to the computational concern (Wu et al., 2018). Rather, for both implementational and conceptual benefit, a common alternative choice of b(s) is the state value function V (s). Similarly in DR, even though the optimal state/environment-dependent baseline is known and given in Eq. (6), the computation of |P| baselines for all the possible environments requires a very high computational and sampling complexity, which is therefore infeasible during the practical training process. Fortunately, similar system dynamics often emerge on environments having the similar parameters, on which the same policy will also obtain the similar expected returns.
In the following, we aim to strike a tradeoff between the variance reduction performance and the computational complexity required for maintaining multiple state/environment-dependent baselines.
Specifically, we propose to maintain an acceptable numberM of state/environment-dependent baselines in practice, where M < |P|. The entire environment parameter space P is then divided as M subspaces {Pj}Mj=1, each of which has a size |Pj |. For each subspace Pj , we can compute the optimal state-only baseline as b∗(s,Pj) = EPj(p|s)Eπ[G(a|s)Qπ(s, a, p)]/Eπ[G(a, s)]. We then denote the state/subspace-dependent baseline as bM (s,P) = {b∗(s,Pj)}Mj=1. Assuming a uniform sampling on P , and referring to Appendix A.4, the total variance of the gradient estimator by incorporating the state/subspace-dependent baseline bM (s,P) can be written as:
V arM (g) = ∑ j=1 |Pj | |P| V ar(gjM ), g j M = ∇θ log πθ(a|s) ( Qπ(s, a, p j i )− b ∗(s,Pj) ) , pji ∈ Pj , (9)
where pji is the i-th environment parameter in subspace j with sampling distribution 1 |Pj | , and V ar(gjM ) is computed over p j i ∈ Pj , following s ∼ µπ(·|p j i ) and a ∼ π. Theorem 2. The variance difference of gradient estimate between the optimal state-dependent baseline and the state/subspace-dependent baseline is:
V arb ∗(s)(g)− V arM (g) (10)
= M∑ j=1 |Pj |∑ i=1 1 |P| ∑ s µπ(s|pji )
[( EP (p|s)[Yp(s)]− Ypji (s) )2 − ( EPj(p|s)[Yp(s)]− Ypji (s) )2] Eπ [G(a, s)] ,
where Yp(s) , Eπ [G(a, s)Qπ(s, a, p)]. For a policy π to be updated at a certain step, and assuming the uniform distribution for sampling environment parameters, we have V arb
∗(s)(g) ≥ V arM (g) if for each subspace Pj:
V arP(Yp(s)) ≥ V arPj (Yp(s)), (11)
where the variance V arP(Yp(s)) and V arPj (Yp(s)) is computed over P and Pj , respectively.
Proof. See Appendix A.5.
Theorem 2 provides a practical guideline for constructing subspaces to reduce the variance of gradient estimate, by holding the variance of Yp(s) in each subspace not exceeding that in the entire environment space. However, it still introduces extra computation to estimating G(a, s) in Yp(s). When the inner product of log policyG(s, a) is loosely correlated to the Q-value function1, we have Ea[G(a, s)Qπ(s, a, p)] = Ea[G(a, s)]Ea[Qπ(s, a, p)], and Eq. (11) is thus equivalent to:
V arP(Vπ(s, p)) ≥ V arPj (Vπ(s, p)), (12)
It indicates that by clustering the entire environment space into some subspaces and holding the variance of expected return in each subspace not greater than that in the entire environment space, the state/subspace-dependent baseline can further reduce the variance of gradient estimate compared to the optimal state-only baseline. Note that by increasing the number of subspaces, the state/subspace-dependent baseline bM (s,P) will approach the optimal sate/environment-dependent baseline b∗(s,P). However, we argue that the more baselines we employ, the more samples are required for estimating these baselines. As will be shortly shown by the experiment, increasing M may not monotonically improve the policy’s performance during the training process.
Based on our theory, we propose a practical variance reduced domain randomization approach (VRDR) for policy gradient and summarize it in Algorithm 1, where the state/subspace-dependent baseline b(s,Pj) = Ep∼PjV (s, p) , V (s,Pi) is employed for each state and subspace pair. At each
1Take the Gaussian policy that is commonly used in policy gradient methods for example. The policy takes s as input and outputs for action selections a Gaussian distribution with the expectation ma and variance σ2. The action a = ma has the minimum gradient of zero, i.e., G(ma, s) = 0, while this state and action pair (ma, s) is not correlated with the Q value before the trained policy obtains a high Q value.
Algorithm 1 Variance Reduced Domain Randomization (VRDR) for Policy Gradient 1: Initialize policy π0, number of environment parameters sampled per iteration H , number of
subspaces M , clustering interval Nc, maximal number of iterations N , subspace prototypes u = {ui}Mi=1, baseline V (s|Pi) for each subspace Pi, and cluster labels l = {li}Mi=1 as shuffled with {i}Mi=1.
2: for k = 0 to N − 1 do 3: if k%Nc == 0 then 4: Sample H environments {pc}H−1c=0 with L trajectories for each environment pc. 5: Compute Ω = {V̂π(pc)}Hc=1, where V̂π(pc) = ∑L−1 j=0 R(τc,j)/L is the average return of environment pc. 6: Apply clustering method on Ω to get the cluster set {Ci}Mi=1, with each Ci labeled by i. 7: Determine corresponding prototypes u′ by computing u′i = ∑ j∈Ci pj/|Ci|.
8: Determine minl ∑ i |u′li − ui| where l = {li}, update prototypes by ui = u ′ li
, and relabel cluster i with li.
9: else 10: Sample a set of environment parameters {pe}H−1e=0 uniformly and determine their cluster label by mini |pe − ui| to obtain the cluster set {Ci}Mi=1. 11: Sample L trajectories {τe,j}L−1j=0 for each environment pe using policy πk. 12: end if 13: Use PPO for policy optimization to get the updated policy πk+1 on trajectories, with the baseline V (s|Pi) of the cluster that has been grouped to. 14: Update V (s|Pi) on the trajectories in cluster Ci. 15: end for
iteration k, we sample M environments and group them into M clusters by finding the nearest subspace prototype. Then, we train the policy on the trajectories sampled on each environment with the corresponding baseline b(s,Pj) and update the baseline b(s,Pj) on the corresponding trajectories. During the clustering phase, as guided by Eq. (12), we perform the clustering method on {pc}H−1c=1 w.r.t. the average return V̂π(pc) to get the M clusters with corresponding subspace prototypes u′i. The clustering methods are usually applied to group a fixed dataset, with the labeling done once and for all. In VRDR, however, we perform clustering multiple times during training, hence the prototypes between two clustering phases would be similar but have different labels. To avoid the case where the new prototype u′i close to a certain current prototype is assigned with a different label, we relabel these new prototypes u′, and update the current ones u according to u′ as described in Line 8 of Algorithm 1, where we aim to find a set of labels l = {li} that minimizes the distance |u′li −ui| between new prototype u′ and current prototype u. Then, after the clustering phase, the subspace Pj can be reconstructed according to the sampled environments in cluster Cj . We utilize loss function LV = ∑ st∈τi |V (st,Pi)− ∑∞ t′=t γ
t′−trt|2 to update the baseline V (s,Pi) for each cluster Ci. It has been proved by Ghadimi & Lan (2013) that the optimization of gradient variance can accelerate the convergence of gradient descent methods. In Appendix A.7, we show that our proposed VRDR method gains a κ = (κ > 1) acceleration on the convergence of policy gradient methods, as compared to the direct application of optimal state-dependent baseline for DR.

heading: 5 EXPERIMENTS
text: In this section, we evaluate our proposed VRDR method on six simulated robot control tasks, where the fundamental environment parameters that affect dynamics are randomized for the generalization of trained policy. The experimental environments are implemented based on the robot control simulator as described in (Brockman et al., 2016). We compare VRDR with two baseline algorithms: the uniform domain randomization (DR) (Mehta et al., 2020) and the multiple value network (MVN) (Mao et al., 2018). We utilize the proximal policy optimization (PPO) (Schulman et al., 2017) to train a generalized policy for all the comparison algorithms. In DR, we uniformly sample the environment parameter p and collect trajectories by using the current policy on the sampled environments for policy update, where a value function that is learned from trajectories from all sampled environments is employed as the state-dependent baseline. In MVN, multiple value functions are learned for the pre-sampled environments at the beginning of training, while each value function Vi
is utilized as a baseline for the gradient estimator of trajectories collected on environment parameters that are closest to the corresponding pre-sampled pi. For VRDR, we apply hierarchical cluster method (Jain, 2010) to divide the entire environment space during training, and group the trajectories collected at each interaction phase as described in Algorithm 1. See Appendix A.14 for detail of hierarchical clustering, and Appendix A.10 for comparison of clustering methods. We keep all the hyper-parameters about policy optimization for PPO the same as the implementation in Brockman et al. (2016), and purely discuss the gain brought by variance reduction for gradient estimate in policy gradient methods. Our experiments are designed to answer the following questions:
• Can VRDR effectively improve the convergence rate of the policy training. Will the final reward achieved by the converged policy trained by VRDR outperform the other two baseline algorithms?
• How would the policy performance of all the three algorithms degrade on the out-of-distribution unseen environments/dynamics?
• How would the specific hyper-parameters in VRDR affect the performance of training process.

heading: 5.1 TRAINING CURVES WITH RANDOMIZED DYNAMICS
text: The six robot control tasks are as follows. 1) Walker2D: control a planar biped robot to run as fast as possible; 2) Hopper: control a planar monopod robot to hop as fast as possible; 3) Halfcheetah: control a planar cheetah robot to run fast; 4 & 5) Pendulum & Pendulum2D: apply the force to swing a pendulum and keep it upright; 6) InvertedDoublePendulum: control a cart (attached to a two-link pendulum) to balance the whole system and keep the pendulum upright. We modify the environment parameters in the configure file to generate six environments with the same control task and different dynamics. The possible sampling range of the environment parameters is shown in Table 1. Specifically, we randomize the material density that determines the mass and inertia, and the sliding friction acting along the tangent plane in Walker2D, Hopper, and Halfcheetah. We randomize the pole length, respectively, in Pendulum, Pendulum2D and InvertedDoublePendulum, and the pole mass additionally in Pendulum2D.
We run the training process on environments sampled on the preset parameter range for the same number of iterations N until all the algorithms are converged. At each iteration k, we generate H = 100 environments by uniformly sampling the parameter range in all algorithms. We run at least 15 seeds for each algorithm on all the environments to obtain the training results. The policy and value networks in each algorithm are trained for the same number of epochs and sampled trajectories at each iteration. We show the training curves of the six tasks, respectively, in Figs. 1(a)-1(f). The solid curve is the average returns on all the seeds at a certain iteration, while the shaded area denotes the standard deviations. It can be seen that by applying DR on PPO, we can improve the average return on the whole training range, while VRDR can accelerate the training process on the six tasks. In some specific tasks, such as Walker2D, Hopper and Halfcheetah, VRDR even achieves a higher average return than DR and MVN. In balancing tasks like Pendulum and Pendulum2D, VRDR has shown a significant acceleration on the convergence of policy training.

heading: 5.2 GENERALIZATION TO UNSEEN ENVIRONMENTS
text: In this subsection, we evaluate the generalization capability of trained policies on the unseen range during training. We learn 15 policies for DR, MVN and VRDR, respectively, on training environments with different random seeds and apply the trained policies on corresponding testing unseen environments. The generalization performance for each algorithm is measured by the average score over 15 policies. The generalization evaluation of DR, MVN and VRDR are shown in Figs. 2(a) and 2(b). VRDR shows the best generalization performance on Walker2D. DR has a broader range of generalization than MVN, although MVN achieves higher score on the training range than DR.
For Pendulum2D, however, all the algorithms present a close performance. This result indicates that the generalization performance is consistent with the average return achieved after convergence in training, and would not be affected by the convergence rate.

heading: 5.3 ABLATION STUDY OF VRDR
text: Number of baselines M : In Theorem 1, we show that by applying b∗(s,P), we maintain a state/environment baseline b∗(s, pi) for each environment pi and can obtain the minimum variance of gradient estimate. Theoretically, increasing M to |P| will achieve a better variance reduction improvement. Figs. 3(a)-3(c) show the training curves of VRDR on Walker2D, Pendulum, and Pendulum2D with different numbers of baselines. Note that VRDR is reduced to DR when setting M = 1. We find that the increase of M will decrease the number of training samples for approximation of each baseline if we sample the same number of environment at each iteration, which hence retards the convergence rate of VRDR. This suggests that we can set M to a small number in practice to strike the tradeoff between the variance reduction and computational complexity.
Clustering interval Nc: Each new clustering result may change the group that each environment belong to, hence altering the value function and affecting the policy training in the next clustering interval. The underlying dynamic mechanisms vary in different environments, and thus the shifting of value function may affect the training with varying degrees. We show the training curves of VRDR with different clustering interval Nc on Walker2D, Hopper, and Halfcheetah in Figs. 4(a)4(c), and the clustering results in Appendix A.9. The results suggest the need of a specific tuning of Nc for each task.

heading: 6 RELATED WORK
text: State-of-the-art methods that have endeavored to tackle the generalization and robustness of DRL, including DR, meta RL and robust RL, all implicitly or explicitly impose diversity on the policy training. DR and meta RL both tend to learn a policy that can generalize to a variety of environments (Jiang et al., 2021; Lin et al., 2020), which may differ in dynamics and reward function during training. By introducing an adversary that acts to disturb the dynamics or the observation of the environment during training (Zhang et al., 2020), the learned policy can gain robustness on deployment.
The introduced diversity for training environments enables the generalization of DRL policy, while the consequent high variance aggravates the sample efficiency of DRL training.
For policy optimization under DR, Mehta et al. (2020) declare that the uniform sampling of DR may lead to suboptimal and high-variance policy, and propose active DR to encourage the sampling distribution to select informative environments. Several works have been proposed to optimize the sampling distribution for DR (Andrychowicz et al., 2020; Paul et al., 2019), while the baseline optimization is seldom considered in the policy search using policy gradient and the direct application of state-dependent baseline is commonly used as formulated in Eq. (4).
Policy gradient methods usually suffer high variance due to the estimation of gradient from sampled trajectories. By learning a Q-function (critic) instead of using its sampling estimation, actor-critic methods reduce the variance with the expense of introducing a bias (Sutton & Barto, 2018). Another line of research follows the idea of control variate (Cheng et al., 2020), by subtracting an commonly used state-dependent baseline from the gradient estimate to reduce the variance without introducing bias. By assuming the independence of each dimension in the action vector, Wu et al. (2018) propose a action/state-dependent baseline, which reduces more variance than the state-only baseline. These methods are designed for standard RL and require further discussion under the context of DR. Variance reduced gradient algorithms like stochastic variance-reduced gradient (SVRG) (Johnson & Zhang, 2013) and momentum-based variance reduction (Cutkosky & Orabona, 2019) methods have been studied in the policy gradient for RL (Huang et al., 2020; Xu et al., 2020). These methods, however, do not consider the variance reduction for the DR setting. Mao et al. (2018) propose an input-dependent baseline to reduce the variance of stochastic input process, which is similar to our state/environment-dependent baseline. Then, the multi-value-network (MVN) approach and metalearning approach are proposed to learn the baseline. Meanwhile, Liu et al. (2019) propose to learn the per-task control variate and the meta control variate for each meta-RL task, where the per-task variate is constructed by the action-dependent baseline. In essence, the MVN and per-task control variates approaches are the same, since they both aim to learn a baseline for each input or task. And both of these meta-learning approaches are built upon model-agnostic meta learning (MAML) (Finn et al., 2017) to scale when the number of input instantiations or tasks are large.

heading: 7 CONCLUSION
text: In this paper, we have focused on reducing the high variance of gradient estimator in policy gradient methods for DR with additional randomness on environment parameters. Specifically, we derived the optimal state/environment-dependent baseline, and verified that by incorporating the environment information further variance reduction could be achieved over the optimal constant or state-only baselines. We then proposed a variance reduced domain randomization (VRDR) approach for policy gradient methods, to strike a tradeoff between the variance reduction and computational complexity in practical implementation. We have validated VRDR on several robot control tasks, demonstrating an overall faster convergence speed of policy training, and even better policy performance in some specific tasks.

heading: A APPENDIX

heading: A.1 DERIVATION OF OPTIMAL BASELINES
text: Following the derivation in (Greensmith et al., 2004), we now give the derivation of three kinds of optimal baselines by solving the optimization problem as proposed in Eq. (2).
Derivation of optimal constant baseline.
It can be verified that the optimization problem in Eq. (2) is convex w.r.t. the constant baseline bc, and we denote:
min bc
F (bc) , EP,µpπ,π [ G(a, s) [ Qπ(s, a, p)− bc ]2] . (13)
By letting the first-order derivative equal to zero:
dF (bc)
dbc = −2EP,µpπ,π
[ G(a, s)[Qπ(s, a, p)− bc] ] = 0, (14)
we have the optimal constant baseline for DR as:
b∗c = EP,µpπ,π[G(a, s)Qπ(s, a, p)]
EP,µpπ,π[G(a, s)] . (15)
Derivation of optimal state-dependent baseline.
The variance minimization problem w.r.t. b(s) is denoted as:
min b(s)
F (b(s)) , EP,µpπ,π [ G(a, s)[Qπ(s, a, p)− b(s)]2 ] . (16)
Following the generating process of joint distribution of p, s and a, we have P (p, s, a) = P (p)P (s|p)P (a|s, p) = P (p)µπ(s|p)π(a|s), where the last equality is because that policy π is constructed without knowing p. The RHS of Eq. (16) can be expanded as:
Ep∼P,µpπ [ Eπ [ G(a, s)[Qπ(s, a, p)− b(s, p)]2 ]] =
|P|∑ i=1 P (pi) ∑ sj µπ(sj |pi)Eπ [ G(a, sj)[Qπ(sj , a, pi)− b(sj , pi)]2 ]
= |S|∑ j=1 |P|∑ i=1 P (pi)µπ(sj |pi)Eπ [ G(a, sj)[Qπ(sj , a, pi)− b(sj , pi)]2 ] . (17)
By letting the first-order partial derivative equal to zero:
∂F (b(s))
∂b(s) = −2 |S|∑ j=1 |P|∑ i=1 P (pi)µπ(sj |pi)Eπ [ G(a, sj)[Qπ(sj , a, pi)− b(sj)] ] = 0, (18)
where b(s) = {b(sj)}, we have: |P|∑ i=1 P (pi)µπ(sj |pi)Eπ [ G(a, sj)[Qπ(sj , a, pi)− b(sj)] ] = 0, for each b(sj). (19)
It can be further written as |P|∑ i=1 P (pi, sj)Eπ [ G(a, sj)[Qπ(sj , a, pi)] ] = |P|∑ i=1 P (pi, sj)Eπ [ G(a, sj)[b(sj)] ] , (20)
and |P|∑ i=1 P (sj)P (pi|sj)Eπ [ G(a, sj)[Qπ(sj , a, pi)] ] = |P|∑ i=1 P (sj)P (pi|sj)Eπ [ G(a, sj) ] b(sj), (21)
where P (sj) can be further canceled on both sides. We can then get the optimal state-dependent baseline for sj as
b∗(sj) =
∑|P| i=1 P (pi|sj)Eπ [ G(a, sj)[Qπ(sj , a, pi)] ] ∑|P| i=1 P (pi|sj)Eπ [ G(a, sj) ] = EP (p|sj)Eπ [ G(a, sj)[Qπ(sj , a, p)] ] Eπ [ G(a, sj)
] . (22)
For a continuous state space, we have
b∗(s) = EP (p|s)Eπ
[ G(a, s)[Qπ(s, a, p)] ] Eπ [ G(a, s)
] , (23) Derivation of optimal state/environment-dependent baseline.
The variance minimization problem w.r.t. b(s,P) in Eq. (5) is denoted as:
min b(s,P)
F (b(s,P)) = Ep∼P,µpπ [ Eπ [ G(a, s)[Qπ(s, a, p)− b(s, p)]2 ]] . (24)
By letting the first-order partial dirivative equal to zero:
∂F (b(s,P)) ∂b(s, pi)
= −2Eπ [ G(a, s) [ Qπ(s, a, p)− b(s, pi) ]] = 0, (25)
we obtain the optimal state/environment-dependent baseline b∗(s,P) = {b∗(s, pi)}|P|i=1, where b∗(s, pi) = Eπ[G(a, s)Q(s, a, pi)]/Eπ[G(a, s)].

heading: A.2 PROOF OF THEOREM 1
text: The variance of policy gradient using the optimal state/environment-dependent baseline b∗(s,P) is:
V arb ∗(s,P)(g) = E [ G(a, s) [ Qπ(s, a, p)−
Eπ[G(a, s)Q(s, a, p)] Eπ[G(a, s)]
]2] − E[g]TE[g]
= E [ G(a, s) [ Q2π(s, a|p)− 2Qπ(s, a, p) Yp(s)
Z + Y 2p (s) Z2
]] − E[gT]E[g]
= EP,µpπ [Xp(s)]− EP,µπ
[ Y 2p (s)
Z
] − E[gT]E[g], (26)
where we denote Xp(s) , Eπ [ G(a, s)Q2π(s, a, p) ] , Yp(s) , Eπ [G(a, s)Qπ(s, a, p)] and Z , Eπ[G(a, s)]. For an arbitrary state-dependent baseline b(s), the variance difference between b(s) and b∗(s,P) is:
V arb(s)(g)− V arb ∗(s,P)(g)
=EP,µpπEπ
[ G(a, s) [ (Qπ(s, a, p)− b(s))2 − ( Qπ(s, a, p)− Yp(s)
Z
)2]]
=EP,µpπEπ
[ G(a, s) [ b2(s)− 2Qπ(s, a, p)b(s) + 2Qπ(s, a, p) Yp(s)
Z − Y 2p (s) Z2
]]
=EP,µpπ [ Eπ[G(a, s)]b2(s)− 2Eπ[G(a, s)Q(s, a, p)]b(s) +
E2π[G(a, s)Q(s, a, p)] Eπ[G(a, s)]
]
=EP,µpπ [√ Eπ[G(a, s)]b(s)−
Eπ[G(a, s)Q(s, a, p)]√ Eπ[G(a, s)]
]2 . (27)
A.3 VARIANCE REDUCTION IMPROVEMENT OF b∗(s,P) OVER b∗c
The application of optimal constant baseline b∗c can be considered as letting b(s) = b ∗ c for each state s ∈ S. Hence, by direct applying Theorem 1, we can obtain the variance reduction improvement of b∗(s,P) over b∗c as:
V arb ∗ c (g)− V arb ∗(s,P)(g)
=EP,µpπ √Eπ[G(a, s)]b∗c − Eπ[G(a, s)Qπ(s, a, p)]√ Eπ [ G(a, s) ] 2
=EP,µpπ Eπ[G(a, s)](EP,µpπ,π[G(a, s)Qπ(s, a, p)]EP,µpπ,π[G(a, s)] − Eπ [ G(a, s)Qπ(s, a, p) ] Eπ [ G(a, s) ] )2  . (28)
A.4 VARIANCE OF POLICY GRADIENT ESTIMATOR BY APPLYING bM (s,P)
Under uniform domain randomization, we demonstrate that the variance of policy gradient in the whole environment space can be formulated as weighted sum of the variance in subspaces:
V arM (g) = |P|∑ k=1 1 |P| ∑ s µπ(s|pk) ∑ a π(a|s)(g(θ, s, a, pk)− Eg(θ, s, a, pk))T(g(θ, s, a, pk)− Eg(θ, s, a, pk))
= M∑ j=1 |Pj | |P| |Pj |∑ i=1 1 |Pj | ∑ s µπ(s|pji ) ∑ a π(a|s)(g(θ, s, a, pji )− Eg(θ, s, a, p j i )) T(g(θ, s, a, pji )− Eg(θ, s, a, p j i ))
= M∑ j=1 |Pj | |P| V ar(gj), (29)
where gj is the gradient estimator of environment in subspace j and pji is the i−th environment in subspace j.

heading: A.5 PROOF OF THEOREM 2
text: In this subsection, we study how to divide subspace to reduce variance of gradient estimator. First, we derive the variance difference in Eq. (10). For a certain state-dependent baseline b(s) and an arbitrary sampling distribution P of environment parameters, the variance of gradient estimate is:
V arb(s)(g) = M∑ j=1 |Pj |∑ i=1 P (pi) ∑ s µπ(s|pji ) ∑ a π(a|s)G(a|s) [ Q2π(s, a, p j i )− 2Qπ(s, a, p j i )b(s) + b 2(s) ]
= M∑ j=1 |Pj |∑ i=1 P (pi) ∑ s µπ(s|pji ) [ Xpji − Y 2 pji (s) Z + Y 2 pji (s) Z − 2b(s)Ypji (s) + b 2(s)Z ]
= M∑ j=1 |Pj |∑ i=1 P (pi) ∑ s µπ(s|pji ) Xpji − Y 2 pji (s) Z + ( Ypji (s) √ Z − b(s) √ Z )2 . (30) The variance of gradient estimate by incorporating the state/subspace-dependent baseline is
V arM (g) = M∑ j=1 |Pj |∑ i=1 P (pi) ∑ s µπ(s|pji ) Xpji − Y 2 pji (s) Z + ( EPj(p|s)Yp(s)√ Z − Ypji (s) √ Z )2 , (31)
and variance of gradient estimate by incorporating the optimal state-dependent baseline is
V arb ∗(s)(g) = M∑ j=1 |Pj |∑ i=1 P (pi) ∑ s µπ(s|pji ) Xpji − Y 2 pji (s) Z + ( EP (p|s)Yp(s)√ Z − Ypji (s) √ Z )2 . (32)
The difference between them is
V arb ∗(s)(g)− V arM (g)
= M∑ j=1 |Pj |∑ i=1 P (pi) ∑ s µπ(s|pji )
[( EP (p|s)[Yp(s)]− Ypji (s) )2 − ( EPj(p|s)[Yp(s)]− Ypji (s) )2] Eπ [G(a, s)] .
(33)
Thus, Eq. (10) can be obtained by letting P (pi) = 1|P| . Then, we discuss the dividing process of subspaces to make the variance reduction improvement V arb ∗(s)(g) ≥ V arM (g) hold. Under the uniform sampling distribution P (p) = 1|P| , we have
M∑ j=1 |Pj | |P| V arP(Yp(s)) = V ar P(Yp(s)) = |P|∑ i=1 P (pi|s)(EP (p|s)[Yp(s)]− Ypi(s))2
= M∑ j=1 |Pj |∑ i=1 P (pji |s)(EP (p|s)[Yp(s)]− Ypji (s)) 2
= M∑ j=1 |Pj |∑ i=1 1 |P| P (s|pji ) P (s) (EP (p|s)[Yp(s)]− Ypji (s)) 2. (34)
The first equality holds since ∑M j=1 |Pj | |P| = 1. And
M∑ j=1 |Pj | |P| V arPj (Yp(s)) = M∑ j=1 |Pj | |P| |Pj |∑ i=1 Pj(pi|s)(EPj(p|s)[Yp(s)]− Ypji (s)) 2
= M∑ j=1 |Pj | |P| |Pj |∑ i=1 1 |Pj | P (s|pji ) P (s) (EPj(p|s)[Yp(s)]− Ypji (s)) 2
= M∑ j=1 |Pj |∑ i=1 1 |P| P (s|pji ) P (s) (EPj(p|s)[Yp(s)]− Ypji (s)) 2. (35)
Note that P (s|pji ) = µπ(s|p j i ). Thus, as long as V ar P(Yp(s)) ≥ V arPj (Yp(s)), we have V arP(Yp(s)) = ∑M j=1 |Pj | |P| V ar P(Yp(s)) ≥ ∑M j=1 |Pj | |P| V ar Pj (Yp(s)). Then, combing Eq. (10), we have V arb ∗(s)(g) ≥ V arM (g).

heading: A.6 DOMAIN RANDOMIZATION WITH AN ARBITRARY SAMPLING DISTRIBUTION
text: In this subsection, we study how to divide subspace to reduce variance of gradient estimator in domain randomization with an arbitrary sampling distribution. Specifically, we prove that for an arbitrary sampling distribution of environment parameters, as long as Eq. (11) holds, we still have V arb
∗(s)(g) ≥ V arM (g). Under arbitrary sampling distribution P , the variance difference of gradient estimate between the optimal state-dependent baseline and the state/subspace-dependent baseline
is: V arb ∗(s)(g)− V arM (g)
= M∑ j=1 ∑ pi∈Pj P (pi) ∑ s µπ(s|pi)
[( EP (p|s)[Yp(s)]− Ypi(s) )2 − ( EPj(p|s)[Yp(s)]− Ypi(s) )2] Eπ [G(a, s)] ,
(36)
where P (pi) is the sampling probability of environment pi from the entire environment space P . Hence, P (pi)∑
pi∈Pj P (pi)
can be used to denote the sampling probability of environment pi within the
subspace Pj . For V arPj (Yp(s)), we have
V arPj (Yp(s)) = ∑ pi∈Pj P (pi)∑ pi∈Pj P (pi) P (s|pi) P (s) (EPj(p|s)[Yp(s)]− Ypi(s)) 2, (37)
and thus M∑ j=1  ∑ pi∈Pj P (pi) V arPj (Yp(s)) = M∑ j=1 ∑ pi∈Pj P (pi) P (s|pi) P (s) (EPj(p|s)[Yp(s)]− Ypi(s)) 2. (38)
For V arP(Yp(s)), we have
M∑ j=1  ∑ pi∈Pj P (pi) V arP(Yp(s)) =V arP(Yp(s)) = ∑ pi∈P P (pi|s)(EP (p|s)[Yp(s)]− Ypi(s))2
= M∑ j=1 ∑ pi∈Pj P (pi|s)(EP (p|s)[Yp(s)]− Ypi(s))2
= M∑ j=1 ∑ pi∈Pj P (pi) P (s|pi) P (s) (EP (p|s)[Yp(s)]− Ypi(s))2, (39)
where the first equality follows that ∑M j=1 [∑ pi∈Pj P (pi) ] = 1 and the second quality is from the definition of V arP(Yp(s)).
Note that P (s|pji ) = µπ(s|p j i ). Thus, as long as V ar P(Yp(s)) ≥ V arPj (Yp(s)), we have∑M j=1 [∑ pi∈Pj P (pi) ] V arP(Yp(s)) ≥ ∑M j=1 [∑ pi∈Pj P (pi) ] V arPj (Yp(s)). Then, combing Eq. (36), we have V arb ∗(s)(g) ≥ V arM (g).

heading: A.7 CONVERGENCE ANALYSIS OF VRDR
text: Let ∇J(θ) = ∇θEp∼P [η(π, p)] be the policy gradient. In this section, we present the theorem proposed by Ghadimi & Lan (2013) under the DR setting. It shows that under Assumption 1 that ∇J(θ) is Lipschitz continuous w.r.t. policy parameter θ, the variance of gradient estimator dominates the convergence rate. Assumption 1. ‖∇J(θ1)−∇J(θ2)‖ ≤ L‖θ1 − θ2‖, ∀θ1, θ2 ∈ Rn.
Applying an arbitrary gradient estimator, the convergence of policy gradient is upper bounded as follows. Theorem 3. (Ghadimi & Lan, 2013) Under Assumption 1, and assuming that the step size αk = min{ 1L ,
1√ V ar(gk)K }, we have
ER‖∇J(θ)‖22 ≤ L(J(θ∗)− J(θ1)) K/2 + Lmaxk √ V ar(gk)√ K , (40)
where J(θ∗) is the maximum expected cumulative discounted reward that can be achieved by policy πθ∗ , K is the maximum number of iterations for policy gradient method, gk = g(θk, s, a) is the gradient estimator at the k-th iteration for (s, a), and
ER‖∇J(θ)‖22 = ∑K k=1(αk − L/2α2k)E‖∇J(θk)‖22∑K
k=1(αk − L/2α2k) (41)
is the expectation w.r.t. distribution PR(θk) = αk−L/2α2k∑K
k=1(αk−L/2α2k) and all the possible randomness.
By holding Eq. (12), we have V ar b∗(s)(g)
V arM (g) > 1 and gains a κ = √ V arb∗(s)(g) V arM (g)
(κ > 1) acceleration on the convergence of policy gradient methods.

heading: A.8 ANALYSIS OF ADDITIONAL COMPUTATIONAL COST OF VRDR
text: In DR, the computational cost contains mainly the feed-forward computation and back-propagation computation of the policy network and the value network. For N iterations, H trajectories with length of Lh, size of state space |S| and constant computational cost of feed-forward and backpropagation computation d1, the computational cost of DR is O(N ·H · Lh · |S| · d1). The additional computational cost introduced by VRDR is mainly from the clustering phase. Considering the hierachical clustering method in Algorithm 2. The maximum number of outer loop is H − M < H . At each outer loop, the computational cost of distance matrix is m2 ≤ H2. Then, let the cost of distance computation in Line 6 of Algorithm 2 be d2, the computational cost is O(N ·H3 · d2). Note that compared with the simple computation of distance between two scalars ui and uj , the computational cost of feed-forward and back-propagation computation are implemented for the entire policy and value networks, both of which contain multiple layers and neurons. Therefore, in practice, d1 is usually multiple order-of-magnitude larger than d2. Thus, under the condition that Lh and |S| are comparable with H , term O(N · H · Lh · |S| · d1) will become the dominate term in the overall computational complexity of VRDR, while the additional computational complexity introduced by the clustering phase of VRDR can be neglected.

heading: A.9 CLUSTERING RESULTS DURING TRAINING
text: In this subsection, we show the clustering results of three successive clustering updates (iteration k = nNc, (n+ 1)Nc, (n+ 2)Nc) on Walker2d, Hopper, and Halfcheetah in Figs. 5(a)-5(c).

heading: A.10 ABLATION STUDY OF VRDR ON CLUSTERING METHODS
text: In this subsection, we study the influence of different clustering methods on VRDR. Considering that we require to specify the number of clusters in VRDR and the clusters should be generated with similar state values to satisfy Eq. (12), we additionally chose k-means for the comparison to the originally adopted hierachical clustering. The comparison results of different clustering methods are shown in Fig. 6(a) and Fig. 6(b). It can be seen that applying k-means and hierachical clustering methods present similar average scores on Hopper and Halfcheetah.

heading: A.11 COMPARISON TO COMBINED STATE-DEPENDENT BASELINE
text: The optimal state/environment baseline can be considered as combined state-dependent baseline, where combined state is composed of original state s and environment parameter p, if we treat p as part of state of the MDP. In this subsection, we conduct experiment to evaluate DR with combined state-dependent baseline (DRCS) and the training curves are shown in Fig. 7(a) and Fig. 7(b). The curves of DRCS show that applying regular state-dependent baseline on this combined state degrades the average score during training as compared to DR and VRDR.

heading: A.12 COMPARISON TO OTHER BASELINE ALGORITHMS
text: In this subsection, we compare VRDR with other baseline algorithms including DR with meta baseline (DRMB) (Mao et al., 2018; Liu et al., 2019) and Epopt (Rajeswaran et al., 2016). We use PPO with the same setting as in Section 5. In DRMB, a meta baseline is applied to learn the simpler
alternative Eπ [Qπ(s, a, p)] instead of state/environment-dependent baseline b∗(s, p). The training curves are shown in Fig. 8(a) and Fig. 8(b). VRDR shows better average scores than DRMB on Walker2d and a similar average score on Hopper.
In Epopt, we use purely trajectories from the α-percentile worst-case environments for training, where we set α = 5. The training curves are shown in Fig. 9(a) and Fig.9(b). And it can be seen that VRDR outperforms Epopt on both environments.
A.13 VARIANCE OF GRADIENT ESTIMATES DURING TRAINING
In this subsection, we empirically evaluate the variance of the gradient estimates that are practically achieved by DR, MVN and VRDR on Pendulum2D. It can be seen that at the beginning of training, VRDR can achieve a significantly lower variance of gradient estimates than the other two baselines, which coincides with the faster convergence behavior of VRDR as shown in Fig. 1(e).

heading: A.14 HIERACHICAL CLUSTERING FOR VRDR
text: In this subsection, we detail the hierarchical clustering method used in the implementation of VRDR, and summarize it in Algorithm 2.
A.15 FROM EQ. (12) TO EQ. (11)
In this subsection, we prove that V arP(Vπ(s, p)) ≥ V arPj (Vπ(s, p)) in Eq. (12) is a sufficient condition of V arP(Yp(s)) ≥ V arPj (Yp(s)) in Eq. (11). When the above condition holds, we have
V arP(Vπ(s, p)) ≥ V arPj (Vπ(s, p)), (42)
and by multiplying both sides with a non-negative term Ea[G(a, s)], we have
Ea[G(a, s)]V arP(Vπ(s, p)) ≥ Ea[G(a, s)]V arPj (Vπ(s, p)). (43)
Algorithm 2 Hierachical Clustering
1: Input Ω = {V̂π(pc)}Hc=1, 2: Initialize number of clusters M , current number of clusters m = H , prototypes {ui = V̂π(pi)}Hi=1, distance matrix Md 3: while m ≥M do 4: for i = 0 to m− 1 do 5: for j = 0 to m− 1 do 6: Md(i, j) = |ui − uj | 7: Md(i, j) = Md(j, i) 8: end for 9: end for
10: merge the two clusters ui∗ and uj∗ having the minimum distance: ui∗ = ui∗ ∪ uj∗ 11: m = m− 1 12: end while 13: Output prototypes {ui}Mi=1
By expanding the LHS with the definition of variance, we have
Ea[G(a, s)]V arP(Vπ(s, p)) (44)
=Ea[G(a, s)] |P|∑ i=1 P (pi|s) [ EP [Vπ(s, p)]− Vπ(s, pi) ]2 = 1
Ea[G(a, s)] |P|∑ i=1 P (pi|s) [ Ea[G(a, s)]EP [ Ea [Qπ(s, a, p)] ] − Ea[G(a, s)]Ea [Qπ(s, a, pi)] ]2
= 1
Ea[G(a, s)] |P|∑ i=1 P (pi|s) [ EP [ Ea [G(a, s)Qπ(s, a, p)] ] − Ea [G(a, s)Qπ(s, a, pi)] ]2 = V arP(Yp(s))
Ea[G(a, s)] ,
where the third equality can be obtained by using the condition Ea[G(a, s)Qπ(s, a, p)] = Ea[G(a, s)]Ea[Qπ(s, a, p)]. Similarly, we can obtain Ea[G(a, s)]V arPj (Vπ(s, p)) = V ar Pj (Yp(s)) Ea[G(a,s)] . Hence, from the inequality in Eq. (43), we have V arP(Yp(s)) ≥ V arPj (Yp(s)), and thus V arb
∗(s)(g) ≥ V arM (g) according to Eq. (10). Namely, the improvement of variance reduction by applying subspaces generated by following Eq. (12) can also be quantified by Eq. (10).

Review summaries:
This paper tackles the variance of policy gradient due to the domain randomization used in RL in simulations. The authors prove that the policy gradient variance can be further reduced by learning a state-dependent baseline for each environment parameter compared to state-dependent baselines. The authors then develop a practical algorithm based on the analysis and analyze the properties of the algorithm. The algorithm is implemented and tested on six robot control tasks. It consistently accelerates policy training. 

this work studies policy gradient methods for domain randomization (DR). in particular, it investigates baselines for policy gradient under the dr settings such that the gradient estimate can have a lower variance to ensure better policy updates and learning. this paper derives optimal state/environment-dependent baseline theoretically, gives general recipes for building the baseline, and proposes an algorithm called variance reduced domain randomization (VRDR). vrdr is evaluated on several continuous control tasks and it performs better compared with two baselines.

This paper tackles the high variance problem caused by the randomization of environments for estimating the policy gradients. The idea is to derive a bias-free and state/environment-dependent optimal baseline for domain randomization. The authors further develop a VRDR method by dividing the entire environment space into subspaces and estimating the state/subspace-dependent baseline.