Title: BACKPROPAGATION THROUGH THE VOID: OPTIMIZING CONTROL VARIATES FOR BLACK-BOX GRADIENT ESTIMATION

Abstract: Gradient-based optimization is the foundation of deep learning and reinforcement learning, but is difficult to apply when the mechanism being optimized is unknown or not differentiable. We introduce a general framework for learning low-variance, unbiased gradient estimators, applicable to black-box functions of discrete or continuous random variables. Our method uses gradients of a surrogate neural network to construct a control variate, which is optimized jointly with the original parameters. We demonstrate this framework for training discrete latent-variable models. We also give an unbiased, action-conditional extension of the advantage actor-critic reinforcement learning algorithm.

1. INTRODUCTION:

Gradient-based optimization has been key to most recent advances in machine learning and reinforcement learning. The back-propagation algorithm (Rumelhart & Hinton, 1986) , also known as reverse-mode automatic differentiation (Speelpenning, 1980; Rall, 1981) computes exact gradients of deterministic, differentiable objective functions. The reparameterization trick (Williams, 1992; Kingma & Welling, 2014; Rezende et al., 2014) allows backpropagation to give unbiased, lowvariance estimates of gradients of expectations of continuous random variables. This has allowed effective stochastic optimization of large probabilistic latent-variable models.

Unfortunately, there are many objective functions relevant to the machine learning community for which backpropagation cannot be applied. In reinforcement learning, for example, the function being optimized is unknown to the agent and is treated as a black box (Schulman et al., 2015a) . Similarly, when fitting probabilistic models with discrete latent variables, discrete sampling operations create discontinuities giving the objective function zero gradient with respect to its parameters. Much recent work has been devoted to constructing gradient estimators for these situations. In reinforcement learning, advantage actor-critic methods (Sutton et al., 2000) give unbiased gradient estimates with reduced variance obtained by jointly optimizing the policy parameters with an estimate of the value function. In discrete latent-variable models, low-variance but biased gradient estimates can be given by continuous relaxations of discrete variables (Maddison et al., 2016; Jang et al., 2016) .

A recent advance by Tucker et al. (2017) used a continuous relaxation of discrete random variables to build an unbiased and lower-variance gradient estimator, and showed how to tune the free parameters of these relaxations to minimize the estimator's variance during training. We generalize the method of Tucker et al. (2017) to learn a free-form control variate parameterized by a neural network. This gives a lower-variance, unbiased gradient estimator which can be applied to a wider variety of problems. Most notably, our method is applicable even when no continuous relaxation is available, as in reinforcement learning or black-box function optimization.

2. BACKGROUND: GRADIENT ESTIMATORS:

How can we choose the parameters of a distribution to maximize an expectation? This problem comes up in reinforcement learning, where we must choose the parameters θ of a policy distribution π(a|s, θ) to maximize the expected reward E τ ∼π [R] over state-action trajectories τ . It also comes up in fitting latent-variable models, when we wish to maximize the marginal probability p(x|θ) = z p(x|z)p(z|θ) = E p(z|θ) [p(x|z) ]. In this paper, we'll consider the general problem of optimizing

EQUATION

When the parameters θ are high-dimensional, gradient-based optimization is appealing because it provides information about how to adjust each parameter individually. Stochastic optimization is essential for scalablility, but is only guaranteed to converge to a fixed point of the objective when the stochastic gradients ĝ are unbiased, i.e. E [ĝ] = ∂ ∂θ L(θ) (Robbins & Monro, 1951) . How can we build unbiased, stochastic gradient estimators? There are several standard methods:

The score-function gradient estimator One of the most generally-applicable gradient estimators is known as the score-function estimator, or REINFORCE (Williams, 1992) :

EQUATION

This estimator is unbiased, but in general has high variance. Intuitively, this estimator is limited by the fact that it doesn't use any information about how f depends on b, only on the final outcome f (b).

The reparameterization trick When f is continuous and differentiable, and the latent variables b can be written as a deterministic, differentiable function of a random draw from a fixed distribution, the reparameterization trick (Williams, 1992; Kingma & Welling, 2014; Rezende et al., 2014) creates a low-variance, unbiased gradient estimator by making the dependence of b on θ explicit through a reparameterization function b = T (θ, ):

EQUATION

This gradient estimator is often used when training high-dimensional, continuous latent-variable models, such as variational autoencoders. One intuition for why this gradient estimator is preferable to REINFORCE is that it depends on ∂f /∂b, which exposes the dependence of f on b. 

Control variates:

EQUATION

This new estimator has the same expectation as the old one, but has lower variance if c(b) is positively correlated with ĝ(b).

3. CONSTRUCTING AND OPTIMIZING A DIFFERENTIABLE SURROGATE:

In this section, we introduce a gradient estimator for the expectation of a function ∂ ∂θ E p(b|θ) [f (b)] that can be applied even when f is unknown, or not differentiable, or when b is discrete. Our estimator combines the score function estimator, the reparameterization trick, and control variates.

First, we consider the case where b is continuous, but that f cannot be differentiated. Instead of differentiating through f , we build a surrogate of f using a neural network c φ , and differentiate c φ instead. Since the score-function estimator and reparameterization estimator have the same expectation, we can simply subtract the score-function estimator for c φ and add back its reparameterization estimator. This gives a gradient estimator which we call LAX:

EQUATION

)

This estimator is unbiased for any choice of c φ . When c φ = f , then LAX becomes the reparameterization estimator for f . Thus LAX can have variance at least as low as the reparameterization estimator. An example of the relative bias and variance of each term in this estimator can be seen below.

- 

3 -2 -1 0 1 2 3 unbiased high variance = ĝREINFORCE [f ] -3 -2 -1 0 1 2 3 biased high variance - ĝREINFORCE [c φ ] -3 -2 -1 0 1 2 3 biased low variance + ĝreparam [c φ ] -3 -2 -1 0 1 2 3 unbiased low variance ĝLAX

3.1. GRADIENT-BASED OPTIMIZATION OF THE CONTROL VARIATE:

Since ĝLAX is unbiased for any choice of the surrogate c φ , the only remaining problem is to choose a c φ that gives low variance to ĝLAX . How can we find a φ which gives our estimator low variance? We simply optimize c φ using stochastic gradient descent, at the same time as we optimize the parameters θ of our model or policy.

To optimize c φ , we require the gradient of the variance of our estimator. To estimate these gradients, we could simply differentiate through the empirical variance over each mini-batch. Or, following Ruiz et al. (2016a) and Tucker et al. (2017) , we can construct an unbiased, single-sample estimator using the fact that our gradient estimator is unbiased. For any unbiased gradient estimator ĝ with parameters φ:

EQUATION

Thus, an unbiased single-sample estimate of the gradient of the variance of ĝ is given by ∂ĝ 2 /∂φ.

This method of directly minimizing the variance of the gradient estimator stands in contrast to other methods such as Q-Prop (Gu et al., 2016) and advantage actor-critic (Sutton et al., 2000) , which train the control variate to minimize the squared error (f (b)c φ (b)) 2 . Our algorithm, which jointly optimizes the parameters θ and the surrogate c φ is given in Algorithm 1.

3.1.1. OPTIMAL SURROGATE:

What is the form of the variance-minimizing c φ ? Inspecting the square of (5), we can see that this loss encourages c φ (b) to approximate f (b), but with a weighting based on ∂ ∂θ log p(b|θ). Moreover, as c φ → f then ĝLAX → ∂ ∂θ c φ . Thus, this objective encourages a balance between the variance of the reparameterization estimator and the variance of the REINFORCE estimator. Figure 3 shows the learned surrogate on a toy problem.

Algorithm 1 LAX: Optimizing parameters and a gradient control variate simultaneously. Require: f (•), log p(b|θ), reparameterized sampler b = T (θ, ), neural network c φ (•),

step sizes α 1 , α 2 while not converged do ∼ p( ) Sample noise b ← T ( , θ) Compute input ĝθ ← [f (b) -c φ (b)] ∇ θ log p(b|θ) + ∇ θ c φ (b) Estimate gradient of objective ĝφ ← ∂ĝ 2 θ /∂φ Estimate gradient of variance of gradient θ ← θ -α 1 ĝθ Update parameters φ ← φ -α 2 ĝφ

Update control variate end while return θ

3.2. DISCRETE RANDOM VARIABLES AND CONDITIONAL REPARAMETERIZATION:

We can adapt the LAX estimator to the case where b is a discrete random variable by introducing a "relaxed" continuous variable z. We require a continuous, reparameterizable distribution p(z|θ) and a deterministic mapping H(z) such that H(z) = b ∼ p(b|θ) when z ∼ p(z|θ). In our implementation, we use the Gumbel-softmax trick, the details of which can be found in appendix B.

The discrete version of the LAX estimator is given by:

EQUATION

)

This estimator is simple to implement and general. However, if we were able to replace the ∂ ∂θ log p(z|θ) in the control variate with ∂ ∂θ log p(b|θ) we should be able to achieve a more correlated control variate, and therefore a lower variance estimator. This is the motivation behind our next estimator, which we call RELAX.

To construct a more powerful gradient estimator, we incorporate a further refinement due to Tucker et al. (2017) . Specifically, we evaluate our control variate both at a relaxed input z ∼ p(z|θ), and also at a relaxed input conditioned on the discrete variable b, denoted z ∼ p(z|b, θ). Doing so gives us:

ĝRELAX = [f (b) -c φ (z)] ∂ ∂θ log p(b|θ) + ∂ ∂θ c φ (z) - ∂ ∂θ c φ (z) (8) b = H(z), z ∼ p(z|θ), z ∼ p(z|b, θ)

This estimator is unbiased for any c φ . A proof and a detailed algorithm can be found in appendix A. We note that the distribution p(z|b, θ) must also be reparameterizable. We demonstrate how to perform this conditional reparameterization for Bernoulli and categorical random variables in appendix B.

3.3. CHOOSING THE CONTROL VARIATE ARCHITECTURE:

The variance-reduction objective introduced above allows us to use any differentiable, parametric function as our control variate c φ . How should we choose the architecture of c φ ? Ideally, we will take advantage of any known structure in f .

In the discrete setting, if f is known and happens to be differentiable, we can use the concrete relaxation (Jang et al., 2016; Maddison et al., 2016) and let c φ (z) = f (σ λ (z)). In this special case, our estimator is exactly the REBAR estimator. We are also free to add a learned component to the concrete relaxation and let c φ (z) = f (σ λ (z)) + r ρ (z) where r ρ is a neural network with parameters ρ making φ = {ρ, λ}. We took this approach in our experiments training discrete variational autoencoders. If f is unknown, we can simply let c φ be a generic function approximator such as a neural network. We took this simpler approach in our reinforcement learning experiments.

3.4. REINFORCEMENT LEARNING:

We now describe how we apply the LAX estimator in the reinforcement learning (RL) setting. By reinforcement learning, we refer to the problem of optimizing the parameters θ of a policy distribution π(a|s, θ) to maximize the sum of rewards. In this setting, the random variable being integrated over is τ , which denotes a series of T actions and states [(s 1 , a 1 ), (s 2 , a 2 ), ..., (s T , a T )]. The function whose expectation is being optimized, R, maps τ to the sum of rewards R(τ ) = T t=1 r t (s t , a t ). Again, we want to estimate the gradient of an expectation of a black-box function:

∂ ∂θ E p(τ |θ) [R(τ )

]. The de facto standard approach is the advantage actor-critic estimator (A2C) (Sutton et al., 2000) :

EQUATION

Where c φ (s t ) is an estimate of the state-value function,

c φ (s) ≈ V π (s) = E τ [R|s 1 = s].

This estimator is unbiased when c φ does not depend on a t . The main limitations of A2C are that c φ does not depend on a t , and that it's not obvious how to optimize c φ . Using the LAX estimator addresses both of these problems.

First, we assume π(a t |s t , θ) is reparameterizable, meaning that we can write a t = a( t , s t , θ), where t does not depend on θ. We again introduce a differentiable surrogate c φ (a, s). Crucially, this surrogate is a function of the action as well as the state.

The extension of LAX to Markov decision processes is:

EQUATION

a t = a( t , s t , θ) t ∼ p( t ).

This estimator is unbiased if the true dynamics of the system are Markovian w.r.t. the state s t .

When T = 1, we recover the special case ĝRL LAX = ĝLAX . Comparing ĝRL LAX to the standard advantage actor-critic estimator in (9), the main difference is that our baseline c φ (a t , s t ) is action-dependent while still remaining unbiased.

To optimize the parameters φ of our control variate c φ (a t , s t ), we can again use the single-sample estimator of the gradient of our estimator's variance given in (6). This approach avoids unstable training dynamics, and doesn't require storage and replay of previous rollouts. Details of this derivation, as well as the discrete and conditionally reparameterized version of this estimator can be found in appendix C.

4. SCOPE AND LIMITATIONS:

The work most related to ours is the recently-developed REBAR method (Tucker et al., 2017) , which greatly inspired our work. The REBAR estimator is a special case of the RELAX estimator, when the surrogate is set to c φ (z) = η • f (softmax λ (z)). The only free parameters of the REBAR estimator are the scaling factor η, and the temperature λ, which gives limited scope to optimize the surrogate. REBAR can only be applied when f is known and differentiable. Furthermore, it depends on essentially undefined behavior of the function being optimized, since it evaluates the discrete loss function at continuous inputs.

Because LAX and RELAX can construct a surrogate from scratch, they can be used for optimizing black-box functions, as in reinforcement learning settings where the reward is an unknown function of the environment. LAX and RELAX only require that we can query the function being optimized, and can sample from and differentiate p(b|θ).

Direct dependence on parameters Above, we assumed that the function f being optimized does not depend directly on θ, which is usually the case in black-box optimization settings. However, a dependence on θ can occur when training probabilistic models, or when we add a regularizer. In both these settings, if the dependence on θ is known and differentiable, we can use the fact that

EQUATION

and simply add ∂ ∂θ f (b, θ) to any of the gradient estimators above to recover an unbiased estimator. Miller et al. (2017) reduce the variance of reparameterization gradients in an orthogonal way to ours by approximating the gradient-generating procedure with a simple model and using that model as a control variate. NVIL (Mnih & Gregor, 2014) 2017) introduce a non-parametric control variate that also leverages gradient information to reduce the variance of an estimator.

5. RELATED WORK:

In parallel to our work, there has been a string of recent developments on action-dependent baselines for policy-gradient methods in reinforcement learning. Such works include Gu et al. ( 2016 Figure 3 : The optimal relaxation for a toy loss function, using different gradient estimators. Because REBAR uses the concrete relaxation of f , which happens to be implemented as a quadratic function, the optimal relaxation is constrained to be a warped quadratic. In contrast, RELAX can choose a free-form relaxation.

We demonstrate the effectiveness of our estimator on a number of challenging optimization problems. Following Tucker et al. (2017) we begin with a simple toy example to illuminate the potential of our method and then continue to the more relevant problems of optimizing binary VAE's and reinforcement learning. Figure 3 plots the learned surrogate c φ for a fixed value of θ. We can see that c φ is near f for all z, keeping the variance of the REINFORCE part of the estimator small. Moreover the derivative of c φ is positive for all z meaning that the reparameterization part of the estimator will produce gradients pointing in the correct direction to optimize the expectation. Conversely, the concrete relaxation of REBAR is close to f only near 0 and 1 and its gradient points in the correct direction only for values of z > log( 1-t t ). These factors together result in the RELAX estimator achieving the best performance.

6.2. DISCRETE VARIATIONAL AUTOENCODER:

Next, we evaluate the RELAX estimator on the task of training a variational autoencoder (Kingma & Welling, 2014; Rezende et al., 2014) with Bernoulli latent variables. We reproduced the variational autoencoder experiments from Tucker et al. (2017) , training models with one or two layers of 200 Bernoulli random variables with linear or nonlinear mappings between them, on both the MNIST and Omniglot (Lake et al., 2015) datasets. Details of these models and our experimental procedure can be found in Appendix E.1.

To take advantage of the available structure in the loss function, we choose the form of our control variate to be c φ (z) = f (σ λ (z)) + rρ (z) where rρ is a neural network with parameters ρ and f (σ λ (z)) is the discrete loss function, the evidence lower-bound (ELBO), evaluated at continuously relaxed inputs as in REBAR. In all experiments, the learned control variate improved the training performance, over the state-of-the-art baseline of REBAR. In both linear models, we achieved improved validation performance as well increased convergence speed. We believe the decrease in validation performance for the nonlinear models was due to overfitting caused by improved optimization of an under-regularized model. We leave exploring this phenomenon to further work. To obtain training curves we created our own implementation of REBAR, which gave identical or slightly improved performance compared to the implementation of Tucker et al. (2017) .

Dataset:

While we obtained a modest improvement in training and validation scores (tables 1 and 3), the most notable improvement provided by RELAX is in its rate of convergence. Training curves for all models can be seen in Figure 4 and in Appendix D. In Table 4 we compare the number of training epochs that are required to match the best validation score of REBAR. In both linear models, RELAX provides an increase in rate of convergence. Table 2 : Mean episodes to solve tasks. Definitions of solving each task can be found in Appendix E.

We apply our gradient estimator to a few simple reinforcement learning environments with discrete and continuous actions. We use the RELAX and LAX estimators for discrete and continuous actions, respectively. We compare with the advantage actor-critic algorithm (A2C) (Sutton et al., 2000) as a baseline.

As our control variate does not have the same interpretation as the value function of A2C, it was not directly clear how to add reward bootstrapping and other variance reduction techniques common in RL into our model. For instance, to do reward bootstrapping, we would need to use the statevalue function. In the discrete experiments, due to the simplicity of the tasks, we chose not to use reward bootstrapping, and therefore omitted the use of state-value function. However, with the more complicated continuous tasks, we chose to use the value function to enable bootstrapping. In this case, the control variate takes the form: c φ (a, s) = V (s) + ĉ(a, s), where V (s) is trained as it would be in A2C. Full details of our experiments can be found in Appendix E.

In the discrete action setting, we test our approach on the Cart Pole and Lunar Lander environments as provided by the OpenAI gym (Brockman et al., 2016) . In the continuous action setting, we test on the MuJoCo-simulated (Todorov et al., 2012) environment Inverted Pendulum also found in the OpenAI gym. In all tested environments we observe improved performance and sample efficiency using our method. The results of our experiments can be seen in Figure 5 , and Table 2 .

We found that our estimator produced policy gradients with drastically reduced variance (see Figure 5 ) allowing for larger learning rates to be used while maintaining stable training. In both discrete environments our estimator achieved greater than a 2-times speedup in convergence over the baseline.

7. CONCLUSIONS AND FUTURE WORK:

In this work we synthesized and generalized several standard approaches for constructing gradient estimators. We proposed a generic gradient estimator that can be applied to expectations of known or black-box functions of discrete or continuous random variables, and adds little computational overhead. We also derived a simple extension to reinforcement learning in both discrete and continuous-action domains.

Future applications of this method could include training models with hard attention or memory indexing (Zaremba & Sutskever, 2015) . One could also apply our estimators to continuous latentvariable models whose likelihood is non-differentiable, such as a 3D rendering engine. Extensions to the reparameterization gradient estimator (Ruiz et al., 2016b; Naesseth et al., 2017) could also be applied to increase the scope of distributions that can be modeled.

In the reinforcement learning setting, our method could be combined with other variance-reduction techniques such as generalized advantage estimation (Kimura et al., 2000; Schulman et al., 2015b) , or other optimization methods, such as KFAC (Wu et al., 2017) . One could also train our control variate off-policy, as in Q-prop (Gu et al., 2016) .

APPENDICES A THE RELAX ALGORITHM:

Proof. We show that ĝRELAX is an unbiased estimator of

∂ ∂θ E p(b|θ) [f (b)]. The estimator is E p(b|θ) f (b) -E p(z|b,θ) [c φ (z)] ∂ ∂θ log p(b|θ) - ∂ ∂θ E p(z|b,θ) [c φ (z)] + ∂ ∂θ E p(z|θ) [c φ (z)] .

Expanding the expectation for clarity of exposition, we account for each term in the estimator separately:

EQUATION

EQUATION

Term ( 12) is an unbiased score-function estimator of

∂ ∂θ E p(b|θ) [f (b)].

It remains to show that the other three terms are zero in expectation. Following Tucker et al. (2017) (see the appendices of that paper for a derivation), we rewrite term ( 14) as follows:

EQUATION

Note that the first term on the right-hand side of equation ( 16) is equal to term (13) with opposite sign. The second term on the right-hand side of equation ( 16) is the score-function estimator of term (15), opposite in sign. The sum of these terms is zero in expectation.

Algorithm 2 RELAX: Low-variance control variate optimization for black-box gradient estimation.

Require: f (•), log p(b|θ), reparameterized samplers b = H(z), z = S( , θ) and z = S( , θ|b),

neural network c φ (•), step sizes α 1 , α 2 while not converged do i , i ∼ p( ) Sample noise z i ← S( i , θ) Compute unconditional relaxed input b i ← H(z i ) Compute input z i ← S( i , θ|b i ) Compute conditional relaxed input ĝθ ← [f (b i ) -c φ ( z i )] ∇ θ log p + ∇ θ c φ (z i ) -∇ θ c φ ( z i ) Estimate gradient ĝφ ← ∂ĝ 2 θ /∂φ Estimate gradient of variance of gradient θ ← θ -α 1 ĝθ Update parameters φ ← φ -α 2 ĝφ

Update control variate end while return θ

B CONDITIONAL RE-SAMPLING FOR DISCRETE RANDOM VARIABLES:

When applying the RELAX estimator to a function of discrete random variables b ∼ p(b|θ), we require that there exists a distribution p(z|θ) and a deterministic mapping H(z) such that if z ∼ p(z|θ) then H(z) = b ∼ p(b|θ). Treating both b and z as random, this procedure defines a probabilistic model p(b, z|θ) = p(b|z)p(z|θ). The RELAX estimator requires reparameterized samples from p(z|θ) and p(z|b, θ). We describe how to sample from these distributions in the common cases of p(b|θ) = Bernoulli(θ) and p(b|θ) = Categorical(θ).

Bernoulli When p(b|θ) is Bernoulli distribution we let H(z) = I(z > 0) and we sample from p(z|θ) with

z = log θ 1 -θ + log u 1 -u , u ∼ uniform[0, 1].

We can sample from p(z|b, θ) with

v = v • (1 -θ) b = 0 v • θ + (1 -θ) b = 1 z = log θ 1 -θ + log v 1 -v v ∼ uniform[0, 1].

Categorical When p(b|θ) is a Categorical distribution where θ i = p(b = i|θ), we let H(z) = argmax(z) and we sample from p(z|θ) with

z = log θ -log(-log u), u ∼ uniform[0, 1] k

where k is the number of possible outcomes.

To sample from p(z|b, θ), we note that the distribution of the largest ẑb is independent of θ, and can be sampled as ẑb =log(-log v b ) where v b ∼ uniform[0, 1]. Then, the remaining v i =b can be sampled as before but with their underlying noise truncated so ẑi =b < ẑb . As shown in the appendix of Tucker et al. (2017) , we can then sample from p(z|b, θ) with:

EQUATION

where

v i ∼ uniform[0, 1].

C DERIVATIONS OF ESTIMATORS USED IN REINFORCEMENT LEARNING:

We give the derivation of the LAX estimator used for continuous RL tasks.

Theorem C.1. The LAX estimator,

EQUATION

a t = a t ( t , s t , θ), t ∼ p( t ), is unbiased.

Proof. Note that by using the score-function estimator, for all t, we have

E p(τ ) ∂ log π(a t |s t , θ) ∂θ c φ (a t , s t ) = E p(a1:t-1,s1:t) ∂ ∂θ E π(at|st,θ) c φ (a t , s t ) .

Then, by adding and subtracting the same term, we have We run all models for 2, 000, 000 iterations with a batch size of 24. For the REBAR models, we tested learning rates in {.005, .001, .0005, .0001, .00005}.

∂ ∂θ E p(τ ) [f (τ )] = E p(τ ) f (τ ) • ∂ ∂θ log p(τ ; θ) - t E p(τ ) ∂ log π(a t |s t , θ) ∂θ c φ (a t , s t ) + t E p(a1:t-1,s1:t) ∂ ∂θ E π(at|st,θ) c φ (a t , s t ) = E p(τ ) ∞ t=1 ∂ log π(a t |s t , θ) ∂θ ∞ t =t r t -c φ (a t , s t ) + t E p(a1:t-1,s1:t) E p( t) ∂ ∂θ c φ (a t ( t , s t , θ), s t ) = E p(τ ) ∞ t=1 ∂ log π(a t |s t , θ) ∂θ ∞ t =t r t -c φ (

RELAX adds more hyperparameters. These are the depth of the neural network component of our control variate r ρ , the weight decay placed on the network, and the scaling on the learning rate for the control variate. We tested neural network models with l layers of 200 units using the ReLU nonlinearity with l ∈ {2, 4}. We trained the control variate with weight decay in {.001, .0001}. We trained the control variate with learning rate scaling in {1, 10}.

To limit the size of hyperparameter search for the RELAX models, we only test the best performing learning rate for the REBAR baseline and the next largest learning rate in our search set. In many cases, we found that RELAX allowed our model to converge at learning rates which made the REBAR estimators diverge. We believe further improvement could be achieved by tuning this parameter. It should be noted that in our experiments, we found the RELAX method to be fairly insensitive to all hyperparameters other than learning rate. In general, we found the larger (4 layer) control variate architecture with weight decay of .001 and learning rate scaling of 1 to work best, but only slightly outperformed other configurations.

All presented results are from the models which achieve the highest ELBO on the validation data.

E.1.1 ONE-LAYER LINEAR MODEL:

In the one-layer linear models we optimize the evidence lower bound (ELBO):

log p(x) ≥ L(θ) = E q(b|x) [log p(x|b) + log p(b) -log q(b|x)]

where q(b 1 |x) = σ(x • W q + β q ) and p(x|b 1 ) = σ(b 1 • W p + β p ) with weight matrices W q , W p and bias vectors β q , β p . The parameters of the prior p(b) are also learned.

E.1.2 TWO LAYER LINEAR MODEL:

In the two layer linear models we optimize the ELBO

L(θ) = E q(b2|b1)q(b1|x) [log p(x|b 1 ) + log p(b 1 |b 2 ) + log p(b 2 ) -log q(b 1 |x) -log q(b 2 |b 1 )] where q(b 1 |x) = σ(x • W q1 + β q1 ), q(b 2 |b 1 ) = σ(b 1 • W q2 + β q2 ), p(x|b 1 ) = σ(b 1 • W p1 + β p1 ), and p(b 1 |b 2 ) = σ(b 2 •W p2 +β p2 ) with weight matrices W q1 , W q2 , W p1 , W p2 and biases β q1 , β q2 , β p1 , β p2 .

As in the one-layer model, the prior p(b 2 ) is also learned.

E.1.3 NONLINEAR MODEL:

In the one-layer nonlinear model, the mappings between random variables consist of 2 deterministic layers with 200 units using the hyperbolic-tangent nonlinearity followed by a linear layer with 200 units.

We run an identical hyperpameter search in all models.

E.2 DISCRETE RL:

In both the baseline A2C and RELAX models, the policy and control variate (value function in the baseline model) were two-layer neural networks with 10 units per layer. The ReLU non linearity was used on all layers except for the output layer which was linear.

For these tasks we estimate the policy gradient with a single Monte Carlo sample. We run one episode of the environment to completion, compute the discounted rewards, and run one iteration of gradient descent. We believe using larger batches will improve performance but would less clearly demonstrate the potential of our method.

Both models were trained with the RMSProp (Tieleman & Hinton, 2012) optimizer and a reward discount factor of .99 was used. Entropy regularization with a weight of .01 was used to encourage exploration.

Both models have 2 hyperparameters to tune; the global learning rate and the scaling factor on the learning rate for the control variate (or value function). We complete a grid search for both parameters in {0.01, 0.003, 0.001} and present the model which "solves" the task in the fewest number of episodes averaged over 5 random seeds. "Solving" the tasks was defined by the creators of the OpenAI gym (Brockman et al., 2016) . The Cart Pole task is considered solved if the agent receives an average reward greater than 195 over 100 consecutive episodes. The Lunar Lander task is considered solved if the agent receives an average reward greater than 200 over 100 consecutive episodes.

The Cart Pole experiments were run for 250,000 frames. The Lunar Lander experiments were run for 5,000,000 frames.

The results presented for the CartPole and LunarLander environments were obtained using a slightly biased sampler for p(z|b, θ).

E.3 CONTINUOUS RL:

The three models-policy, value, and control variate, are two-layer neural networks with 64 hidden units per layer. The value and control variate networks are identical, with the ELU (Djork-Arné Clevert & Hochreiter, 2016) nonlinearity in each hidden layer. The policy network has tanh nonlinearity. The policy network, which parameterizes the Gaussian policy comprises of a network (with the architecture mentioned above) that outputs the mean, and a separate, trainable log standard deviation value that is not input dependent. All three networks have a linear output layer. We selected the batch size to be 2500, meaning for a fixed timestep (2500) we collect multiple rollouts of a task and update the networks' parameters with the batch of episodes. Per one policy update, we optimize both the value and control variate network multiple times. The number of times we train the value network is fixed to 25, while for the control variate, it was chosen to be a hyperparameter. All models were trained using ADAM (Kingma & Ba, 2015) , with β 1 = 0.9, β 2 = 0.999, and = 1e -08.

The baseline A2C case has 2 hyperparameters to tune: the learning rate for the optimizer for the policy and value network. A grid search was done over the set: {0.03, 0.003, 0.0003}. RELAX has 4 hyperparameters to tune: 3 learning rates for the optimizer per network, and the number of training iterations of the control variate per policy gradient update. Due to the large number of hyperparameters, we restricted the size of the grid search set to {0.003, 0.0003} for the learning rates, and {1, 5, 25} for the control variate training iteration number. We chose the hyperparameter setting that yielded the shortest episode-to-completion time averaged over 5 random seeds. As with the discrete case, we used the definition of completion provided by the OpenAI gym (Brockman et al., 2016) for each task.

The Inverted Pendulum experiments were run for 1,000,000 frames. Tucker et al. (2018) pointed out a bug in our initially released code for the continuous RL experiments. This issue has been fixed in the publicly available code and the results presented in this paper were generated with the corrected code.

E.3.1 IMPLEMENTATION CONSIDERATIONS:

For continuous RL tasks, it is convention to employ a batch of a fixed number of timesteps (here, 2500) in which the number of episodes vary. We follow this convention for the sake of providing a fair comparison to the baseline. However, this causes a complication when calculating the variance loss for the control variate because we must compute the variance averaged over completed episodes, which is difficult to obtain when the number of episodes is not fixed. For this reason, in our implementation we compute the gradients for the control variate outside of the Tensorflow computation graph. However, for practical reasons we recommend using a batch of fixed number of episodes when using our method.

:



Figures and Tables:

Figure 1: Left: Training curves comparing different gradient estimators on a toy problem: L(θ) = E p(b|θ) [(b -0.499) 2 ] Right: Log-variance of each estimator's gradient.

Control variates are a general method for reducing the variance of a stochastic estimator. A control variate is a function c(b) with a known mean E p(b) [c(b)]. Given an estimator ĝ(b), subtracting the control variate from this estimator and adding its mean gives us a new estimator:

Figure 2: Histograms of samples from the gradient estimators that create LAX. Samples generated from our one-layer VAE experiments (Section 6.2).

) andGu et al. (2017) which train an action-dependent baseline which incorporates off-policy data.Liu et al. (2017) independently develop a method similar to LAX applied to continuous control.Wu et al. (2018) exploit per-dimension independence of the action distribution in continuous control tasks to produce an action-dependent unbiased baseline.

TOY EXPERIMENT As a simple example, we followTucker et al. (2017) in minimizing E p(b|θ) [(bt) 2 ] as a function of the parameter θ where p(b|θ) = Bernoulli(b|θ).Tucker et al. (2017) set the target t = .45. We focus on the more challenging case where t = .499. Figures1a and 1bshow the relative performance and gradient log-variance of REINFORCE, REBAR, and RE-LAX.

Figure 4: Training curves for the VAE Experiments with the one-layer linear model. The horizontal dashed line indicates the lowest validation error obtained by REBAR.

Figure 5: Top row: Reward curves. Bottom row: Log-variance of policy gradients. In each curve, the center line indicates the mean reward over 5 random seeds. The opaque bars in the top row indicate the 25th and 75th percentiles. The opaque bars in the bottom row indicate 1 standard deviation. Since the gradient estimator is defined at the end of each episode, we display log-variance per episode. After every 10th training episode 100 episodes were run and the sample log-variance is reported averaged over all policy parameters.

Figure 7: Training curves for the VAE Experiments with the one-layer nonlinear model. The horizontal dashed line indicates the lowest validation error obtained by REBAR.

and VIMCO(Mnih & Rezende, 2016) provide reduced variance gradient estimation in the special case of discrete latent variable models and discrete latent variable models with Monte Carlo objectives.Salimans et al. (2017) estimate gradients using a form of finite differences, evaluating hundreds of different parameter values in parallel to construct a gradient estimate. In contrast, our method is a single-sample estimator.

Table content: <table/>

Highest training ELBO for discrete variational autoencoders.

Table content: <table><tr><td>Model</td><td>Concrete</td><td>NVIL</td><td>MuProp REBAR RELAX</td></tr><tr><td colspan="4">Nonlinear MNIST linear one-layer linear two-layer Nonlinear Omniglot linear one-layer linear two-layer -109.95 -109.98 -109.55 -108.71 -108.54 -102.2 -101.1 -81.01 -78.13 -101.5 -111.3 -112.5 -111.6 -111.20 -111.7 -99.62 -99.6 -98.22 -98.00 -99.07 -56.76 -56.12 -110.4 -109.58 -108.72 -117.23 -117.44 -117.09 -116.63 -116.57</td></tr></table>

a t , s t ) + ∂ ∂θ c φ (a ( t , s t , θ), s t ) In the discrete control setting, our policy parameterizes a soft-max distribution which we use to sample actions. We define z t ∼ p(z t |s t ), which is equal to σ(log πlog(-log(u))) where u ∼ uniform[0, 1], a t = argmax(z t ), σ is the soft-max function. We also define zt ∼ p(z t |a t , s t ) and uses the same reparametrization trick for sampling zt as explicated in Appendix B. Theorem C.2. The RELAX estimator, Since p(z t |s t ) is reparametrizable, we obtain the estimator in Eq.(19). Highest obtained validation ELBO.

Table content: <table><tr><td colspan="2">ĝRL RELAX =</td><td>T t=1</td><td colspan="4">∂ log π(a t |s t , θ) ∂θ</td><td colspan="2">T t =t</td><td>r t -c φ (z t , s t ) -</td><td>∂ ∂θ</td><td>c φ (z t , s t ) +</td><td>∂ ∂θ</td><td>c φ (z t , s t ), (19)</td></tr><tr><td colspan="2">is unbiased.</td><td/><td/><td/><td/><td/><td/><td/><td>zt ∼ p(z t |a t , s t ),</td><td>z t ∼ p(z t |s t ),</td></tr><tr><td colspan="10">Proof. Note that by using the score-function estimator, for all t, we have</td></tr><tr><td/><td/><td/><td colspan="2">E p(a1:t,s1:t)</td><td/><td colspan="4">∂ log π(a t |s t , θ) ∂θ</td><td>E p(zt|at,st) [c φ (z t , s t )]</td></tr><tr><td/><td/><td/><td colspan="5">= E p(a1:t-1,s1:t)</td><td colspan="2">∂ ∂θ</td><td>E π(at|st,θ) E p(zt|at,st) [c φ (z t , s t )]</td></tr><tr><td/><td/><td/><td colspan="5">= E p(a1:t-1,s1:t)</td><td colspan="2">∂ ∂θ</td><td>E p(zt|st) [c φ (z t , s t )]</td></tr><tr><td colspan="10">Then, by adding and subtracting the same term, we have</td></tr><tr><td>∂ ∂θ</td><td colspan="7">E p(τ ) [f (τ )] = E p(τ ) f (τ ) •</td><td colspan="2">∂ ∂θ</td><td>log p(τ ; θ)</td></tr><tr><td/><td/><td/><td>-</td><td>t</td><td/><td colspan="4">E p(a1:t,s1:t)</td><td>∂ log π(a t |s t , θ) ∂θ</td><td>E p(zt|at,st) [c φ (z t , s t )]</td></tr><tr><td/><td/><td/><td>+</td><td>t</td><td/><td colspan="4">E p(a1:t-1,s1:t)</td><td>∂ ∂θ</td><td>E p(zt|st) [c φ (z t , s t )]</td></tr><tr><td/><td/><td/><td colspan="2">= E p(τ )</td><td colspan="2">∞ t=1</td><td colspan="3">∂ log π(a t |s t , θ) ∂θ</td><td>∞ t =t</td><td>r t -E p(zt|at,st) [c φ (z t , s t )]</td></tr><tr><td/><td/><td/><td>+</td><td>t</td><td/><td colspan="4">E p(a1:t-1,s1:t)</td><td>∂ ∂θ</td><td>E p(zt|st) [c φ (z t , s t )]</td></tr><tr><td/><td/><td/><td colspan="2">= E p(τ )</td><td colspan="2">∞ t=1</td><td colspan="3">∂ log π(a t |s t , θ) ∂θ</td><td>∞ t =t</td><td>r t -E p(zt|at,st) [c φ (z t , s t )</td></tr><tr><td/><td/><td/><td>-</td><td colspan="2">∂ ∂θ</td><td colspan="4">E p(zt|at,st) [c φ (z t , s t )] +</td><td>∂ ∂θ</td><td>E p(zt|st) [c φ (z t , s t )]</td></tr></table>

Epochs needed to achieve REBAR's best validation score. "-" indicates that the nonlinear RELAX models achieved lower validation scores than REBAR.

Table content: <table><tr><td>E EXPERIMENTAL DETAILS</td></tr><tr><td>E.1 DISCRETE VAE</td></tr></table>

Peer review (iclr2018):
 This paper suggests a new approach to performing gradient descent for blackbox optimization or training discrete latent variable models. The paper gives a very clear account of existing gradient estimators and finds a way to combine them so as to construct and optimize a differentiable surrogate function. The resulting new gradient estimator is then studied both theoretically and empirically. The empirical study shows the benefits of the new estimator for training discrete variational autoencoders and for performing deep reinforcement learning. To me, the main strengths of the paper is the very clear account of existing gradient estimators (among other things it helped me understand obscurities of the Q-prop paper) and a nice conceptual idea. The empirical study itself is more limited and the paper suffers from a few mistakes and missing information, but to me the good points are enough to warrant publication of the paper in a good conference like ICLR. Below are my comments for the authors. --------------------------------- General, conceptual comments: When reading (6), it is clear that the framework performs regression of towards the unknown simultaneously with optimization over . Taking this perspective, I would be glad to see how the regression part performs with respect to standard least square regression, i.e. just using as loss function. You may compare the speed of convergence of towards using (6) and the least squared error. You may also investigate the role of this regression part into the global g_LAX optimization by studying the evolution of the components of (6). Related to the above comment, in Algo. 1, you mention "f(.)" as given to the algo. Actually, the algo does not know f itself, otherwise it would not be blackbox optimization. So you may mean different things. In a batch setting, you may give a batch of [x,f(x) (,cost(x)?)] points to the algo. You more probably mean here that you have an "oracle" that, given some x, tells you f(x) on demand. But the way you are sampling x is not specified clearly. This becomes more striking when you move to reinforcement learning problems, which is my main interest. The RL algorithm itself is not much specified. Does it use a replay buffer (probably not)? Is it on-policy or off-policy (probably on-policy)? What about the exploration policy? I want to know more... Probably you just replace (10) with (11) in A2C, but this is not clearly specified. In Section 4, can you explain why, in the RL case, you must introduce stochasticity to the inputs? Is this related to the exploration issue (see above)? Last sentence of conclusion: you are too allusive about the relationship between your learned control variate and the Q-function. I don*t get it, and I want to know more... ----------------------------------- Local comments: Backpropagation through the void: I don*t understand why this title. I*m not a native english speaker, I*m probably missing a reference to something, I would be glad to get it. Figure 1 right. Caption states variance, but it is log variance. Why does it oscillate so much with RELAX? Beginning of 3.1: you may state more clearly that optimizing the way you do it will also "minimize" the variance, and explain better why ("we require the gradient of the variance of our gradient estimator"...). It took me a while to get it. In 3.1.1 a weighting based on => shouldn*t you write as before? Figure 2 is mentioned in p.3, it should appear much sooner than p6. In Figure 2, there is nothing about the REINFORCE PART. Why? In 3.4 you alternate sums over an infinite horizon and sums over T time steps. You should stick to the T horizon case, as you mention the case T=1 later. p6 Related work The link to the work of Salimans 2017 is far from obvious, I would be glad to know more... Q-prop (Haarnoja et al.,2017): this is not the adequate reference to Q-prop, it should be (Gu et al. 2016), you have it correct later ;) Figure 3: why do you stop after so few epochs? I wondered how expensive is the computation of your estimator, but since in the RL case you go up to 50 millions (or 4 millions?), it*s probably not the issue. I would be glad to see another horizontal lowest validation error for your RELAX estimator (so you need to run more epochs). "ELBO" should be explained here (it is only explained in the appendices). 6.2, Table 1: Best obtained training objective: what does this mean? Should it be small or large? You need to explain better. How much is the modest improvement (rather give relative improvement in the text?)? To me, you should not defer Table 3 to an appendix (nor Table 4). Figure 4: Any idea why A2C oscillates so much on inverted pendulum? Any idea why variance starts to decrease after 500 episodes using RELAX? Isn*t related to the combination of regression and optimization, as suggested above? About Double Inverted Pendulum, Appendix E3 mentions 50 million frames, but the figure shows 4 millions steps. Where is the truth? Why do you give steps for the reward, and episodes for log-variance? The caption mentions "variance (log-scale)", but saying "log-variance" would be more adequate. p9: the optimal control variate: what is this exactly? How do you compare a control variate over another? This may be explained in Section 2. GAE (Kimura, 2000). I*m glad you refer to former work (there is a very annoying tendency those days to refer only to very recent papers from a small set of people who do not correctly refer themselves to previous work), but you may nevertheless refer to John Schulman*s paper about GAEs anyways... ;) Appendix E.1 could be reorganized, with a common hat and then E.1.1 for one layer model(s?) and E.1.2 for the two layer model(s?) A sensitivity analysis wrt to your hyper-parameters would be welcome, this is true for all empirical studies. In E2, is the output layer linear? You just say it is not ReLU... The networks used in E2 are very small (a standard would be 300 and 400 neurons in hidden layers). Do you have a constraint on this? "As our control variate does not have the same interpretation as the value function of A2C, it was not directly clear how to add reward bootstrapping and other variance reduction techniques common in RL into our model. We leave the task of incorporating these and other variance reduction techniques to future work." First, this is important, so if this is true I would move this to the main text (not in appendix). But also, it seems to me that the first sentence of E3 contradicts this, so where is the truth? {0.01,0.003,0.001} I don*t believe you just tried these values. Most probably, you played with other values before deciding to perform grid search on these, right? The same for 25 in E3. Globally, you experimental part is rather weak, we would expect a stronger methodology, more experiments also with more difficult benchmarks (half-cheetah and the whole gym zoo ;)), more detailed analyses of the results, but to me the value of your paper is more didactical and conceptual than experimental, which I really appreciate, so I will support your paper despite these weaknesses. Good luck! :) --------------------------------------- Typos: p5 monte-carlo => Monte(-)Carlo (no - later...) taylor => Taylor you should always capitalize Section, equation, table, figure, appendix, ... gradient decent => descent (twice) p11: probabalistic p15 ELU(Djork-... => missing space