Title: A BETTER BASELINE FOR SECOND ORDER GRADIENT ESTIMATION IN STOCHASTIC COMPUTATION GRAPHS Anonymous authors Paper under double-blind review

Abstract: Motivated by the need for higher order gradients in multi-agent reinforcement learning and meta-learning, this paper studies the construction of baselines for second order Monte Carlo gradient estimators in order to reduce the sample variance. Following the construction of a stochastic computation graph (SCG), the Infinitely Differentiable Monte-Carlo Estimator (DiCE) can generate correct estimates of arbitrary order gradients through differentiation. However, a baseline term that serves as a control variate for reducing variance is currently provided only for first order gradient estimation, limiting the utility of higher-order gradient estimates. To improve the sample efficiency of DiCE, we propose a new baseline term for higher order gradient estimation. This term may be easily included in the objective, and produces unbiased variance-reduced estimators under (automatic) differentiation, without affecting the estimate of the objective itself or of the first order gradient. Importantly it reuses the same baseline function (e.g. the state-value function in reinforcement learning) already used for the first order baseline. We provide theoretical analysis and numerical evaluations of our baseline term, which demonstrate that it can dramatically reduce the variance of second order gradient estimators produced by DiCE. This computational tool can be easily used to estimate second order gradients with unprecedented efficiency wherever automatic differentiation is utilised, and has the potential to unlock applications of higher order gradients in reinforcement learning and meta-learning.

1. INTRODUCTION:

Problems that have intractable stochasticity often give rise to objectives that are not directly differentiable. In reinforcement learning, for example, the expected return involves an expectation over the stochasticity induced by both the policy and the environment dynamics. As a result, the gradient of this objective with respect to the policy parameters cannot be directly calculated. However, we may construct Monte Carlo estimates of the gradient from samples, and then apply gradient-based optimisation methods. In such problems, the score function trick (Fu, 2006 ) may be used to easily define estimates of the first order gradients of the stochastic objective. However, to calculate these gradient estimates in practice, we need to leverage the powerful toolbox of automatic differentiation. To this end, Schulman et al. (2015) introduce the surrogate loss (SL) within the formalism of stochastic computation graphs (SCG). Under single differentiation the SL produces an unbiased gradient estimator for the first order gradient of the primary objective.

Estimating higher order gradients of these stochastic objectives is important in many settings. One example is in multi-agent learning. In Learning with Opponent-Learning Awareness (LOLA) (Foerster et al., 2018a) , the expected return of one agent is differentiated through the learning step of another agent. Another use-case is the combination of meta-learning with gradient-based methods applied to reinforcement learning (Finn et al., 2017; Al-Shedivat et al., 2017) , as the objective function is repeatedly differentiated through a hierarchy of learning processes. Lastly, higher order gradients may be used directly for some optimisation algorithms, such as the quasi-Newton algorithm (Wright & Nocedal, 1999) .

Despite the success of higher order gradients in these applications, accurate and efficient estimation of higher order gradients is challenging. This is due to the complexity of constructing the corresponding estimators, as well as their extremely high variance. It is therefore critical to develop methods that produce low variance estimates of higher order gradients and are easy to use in practice through automatic differentiation. One way to reduce variance of stochastic estimators is by introducing control variates (Paisley et al., 2012; Tucker et al., 2017; Grathwohl et al., 2017) . The key contribution of this work is the design of a variance reduction technique for higher order gradient estimators based on the control variate framework and amenable to automatic differentiation.

Given an objective function with random variables, the naive approach is to derive the corresponding higher order gradient estimators analytically. Al-Shedivat et al. (2017) use the score function estimator repeatedly to obtain proper estimators for higher orders in a meta-learning setting. Foerster et al. (2018a) combine this approach with Taylor expansion to generate higher order gradient estimators in a multi-agent setting. However, this approach is difficult to generalise to arbitrary objective functions, as well as being error-prone and incompatible with automatic differentiation. Schulman et al. (2015) argue that the gradient estimate produced by differentiating an SL objective may be treated as an objective itself, and a new SL can be built to estimate higher order gradients. Unfortunately, as shown by Foerster et al. (2018b) , this approach can produce incorrect higher order gradient estimates because the cost terms are treated as fixed samples in the SL, and so it does not maintain all necessary dependencies in the SCG after differentiation. Foerster et al. (2018b) propose the Infinitely Differentiable Monte-Carlo Estimator (DiCE) to estimate higher order gradients correctly while maintaining the ease of use by leveraging automatic differentiation. DiCE uses two methods to reduce the variance of its first order gradient estimates. First, it respects the causal dependence of costs on stochastic events that can influence them, and second, it implements a simple baseline method. However, the higher order gradient estimates generated by DiCE still have high variance, and their quality relies on a large number of samples.

In this paper, we design a novel baseline term for second-order gradient estimation based on DiCE. This term can be easily included in the original objective without changing the estimate of the objective itself or of the first order gradients. Nonetheless, appropriate control variates for the higher order gradients are produced automatically upon repeated differentiation of the modified objective. In this baseline term, we include an additional dependence which properly captures the causal relationship between stochastic nodes in an SCG. Using the DiCE approach, we are able to preserve these dependencies through differentiation. We prove that adding our baseline term to the DiCE objective will not affect the expected estimate of second order gradients. We explicitly derive the second order gradients of the DiCE objective with our baseline term in order to demonstrate how it introduces control variates for higher order gradient estimates. Additionally, we conduct a series of numerical evaluations to verify the correctness of our baseline term and show its effectiveness for variance reduction. We believe that our baseline term is an important missing component to make DiCE an extremely powerful and valuable tool to access higher order gradients in reinforcement learning and meta-learning.

2. BACKGROUND:

Suppose x is a random variable distributed as x ∼ p(x; θ), and f (x) is a deterministic function of x. We assume that f (x) is independent of θ so that ∇ n θ f = 0 for n ∈ {1, 2, . . . }. Suppose we have the objective function L(θ) = E x [f (x)] and we need to compute the gradients of the expectation,

∇ θ E x [f (x)]

, in order to use gradient-based optimization methods. An unbiased gradient estimator

g is a random variable such that E[g(f )] = ∇ θ E[f (x)].

The score function estimator (Fu, 2006 ) is an unbiased estimator given by

E x [f (x)∇ θ log p(x; θ)] = ∇ θ E x [f (x)].

(1)

The control variates method is a variance reduction technique for improving the efficiency of Monte Carlo estimators. A control variate is a function c(x) whose value can be easily obtained, and whose expectation E[c(x)] is known. Using the control variate, we can construct a new random variable

EQUATION

The expectation of the random variable z(f ) is

E[z(f )] = E x [g(f )] -E x [c(x)] + E x [c(x)] = E x [f (x)].

Consequently, if g(f ) is an unbiased estimator of the gradient, so is z(f ). However, if the random variables g(f ) and z(f ) are positively correlated, the variance of z(f ) can be lower than that of g(f ) (Grathwohl et al., 2017) .

2.1. STOCHASTIC COMPUTATION GRAPHS:

A stochastic computation graph (SCG) (Schulman et al., 2015) is a directed and acyclic graph that consists of three types of nodes:

1. Input nodes Θ: an input node θ ∈ Θ contains parameters set externally. We may be interested in the dependence of an objective function on these nodes, and will attempt to differentiate the objective with respect to their parameters. 2. Deterministic nodes D: a deterministic node d ∈ D is a deterministic function of its parent nodes. 3. Stochastic nodes S: a stochastic node w ∈ S is a random variable whose distribution is conditioned on its parent nodes.

Additionally, cost nodes C can be added into the formalism of an SCG without loss of generality. A cost node c ∈ C is a determinstic function of its parent nodes that produces a scalar value. The set of cost nodes C are those associated with an objective function

L = E[ c∈C c].

In an SCG, (v, w) is a directed edge that connects node v and non-input node w, where v is a parent node of w. The notation v ≺ w means there is a path from node v to node w, i.e., node v influences node w.

2.2. DICE:

In order to estimate higher order gradients correctly, Foerster et al. (2018b) propose the Infinitely Differentiable Monte-Carlo Estimator (DiCE) within the formalism of SCGs. DiCE uses the magic box as a novel operator. The input to is a set of stochastic nodes W, and is designed to have the following properties:

1. (W) 1, 2. ∇ θ (W) = (W) w∈W ∇ θ log p(w; θ).

Here means "evaluates to", which is different from "equals to", =, i.e., full equality including equality of all derivatives. In the context of a computation graph, denotes a forward pass evaluation. In contrast, the second property describes the behaviour of under differentiation. The right hand side of this equality can in turn be evaluated to estimate gradients as described below, or differentiated further. To achieve these properties, Foerster et al. (2018b) show that can be straightforwardly implemented as follows:

(W) = exp(τ -⊥(τ )),

where τ = w∈W ∇ θ log p(w; θ) and ⊥ is a 'stop-grad' operator that sets the derivative to zero, ∇ x ⊥(x) = 0, as it is commonly available in auto-differentiation libraries. This implementation will give us the required properties of the magic box operator in practice.

For a node w in an SCG, we use S w to denote the set of stochastic nodes that influence the node w and are influenced by θ, i.e., S w = {s|s ∈ S, s ≺ w, θ ≺ s}. Using , the DiCE objective (Foerster et al., 2018b) is defined as

L = c∈C (S c )c.

(3)

Under repeated differentiation the DiCE objective generates arbitrary order gradient estimators (Foerster et al., 2018b, Theorem 1):

E[∇ n θ L ] ∇ n θ L, for n ∈ {0, 1, 2, . . . }.

2.3. VARIANCE REDUCTION WITH DICE:

L by itself already implements a simple form of variance reduction by respecting causality. In gradient estimates, each cost node c is multiplied by the sum of gradients of log-probabilities of only upstream nodes S c that can influence c. This reduces variance compared to using the log joint probability of all stochastic nodes, which would still create an unbiased gradient estimate.

However, Foerster et al. (2018b) offer additional variance reduction for first-order gradient estimation by including a baseline

EQUATION

where b w1 is a function of the set NONINFLUENCED(w) = {v|w ⊀ v}, i.e. the set of nodes that does not influence w. Here b w may be chosen to reduce variance, and a common choice for b w is the average cost-to-go, i.e. E[R w |NONINFLUENCED(w))]. Here R w = c∈Cw c, where C w = {c|c ∈ C, w ≺ c}, i.e., the set of cost nodes that depend on node w. 2 In order to maintain unbiased gradient estimates, the baseline factor b w should be a function that is independent of the stochastic node w. Greensmith et al. (2004) provide an overview of variance reduction techniques for gradient estimators, including the use of this type of baseline. The baseline term B

(1) can be added to the DiCE objective to obtain

EQUATION

)

Note that L b1 evaluates to the same value as L because (1 -(W)) 0.

3. METHOD:

First, consider explicitly the effect of the traditional baseline on the first order gradient estimates.

The estimates without and with baseline are as follows (derivations given in Appendix A.1):

EQUATION

For each stochastic node w ∈ S, the term b w ∇ θ log p(w; θ) works as a control variate to reduce the variance of the term R w ∇ θ log p(w; θ). To ensure the appropriate correlations, b w may be a function trained to estimate E[R w |NONINFLUENCED(w))]. As a result, ∇ θ L b1 is a first order gradient estimator with lower variance than

∇ θ L . Additionally, ∇ θ L b1 is unbiased because E[∇ θ B (1) ] 0 (see Appendix A.1).

Note that in (6) we have omitted a term, c∈C ∇ θ c, that arises when the cost nodes depend directly on θ. In most use-cases this term will not appear, as the costs are sampled from an unparameterised process, such as the unkown environment in reinforcement learning. This straight-through contribution to the gradient estimate is also typically much lower variance than the contribution estimated using the score function trick. Due to these considerations, we assume that the costs are independent of θ in the remainder of this work, although the remaining terms for both first and second order are derived in the appendix.

Next, we consider second-order gradient estimation using the objective L b1 . The second order gradient of the DiCE objective can be evaluated as follows (derivations given in Appendix A.2):

∇ 2 θ L w∈S R w ∇ 2 θ p(w; θ) p(w; θ) + 2 w∈S ∇ θ log p(w; θ) v∈S,w≺v R v ∇ θ log p(v; θ) , ∇ 2 θ L b1 w∈S (R w -b w ) ∇ 2 θ p(w; θ) p(w; θ) + 2 w∈S ∇ θ log p(w; θ) v∈S,w≺v R v ∇ θ log p(v; θ) . (7)

The baseline objective function L b1 still implements a partial variance reduction in the second order gradient estimates, by providing a control variate for the first term in (7). However, the R v in the second term are not paired with suitable control variates. As a result, the variance of this term could be extremely high. In fact, due to the nested summations over the high-variance R v , this term can dominate the variance of total gradient estimate. We explore this empirically in section 4, where we observe that B

(1) is of little use for reducing the overall variance of the second order gradient estimates.

3.1. A SECOND ORDER BASELINE:

To substantially reduce variance for the second order gradient estimator, we propose a new baseline:

EQUATION

Here S = {w|w ∈ S, S w = ∅, θ ≺ w}, i.e., the set of stochastic nodes that depend on θ and at least one other stochastic node. Note that B

(2)

0 because (1 -({w})) 0 and (1 -(S w )) 0,

and b w is the same as that used in B 1) . The new DiCE objective function becomes:

EQUATION

Since B

(1) 0 and B

(2) 0, L , L b1 , and L b2 all evaluate to the same estimate of the original objective. Further, all derivatives of our modified objective L b2 are unbiased estimators of the derivatives of the original objective, that now contain suitable control variates for variance reduction. We now show how this baseline term indeed leads to a lower variance while still being an unbiased estimate for the higher order derivatives of our objective.

3.2. BIAS AND VARIANCE ANALYSIS:

In the DiCE objective L , for each cost node c ∈ C, the corresponding (S c ) reflects the dependency of c on all stochastic nodes which influence it (and depend on θ). In contrast, the baseline term B

(1) only includes ({w}), considering each stochastic node w separately. This simple approach results in variance reduction for first order gradients, as shown in (6). However, the failure to capture the dependence of stochastic nodes on each other in the simple baseline prevents it from reducing the variance of the cross terms that arise in second order derivatives (the final term in ( 7)). To capture these relationships properly, we include (S w ) in the definition of B

(2) , i.e., an additional dependence on the stochastic nodes that influence w. Use of the operator ensures that these dependencies are preserved through differentiation.

To verify that our proposed baseline indeed captures these dependencies appropriately, we now consider its impact on the gradient estimates. The first and second order gradients of the baseline term B

(2) can be evaluated as follows (derivations given in Appendix A.2):

EQUATION

The first order gradient estimates remain unchanged: as ∇ θ B

(2) 0, ∇ θ L b2 evaluates to the same value as ∇ θ L b1 . The second order gradient estimate of our full objective, ∇ 2 θ L b2 , is as follows:

EQUATION

Control variates have been introduced for the terms in the second part of (11), when using our new baseline term B

(2) . R w and b w are positively correlated by design, as they should be for variance reduction of the first order gradients. As a result, the estimator ∇ 2 θ L b2 could have significantly lower variance compared with ∇ 2 θ L b1 and ∇ 2 θ L , as we verify empirically in Section 4. Furthermore, we verify that our baseline does not change the expected estimate of second order derivatives.

Theorem 1. E ∇ 2 θ L b2 ∇ 2 θ E L . Proof. First, we can prove that E[∇ 2 θ B (1) ] 0 and E[∇ 2 θ B (2) ] 0 (See Appendix). Since ∇ 2 θ L is an unbiased estimator of ∇ 2 θ E L , i.e., ∇ 2 θ L ∇ 2 θ E L , then: E ∇ 2 θ L b2 = E ∇ 2 θ L + E ∇ 2 θ B (1) -E ∇ 2 θ B (2) ∇ 2 θ E L .

Thus, ∇ 2 θ L b is an unbiased second order gradient estimator of the original objective E L .

3.3. REINFORCEMENT LEARNING:

We now consider the particular case of reinforcement learning. Given a policy π, we can generate an episode of horizon T : τ = (s 0 , a 0 , r 0 , . . . , s T , a T , r T ).

The discounted return at time step t is the discounted sum of future rewards, R t (τ ) = T k=t γ k-t r t , where γ ∈ [0, 1] is a discount factor. When the reinforcement learning problem is formalised as an SCG, the cost nodes are the discounted rewards and the objective function is

L = E[ T t=0 γ t r t ].

The corresponding DiCE objective function is:

EQUATION

)

where a t ≤t is the set of all previous actions at time step t, i.e., a t ≤t = {a 0 , a 1 , . . . , a t }. Clearly, these are the stochastic nodes that influence the reward at time t. We choose the baseline b(s t ) to be a function of state s t ; it must be independent of the action a t . In particular, we choose b(s t ) = γ t V (s t ), where V (s t ) is an estimate of the state value function

V π (s t ) = E[R t |s t ].

First order variance reduction may now be achieved with the baseline term:

EQUATION

)

To reduce the variance of the second order gradient estimators, we can use our novel baseline term:

EQUATION

)

These baseline terms can be added to our original objective. As in the general case, the corresponding DiCE objectives with baselines are 1) and 2) .

EQUATION

EQUATION

In (a t <t ), we need to have strict inequality t < t, which captures the causality from all previous actions. The agent is able to look backward at its past actions but excludes its current action. Since there is no previous action at t = 0, the summation runs from t = 1 to t = T . It is essential to exclude the current action a t at time step t for variance reduction because the baseline b(s t ) must be independent of the action a t to remain unbiased. Note that this does not leave a term in the gradient estimate without a control variate: the "diagonal" term corresponding to only the action at t = 0 is already addressed by the second derivative of B

(1) and appears in the first term in (11).

4. EXPERIMENTS:

First, we numerically verify that DiCE with our new baseline term L b2 can generate correct estimators of the Hessians in an SCG using a set of randomly initialised fixed policies in the iterated prisoner's dilemma.

In this setting, two agents play the game of the prisoner's dilemma iteratively. At each round, there are two possible actions for each agent, which are Cooperate (C) and Defect (D). As a result, there are four possible outcomes, CC, CD, DC, and DD at each round, which are the observation at the next time step. The payoff matrix of this game is given in Figure 1 .

C D C -1 0 -1 -3 D -3 -2 0 -2

Figure 1 : The payoff matrix of prisoner's dilemma. Numbers in a cell correspond to the utilities of the player with the same colour.

Multi-agent DiCE. The objective function for agent i is

L i = E[ T t=0 γ t r i t ].

The per-agent DiCE objective L i is a simple extension of ( 12), replacing r t by the per-agent reward r i t , and a t by the joint action a j∈{1,2} t

. For correct higher order gradients it is essential to consider the dependence of the reward on the actions of both agents in this way. We will require per-agent baseline factors b i (s t ) to then form per-agent baseline terms B

i,(1) and B i,(2) in analogy with (13, 14) . Again, the single-agent action at each timestep is replaced by the joint action.

Using DiCE, the dependencies between the returns and parameters of the two agents are accounted for, and first and second order gradients can be estimated efficiently using automatic differentiation. We will test and compare the performance of L b1,i and L b2,i in second-order gradient estimation. Foerster et al. (2018a) derive the value function of IPD analytically, which we use as ground truth to verify the correctness of our estimator. Figure 2 (b) shows that we can obtain correct secondorder gradient estimates using our baseline term. Comparing to Figure 2 (a), our novel baseline term dramatically improves the estimation of second order gradients. In the original DiCE paper (Foerster et al., 2018b) , a sample size of 100k is required to obtain second order gradient estimates with correlation coefficient 0.97. After formulating our baseline term, the required sample size is reduced to 1k, a reduction by two orders of magnitude. Figure 3 shows the correlation coefficients of the exact Hessian and the estimated Hessian using different sample sizes. These results demonstrate that our baseline term is important for estimating second order gradients accurately and efficiently when using DiCE. Under review as a conference paper at ICLR 2019 LOLA-DiCE. In LOLA-DiCE (Foerster et al., 2018b) agents differentiate through the learning step of other agents, using the DiCE objective to calculate higher order derivatives:

L 1 (θ 1 , θ 2 ) LOLA = E π θ 1 ,π θ 2 +∆θ2(θ1,θ2) [ T t=0 γ t r 1 t ],

where (2),i . The error bar shows the standard deviation. Figure 4 shows the performance of LOLA-DiCE with and without our second order baseline. We find that without the second order baseline agents fail to learn, resulting in an average per-step return of around -1.6, close to that of a random policy which achieves -1.5. Using a two times smaller batch size (32 vs 64), performance is comparable to what was achieved in the original work. However, our results using the first order baseline are much worse than what is reported in the original work, albeit at a smaller batch size. In communication with the authors we established that those results were produced by making the rewards at each timestep zero-mean within each batch, rather than relying on the first order baseline. In settings where the value function is mostly independent of the state, which happens to be the case in the IPD with a large γ, this simple trick can produce variance reduction similar to what we achieve with our second order baseline. However, this ad-hoc normalisation would fail in a setting with sparser rewards or, in general, in settings where the value function strongly depends on the current state.

∆θ 2 (θ 1 , θ 2 ) = α 2 ∇ θ2 E π θ 1 ,π θ 2 [ T t=0 γ t r 2 t ]

5. CONCLUSION:

Recent progress in multi-agent reinforcement learning and meta-learning has lead to a variety of approaches that employ second order gradient estimators. While these are easy to construct through the recently introduced DiCE objective (Foerster et al., 2018b) , the high variance of second order gradient estimators has prevented their widespread application in practice. By reusing the DiCE formalism, we introduce a baseline for second order gradient estimators in stochastic computation graphs. Similar to DiCE, this baseline is automatically constructed from user-defined objectives using automatic differentiation frameworks, making it straightforward to use in practice. Our baseline does not change the expected value of any derivatives. We demonstrate empirically that our new baseline dramatically improves second order gradient estimation in a multi-agent task, reducing the required sample size by two orders of magnitude. We believe that low-variance second order gradient estimators will unlock a large variety of reinforcement learning and meta-learning applications in the future. Furthermore, we would like to extend the approach to deal with settings where the costs depend directly on the parameters. Lastly, we are interested in extending our framework to a baseline-generating term for any-order gradient estimators.

A APPENDIX:

A.1 FIRST ORDER GRADIENTS DiCE Objectice. 

∇ θ L = c∈C ∇ θ (S c ) • c = c∈C c • ∇ θ (S c ) + c∈C (S c ) • ∇ θ c = c∈C c • (S c ) w∈Sc ∇ θ log p(w; θ)) + c∈C (S c ) • ∇ θ c w∈S c∈C 1 (w≺c) c • ∇ θ log

:

b(NONINFLUENCED(w)) in(Schulman et al.,

2015)2 We use the Rw notation to correspond with a return for readers familiar with reinforcement learning, a key use case. The cost notation for nodes is kept to maintain consistency withSchulman et al. (2015).

Figures and Tables:

(a) Flattened Hessian (green) of L b 1 ,1 . The correlation coefficient is 0.29. (b) Flattened Hessian (blue) of L b 2 ,1 . The correlation coefficient is 0.97.

Figure 2: Flattened true (Red) and estimated Hessian of agent 1 for the iterated prisoner's dilemma. The sample size is 1000.

and α 2 is a step size. Training details are provided in Appendix A.3.

Figure 3: The correlation coefficients of the exact Hessian and the estimated Hessian generated from the multi-agent DiCE objective function with (orange) and without (blue) the second order baseline term B(2),i . The error bar shows the standard deviation.

Figure 4: The performance of the LOLA-DiCE algorithm on the IPD with (blue) and without (red) the new second order baseline. Shading indicates the error of the mean.

θ log p(w; θ)+ c∈C ∇ θ c.When the cost nodes does not depend on θ directly, we have ∇ θ c = 0. Thus,∇ θ L w∈S R w ∇ θ log p(w; θ).Baseline Terms. For the first baseline term, {w})∇ θ log p(w; θ)-w∈S b w ∇ θ log p(w; θ). (15)We can consider a single term in (15),E[b w ∇ θ log p(w; θ)] 1 -(S w ) ∇ θ ({w}) -1 -({w}) ∇ θ (S w ) c ) • c = c∈C c • ∇ 2 θ (S c ) A + c∈C 2∇ θ c • ∇ θ (S c ) a t ) (∇ θ log p(w; θ)) 2 + ∇ 2 θ log p(w; θ) -w∈S b w (∇ θ log p(w; θ)) 2 + ∇ 2 θ log p(w; θ) ) • 1 -(S w ) -1 -({w}) • ∇ 2 θ (S w ) + 2 ({w})∇ θ log p(w; θ) • (S w ) v∈Sw ∇ θ log p(v; θ) 2 w∈S b w ∇ θ log p(w; θ) v∈Sw ∇ θ log p(v; θ) ) b w ∇ θ log p(w; θ) • ∇ θ log p(v; θ) = 2 v∈S w∈Sv,v≺w b w ∇ θ log p(w; θ) ∇ θ log p(v; θ) θ log p(w; θ) • b w .(17)Next, we consider the expectation of a single term in (17)E ∇ θ log p(v; θ) w∈Sv,v≺w b w ∇ θ log p(w; θ) = E E ∇ θ log p(v; θ) w∈Sv,v≺w b w ∇ θ log p(w; θ) v = E ∇ θ log p(v; θ) w∈Sv,v≺w b w E ∇ log p(w; θ) v = 0because E ∇ θ log p(w; θ) v = 0 where v ≺ w. According to the linearity of expectations, we can obtain that E[∇ 2 θ B ] 0.

Peer review (iclr2019):
 Overview: This nicely written paper contributes a useful variance reduction baseline to make the recent formalism of the DiCE estimator more practical in application. I assess the novelty and scale of the current contribution as too low for publication at ICLR. Also, the paper includes a few incorrect assertions regarding the control variate framework as well as action-dependent baselines in reinforcement learning. Such issues reduce the value of the contribution in its current form and may contribute to ongoing misunderstandings of the control variate framework and action-dependent baselines in RL, to the detriment of variance reduction techniques in machine learning. I do not recommend publication at this time. Pros: The paper is well written modulo the issues discussed below. It strikes me as a valuable workshop contribution once the errors are addressed, but it lacks enough novelty for the main conference track. Issues: * (p.5) "R_w and b_w are positively correlated by design, as they should be for variance reduction of the first order gradients." This statement is not true in general. Intuitively, a control variate reduces variance because when a single estimate of an expectation of a function diverges from its true value according to some delta, then, with high probability, some function strongly correlated with that function will also diverge with a similar delta. Such a delta might be positive or negative, so long as the error may be appropriately modeled as drawn from some symmetric distribution (i.e. is Gaussian). Control variates are often estimated with an optimal scaling constant that depends on the covariance of the original function and its control variate. Due to the dependence on the covariance, the scaling constant flips sign as appropriate in order reduce variance for any delta. For more information, see the chapter on variance reduction and subsection on control variates in Sheldon Ross*s textbook "Simulation." The fact that a control variate appears to work despite this is not surprising. Biased and suboptimal unbiased gradient estimators have been shown to work well for reasons not fully explored in the literature yet. See, for example, Tucker et al.*s "Mirage of Action-Dependent Baselines", https://arxiv.org/abs/1802.10031. Since the authors claim on page 6 that the baseline is positively correlated by design, this misunderstanding of the control variate framework appears to be baked into the baseline itself. I recommend the authors look into adaptively estimating an optimal scale for the baseline using a rolling estimator of the covariance and variance to fix this issue. See the Ross book cited above for full derivation of this optimal scale. * The second error is a mischaracterization of the use and utility of action-dependent baselines for RL problems, on page 6: "We choose the baseline ... to be a function of state ... it must be independent of the action ...." and "it is essential to exclude the current action ... because the baselines ... must be independent of the action ... to remain unbiased." In the past year, a slew of papers have presented techniques for the use of action-dependent baselines, with mixed results (see the Mirage paper just cited), including two of the papers the authors cited. Cons * Much of paper revises the DiCE estimator results, arguing for and explaining again those results rather than referring to them as a citation. * I assess the novelty of proposed contribution as too low for publication. The baseline is an extension of the same method used in the original paper, and does not generalize past the second order gradient, making the promising formalism of the DiCE estimator as infinitely differentiable still unrealizable in practice. * The experiments are practically identical to the DiCE estimator paper, also reducing the novelty and contribution of the paper. *EDIT: I thank the authors for a careful point-by-point comparison of our disagreements on this paper so that we may continue the discussion. However, none of the points I identified were addressed, and so I maintain my original score and urge against publication. In their rebuttal, the authors have defended errors and misrepresentations in the original submission, and so I provide a detailed response to each of the numbered issues below: (1) I acknowledge that it is common to set c=1 in experiments. This is not the same as the misstatements I cited, verbatim, in the paper that suggest this is required for variance reduction. My aim in identifying these mistakes is not to shame the authors (they appear to simply be typos) but simply to ensure that future work in this area begins with a correct understanding of the theory. I request again that the authors revise the cited lines that incorrectly state the reliance of a control variate on positive correlation. It is not enough to state that "everyone knows" what is meant when the actual claim is misleading. (2) Without more empirical investigation, the authors* new claim that a strictly state-value-function baseline is a strength rather than a weakness cannot be evaluated. This may be the case, and I would welcome some set of experiments that establish this empirical claim by comparing against state-action-dependent baselines. The authors appear to believe that state-action-dependent baselines are never effective in reducing variance, and this is perhaps the central error in the paper that should be addressed. See response (3). Were the authors to fix this, they would necessarily compare against state-action-dependent baselines, which would be of great value for the community at large in settling this open issue. (3) Action-dependent baselines have not been shown to be ineffective. I wish to strongly emphasize that this is not the conclusion of the Mirage paper, and the claim repeated in the authors* response (3) has not been validated empirically or analytically, and does not represent the state of variance reduction in reinforcement learning as of this note. I repeat a few key arguments from the Mirage paper in an attempt to dispel the authors* repeated misinterpretation of the paper. The variance of the policy gradient estimator, subject to a baseline "phi," is decomposed using the Law of Total Variance in Eq (3) of the Mirage paper. This decomposition identifies a non-zero contribution from "phi(a,s)", the (adaptive or non-adaptive) baseline. The Mirage paper analyzes under what conditions such a contribution is expected to be non-negligible. Quoting from the paper: "We expect this to be the case when single actions have a large effect on the overall discounted return (e.g., in a Cliffworld domain, where a single action could cause the agent to fall of the cliff and suffer a large negative reward)." Please see Sec. 3, "Policy Gradient Variance Decomposition" of the Mirage paper for further details. The Mirage paper does indeed cast reasonable doubt on subsets of a few papers* experiments, and shows that the strong claim, mistakenly made by these papers, that state-action-dependence is always required for an adaptive control variate to reduce variance over state dependence, is not true. It should be clear from the discussion of the paper to this point that this does _not_ imply the even stronger claim in "A Better Second Order Baseline" that action dependence is never effective and should no longer be considered as a means to reduce variance from a practitioner*s point of view. Such a misinterpretation should not be legitimized through publication, as it will muddy the waters in future research. I again urge the authors to remove this mistake from the paper. (4) I acknowledge the efforts of the authors to ensure that adequate background is provided for readers. This is a thorny issue, and it is difficult to balance in any work. Since this material represents a sizeable chunk of the paper and is nearly identical to existing published work, it leads me to lower the score for novelty of contribution simply by that fact. Perhaps the authors could have considered placing the extensive background materials in the appendix and instead summarizing them briefly in the body of the paper, leaving more room for discussion and experimental validation beyond the synthetic cases already studied in the DiCE paper. (5), (6) In my review I provided specific, objective criteria by which I have assessed the novelty of this paper: the lack of original written material, and the nearly identical experiments to the DiCE paper. As I noted in response (4) above, this reduces space for further analysis and experimentation.