Title: Q-PROP: SAMPLE-EFFICIENT POLICY GRADIENT WITH AN OFF-POLICY CRITIC

Abstract: Model-free deep reinforcement learning (RL) methods have been successful in a wide variety of simulated domains. However, a major obstacle facing deep RL in the real world is their high sample complexity. Batch policy gradient methods offer stable learning, but at the cost of high variance, which often requires large batches. TD-style methods, such as off-policy actor-critic and Q-learning, are more sample-efficient but biased, and often require costly hyperparameter sweeps to stabilize. In this work, we aim to develop methods that combine the stability of policy gradients with the efficiency of off-policy RL. We present Q-Prop, a policy gradient method that uses a Taylor expansion of the off-policy critic as a control variate. Q-Prop is both sample efficient and stable, and effectively combines the benefits of on-policy and off-policy methods. We analyze the connection between Q-Prop and existing model-free algorithms, and use control variate theory to derive two variants of Q-Prop with conservative and aggressive adaptation. We show that conservative Q-Prop provides substantial gains in sample efficiency over trust region policy optimization (TRPO) with generalized advantage estimation (GAE), and improves stability over deep deterministic policy gradient (DDPG), the stateof-the-art on-policy and off-policy methods, on OpenAI Gym's MuJoCo continuous control environments.

1. INTRODUCTION:

Model-free reinforcement learning is a promising approach for solving arbitrary goal-directed sequential decision-making problems with only high-level reward signals and no supervision. It has recently been extended to utilize large neural network policies and value functions, and has been shown to be successful in solving a range of difficult problems (Mnih et al., 2015; Schulman et al., 2015; Lillicrap et al., 2016; Silver et al., 2016; Gu et al., 2016b; Mnih et al., 2016) . Deep neural network parametrization minimizes the need for manual feature and policy engineering, and allows learning end-to-end policies mapping from high-dimensional inputs, such as images, directly to actions. However, such expressive parametrization also introduces a number of practical problems. Deep reinforcement learning algorithms tend to be sensitive to hyperparameter settings, often requiring extensive hyperparameter sweeps to find good values. Poor hyperparameter settings tend to produce unstable or non-convergent learning. Deep RL algorithms also tend to exhibit high sample complexity, often to the point of being impractical to run on real physical systems. Although a number of recent techniques have sought to alleviate some of these issues (Hasselt, 2010; Mnih et al., 2015; Schulman et al., 2015; 2016) , these recent advances still provide only a partial solution to the instability and sample complexity challenges.

Model-free reinforcement learning consists of on-and off-policy methods. Monte Carlo policy gradient methods (Peters & Schaal, 2006; Schulman et al., 2015) are popular on-policy methods that directly maximize the cumulative future returns with respect to the policy. While these algorithms can offer unbiased (or nearly unbiased, as discussed in Section 2.1) estimates of the gradient, they rely on Monte Carlo estimation and often suffer from high variance. To cope with high variance gradient estimates and difficult optimization landscapes, a number of techniques have been proposed, including constraining the change in the policy at each gradient step (Kakade, 2001; Peters et al., 2010) and mixing value-based back-ups to trade off bias and variance in Monte Carlo return estimates (Schulman et al., 2015) . However, these methods all tend to require very large numbers of samples to deal with the high variance when estimating gradients of high-dimensional neural network policies. The crux of the problem with policy gradient methods is that they can only effectively use on-policy samples, which means that they require collecting large amounts of on-policy experiences after each parameter update to the policy. This makes them very sample intensive. Offpolicy methods, such as Q-learning (Watkins & Dayan, 1992; Sutton et al., 1999; Mnih et al., 2015; Gu et al., 2016b) and off-policy actor-critic methods (Lever, 2014; Lillicrap et al., 2016) , can instead use all samples, including off-policy samples, by adopting temporal difference learning with experience replay. Such methods are much more sample-efficient. However, convergence of these algorithms is in general not guaranteed with non-linear function approximators, and practical convergence and instability issues typically mean that extensive hyperparameter tuning is required to attain good results.

In order to make deep reinforcement learning practical as a tool for tackling real-world tasks, we must develop methods that are both data efficient and stable. In this paper, we propose Q-Prop, a step in this direction that combines the advantages of on-policy policy gradient methods with the efficiency of off-policy learning. Unlike prior approaches for off-policy learning, which either introduce bias (Sutton et al., 1999; Silver et al., 2014) or increase variance (Precup, 2000; Levine & Koltun, 2013; Munos et al., 2016) , Q-Prop can reduce the variance of gradient estimator without adding bias; unlike prior approaches for critic-based variance reduction (Schulman et al., 2016) which fit the value function on-policy, Q-Prop learns the action-value function off-policy. The core idea is to use the first-order Taylor expansion of the critic as a control variate, resulting in an analytical gradient term through the critic and a Monte Carlo policy gradient term consisting of the residuals in advantage approximations. The method helps unify policy gradient and actor-critic methods: it can be seen as using the off-policy critic to reduce variance in policy gradient or using on-policy Monte Carlo returns to correct for bias in the critic gradient. We further provide theoretical analysis of the control variate, and derive two additional variants of Q-Prop. The method can be easily incorporated into any policy gradient algorithm. We show that Q-Prop provides substantial gains in sample efficiency over trust region policy optimization (TRPO) with generalized advantage estimation (GAE) (Schulman et al., 2015; 2016) , and improved stability over deep deterministic policy gradient (DDPG) (Lillicrap et al., 2016) across a repertoire of continuous control tasks.

2. BACKGROUND:

Reinforcement learning (RL) aims to learn a policy for an agent such that it behaves optimally according to a reward function. At a time step t and state s t , the agent chooses an action a t according to its policy π(a t |s t ), the state of the agent and the environment changes to new state s t+1 according to dynamics p(s t+1 |s t , a t ), the agent receives a reward r(s t , a t ), and the process continues. Let R t denote a γ-discounted cumulative return from t for an infinite horizon problem, i.e R t = ∑ ∞ t =t γ t -t r(s t , a t ). The goal of reinforcement learning is to maximize the expected return J(θ ) = E π θ [R 0 ] with respect to the policy parameters θ . In this section, we review several standard techniques for performing this optimization, and in the next section, we will discuss our proposed Q-Prop algorithm that combines the strengths of these approaches to achieve efficient, stable RL. Monte Carlo policy gradient refers to policy gradient methods that use full Monte Carlo returns, e.g. REINFORCE (Williams, 1992) and TRPO (Schulman et al., 2015) , and policy gradient with function approximation refers to actor-critic methods (Sutton et al., 1999) which optimize the policy against a critic, e.g. deterministic policy gradient (Silver et al., 2014; Lillicrap et al., 2016) .

2.1. MONTE CARLO POLICY GRADIENT METHODS:

Monte Carlo policy gradient methods apply direct gradient-based optimization to the reinforcement learning objective. This involves directly differentiating the J(θ ) objective with respect to the policy parameters θ . The standard form, known as the REINFORCE algorithm (Williams, 1992) , is shown below:

∇ θ J(θ ) = E π [ ∞ ∑ t=0 ∇ θ log π θ (a t |s t )γ t R t ] = E π [ ∞ ∑ t=0 γ t ∇ θ log π θ (a t |s t )(R t -b(s t ))],

(1) where b(s t ) is known as the baseline. For convenience of later derivations, Eq. 1 can also be written as below, where ρ π (s) = ∑ ∞ t=0 γ t p(s t = s) is the unnormalized discounted state visitation frequency,

EQUATION

Eq. 2 is an unbiased gradient of the RL objective. However, in practice, most policy gradient methods effectively use undiscounted state visitation frequencies, i.e. γ = 1 in the equal for ρ π , and are therefore biased; in fact, making them unbiased often hurts performance (Thomas, 2014) . In this paper, we mainly discuss bias due to function approximation, off-policy learning, and value back-ups.

The gradient is estimated using Monte Carlo samples in practice and has very high variance. A proper choice of baseline is necessary to reduce the variance sufficiently such that learning becomes feasible. A common choice is to estimate the value function of the state V π (s t ) to use as the baseline, which provides an estimate of advantage function A π (s t , a t ), which is a centered action-value function Q π (s t , a t ), as defined below:

EQUATION

Q π (s t , a t ) summarizes the performance of each action from a given state, assuming it follows π thereafter, and A π (s t , a t ) provides a measure of how each action compares to the average performance at the state s t , which is given by V π (s t ). Using A π (s t , a t ) centers the learning signal and reduces variance significantly.

Besides high variance, another problem with the policy gradient is that it requires on-policy samples. This makes policy gradient optimization very sample intensive. To achieve similar sample efficiency as off-policy methods, we can attempt to include off-policy data. Prior attempts use importance sampling to include off-policy trajectories; however, these are known to be difficult scale to highdimensional action spaces because of rapidly degenerating importance weights (Precup, 2000) .

2.2. POLICY GRADIENT WITH FUNCTION APPROXIMATION:

Policy gradient methods with function approximation (Sutton et al., 1999) , or actor-critic methods, include a policy evaluation step, which often uses temporal difference (TD) learning to fit a critic Q w for the current policy π(θ ), and a policy improvement step which greedily optimizes the policy π against the critic estimate Q w . Significant gains in sample efficiency may be achievable using offpolicy TD learning for the critic, as in Q-learning and deterministic policy gradient (Sutton, 1990; Silver et al., 2014) , typically by means of experience replay for training deep Q networks (Mnih et al., 2015; Lillicrap et al., 2016; Gu et al., 2016b ).

One particularly relevant example of such a method is the deep deterministic policy gradient (DDPG) (Silver et al., 2014; Lillicrap et al., 2016) . The updates for this method are given below, where π θ (a t |s t ) = δ (a t = µ θ (s t )) is a deterministic policy, β is arbitrary exploration distribution, and ρ β corresponds to sampling from a replay buffer. Q(•, •) is the target network that slowly tracks Q w (Lillicrap et al., 2016) .

EQUATION

When the critic and policy are parametrized with neural networks, full optimization is expensive, and instead stochastic gradient optimization is used. The gradient in the policy improvement phase is given below, which is generally a biased gradient of J(θ ).

EQUATION

The crucial benefits of DDPG are that it does not rely on high variance REINFORCE gradients and is trainable on off-policy data. These properties make DDPG and other analogous off-policy methods significantly more sample-efficient than policy gradient methods (Lillicrap et al., 2016; Gu et al., 2016b; Duan et al., 2016) . However, the use of a biased policy gradient estimator makes analyzing its convergence and stability properties difficult.

3. Q-PROP:

In this section, we derive the Q-Prop estimator for policy gradient. The key idea from this estimator comes from observing Equations 2 and 5 and noting that the former provides an almost unbiased (see Section 2.1), but high variance gradient, while the latter provides a deterministic, but biased gradient. By using the deterministic biased estimator as a particular form of control variate (Ross, 2006; Paisley et al., 2012) for the Monte Carlo policy gradient estimator, we can effectively use both types of gradient information to construct a new estimator that in practice exhibits improved sample efficiency through the inclusion of off-policy samples while preserving the stability of on-policy Monte Carlo policy gradient.

3.1. Q-PROP ESTIMATOR:

To derive the Q-Prop gradient estimator, we start by using the first-order Taylor expansion of an arbitrary function

f (s t , a t ), f (s t , a t ) = f (s t , āt ) + ∇ a f (s t , a)| a= āt (a t -āt )

as the control variate for the policy gradient estimator. We use

EQUATION

Eq. 6 is general for arbitrary function f (s t , a t ) that is differentiable with respect to a t at an arbitrary value of āt ; however, a sensible choice is to use the critic Q w for f and µ θ (s t ) for āt to get,

EQUATION

Finally, since in practice we estimate advantages Â(s t , a t ), we write the Q-Prop estimator in terms of advantages to complete the basic derivation,

EQUATION

Eq. 8 is composed of an analytic gradient through the critic as in Eq. 5 and a residual REINFORCE gradient in Eq. 2. From the above derivation, Q-Prop is simply a Monte Carlo policy gradient estimator with a special form of control variate. The important insight comes from the fact that Q w can be trained using off-policy data as in Eq. 4. Under this setting, Q-Prop is no longer just a Monte Carlo policy gradient method, but more closely resembles an actor-critic method, where the critic can be updated off-policy but the actor is always updated on-policy with an additional REINFORCE correction term so that it remains a Monte Carlo policy gradient method regardless of the parametrization, training method, and performance of the critic. Therefore, Q-Prop can be directly combined with a number of prior techniques from both on-policy methods such as natural policy gradient (Kakade, 2001) , trust-region policy optimization (TRPO) (Schulman et al., 2015) and generalized advantage estimation (GAE) (Schulman et al., 2016) , and off-policy methods such as DDPG (Lillicrap et al., 2016) and Retrace(λ ) (Munos et al., 2016) .

Intuitively, if the critic Q w approximates Q π well, it provides a reliable gradient, reduces the estimator variance, and improves the convergence rate. Interestingly, control variate analysis in the next section shows that this is not the only circumstance where Q-Prop helps reduce variance.

3.2. CONTROL VARIATE ANALYSIS AND ADAPTIVE Q-PROP:

For Q-Prop to be applied reliably, it is crucial to analyze how the variance of the estimator changes before and after the application of control variate. Following the prior work on control variates (Ross, 2006; Paisley et al., 2012) , we first introduce η(s t ) to Eq. 8, a weighing variable that modulates the strength of control variate. This additional variable η(s t ) does not introduce bias to the estimator.

EQUATION

The variance of this estimator is given below, where m = 1...M indexes the dimension of θ ,

EQUATION

)

If we choose η(s t ) such that Var * < Var, where Var

= E ρ π [∑ m Var a t (∇ θ m log π θ (a t |s t ) Â(s t , a t ))]

is the original estimator variance measure, then we have managed to reduce the variance. Directly analyzing the above variance measure is nontrivial, for the same reason that computing the optimal baseline is difficult (Weaver & Tao, 2001) . In addition, it is often impractical to get multiple action samples from the same state, which prohibits using naïve Monte Carlo to estimate the expectations. Instead, we propose a surrogate variance measure, Var = E ρ π [Var a t ( Â(s t , a t ))]. A similar surrogate is also used by prior work on learning state-dependent baseline (Mnih & Gregor, 2014) , and the benefit is that the measure becomes more tractable,

EQUATION

Since E π [ Â(s t , a t )] = E π [ Ā(s t , a t )] = 0, the terms can be simplified as below,

EQUATION

where Σ θ (s t ) is the covariance matrix of the stochastic policy π θ . The nice property of Eq. 11 is that Var a t ( Ā) is analytical and Cov a t ( Â, Ā) can be estimated with single action sample. Using this estimate, we propose adaptive variants of Q-Prop that regulate the variance of the gradient estimate.

Adaptive Q-Prop. The optimal state-dependent factor η(s t ) can be computed per state, according to η * (s t ) = Cov a t ( Â, Ā)/Var a t ( Ā). This provides maximum reduction in variance according to Eq. 11. Substituting η * (s t ) into Eq. 11, we get Var

* = E ρ π [(1 -ρ corr ( Â, Ā) 2 )Var a t ( Â)]

, where ρ corr is the correlation coefficient, which achieves guaranteed variance reduction if at any state Ā is correlated with Â. We call this the fully adaptive Q-Prop method. An important conclusion from this analysis is that, in adaptive Q-Prop, the critic Q w does not necessarily need to be approximating Q π well to produce good results. Its Taylor expansion merely needs to be correlated with Â, positively or even negatively. This is in contrast with actor-critic methods, where performance is greatly dependent on the absolute accuracy of the critic's approximation.

Conservative and Aggressive Q-Prop. In practice, the single-sample estimate of Cov a t ( Â, Ā) has high variance itself, and we propose the following two practical implementations of adaptive Q-Prop:

(1) η(s t ) = 1 if Ĉ ov a t ( Â, Ā) > 0 and η(s t ) = 0 if otherwise, and (2) η(s t ) = sign( Ĉ ov a t ( Â, Ā)). The first implementation, which we call conservative Q-Prop, can be thought of as a more conservative version of Q-Prop, which effectively disables the control variate for some samples of the states. This is sensible as if Â and Ā are negatively correlated, it is likely that the critic is very poor. The second variant can correspondingly be termed aggressive Q-Prop, since it makes more liberal use of the control variate.

3.3. Q-PROP ALGORITHM:

Pseudo-code for the adaptive Q-Prop algorithm is provided in Algorithm 1. It is a mixture of policy gradient and actor-critic. At each iteration, it first rolls out the stochastic policy to collect on-policy Algorithm 1 Adaptive Q-Prop 1: Initialize w for critic Q w , θ for stochastic policy π θ , and replay buffer R ← / 0. 2: repeat 3:

for e = 1, . . . , E do Collect E episodes of on-policy experience using π θ 4: s 0,e ∼ p(s 0 ) 5:

for t = 0, . . . , T -1 do 6: a t,e ∼ π θ (•|s t,e ), s t+1,e ∼ p(•|s t,e , a t,e ), r t,e = r(s t,e , a t,e ) 7:

Add batch data B = {s 0:T,1:E , a 0:T -1,1:E , r 0:T -1,1:E } to replay buffer R 8:

Take E • T gradient steps on Q w using R and π θ 9:

Fit V φ (s t ) using B 10:

Compute Ât,e using GAE(λ ) and Āt,e using Eq. 7 11:

Set η t,e based on Section 3.2 12:

Compute and center the learning signals l t,e = Ât,eη t,e Āt,e 13:

Compute Take a gradient step on π θ using ∇ θ J(θ ), optionally with a trust-region constraint using B 15: until π θ converges.

∇ θ J(θ ) ≈ 1 ET ∑ e ∑ t ∇

samples, adds the batch to a replay buffer, takes a few gradient steps on the critic, computes Â and Ā, and finally applies a gradient step on the policy π θ . In our implementation, the critic Q w is fitted with off-policy TD learning using the same techniques as in DDPG (Lillicrap et al., 2016) :

EQUATION

)

V φ is fitted with the same technique in (Schulman et al., 2016) . Generalized advantage estimation (GAE) (Schulman et al., 2016) is used to estimate Â. The policy update can be done by any method that utilizes the first-order gradient and possibly the on-policy batch data, which includes trust region policy optimization (TRPO) (Schulman et al., 2015) . Importantly, this is just one possible implementation of Q-Prop, and in Appendix C we show a more general form that can interpolate between pure policy gradient and off-policy actor-critic.

3.4. LIMITATIONS:

A limitation with Q-Prop is that if data collection is very fast, e.g. using fast simulators, the compute time per episode is bound by the critic training at each iteration, and similar to that of DDPG and usually much more than that of TRPO. However, in applications where data collection speed is the bottleneck, there is sufficient time between policy updates to fit Q w well, which can be done asynchronously from the data collection, and the compute time of Q-Prop will be about the same as that of TRPO.

Another limitation is the robustness to bad critics. We empirically show that our conservative Q-Prop is more robust than standard Q-Prop and much more robust than pure off-policy actor-critic methods such as DDPG; however, estimating when an off-policy critic is reliable or not is still a fundamental problem that shall be further investigated. We can also alleviate this limitation by adopting more stable off-policy critic learning techniques such as Retrace(λ ) (Munos et al., 2016) .

4. RELATED WORK:

Variance reduction in policy gradient methods is a long-standing problem with a large body of prior work (Weaver & Tao, 2001; Greensmith et al., 2004; Schulman et al., 2016) . However, exploration of action-dependent control variates is relatively recent, with most work focusing instead on simpler baselining techniques (Ross, 2006) . A subtle exception is compatible feature approximation (Sutton et al., 1999) which can be viewed as a control variate as explained in Appendix B. Another exception is doubly robust estimator in contextual bandits (Dudík et al., 2011) , which uses a different control variate whose bias cannot be tractably corrected. Control variates were explored recently not in RL but for approximate inference in stochastic models (Paisley et al., 2012) , and the closest related work in that domain is the MuProp algorithm (Gu et al., 2016a) which uses a mean-field network as a surrogate for backpropagating a deterministic gradient through stochastic discrete variables. MuProp is not directly applicable to model-free RL because the dynamics are unknown; however, it can be if the dynamics are learned as in model-based RL (Atkeson & Santamaria, 1997; Deisenroth & Rasmussen, 2011) . This model-based Q-Prop is itself an interesting direction of research as it effectively corrects bias in model-based learning.

Part of the benefit of Q-Prop is the ability to use off-policy data to improve on-policy policy gradient methods. Prior methods that combine off-policy data with policy gradients either introduce bias (Sutton et al., 1999; Silver et al., 2014) or use importance weighting, which is known to result in degenerate importance weights in high dimensions, resulting in very high variance (Precup, 2000; Levine & Koltun, 2013) . Q-Prop provides a new approach for using off-policy data to reduce variance without introducing further bias.

Lastly, since Q-Prop uses both on-policy policy updates and off-policy critic learning, it can take advantage of prior work along both lines of research. We chose to implement Q-Prop on top of TRPO-GAE primarily for the purpose of enabling a fair comparison in the experiments, but combining Q-Prop with other on-policy update schemes and off-policy critic training methods is an interesting direction for future work. For example, Q-Prop can also be used with other on-policy policy gradient methods such as A3C (Mnih et al., 2016) and off-policy advantage estimation methods such as Retrace(λ ) (Munos et al., 2016 ), GTD2 (Sutton et al., 2009 ), emphatic TD (Sutton et al., 2015) , and WIS-LSTD (Mahmood et al., 2014) . We evaluated Q-Prop and its variants on continuous control environments from the OpenAI Gym benchmark (Brockman et al., 2016) using the MuJoCo physics simulator (Todorov et al., 2012) as shown in Figure 1 . Algorithms are identified by acronyms, followed by a number indicating batch size, except for DDPG, which is a prior online actor-critic algorithm (Lillicrap et al., 2016) . "c-" and "v-" denote conservative and aggressive Q-Prop variants as described in Section 3.2. "TR-" denotes trust-region policy optimization (Schulman et al., 2015) , while "V-" denotes vanilla policy gradient. For example, "TR-c-Q-Prop-5000" means convervative Q-Prop with the trust-region policy update, and a batch size of 5000. "VPG" and "TRPO" are vanilla policy gradient and trust-region policy optimization respectively (Schulman et al., 2016; Duan et al., 2016) . Unless otherwise stated, all policy gradient methods are implemented with GAE(λ = 0.97) (Schulman et al., 2016) . Note that TRPO-GAE is currently the state-of-the-art method on most of the OpenAI Gym benchmark tasks, though our experiments show that a well-tuned DDPG implementation sometimes achieves better results.

5. EXPERIMENTS:

(a) (b) (c) (d) (e) (f) (g)

Our algorithm implementations are built on top of the rllab TRPO and DDPG codes from Duan et al. ( 2016) and available at https://github.com/shaneshixiang/rllabplusplus. Policy and value function architectures and other training details including hyperparameter values are provided in Appendix D.

5.1. ADAPTIVE Q-PROP:

First, it is useful to identify how reliable each variant of Q-Prop is. In this section, we analyze standard Q-Prop and two adaptive variants, c-Q-Prop and a-Q-Prop, and demonstrate the stability of the method across different batch sizes. Figure 2a shows a comparison of Q-Prop variants with trust-region updates on the HalfCheetah-v1 domain, along with the best performing TRPO hyperparameters. The results are consistent with theory: conservative Q-Prop achieves much more stable performance than the standard and aggressive variants, and all Q-Prop variants significantly outperform TRPO in terms of sample efficiency, e.g. conservative Q-Prop reaches average reward of 4000 using about 10 times less samples than TRPO. Figure 2b shows the performance of conservative Q-Prop against TRPO across different batch sizes. Due to high variance in gradient estimates, TRPO typically requires very large batch sizes, e.g. 25000 steps or 25 episodes per update, to perform well. We show that our Q-Prop methods can learn even with just 1 episode per update, and achieves better sample efficiency with small batch sizes. This shows that Q-Prop significantly reduces the variance compared to the prior methods.

As we discussed in Section 1, stability is a significant challenge with state-of-the-art deep RL methods, and is very important for being able to reliably use deep RL for real world tasks. In the rest of the experiments, we will use conservative Q-Prop as the main Q-Prop implementation. In this section, we evaluate two versions of conservative Q-Prop, v-c-Q-Prop using vanilla policy gradient and TR-c-Q-Prop using trust-region updates, against other model-free algorithms on the HalfCheetah-v1 domain. Figure 3a shows that c-Q-Prop methods significantly outperform the best TRPO and VPG methods. Even Q-Prop with vanilla policy gradient is comparable to TRPO, confirming the significant benefits from variance reduction. DDPG on the other hand exhibits inconsistent performances. With proper reward scaling, i.e. "DDPG-r0.1", it outperforms other methods as well as the DDPG results reported in prior work (Duan et al., 2016; Amos et al., 2016) . This illustrates the sensitivity of DDPG to hyperparameter settings, while Q-Prop exhibits more stable, monotonic learning behaviors when compared to DDPG. In the next section we show this improved stability allows Q-Prop to outperform DDPG in more complex domains.

5.2. EVALUATION ACROSS ALGORITHMS:

Table 1 : Q-Prop, TRPO and DDPG results showing the max average rewards attained in the first 30k episodes and the episodes to cross specific reward thresholds. Q-Prop often learns more sample efficiently than TRPO and can solve difficult domains such as Humanoid better than DDPG.

6. DISCUSSION AND CONCLUSION:

We presented Q-Prop, a policy gradient algorithm that combines reliable, consistent, and potentially unbiased on-policy gradient estimation with a sample-efficient off-policy critic that acts as a control variate. The method provides a large improvement in sample efficiency compared to stateof-the-art policy gradient methods such as TRPO, while outperforming state-of-the-art actor-critic methods on more challenging tasks such as humanoid locomotion. We hope that techniques like these, which combine on-policy Monte Carlo gradient estimation with sample-efficient variance reduction through off-policy critics, will eventually lead to deep reinforcement learning algorithms that are more stable and efficient, and therefore better suited for application to complex real-world learning tasks.

This holds true when f (s t , a t ) is an arbitrary function differentiable with respect to a t and f is its first-order Taylor expansion around a t = āt , i.e. f (s t , a t ) = f (s t , āt ) + ∇ a f (s t , a)| a= āt (a tāt ).

Here, µ θ (s t ) = E π [a t ] is the mean of stochastic policy π θ . The derivation appears below:

EQUATION

B CONNECTION BETWEEN Q-PROP AND COMPATIBLE FEATURE APPROXIMATION

In this section we show that actor-critic with compatible feature approximation is a form of

control variate. A critic Q w is compatible (Sutton et al., 1999) if it satisfies (1) Q w (s t , a t ) = w T ∇ θ log π θ (a t |s t ), i.e. ∇ w Q w (s t , a t ) = ∇ θ log π θ (a t |s t ), and (2) w is fit with objective w = arg min w L(w) = arg min w E ρ π ,π [( Q(s t , a t ) -Q w (s t , a t )) 2 ],

that is fitting Q w on on-policy Monte Carlo returns. Condition (2) implies the following identity,

EQUATION

In compatible feature approximation, it directly uses Q w as control variate, rather than its Taylor expansion Qw as in Q-Prop. Using Eq. 15, the Monte Carlo policy gradient is,

EQUATION

where

I(θ ; s t ) = E π θ [∇ θ log π θ (a t |s t )∇ θ log π θ (a t |s t ) T

] is Fisher's information matrix. Thus, variance reduction depends on ability to compute or estimate I(θ ; s t ) and w effectively.

C UNIFYING POLICY GRADIENT AND ACTOR-CRITIC Q-Prop closely ties together policy gradient and actor-critic algorithms. To analyze this point, we write a generalization of Eq. 9 below, introducing two additional variables α, ρ CR :

EQUATION

Eq. 17 enables more analysis where bias generally is introduced only when α = 1 or ρ CR = ρ π . Importantly, Eq. 17 covers both policy gradient and deterministic actor-critic algorithm as its special cases. Standard policy gradient is recovered by η = 0, and deterministic actor-critic is recovered by α = 0 and ρ CR = ρ β . This allows heuristic or automatic methods for dynamically changing these variables through the learning process for optimizing different metrics, e.g. sample efficiency, convergence speed, stability. Table 2 : Implementation options and edge cases of the generalized Q-Prop estimator in Eq. 17.

Section 2.1). A natural choice is to use off-policy temporal difference learning to learn the critic Q w corresponding to policy π. This enables effectively utilizing off-policy samples without introducing further bias. An interesting alternative to this is to utilize model-based roll-outs to estimate the critic, which resembles MuProp in stochastic neural networks (Gu et al., 2016a) . Unlike prior work on using fitted dynamics model to accelerate model-free learning (Gu et al., 2016b) , this approach does not introduce bias to the gradient of the original objective.

D EXPERIMENT DETAILS:

Policy and value function architectures. The network architectures are largely based on the benchmark paper by Duan et al. (2016) . For policy gradient methods, the stochastic policy π θ (a t |s t ) = N (µ θ (s t ), Σ θ ) is a local Gaussian policy with a local state-dependent mean and a global covariance matrix. µ θ (s t ) is a neural network with 3 hidden layers of sizes 100-50-25 and tanh nonlinearities at the first 2 layers, and Σ θ is diagonal. For DDPG, the policy is deterministic and has the same architecture as µ θ except that it has an additional tanh layer at the output. V φ (s t ) for baselines and GAE is fit with the same technique by Schulman et al. (2016) , a variant of linear regression on Monte Carlo returns with soft-update constraint. For Q-Prop and DDPG, Q w (s, a) is parametrized with a neural network with 2 hidden layers of size 100 and ReLU nonlinearity, where a is included after the first hidden layer.

Training details. This section describes parameters of the training algorithms and their hyperparameter search values in {}. The optimal performing hyperparameter results are reported. Policy gradient methods (VPG, TRPO, Q-Prop) used batch sizes of {1000, 5000, 25000} time steps, step sizes of {0.1, 0.01, 0.001} for the trust-region method, and base learning rates of {0.001, 0.0001} with Adam (Kingma & Ba, 2014) for vanilla policy gradient methods. For Q-Prop and DDPG, Q w is learned with the same technique as in DDPG (Lillicrap et al., 2016) , using soft target networks with τ = 0.999, a replay buffer of size 10 6 steps, a mini-batch size of 64, and a base learning rate of {0.001, 0.0001} with Adam (Kingma & Ba, 2014) . For Q-Prop we also tuned the relative ratio of gradient steps on the critic Q w against the number of steps on the policy, in the range {0.1, 0.5, 1.0}, where 0.1 corresponds to 100 critic updates for every policy update if the batch size is 1000.

For DDPG, we swept the reward scaling using {0.01,0.1,1.0} as it is sensitive to this parameter.

:



Figures and Tables:

Figure 1: Illustrations of OpenAI Gym MuJoCo domains (Brockman et al., 2016; Duan et al., 2016): (a) Ant, (b) HalfCheetah, (c) Hopper, (d) Humanoid, (e) Reacher, (f) Swimmer, (g) Walker.

(a) Standard Q-Prop vs adaptive variants. (b) Conservative Q-Prop vs TRPO across batch sizes.

Figure 2: Average return over episodes in HalfCheetah-v1 during learning, exploring adaptive Q-Prop methods and different batch sizes. All variants of Q-Prop substantially outperform TRPO in terms of sample efficiency. TR-c-QP, conservative Q-Prop with trust-region update performs most stably across different batch sizes.

(a) Comparing algorithms on HalfCheetah-v1. (b) Comparing algorithms on Humanoid-v1.

Figure 3: Average return over episodes in HalfCheetah-v1 and Humanoid-v1 during learning, comparing Q-Prop against other model-free algorithms. Q-Prop with vanilla policy gradient outperforms TRPO on HalfCheetah. Q-Prop significantly outperforms TRPO in convergence time on Humanoid.

θ log π θ (a t,e |s t,e )l t,e + η t,e ∇ a Q w (s t,e , a)| a=µ θ (s t,e ) ∇ θ µ θ (s t,e ) 14:

Table content: <table/>

summarizes the various edge cases of Eq. 17. For example, since we derive our method from a control variates standpoint, Q w can be any function and the gradient remains almost unbiased (see off-policy TD; on-policy TD(λ ); model-based; etc. No V φ on-policy Monte Carlo fitting; E π θ [Q w (s t , a t )]; etc

Table content: <table><tr><td>Parameter</td><td>Implementation options</td><td>Introduce bias?</td></tr><tr><td>Q w</td><td/><td/></tr><tr><td/><td/><td>No</td></tr><tr><td>λ</td><td>0 ≤ λ ≤ 1</td><td>Yes, except λ = 1</td></tr><tr><td>α</td><td>α ≥ 0</td><td>Yes, except α = 1</td></tr><tr><td>η</td><td>any η</td><td>No</td></tr><tr><td>ρ CR</td><td>ρ of any policy</td><td>Yes, except ρ CR = ρ π</td></tr></table>

Peer review (iclr2017):
**Edit: Based on the discussion below, my main problem (#2) was not correct. I have changed my overall rating from a 3 to a 7** This paper makes a fascinating observation: one can introduce an action-dependent baseline (control variate) into REINFORCE, which introduces bias, and then include a correction term to remove the bias. The variance of the correction term is low relative to the REINFORCE update and the action-dependent baseline, and so this results in benefits. However, the paper is poorly executed. Below I list my concerns. 1. The paper tries to distinguish between *policy gradient* methods and *actor critic* methods by defining them in a non-standard way. Specifically, when this paper says *policy gradient* it means REINFORCE. Historically, the two have meant different things: some policy gradient algorithms are actor-critics (e.g., Degris et al*s INAC algorithm) while others are not (e.g. REINFORCE). 2. The proposed Q-Prop algorithm includes many interesting design choices that make in unclear what the real source of improved performance is. Is the improved performance due to the use of the action-dependent control variate? Would the same setup but using a state-value baseline still perform just as well? Are the performance benefits due to the use of an off-policy advantage estimation algorithm, GAE(lambda)? Or, would performance have been similar with an on-policy advantage estimation algorithm? What about if a different off-policy advantage estimation algorithm was used, like Retrace(lambda), GTD2, ETD, or WIS-LSTD? Or, is the improved performance due to the use of a replay buffer? Comparisons are not performed between variants of Q-Prop that show the importances of these different components. Rather the authors opt to show better performance on a benchmark task. I find this to be non-scientific, and more of a paper showing a feat of engineering (by combining many different ideas) than it is a research paper that studies the details of which parts of Q-Prop make it work well. For example, after reading this paper, it is not clear whether having the action-dependent baseline (or using the first order Taylor approximation for the baseline) is beneficial or not - it could be that the strong performance comes from GAE(lambda) or the use of a replay buffer. At the very least I would have expected comparisons to Q-Prop using a state-value baseline (which would then be a variant of REINFORCE using off-policy data and a replay buffer, and which would show whether the action-dependent baseline is important). 3. There is a fair amount of discussion about unbiased policy gradient algorithms, which is not accurate. Most policy gradient algorithms are biased, and making them unbiased tends to hurt performance. This is discussed in the paper *Bias in Natural Actor-Critic Algorithms*, which applies to non-natural algorithms as well. Also, I suspect that the use of GAE(lambda) results in the exact sort of bias discussed in that paper, even when lambda=1. As a result, Q-Prop may act more like an average reward method than expected. This should be discussed. 4. The proposed algorithm can be applied to deep architectures, just as most linear-time policy gradient algorithms can. However, it does not have to be applied to deep architectures. The emphasis on *deep* therefore seems to detract from the core ideas of the paper. 5. The paper repeatedly says that importance sampling based methods result in high variance. This ignores weighted importance sampling methods that have very low variance. A good example of this is Mahmood et al*s WIS-LSTD algorithm. WIS-LSTD has high computational complexity, so it would only be compared to on non-deep RL problems, of which there are plenty. Alternatively, algorithms like Retrace(lambda) have quite low variance since the likelihood ratios are never bigger than one. Others might argue that ETD algorithms are currently the most effective. The simple dismissal of these algorithms because the original importance sampling estimator proposed in 2000 has high variance is not sufficient. 6. The paper does not compare to natural actor-critic algorithms. Once the weights, w, have been computed, REINFORCE uses samples of states from the normalized discounted state distribution and samples of the corresponding returns to estimate the policy gradient. One of the main reasons Q-Prop should work better than REINFORCE is that it includes a control variate that reduces the variance of the policy gradient update after w has been computed. Now, compare this to natural policy gradient algorithms. Once the weights, w, have been computed (admittedly, using compatible features for the advantage estimation but any features for the state-value estimation) the resulting update is = w. That is, is has zero variance and does not require additional sampling. It is as though a perfect control variate was used. Furthermore, natural gradient algorithms can be applied to deep architectures. Degris et al*s INAC algorithm is linear time. Desjardin et al*s *natural neural networks* paper also discusses efficient implementations of natural gradients for neural networks. Dabney*s Natural Temporal Difference algorithms have linear time variants that fit this paper*s description of actor-critic algorithms. To summarize, given the weights w, REINFORCE has high variance, and Q-Prop claims to reduce the variance of REINFORCE. However, natural policy gradient methods have zero variance given the weights w. So, what is the benefit of Q-Prop over natural gradient algorithms using off-policy value function estimation methods to estimate Q (or A)? That is, why should we expect Q-Prop to perform better than NAC-LSTD using GAE(lambda) with experience replay in place of LSTD? 7. Equation (2) is false. The right side is proportional to the left side, not equal to it. There is a (1-gamma) term missing. There are also other typos throughout (e.g., Q and A sometimes are missing their action arguments). Although I have listed my concerns, I would like to re-iterate that I do find the idea of an action-dependent baseline fascinating. My problem with this paper is with its execution, not with the novelty, impact, or quality of the core idea.