Title: ACTION-DEPENDENT CONTROL VARIATES FOR POL-ICY OPTIMIZATION VIA STEIN'S IDENTITY

Abstract: Policy gradient methods have achieved remarkable successes in solving challenging reinforcement learning problems. However, it still often suffers from the large variance issue on policy gradient estimation, which leads to poor sample efficiency during training. In this work, we propose a control variate method to effectively reduce variance for policy gradient methods. Motivated by the Stein's identity, our method extends the previous control variate methods used in REINFORCE and advantage actor-critic by introducing more general action-dependent baseline functions. Empirical studies show that our method significantly improves the sample efficiency of the state-of-the-art policy gradient approaches. * Both authors contributed equally. Author ordering determined by coin flip over a Google Hangout.

1. INTRODUCTION:

Deep reinforcement learning (RL) provides a general framework for solving challenging goaloriented sequential decision-making problems, It has recently achieved remarkable successes in advancing the frontier of AI technologies (Silver et al., 2017; Mnih et al., 2013; Silver et al., 2016; Schulman et al., 2017) . Policy gradient (PG) is one of the most successful model-free RL approaches that has been widely applied to high dimensional continuous control, vision-based navigation and video games (Schulman et al., 2016; Kakade, 2002; Schulman et al., 2015; Mnih et al., 2016) .

Despite these successes, a key problem of policy gradient methods is that the gradient estimates often have high variance. A naive solution to fix this issue would be generating a large amount of rollout samples to obtain a reliable gradient estimation in each step. Regardless of the cost of generating large samples, in many practical applications like developing driverless cars, it may not even be possible to generate as many samples as we want. A variety of variance reduction techniques have been proposed for policy gradient methods (See e.g. Weaver & Tao 2001 , Greensmith et al. 2004 , Schulman et al. 2016 and Asadi et al. 2017) .

In this work, we focus on the control variate method, one of the most widely used variance reduction techniques in policy gradient and variational inference. The idea of the control variate method is to subtract a Monte Carlo gradient estimator by a baseline function that analytically has zero expectation. The resulted estimator does not introduction biases theoretically, but may achieve much lower variance if the baseline function is properly chosen such that it cancels out the variance of the original gradient estimator. Different control variates yield different variance reduction methods. For example, in REINFORCE (Williams, 1992) , a constant baseline function is chosen as a control variate; advantage actor-critic (A2C) (Sutton & Barto, 1998; Mnih et al., 2016) considers a state-dependent baseline function as the control variate, which is often set to be an estimated value function V (s). More recently, in Q-prop (Gu et al., 2016b) , a more general baseline function that linearly depends on the actions is proposed and shows promising results on several challenging tasks. It is natural to expect even more flexible baseline functions which depend on both states and actions to yield powerful variance reduction. However, constructing such baseline functions turns out to be fairly challenging, because it requires new and more flexible mathematical identities that can yield a larger class of baseline functions with zero analytic expectation under the policy distribution of interest.

To tackle this problem, we sort to the so-called Stein's identity (Stein, 1986) which defines a broad class of identities that are sufficient to fully characterize the distribution under consideration (see e.g., Liu et al., 2016; Chwialkowski et al., 2016) . By applying the Stein's identity and also drawing connection with the reparameterization trick (Kingma & Welling, 2013; Rezende et al., 2014) , we construct a class of Stein control variate that allows us to use arbitrary baseline functions that depend on both actions and states. Our approach tremendously extends the existing control variates used in REINFORCE, A2C and Q-prop.

We evaluate our method on a variety of reinforcement learning tasks. Our experiments show that our Stein control variate can significantly reduce the variance of gradient estimation with more flexible and nonlinear baseline functions. When combined with different policy optimization methods, including both proximal policy optimization (PPO) (Schulman et al., 2017; Heess et al., 2017) and trust region policy optimization (TRPO) (Schulman et al., 2015; 2016) , it greatly improves the sample efficiency of the entire policy optimization.

2. BACKGROUND:

We first introduce basic backgrounds of reinforcement learning and policy gradient and set up the notation that we use in the rest of the paper in Section 2.1, and then discuss the control variate method as well as its application in policy gradient in Section 2.2.

2.1. REINFORCEMENT LEARNING AND POLICY GRADIENT:

Reinforcement learning considers the problem of finding an optimal policy for an agent which interacts with an uncertain environment and collects reward per action. The goal of the agent is to maximize the long-term cumulative reward. Formally, this problem can be formulated as a Markov decision process over the environment states s ∈ S and agent actions a ∈ A, under an unknown environmental dynamic defined by a transition probability T (s |s, a) and a reward signal r(s, a) immediately following the action a performed at state s. The agent's action a is selected by a conditional probability distribution π(a|s) called policy. In policy gradient methods, we consider a set of candidate policies π θ (a|s) parameterized by θ and obtain the optimal policy by maximizing the expected cumulative reward or return

J(θ) = E s∼ρπ,a∼π(a|s) [r(s, a)] ,

where ρ π (s) = ∞ t=1 γ t-1 Pr(s t = s) is the normalized discounted state visitation distribution with discount factor γ ∈ [0, 1). To simplify the notation, we denote E s∼ρπ,a∼π(a|s) [•] by simply E π [•] in the rest of paper. According to the policy gradient theorem (Sutton & Barto, 1998) , the gradient of J(θ) can be written as

EQUATION

where

Q π (s, a) = E π ∞ t=1 γ t-1 r(s t , a t

)|s 1 = s, a 1 = a denotes the expected return under policy π starting from state s and action a. Different policy gradient methods are based on different stochastic estimation of the expected gradient in Eq (1). Perhaps the most straightforward way is to simulate the environment with the current policy π to obtain a trajectory {(s t , a t , r t )} n t=1 and estimate ∇ θ J(θ) using the Monte Carlo estimation:

EQUATION

where Qπ (s t , a t ) is an empirical estimate of Q π (s t , a t ), e.g., Qπ (s t , a t ) = j≥t γ j-t r j . Unfortunately, this naive method often introduces large variance in gradient estimation. It is almost always the case that we need to use control variates method for variance reduction, which we will introduce in the following. It has been found that biased estimators help improve the performance, e.g., by using biased estimators of Q π or dropping the γ t-1 term in Eq (2). In this work, we are interested in improving the performance without introducing additional biases, at least theoretically.

2.2. CONTROL VARIATE:

The control variates method is one of the most widely used variance reduction techniques in policy gradient. Suppose that we want to estimate the expectation µ = E τ [g(s, a)] with Monte Carlo samples (s t , a t ) n t=1 drawn from some distribution τ, which is assumed to have a large variance var τ (g). The control variate is a function f (s, a) with known analytic expectation under τ , which, without losing of generality, can be assumed to be zero: E τ [f (s, a)] = 0. With f , we can have an alternative unbiased estimator

μ = 1 n n t=1 (g(s t , a t ) -f (s t , a t )) ,

where the variance of this estimator is var τ (g -f )/n, instead of var τ (g)/n for the Monte Carlo estimator. By taking f to be similar to g, e.g. f = g -µ in the ideal case, the variance of g -f can be significantly reduced, thus resulting in a more reliable estimator.

The key step here is to find an identity that yields a large class of functional f with zero expectation.

In most existing policy gradient methods, the following identity is used

EQUATION

Combining it with the policy gradient theorem, we obtain

EQUATION

Note that we drop the γ t-1 term in Eq (2) as we do in practice. The introduction of the function φ does not change the expectation but can decrease the variance significantly when it is chosen properly to cancel out the variance of Q π (s, a). In REINFORCE, φ is set to be a constant φ(s) = b baseline, and b is usually set to approximate the average reward, or determined by minimizing var( ∇θ J(θ)) empirically. In advantage actor-critic (A2C), φ(s) is set to be an estimator of the value function V π (s) = E π(a|s) [Q π (s, a)], so that Qπ (s, a) -φ(s) is an estimator of the advantage function. For notational consistency, we call φ the baseline function and f (s, a) = ∇ θ log π(a|s)φ(s) the corresponding control variate.

Although REINFORCE and A2C have been widely used, their applicability is limited by the possible choice of φ. Ideally, we want to set φ to equal Q π (s, a) up to a constant to reduce the variance of ∇θ J(θ) to close to zero. However, this is impossible for REINFORCE or A2C because φ(s) only depends on state s but not action a by its construction. Our goal is to develop a more general control variate that yields much smaller variance of gradient estimation than the one in Eq (4).

3. POLICY GRADIENT WITH STEIN CONTROL VARIATE:

In this section, we present our Stein control variate for policy gradient methods. We start by introducing Stein's identity in Section 3.1, then develop in Section 3.2 a variant that yields a new control variate for policy gradient and discuss its connection to the reparameterization trick and the Q-prop method. We provide approaches to estimate the optimal baseline functions in Section 3.3, and discuss the special case of the Stein control variate for Gaussian policies in Section 3.4. We apply our control variate to proximal policy optimization (PPO) in Section 3.5.

3.1. STEIN'S IDENTITY:

Given a policy π(a|s), Stein's identity w.r.t π is

EQUATION

which holds for any real-valued function φ(s, a) with some proper conditions. To see this, note the left hand side of Eq ( 5) is equivalent to ∇ a (π(a|s)φ(s, a)) da, which equals zero if π(a|s)φ(s, a) equals zero on the boundary of the integral domain, or decay sufficiently fast (e.g., exponentially) when the integral domain is unbounded.

The power of Stein's identity lies in the fact that it defines an infinite set of identities, indexed by arbitrary function φ(s, a), which is sufficient to uniquely identify a distribution as shown in the work of Stein's method for proving central limit theorems (Stein, 1986; Barbour & Chen, 2005) , goodness-of-fit test (Chwialkowski et al., 2016; Liu et al., 2016) , and approximate inference (Liu & Wang, 2016) . Oates et al. (2017) has applied Stein's identity as a control variate for general Monte Carlo estimation, which is shown to yield a zero-variance estimator because the control variate is flexible enough to approximate the function of interest arbitrarily well.

3.2. STEIN CONTROL VARIATE FOR POLICY GRADIENT:

Unfortunately, for the particular case of policy gradient, it is not straightforward to directly apply Stein's identity (5) as a control variate, since the dimension of the left-hand side of ( 5) does not match the dimension of a policy gradient: the gradient in ( 5) is taken w.r.t. the action a, while the policy gradient in ( 1) is taken w.r.t. the parameter θ. Therefore, we need a general approach to connect ∇ a log π(a|s) to ∇ θ log π(a|s) in order to apply Stein's identity as a control variate for policy gradient. We show in the following theorem that this is possible when the policy is reparameterizable in that a ∼ π θ (a|s) can be viewed as generated by a = f θ (s, ξ) where ξ is a random noise drawn from some distribution independently of θ. With an abuse of notation, we denote by π(a, ξ|s) the joint distribution of (a, ξ) conditioned on s, so that π(a|s) = π(a|s, ξ)π(ξ)dξ, where π(ξ) denotes the distribution generating ξ and π(a|s, ξ) = δ(a -f (s, ξ)) where δ is the Delta function.

Theorem 3.1. With the reparameterizable policy defined above, using Stein's identity, we can derive

EQUATION

Proof. See Appendix for the detail proof. To help understand the intuition, we can consider the Delta function as a Gaussian with a small variance h 2 , i.e. π(a|s, ξ) ∝ exp(-a -f (s, ξ) 2 2 /2h 2 ), for which it is easy to show that

EQUATION

This allows us to convert between the derivative w.r.t. a and w.r.t. θ, and apply Stein's identity.

Stein Control Variate Using Eq (6) as a control variate, we obtain the following general formula of policy gradient:

EQUATION

where any fixed choice of φ does not introduce bias to the expectation. Given a sample set (s t , a t , ξ t ) n t=1 where a t = f θ (s t , ξ t ), an estimator of the gradient is

∇θ J(θ) = 1 n n t=1 ∇ θ log π(a t | s t )( Qπ (s t , a t ) -φ(s t , a t )) + ∇ θ f θ (s t , ξ t )∇ a φ(s t , a t ) . (9)

This estimator clearly generalizes the control variates used in A2C and REINFORCE. To see this, let φ be action independent, i.e. φ(s, a) = φ(s) or even φ(s, a) = b, in both cases the last term in (9) equals to zero because ∇ a φ = 0. When φ is action-dependent, the last term (9) does not vanish in general, and in fact will play an important role for variance reduction as we will illustrate later.

Relation to Q-prop Q-prop is a recently introduced sample-efficient policy gradient method that constructs a general control variate using Taylor expansion. Here we show that Q-prop can be derived from ( 8) with a special φ that depends on the action linearly, so that its gradient w.r.t. a is action-independent, i.e. ∇ a φ(a, s) = ϕ(s). In this case, Eq (8) becomes

∇ θ J(θ) = E π [∇ θ log π(a|s)(Q π (s, a) -φ(s, a)) + ∇ θ f θ (s, ξ)ϕ(s)] . Furthermore, note that E π(ξ) [∇ θ f (s, ξ)] = ∇ θ E π(ξ) [f (s, ξ)] := ∇ θ µ π (s)

, where µ π (s) is the expectation of the action conditioned on s. Therefore,

∇ θ J(θ) = E π [∇ θ log π(a|s) (Q π (s, a) -φ(s, a)) + ∇ θ µ π (s)ϕ(s)] ,

which is the identity used in Q-prop to construct their control variate (see Eq 6 in Gu et al. 2016b ).

In Q-prop, the baseline function is constructed empirically by the first-order Taylor expansion as

EQUATION

where V π (s) and Qπ (s, a) are parametric functions that approximate the value function and Q function under policy π, respectively. In contrast, our method allows us to use more general and flexible, nonlinear baseline functions φ to construct the Stein control variate which is able to decrease the variance more significantly.

Relation to the reparameterization trick The identity ( 6) is closely connected to the reparameterization trick for gradient estimation which has been widely used in variational inference recently (Kingma & Welling, 2013; Rezende et al., 2014) . Specifically, let us consider an auxiliary objective function based on function φ:

L s (θ) := E π(a|s) [φ(s, a)] = π(a|s)φ(s, a)da.

Then by the log-derivative trick, we can obtain the gradient of this objective function as

EQUATION

which is the left-hand side of ( 6). On the other hand, if a ∼ π(a|s) can be parameterized by

a = f θ (s, ξ), then L s (θ) = E π(ξ) [φ(s, f θ (s, ξ))],

leading to the reparameterized gradient in Kingma & Welling (2013) :

EQUATION

Equation ( 11) and ( 12) are equal to each other since both are ∇ θ L s (θ). This provides another way to prove the identity in (6). The connection between Stein's identity and the reparameterization trick that we reveal here is itself interesting, especially given that both of these two methods have been widely used in different areas.

3.3. CONSTRUCTING THE BASELINE FUNCTIONS FOR STEIN CONTROL VARIATE:

We need to develop practical approaches to choose the baseline functions φ in order to fully leverage the power of the flexible Stein control variate. In practice, we assume a flexible parametric form φ w (s, a) with parameter w, e.g. linear functions or neural networks, and hope to optimize w efficiently for variance reduction. Here we introduce two approaches for optimizing w and discuss some practical considerations.

We should remark that if φ is constructed based on data (s t , a t ) n t=1 , it introduces additional dependency and ( 4) is no longer an unbiased estimator theoretically. However, the bias introduced this way is often negligible in practice (see e.g., Section 2.3.4 of Oates & Girolami (2016) ). For policy gradient, this bias can be avoided by estimating φ based on the data from the previous iteration.

Estimating φ by Fitting Q Function Eq (8) provides an interpolation between the log-likelihood ratio policy gradient (1) (by taking φ = 0) and a reparameterized policy gradient as follows (by taking φ(s, a) = Q π (s, a)):

EQUATION

It is well known that the reparameterized gradient tends to yield much smaller variance than the log-likelihood ratio gradient from the variational inference literature (see e.g., Kingma & Welling, 2013; Rezende et al., 2014; Roeder et al., 2017; Tucker et al., 2017 ). An intuitive way to see this is to consider the extreme case when the policy is deterministic. In this case the variance of ( 11) is infinite because log π(a|s) is either infinite or does not exist, while the variance of ( 12) is zero because ξ is deterministic. Because optimal policies often tend to be close to deterministic, the reparameterized gradient should be favored for smaller variance.

Therefore, one natural approach is to set φ to be close to Q function, that is, φ(s, a) = Qπ (s, a) so that the log-likelihood ratio term is small. Any methods for Q function estimation can be used. In our experiments, we optimize the parameter w in φ w (s, a) by

EQUATION

)

where R t an estimate of the reward starting from (s t , a t ). It is worth noticing that with deterministic policies, ( 13) is simplified to the update of deep deterministic policy gradient (DDPG) (Lillicrap et al., 2015; Silver et al., 2014) . However, DDPG directly plugs an estimator Qπ (s, a) into ( 13) to estimate the gradient, which may introduce a large bias; our formula (8) can be viewed as correcting this bias in the reparameterized gradient using the log-likelihood ratio term.

Estimating φ by Minimizing the Variance Another approach for obtaining φ is to directly minimize the variance of the gradient estimator. Note that var( ∇θ

J(θ)) = E[( ∇θ J(θ)) 2 ] -E[ ∇θ J(θ)] 2 .

Since E[ ∇θ J(θ)] = ∇ θ J(θ) which does not depend on φ, it is sufficient to minimize the first term. Specifically, for φ w (s, a) we optimize w by

EQUATION

)

In practice, we find that it is difficult to implement this efficiently using the auto-differentiation in the current deep learning platforms because it involves derivatives w.r.t. both θ and a. We develop a computational efficient approximation for the special case of Gaussian policy in Section 3.4.

Architectures of φ Given the similarity between φ and the Q function as we mentioned above, we may decompose φ into φ w (s, a) = V π (s) + ψ w (s, a).

The term V π (s) is parametric function approximation of the value function which we separately estimate in the same way as in A2C, and w is optimized using the method above with fixed V π (s).

Here the function ψ w (s, a) can be viewed as an estimate of the advantage function, whose parameter w is optimized using the two optimization methods introduced above. To see, we rewrite our gradient estimator to be

EQUATION

where Âπ (s t , a t ) = Qπ (s t , a t ) -V π (s t ) is an estimator of the advantage function. If we set ψ w (s, a) = 0, then Eq (16) clearly reduces to A2C. We find that separating V π (s) from ψ w (s, a) works well in practice, because it effectively provides a useful initial estimation of φ, and allows us to directly improve the φ on top of the value function baseline.

3.4. STEIN CONTROL VARIATE FOR GAUSSIAN POLICIES:

Gaussian policies have been widely used and are shown to perform efficiently in many practical continuous reinforcement learning settings. Because of their wide applicability, we derive the gradient estimator with the Stein control variate for Gaussian policies here and use it in our experiments.

Specifically, Gaussian policies take the form π(a | s) = N (a; µ θ1 (s), Σ θ2 (s)), where mean µ and covariance matrix Σ are often assumed to be parametric functions with parameters θ = [θ 1 , θ 2 ]. This is equivalent to generating a by a = f θ (s, ξ) = µ θ1 (s) + Σ θ2 (s) 1/2 ξ, where ξ ∼ N (0, 1). Following Eq (8), the policy gradient w.r.t. the mean parameter θ 1 is

EQUATION

For each coordinate θ in the variance parameter θ 2 , its gradient is computed as

EQUATION

where A, B := trace(AB) for two d a × d a matrices.

Note that the second term in (18) contains ∇ a log π(a|s); we can further apply Stein's identity on it to obtain a simplified formula

EQUATION

)

The estimator in ( 19) requires to evaluate the second order derivative ∇ a,a φ, but may have lower variance compared to that in (18). To see this, note that if φ(s, a) is a linear function of a (like the case of Q-prop), then the second term in (19) vanishes to zero, while that in (18) does not.

We also find it is practically convenient to estimate the parameters w in φ by minimizing var( ∇µ J)+ var( ∇Σ J), instead of the exact variance var( ∇θ J). Further details can be found in Appendix 7.2.

3.5. PPO WITH STEIN CONTROL VARIATE:

Proximal Policy Optimization (PPO) (Schulman et al., 2017; Heess et al., 2017) is recently introduced for policy optimization. It uses a proximal Kullback-Leibler (KL) divergence penalty to regularize and stabilize the policy gradient update. Given an existing policy π old , PPO obtains a new policy by maximizing the following surrogate loss function

J ppo (θ) = E πold π θ (a|s) π old (a|s) Q π (s, a) -λKL [π old (•|s) || π θ (•|s)] ,

where the first term is an approximation of the expected reward, and the second term enforces the the updated policy to be close to the previous policy under KL divergence. The gradient of J ppo (θ) can be rewritten as

∇ θ J ppo (θ) = E πold w π (s, a)∇ θ log π(a|s)Q π λ (s, a)

where w π (s, a) := π θ (a|s)/π old (a|s) is the density ratio of the two polices, and Q π λ (s, a) := Q π (s, a) + λw π (s, a) -1 where the second term comes from the KL penalty. Note that , a) ] by canceling the density ratio. Applying (6), we obtain

E πold [w π (s, a)f (s, a)] = E π [f (s

EQUATION

)

Putting everything together, we summarize our PPO algorithm with Stein control variates in Algorithm 1. It is also straightforward to integrate the Stein control variate with TRPO.

4. RELATED WORK:

Stein's identity has been shown to be a powerful tool in many areas of statistical learning and inference. An incomplete list includes Gorham & Mackey (2015) , Oates et al. (2017) , Oates et al. (2016) , Chwialkowski et al. (2016) , Liu et al. (2016) , Sedghi et al. (2016) , Liu & Wang (2016 ), Feng et al. (2017) , Liu & Lee (2017) . This work was originally motivated by Oates et al. (2017) , which uses Stein's identity as a control variate for general Monte Carlo estimation. However, as discussed in Section 3.1, the original formulation of Stein's identity can not be directly applied to policy gradient, and we need the mechanism introduced in ( 6) that also connects to the reparameterization trick (Kingma & Welling, 2013; Rezende et al., 2014) .

Control variate method is one of the most widely used variance reduction techniques in policy gradient (see e.g., Greensmith et al., 2004) 17) and ( 19) for Gaussian policies). end for (Gu et al., 2016b) which we draw close connection to, the work of Thomas & Brunskill (2017) also suggests a way to incorporate action-dependent baselines, but is restricted to the case of compatible function approximation. More recently, Tucker et al. (2017) studied a related action-dependent control variate for discrete variables in learning latent variable models.

// Adjust the KL penalty coefficient λ if KL[πold|π θ ] > βhighKLtarget then λ ← αλ else if KL[πold|π θ ] < βlowKLtarget then λ ← λ/α end if until Convergence studied. Besides Q-prop

Recently, Gu et al. (2017) proposed an interpolated policy gradient (IPG) framework for integrating on-policy and off-policy estimates that generalizes various algorithms including DDPG and Q-prop. If we set ν = 1 and p π = p β (corresponding to using off-policy data purely) in IPG, it reduces to a special case of ( 16) with ψ w (s, a) = Q w (s, a) -E π(a|s) [Q w (s, a)] where Q w an approximation of the Q-function. However, the emphasis of Gu et al. (2017) is on integrating on-policy and offpolicy estimates, generally yielding theoretical bias, and the results of the case when ν = 1 and p π = p β were not reported. Our work presents the result that shows significant improvement of sample efficiency in policy gradient by using nonlinear, action-dependent control variates.

In parallel to our work, there have been some other works discovered action-dependent baselines for policy-gradient methods in reinforcement learning. Such works include Grathwohl et al. (2018) which train an action-dependent baseline for both discrete and continuous control tasks. Wu et al. (2018) exploit per-dimension independence of the action distribution to produce an action-dependent baseline in continuous control tasks.

5. EXPERIMENTS:

We evaluated our control variate method when combining with PPO and TRPO on continuous control environments from the OpenAI Gym benchmark (Brockman et al., 2016) using the MuJoCo physics simulator (Todorov et al., 2012) . We show that by using our more flexible baseline functions, we can significantly improve the sample efficiency compared with methods based on the typical value function baseline and Q-prop.

All our experiments use Gaussian policies. As suggested in Section 3.3, we assume the baseline to have a form of φ w (s, a) = V π (s) + ψ w (s, a), where V π is the valued function estimated separately in the same way as the value function baseline, and ψ w (s, a) is a parametric function whose value w is decided by minimizing either Eq (14) (denoted by FitQ), or Eq (27) designed for Gaussian policy (denoted by MinVar). We tested three different architectures of ψ w (s, a), including Linear. ψ w (s, a) = ∇ a q w (a, µ π (s)), (a -µ π (s)) , where q w is a parametric function designed for estimating the Q function Q π . This structure is motivated by Q-prop, which estimates w by fitting q w (s, a) with Q π . Our MinVar, and FitQ methods are different in that they optimize w as a part of φ w (s, a) by minimizing the objective in Eq (14) and Eq (27). We show in Section 5.2 that our optimization methods yield better performance than Q-prop even with the same architecture of ψ w . This is because our methods directly optimize for the baseline function φ w (s, a), instead of q w (s, a) which serves an intermediate step.

Quadratic. ψ w (s, a) = -(a -µ w (s)) Σ -1 w (a -µ w (s)).

In our experiments, we set µ w (s) to be a neural network, and Σ w a positive diagonal matrix that is independent of the state s. This is motivated by the normalized advantage function in Gu et al. (2016a) .

MLP. ψ w (s, a) is assumed to be a neural network in which we first encode the state s with a hidden layer, and then concatenate it with the action a and pass them into another hidden layer before the output.

Further, we denote by Value the typical value function baseline, which corresponds to setting ψ w (s, a) = 0 in our case. For the variance parameters θ 2 of the Gaussian policy, we use formula (19) for Linear and Quadratic, but (18) for MLP due to the difficulty of calculating the second order derivative ∇ a,a ψ w (s, a) in MLP. All the results we report are averaged over three random seeds. See Appendix for implementation details.

5.1. COMPARING THE VARIANCE OF DIFFERENT GRADIENT ESTIMATORS:

We start with comparing the variance of the gradient estimators with different control variates. Figure 1 shows the results on Walker2d-v1, when we take a fixed policy obtained by running the vanilla PPO for 2000 steps and evaluate the variance of the different gradient estimators under different sample size n. In order to obtain unbiased estimates of the variance, we estimate all the baseline functions using a hold-out dataset with a large sample size. We find that our methods, especially those using the MLP and Quadratic baselines, obtain significantly lower variance than the typical value function baseline methods. In our other experiments of policy optimization, we used the data from the current policy to estimate φ, which introduces a small bias theoretically, but was found to perform well empirically (see Appendix 7.4 for more discussion on this issue).

5.2. COMPARISON WITH Q-PROP USING TRPO FOR POLICY OPTIMIZATION:

Next we want to check whether our Stein control variate will improve the sample efficiency of policy gradient methods over existing control variate, e.g. Q-prop (Gu et al., 2016b) . One major advantage of Q-prop is that it can leverage the off-policy data to estimate q w (s, a). Here we compare our methods with the original implementation of Q-prop which incorporate this feature for policy optimization. Because the best existing version of Q-prop is implemented with TRPO, we implement a variant of our method with TRPO for fair comparison. The results on Hopper-v1 and Walker2d-v1 are shown in Figure 2 , where we find that all Stein control variates, even including FitQ+Linear and MinVar+Linear, outperform Q-prop on both tasks. This is somewhat surprising because the Q-prop compared here utilizes both on-policy and off-policy data to update w, while our methods use only on-policy data. We expect that we can further boost the performance by leveraging the offpolicy data properly, which we leave it for future work. In addition, we noticed that the Quadratic baseline generally does not perform as well as it promises in Figure 1 ; this is probably because that in the setting of policy training we optimize φ w for less number of iterations than what we do for evaluating a fixed policy in Figure 1 , and it seems that Quadratic requires more iterations than MLP to converge well in practice.

5.3. PPO WITH DIFFERENT CONTROL VARIATES:

Finally, we evaluate the different Stein control variates with the more recent proximal policy optimization (PPO) method which generally outperforms TRPO. We first test all the three types of φ listed above on Humanoid-v1 and HumanoidStandup-v1, and present the results in Table 1 . We can see that all the three types of Stein control variates consistently outperform the value function baseline, and Quadratic and MLP tend to outperform Linear in general.

We further evaluate our methods on a more extensive list of tasks shown in Figure 3 , where we only show the result of PPO+MinVar+MLP and PPO+FitQ+MLP which we find tend to perform the best according to Table 1 . We can see that our methods can significantly outperform PPO+Value which is the vanilla PPO with the typical value function baseline (Heess et al., 2017) .

It seems that MinVar tends to work better with MLP while FitQ works better with Quadratic in our settings. In general, we find that MinVar+MLP tends to perform the best in most cases. Note that the MinVar here is based on minimizing the approximate objective ( 27) specific to Gaussian policy, and it is possible that we can further improve the performance by directly minimizing the exact objective in (15) if an efficient implementation is made possible. We leave this a future direction. 

6. CONCLUSION:

We developed the Stein control variate, a new and general variance reduction method for obtaining sample efficiency in policy gradient methods. Our method generalizes several previous approaches. We demonstrated its practical advantages over existing methods, including Q-prop and value-function control variate, in several challenging RL tasks. In the future, we will investigate how to further boost the performance by utilizing the off-policy data, and search for more efficient ways to optimize φ. We would also like to point out that our method can be useful in other challenging optimization tasks such as variational inference and Bayesian optimization where gradient estimation from noisy data remains a major challenge.

7.1 PROOF OF THEOREM 3.1

Proof. Assume a = f θ (s, ξ) + ξ 0 where ξ 0 is Gaussian noise N (0, h 2 ) with a small variance h that we will take h → 0 + . Denote by π(a, ξ|s) the joint density function of (a, ξ) conditioned on s. It can be written as

π(a, ξ|s) = π(a|s, ξ)π(ξ) ∝ exp - 1 2h 2 ||a -f θ (s, ξ)|| 2 π(ξ).

Taking the derivative of log π(a, ξ|s) w.r.t. a gives ∇ a log π(a, ξ|s) = -1 h 2 (a -f θ (s, ξ)) . Similarly, taking the derivative of log π(a, ξ|s) w.r.t. θ, we have ∇ θ log π(a, ξ|s) = 1 h 2 ∇ θ f θ (s, ξ) (a -f θ (s, ξ)) = -∇ θ f θ (s, ξ)∇ a log π(a, ξ|s).

Multiplying both sides with φ(s, a) and taking the conditional expectation yield E π(a,ξ|s) ∇ θ log π(a, ξ|s)φ(s, a) = -E π(a,ξ|s) ∇ θ f θ (s, ξ)∇ a log π(a, ξ|s)φ(s, a)

= E π(ξ) ∇ θ f θ (s, ξ)E π(a|s,ξ) -∇ a log π(a, ξ|s)φ(s, a)

= E π(ξ) ∇ θ f θ (s, ξ)E π(a|s,ξ) ∇ a φ(s, a)

= E π(a,ξ|s) ∇ θ f θ (s, ξ)∇ a φ(s, a)

where the third equality comes from Stein's identity (5) of π(a|ξ, s). One the other hand, The above result does not depend on h, and hence holds when h → 0 + . This completes the proof.

7.2. ESTIMATING φ FOR GAUSSIAN POLICIES:

The parameters w in φ should be ideally estimated by minimizing the variance of the gradient estimator var(∇ θ J(θ)) using ( 15). Unfortunately, it is computationally slow and memory inefficient to directly solve (15) with the current deep learning platforms, due to the limitation of the auto-differentiation implementations. In general, this problem might be solved with a customized implementation of gradient calculation as a future work. But in the case of Gaussian policies, we find minimizing var( ∇µ J(θ)) + var( ∇Σ J(θ)) provides an approximation that we find works in our experiments. 

All experiments of PPO with Stein control variate selects the best learning rate from {0.001, 0.0005, 0.0001} for φ networks. We use ADAM (Kingma & Ba, 2014) for gradient descent and evaluate the policy every 20 iterations. Stein control variate is trained for the best iteration in range of {250, 300, 400, 500, 800}.

7.4 ESTIMATING φ USING DATA FROM PREVIOUS ITERATIONS Our experiments on policy optimization estimate φ based on the data from the current iteration.

Although this theoretically introduces a bias into the gradient estimator, we find it works well empirically in our experiments. In order to exam the effect of such bias, we tested a variant of PPO-MinVar-MLP which fits φ using data from the previous iteration, or previous two iterations, both of which do not introduce additional bias due to the dependency of φ on the data. Figure 4 shows the results in Hopper-v1 and Walker2d-v1, where we find that using the data from previous iterations does not seem to improve the result. The may be because during the policy optimization, the updates of φ are early stopped and hence do not introduce overfitting even when it is based on the data from the current iteration.

:



Figures and Tables:

Figure 1: The variance of gradient estimators of different control variates under a fixed policy obtained by running vanilla PPO for 200 iterations in the Walker2d-v1 environment.

Figure 2: Evaluation of TRPO with Q-prop and Stein control variates on Hopper-v1 and Walker2d-v1.

Figure 3: Evaluation of PPO with the value function baseline and Stein control variates across different Mujoco environments: HumanoidStandup

π(a,ξ|s) ∇ θ log π(a, ξ|s)φ(s, a) = E π(a,ξ|s) ∇ θ log π(a|s)φ(s, a) + E π(a,ξ|s) ∇ θ log π(ξ|s, a)φ(s, a)(22)= E π(a,ξ|s) ∇ θ log π(a|s)φ(s, a) ,(23)where the second term of (22) equals zero because E π(a,ξ|s) ∇ θ log π(ξ|s, a)φ(s, a) = E π(a|s) E π(ξ|s,a) ∇ θ log π(ξ|s, a)] φ(s, a) = 0. Combining (21) and (23) gives the result: E π(a|s) ∇ θ log π(a|s)φ(s, a) = E π(a,ξ|s) ∇ θ f θ (s, ξ)∇ a φ(s, a)

More specifically, recall that Gaussian policy has a form ofπ(a | s) ∝ 1 |Σ(s)| exp -1 2 (a -µ(s)) Σ(s) -1 (a -µ(s)) ,where µ(s) and Σ(s) are parametric functions of state s, and |Σ| is the determinant of Σ. Following Eq (8) we have∇ µ J(θ) = E π [-∇ a log π(a|s)(Q π (s, a) -φ(s, a)) + ∇ a φ(s, a)] ,

PPO with Control Variate through Stein's Identity (the PPO procedure is adapted from Algorithm 1 in Heess et al. 2017) repeat Run policy π θ for n timesteps, collecting {st, at, ξt, rt}, where ξt is the random seed that generates action at, i.e., at = f θ (st, ξt). Set πold ← π θ .

Table content: <table><tr><td>// Updating the baseline function φ</td></tr><tr><td>for K iterations do</td></tr><tr><td>Update w by one stochastic gradient descent step according to (14), or (15), or (27) for Gaussian</td></tr><tr><td>policies.</td></tr><tr><td>end for</td></tr><tr><td>// Updating the policy π</td></tr><tr><td>for M iterations do</td></tr><tr><td>Update θ by one stochastic gradient descent step with (20) (adapting it with (</td></tr></table>

Results of different control variates and methods for optimizing φ, when combined with PPO. The reported results are the average reward at the 10000k-th time step on Humanoid-v1 and the 5000k-th time step on HumanoidStandup-v1.

Table content: <table><tr><td/><td colspan="2">Humanoid-v1</td><td colspan="2">HumanoidStandup-v1</td></tr><tr><td>Function</td><td>MinVar</td><td>FitQ</td><td>MinVar</td><td>FitQ</td></tr><tr><td>MLP</td><td colspan="3">3847 ± 249.3 3847 ± 249.3 3847 ± 249.3 3334 ± 695.7 143314 ± 9471 143314 ± 9471 143314 ± 9471</td><td>139315 ± 10527</td></tr><tr><td colspan="4">Quadratic 2356 ± 294.7 3563 ± 235.1 3563 ± 235.1 3563 ± 235.1 117962 ± 5798</td><td>141692 ± 3489 141692 ± 3489 141692 ± 3489</td></tr><tr><td>Linear</td><td colspan="4">2547 ± 701.8 3404 ± 813.1 129393 ± 18574 132112 ± 11450</td></tr><tr><td>Value</td><td colspan="2">2207 ± 554</td><td colspan="2">128765 ± 13440</td></tr></table>

Peer review (iclr2018):
 This paper proposed a class of control variate methods based on Stein*s identity. Stein*s identity has been widely used in classical statistics and recently in statistical machine learning literature. Nevertheless, applying Stein*s identity to estimating policy gradient is a novel approach in reinforcement learning community. To me, this approach is the right way of constructing control variates for estimating policy gradient. The authors also did a good job in connecting with existing works and gave concrete examples for Gaussian policies. The experimental results also look promising. It would be nice to include some theoretical analyses like under what conditions, the proposed method can achieve smaller sample complexity than existing works. Overall this is a strong paper and I recommend to accept.