Twin Delayed Deep Deterministic policy gradient

Fujimoto, S., Van Hoof, H., & Meger, D. (2018). Addressing Function Approximation Error in Actor-Critic Methods. 35th International Conference on Machine Learning, ICML 2018, 4, 2587–2601.

1. TD3 概念

Q-learning 和 actor-critic 都存在状态值过估计以及收敛于次优策略的问题。本文依照 double Q-learning 的思想提出了 TD3 算法，研究了过估计误差和目标网络间的联系，以及通过延迟策略的更新来降低每次更新的误差，提高策略的性能。

离散动作空间的过估计问题已经进行了研究，提出了 double Q-learning 算法。但是对于连续动作空间的 actor-critic 框架，过估计问题和误差的累积问题同样存在。过估计问题的来源主要是对带有噪声的状态值进行最大化，导致了最终目标产生过估计。另外，基于时间差分算法的强化学习算法，会利用一个本身不正确的状态估计值来进行下一次更新，导致误差累积。过估计和误差累积通常会导致一个本来很差的状态被估计成很高的状态值，产生次优策略。

本文主要有三个贡献：

• 首先，本文展示了采用目标网络是降低误差累积和降低误差的重要方法。
• 其次，本文提出了策略延迟更新的策略，即在状态估计收敛后再更新策略。
• 最后，本文提出了一种新颖的正则方法。

最终，本文将以上的方法与 DDPG 融合起来，产生的算法命名为 TD3 (Twin Delayed Deep Deterministic policy gradient algorithm)。

2. 相关知识

强化学习的目标：

$$R_t = \sum_{i=t}^{T} \gamma^{i-t} r(s_i,a_i) \tag{1}$$

DDPG 的目标求导：

$$\nabla_\phi J(\phi) = \mathbb{E}_{s \sim p_\pi} [\nabla_a Q^\pi(s,a)|_{a=\pi(s)} \nabla_\phi \pi_\phi(s)] \tag{2}$$

Q-learning 的时间差分更新公式：

$$Q^\pi(s,a) = r + \gamma \mathbb{E}_{s',a'}[Q^\pi(s',a')], \;\; a' \sim \pi(s') \tag{3} \label{3}$$

DQN 的目标函数：

$$y = r + \gamma Q_{\theta'}(s',a'), \;\; a' \sim \pi_{\phi'}(s') \tag{4}$$

其中 $\pi_{\phi’}$ 是由目标网络计算出来的，目标网络的参数更新方式为：

$$\theta' \leftarrow \tau \theta + (1-\tau) \theta' \tag{5}$$

3. 过估计偏差

在离散空间的 Q-learning 算法，过估计偏差的来源比较明显。首先对于一个贪婪的目标函数：$y=r+\gamma \max_{a’}Q(s’,a’)$，如果该函数对误差 $\epsilon$ 比较敏感，则在 $Q(s’,a’)$ 上求最大值通常会大于实际的最大值：$\mathbb{E}_\epsilon[\max_{a’}(Q(s’,a’)+\epsilon)] \ge \max_{a’} Q(s’,a’)$ 。即使误差是零均值的，也会导致过高的动作值估计，并且通过贝尔曼方程传播，如公式$ \eqref{3}$，从而导致误差累积。

在连续空间的 AC 框架中，过估计偏差并不是那么明显，但是它的确存在。

3.1 AC 中的过估计偏差

AC 框架中的策略更新依赖于 critic 对状态值的估计。但是状态值的估计过程中会存在过估计偏差，导致产生次优策略

现在假设两种策略函数参数 $\phi_{approx}$ 和 $\phi_{true}$，对应的策略表示为 $\pi_{approx}$ 和 $\pi_{true}$ 。其中 $\phi_{approx}$ 的更新依赖于动作值估计函数 $Q_\theta(s,a)$，而 $\phi_{true}$ 的更新依赖于真实的动作值估计函数 $Q^\pi(s,a)$，但这是未知的。导数如下：

$$\begin{aligned} \phi_{approx} &= \phi + \frac{\alpha}{Z_1} \mathbb{E}_{s \sim p_\pi} [\nabla_\phi \pi_\phi(s) \nabla_a Q_\theta(s,a) |_{a=\pi_\phi(s)}] \\ \phi_{true} &= \phi + \frac{\alpha}{Z_2} \mathbb{E}_{s \sim p_\pi} [\nabla_\phi \pi_\phi(s) \nabla_a Q^\pi(s,a) |_{a=\pi_\phi(s)}] \end{aligned} \tag{6}$$

其中 $Z_1$ 和 $Z_2$ 是规范化参数，即 $Z^{-1} | \mathbb{E}[\cdot] |=1$ 。通过规范化参数，噪声的存在就可以反映为学习步长的变化。

由于梯度的方向只是局部的最大化方向，存在噪声 $\alpha \le \epsilon_1$（噪声足够小），那么 $\pi_{approx}$ 的近似动作值 $Q_\theta$ 就会大于 $\pi_{true }$ 。这可以理解为，$\pi_{approx}$ 和 $\pi_{ture}$ 都在近似动作值函数 $Q_\theta$ 图像的山腰，但是 $\pi_{approx}$ 前进的步数大于 $\pi_{ture}$，用公式表示如下：

$$\mathbb{E}[Q_\theta(s,\pi_{approx}(s))] \ge \mathbb{E}[Q_\theta(s,\pi_{true}(s))] \tag{7} \label{7}$$

同理，存在噪声 $\alpha \le \epsilon_2$（噪声足够小），那么 $\pi_{approx}$ 的真实动作值 $Q^\pi$ 就会小于 $\pi_{true }$ 。这可以理解为，$\pi_{approx}$ 和 $\pi_{ture}$ 都在真实动作值函数 $Q^\pi$ 图像的山顶，但是 $\pi_{approx}$ 前进的步数大于 $\pi_{ture}$，用公式表示如下：

$$\mathbb{E}[Q^\pi(s,\pi_{true}(s))] \ge \mathbb{E}[Q^\pi(s,\pi_{approx}(s))] \tag{8} \label{8}$$

同时，近似动作值函数对于 $\pi_{ture}$ 而言通常都是过估计的，也就是 $\mathbb{E}[Q_\theta(s,\pi_{ture}(s))] \ge \mathbb{E}[Q^\pi(s,\pi_{ture}(s))]$，结合公式 $\eqref{7}$ 和公式 $\eqref{8}$ ，可以得到：

$$\mathbb{E}[Q_\theta(s,\pi_{approx}(s))] \ge \mathbb{E}[Q^\pi(s,\pi_{approx}(s))] \tag{9} \label{9}$$

由公式 $\eqref{9}$ 可以知道，近似动作值函数对于学习的策略存在过估计，这种过估计偏差虽然在一个更新步骤中很小，但是经过非常多的更新步骤积累起来的估计偏差将会变得非常大。而过估计的动作值函数将会产生次优策略，从而导致新一轮的偏差出现。

本文为了降低 critic 的过估计偏差，提出了 Clipped Double Q-learning 方法。

3.2 Clipped Double Q-learning

在 Double DQN 方法中，作者利用了一个目标网络对时间差分更新公式中的动作值进行估计，但是在采取行动策略时，用的是行为网络的贪婪策略。

但是本文作者发现，这种方法对于 AC 框架的作用效果不大，目标网络和行为网络对状态值的估计相似，不能很好地解决过估计问题。本文作者提出，采用一对 actors $(\pi_{\phi_1},\pi_{\phi_2})$ 和一对 critics $(Q_{\theta_1},Q_{\theta_2})$，$\pi_{\phi_1}$ 的更新依赖于 $Q_{\theta_1}$，$\pi_{\phi_2}$ 的更新依赖于 $Q_{\theta_2}$，但是在时间差分更新公式中，目标 $y_1$ 依赖于 $Q_{\theta_2}$，目标 $y_2$ 依赖于 $Q_{\theta_1}$：

$$y_1 = r + \gamma Q_{\theta_2'}(s',\pi_{\phi_1}(s')) \\ y_2 = r + \gamma Q_{\theta_1'}(s',\pi_{\phi_2}(s')) \tag{10} \label{10}$$

在公式 $\eqref{10}$ 中，由于$Q_{\theta_1}$ 和 $Q_{\theta_2}$ 并不是特别独立（参数更新依赖于对方以及使用同一个经验回放池），还是会存在过估计的问题，本文进而提出 Clipped Double Q-learning 方法：

$$y_1 = r + \gamma \min_{i=1,2} Q_{\theta_2'}(s',\pi_{\phi_1}(s')) \tag{11} \label{11}$$

公式 $\eqref{11}$ 可能会存在欠估计（underestimation）问题，但是欠估计的偏差不会在策略更新中传播（因为策略不会选一个欠优的动作）。对于 $Q_{\theta_2}$ 的更新，可以简单令 $y_2=y_1$ 。

4. 解决高方差

除了过估计偏差的影响，高方差也会给策略梯度的更新带来影响。

在使用时间差分公式进行更新时，实际上贝尔曼方程并没有完全满足，每次更新都会与真正的贝尔曼方程存在残差，称为 TD误差 $\delta(s,a)$：

$$Q_\theta(s,a) = r + \gamma \mathbb{E}[Q_\theta(s',a')] - \delta(s,a) \tag{12} \label{12}$$

对公式 $\eqref{12}$ 进行改写：

$$\begin{aligned} Q_\theta(s_t,a_t) &= r_t + \gamma \mathbb{E}[Q_\theta(s_{t+1},a_{t+1})] - \delta_t \\ &= r_t + \gamma \mathbb{E}[r_{t+1} + \gamma \mathbb{E}[Q_\theta(s_{t+2},a_{t+2}) - \delta_{t+1}]] - \delta_t \\ &= \mathbb{E}_{s_i \sim p_\pi, a_i \sim \pi} \left[ \sum_{i=t}^T \gamma^{i-t}(r_i - \delta_i) \right] \end{aligned} \tag{13} \label{13}$$

从公式 $\eqref{13}$ 可以看出动作值估计 $Q_\theta$ 的方差不仅依赖于期望回报值，也依赖于 TD 误差总和。如果 $\gamma$ 比较大，那么 TD 总误差的方差是很大的。

4.1 目标网络和延迟更新

目标网络是强化学习实现稳定更新的重要方法。目标网络给强化学习提供了一个稳定的目标。如果没有一个稳定的目标，每次更新过程中都会产生残差，并且积累，最终产生较大的方差。

目标网络参数的更新可以采用软更新公式：

$$\theta' \leftarrow \tau \theta + (1-\tau)\theta' \tag{14}$$

目标网络在经历多次更新才能收敛，并且策略在高误差的状态估计下更新会产生发散的动作。本文认为策略网络的更新应该比状态网络的更新频率更低。也就是说在进行策略更新之前，应该先降低状态估计的误差。

因此延迟更新是让策略更新在每隔 $d$ 个状态更新之后才进行。

4.2 对目标策略的正则化

如果策略采用的是确定性策略，存在的问题是确定性策略经常会受到状态估计的误差的影响，导致过拟合。本文通过对目标策略添加受限的噪声来进行正则化。

$$y = r + \gamma Q_{\theta'}(s',\pi_{\phi'}(s') + \epsilon), \\ \epsilon \sim clip(\mathcal{N}(0,\sigma),-c,c) \tag{15} \label{15}$$

注意公式 $\eqref{15}$ 中目标策略所用的噪声 $\epsilon$ 是和探索策略所用的噪声 $\epsilon$ 区分开的。

5. 算法伪代码