Addressing Function Approximation Error in Actor-Critic Methods β€” part 3/4

Cleaned-text code points [28666, 43525). Bibliography omitted here; source.md includes it.

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 ( Sutton & Barto, 1998 ) . 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 β€² ) + Ο΅ ) ] , y=r+\mathbb{E}_{\epsilon}\left[Q_{\theta^{\prime}}(s^{\prime},\pi_{\phi^{\prime}}(s^{\prime})+\epsilon)\right], (13) 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 \displaystyle y = r + Ξ³ ​ Q ΞΈ β€² ​ ( s β€² , Ο€ Ο• β€² ​ ( s β€² ) + Ο΅ ) , \displaystyle=r+\gamma Q_{\theta^{\prime}}(s^{\prime},\pi_{\phi^{\prime}}(s^{\prime})+\epsilon), (14) Ο΅ ∼ clip ( 𝒩 ⁑ ( 0 , Οƒ ) , βˆ’ c , c ) , \displaystyle\epsilon\sim\clip(\mathcal{N}(0,\sigma),-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 ( Van Seijen et al., 2009 ) , 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 Οƒ \sigma .

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 Nachum et al. (2018) , smoothing over Q ΞΈ Q_{\theta} , rather than Q ΞΈ β€² Q_{\theta^{\prime}} .

## 6 Experiments

We present the Twin Delayed Deep Deterministic policy gradient algorithm (TD3), which builds on the Deep Deterministic Policy Gradient algorithm (DDPG) ( Lillicrap et al., 2015 ) by applying the modifications described in Sections 4.2 , 5.2 and 5.3 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 \displaystyle y = r + Ξ³ ​ min i = 1 , 2 ​ Q ΞΈ i β€² ​ ( s β€² , Ο€ Ο• β€² ​ ( s β€² ) + Ο΅ ) , \displaystyle=r+\gamma\min_{i=1,2}Q_{\theta^{\prime}_{i}}(s^{\prime},\pi_{\phi^{\prime}}(s^{\prime})+\epsilon), (15) Ο΅ ∼ clip ( 𝒩 ⁑ ( 0 , Οƒ ) , βˆ’ c , c ) . \displaystyle\epsilon\sim\clip(\mathcal{N}(0,\sigma),-c,c). Every d d iterations, the policy is updated with respect to Q ΞΈ 1 Q_{\theta_{1}} following the deterministic policy gradient algorithm ( Silver et al., 2014 ) . TD3 is summarized in Algorithm 1 .

### 6.1 Evaluation

To evaluate our algorithm, we measure its performance on the suite of MuJoCo continuous control tasks ( Todorov et al., 2012 ) , interfaced through OpenAI Gym ( Brockman et al., 2016 ) (Figure 4 ). To allow for reproducible comparison, we use the original set of tasks from Brockman et al. (2016) with no modifications to the environment or reward.

For our implementation of DDPG ( Lillicrap et al., 2015 ) , 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 ( Kingma & Ba, 2014 ) with a learning rate of 10 βˆ’ 3 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 ) \epsilon\sim\mathcal{N}(0,0.2) to the actions chosen by the target actor network, clipped to ( βˆ’ 0.5 , 0.5 ) (-0.5,0.5) , delayed policy updates consists of only updating the actor and target critic network every d d iterations, with d = 2 d=2 . While a larger d 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 \tau=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 ) \mathcal{N}(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 ( Uhlenbeck & Ornstein, 1930 ) 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 ( Lillicrap et al., 2015 ) as well as the state of art policy gradient algorithms: PPO ( Schulman et al., 2017 ) , ACKTR ( Wu et al., 2017 ) and TRPO ( Schulman et al., 2015 ) , as implemented by OpenAI’s baselines repository ( Dhariwal et al., 2017 ) , and SAC ( Haarnoja et al., 2018 ) , as implemented by the author’s GitHub 1 1 1 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 1 and learning curves in Figure 5 . TD3 matches or outperforms all other algorithms in both final performance and learning speed across all tasks.

### 6.2 Ablation Studies

We perform ablation studies to understand the contribution of each individual component: Clipped Double Q-learning (Section 4.2 ), delayed policy updates (Section 5.2 ) and target policy smoothing (Section 5.3 ). We present our results in Table 2 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 ( Van Hasselt, 2010 ) and Double DQN ( Van Hasselt et al., 2016 ) , denoted DQ-AC and DDQN-AC respectively, in Table 2 . 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 4 . 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.

## 7 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.

## Appendix A 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^{A} , Q B Q^{B} . At each time step we select actions a βˆ— = argmax a Q A ​ ( s , a ) a^{*}=\argmax_{a}Q^{A}(s,a) and then perform an update by setting target y y : a βˆ— \displaystyle a^{*} = argmax a Q A ​ ( s β€² , a ) \displaystyle=\argmax_{a}Q^{A}(s^{\prime},a) (16) y \displaystyle y = r + Ξ³ ​ min ⁑ ( Q A ​ ( s β€² , a βˆ— ) , Q B ​ ( s β€² , a βˆ— ) ) , \displaystyle=r+\gamma\min(Q^{A}(s^{\prime},a^{*}),Q^{B}(s^{\prime},a^{*})), and update the value estimates with respect to the target and learning rate Ξ± t ​ ( s , a ) \alpha_{t}(s,a) : Q A ​ ( s , a ) \displaystyle Q^{A}(s,a) = Q A ​ ( s , a ) + Ξ± t ​ ( s , a ) ​ ( y βˆ’ Q A ​ ( s , a ) ) \displaystyle=Q^{A}(s,a)+\alpha_{t}(s,a)(y-Q^{A}(s,a)) (17) Q B ​ ( s , a ) \displaystyle Q^{B}(s,a) = Q B ​ ( s , a ) + Ξ± t ​ ( s , a ) ​ ( y βˆ’ Q B ​ ( s , a ) ) . \displaystyle=Q^{B}(s,a)+\alpha_{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 Q^{A} or Q B 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 Q^{A} and Q B Q^{B} at each iteration. The proof extends naturally to updating either randomly.

The proof borrows heavily from the proof of convergence of SARSA ( Singh et al., 2000 ) as well as Double Q-learning ( Van Hasselt, 2010 ) . The proof of lemma 1 can be found in Singh et al. (2000) , building on a proposition from Bertsekas (1995) .

Lemma 1. Consider a stochastic process ( ΞΆ t , Ξ” t , F t ) , t β‰₯ 0 (\zeta_{t},\Delta_{t},F_{t}),t\geq 0 where ΞΆ t , Ξ” t , F t : X β†’ ℝ \zeta_{t},\Delta_{t},F_{t}:X\rightarrow\mathbb{R} satisfy the equation: Ξ” t + 1 ​ ( x t ) = ( 1 βˆ’ ΞΆ t ​ ( x t ) ) ​ Ξ” t ​ ( x t ) + ΞΆ t ​ ( x t ) ​ F t ​ ( x t ) , \Delta_{t+1}(x_{t})=(1-\zeta_{t}(x_{t}))\Delta_{t}(x_{t})+\zeta_{t}(x_{t})F_{t}(x_{t}), (18) where x t ∈ X x_{t}\in X and t = 0 , 1 , 2 , … t=0,1,2,... . Let P t P_{t} be a sequence of increasing Οƒ \sigma -fields such that ΞΆ 0 \zeta_{0} and Ξ” 0 \Delta_{0} are P 0 P_{0} -measurable and ΞΆ t , Ξ” t \zeta_{t},\Delta_{t} and F t βˆ’ 1 F_{t-1} are P t P_{t} -measurable, t = 1 , 2 , … t=1,2,... . Assume that the following hold: 1. The set X X is finite.

2. ΞΆ t ​ ( x t ) ∈ [ 0 , 1 ] , βˆ‘ t ΞΆ t ​ ( x t ) = ∞ , βˆ‘ t ( ΞΆ t ​ ( x t ) ) 2 < ∞ \zeta_{t}(x_{t})\in[0,1],\sum_{t}\zeta_{t}(x_{t})=\infty,\sum_{t}(\zeta_{t}(x_{t}))^{2}<\infty with probability 1 1 and βˆ€ x β‰  x t : ΞΆ ⁑ ( x ) = 0 \forall x\neq x_{t}:\zeta(x)=0 .

3. β€– 𝔼 ⁑ [ F t | P t ] β€– ≀ ΞΊ | | Ξ” t | | + c t ||\mathbb{E}\left[F_{t}|P_{t}\right]||\leq\kappa||\Delta_{t}||+c_{t} where ΞΊ ∈ [ 0 , 1 ) \kappa\in[0,1) and c t c_{t} converges to 0 0 with probability 1 1 .

4. Var [ F t ​ ( x t ) | P t ] ≀ K ​ ( 1 + ΞΊ ​ β€– Ξ” t β€– ) 2 \left[F_{t}(x_{t})|P_{t}\right]\leq K(1+\kappa||\Delta_{t}||)^{2} , where K K is some constant

Where | | β‹… | | ||\cdot|| denotes the maximum norm. Then Ξ” t \Delta_{t} converges to 0 0 with probability 1 1 .

Theorem 1. Given the following conditions: 1. Each state action pair is sampled an infinite number of times.

2. The MDP is finite.

3. γ ∈ [ 0 , 1 ) \gamma\in[0,1) .

4. Q values are stored in a lookup table.

5. Both Q A Q^{A} and Q B Q^{B} receive an infinite number of updates.

6. The learning rates satisfy Ξ± t ​ ( s , a ) ∈ [ 0 , 1 ] , βˆ‘ t Ξ± t ​ ( s , a ) = ∞ , βˆ‘ t ( Ξ± t ​ ( s , a ) ) 2 < ∞ \alpha_{t}(s,a)\in[0,1],\sum_{t}\alpha_{t}(s,a)=\infty,\sum_{t}(\alpha_{t}(s,a))^{2}<\infty with probability 1 1 and Ξ± t ​ ( s , a ) = 0 , βˆ€ ( s , a ) β‰  ( s t , a t ) \alpha_{t}(s,a)=0,\forall(s,a)\neq(s_{t},a_{t}) .

7. Var [ r ⁑ ( s , a ) ] < ∞ , βˆ€ s , a \left[r(s,a)\right]<\infty,\forall s,a .

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

Proof of Theorem 1. We apply Lemma 1 with P t = { Q 0 A , Q 0 B , s 0 , a 0 , Ξ± 0 , r 1 , s 1 , … , s t , a t } , X = S Γ— A , Ξ” t = Q t A βˆ’ Q βˆ— , ΞΆ t = Ξ± t P_{t}=\{Q^{A}_{0},Q^{B}_{0},s_{0},a_{0},\alpha_{0},r_{1},s_{1},...,s_{t},a_{t}\},X=S\times A,\Delta_{t}=Q^{A}_{t}-Q^{*},\zeta_{t}=\alpha_{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 \zeta_{t}=\alpha_{t} .