Addressing Function Approximation Error in Actor-Critic Methods — part 4/4
Cleaned-text code points [43525, 53143). Bibliography omitted here; source.md includes it.
Defining a ∗ = argmax a Q A ( s t + 1 , a ) a^{*}=\argmax_{a}Q^{A}(s_{t+1},a) we have Δ t + 1 ( s t , a t ) \displaystyle\Delta_{t+1}(s_{t},a_{t}) = ( 1 − α t ( s t , a t ) ) ( Q t A ( s t , a t ) − Q ∗ ( s t , a t ) ) \displaystyle=(1-\alpha_{t}(s_{t},a_{t}))(Q^{A}_{t}(s_{t},a_{t})-Q^{*}(s_{t},a_{t})) (19) + α t ( s t , a t ) ( r t + γ min ( Q t A ( s t + 1 , a ∗ ) , Q t B ( s t + 1 , a ∗ ) ) − Q ∗ ( s t , a t ) ) \displaystyle+\alpha_{t}(s_{t},a_{t})(r_{t}+\gamma\min(Q^{A}_{t}(s_{t+1},a^{*}),Q^{B}_{t}(s_{t+1},a^{*}))-Q^{*}(s_{t},a_{t})) OPEN = ( 1 − α t ( s t , a t ) ) Δ t ( s t , a t ) + α t ( s t , a t ) F t ( s t , a t ) ) , \displaystyle=(1-\alpha_{t}(s_{t},a_{t}))\Delta_{t}(s_{t},a_{t})+\alpha_{t}(s_{t},a_{t})F_{t}(s_{t},a_{t})), where we have defined F t ( s t , a t ) F_{t}(s_{t},a_{t}) as: F t ( s t , a t ) \displaystyle F_{t}(s_{t},a_{t}) = r t + γ min ( Q t A ( s t + 1 , a ∗ ) , Q t B ( s t + 1 , a ∗ ) ) − Q t ∗ ( s t , a t ) \displaystyle=r_{t}+\gamma\min(Q^{A}_{t}(s_{t+1},a^{*}),Q^{B}_{t}(s_{t+1},a^{*}))-Q^{*}_{t}(s_{t},a_{t}) (20) = r t + γ min ( Q t A ( s t + 1 , a ∗ ) , Q t B ( s t + 1 , a ∗ ) ) − Q t ∗ ( s t , a t ) + γ Q t A ( s t + 1 , a ∗ ) − γ Q t A ( s t + 1 , a ∗ ) \displaystyle=r_{t}+\gamma\min(Q^{A}_{t}(s_{t+1},a^{*}),Q^{B}_{t}(s_{t+1},a^{*}))-Q^{*}_{t}(s_{t},a_{t})+\gamma Q^{A}_{t}(s_{t+1},a^{*})-\gamma Q^{A}_{t}(s_{t+1},a^{*}) = F t Q ( s t , a t ) + c t , \displaystyle=F^{Q}_{t}(s_{t},a_{t})+c_{t}, where F t Q = r t + γ Q t A ( s t + 1 , a ∗ ) − Q t ∗ ( s t , a t ) F^{Q}_{t}=r_{t}+\gamma Q^{A}_{t}(s_{t+1},a^{*})-Q^{*}_{t}(s_{t},a_{t}) denotes the value of F t F_{t} under standard Q-learning and c t = γ min ( Q t A ( s t + 1 , a ∗ ) , Q t B ( s t + 1 , a ∗ ) ) − γ Q t A ( s t + 1 , a ∗ ) c_{t}=\gamma\min(Q^{A}_{t}(s_{t+1},a^{*}),Q^{B}_{t}(s_{t+1},a^{*}))-\gamma Q^{A}_{t}(s_{t+1},a^{*}) . As 𝔼 [ F t Q | P t ] ≤ γ ‖ Δ t ‖ \mathbb{E}\left[F^{Q}_{t}|P_{t}\right]\leq\gamma||\Delta_{t}|| is a well-known result, then condition 3 of lemma 1 holds if it can be shown that c t c_{t} converges to 0 with probability 1.
Let y = r t + γ min ( Q t B ( s t + 1 , a ∗ ) , Q t A ( s t + 1 , a ∗ ) ) y=r_{t}+\gamma\min(Q^{B}_{t}(s_{t+1},a^{*}),Q^{A}_{t}(s_{t+1},a^{*})) and Δ t B A ( s t , a t ) = Q t B ( s t , a t ) − Q t A ( s t , a t ) \Delta^{BA}_{t}(s_{t},a_{t})=Q^{B}_{t}(s_{t},a_{t})-Q^{A}_{t}(s_{t},a_{t}) , where c t c_{t} converges to 0 if Δ B A \Delta^{BA} converges to 0. The update of Δ t B A \Delta^{BA}_{t} at time t t is the sum of updates of Q A Q^{A} and Q B Q^{B} : Δ t + 1 B A ( s t , a t ) \displaystyle\Delta^{BA}_{t+1}(s_{t},a_{t}) = Δ t B A ( s t , a t ) + α t ( s t , a t ) ( y − Q t B ( s t , a t ) − ( y − Q t A ( s t , a t ) ) ) \displaystyle=\Delta^{BA}_{t}(s_{t},a_{t})+\alpha_{t}(s_{t},a_{t})\left(y-Q^{B}_{t}(s_{t},a_{t})-(y-Q^{A}_{t}(s_{t},a_{t}))\right) (21) = Δ t B A ( s t , a t ) + α t ( s t , a t ) ( Q t A ( s t , a t ) − Q t B ( s t , a t ) ) \displaystyle=\Delta^{BA}_{t}(s_{t},a_{t})+\alpha_{t}(s_{t},a_{t})\left(Q^{A}_{t}(s_{t},a_{t})-Q^{B}_{t}(s_{t},a_{t})\right) = ( 1 − α t ( s t , a t ) ) Δ t B A ( s t , a t ) . \displaystyle=(1-\alpha_{t}(s_{t},a_{t}))\Delta^{BA}_{t}(s_{t},a_{t}). Clearly Δ t B A \Delta^{BA}_{t} will converge to 0 0 , which then shows we have satisfied condition 3 of lemma 1, implying that Q A ( s t , a t ) Q^{A}(s_{t},a_{t}) converges to Q t ∗ ( s t , a t ) Q^{*}_{t}(s_{t},a_{t}) . Similarly, we get convergence of Q B ( s t , a t ) Q^{B}(s_{t},a_{t}) to the optimal vale function by choosing Δ t = Q t B − Q ∗ \Delta_{t}=Q^{B}_{t}-Q^{*} and repeating the same arguments, thus proving theorem 1.
## Appendix B 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: \displaystyle 𝔼 s ∼ π [ Q θ ( s , π new ( s ) ) ] = 𝔼 s ∼ π [ Q π ( s , π new ( s ) ) ] \displaystyle\mathbb{E}_{s\sim\pi}\left[Q_{\theta}(s,\pi_{\textnormal{new}}(s))\right]=\mathbb{E}_{s\sim\pi}\left[Q^{\pi}(s,\pi_{\textnormal{new}}(s))\right] (22) ∀ ϕ new ∈ [ ϕ , ϕ + β ( ϕ true − ϕ ) ] such that β > 0 . \displaystyle\forall\phi_{\textnormal{new}}\in[\phi,\phi+\beta(\phi_{\textnormal{true}}-\phi)]\text{ such that }\beta>0. Noting that ϕ true \phi_{\textnormal{true}} maximizes the rate of change of the true value Δ true π = Q π ( s , π true ( s ) ) − Q π ( s , π ϕ ( s ) ) \Delta^{\pi}_{\textnormal{true}}=Q^{\pi}(s,\pi_{\textnormal{true}}(s))-Q^{\pi}(s,\pi_{\phi}(s)) , Δ true π ≥ Δ approx π \Delta^{\pi}_{\textnormal{true}}\geq\Delta^{\pi}_{\textnormal{approx}} . By the given condition 22 the maximal rate of change of the approximate value must be at least as great Δ approx θ ≥ Δ true π \Delta^{\theta}_{\textnormal{approx}}\geq\Delta^{\pi}_{\textnormal{true}} . Given Q θ ( s , π ϕ ) = Q π ( s , π ϕ ) Q_{\theta}(s,\pi_{\phi})=Q^{\pi}(s,\pi_{\phi}) this implies Q θ ( s , π approx ( s ) ) ≥ Q π ( s , π true ( s ) ) ≥ Q π ( s , π approx ( s ) ) Q_{\theta}(s,\pi_{\textnormal{approx}}(s))\geq Q^{\pi}(s,\pi_{\textnormal{true}}(s))\geq Q^{\pi}(s,\pi_{\textnormal{approx}}(s)) , showing an overestimation of the value function.
## Appendix C DDPG Network and Hyper-parameter Comparison
DDPG Critic Architecture (state dim, 400) ReLU (action dim + 400, 300) ReLU (300, 1) DDPG Actor Architecture (state dim, 400) ReLU (400, 300) ReLU (300, 1) tanh
Our Critic Architecture (state dim + action dim, 400) ReLU (action dim + 400, 300) RelU (300, 1) Our Actor Architecture (state dim, 400) ReLU (400, 300) RelU (300, 1) tanh
## Appendix D 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 , ⋅ ) Q(s,\cdot) is set to 0 0 in the target y y : y = { r if terminal s ′ and t < max horizon r + γ Q θ ′ ( s ′ , π ϕ ′ ( s ′ ) ) else y=\begin{cases}r&\text{if terminal }s^{\prime}\text{ and }t<\text{max horizon}\\ r+\gamma Q_{\theta^{\prime}}(s^{\prime},\pi_{\phi^{\prime}}(s^{\prime}))&\text{else}\\ \end{cases}
For target policy smoothing (Section 5.3 ), the added noise is clipped to the range of possible actions, to avoid error introduced by using values of impossible actions: y \displaystyle y = r + γ Q θ ′ ( s ′ , clip ( π ϕ ′ ( s ′ ) + ϵ , min action , max action ) ) , \displaystyle=r+\gamma Q_{\theta^{\prime}}(s^{\prime},\clip(\pi_{\phi^{\prime}}(s^{\prime})+\epsilon,\text{min action},\text{max action})), ϵ ∼ clip ( 𝒩 ( 0 , σ ) , − c , c ) . \displaystyle\epsilon\sim\clip(\mathcal{N}(0,\sigma),-c,c).
## Appendix E Soft Actor-Critic Implementation Details
For our implementation of Soft Actor-Critic ( Haarnoja et al., 2018 ) 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.
## Appendix F Additional Learning Curves
## Instructions for reporting errors
We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:
Click the "Report Issue" ( ) button, located in the page header.
Tip: You can select the relevant text first, to include it in your report.
Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.
Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .