Addressing Function Approximation Error in Actor-Critic Methods — part 1/4
Cleaned-text code points [0, 14498). Bibliography omitted here; source.md includes it.
# Supplementary Material
###### Abstract
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.
###### Keywords:
## 1 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 ( Thrun & Schwartz, 1993 ) . 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 ( Sutton, 1988 ) , 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 ( Silver et al., 2014 ) , in the continuous control setting. Furthermore, we find the ubiquitous solution in the discrete action setting, Double DQN ( Van Hasselt et al., 2016 ) , 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 ( Van Hasselt, 2010 ) , 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) ( Lillicrap et al., 2015 ) , 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 ( Brockman et al., 2016 ) , where we outperform the state of the art by a wide margin.
Given the recent concerns in reproducibility ( Henderson et al., 2017 ) , 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 ).
## 2 Related Work
Function approximation error and its effect on bias and variance in reinforcement learning algorithms have been studied in prior works ( Pendrith et al., 1997 ; Mannor et al., 2007 ) . 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 ( Van Hasselt, 2010 ; Van Hasselt et al., 2016 ) . Other approaches have focused directly on reducing the variance ( Anschel et al., 2017 ) , minimizing over-fitting to early high variance estimates ( Fox et al., 2016 ) , or through corrective terms ( Lee et al., 2013 ) . Further, the variance of the value estimate has been considered directly for risk-aversion ( Mannor & Tsitsiklis, 2011 ) and exploration ( O’Donoghue et al., 2017 ) , 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, Nachum et al. (2018) 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 ( Precup et al., 2001 ; Munos et al., 2016 ) , distributed methods ( Mnih et al., 2016 ; Espeholt et al., 2018 ) , and approximate bounds ( He et al., 2016 ) . 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 ( Petrik & Scherrer, 2009 ) , reducing the contribution of each error.
Our method builds on the Deterministic Policy Gradient algorithm (DPG) ( Silver et al., 2014 ) , an actor-critic method which uses a learned value estimate to train a deterministic policy. An extension of DPG to deep reinforcement learning, DDPG ( Lillicrap et al., 2015 ) , 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 ( Popov et al., 2017 ) , along with multi-step returns and prioritized experience replay ( Schaul et al., 2016 ; Horgan et al., 2018 ) , and distributional methods ( Bellemare et al., 2017 ; Barth-Maron et al., 2018 ) .
## 3 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 t , with a given state s ∈ 𝒮 s\in\mathcal{S} , the agent selects actions a ∈ 𝒜 a\in\mathcal{A} with respect to its policy π : 𝒮 → 𝒜 \pi:\mathcal{S}\rightarrow\mathcal{A} , receiving a reward r r and the new state of the environment s ′ s^{\prime} . The return is defined as the discounted sum of rewards R t = ∑ i = t T γ i − t r ( s i , a i ) R_{t}=\sum_{i=t}^{T}\gamma^{i-t}r(s_{i},a_{i}) , where γ \gamma is a discount factor determining the priority of short-term rewards.
In reinforcement learning, the objective is to find the optimal policy π ϕ \pi_{\phi} , with parameters ϕ \phi , which maximizes the expected return J ( ϕ ) = 𝔼 s i ∼ p π , a i ∼ π [ R 0 ] J(\phi)=\mathbb{E}_{s_{i}\sim p_{\pi},a_{i}\sim\pi}\left[R_{0}\right] . For continuous control, parametrized policies π ϕ \pi_{\phi} can be updated by taking the gradient of the expected return ∇ ϕ J ( ϕ ) \nabla_{\phi}J(\phi) . In actor-critic methods, the policy, known as the actor, can be updated through the deterministic policy gradient algorithm ( Silver et al., 2014 ) : ∇ ϕ J ( ϕ ) = 𝔼 s ∼ p π [ ∇ a Q π ( s , a ) | a = π ( s ) ∇ ϕ π ϕ ( s ) ] . \nabla_{\phi}J(\phi)=\mathbb{E}_{s\sim p_{\pi}}\left[\nabla_{a}Q^{\pi}(s,a)|_{a=\pi(s)}\nabla_{\phi}\pi_{\phi}(s)\right]. (1) Q π ( s , a ) = 𝔼 s i ∼ p π , a i ∼ π [ R t | s , a ] Q^{\pi}(s,a)=\mathbb{E}_{s_{i}\sim p_{\pi},a_{i}\sim\pi}\left[R_{t}|s,a\right] , the expected return when performing action a a in state s s and following π \pi after, is known as the critic or the value function.
In Q-learning, the value function can be learned using temporal difference learning ( Sutton, 1988 ; Watkins, 1989 ) , an update rule based on the Bellman equation ( Bellman, 1957 ) . The Bellman equation is a fundamental relationship between the value of a state-action pair ( s , a ) (s,a) and the value of the subsequent state-action pair ( s ′ , a ′ ) (s^{\prime},a^{\prime}) : Q π ( s , a ) = r + γ 𝔼 s ′ , a ′ [ Q π ( s ′ , a ′ ) ] , a ′ ∼ π ( s ′ ) . Q^{\pi}(s,a)=r+\gamma\mathbb{E}_{s^{\prime},a^{\prime}}\left[Q^{\pi}(s^{\prime},a^{\prime})\right],\quad a^{\prime}\sim\pi(s^{\prime}). (2)
For a large state space, the value can be estimated with a differentiable function approximator Q θ ( s , a ) Q_{\theta}(s,a) , with parameters θ \theta . In deep Q-learning ( Mnih et al., 2015 ) , the network is updated by using temporal difference learning with a secondary frozen target network Q θ ′ ( s , a ) Q_{\theta^{\prime}}(s,a) to maintain a fixed objective y y over multiple updates: y = r + γ Q θ ′ ( s ′ , a ′ ) , a ′ ∼ π ϕ ′ ( s ′ ) , y=r+\gamma Q_{\theta^{\prime}}(s^{\prime},a^{\prime}),\quad a^{\prime}\sim\pi_{\phi^{\prime}}(s^{\prime}), (3) where the actions are selected from a target actor network π ϕ ′ \pi_{\phi^{\prime}} . The weights of a target network are either updated periodically to exactly match the weights of the current network, or by some proportion τ \tau at each time step θ ′ ← τ θ + ( 1 − τ ) θ ′ \theta^{\prime}\leftarrow\tau\theta+(1-\tau)\theta^{\prime} . This update can be applied in an off-policy fashion, sampling random mini-batches of transitions from an experience replay buffer ( Lin, 1992 ) .
## 4 Overestimation Bias
In Q-learning with discrete actions, the value estimate is updated with a greedy target y = r + γ max a ′ Q ( s ′ , a ′ ) y=r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime}) , however, if the target is susceptible to error ϵ \epsilon , 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 ′ ) \mathbb{E}_{\epsilon}[\max_{a^{\prime}}(Q(s^{\prime},a^{\prime})+\epsilon)]\geq\max_{a^{\prime}}Q(s^{\prime},a^{\prime}) ( Thrun & Schwartz, 1993 ) . 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 4.1 and then propose a clipped variant of Double Q-learning in an actor-critic setting to reduce overestimation bias in Section 4.2 .
### 4.1 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 ϕ \phi , let ϕ approx \phi_{\textnormal{approx}} define the parameters from the actor update induced by the maximization of the approximate critic Q θ ( s , a ) Q_{\theta}(s,a) and ϕ true \phi_{\textnormal{true}} the parameters from the hypothetical actor update with respect to the true underlying value function Q π ( s , a ) Q^{\pi}(s,a) (which is not known during learning): ϕ approx \displaystyle\phi_{\textnormal{approx}} = ϕ + α Z 1 𝔼 s ∼ p π [ ∇ ϕ π ϕ ( s ) ∇ a Q θ ( s , a ) | a = π ϕ ( s ) ] \displaystyle=\phi+\frac{\alpha}{Z_{1}}\mathbb{E}_{s\sim p_{\pi}}\left[\nabla_{\phi}\pi_{\phi}(s)\nabla_{a}Q_{\theta}(s,a)|_{a=\pi_{\phi}(s)}\right] (4) ϕ true \displaystyle\phi_{\textnormal{true}} = ϕ + α Z 2 𝔼 s ∼ p π [ ∇ ϕ π ϕ ( s ) ∇ a Q π ( s , a ) | a = π ϕ ( s ) ] , \displaystyle=\phi+\frac{\alpha}{Z_{2}}\mathbb{E}_{s\sim p_{\pi}}\left[\nabla_{\phi}\pi_{\phi}(s)\nabla_{a}Q^{\pi}(s,a)|_{a=\pi_{\phi}(s)}\right], where we assume Z 1 Z_{1} and Z 2 Z_{2} are chosen to normalize the gradient, i.e., such that Z − 1 ‖ 𝔼 [ ⋅ ] ‖ = 1 Z^{-1}||\mathbb{E}[\cdot]||=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 \pi_{\textnormal{approx}} and π true \pi_{\textnormal{true}} as the policy with parameters ϕ approx \phi_{\textnormal{approx}} and ϕ true \phi_{\textnormal{true}} respectively.