本文主要讲解有关Double DQN算法、Prioritized Experience Replay DQN 算法和 Dueling DQN 算法的相关内容。
对于 DQN 算法的改进主要有三种——Double DQN算法、Prioritized Experience Replay DQN 算法和 Dueling DQN 算法。
一、Double DQN
传统 DQN 中的 Q-target 部分如下：
$$
Y_t^{DQN}=R_{t+1}+\gamma\max_aQ(S_{t+1},a;\theta_t^-)
$$
$\theta^-$ 表示旧的神经网络参数。因为在选择行为 a 和得到对应的 Q 值时使用的是同一张 Q 表，而神经网络总是倾向于选择被高估的动作，可能导致估计值过大，过于乐观。所以可以引入另一个神经网络来减小误差的影响。而 DQN 中本来就有两个神经网络，所以可以用估值网络来估计 Q-target 中 max Q 中动作的最大值。
$$
Y_t^{DoubleDQN}=R_{t+1}+\gamma Q(S_{t+1},\arg\max_aQ(S_{t+1},a;\theta_t);\theta_t^-)
$$
在实操时，它首先使用估值网络计算下一个状态 $S_{t+1}$ 的对应各个 Action 的 Q 值，然后选取最大的那个 Q 值对应 Action 的索引，再使用目标网络选取估值网络中给定Action 索引对应的 Q 值。即用一张 Q 表来选择具有最大值的行动 a，再用另一张 Q 表来计算 $Q(S_{t+1},a)$ 的最大值。
Double DQN 走迷宫例子
莫烦大神的 Double DQN 只给了一个基于 gym 的例子，一开始我以为 gym 不支持 windows（目前已经部分支持了），于是就还是以走迷宫为例，自己实现了一下，下面说下碰到的几个坑。
下面只给出在 build_net 函数中的关键语句，完整的代码可以见我的 github。
1 | with tf.variable_scope("eval_net"): # 估值网络 |
其实思想很简单，就是找到估值网络中每个状态的动作最大值对应的下标，然后在计算 Q-target 时使用以上得到的下标。但是由于 TensorFlow 是静态定义计算图，然后再喂进数据动态进行计算的， 所以在喂数据之前张量的大小是不确定的，张量的值也是不知道的。直接使用得到的下标会出错，需要全部改成动态的过程。比如我之前是用以下方式写的，程序会报错。
1 | q_target = self.r + self.gamma * self.q_next[row,action_index] |
二、Prioritized Replay DQN
当正负奖励的样本不均衡时，需要重视那种比较少量但是值得学习的样本。所以在取一个 batch 的样本时不再采用随机采样，而是按照所有样本的优先级来采样。所谓一个样本就是一个 $(s,a,r,s’)$ 。
样本的优先级定义为 $Q_{target} - Q_{evalue}$，即两者之间的差异大小，也就是 TD-error。该值越大则说明预测的精度有比较大的上升空间，这个样本就越需要被学习，优先级越高。
假设有 4 个样本，其优先级分别为 3，10，12，4；每个样本所占的区间长度为其优先级大小，即第一个样本的区间为 (0 , 3)，第二个样本为 (3 , 13)，第三个为 (13 , 25)，第四个为 (25 , 29)。那么可以在 (0 , 29) 的范围内随机生成一个整数，这个整数处于哪个样本对应的区间内，则对哪个样本进行采样。这样优先级高的样本被采样到的概率也高。为了实现动态地按优先级采样，又提出了 SumTree 的结构。
SumTree 是一棵完全二叉树，如下图所示，它的每个叶节点对应一个样本，圆圈内的数字是样本的优先级，叶子节点下方的数是该样本所占的区间范围。内部节点的值是其儿子节点优先级值的和。
那么怎么利用 SumTree 进行搜索呢？假设优先级之和（根节点中的数字）为 sum，则在 (0 , sum) 的区间内随机生成一个整数 A，从根节点开始，不断与当前节点的 左儿子 对应的数值比较，若 A 小于该数值，则在当前节点的左子树中搜索；反之在右子树中搜索，同时将数值 A 更新为 $A=A-当前节点左儿子的值$。重复搜索过程直到到达叶子节点，则搜索结果落在哪个区间内，该区间对应的样本将会被采样。
举个例子，在上图中，由于优先级之和为 42，那么可以在 (0 , 42) 的范围内随机生成一个整数，比如生成的数是 24，那么从根节点开始 24 先于根节点的左儿子对应的数值 29 比较，明显 24<29，应该在根节点的左子树中搜索，然后再与值为 29 的节点的左儿子 13 比较，因为 24>13，所以应该在右子树中搜索，同时将搜索值更新为 $24-13=11$，不断搜索，最终落在第 3 个叶子节点对应的样本中，于是将对该样本进行采样。
上面是对一个样本根据优先级进行随机采样，如果是采样 n 个样本呢？可以先将总优先级平均分为 n 个区间，然后在每个区间各产生一个随机数，再进行上述采样。
在更新时，不仅要更新样本的值，而且要更新 SumTree 中该样本以及该样本的祖先节点的优先级。因为 SumTree 是一棵完全二叉树，所以可以用数组表示 SumTree，如果一个节点的下标为 i，则其左右儿子节点的下标分别为 $2\times i$ 和 $2\times i +1$，这样要寻找一个节点的祖先节点就比较方便了。另外还需要一个数组来存储样本的值。
最后来思考一个问题，numpy 中提供了一个 np.random.choice() 函数，这个函数也可以实现按照概率从数组中随机取数，那么为什么不直接用它呢？原因很简单，这个函数的复杂度太高了，不过我没有在网上找到它的复杂度到底是多少，有知道小伙伴还请告知。
因为使用优先级采样的方式改变了样本的分布，所以会产生误差，为了消除偏差，使用了重要性采样（Importance Sampling）的方法，也就是让原来的损失函数变为：
$$
L(\theta)=E[ISWeights\times(Q_target-Q_evalue)^2]
$$
ISWeights 就是下面会提到的重要性权重。
Importance sampling（重要性采样）：
$$
E_{x\sim p}[f(x)]=\int f(x)p(x)dx=\int f(x)\frac{p(x)}{q(x)}q(x)dx=E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]
$$
当只能从 q(x) 分布得到样本时，可以做以上变换来计算 p(x) 分布的期望，其中 $\frac{p(x)}{q(x)}$ 被称为重要性权重。
重要性采样的一个问题就是：两个分布之间的差别不能太大，否则方差会出现较大差别。
方差公式：
$$
Var[x]=E[x^2]-(E[x])^2
$$
上面已经推出两个分布的期望相等：
$$
E_{x\sim p}[f(x)]=E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]
$$
两个分布的方差：
$$
Var_{x\sim p}[f(x)]=E_{x\sim p}[f(x)^2]-(E_{x\sim p}[f(x)])^2
$$
$$
Var_{x\sim q}[f(x)\frac{p(x)}{q(x)}]=E_{x\sim q}[(f(x)\frac{p(x)}{q(x)})^2]-(E_{x\sim q}[f(x)\frac{p(x)}{q(x)}])^2
$$
$$
=E_{x\sim p}[(f(x)^2\frac{p(x)}{q(x)})]-(E_{x\sim p}[f(x)])^2
$$
这样就得到了两者方差之间的关系。最后一个等式成立的原因是分布 q 和 p 的期望相等，并且因为：
$$
E_{x\sim q}[(f(x)\frac{p(x)}{q(x)})^2]=\int f^2(x)\frac{p^2(x)}{q^2(x)}\cdot q(x)dx=\int f^2(x)\frac{p^2(x)}{q(x)}dx
$$
$$
=\int f^2(x)\frac{p(x)}{q(x)}\cdot p(x)dx=E_{x\sim p}[(f(x)^2\frac{p(x)}{q(x)})]
$$
根据重要性采样的思想（$E_{x\sim p}[f(x)]=E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]$），将 on-policy 变为 off-policy：
$$
\nabla \bar R_\theta=E_{\tau\sim p_\theta(\tau)}[R(\tau)\nabla\log p_\theta(\tau)]=E_{\tau\sim p_\theta’(\tau)}[\frac{p_\theta(\tau)}{p_\theta’(\tau)}R(\tau)\nabla\log p_\theta(\tau)]
$$
三、Dueling DQN
在普通的 DQN 中，在某些状态下值函数的大小与动作无关，所以 Dueling DQN 将Q网络分成两部分。第一部分仅与状态 S 有关，与具体要采用的动作 A 无关，这部分我们叫做 价值函数 部分，记做 $V(S,w,\alpha)$ 。第二部分同时与状态 S 和动作 A 有关，这部分叫做 优势函数 （Advantage Function）部分，记为 $A(S,A,w,\beta)$。V 表示静态的状态环境本身具有的价值，而 A 表示选择某个 action 带来的额外价值。
那么最终的 Q 函数可以重新表示为：
$$
Q(S,A,w,\alpha,\beta)=V(S,w,\alpha)+A(S,A,w,\beta)
$$
其中，$w$ 是公共部分的网络参数，而 $\alpha$ 是价值函数独有部分的网络参数，而 $\beta$ 是优势函数独有部分的网络参数。
我们可以直接使用上面的价值函数的组合公式得到我们的动作价值，但是这个式子无法辨识最终输出里面 $V(S,w,\alpha)$ 和 $A(S,A,w,\beta)$ 各自的作用。也就是说当 Q 值一定时，V 和 A 的值可能有多种情况。为了可以体现这种可辨识性（identifiability），实际使用的组合公式如下：
$$
Q(S,A,w,\alpha,\beta)=V(S,w,\alpha)+[A(S,A,w,\beta)−\frac{1}{|A|}\sum_{a′\in A}A(S,a′,w,\beta)]
$$
其实就是对优势函数部分做了中心化的处理。
减去同一状态下动作值的平均值做法的另一种解释是，网络在训练时可能为了简单而直接让 Q=A，也就是让 V=0，为了避免这个情况的发生，于是加入了该限制。这样 A 同一状态下动作值之和为 0，而 V 同一状态下动作值为 Q 同一状态下动作值的均值，两者都不可能全为 0 了。
四、其他优化方法
1. Noisy DQN
$\epsilon-greedy$ 是对每一个动作加噪声，而 Noisy DQN 是对每一个回合的 Q-function 的参数加噪声，也就是说每个回合中 Q-function 的参数不会边。相较而言后者的方式比较好。
2. Distributional DQN
Q(s,a) 是累计收益的期望值，也就是价值函数的均值，但是不同的分布得到的均值可能相同，所以 Distributional DQN 认为可以输出 Q 值的分布，当具有相同的均值时，选择具有较小方差（风险）的那个。但是实际上这个方法难以实现。
3. RainBow
RainBow 这个版本的 DQN 是结合了上述多种不同的对 DQN 的优化方法得到的，提升还是蛮大的。作者在论文里对比了各种方法的得分（如左图所示），还对比了 RainBow 分别去掉一个优化的方法后的得分（如右图所示）。
五、总结
在 Double DQN 中，我们通过优化目标 Q 值的计算来优化算法；在 Prioritized Replay DQN 中，我们通过优化经验回放池按优先级采样来优化算法；而在 Dueling DQN 中，我们通过优化神经网络的结构来优化算法。
- 本文作者： 俎志昂
- 本文链接： zuzhiang.cn/2019/10/11/DQN-improve/
- 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！