Addressing Function Approximation Error in Actor-Critic Methods

处理 Actor-Critic 方法中的函数逼近误差

Scott Fujimoto Affiliation:  McGill University, Montreal, Canada Correspondence to: scott.fujimoto@mail.mcgill.ca    Herke van Hoof Affiliation:  University of Amsterdam, Amsterdam, Netherlands    David Meger Affiliation:  McGill University, Montreal, Canada

Supplementary Material

补充材料

Scott Fujimoto Affiliation:  McGill University, Montreal, Canada Correspondence to: scott.fujimoto@mail.mcgill.ca    Herke van Hoof Affiliation:  University of Amsterdam, Amsterdam, Netherlands    David Meger Affiliation:  McGill University, Montreal, Canada

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.

在深度 Q 学习等基于价值的强化学习方法中，函数逼近误差会导致价值估计偏高，并得到次优策略。我们表明这一问题在 actor-critic 设定下依然存在，并提出新机制以分别削弱其对 actor 与 critic 的影响。算法建立在 Double Q-learning 之上：在一对评论家之间取较小值以限制高估。我们把目标网络与高估偏置联系起来，并建议延迟策略更新，以降低每次更新的误差并进一步提升表现。我们在 OpenAI gym 任务集上评测，在所有测试环境中均超过当时最优方法。

1 Introduction

1 引言

Keywords:

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.

关键词：

在离散动作空间的强化学习问题中，由函数逼近误差引起的价值高估已被充分研究。然而，连续控制域中 actor-critic 方法的类似问题基本上未被触及。本文表明：高估偏置与时序差分方法中的误差累积，在 actor-critic 设定下同样存在。我们所提方法针对这些问题，并大幅超过当时最优水平。

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.

高估偏置是 Q-learning 的固有性质：对带噪价值估计做最大化，会诱导持续的高估（Thrun & Schwartz 1993）。在函数逼近设定下，估计器本身不精确，这种噪声不可避免。时序差分学习（Sutton 1988）的性质会进一步放大不精确：价值函数的估计要用后续状态的估计来更新。这意味着每次更新若使用不精确估计，误差就会累积。由于存在高估偏置，累积误差可能把任意差的状态估成高价值，从而导致次优策略更新乃至发散。

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.

本文首先确立：在连续控制设定下，确定性策略梯度（Silver et al. 2014）同样具有这种高估性质。此外，我们发现离散动作设定中无处不在的解法 Double DQN（Van Hasselt et al. 2016）在 actor-critic 中无效。训练时，Double DQN 用单独的目标价值函数估计当前策略的价值，从而在不做最大化偏置的情况下评估动作。不幸的是，由于 actor-critic 中策略变化缓慢，当前与目标价值估计仍然过于相似，无法避免最大化偏置。对此可把更早的变体 Double Q-learning（Van Hasselt 2010）改造成 actor-critic 形式：使用一对独立训练的评论家。这样可以得到偏置更小的价值估计，但即便是无偏却高方差的估计，仍可能在状态空间局部区域造成未来高估，进而损害全局策略。为应对这一担忧，我们提出截断的 Double Q-learning 变体：利用「受高估偏置影响的价值估计可当作对真值估计的近似上界」这一想法。它偏向低估；低估在学习中不易被传播，因为策略会避开低价值估计的动作。

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.

鉴于噪声与高估偏置的联系，本文包含若干面向降方差的组件。首先，我们表明深度 Q 学习中常见的目标网络，对通过减少误差累积来降方差至关重要。其次，为处理价值与策略的耦合，我们提出延迟策略更新，直到价值估计收敛。最后，我们引入一种新的正则化策略：用类似 SARSA 的更新对相近动作估计做自举，以进一步降方差。

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.

我们把这些修改施加到当时连续控制最优的 actor-critic 方法——深度确定性策略梯度算法（DDPG）（Lillicrap et al. 2015）上，形成双延迟深度确定性策略梯度算法（TD3）：一种同时考虑策略更新与价值更新中函数逼近误差相互作用的 actor-critic 算法。我们在 OpenAI gym（Brockman et al. 2016）的七个连续控制域上评测，大幅超过当时最优水平。

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

鉴于近期对可复现性的关切（Henderson et al. 2017），我们在大量随机种子上用公平评测指标做实验，对每项贡献做消融，并开源代码与学习曲线（https://github.com/sfujim/TD3）。

2 Related Work

2 相关工作

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.

函数逼近误差及其对强化学习算法中偏置与方差的影响，已有先前工作研究（Pendrith et al. 1997；Mannor et al. 2007）。我们的工作聚焦于估计误差带来的两类结果，即高估偏置与高方差累积。

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.

已有多种方法用于削弱 Q-learning 中由函数逼近与策略优化引起的高估偏置。Double Q-learning 用两个独立估计器做无偏价值估计（Van Hasselt 2010；Van Hasselt et al. 2016）。其他方法直接降方差（Anschel et al. 2017）、减轻对早期高方差估计的过拟合（Fox et al. 2016），或通过校正项（Lee et al. 2013）。此外，价值估计的方差也曾被直接用于风险规避（Mannor & Tsitsiklis 2011）与探索（O’Donoghue et al. 2017），但未与高估偏置联系起来。

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.

时序差分学习中因误差累积引起的方差问题，大体上通过最小化每步误差大小，或混合离策略与蒙特卡洛回报来处理。我们的工作表明标准技术——目标网络——对降低每次更新误差的重要性，并发展了一种通过对价值估计取平均来降方差的正则化技术。同期，Nachum et al. 2018 表明平滑价值函数可用于训练随机策略，以降方差并提升表现。多步回报方法在累积估计偏置与由策略和环境引入的方差之间做权衡；它们通过重要性采样（Precup et al. 2001；Munos et al. 2016）、分布式方法（Mnih et al. 2016；Espeholt et al. 2018）与近似界（He et al. 2016）被证明有效。不过，这些方法并未直接解决误差累积，而是通过考虑更长视界绕过问题。另一种做法是减小折扣因子（Petrik & Scherrer 2009），以降低每个误差的贡献。

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

我们的方法建立在确定性策略梯度算法（DPG）（Silver et al. 2014）之上：这是一种用学到的价值估计来训练确定性策略的 actor-critic 方法。把 DPG 扩展到深度强化学习的 DDPG（Lillicrap et al. 2015），已表明能以较少迭代达到当时最优结果。与我们正交的近期 DDPG 改进包括分布式方法（Popov et al. 2017），以及多步回报与优先经验回放（Schaul et al. 2016；Horgan et al. 2018），还有分布方法（Bellemare et al. 2017；Barth-Maron et al. 2018）。

3 Background

3 背景

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\in\mathcal{S}$, the agent selects actions $a\in\mathcal{A}$ with respect to its policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$, receiving a reward $r$ and the new state of the environment $s^{\prime}$. The return is defined as the discounted sum of rewards $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.

强化学习考虑智能体与环境交互、以学习最大化奖励行为的范式。在每个离散时间步 $t$，给定状态 $s\in\mathcal{S}$，智能体按策略 $\pi:\mathcal{S}\rightarrow\mathcal{A}$ 选择动作 $a\in\mathcal{A}$，收到奖励 $r$ 与环境新状态 $s^{\prime}$。回报定义为折扣奖励和 $R_{t}=\sum_{i=t}^{T}\gamma^{i-t}r(s_{i},a_{i})$，其中 $\gamma$ 是决定短期奖励优先级的折扣因子。

In reinforcement learning, the objective is to find the optimal policy $\pi_{\phi}$, with parameters $\phi$, which maximizes the expected return $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 $\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):

在强化学习中，目标是找到参数为 $\phi$ 的最优策略 $\pi_{\phi}$，以最大化期望回报 $J(\phi)=\mathbb{E}_{s_{i}\sim p_{\pi},a_{i}\sim\pi}\left[R_{0}\right]$。对连续控制，参数化策略 $\pi_{\phi}$ 可通过取期望回报的梯度 $\nabla_{\phi}J(\phi)$ 来更新。在 actor-critic 方法中，称为 actor 的策略可通过确定性策略梯度算法（Silver et al. 2014）更新：

$$\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]. \tag{1}$$

$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$ in state $s$ and following $\pi$ after, is known as the critic or the value function.

$Q^{\pi}(s,a)=\mathbb{E}_{s_{i}\sim p_{\pi},a_{i}\sim\pi}\left[R_{t}|s,a\right]$，即在状态 $s$ 执行动作 $a$ 并随后遵循 $\pi$ 的期望回报，称为评论家或价值函数。

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)$ and the value of the subsequent state-action pair $(s^{\prime},a^{\prime})$:

在 Q-learning 中，价值函数可用时序差分学习（Sutton 1988；Watkins 1989）学习，这是一种基于贝尔曼方程（Bellman 1957）的更新规则。贝尔曼方程给出状态—动作对 $(s,a)$ 的价值与后续状态—动作对 $(s^{\prime},a^{\prime})$ 的价值之间的基本关系：

$$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}). \tag{2}$$

For a large state space, the value can be estimated with a differentiable function approximator $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_{\theta^{\prime}}(s,a)$ to maintain a fixed objective $y$ over multiple updates:

对较大状态空间，可用可微函数逼近器 $Q_{\theta}(s,a)$（参数 $\theta$）估计价值。在深度 Q 学习（Mnih et al. 2015）中，网络用时序差分学习更新，并借助第二个冻结的目标网络 $Q_{\theta^{\prime}}(s,a)$，在多次更新中保持固定目标 $y$：

$$y=r+\gamma Q_{\theta^{\prime}}(s^{\prime},a^{\prime}),\quad a^{\prime}\sim\pi_{\phi^{\prime}}(s^{\prime}), \tag{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 $\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).

其中动作由目标 actor 网络 $\pi_{\phi^{\prime}}$ 选择。目标网络的权重要么周期性精确匹配当前网络，要么每步按比例 $\tau$ 更新：$\theta^{\prime}\leftarrow\tau\theta+(1-\tau)\theta^{\prime}$。该更新可以离策略进行：从经验回放缓冲 （Lin 1992）中随机采样小批量转移。

4 Overestimation Bias

4 高估偏置

In Q-learning with discrete actions, the value estimate is updated with a greedy target $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, $\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.

在离散动作的 Q-learning 中，价值估计用贪心目标 $y=r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})$ 更新；然而若目标易受误差 $\epsilon$ 影响，则对价值及其误差取最大通常会大于真最大，$\mathbb{E}_{\epsilon}[\max_{a^{\prime}}(Q(s^{\prime},a^{\prime})+\epsilon)]\geq\max_{a^{\prime}}Q(s^{\prime},a^{\prime})$（Thrun & Schwartz 1993）。于是，即便初始为零均值误差，价值更新也会造成持续的高估偏置，再经贝尔曼方程传播。这很成问题，因为函数逼近引入的误差不可避免。

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.

在离散动作设定中，高估偏置是解析最大化的明显产物；而在策略经梯度下降更新的 actor-critic 设定中，高估偏置是否存在及其影响则不那么清楚。我们先在第 4.1 节证明：在一些基本假设下，确定性策略梯度中的价值估计会高估；再在第 4.2 节提出 actor-critic 设定下的截断 Double Q-learning 变体，以降低高估偏置。

4.1 Overestimation Bias in Actor-Critic

4.1 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 $\phi_{\textnormal{approx}}$ define the parameters from the actor update induced by the maximization of the approximate critic $Q_{\theta}(s,a)$ and $\phi_{\textnormal{true}}$ the parameters from the hypothetical actor update with respect to the true underlying value function $Q^{\pi}(s,a)$ (which is not known during learning):

在 actor-critic 方法中，策略相对近似评论家的价值估计做更新。本节假设策略用确定性策略梯度更新，并表明该更新会诱导价值估计高估。给定当前策略参数 $\phi$，令 $\phi_{\textnormal{approx}}$ 表示由最大化近似评论家 $Q_{\theta}(s,a)$ 诱导的 actor 更新参数，$\phi_{\textnormal{true}}$ 表示相对真实底层价值函数 $Q^{\pi}(s,a)$（学习中未知）的假想 actor 更新参数：

$$\displaystyle\phi_{\textnormal{approx}} \\ \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] \\ \displaystyle\phi_{\textnormal{true}} \\ \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}$ and $Z_{2}$ are chosen to normalize the gradient, i.e., such that $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 $\pi_{\textnormal{approx}}$ and $\pi_{\textnormal{true}}$ as the policy with parameters $\phi_{\textnormal{approx}}$ and $\phi_{\textnormal{true}}$ respectively.

其中我们假设 $Z_{1}$ 与 $Z_{2}$ 用于归一化梯度，即使得 $Z^{-1}||\mathbb{E}[\cdot]||=1$。若不做梯度归一化，在稍严格的条件下高估偏置仍保证发生。我们在补充材料中进一步考察该情形。分别记带参数 $\phi_{\textnormal{approx}}$ 与 $\phi_{\textnormal{true}}$ 的策略为 $\pi_{\textnormal{approx}}$ 与 $\pi_{\textnormal{true}}$。

As the gradient direction is a local maximizer, there exists $\epsilon_{1}$ sufficiently small such that if $\alpha\leq\epsilon_{1}$ then the approximate value of $\pi_{\textnormal{approx}}$ will be bounded below by the approximate value of $\pi_{\textnormal{true}}$:

由于梯度方向是局部最大化方向，存在充分小的 $\epsilon_{1}$，使得若 $\alpha\leq\epsilon_{1}$，则 $\pi_{\textnormal{approx}}$ 的近似价值下界不低于 $\pi_{\textnormal{true}}$ 的近似价值：

$$\mathbb{E}\left[Q_{\theta}(s,\pi_{\textnormal{approx}}(s))\right]\geq\mathbb{E}\left[Q_{\theta}(s,\pi_{\textnormal{true}}(s))\right]. \tag{5}$$

Conversely, there exists $\epsilon_{2}$ sufficiently small such that if $\alpha\leq\epsilon_{2}$ then the true value of $\pi_{\textnormal{approx}}$ will be bounded above by the true value of $\pi_{\textnormal{true}}$:

反之，存在充分小的 $\epsilon_{2}$，使得若 $\alpha\leq\epsilon_{2}$，则 $\pi_{\textnormal{approx}}$ 的真实价值上界不高于 $\pi_{\textnormal{true}}$ 的真实价值：

$$\mathbb{E}\left[Q^{\pi}(s,\pi_{\textnormal{true}}(s))\right]\geq\mathbb{E}\left[Q^{\pi}(s,\pi_{\textnormal{approx}}(s))\right]. \tag{6}$$

If in expectation the value estimate is at least as large as the true value with respect to $\phi_{true}$, $\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 $\alpha<\min(\epsilon_{1},\epsilon_{2})$, then the value estimate will be overestimated:

若期望上，价值估计相对 $\phi_{true}$ 至少不小于真实价值，$\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]$，则式 (5) 与 (6) 意味着：若 $\alpha<\min(\epsilon_{1},\epsilon_{2})$，价值估计将被高估：

$$\mathbb{E}\left[Q_{\theta}(s,\pi_{\textnormal{approx}}(s))\right]\geq\mathbb{E}\left[Q^{\pi}(s,\pi_{\textnormal{approx}}(s))\right]. \tag{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.

尽管每次更新的高估可能很小，误差的存在仍引出两点担忧。第一，若不加约束，高估可能在多次更新后发展成更显著的偏置。第二，不准确的价值估计可能导致糟糕的策略更新。这尤其成问题，因为会形成反馈回路：次优动作可能被次优评论家打高分，从而在下一次策略更新中强化该次优动作。

(a) Hopper-v1

（a）Hopper-v1

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.

这种理论上的高估在当时最优方法中是否真的出现？ 我们通过绘制 DDPG（Lillicrap et al. 2015）在 OpenAI gym 环境 Hopper-v1 与 Walker2d-v1（Brockman et al. 2016）上学习过程中的价值估计来回答。图 1 中，我们画出 10000 个状态上的平均价值估计，并与真实价值的估计对比。真实价值用从回放缓冲采样的状态出发、跟随当前策略跑 1000 条回合的平均折扣回报来估计。学习过程中出现了非常清晰的高估偏置；这与下一节描述的新方法——截断 Double Q-learning——形成对比，后者大幅降低了评论家的高估。

4.2 Clipped Double Q-Learning for Actor-Critic

4.2 面向 Actor-Critic 的截断 Double Q-Learning

(a) Hopper-v1

（a）Hopper-v1

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.

尽管已有多种降低高估偏置的方法，我们发现它们在 actor-critic 设定下无效。本节引入一种新颖的截断 Double Q-learning 变体（Van Hasselt 2010），可替换任意 actor-critic 方法中的评论家。

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:

在 Double Q-learning 中，贪心更新与价值函数被拆开：维护两个独立的价值估计，各自用来更新对方。若价值估计相互独立，便可用它们对由对方价值估计选出的动作做无偏估计。在 Double DQN（Van Hasselt et al. 2016）中，作者提议把目标网络当作其中一个价值估计，并通过贪心最大化当前价值网络（而非目标网络）得到策略。在 actor-critic 设定中，类似的更新在学习目标里用当前策略而非目标策略：

$$y=r+\gamma Q_{\theta^{\prime}}(s^{\prime},\pi_{\phi}(s^{\prime})). \tag{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 ($\pi_{\phi_{1}}$, $\pi_{\phi_{2}}$) and critics ($Q_{\theta_{1}}$, $Q_{\theta_{2}}$), where $\pi_{\phi_{1}}$ is optimized with respect to $Q_{\theta_{1}}$ and $\pi_{\phi_{2}}$ with respect to $Q_{\theta_{2}}$:

但实践中我们发现：由于 actor-critic 中策略变化缓慢，当前网络与目标网络过于相似，难以做出独立估计，几乎没有改进。于是可采用原始 Double Q-learning 形式，使用一对 actor（$\pi_{\phi_{1}}$，$\pi_{\phi_{2}}$）与评论家（$Q_{\theta_{1}}$，$Q_{\theta_{2}}$），其中 $\pi_{\phi_{1}}$ 相对 $Q_{\theta_{1}}$ 优化、$\pi_{\phi_{2}}$ 相对 $Q_{\theta_{2}}$ 优化：

$$\displaystyle y_{1} \\ \displaystyle=r+\gamma Q_{\theta^{\prime}_{2}}(s^{\prime},\pi_{\phi_{1}}(s^{\prime})) \\ \displaystyle y_{2} \\ \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.

我们在图 2 中测量高估偏置，表明 actor-critic 版 Double DQN 遭受与 DDPG 类似的高估（如图 1 所示）。虽然 Double Q-learning 更有效，但并未完全消除高估。我们在第 6.1 节进一步用实验表明，这种降低仍不够。

As $\pi_{\phi_{1}}$ optimizes with respect to $Q_{\theta_{1}}$, using an independent estimate in the target update of $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$ we will have $Q_{\theta_{2}}(s,\pi_{\phi_{1}}(s))>Q_{\theta_{1}}(s,\pi_{\phi_{1}}(s))$. This is problematic because $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_{\theta_{2}}$ by the biased estimate $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:

由于 $\pi_{\phi_{1}}$ 相对 $Q_{\theta_{1}}$ 优化，在 $Q_{\theta_{1}}$ 的目标更新中使用独立估计可避免策略更新引入的偏置。然而评论家并非完全独立：学习目标中用了对方评论家，且共享同一回放缓冲。因此对某些状态 $s$ 会有 $Q_{\theta_{2}}(s,\pi_{\phi_{1}}(s))>Q_{\theta_{1}}(s,\pi_{\phi_{1}}(s))$。这成问题，因为 $Q_{\theta_{1}}(s,\pi_{\phi_{1}}(s))$ 通常会高估真值，而在状态空间某些区域高估还会被进一步放大。为解决该问题，我们提议简单地用偏置更大的估计 $Q_{\theta_{1}}$ 给偏置更小的估计 $Q_{\theta_{2}}$ 加上界。结果是取两个估计的最小值，得到我们截断 Double Q-learning 算法的目标更新：

$$y_{1}=r+\gamma\min_{i=1,2}Q_{\theta^{\prime}_{i}}(s^{\prime},\pi_{\phi_{1}}(s^{\prime})). \tag{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.

有了截断 Double Q-learning，价值目标不会比使用标准 Q-learning 目标引入更多额外高估。尽管该更新规则可能诱导低估偏置，但这远优于高估偏置：与高估动作不同，低估动作的价值不会通过策略更新被显式传播。

In implementation, computational costs can be reduced by using a single actor optimized with respect to $Q_{\theta_{1}}$. We then use the same target $y_{2}=y_{1}$ for $Q_{\theta_{2}}$. If $Q_{\theta_{2}}>Q_{\theta_{1}}$ then the update is identical to the standard update and induces no additional bias. If $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.

实现上，可用相对 $Q_{\theta_{1}}$ 优化的单个 actor 来降低计算成本。然后对 $Q_{\theta_{2}}$ 使用同一目标 $y_{2}=y_{1}$。若 $Q_{\theta_{2}}>Q_{\theta_{1}}$，则更新与标准更新相同，不引入额外偏置。若 $Q_{\theta_{2}}<Q_{\theta_{1}}$，则提示发生了高估，价值会类似 Double Q-learning 被压低。有限 MDP 设定下的收敛证明由此直觉出发。我们在补充材料中给出形式细节与论证。

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.

次要好处是：若把函数逼近误差当作随机变量，可以看到最小化算子应对估计误差方差更低的状态赋予更高价值，因为一组随机变量的期望最小值会随方差增大而减小。该效应意味着式 (10) 中的最小化会偏好低方差价值估计的状态，从而带来更安全的策略更新与更稳定的学习目标。

5 Addressing Variance

5 处理方差

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.

第 4 节处理方差对高估偏置的贡献；我们还主张方差本身应被直接处理。除影响高估偏置外，高方差估计还给策略更新提供嘈杂梯度。已知这会降低学习速度（Sutton & Barto 1998），并在实践中损害表现。本节强调最小化每次更新误差的重要性，建立目标网络与估计误差的联系，并提出对 actor-critic 学习流程的修改以降低方差。

5.1 Accumulating Error

5.1 误差累积

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 $\delta(s,a)$:

由于时序差分更新用后续状态的估计来构建价值函数估计，误差会累积。单次更新出现小误差是合理的，但这些估计误差可能累积，造成大幅高估偏置与次优策略更新。在函数逼近设定下这一问题更严重：贝尔曼方程从不完全满足，每次更新都会留下一定残差 TD 误差 $\delta(s,a)$：

$$Q_{\theta}(s,a)=r+\gamma\mathbb{E}[Q_{\theta}(s^{\prime},a^{\prime})]-\delta(s,a). \tag{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:

进而可以证明：价值估计近似的并非期望回报本身，而是期望回报减去未来 TD 误差的期望折扣和：

$$\displaystyle Q_{\theta}(s_{t},a_{t})=r_{t}+\gamma\mathbb{E}[Q_{\theta}(s_{t+1},a_{t+1})]-\delta_{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} \\ \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]. \tag{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.

若价值估计是未来奖励与估计误差的函数，则估计的方差将与未来奖励及估计误差的方差成比例。给定较大的折扣因子 $\gamma$，若每次更新的误差不受控，方差会随更新迅速增长。此外，每次梯度更新只相对一小批样本降低误差，对小批之外价值估计的误差大小没有任何保证。

5.2 Target Networks and Delayed Policy Updates

5.2 目标网络与延迟策略更新

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

为给出直观，我们在图 3 中考察有无目标网络时评论家与 actor 的学习行为：以类似图 1 的方式，在 Hopper-v1 环境中绘制价值。在 (a) 中比较固定策略下的行为；在 (b) 中考察策略持续学习、并用当前价值估计训练时的价值估计。目标网络使用由 $\tau$ 参数化的慢速更新率。

(a) Fixed Policy

（a）固定策略

While updating the value estimate without target networks ($\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.

虽不使用目标网络（$\tau=1$）更新价值估计会增加波动，但在固定策略下，所有更新率都呈现类似的收敛行为。然而，当策略用当前价值估计训练时，使用快速更新的目标网络会导致高度发散的行为。

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.

Actor-critic 方法何时学不会？ 这些结果提示：没有目标网络时出现的发散，来自用高方差价值估计做策略更新。图 3 以及第 4 节提示：失败可能源于 actor 与 critic 更新之间的相互作用。当策略较差时，价值估计会通过高估发散；若价值估计本身不准确，策略也会变差。

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 $\theta^{\prime}\leftarrow\tau\theta+(1-\tau)\theta^{\prime}$.

若目标网络可用于在多次更新中降低误差，而在高误差状态上做策略更新会导致发散，那么策略网络应以低于价值网络的频率更新，以便在引入策略更新之前先最小化误差。我们提议延迟策略更新，直到价值误差尽可能小。具体修改是：仅在对评论家做固定次数 $d$ 次更新之后，才更新策略与目标网络。为确保 TD 误差保持较小，我们缓慢更新目标网络 $\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.

通过充分延迟策略更新，我们降低相对未变评论家重复更新的可能性。较少发生的策略更新将使用方差更低的价值估计，原则上应带来更高质量的策略更新。这形成双时间尺度算法，正如线性设定收敛常要求的那样（Konda & Tsitsiklis 2003）。该策略的有效性由第 6.1 节的实证结果体现：在使用更少策略更新的同时提升了表现。

5.3 Target Policy Smoothing Regularization

5.3 目标策略平滑正则化

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

确定性策略的一个担忧是：它们可能过拟合价值估计中的窄峰。更新评论家时，使用确定性策略的学习目标极易受函数逼近误差引起的不精确影响，从而增大目标方差。可通过正则化降低这种诱导方差。我们为深度价值学习引入一种正则化策略——目标策略平滑，它模仿 SARSA（Sutton & Barto 1998）的学习更新。我们的方法强制「相近动作应有相近价值」这一观念。虽然函数逼近会隐式做到这一点，但可通过修改训练流程显式强制相近动作之间的关系。我们提议拟合目标动作周围一小片区域的价值

$$y=r+\mathbb{E}_{\epsilon}\left[Q_{\theta^{\prime}}(s^{\prime},\pi_{\phi^{\prime}}(s^{\prime})+\epsilon)\right], \tag{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:

这样做的好处是：通过对相近状态—动作价值估计做自举来平滑价值估计。实践中，可通过向目标策略加入少量随机噪声并在小批量上取平均，来近似动作上的期望。于是我们修改后的目标更新为：

$$\displaystyle y \\ \displaystyle=r+\gamma Q_{\theta^{\prime}}(s^{\prime},\pi_{\phi^{\prime}}(s^{\prime})+\epsilon), \\ \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$.

其中加入的噪声被裁剪，以使目标靠近原动作。结果是一种让人联想到 Expected SARSA（Van Seijen et al. 2009）的算法：价值估计改为离策略学习，加到目标策略上的噪声独立于探索策略选取。所学价值估计相对由参数 $\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_{\theta}$, rather than $Q_{\theta^{\prime}}$.

直观上，已知由 SARSA 价值估计导出的策略往往更安全，因为它们对能抵抗扰动的动作赋予更高价值。因此，这类更新还可在有失败情形的随机域中带来改进。Nachum et al. 2018 同期引入了类似想法，不过是对 $Q_{\theta}$ 而非 $Q_{\theta^{\prime}}$ 做平滑。

6 Experiments

6 实验

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:

我们提出双延迟深度确定性策略梯度算法（TD3）：它建立在深度确定性策略梯度算法（DDPG）（Lillicrap et al. 2015）之上，并应用第 4.2、5.2 与 5.3 节所述修改，在考虑函数逼近误差的前提下提升稳定性与表现。TD3 维护一对评论家与单个 actor。每一步，我们把这对评论家朝目标策略所选动作的最小目标价值更新：

$$\displaystyle y \\ \displaystyle=r+\gamma\min_{i=1,2}Q_{\theta^{\prime}_{i}}(s^{\prime},\pi_{\phi^{\prime}}(s^{\prime})+\epsilon), \\ \displaystyle\epsilon\sim\clip(\mathcal{N}(0,\sigma),-c,c).$$

Every $d$ iterations, the policy is updated with respect to $Q_{\theta_{1}}$ following the deterministic policy gradient algorithm (Silver et al. 2014). TD3 is summarized in Algorithm 1.

每 $d$ 次迭代，策略相对 $Q_{\theta_{1}}$ 按确定性策略梯度算法（Silver et al. 2014）更新。TD3 总结于算法 1。

Initialize critic networks $Q_{\theta_{1}}$, $Q_{\theta_{2}}$, and actor network $\pi_{\phi}$ with random parameters $\theta_{1}$, $\theta_{2}$, $\phi$
Initialize target networks $\theta^{\prime}_{1}\leftarrow\theta_{1}$, $\theta^{\prime}_{2}\leftarrow\theta_{2}$, $\phi^{\prime}\leftarrow\phi$
Initialize replay buffer $\mathcal{B}$
for $t=1$ to $T$ do
Select action with exploration noise $a\sim\pi_{\phi}(s)+\epsilon$,
$\epsilon\sim\mathcal{N}(0,\sigma)$ and observe reward $r$ and new state $s^{\prime}$
Store transition tuple $(s,a,r,s^{\prime})$ in $\mathcal{B}$

Sample mini-batch of $N$ transitions $(s,a,r,s^{\prime})$ from $\mathcal{B}$
$\tilde{a}\leftarrow\pi_{\phi^{\prime}}(s^{\prime})+\epsilon,\quad\epsilon\sim\clip(\mathcal{N}(0,\tilde{\sigma}),-c,c)$
$y\leftarrow r+\gamma\min_{i=1,2}Q_{\theta^{\prime}_{i}}(s^{\prime},\tilde{a})$
Update critics $\theta_{i}\leftarrow\argmin_{\theta_{i}}N^{-1}\sum(y-Q_{\theta_{i}}(s,a))^{2}$
if $t$ mod $d$ then
Update $\phi$ by the deterministic policy gradient:
$\nabla_{\phi}J(\phi)=N^{-1}\sum\nabla_{a}Q_{\theta_{1}}(s,a)|_{a=\pi_{\phi}(s)}\nabla_{\phi}\pi_{\phi}(s)$
Update target networks:
$\theta^{\prime}_{i}\leftarrow\tau\theta_{i}+(1-\tau)\theta^{\prime}_{i}$
$\phi^{\prime}\leftarrow\tau\phi+(1-\tau)\phi^{\prime}$
end if
end for

Algorithm 1 TD3

用随机参数 $\theta_{1}$、$\theta_{2}$、$\phi$ 初始化评论家网络 $Q_{\theta_{1}}$、$Q_{\theta_{2}}$ 与 actor 网络 $\pi_{\phi}$
初始化目标网络 $\theta^{\prime}_{1}\leftarrow\theta_{1}$，$\theta^{\prime}_{2}\leftarrow\theta_{2}$，$\phi^{\prime}\leftarrow\phi$
初始化回放缓冲 $\mathcal{B}$
for $t=1$ to $T$ do
选择带探索噪声的动作 $a\sim\pi_{\phi}(s)+\epsilon$，
$\epsilon\sim\mathcal{N}(0,\sigma)$，并观察奖励 $r$ 与新状态 $s^{\prime}$
将转移元组 $(s,a,r,s^{\prime})$ 存入 $\mathcal{B}$

从 $\mathcal{B}$ 采样大小为 $N$ 的小批量转移 $(s,a,r,s^{\prime})$
$\tilde{a}\leftarrow\pi_{\phi^{\prime}}(s^{\prime})+\epsilon,\quad\epsilon\sim\clip(\mathcal{N}(0,\tilde{\sigma}),-c,c)$
$y\leftarrow r+\gamma\min_{i=1,2}Q_{\theta^{\prime}_{i}}(s^{\prime},\tilde{a})$
更新评论家 $\theta_{i}\leftarrow\argmin_{\theta_{i}}N^{-1}\sum(y-Q_{\theta_{i}}(s,a))^{2}$
if $t$ mod $d$ then
按确定性策略梯度更新 $\phi$：
$\nabla_{\phi}J(\phi)=N^{-1}\sum\nabla_{a}Q_{\theta_{1}}(s,a)|_{a=\pi_{\phi}(s)}\nabla_{\phi}\pi_{\phi}(s)$
更新目标网络：
$\theta^{\prime}_{i}\leftarrow\tau\theta_{i}+(1-\tau)\theta^{\prime}_{i}$
$\phi^{\prime}\leftarrow\tau\phi+(1-\tau)\phi^{\prime}$
end if
end for

算法 1 TD3

(a)

（a）

6.1 Evaluation

6.1 评测

(a) HalfCheetah-v1

（a）HalfCheetah-v1

Environment	TD3	DDPG	Our DDPG	PPO	TRPO	ACKTR	SAC
HalfCheetah	9636.95 $\pm$ 859.065	3305.60	8577.29	1795.43	-15.57	1450.46	2347.19
Hopper	3564.07 $\pm$ 114.74	2020.46	1860.02	2164.70	2471.30	2428.39	2996.66
Walker2d	4682.82 $\pm$ 539.64	1843.85	3098.11	3317.69	2321.47	1216.70	1283.67
Ant	4372.44 $\pm$ 1000.33	1005.30	888.77	1083.20	-75.85	1821.94	655.35
Reacher	-3.60 $\pm$ 0.56	-6.51	-4.01	-6.18	-111.43	-4.26	-4.44
InvPendulum	1000.00 $\pm$ 0.00	1000.00	1000.00	1000.00	985.40	1000.00	1000.00
InvDoublePendulum	9337.47 $\pm$ 14.96	9355.52	8369.95	8977.94	205.85	9081.92	8487.15

Table 1: Max Average Return over 10 trials of 1 million time steps. Maximum value for each task is bolded. $\pm$ corresponds to a single standard deviation over trials.

环境	TD3	DDPG	Our DDPG	PPO	TRPO	ACKTR	SAC
HalfCheetah	9636.95 $\pm$ 859.065	3305.60	8577.29	1795.43	-15.57	1450.46	2347.19
Hopper	3564.07 $\pm$ 114.74	2020.46	1860.02	2164.70	2471.30	2428.39	2996.66
Walker2d	4682.82 $\pm$ 539.64	1843.85	3098.11	3317.69	2321.47	1216.70	1283.67
Ant	4372.44 $\pm$ 1000.33	1005.30	888.77	1083.20	-75.85	1821.94	655.35
Reacher	-3.60 $\pm$ 0.56	-6.51	-4.01	-6.18	-111.43	-4.26	-4.44
InvPendulum	1000.00 $\pm$ 0.00	1000.00	1000.00	1000.00	985.40	1000.00	1000.00
InvDoublePendulum	9337.47 $\pm$ 14.96	9355.52	8369.95	8977.94	205.85	9081.92	8487.15

表 1：在 10 次试验、各 100 万时间步上的最大平均回报。每个任务的最大值加粗。$\pm$ 对应跨试验的一个标准差。

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.

为评测算法，我们在经 OpenAI Gym（Brockman et al. 2016）接口的 MuJoCo 连续控制任务集（Todorov et al. 2012）上测量表现（图 4）。为便于可复现比较，我们使用 Brockman et al. 2016 的原始任务集，不对环境或奖励做任何修改。

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}$. 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.

对我们实现的 DDPG（Lillicrap et al. 2015），actor 与 critic 均使用两层前馈网络，隐层节点数分别为 400 与 300，层间为 ReLU，actor 输出后接最终 tanh 单元。与原始 DDPG 不同，评论家在第一层同时接收状态与动作作为输入。两个网络的参数均用 Adam（Kingma & Ba 2014）更新，学习率为 $10^{-3}$。每一步后，用从包含智能体全部历史的回放缓冲中均匀采样的 100 条转移组成的小批量训练网络。

The target policy smoothing is implemented by adding $\epsilon\sim\mathcal{N}(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 $\tau=0.005$.

目标策略平滑的实现是：向目标 actor 网络所选动作加入 $\epsilon\sim\mathcal{N}(0,0.2)$，并裁剪到 $(-0.5,0.5)$；延迟策略更新则是仅每 $d$ 次迭代更新 actor 与目标评论家网络，取 $d=2$。更大的 $d$ 对累积误差更有利，但为公平比较，评论家每时间步只训练一次，而 actor 训练过少会削弱学习。两个目标网络均以 $\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 $\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.

为去除对策略初始参数的依赖，对长度较稳定的环境（HalfCheetah-v1 与 Ant-v1）前 10000 步使用纯探索策略，其余环境前 1000 步如此。之后使用离策略探索策略，向每个动作加入高斯噪声 $\mathcal{N}(0,0.1)$。与原始 DDPG 实现不同，我们用无相关噪声做探索，因为发现从 Ornstein-Uhlenbeck（Uhlenbeck & Ornstein 1930）过程抽取的噪声并无性能收益。

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.

每个任务跑 100 万时间步，每 5000 步评测一次；每次评测报告无探索噪声下 10 个回合的平均奖励。结果在 Gym 模拟器与网络初始化的 10 个随机种子上报告。

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

我们与 DDPG（Lillicrap et al. 2015）以及当时最优的策略梯度算法对比：PPO（Schulman et al. 2017）、ACKTR（Wu et al. 2017）与 TRPO（Schulman et al. 2015），实现来自 OpenAI 的 baselines 仓库（Dhariwal et al. 2017）；以及 SAC（Haarnoja et al. 2018），实现来自作者 GitHub[^1]。此外，我们还与我们重调版 DDPG 对比：它包含对 DDPG 的全部架构与超参数修改，但不含我们所提调整。重调版与 baselines DDPG 的完整对比见补充材料。

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.

结果见表 1，学习曲线见图 5。TD3 在所有任务上，最终表现与学习速度均达到或超过其余全部算法。

6.2 Ablation Studies

6.2 消融实验

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.

我们做消融以理解各组件贡献：截断 Double Q-learning（第 4.2 节）、延迟策略更新（第 5.2 节）与目标策略平滑（第 5.3 节）。结果见表 2：比较从 TD3 中去掉各组件，以及我们对架构与超参数的修改。额外学习曲线见补充材料。

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.

各组件的重要性因任务而异。多数情况下只加单一组件提升不明显，而组合起来表现高得多。完整算法在多数任务上超过其他每一种组合。尽管 actor 只训练一半次数的迭代，加入延迟策略更新通常仍能提升表现，同时减少训练时间。

Method	HCheetah	Hopper	Walker2d	Ant
TD3	9532.99	3304.75	4565.24	4185.06
DDPG	3162.50	1731.94	1520.90	816.35
AHE	8401.02	1061.77	2362.13	564.07
AHE + DP	7588.64	1465.11	2459.53	896.13
AHE + TPS	9023.40	907.56	2961.36	872.17
AHE + CDQ	6470.20	1134.14	3979.21	3818.71
TD3 - DP	9590.65	2407.42	4695.50	3754.26
TD3 - TPS	8987.69	2392.59	4033.67	4155.24
TD3 - CDQ	9792.80	1837.32	2579.39	849.75
DQ-AC	9433.87	1773.71	3100.45	2445.97
DDQN-AC	10306.90	2155.75	3116.81	1092.18

Table 2: Average return over the last 10 evaluations over 10 trials of 1 million time steps, comparing ablation over delayed policy updates (DP), target policy smoothing (TPS), Clipped Double Q-learning (CDQ) and our architecture, hyper-parameters and exploration (AHE). Maximum value for each task is bolded.

方法	HCheetah	Hopper	Walker2d	Ant
TD3	9532.99	3304.75	4565.24	4185.06
DDPG	3162.50	1731.94	1520.90	816.35
AHE	8401.02	1061.77	2362.13	564.07
AHE + DP	7588.64	1465.11	2459.53	896.13
AHE + TPS	9023.40	907.56	2961.36	872.17
AHE + CDQ	6470.20	1134.14	3979.21	3818.71
TD3 - DP	9590.65	2407.42	4695.50	3754.26
TD3 - TPS	8987.69	2392.59	4033.67	4155.24
TD3 - CDQ	9792.80	1837.32	2579.39	849.75
DQ-AC	9433.87	1773.71	3100.45	2445.97
DDQN-AC	10306.90	2155.75	3116.81	1092.18

表 2：在 10 次试验、各 100 万时间步上最后 10 次评测的平均回报，对比延迟策略更新（DP）、目标策略平滑（TPS）、截断 Double Q-learning（CDQ）以及我们的架构、超参数与探索（AHE）的消融。每个任务的最大值加粗。

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.

我们还在表 2 中比较 actor-critic 版 Double Q-learning（Van Hasselt 2010）与 Double DQN（Van Hasselt et al. 2016）的有效性，分别记为 DQ-AC 与 DDQN-AC。为公平比较，这些方法也受益于延迟策略更新、目标策略平滑，并使用我们的架构与超参数。第 4 节已表明二者降低高估偏置不如截断 Double Q-learning。经验上也反映这一点：二者相对 TD3 - CDQ 的提升都不显著，Ant-v1 例外——该环境似乎从任何高估削减中都大幅受益。由于把截断 Double Q-learning 纳入完整方法超过此前两种方法，这表明压制来自无偏估计器的高估，是提升表现的有效措施。

7 Conclusion

7 结论

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.

高估已被认定是基于价值方法的关键问题。本文确立：高估偏置在 actor-critic 方法中同样成问题。我们发现离散动作深度 Q 学习中常用的降低高估偏置解法在 actor-critic 设定下无效，并发展出一种限制可能高估的新颖 Double Q-learning 变体。结果表明缓解高估可大幅提升现代算法的表现。

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.

鉴于噪声与高估的联系，我们考察时序差分学习中的误差累积。我们的工作调查深度强化学习中标准技术——目标网络——的重要性，并考察它们在限制不精确函数逼近与随机优化误差中的作用。最后，我们引入一种类 SARSA 的正则化技术，修改时序差分目标以对相近状态—动作对做自举。

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.

综合这些改进，我们提出双延迟深度确定性策略梯度算法（TD3），在连续控制设定的若干挑战任务上大幅提升 DDPG 的学习速度与表现。我们的算法超过众多当时最优算法。由于修改实现简单，它们可轻易加入任何其他 actor-critic 算法。

References

参考文献

Anschel et al. (2017) Anschel, O., Baram, N., and Shimkin, N. Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning. In International Conference on Machine Learning , pp. 176–185, 2017.

Barth-Maron et al. (2018) Barth-Maron, G., Hoffman, M. W., Budden, D., Dabney, W., Horgan, D., TB, D., Muldal, A., Heess, N., and Lillicrap, T. Distributional policy gradients. International Conference on Learning Representations , 2018.

Bellemare et al. (2017) Bellemare, M. G., Dabney, W., and Munos, R. A distributional perspective on reinforcement learning. In International Conference on Machine Learning , pp. 449–458, 2017.

Bellman (1957) Bellman, R. Dynamic Programming . Princeton University Press, 1957.

Bertsekas (1995) Bertsekas, D. P. Dynamic programming and optimal control , volume 1. Athena scientific Belmont, MA, 1995.

Brockman et al. (2016) Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. Openai gym, 2016.

Dhariwal et al. (2017) Dhariwal, P., Hesse, C., Plappert, M., Radford, A., Schulman, J., Sidor, S., and Wu, Y. Openai baselines. https://github.com/openai/baselines , 2017.

Espeholt et al. (2018) Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I., et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint arXiv:1802.01561 , 2018.

Fox et al. (2016) Fox, R., Pakman, A., and Tishby, N. Taming the noise in reinforcement learning via soft updates. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence , pp. 202–211. AUAI Press, 2016.

Haarnoja et al. (2018) Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.01290 , 2018.

He et al. (2016) He, F. S., Liu, Y., Schwing, A. G., and Peng, J. Learning to play in a day: Faster deep reinforcement learning by optimality tightening. arXiv preprint arXiv:1611.01606 , 2016.

Henderson et al. (2017) Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., and Meger, D. Deep Reinforcement Learning that Matters. arXiv preprint arXiv:1709.06560 , 2017.

Horgan et al. (2018) Horgan, D., Quan, J., Budden, D., Barth-Maron, G., Hessel, M., van Hasselt, H., and Silver, D. Distributed prioritized experience replay. International Conference on Learning Representations , 2018.

Kingma & Ba (2014) Kingma, D. and Ba, J. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 , 2014.

Konda & Tsitsiklis (2003) Konda, V. R. and Tsitsiklis, J. N. On actor-critic algorithms. SIAM journal on Control and Optimization , 42(4):1143–1166, 2003.

Lee et al. (2013) Lee, D., Defourny, B., and Powell, W. B. Bias-corrected q-learning to control max-operator bias in q-learning. In Adaptive Dynamic Programming And Reinforcement Learning (ADPRL), 2013 IEEE Symposium on , pp. 93–99. IEEE, 2013.

Lillicrap et al. (2015) Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971 , 2015.

Lin (1992) Lin, L.-J. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning , 8(3-4):293–321, 1992.

Mannor & Tsitsiklis (2011) Mannor, S. and Tsitsiklis, J. N. Mean-variance optimization in markov decision processes. In International Conference on Machine Learning , pp. 177–184, 2011.

Mannor et al. (2007) Mannor, S., Simester, D., Sun, P., and Tsitsiklis, J. N. Bias and variance approximation in value function estimates. Management Science , 53(2):308–322, 2007.

Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. Nature , 518(7540):529–533, 2015.

Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., and Kavukcuoglu, K. Asynchronous methods for deep reinforcement learning. In International Conference on Machine Learning , pp. 1928–1937, 2016.

Munos et al. (2016) Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M. Safe and efficient off-policy reinforcement learning. In Advances in Neural Information Processing Systems , pp. 1054–1062, 2016.

Nachum et al. (2018) Nachum, O., Norouzi, M., Tucker, G., and Schuurmans, D. Smoothed action value functions for learning gaussian policies. arXiv preprint arXiv:1803.02348 , 2018.

O’Donoghue et al. (2017) O’Donoghue, B., Osband, I., Munos, R., and Mnih, V. The uncertainty bellman equation and exploration. arXiv preprint arXiv:1709.05380 , 2017.

Pendrith et al. (1997) Pendrith, M. D., Ryan, M. R., et al. Estimator variance in reinforcement learning: Theoretical problems and practical solutions . University of New South Wales, School of Computer Science and Engineering, 1997.

Petrik & Scherrer (2009) Petrik, M. and Scherrer, B. Biasing approximate dynamic programming with a lower discount factor. In Advances in Neural Information Processing Systems , pp. 1265–1272, 2009.

Popov et al. (2017) Popov, I., Heess, N., Lillicrap, T., Hafner, R., Barth-Maron, G., Vecerik, M., Lampe, T., Tassa, Y., Erez, T., and Riedmiller, M. Data-efficient deep reinforcement learning for dexterous manipulation. arXiv preprint arXiv:1704.03073 , 2017.

Precup et al. (2001) Precup, D., Sutton, R. S., and Dasgupta, S. Off-policy temporal-difference learning with function approximation. In International Conference on Machine Learning , pp. 417–424, 2001.

Schaul et al. (2016) Schaul, T., Quan, J., Antonoglou, I., and Silver, D. Prioritized experience replay. In International Conference on Learning Representations , Puerto Rico, 2016.

Schulman et al. (2015) Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International Conference on Machine Learning , pp. 1889–1897, 2015.

Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 , 2017.

Silver et al. (2014) Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. Deterministic policy gradient algorithms. In International Conference on Machine Learning , pp. 387–395, 2014.

Singh et al. (2000) Singh, S., Jaakkola, T., Littman, M. L., and Szepesvári, C. Convergence results for single-step on-policy reinforcement-learning algorithms. Machine learning , 38(3):287–308, 2000.

Sutton (1988) Sutton, R. S. Learning to predict by the methods of temporal differences. Machine learning , 3(1):9–44, 1988.

Sutton & Barto (1998) Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction , volume 1. MIT press Cambridge, 1998.

Thrun & Schwartz (1993) Thrun, S. and Schwartz, A. Issues in using function approximation for reinforcement learning. In Proceedings of the 1993 Connectionist Models Summer School Hillsdale, NJ. Lawrence Erlbaum , 1993.

Todorov et al. (2012) Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physics engine for model-based control. In Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on , pp. 5026–5033. IEEE, 2012.

Uhlenbeck & Ornstein (1930) Uhlenbeck, G. E. and Ornstein, L. S. On the theory of the brownian motion. Physical review , 36(5):823, 1930.

Van Hasselt (2010) Van Hasselt, H. Double q-learning. In Advances in Neural Information Processing Systems , pp. 2613–2621, 2010.

Van Hasselt et al. (2016) Van Hasselt, H., Guez, A., and Silver, D. Deep reinforcement learning with double q-learning. In AAAI , pp. 2094–2100, 2016.

Van Seijen et al. (2009) Van Seijen, H., Van Hasselt, H., Whiteson, S., and Wiering, M. A theoretical and empirical analysis of expected sarsa. In Adaptive Dynamic Programming and Reinforcement Learning, 2009. ADPRL’09. IEEE Symposium on , pp. 177–184. IEEE, 2009.

Watkins (1989) Watkins, C. J. C. H. Learning from delayed rewards . PhD thesis, King’s College, Cambridge, 1989.

Wu et al. (2017) Wu, Y., Mansimov, E., Grosse, R. B., Liao, S., and Ba, J. Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation. In Advances in Neural Information Processing Systems , pp. 5285–5294, 2017.

Appendix A Proof of Convergence of Clipped Double Q-Learning

附录 A 截断 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^{*}=\argmax_{a}Q^{A}(s,a)$ and then perform an update by setting target $y$:

在有限 MDP 设定下的截断 Double Q-learning 版本中，我们维护两个表格价值估计 $Q^{A}$、$Q^{B}$。每一步选择动作 $a^{*}=\argmax_{a}Q^{A}(s,a)$，然后通过设定目标 $y$ 做更新：

$$\displaystyle a^{*} \\ \displaystyle=\argmax_{a}Q^{A}(s^{\prime},a) \\ \displaystyle y \\ \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 $\alpha_{t}(s,a)$:

并相对目标与学习率 $\alpha_{t}(s,a)$ 更新价值估计：

$$\displaystyle Q^{A}(s,a) \\ \displaystyle=Q^{A}(s,a)+\alpha_{t}(s,a)(y-Q^{A}(s,a)) \\ \displaystyle 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}$ 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.

在有限 MDP 设定中，Double Q-learning 常用于处理随机奖励或状态转移引入的噪声，因此随机更新 $Q^{A}$ 或 $Q^{B}$ 之一。然而在函数逼近设定中，兴趣可能更偏向逼近误差，因而可在每次迭代同时更新 $Q^{A}$ 与 $Q^{B}$。证明自然扩展到随机更新其一的情形。

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.

证明大量借用 SARSA 收敛证明（Singh et al. 2000）以及 Double Q-learning（Van Hasselt 2010）。引理 1 的证明可见 Singh et al. 2000，建立在 Bertsekas 1995 的一个命题之上。

Lemma 1. Consider a stochastic process $(\zeta_{t},\Delta_{t},F_{t}),t\geq 0$ where $\zeta_{t},\Delta_{t},F_{t}:X\rightarrow\mathbb{R}$ satisfy the equation:

引理 1. 考虑随机过程 $(\zeta_{t},\Delta_{t},F_{t}),t\geq 0$，其中 $\zeta_{t},\Delta_{t},F_{t}:X\rightarrow\mathbb{R}$ 满足方程：

$$\Delta_{t+1}(x_{t})=(1-\zeta_{t}(x_{t}))\Delta_{t}(x_{t})+\zeta_{t}(x_{t})F_{t}(x_{t}), \tag{18}$$

where $x_{t}\in X$ and $t=0,1,2,...$. Let $P_{t}$ be a sequence of increasing $\sigma$-fields such that $\zeta_{0}$ and $\Delta_{0}$ are $P_{0}$-measurable and $\zeta_{t},\Delta_{t}$ and $F_{t-1}$ are $P_{t}$-measurable, $t=1,2,...$. Assume that the following hold:

其中 $x_{t}\in X$ 且 $t=0,1,2,...$。令 $P_{t}$ 为递增 $\sigma$-域序列，使得 $\zeta_{0}$ 与 $\Delta_{0}$ 为 $P_{0}$-可测，且 $\zeta_{t},\Delta_{t}$ 与 $F_{t-1}$ 为 $P_{t}$-可测，$t=1,2,...$。假设下列成立：

1. The set $X$ is finite.
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$ and $\forall x\neq x_{t}:\zeta(x)=0$.
3. $||\mathbb{E}\left[F_{t}|P_{t}\right]||\leq\kappa||\Delta_{t}||+c_{t}$ where $\kappa\in[0,1)$ and $c_{t}$ converges to $0$ with probability $1$.
4. Var$\left[F_{t}(x_{t})|P_{t}\right]\leq K(1+\kappa||\Delta_{t}||)^{2}$, where $K$ is some constant

1. 集合 $X$ 有限。
2. $\zeta_{t}(x_{t})\in[0,1],\sum_{t}\zeta_{t}(x_{t})=\infty,\sum_{t}(\zeta_{t}(x_{t}))^{2}<\infty$ 以概率 $1$ 成立，且 $\forall x\neq x_{t}:\zeta(x)=0$。
3. $||\mathbb{E}\left[F_{t}|P_{t}\right]||\leq\kappa||\Delta_{t}||+c_{t}$，其中 $\kappa\in[0,1)$，且 $c_{t}$ 以概率 $1$ 收敛到 $0$。
4. Var$\left[F_{t}(x_{t})|P_{t}\right]\leq K(1+\kappa||\Delta_{t}||)^{2}$，其中 $K$ 为某常数

Where $||\cdot||$ denotes the maximum norm. Then $\Delta_{t}$ converges to $0$ with probability $1$.

其中 $||\cdot||$ 表示最大范数。则 $\Delta_{t}$ 以概率 $1$ 收敛到 $0$。

Theorem 1. Given the following conditions:

定理 1. 给定下列条件：

1. Each state action pair is sampled an infinite number of times.
2. The MDP is finite.
3. $\gamma\in[0,1)$.
4. Q values are stored in a lookup table.
5. Both $Q^{A}$ and $Q^{B}$ receive an infinite number of updates.
6. The learning rates satisfy $\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$ and $\alpha_{t}(s,a)=0,\forall(s,a)\neq(s_{t},a_{t})$.
7. Var$\left[r(s,a)\right]<\infty,\forall s,a$.

1. 每个状态—动作对被采样无穷多次。
2. MDP 有限。
3. $\gamma\in[0,1)$。
4. Q 值存储在查找表中。
5. $Q^{A}$ 与 $Q^{B}$ 均收到无穷多次更新。
6. 学习率满足 $\alpha_{t}(s,a)\in[0,1],\sum_{t}\alpha_{t}(s,a)=\infty,\sum_{t}(\alpha_{t}(s,a))^{2}<\infty$ 以概率 $1$，且 $\alpha_{t}(s,a)=0,\forall(s,a)\neq(s_{t},a_{t})$。
7. Var$\left[r(s,a)\right]<\infty,\forall 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$.

则截断 Double Q-learning 将以概率 $1$ 收敛到由贝尔曼最优方程定义的最优价值函数 $Q^{*}$。

Proof of Theorem 1. We apply Lemma 1 with $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}$.

定理 1 的证明. 我们对 $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}$ 应用引理 1。

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 $\zeta_{t}=\alpha_{t}$.

首先注意：引理条件 1 与 4 分别由定理条件 2 与 7 保证。引理条件 2 由定理条件 6 以及我们选取 $\zeta_{t}=\alpha_{t}$ 保证。

Defining $a^{*}=\argmax_{a}Q^{A}(s_{t+1},a)$ we have

定义 $a^{*}=\argmax_{a}Q^{A}(s_{t+1},a)$，我们有

$$\displaystyle\Delta_{t+1}(s_{t},a_{t}) \\ \displaystyle=(1-\alpha_{t}(s_{t},a_{t}))(Q^{A}_{t}(s_{t},a_{t})-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})) \\ \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})$ as:

其中我们把 $F_{t}(s_{t},a_{t})$ 定义为：

$$\displaystyle F_{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}) \\ \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^{*}) \\ \displaystyle=F^{Q}_{t}(s_{t},a_{t})+c_{t},$$