最近自己会把自己个人博客中的文章陆陆续续的复制到CSDN上来，欢迎大家关注我的 个人博客，以及我的github。
本文主要讲解有关Double DQN算法、Prioritized Experience Replay DQN 算法和 Dueling DQN 算法的相关内容。
对于 DQN 算法的改进主要有三种——Double DQN算法、Prioritized Experience Replay DQN 算法和 Dueling DQN 算法。
一、Double DQN
传统 DQN 中的 Q-target 部分如下：
Y
t
D
Q
N
=
R
t
+
1
+
γ
max
a
Q
(
S
t
+
1
,
a
;
θ
t
−
)
Y_t^{DQN}=R_{t+1}+\gamma\max_aQ(S_{t+1},a;\theta_t^-)
YtDQN=Rt+1+γamaxQ(St+1,a;θt−)
θ
−
\theta^-
θ− 表示旧的神经网络参数。因为在选择行为 a 和得到对应的 Q 值时使用的是同一张 Q 表，而神经网络总是倾向于选择被高估的动作，可能导致估计值过大，过于乐观。所以可以引入另一个神经网络来减小误差的影响。而 DQN 中本来就有两个神经网络，所以可以用估值网络来估计 Q-target 中 max Q 中动作的最大值。
Y
t
D
o
u
b
l
e
D
Q
N
=
R
t
+
1
+
γ
Q
(
S
t
+
1
,
arg
max
a
Q
(
S
t
+
1
,
a
;
θ
t
)
;
θ
t
−
)
Y_t^{DoubleDQN}=R_{t+1}+\gamma Q(S_{t+1},\arg\max_aQ(S_{t+1},a;\theta_t);\theta_t^-)
YtDoubleDQN=Rt+1+γQ(St+1,argamaxQ(St+1,a;θt);θt−)
在实操时，它首先使用估值网络计算下一个状态
S
t
+
1
S_{t+1}
St+1 的对应各个 Action 的 Q 值，然后选取最大的那个 Q 值对应 Action 的索引，再使用目标网络选取估值网络中给定Action 索引对应的 Q 值。即用一张 Q 表来选择具有最大值的行动 a，再用另一张 Q 表来计算
Q
(
S
t
+
1
,
a
)
Q(S_{t+1},a)
Q(St+1,a) 的最大值。
Double DQN 走迷宫例子
莫烦大神的 Double DQN 只给了一个基于 gym 的例子，一开始我以为 gym 不支持 windows（目前已经部分支持了），于是就还是以走迷宫为例，自己实现了一下，下面说下碰到的几个坑。
下面只给出在 build_net 函数中的关键语句，完整的代码可以见我的 github。
with tf.variable_scope("eval_net"): # 估值网络
e1 = tf.layers.dense(self.s, 20, tf.nn.relu, kernel_initializer=w_initializer,
bias_initializer=b_initializer, name="e1") # 第1层
self.q_eval = tf.layers.dense(e1, self.n_actions, kernel_initializer=w_initializer,
bias_initializer=b_initializer, name="e2") # 第二层
# Q估计中每个状态的动作值最大的下标
action_index = tf.argmax(self.q_eval,axis=1,output_type = tf.int32)
with tf.variable_scope("q_target"):
# 下面的语句不可换为：self.q_next.shape[0]，因为该语句是静态获取shape
row=tf.range(tf.shape(self.q_next)[0])
pos = tf.stack([row,action_index],axis=1)
'''
tf.gather(data,indices,axis): 在data张量的axis对应的轴中，按照下标数组
indices选取元素。
tf.gather_nd(data,indices): 在data张量中，按照下标数组indices选取元素，
其中indices是data的前几个维度。
'''
val = tf.gather_nd(params=self.q_next,indices=pos)
q_target = self.r + self.gamma * val # Q 现实
self.q_target = tf.stop_gradient(q_target) # 对 q_target的反向传播进行截断
其实思想很简单，就是找到估值网络中每个状态的动作最大值对应的下标，然后在计算 Q-target 时使用以上得到的下标。但是由于 TensorFlow 是静态定义计算图，然后再喂进数据动态进行计算的， 所以在喂数据之前张量的大小是不确定的，张量的值也是不知道的。直接使用得到的下标会出错，需要全部改成动态的过程。比如我之前是用以下方式写的，程序会报错。
q_target = self.r + self.gamma * self.q_next[row,action_index]
二、Prioritized Replay DQN
当正负奖励的样本不均衡时，需要重视那种比较少量但是值得学习的样本。所以在取一个 batch 的样本时不再采用随机采样，而是按照所有样本的优先级来采样。所谓一个样本就是一个 ( s , a , r , s ′ ) (s,a,r,s') (s,a,r,s′) 。
样本的优先级定义为 Q _ t a r g e t − Q _ e v a l u e Q\_{target} - Q\_{evalue} 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 − 当 前 节 点 左 儿 子 的 值 A=A-当前节点左儿子的值 A=A−当前节点左儿子的值。重复搜索过程直到到达叶子节点，则搜索结果落在哪个区间内，该区间对应的样本将会被采样。
举个例子，在上图中，由于优先级之和为 42，那么可以在 (0 , 42) 的范围内随机生成一个整数，比如生成的数是 24，那么从根节点开始 24 先于根节点的左儿子对应的数值 29 比较，明显 24<29，应该在根节点的左子树中搜索，然后再与值为 29 的节点的左儿子 13 比较，因为 24>13，所以应该在右子树中搜索，同时将搜索值更新为 24 − 13 = 11 24-13=11 24−13=11，不断搜索，最终落在第 3 个叶子节点对应的样本中，于是将对该样本进行采样。
上面是对一个样本根据优先级进行随机采样，如果是采样 n 个样本呢？可以先将总优先级平均分为 n 个区间，然后在每个区间各产生一个随机数，再进行上述采样。
在更新时，不仅要更新样本的值，而且要更新 SumTree 中该样本以及该样本的祖先节点的优先级。因为 SumTree 是一棵完全二叉树，所以可以用数组表示 SumTree，如果一个节点的下标为 i，则其左右儿子节点的下标分别为 2 × i 2\times i 2×i 和 2 × i + 1 2\times i +1 2×i+1，这样要寻找一个节点的祖先节点就比较方便了。另外还需要一个数组来存储样本的值。
最后来思考一个问题，numpy 中提供了一个 np.random.choice() 函数，这个函数也可以实现按照概率从数组中随机取数，那么为什么不直接用它呢？原因很简单，这个函数的复杂度太高了，不过我没有在网上找到它的复杂度到底是多少，有知道小伙伴还请告知。
因为使用优先级采样的方式改变了样本的分布，所以会产生误差，为了消除偏差，使用了重要性采样（Importance Sampling）的方法，也就是让原来的损失函数变为：
L
(
θ
)
=
E
[
I
S
W
e
i
g
h
t
s
×
(
Q
_
t
a
r
g
e
t
−
Q
_
e
v
a
l
u
e
)
2
]
L(\theta)=E[ISWeights\times(Q\_target-Q\_evalue)^2]
L(θ)=E[ISWeights×(Q_target−Q_evalue)2]
ISWeights 就是下面会提到的重要性权重。
Importance sampling（重要性采样）：
E
x
∼
p
[
f
(
x
)
]
=
∫
f
(
x
)
p
(
x
)
d
x
=
∫
f
(
x
)
p
(
x
)
q
(
x
)
q
(
x
)
d
x
=
E
x
∼
q
[
f
(
x
)
p
(
x
)
q
(
x
)
]
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)}]
Ex∼p[f(x)]=∫f(x)p(x)dx=∫f(x)q(x)p(x)q(x)dx=Ex∼q[f(x)q(x)p(x)]
当只能从 q(x) 分布得到样本时，可以做以上变换来计算 p(x) 分布的期望，其中
p
(
x
)
q
(
x
)
\frac{p(x)}{q(x)}
q(x)p(x) 被称为重要性权重。
重要性采样的一个问题就是：两个分布之间的差别不能太大，否则方差会出现较大差别。
方差公式：
V
a
r
[
x
]
=
E
[
x
2
]
−
(
E
[
x
]
)
2
Var[x]=E[x^2]-(E[x])^2
Var[x]=E[x2]−(E[x])2
上面已经推出两个分布的期望相等：
E
x
∼
p
[
f
(
x
)
]
=
E
x
∼
q
[
f
(
x
)
p
(
x
)
q
(
x
)
]
E_{x\sim p}[f(x)]=E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]
Ex∼p[f(x)]=Ex∼q[f(x)q(x)p(x)]
两个分布的方差：
V
a
r
x
∼
p
[
f
(
x
)
]
=
E
x
∼
p
[
f
(
x
)
2
]
−
(
E
x
∼
p
[
f
(
x
)
]
)
2
Var_{x\sim p}[f(x)]=E_{x\sim p}[f(x)^2]-(E_{x\sim p}[f(x)])^2
Varx∼p[f(x)]=Ex∼p[f(x)2]−(Ex∼p[f(x)])2
V a r x ∼ q [ f ( x ) p ( x ) q ( x ) ] = E x ∼ q [ ( f ( x ) p ( x ) q ( x ) ) 2 ] − ( E x ∼ q [ f ( x ) p ( x ) q ( 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 Varx∼q[f(x)q(x)p(x)]=Ex∼q[(f(x)q(x)p(x))2]−(Ex∼q[f(x)q(x)p(x)])2
= E x ∼ p [ ( f ( x ) 2 p ( x ) q ( x ) ) ] − ( E x ∼ p [ f ( x ) ] ) 2 =E_{x\sim p}[(f(x)^2\frac{p(x)}{q(x)})]-(E_{x\sim p}[f(x)])^2 =Ex∼p[(f(x)2q(x)p(x))]−(Ex∼p[f(x)])2
这样就得到了两者方差之间的关系。最后一个等式成立的原因是分布 q 和 p 的期望相等，并且因为：
E
x
∼
q
[
(
f
(
x
)
p
(
x
)
q
(
x
)
)
2
]
=
∫
f
2
(
x
)
p
2
(
x
)
q
2
(
x
)
⋅
q
(
x
)
d
x
=
∫
f
2
(
x
)
p
2
(
x
)
q
(
x
)
d
x
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
Ex∼q[(f(x)q(x)p(x))2]=∫f2(x)q2(x)p2(x)⋅q(x)dx=∫f2(x)q(x)p2(x)dx
= ∫ f 2 ( x ) p ( x ) q ( x ) ⋅ p ( x ) d x = E x ∼ p [ ( f ( x ) 2 p ( x ) q ( x ) ) ] =\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)})] =∫f2(x)q(x)p(x)⋅p(x)dx=Ex∼p[(f(x)2q(x)p(x))]
根据重要性采样的思想（
E
x
∼
p
[
f
(
x
)
]
=
E
x
∼
q
[
f
(
x
)
p
(
x
)
q
(
x
)
]
E_{x\sim p}[f(x)]=E_{x\sim q}[f(x)\frac{p(x)}{q(x)}]
Ex∼p[f(x)]=Ex∼q[f(x)q(x)p(x)]），将 on-policy 变为 off-policy：
∇
R
ˉ
θ
=
E
τ
∼
p
θ
(
τ
)
[
R
(
τ
)
∇
log
p
θ
(
τ
)
]
=
E
τ
∼
p
θ
′
(
τ
)
[
p
θ
(
τ
)
p
θ
′
(
τ
)
R
(
τ
)
∇
log
p
θ
(
τ
)
]
\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)]
∇Rˉθ=Eτ∼pθ(τ)[R(τ)∇logpθ(τ)]=Eτ∼pθ′(τ)[pθ′(τ)pθ(τ)R(τ)∇logpθ(τ)]
三、Dueling DQN
在普通的 DQN 中，在某些状态下值函数的大小与动作无关，所以 Dueling DQN 将Q网络分成两部分。第一部分仅与状态 S 有关，与具体要采用的动作 A 无关，这部分我们叫做 价值函数 部分，记做 V ( S , w , α ) V(S,w,\alpha) V(S,w,α) 。第二部分同时与状态 S 和动作 A 有关，这部分叫做 优势函数 （Advantage Function）部分，记为 A ( S , A , w , β ) A(S,A,w,\beta) A(S,A,w,β)。V 表示静态的状态环境本身具有的价值，而 A 表示选择某个 action 带来的额外价值。
那么最终的 Q 函数可以重新表示为：
Q
(
S
,
A
,
w
,
α
,
β
)
=
V
(
S
,
w
,
α
)
+
A
(
S
,
A
,
w
,
β
)
Q(S,A,w,\alpha,\beta)=V(S,w,\alpha)+A(S,A,w,\beta)
Q(S,A,w,α,β)=V(S,w,α)+A(S,A,w,β)
其中，
w
w
w 是公共部分的网络参数，而
α
\alpha
α 是价值函数独有部分的网络参数，而
β
\beta
β 是优势函数独有部分的网络参数。
我们可以直接使用上面的价值函数的组合公式得到我们的动作价值，但是这个式子无法辨识最终输出里面
V
(
S
,
w
,
α
)
V(S,w,\alpha)
V(S,w,α) 和
A
(
S
,
A
,
w
,
β
)
A(S,A,w,\beta)
A(S,A,w,β) 各自的作用。也就是说当 Q 值一定时，V 和 A 的值可能有多种情况。为了可以体现这种可辨识性（identifiability），实际使用的组合公式如下：
Q
(
S
,
A
,
w
,
α
,
β
)
=
V
(
S
,
w
,
α
)
+
[
A
(
S
,
A
,
w
,
β
)
−
1
∣
A
∣
∑
a
′
∈
A
A
(
S
,
a
′
,
w
,
β
)
]
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(S,A,w,α,β)=V(S,w,α)+[A(S,A,w,β)−∣A∣1a′∈A∑A(S,a′,w,β)]
其实就是对优势函数部分做了中心化的处理。
减去同一状态下动作值的平均值做法的另一种解释是，网络在训练时可能为了简单而直接让 Q=A，也就是让 V=0，为了避免这个情况的发生，于是加入了该限制。这样 A 同一状态下动作值之和为 0，而 V 同一状态下动作值为 Q 同一状态下动作值的均值，两者都不可能全为 0 了。
四、其他优化方法
1. Noisy DQN
ϵ − g r e e d y \epsilon-greedy ϵ−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 中，我们通过优化神经网络的结构来优化算法。
