Addressing Function Approximation Error in Actor-Critic Methods — part 2/4
Cleaned-text code points [14498, 28666). Bibliography omitted here; source.md includes it.
As the gradient direction is a local maximizer, there exists ϵ 1 \epsilon_{1} sufficiently small such that if α ≤ ϵ 1 \alpha\leq\epsilon_{1} then the approximate value of π approx \pi_{\textnormal{approx}} will be bounded below by the approximate value of π true \pi_{\textnormal{true}} : 𝔼 [ Q θ ( s , π approx ( s ) ) ] ≥ 𝔼 [ Q θ ( s , π true ( s ) ) ] . \mathbb{E}\left[Q_{\theta}(s,\pi_{\textnormal{approx}}(s))\right]\geq\mathbb{E}\left[Q_{\theta}(s,\pi_{\textnormal{true}}(s))\right]. (5) Conversely, there exists ϵ 2 \epsilon_{2} sufficiently small such that if α ≤ ϵ 2 \alpha\leq\epsilon_{2} then the true value of π approx \pi_{\textnormal{approx}} will be bounded above by the true value of π true \pi_{\textnormal{true}} : 𝔼 [ Q π ( s , π true ( s ) ) ] ≥ 𝔼 [ Q π ( s , π approx ( s ) ) ] . \mathbb{E}\left[Q^{\pi}(s,\pi_{\textnormal{true}}(s))\right]\geq\mathbb{E}\left[Q^{\pi}(s,\pi_{\textnormal{approx}}(s))\right]. (6) If in expectation the value estimate is at least as large as the true value with respect to ϕ t r u e \phi_{true} , 𝔼 [ Q θ ( s , π true ( s ) ) ] ≥ 𝔼 [ Q π ( s , π true ( s ) ) ] \mathbb{E}\left[Q_{\theta}\left(s,\pi_{\textnormal{true}}(s)\right)\right]\geq\mathbb{E}\left[Q^{\pi}\left(s,\pi_{\textnormal{true}}(s)\right)\right] , then Equations ( 5 ) and ( 6 ) imply that if α < min ( ϵ 1 , ϵ 2 ) \alpha<\min(\epsilon_{1},\epsilon_{2}) , then the value estimate will be overestimated: 𝔼 [ Q θ ( s , π approx ( s ) ) ] ≥ 𝔼 [ Q π ( s , π approx ( s ) ) ] . \mathbb{E}\left[Q_{\theta}(s,\pi_{\textnormal{approx}}(s))\right]\geq\mathbb{E}\left[Q^{\pi}(s,\pi_{\textnormal{approx}}(s))\right]. (7)
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 ( Lillicrap et al., 2015 ) over time while it learns on the OpenAI gym environments Hopper-v1 and Walker2d-v1 ( Brockman et al., 2016 ) . In Figure 1 , 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.
### 4.2 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 ( Van Hasselt, 2010 ) , 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 ( Van Hasselt et al., 2016 ) , 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 ′ ) ) . y=r+\gamma Q_{\theta^{\prime}}(s^{\prime},\pi_{\phi}(s^{\prime})). (8) 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 \pi_{\phi_{1}} , π ϕ 2 \pi_{\phi_{2}} ) and critics ( Q θ 1 Q_{\theta_{1}} , Q θ 2 Q_{\theta_{2}} ), where π ϕ 1 \pi_{\phi_{1}} is optimized with respect to Q θ 1 Q_{\theta_{1}} and π ϕ 2 \pi_{\phi_{2}} with respect to Q θ 2 Q_{\theta_{2}} : y 1 \displaystyle y_{1} = r + γ Q θ 2 ′ ( s ′ , π ϕ 1 ( s ′ ) ) \displaystyle=r+\gamma Q_{\theta^{\prime}_{2}}(s^{\prime},\pi_{\phi_{1}}(s^{\prime})) (9) y 2 \displaystyle y_{2} = r + γ Q θ 1 ′ ( s ′ , π ϕ 2 ( s ′ ) ) . \displaystyle=r+\gamma Q_{\theta^{\prime}_{1}}(s^{\prime},\pi_{\phi_{2}}(s^{\prime})). We measure the overestimation bias in Figure 2 , which demonstrates that the actor-critic Double DQN suffers from a similar overestimation as DDPG (as shown in Figure 1 ). 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 6.1 .
As π ϕ 1 \pi_{\phi_{1}} optimizes with respect to Q θ 1 Q_{\theta_{1}} , using an independent estimate in the target update of Q θ 1 Q_{\theta_{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 s we will have Q θ 2 ( s , π ϕ 1 ( s ) ) > Q θ 1 ( s , π ϕ 1 ( s ) ) Q_{\theta_{2}}(s,\pi_{\phi_{1}}(s))>Q_{\theta_{1}}(s,\pi_{\phi_{1}}(s)) . This is problematic because Q θ 1 ( s , π ϕ 1 ( s ) ) Q_{\theta_{1}}(s,\pi_{\phi_{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 Q_{\theta_{2}} by the biased estimate Q θ 1 Q_{\theta_{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 ′ ) ) . y_{1}=r+\gamma\min_{i=1,2}Q_{\theta^{\prime}_{i}}(s^{\prime},\pi_{\phi_{1}}(s^{\prime})). (10) 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 Q_{\theta_{1}} . We then use the same target y 2 = y 1 y_{2}=y_{1} for Q θ 2 Q_{\theta_{2}} . If Q θ 2 > Q θ 1 Q_{\theta_{2}}>Q_{\theta_{1}} then the update is identical to the standard update and induces no additional bias. If Q θ 2 < Q θ 1 Q_{\theta_{2}}<Q_{\theta_{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 ( 10 ) will lead to a preference for states with low-variance value estimates, leading to safer policy updates with stable learning targets.
## 5 Addressing Variance
While Section 4 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 ( Sutton & Barto, 1998 ) 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.
### 5.1 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 ) \delta(s,a) : Q θ ( s , a ) = r + γ 𝔼 [ Q θ ( s ′ , a ′ ) ] − δ ( s , a ) . Q_{\theta}(s,a)=r+\gamma\mathbb{E}[Q_{\theta}(s^{\prime},a^{\prime})]-\delta(s,a). (11) 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 \displaystyle Q_{\theta}(s_{t},a_{t})=r_{t}+\gamma\mathbb{E}[Q_{\theta}(s_{t+1},a_{t+1})]-\delta_{t} = r t + γ 𝔼 [ r t + 1 + γ 𝔼 [ Q θ ( s t + 2 , a t + 2 ) − δ t + 1 ] ] − δ t \displaystyle=r_{t}+\gamma\mathbb{E}\left[r_{t+1}+\gamma\mathbb{E}\left[Q_{\theta}(s_{t+2},a_{t+2})-\delta_{t+1}\right]\right]-\delta_{t} = 𝔼 s i ∼ p π , a i ∼ π [ ∑ i = t T γ i − t ( r i − δ i ) ] . \displaystyle=\mathbb{E}_{s_{i}\sim p_{\pi},a_{i}\sim\pi}\left[\sum_{i=t}^{T}\gamma^{i-t}(r_{i}-\delta_{i})\right]. (12) 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 γ \gamma , 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.
### 5.2 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 3 , where we graph the value, in a similar manner to Figure 1 , 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 τ \tau .
While updating the value estimate without target networks ( τ = 1 \tau=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 3 , as well as Section 4 , 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 d to the critic. To ensure the TD-error remains small, we update the target networks slowly θ ′ ← τ θ + ( 1 − τ ) θ ′ \theta^{\prime}\leftarrow\tau\theta+(1-\tau)\theta^{\prime} .
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 ( Konda & Tsitsiklis, 2003 ) . The effectiveness of this strategy is captured by our empirical results presented in Section 6.1 , which show an improvement in performance while using fewer policy updates.
### 5.3 Target Policy Smoothing Regularization