DQN中的高估问题及解决方案

一、DQN 中的 Bootstrapping

Bootstrapping，自举，字面意思是：拔自己的鞋带，把自己举起来。而 Bootstrapping 在强化学习中的意思是：用一个估算去更新同类的估算。

在 DQN 算法中，我们让 DQN 在 $t$ 时刻的估计值 $Q(s_t)$ 尽量接近 TD target：

$$y_t = r_t + \gamma \cdot \underset{a}{\operatorname{max}} Q_*(s_{t+1}, a)$$

TD target 中使用到了 DQN 在 $t+1$ 时刻的估计值 $Q(s_{t+1})$ ，即：我们 用 Q 网络在 $t+1$ 时刻的 估计值 去更新 $t$ 时刻的 估计值 。

二、DQN 中的高估问题

2.1 最大化操作导致高估

最大化操作本身会导致值被高估。

举个例子，假如我们有一个数组 $A$：

$$A = [-1, 5, -6, 8, 3, 2, -4, -7, 9]$$

数组 $A$ 的最大值是9，平均值是1。

数组 $A$ 加上一个均值为0数组 $B$：

$$B = [-1, 1, -1, 0, 1, 1, -1, -1, 1]$$

后得到的数组 $C$：

$$C = A+B = [-2, 6, -7, 8, 4, 3, -5, -8, 10]$$

数组 $C$ 的平均值依然是1，但是最大值却变成了10。

在 DQN 中，数组 $A$ 相当于各个动作真实的 Q 值，因为我们并不知道这个真实值，所以用 DQN 来估算它们。而估算总会有误差，相当于引入了上面的数组 $B$ 。假设 DQN 对真实动作价值的估算是无偏的（无偏估计），即 DQN 对动作估算的 Q 值和真实的 Q 值的均值相同，这和上面的例子一样。最后 DQN 估算出各个动作的 Q 值的结果相当于上面例子的 $A+B$ ，均值依然保持不变，但是最大值却变大了，所以 DQN 中最大化操作可能得到的结果也是比真实 Q 值更大的值，即最大化的操作导致了 DQN 高估了 Q 值。

2.2 Bootstrapping 传播高估

在上面分析到， TD target 中使用了 Q 网络在 $t+1$ 时刻的预估值，因为预估本身可能会导致高估真实的 Q 值，而让 DQN 在 $t$ 时刻的估计值 $Q(s_t)$ 尽量接近 TD target 则会将高估传播回 DQN，从而形成了一种正反馈。所以，一旦 DQN 中出现了高估，这种正反馈会让高估越来越严重。

四、高估导致的问题

对不同动作不同程度的高估会导致原本最优的动作变成不是最优的，原本最差的动作可能会变成最优的动作。

假设某个状态下，两个动作真实的 Q 值分别是110和150，但是经过 DQN 高估后得到 Q 值分别是200和180。显然，经过高估后的各个动作的优劣完全变了样：原本最优的动作变成了最差的，最差的动作却成了最优的了。

因为各个状态下各个动作出现的概率总是不均匀的，越频繁出现的动作 DQN 对该动作的估算更新得也更频繁，估算中出现的高估则进一步加剧了这种情况。最后导致了 DQN 对各个状态下各个动作的高估程度不同。

五、解决方案

5.1 使用 target network 避免 Bootstrapping

在 DQN 中新加一个名为 target network 的网络 $Q(s,a; \mathbf{w}^-)$ ，其结构和原始的 Q 网络 $Q(s,a; \mathbf{w})$ 相同，但是使用不同的网络参数 $\mathbf{w}^-$ 。

两个网络的用处不同，原来的 Q 网络 $Q(s,a; \mathbf{w})$ 用来控制智能体和收集学习用的经验，而 target network 则用来计算 TD target 。

使用了 target network 的 DQN 算法的完整流程如下：

1. 计算 TD target ：

   $$y_t = r_t + \gamma \cdot \underset{a}{\operatorname{max}} Q(s_{t+1}, a; \mathbf{w}^-)$$

2. 计算 TD error ：

   $$\delta^t = Q(s_t,a_t; \mathbf{w}) - y_t$$

3. 使用梯度下降算法来更新 Q 网络 $Q(s_t,a_t; \mathbf{w})$ 的参数：

   $$\mathbf{w} \leftarrow \mathbf{w} - \alpha \cdot \delta^t \cdot \frac{\partial Q(s_t,a_t;\mathbf{w})}{\partial \mathbf{w}}$$

因为使用了 target network 的预估值来更新原来的 Q 网络的预估值，这就避免了 Bootstrapping ，缓解了高估的问题。但是因为需要周期性的用 Q 网络的参数值来更新 target network，所以并不能完全解决高估问题，只能缓解。

target network 参数的更新方式是周期性的同步自原来的Q网络。同步的方式有两种：

1. 直接使用原来的 Q 网络参数替换 target network 的参数：

   $$\mathbf{w}^- \leftarrow \mathbf{w}$$

2. 将原来的 Q 网络参数和 target network 的参数做加权平均：

   $$\mathbf{w}^- \leftarrow \tau \cdot \mathbf{w} + (1 - \tau) \cdot \mathbf{w}^-$$

5.2 使用 Double DQN 避免最大化导致的高估

5.2.1 原始的 DQN

其实 DQN 在计算 TD target 时，其中的 $\underset{a}{\operatorname{max}} Q(s_{t+1}, a; \mathbf{w})$ 可以分解成两步操作：

1. 使用 原来的 Q 网络 选择最优动作 $$a_* = \underset{a}{\operatorname{argmax}} Q(s_{t+1},a; \mathbf{w})$$
2. 同时 使用 原来的 Q 网络 预估动作的价值 $$y_t = r_t + \gamma \cdot Q(s_{t+1}, a_*; \mathbf{w})$$

这两步用的都是 原来的 Q 网络 来进行计算，这种方式的表现最差，训练出的网络会严重高估真实的动作价值。

5.2.2 使用了 target network 的 DQN

使用了 target network 的 DQN 计算 TD target 时：

1. 使用 target network 选择最优动作 $$a_* = \underset{a}{\operatorname{argmax}} Q(s_{t+1},a; \mathbf{w}^-)$$
2. 同时 使用 target network 预估动作的价值 $$y_t = r_t + \gamma \cdot Q(s_{t+1}, a_*; \mathbf{w}^-)$$

这两步用的都是 target network 来进行计算，这种方式因避免了 Bootstrapping，所以表现会比原始的 DQN 好一些，但是训练出的网络依然会高估真实的动作价值。

5.2.3 Double DQN

而 Double DQN 则是对原始的 DQN 和使用了 target network 的 DQN 的一种改进：

1. 使用 原来的 Q 网络 选择最优动作 $$a_* = \underset{a}{\operatorname{argmax}} Q(s_{t+1},a; \mathbf{w})$$
2. 使用 target network 预估动作的价值 $$y_t = r_t + \gamma \cdot Q(s_{t+1}, a_*; \mathbf{w}^-)$$

Double DQN 中使用 原来的 Q 网络 选择最优动作，另外使用了 target network 预估动作的价值。两步使用了不同了网络，虽然改动很少，但是却能进一步的缓解高估的问题（依然没有根除高估的问题）。

对 target network 来说可以证明如下的等式是成立的：

$$Q(s_{t+1}, a_*; \mathbf{w}^-) \le \underset{a}{\operatorname{max}} Q(s_{t+1}, a; \mathbf{w}^-)$$

等式左边是 Double DQN 算出的，等式右边是 target network 算出的。上面的等式表面了 Double DQN 估算出的 Q 值总是不高于使用 target network 计算出 Q 值，所以缓解了高估的问题。

5.3 使用 Dueling Network 改进网络结构

Dueling Network 中使用到了优势函数的概念，这里先介绍一下优势函数。

后面的推导，特别是关于优势函数的推导与原论文中的推导不同。

5.3.1 优势函数（Advantage Function）

1. 定义

   定义优势函数为：

   $$A_*(s,a) = Q_*(s,a) - V_*(s)$$

   其意义是：将 $V_*(s)$ 作为基准，在状态 $s$ 的情况下，执行动作 $a$ 的好坏。即动作 $a$ 相对 $V_*(s)$ 的优势。

2. 性质

   对优势函数等式的两边同时做基于动作 $a$ 的 $max$ 操作得到：

   $$\underset{a}{max}A_*(s,a) = \underset{a}{max}Q_*(s,a) - V_*(s)$$

   根据贝尔曼最优方程（Bellman Optimality Equation）：

   $$V_*(s) = \max_a Q_*(s,a)$$

   于是：

   $$\begin{aligned} \underset{a}{max}A_*(s,a) & = \underset{a}{max}Q_*(s,a) - V_*(s) \\ & = \underset{a}{max}Q_*(s,a) - \underset{a}{max}Q_*(s,a) \\ & = 0 \end{aligned}$$

   即：

   $$\underset{a}{max}A_*(s,a) = 0$$

3. 推导

   变换一下优势函数定义的等式，可以得到下面的等式：

   $$Q_*(s,a) = V_*(s) + A_*(s,a)$$

   同时根据优势函数的性质，可以在上面等式右边减去一个 $0$，得到等式：

   $$Q_*(s,a) = V_*(s) + A_*(s,a) - \underset{a}{max}A_*(s,a) \tag{5.3.1}$$

   但是为什么要在等式的右边减去一个0呢？对比一下减去0前后的两个等式：

   $$\begin{aligned} Q_*(s,a) & = V_*(s) + A_*(s,a) \\ Q_*(s,a) & = V_*(s) + A_*(s,a) - \underset{a}{max}A_*(s,a) \\ \end{aligned}$$

   发现，上面的公式有一个下面公式没有的 唯一解问题 ：如果 $V_*(s)$ 的值整体加 $x$，而 $A_*(s,a)$ 的值整体减 $x$。上面的等式最后的值 $Q_*(s,a)$ 没变，但是下面等式最后的值增加了 $x$。 而没有唯一解在强化学习中就意味着难以训练出模型，所以下面一个等式才能应用到强化学习中。

5.3.2 优势函数的应用 Dueling Network

根据上面利用优势函数推导出的等式：

$$Q_*(s,a) = V_*(s) + A_*(s,a) - \underset{a}{max}A_*(s,a)$$

使用两个神经网络来分别近似 $V_*(s)$ 函数和 $A_*(s,a)$ 函数，进而就可以得到 $Q_*(s,a)$ 函数，这就是 Dueling Network。

在实际使用时，根据数学公式推导出的 Dueling Network 中对优势函数求最大化的操作，换成均值操作得到的效果更好更稳定，这种替换操作没有理论依据，但是实际效果更好。

$$Q_*(s,a) = V_*(s) + A_*(s,a) - \underset{a}{mean}A_*(s,a)$$

最后，因为 Dueling Network 只是改进了 DQN 中原始 Q 网络的结构，所以使用了 Dueling Network 的 DQN 的训练方法与使用了原始的 Q 网络的 DQN 训练方法相同，DQN 改进的技巧（比如Double DQN）也依然都是可以使用的。

---

参考：高估问题、Target Network、Double DQN
DQN 论文：Playing Atari with Deep Reinforcement Learning
Target Network 论文：Human-level control through deep reinforcement learning
Double DQN 论文：Deep Reinforcement Learning with Double Q-learning
Dueling Network 论文：Dueling Network Architectures for Deep Reinforcement Learning