Addressing Function Approximation Error in Actor-Critic Methods
Scott Fujimoto Herke van Hoof David Meger


[
Addressing Function Approximation Error in Actor-Critic Methods














equal*


Scott Fujimotomcgill
Herke van Hoofams
David Megermcgill


mcgillMcGill University, Montreal, Canada
amsUniversity of Amsterdam, Amsterdam, Netherlands
Scott Fujimotoscott.fujimoto@mail.mcgill.ca
reinforcement learning, deep learning

0.3in
]









  



In value-based reinforcement learning methods such as deep Q-learning, function approximation errors are known to lead  to overestimated value estimates and suboptimal policies. We show that this problem persists in an actor-critic setting and propose novel mechanisms to minimize its effects on both the actor and the critic. Our algorithm builds on Double Q-learning, by taking the minimum value between a pair of critics to limit overestimation. We draw the connection between target networks and overestimation bias, and suggest delaying policy updates to reduce per-update error and further improve performance. We evaluate our method on the suite of OpenAI gym tasks, outperforming the state of the art in every environment tested.





§ INTRODUCTION



In reinforcement learning problems with discrete action spaces, the issue of value overestimation as a result of function approximation errors is well-studied. However, similar issues with actor-critic methods in continuous control domains have been largely left untouched. In this paper, we show overestimation bias and the accumulation of error in temporal difference methods are present in an actor-critic setting. Our proposed method addresses these issues, and greatly outperforms the current state of the art.

Overestimation bias is a property of Q-learning in which the maximization of a noisy value estimate induces a consistent overestimation <cit.>. In a function approximation setting, this noise is unavoidable given the imprecision of the estimator. This inaccuracy is further exaggerated by the nature of temporal difference learning <cit.>, in which an estimate of the value function is updated using the estimate of a subsequent state. This means using an imprecise estimate within each update will lead to an accumulation of error.
Due to overestimation bias, this accumulated error can cause arbitrarily bad states to be estimated as high value, resulting in suboptimal policy updates and divergent behavior.

This paper begins by establishing this overestimation property is also present for deterministic policy gradients <cit.>, in the continuous control setting. Furthermore, we find the ubiquitous solution in the discrete action setting, Double DQN <cit.>, to be ineffective in an actor-critic setting. During training, Double DQN estimates the value of the current policy with a separate target value function, allowing actions to be evaluated without maximization bias. Unfortunately, due to the slow-changing policy in an actor-critic setting, the current and target value estimates remain too similar to avoid maximization bias. This can be dealt with by adapting an older variant, Double Q-learning <cit.>, to an actor-critic format by using a pair of independently trained critics. While this allows for a less biased value estimation, even an unbiased estimate with high variance can still lead to future overestimations in local regions of state space, which in turn can negatively affect the global policy. To address this concern, we propose a clipped Double Q-learning variant which leverages the notion that a value estimate suffering from overestimation bias can be used as an approximate upper-bound to the true value estimate. This favors underestimations, which do not tend to be propagated during learning, as actions with low value estimates are avoided by the policy.

Given the connection of noise to overestimation bias, this paper contains a number of components that address variance reduction. First, we show that target networks, a common approach in deep Q-learning methods, are critical for variance reduction by reducing the accumulation of errors. Second, to address the coupling of value and policy, we propose delaying policy updates until the value estimate has converged. Finally, we introduce a novel regularization strategy, where a SARSA-style update bootstraps similar action estimates to further reduce variance. 

Our modifications are applied to the state of the art actor-critic method for continuous control, Deep Deterministic Policy Gradient algorithm (DDPG) <cit.>, to form the Twin Delayed Deep Deterministic policy gradient algorithm (TD3), an actor-critic algorithm which considers the interplay between function approximation error in both policy and value updates. We evaluate our algorithm on seven continuous control domains from OpenAI gym <cit.>, where we outperform the state of the art by a wide margin.

Given the recent concerns in reproducibility <cit.>, we run our experiments across a large number of seeds with fair evaluation metrics, perform ablation studies across each contribution, and open source both our code and learning curves (<https://github.com/sfujim/TD3>). 




§ RELATED WORK



Function approximation error and its effect on bias and variance in reinforcement learning algorithms have been studied in prior works <cit.>. Our work focuses on two outcomes that occur as the result of estimation error, namely overestimation bias and a high variance build-up.  

Several approaches exist to reduce the effects of overestimation bias due to function approximation and policy optimization in Q-learning. Double Q-learning uses two independent estimators to make unbiased value estimates <cit.>. Other approaches have focused directly on reducing the variance <cit.>, minimizing over-fitting to early high variance estimates <cit.>, or through corrective terms <cit.>. Further, the variance of the value estimate has been considered directly for risk-aversion <cit.> and exploration <cit.>, but without connection to overestimation bias. 

The concern of variance due to the accumulation of error in temporal difference learning has been largely dealt with by either minimizing the size of errors at each time step or mixing off-policy and Monte-Carlo returns. Our work shows the importance of a standard technique, target networks, for the reduction of per-update error, and develops a regularization technique for the variance reduction by averaging over value estimates. Concurrently, <cit.> showed smoothed value functions could be used to train stochastic policies with reduced variance and improved performance. Methods with multi-step returns offer a trade-off between accumulated estimation bias and variance induced by the policy and the environment. These methods have been shown to be an effective approach, through importance sampling <cit.>, distributed methods <cit.>, and approximate bounds <cit.>. However, rather than provide a direct solution to the accumulation of error, these methods circumvent the problem by considering a longer horizon. Another approach is a reduction in the discount factor <cit.>, reducing the contribution of each error.

Our method builds on the Deterministic Policy Gradient algorithm (DPG) <cit.>, an actor-critic method which uses a learned value estimate to train a deterministic policy. An extension of DPG to deep reinforcement learning, DDPG <cit.>, has shown to produce state of the art results with an efficient number of iterations.
Orthogonal to our approach, recent improvements to DDPG include distributed methods <cit.>, along with multi-step returns and prioritized experience replay <cit.>, and distributional methods <cit.>. 






§ BACKGROUND



Reinforcement learning considers the paradigm of an agent interacting with its environment with the aim of learning reward-maximizing behavior. At each discrete time step t, with a given state s ∈𝒮, the agent selects actions a ∈𝒜 with respect to its policy π: 𝒮→𝒜, receiving a reward r and the new state of the environment s'. The return is defined as the discounted sum of rewards R_t = ∑_i=t^T^i-t r(s_i, a_i), where  is a discount factor determining the priority of short-term rewards. 

In reinforcement learning, the objective is to find the optimal policy π_ϕ, with parameters ϕ, which maximizes the expected return J(ϕ) = _s_i ∼ p_π, a_i ∼π R_0. For continuous control, parametrized policies π_ϕ can be updated by taking the gradient of the expected return ∇_ϕ J(ϕ). In actor-critic methods, the policy, known as the actor, can be updated through the deterministic policy gradient algorithm <cit.>:

    ∇_ϕ J(ϕ) = _s ∼ p_π∇_a Q^π(s,a)|_a=π(s)∇_ϕπ_ϕ(s) .

Q^π(s,a) = _s_i ∼ p_π, a_i ∼π R_t | s, a, the expected return when performing action a in state s and following π after, is known as the critic or the value function. 

In Q-learning, the value function can be learned using temporal difference learning <cit.>, an update rule based on the Bellman equation <cit.>. The Bellman equation is a fundamental relationship between the value of a state-action pair (s,a) and the value of the subsequent state-action pair (s',a'):

    Q^π(s, a) = r + _s', a' Q^π(s', a') ,    a' ∼π(s').


For a large state space, the value can be estimated with a differentiable function approximator Q_θ(s, a), with parameters θ. In deep Q-learning <cit.>, the network is updated by using temporal difference learning with a secondary frozen target network Q_θ'(s,a) to maintain a fixed objective y over multiple updates:

    y = r +  Q_θ'(s',a'),    a' ∼π_ϕ'(s'),

where the actions are selected from a target actor network π_ϕ'. The weights of a target network are either updated periodically to exactly match the weights of the current network, or by some proportion τ at each time step θ' ←τθ + (1 - τ) θ'. This update can be applied in an off-policy fashion, sampling random mini-batches of transitions from an experience replay buffer <cit.>.




§ OVERESTIMATION BIAS
 


In Q-learning with discrete actions, the value estimate is updated with a greedy target y = r + max_a' Q(s',a'), however, if the target is susceptible to error , then the maximum over the value along with its error will generally be greater than the true maximum, _[max_a' (Q(s',a') + )] ≥max_a' Q(s',a') <cit.>. As a result, even initially zero-mean error can cause value updates to result in a consistent overestimation bias, which is then propagated through the Bellman equation. This is problematic as errors induced by function approximation are unavoidable. 

While in the discrete action setting overestimation bias is an obvious artifact from the analytical maximization, the presence and effects of overestimation bias is less clear in an actor-critic setting where the policy is updated via gradient descent. We begin by proving that the value estimate in deterministic policy gradients will be an overestimation under some basic assumptions in Section <ref> and then propose a clipped variant of Double Q-learning in an actor-critic setting to reduce overestimation bias in Section <ref>. 




 §.§ Overestimation Bias in Actor-Critic
 


In actor-critic methods the policy is updated with respect to the value estimates of an approximate critic. In this section we assume the policy is updated using the deterministic policy gradient, and show that the update induces overestimation in the value estimate. 
Given current policy parameters ϕ, let ϕ_approx define the parameters from the actor update induced by the maximization of the approximate critic Q_θ(s,a) and ϕ_true the parameters from the hypothetical actor update with respect to the true underlying value function Q^π(s,a) (which is not known during learning): 

    ϕ_approx   = ϕ + α/Z_1_s ∼ p_π∇_ϕπ_ϕ(s) ∇_a Q_θ(s,a)|_a=π_ϕ(s)
    ϕ_true   = ϕ + α/Z_2_s ∼ p_π∇_ϕπ_ϕ(s) ∇_a Q^π(s,a)|_a=π_ϕ(s),
 
where we assume Z_1 and Z_2 are chosen to normalize the gradient, i.e., such that Z^-1||[·]|| = 1. Without normalized gradients, overestimation bias is still guaranteed to occur with slightly stricter conditions. We examine this case further in the supplementary material. We denote π_approx and π_true as the policy with parameters ϕ_approx and ϕ_true respectively. 

As the gradient direction is a local maximizer, there exists _1 sufficiently small such that if α≤_1 then the approximate value of π_approx will be bounded below by the approximate value of π_true:

    Q_θ(s, π_approx(s)) ≥ Q_θ(s, π_true(s)) .

Conversely, there exists _2 sufficiently small such that if α≤_2 then the true value of π_approx will be bounded above by the true value of π_true:

    Q^π(s, π_true(s)) ≥ Q^π(s, π_approx(s)) .

If in expectation the value estimate is at least as large as the true value with respect to ϕ_true, 
Q_θ s, π_true(s) ≥ Q^π s, π_true(s), then Equations (<ref>) and (<ref>) imply that if α < min(_1, _2), then the value estimate will be overestimated:

    Q_θ(s, π_approx(s)) ≥ Q^π(s, π_approx(s)) .


Although this overestimation may be minimal with each update, the presence of error raises two concerns. Firstly, the overestimation may develop into a more significant bias over many updates if left unchecked. Secondly, an inaccurate value estimate may lead to poor policy updates. This is particularly problematic because a feedback loop is created, in which suboptimal actions might be highly rated by the suboptimal critic, reinforcing the suboptimal action in the next policy update.



Does this theoretical overestimation occur in practice for state-of-the-art methods? We answer this question by plotting the value estimate of DDPG <cit.> over time while it learns on the OpenAI gym environments Hopper-v1 and Walker2d-v1 <cit.>. In Figure <ref>, we graph the average value estimate over 10000 states and compare it to an estimate of the true value. The true value is estimated using the average discounted return over 1000 episodes following the current policy, starting from states sampled from the replay buffer. A very clear overestimation bias occurs from the learning procedure, which contrasts with the novel method that we describe in the following section, Clipped Double Q-learning, which greatly reduces overestimation by the critic. 




 §.§ Clipped Double Q-Learning for Actor-Critic
 




While several approaches to reducing overestimation bias have been proposed, we find them ineffective in an actor-critic setting. This section introduces a novel clipped variant of Double Q-learning <cit.>, which can replace the critic in any actor-critic method. 

In Double Q-learning, the greedy update is disentangled from the value function by maintaining two separate value estimates, each of which is used to update the other. If the value estimates are independent, they can be used to make unbiased estimates of the actions selected using the opposite value estimate. In Double DQN <cit.>, the authors propose using the target network as one of the value estimates, and obtain a policy by greedy maximization of the current value network rather than the target network. In an actor-critic setting, an analogous update uses the current policy rather than the target policy in the learning target:

    y = r +  Q_θ'(s', π_ϕ(s')).


In practice however, we found that with the slow-changing policy in actor-critic, the current and target networks were too similar to make an independent estimation, and offered little improvement.

Instead, the original Double Q-learning formulation can be used, with a pair of actors (π_ϕ_1, π_ϕ_2) and critics (Q_θ_1, Q_θ_2), where π_ϕ_1 is optimized with respect to Q_θ_1 and π_ϕ_2 with respect to Q_θ_2:

    y_1    = r +  Q_θ'_2(s',π_ϕ_1(s')) 
    
    y_2    = r +  Q_θ'_1(s',π_ϕ_2(s')).

We measure the overestimation bias in Figure <ref>, which demonstrates that the actor-critic Double DQN suffers from a similar overestimation as DDPG (as shown in Figure <ref>). While Double Q-learning is more effective, it does not entirely eliminate the overestimation. We further show this reduction is not sufficient experimentally in Section <ref>. 

As π_ϕ_1 optimizes with respect to Q_θ_1, using an independent estimate in the target update of Q_θ_1 would avoid the bias introduced by the policy update. 
However the critics are not entirely independent, due to the use of the opposite critic in the learning targets, as well as the same replay buffer. As a result, for some states s we will have Q_θ_2(s, π_ϕ_1(s)) > Q_θ_1(s, π_ϕ_1(s)). 

This is problematic because Q_θ_1(s, π_ϕ_1(s)) will generally overestimate the true value, and in certain areas of the state space the overestimation will be further exaggerated.  

To address this problem, we propose to simply upper-bound the less biased value estimate Q_θ_2 by the biased estimate Q_θ_1. This results in taking the minimum between the two estimates, to give the target update of our Clipped Double Q-learning algorithm: 

    y_1 = r + min_i=1,2 Q_θ'_i(s', π_ϕ_1(s')).



With Clipped Double Q-learning, the value target cannot introduce any additional overestimation over using the standard Q-learning target. 
While this update rule may induce an underestimation bias, this is far preferable to overestimation bias, as unlike overestimated actions, the value of underestimated actions will not be explicitly propagated through the policy update. 



In implementation, computational costs can be reduced by using a single actor optimized with respect to Q_θ_1. We then use the same target y_2=y_1 for Q_θ_2. If Q_θ_2 > Q_θ_1 then the update is identical to the standard update and induces no additional bias. If Q_θ_2 < Q_θ_1, this suggests overestimation has occurred and the value is reduced similar to Double Q-learning. A proof of convergence in the finite MDP setting follows from this intuition. We provide formal details and justification in the supplementary material.

A secondary benefit is that by treating the function approximation error as a random variable we can see that the minimum operator should provide higher value to states with lower variance estimation error, as the expected minimum of a set of random variables decreases as the variance of the random variables increases. This effect means that the minimization in Equation (<ref>) will lead to a preference for states with low-variance value estimates, leading to safer policy updates with stable learning targets.




§ ADDRESSING VARIANCE
 


While Section <ref> deals with the contribution of variance to overestimation bias, we also argue that variance itself should be directly addressed. Besides the impact on overestimation bias, high variance estimates provide a noisy gradient for the policy update. This is known to reduce learning speed <cit.> as well as hurt performance in practice. In this section we emphasize the importance of minimizing error at each update, build the connection between target networks and estimation error and propose modifications to the learning procedure of actor-critic for variance reduction. 




 §.§ Accumulating Error
 


Due to the temporal difference update, where an estimate of the value function is built from an estimate of a subsequent state, there is a build up of error. While it is reasonable to expect small error for an individual update, these estimation errors can accumulate, resulting in the potential for large overestimation bias and suboptimal policy updates. This is exacerbated in a function approximation setting where the Bellman equation is never exactly satisfied, and each update leaves some amount of residual TD-error δ(s,a):

    Q_θ(s, a) = r + [Q_θ(s', a')] - δ(s,a).
 
It can then be shown that rather than learning an estimate of the expected return, the value estimate approximates the expected return minus the expected discounted sum of future TD-errors:

    Q_θ(s_t, a_t) = r_t +  [ Q_θ(s_t+1, a_t+1) ] - δ_t 
       = r_t +  r_t+1 +  Q_θ(s_t+2,a_t+2) - δ_t+1  - δ_t 
    
    
    
    
       = _s_i ∼ p_π, a_i ∼π∑_i=t^T ^i-t (r_i - δ_i) .

If the value estimate is a function of future reward and estimation error, it follows that the variance of the estimate will be proportional to the variance of future reward and estimation error. Given a large discount factor , the variance can grow rapidly with each update if the error from each update is not tamed. Furthermore each gradient update only reduces error with respect to a small mini-batch which gives no guarantees about the size of errors in value estimates outside the mini-batch. 




 §.§ Target Networks and Delayed Policy Updates
 


In this section we examine the relationship between target networks and function approximation error, and show the use of a stable target reduces the growth of error. This insight allows us to consider the interplay between high variance estimates and policy performance, when designing reinforcement learning algorithms. 
 
Target networks are a well-known tool to achieve stability in deep reinforcement learning. As deep function approximators require multiple gradient updates to converge, target networks provide a stable objective in the learning procedure, and allow a greater coverage of the training data. Without a fixed target, each update may leave residual error which will begin to accumulate. While the accumulation of error can be detrimental in itself, when paired with a policy maximizing over the value estimate, it can result in wildly divergent values. 

To provide some intuition, we examine the learning behavior with and without target networks on both the critic and actor in Figure <ref>, where we graph the value, in a similar manner to Figure <ref>, in the Hopper-v1 environment. In (a) we compare the behavior with a fixed policy and in (b) we examine the value estimates with a policy that continues to learn, trained with the current value estimate. The target networks use a slow-moving update rate, parametrized by τ. 



While updating the value estimate without target networks (τ=1) increases the volatility, all update rates result in similar convergent behaviors when considering a fixed policy. However, when the policy is trained with the current value estimate, the use of fast-updating target networks results in highly divergent behavior. 

When do actor-critic methods fail to learn?
These results suggest that the divergence that occurs without target networks is the result of policy updates with a high variance value estimate. Figure <ref>, as well as Section <ref>, suggest failure can occur due to the interplay between the actor and critic updates. Value estimates diverge through overestimation when the policy is poor, and the policy will become poor if the value estimate itself is inaccurate. 

If target networks can be used to reduce the error over multiple updates, and policy updates on high-error states cause divergent behavior, then the policy network should be updated at a lower frequency than the value network, to first minimize error before introducing a policy update.
We propose delaying policy updates until the value error is as small as possible. 

The modification is to only update the policy and target networks after a fixed number of updates d to the critic. To ensure the TD-error remains small, we update the target networks slowly θ' ←τθ + (1 - τ) θ'. 

By sufficiently delaying the policy updates we limit the likelihood of repeating updates with respect to an unchanged critic. The less frequent policy updates that do occur will use a value estimate with lower variance, and in principle, should result in higher quality policy updates. This creates a two-timescale algorithm, as often required for convergence in the linear setting <cit.>. The effectiveness of this strategy is captured by our empirical results presented in Section <ref>, which show an improvement in performance while using fewer policy updates. 




 §.§ Target Policy Smoothing Regularization
 


A concern with deterministic policies is they can overfit to narrow peaks in the value estimate. When updating the critic, a learning target using a deterministic policy is highly susceptible to inaccuracies induced by function approximation error, increasing the variance of the target. This induced variance can be reduced through regularization. We introduce a regularization strategy for deep value learning, target policy smoothing, which mimics the learning update from SARSA <cit.>. Our approach enforces the notion that similar actions should have similar value. While the function approximation does this implicitly, the relationship between similar actions can be forced explicitly by modifying the training procedure. We propose that fitting the value of a small area around the target action

    y = r + _ Q_θ'(s',  π_ϕ'(s') + ) ,

would have the benefit of smoothing the value estimate by bootstrapping off of similar state-action value estimates. In practice, we can approximate this expectation over actions by adding a small amount of random noise to the target policy and averaging over mini-batches. This makes our modified target update: 

    y    = r +  Q_θ'(s', π_ϕ'(s') + ), 
       ∼((0, ), -c, c),

where the added noise is clipped to keep the target close to the original action. 
The outcome is an algorithm reminiscent of Expected SARSA <cit.>, where the value estimate is instead learned off-policy and the noise added to the target policy is chosen independently of the exploration policy.
The value estimate learned is with respect to a noisy policy defined by the parameter . 

Intuitively, it is known that policies derived from SARSA value estimates tend to be safer, as they provide higher value to actions resistant to perturbations. Thus, this style of update can additionally lead to improvement in stochastic domains with failure cases. A similar idea was introduced concurrently by <cit.>, smoothing over Q_θ, rather than Q_θ'. 




§ EXPERIMENTS



We present the Twin Delayed Deep Deterministic policy gradient algorithm (TD3), which builds on the Deep Deterministic Policy Gradient algorithm (DDPG) <cit.> by applying the modifications described in Sections <ref>, <ref> and <ref> to increase the stability and performance with consideration of function approximation error. 
TD3 maintains a pair of critics along with a single actor. For each time step, we update the pair of critics towards the minimum target value of actions selected by the target policy:

    y    = r + min_i=1,2 Q_θ'_i(s', π_ϕ'(s') + ), 
       ∼((0, ), -c, c).

Every d iterations, the policy is updated with respect to Q_θ_1 following the deterministic policy gradient algorithm <cit.>. TD3 is summarized in Algorithm <ref>.








 §.§ Evaluation
 

 




To evaluate our algorithm, we measure its performance on the suite of MuJoCo continuous control tasks <cit.>, interfaced through OpenAI Gym <cit.> (Figure <ref>). To allow for reproducible comparison, we use the original set of tasks from <cit.> with no modifications to the environment or reward. 

For our implementation of DDPG <cit.>, we use a two layer feedforward neural network of 400 and 300 hidden nodes respectively, with rectified linear units (ReLU) between each layer for both the actor and critic, and a final tanh unit following the output of the actor. Unlike the original DDPG, the critic receives both the state and action as input to the first layer. Both network parameters are updated using Adam <cit.> with a learning rate of 10^-3. After each time step, the networks are trained with a mini-batch of a 100 transitions, sampled uniformly from a replay buffer containing the entire history of the agent. 

The target policy smoothing is implemented by adding ∼(0, 0.2) to the actions chosen by the target actor network, clipped to (-0.5, 0.5), delayed policy updates consists of only updating the actor and target critic network every d iterations, with d=2. While a larger d would result in a larger benefit with respect to accumulating errors, for fair comparison, the critics are only trained once per time step, and training the actor for too few iterations would cripple learning. Both target networks are updated with τ=0.005. 

To remove the dependency on the initial parameters of the policy we use a purely exploratory policy for the first 10000 time steps of stable length environments (HalfCheetah-v1 and Ant-v1) and the first 1000 time steps for the remaining environments. Afterwards, we use an off-policy exploration strategy, adding Gaussian noise 𝒩(0, 0.1) to each action. Unlike the original implementation of DDPG, we used uncorrelated noise for exploration as we found noise drawn from the Ornstein-Uhlenbeck <cit.> process offered no performance benefits.

Each task is run for 1 million time steps with evaluations every 5000 time steps, where each evaluation reports the average reward over 10 episodes with no exploration noise. Our results are reported over 10 random seeds of the Gym simulator and the network initialization. 

We compare our algorithm against DDPG <cit.> as well as the state of art policy gradient algorithms: PPO <cit.>, ACKTR <cit.> and TRPO <cit.>, as implemented by OpenAI's baselines repository <cit.>, and SAC <cit.>, as implemented by the author's GitHub[See the supplementary material for hyper-parameters and a discussion on the discrepancy in the reported results of SAC.]. 

Additionally, we compare our method with our re-tuned version of DDPG, which includes all architecture and hyper-parameter modifications to DDPG without any of our proposed adjustments. 
A full comparison between our re-tuned version and the baselines DDPG is provided in the supplementary material.

Our results are presented in Table <ref> and learning curves in Figure <ref>. TD3 matches or outperforms all other algorithms in both final performance and learning speed across all tasks. 




 §.§ Ablation Studies



We perform ablation studies to understand the contribution of each individual component: Clipped Double Q-learning (Section <ref>), delayed policy updates (Section <ref>) and target policy smoothing (Section <ref>). We present our results in Table <ref> in which we compare the performance of removing each component from TD3 along with our modifications to the architecture and hyper-parameters. Additional learning curves can be found in the supplementary material. 

The significance of each component varies task to task. While the addition of only a single component causes insignificant improvement in most cases, the addition of combinations performs at a much higher level.  The full algorithm outperforms every other combination in most tasks. Although the actor is trained for only half the number of iterations, the inclusion of delayed policy update generally improves performance, while reducing training time. 



We additionally compare the effectiveness of the actor-critic variants of Double Q-learning <cit.> and Double DQN <cit.>, denoted DQ-AC and DDQN-AC respectively, in Table <ref>. For fairness in comparison, these methods also benefited from delayed policy updates, target policy smoothing and use our architecture and hyper-parameters. Both methods were shown to reduce overestimation bias less than Clipped Double Q-learning in Section <ref>. This is reflected empirically, as both methods result in insignificant improvements over TD3 - CDQ, with an exception in the Ant-v1 environment, which appears to benefit greatly from any overestimation reduction. As the inclusion of Clipped Double Q-learning into our full method outperforms both prior methods, this suggests that subduing the overestimations from the unbiased estimator is an effective measure to improve performance. 




§ CONCLUSION



Overestimation has been identified as a key problem in value-based methods. In this paper, we establish overestimation bias is also problematic in actor-critic methods. We find the common solutions for reducing overestimation bias in deep Q-learning with discrete actions are ineffective in an actor-critic setting, and develop a novel variant of Double Q-learning which limits possible overestimation. Our results demonstrate that mitigating overestimation can greatly improve the performance of modern algorithms. 

Due to the connection between noise and overestimation, we examine the accumulation of errors from temporal difference learning. Our work investigates the importance of a standard technique in deep reinforcement learning, target networks, and examines their role in limiting errors from imprecise function approximation and stochastic optimization. Finally, we introduce a SARSA-style regularization technique which modifies the temporal difference target to bootstrap off similar state-action pairs. 

Taken together, these improvements define our proposed approach, the Twin Delayed Deep Deterministic policy gradient algorithm (TD3), which greatly improves both the learning speed and performance of DDPG in a number of challenging tasks in the continuous control setting. Our algorithm exceeds the performance of numerous state of the art algorithms. As our modifications are simple to implement, they can be easily added to any other actor-critic algorithm. 


icml2018




Supplementary Material










§ PROOF OF CONVERGENCE OF CLIPPED DOUBLE Q-LEARNING
 


In a version of Clipped Double Q-learning for a finite MDP setting, we maintain two tabular value estimates Q^A, Q^B. At each time step we select actions a^* = _a Q^A(s,a) and then perform an update by setting target y:

    a^*    = _a Q^A(s',a) 
    
    y    = r + min(Q^A(s',a^*), Q^B(s',a^*)),

and update the value estimates with respect to the target and learning rate α_t(s,a): 

    Q^A(s,a)    = Q^A(s,a) + α_t(s,a)(y - Q^A(s,a)) 
    
    Q^B(s,a)    = Q^B(s,a) + α_t(s,a)(y - Q^B(s,a)).


In a finite MDP setting, Double Q-learning is often used to deal with noise induced by random rewards or state transitions, and so either Q^A or Q^B is updated randomly. However, in a function approximation setting, the interest may be more towards the approximation error and thus we can update both Q^A and Q^B at each iteration. The proof extends naturally to updating either randomly. 

The proof borrows heavily from the proof of convergence of SARSA <cit.> as well as Double Q-learning <cit.>. The proof of lemma 1 can be found in <cit.>, building on a proposition from <cit.>. 

Lemma 1. Consider a stochastic process (ζ_t, Δ_t, F_t), t ≥ 0 where ζ_t, Δ_t, F_t: X →ℝ satisfy the equation:

    Δ_t+1(x_t) = (1 - ζ_t(x_t))Δ_t(x_t) + ζ_t(x_t)F_t(x_t),

where x_t ∈ X and t=0,1,2,.... Let P_t be a sequence of increasing σ-fields such that ζ_0 and Δ_0 are P_0-measurable and ζ_t, Δ_t and F_t-1 are P_t-measurable, t=1,2,.... Assume that the following hold:


  * The set X is finite.

  * ζ_t(x_t) ∈ [0,1], ∑_t ζ_t(x_t) = ∞, ∑_t (ζ_t(x_t))^2 < ∞ with probability 1 and ∀ x ≠ x_t : ζ(x) = 0.

  * ||  F_t | P_t  || ≤κ || Δ_t || + c_t where κ∈ [0,1) and c_t converges to 0 with probability 1.

  * VarF_t(x_t)|P_t ≤ K(1 + κ||Δ_t||)^2, where K is some constant 

Where ||·|| denotes the maximum norm. Then Δ_t converges to 0 with probability 1. 

Theorem 1. Given the following conditions:


  * Each state action pair is sampled an infinite number of times. 

  * The MDP is finite. 

  * ∈ [0,1).

  * Q values are stored in a lookup table.

  * Both Q^A and Q^B receive an infinite number of updates.

  * The learning rates satisfy α_t(s,a) ∈ [0,1], ∑_t α_t(s,a) = ∞, ∑_t(α_t(s,a))^2 < ∞ with probability 1 and α_t(s,a) = 0, ∀(s,a) ≠ (s_t,a_t).

  * Varr(s,a)  < ∞, ∀ s,a. 

Then Clipped Double Q-learning will converge to the optimal value function Q^*, as defined by the Bellman optimality equation, with probability 1.

Proof of Theorem 1. We apply Lemma 1 with P_t = {Q^A_0, Q^B_0, s_0, a_0, α_0, r_1, s_1, ..., s_t, a_t}, X = S × A, Δ_t = Q^A_t - Q^*, ζ_t = α_t.  

First note that condition 1 and 4 of the lemma holds by the conditions 2 and 7 of the theorem respectively. Lemma condition 2 holds by the theorem condition 6 along with our selection of ζ_t = α_t.  

Defining a^* = _a Q^A(s_t+1, a) we have

    Δ_t+1(s_t,a_t)    = (1 - α_t(s_t,a_t))(Q^A_t(s_t,a_t) - Q^*(s_t,a_t)) 
            + α_t(s_t,a_t)(r_t + min (Q^A_t(s_t+1, a^*), Q^B_t(s_t+1, a^*)) - Q^*(s_t,a_t)) 
       = (1 - α_t(s_t,a_t))Δ_t(s_t,a_t) + α_t(s_t,a_t)F_t(s_t,a_t)),

where we have defined F_t(s_t,a_t) as:

    F_t(s_t, a_t)    = r_t + min (Q^A_t(s_t+1, a^*), Q^B_t(s_t+1, a^*)) - Q^*_t(s_t,a_t) 
       =r_t + min (Q^A_t(s_t+1, a^*), Q^B_t(s_t+1, a^*)) - Q^*_t(s_t,a_t) +  Q^A_t(s_t+1, a^*) -  Q^A_t(s_t+1, a^*) 
       = F^Q_t(s_t,a_t) + c_t,

where F^Q_t = r_t +  Q^A_t(s_t+1, a^*) - Q^*_t(s_t,a_t) denotes the value of F_t under standard Q-learning and c_t = min (Q^A_t(s_t+1, a^*), Q^B_t(s_t+1, a^*)) -  Q^A_t(s_t+1, a^*).
As F^Q_t | P_t ≤ ||Δ_t|| is a well-known result, then condition 3 of lemma 1 holds if it can be shown that c_t converges to 0 with probability 1. 

Let y = r_t + min (Q^B_t(s_t+1, a^*), Q^A_t(s_t+1, a^*)) and Δ^BA_t(s_t,a_t) = Q^B_t(s_t,a_t) - Q^A_t(s_t,a_t), where c_t converges to 0 if Δ^BA converges to 0.
The update of Δ^BA_t at time t is the sum of updates of Q^A and Q^B:

    Δ^BA_t+1(s_t,a_t)    = Δ^BA_t(s_t,a_t) + α_t(s_t,a_t)  y - Q^B_t(s_t,a_t) - (y - Q^A_t(s_t,a_t)) 
       = Δ^BA_t(s_t,a_t) + α_t(s_t,a_t)  Q^A_t(s_t,a_t) - Q^B_t(s_t,a_t) 
       = (1 - α_t(s_t,a_t))Δ^BA_t(s_t,a_t).

Clearly Δ^BA_t will converge to 0, which then shows we have satisfied condition 3 of lemma 1, implying that Q^A(s_t,a_t) converges to Q^*_t(s_t,a_t). Similarly, we get convergence of Q^B(s_t,a_t) to the optimal vale function by choosing Δ_t = Q^B_t - Q^* and repeating the same arguments, thus proving theorem 1. 




§ OVERESTIMATION BIAS IN DETERMINISTIC POLICY GRADIENTS
 


If the gradients from the deterministic policy gradient update are unnormalized, this overestimation is still guaranteed to occur under a slightly stronger condition on the expectation of the value estimate. Assume the approximate value function is equal to the true value function, in expectation over the steady-state distribution, with respect to policy parameters between the original policy and in the direction of the true policy update:

    _s ∼π Q_θ(s, π_new(s)) = _s ∼π Q^π(s, π_new(s)) 
       ∀ϕ_new∈ [ϕ,ϕ + β (ϕ_true - ϕ)]  such that β > 0.

Noting that ϕ_true maximizes the rate of change of the true value Δ^π_true = Q^π(s,π_true(s)) - Q^π(s,π_ϕ(s)), Δ^π_true≥Δ^π_approx. By the given condition <ref> the maximal rate of change of the approximate value must be at least as great Δ^θ_approx≥Δ^π_true. Given Q_θ(s, π_ϕ) = Q^π(s, π_ϕ) this implies Q_θ(s,π_approx(s)) ≥ Q^π(s,π_true(s)) ≥ Q^π(s,π_approx(s)), showing an overestimation of the value function.





§ DDPG NETWORK AND HYPER-PARAMETER COMPARISON




DDPG Critic Architecture

DDPG Actor Architecture


Our Critic Architecture

Our Actor Architecture







§ ADDITIONAL IMPLEMENTATION DETAILS



For clarity in presentation, certain implementation details were omitted, which we describe here. For the most complete possible description of the algorithm, code can be found on our GitHub (<https://github.com/sfujim/TD3>). 

Our implementation of both DDPG and TD3 follows a standard practice in deep Q-learning, in which the update differs for terminal transitions. For transitions where the episode terminates by reaching some failure state, and not due to the episode running until the max horizon, the value of Q(s, ·) is set to 0 in the target y: 

    y = 
      
       r     if terminal  s'  and  t < max horizon
    
       r +  Q_θ'(s',π_ϕ'(s'))    else


For target policy smoothing (Section <ref>), the added noise is clipped to the range of possible actions, to avoid error introduced by using values of impossible actions: 

    y    = r +  Q_θ'(s',  (π_ϕ'(s') + , min action, max action)), 
       ∼((0, ), -c, c).








§ SOFT ACTOR-CRITIC IMPLEMENTATION DETAILS



For our implementation of Soft Actor-Critic <cit.> we use the code provided by the author (<https://github.com/haarnoja/sac>), using the hyper-parameters described by the paper. We use a Gaussian mixture policy with 4 Gaussian distributions, except for the Reacher-v1 task, where we use a single Gaussian distribution due to numerical instability issues in the provided implementation. We use the environment-dependent reward scaling as described by the authors, multiplying the rewards by 3 for Walker2d-v1 and Ant-v1, and 1 for all remaining environments. 

For fair comparison with our method, we train for only 1 iteration per time step, rather than the 4 iterations used by the results reported by the authors. This along with fewer total time steps should explain for the discrepancy in results on some of the environments. Additionally, we note this comparison is against a prior version of Soft Actor-Critic, while the most recent variant includes our Clipped Double Q-learning in the value update and produces competitive results to TD3 on most tasks. 






§ ADDITIONAL LEARNING CURVES
 













