deepsort算法原理（DQN（deep Q-network）算法简述）
本文通过整理李宏毅老师的机器学习教程的内容 ，简要介绍深度强化学习（deep reinforcement learning）中的 DQN（deep Q-network）算法 。
李宏毅老师课程的B站链接：
李宏毅, 深度强化学习, Q-learning, basic idea
李宏毅, 深度强化学习, Q-learning, advanced tips
李宏毅, 深度强化学习, Q-learning, continuous action相关笔记：
策略梯度法（policy gradient）算法简述
近端策略优化（proximal policy optimization）算法简述
actor-critic 相关算法简述1. 基本概念
DQN 是基于价值（value-based）而非策略（policy-based）的方法 ，学习的不是策略 ，而是一个评论家（critic） 。critic 并不直接采取行为 ，而是评价行为的好坏 。
1.1 状态价值函数（state value function）
有一种 critic 叫做状态价值函数（state value function）
V
π
(
s
)
V^{\pi}(s)
Vπ(s) ，即以一个策略π
\pi
π 与环境做互动 ，当处于某一状态s
s
s 时 ，接下来直到游戏结束的累计激励的期望值 。当策略不同时 ，即使状态相同 ，得到的激励也是不一样的 ，V
π
(
s
)
V^{\pi}(s)
Vπ(s) 就不一样 。此外 ，由于无法列举所有的状态 ，因此
V
π
(
s
)
V^{\pi}(s)
Vπ(s) 实际上是一个网络 ，在训练时也就是一个回归（regression）问题 。具体地 ，衡量状态价值函数有两种不同的方法：基于蒙特卡洛的方法（Monte-Carlo based approach, MC）和基于时序差分的方法（temporal-difference approach, TD） 。
基于蒙特卡洛的方法即是让 actor 与环境做互动 ，优化目标为 ，使各状态的
V
π
(
s
)
V^{\pi}(s)
Vπ(s) 与后续累计激励G
s
G_s
Gs尽可能接近 。
但是基于蒙特卡洛的方法在每次更新网络时 ，都需要把游戏玩到结束 ，但有些游戏的时间比较长 ，因此会采用基于时序差分的方法
。该方法不需要把游戏玩到底 ，而是通过时序差分的方式 ，使相邻状态下的价值函数之差与前一状态的激励尽可能接近：
由于游戏本身可能具有随机性 ，激励即为随机变量 ，其方差会对算法效果产生影响 。基于蒙特卡洛的方法由于使用累计激励
G
s
G_s
Gs ，方差会很大；而基于时序差分的方法使用单步激励r
t
r_t
rt ，方差比较小 ，但是会遇到一个问题就是V
π
(
s
t
+
1
)
V^{\pi}(s_{t+1})
Vπ(st+1)可能估计不准 ，也会影响学习结果 。实际上 ，基于时序差分的方法比较常用 ，而基于蒙特卡洛的方法较少见 。
此外 ，两种方法产生的估计结果也可能不同 ，举例说明：
在上例中 ，当状态s
a
s_a
sa 产生s
b
s_b
sb 不是巧合时 ，即s
a
s_a
sa 影响了s
b
s_b
sb ，看到s
a
s_a
sa 之后s
b
s_b
sb 就会得不到激励 ，则基于蒙特卡洛的方法合理；而如果状态s
a
s_a
sa 产生s
b
s_b
sb 只是巧合 ，则基于时序差分的方法合理 。1.2 状态-动作价值函数（state-action value function, Q function）
另一种 critic 叫做状态-动作价值函数（state-action value function） ，也叫 Q 函数 ，即在某一状态
s
s
s 采取某一动作a
a
a ，假设一直使用同一个策略π
\pi
π ，得到的累计激励的期望值 。需要注意的是 ，对于策略
π
\pi
π 来说 ，在状态s
s
s 不一定采取动作a
a
a ，但 Q 函数可以强制其采取动作a
a
a ，而后续仍使用策略π
\pi
π 继续进行 ，即Q
π
(
s
,
a
)
Q^{\pi}(s, a)
Qπ(s,a)。具体地 ，Q 函数有两种写法：
只要有了 Q 函数 ，就可以做强化学习了 ，流程图如下：
其中：
π
′
(
s
)
=
arg
max
a
Q
π
(
s
,
a
)
\pi^{\prime}(s) = \arg \max_a Q^{\pi}(s, a)
π′(s)=argamaxQπ(s,a)所以 ，实际上并没有一个所谓的策略
π
′
\pi^{\prime}
π′ ，π
′
\pi^{\prime}
π′ 是由 Q 函数推出来的 。下面证明为什么由 Q 函数推出来的
π
′
\pi^{\prime}
π′ 比π
\pi
π 要好 。所谓的好 ，即是对所有状态而言 ，状态价值函数都更大 ，具体推导如下：
V
π
(
s
)
=
Q
π
(
s
,
π
(
s
)
)
≤
max
a
Q
π
(
s
,
a
)
=
Q
π
(
s
,
π
′
(
s
)
)
V
π
(
s
)
≤
Q
π
(
s
,
π
′
(
s
)
)
=
E
[
r
t
+
V
π
(
s
t
+
1
)
∣
s
t
=
s
,
a
t
=
π
′
(
s
t
)
]
≤
E
[
r
t
+
Q
π
(
s
t
+
1
,
π
′
(
s
t
+
1
)
)
∣
s
t
=
s
,
a
t
=
π
′
(
s
t
)
]
=
E
[
r
t
+
r
t
+
1
+
V
π
(
s
t
+
2
)
∣
.
.
.
]
≤
E
[
r
t
+
r
t
+
1
+
Q
π
(
s
t
+
2
,
π
′
(
s
t
+
2
)
)
∣
.
.
.
]
=
.
.
.
≤
V
π
′
(
s
)
V^{\pi}(s) = Q^{\pi}(s, \pi(s)) \leq \max_a Q^{\pi}(s, a) = Q^{\pi}(s, \pi^{\prime}(s)) \\ \ \\ V^{\pi}(s) \leq Q^{\pi}(s, \pi^{\prime}(s)) = E[r_t + V^{\pi}(s_{t+1}) | s_t = s, a_t = \pi^{\prime}(s_t)] \leq E[r_t + Q^{\pi}(s_{t+1}, \pi^{\prime}(s_{t+1})) | s_t = s, a_t = \pi^{\prime}(s_t)] = E[r_t + r_{t+1} + V^{\pi}(s_{t+2}) | ...] \leq E[r_t + r_{t+1} + Q^{\pi}(s_{t+2}, \pi^{\prime}(s_{t+2})) | ...] = ... \leq V^{\pi^{\prime}}(s)
Vπ(s)=Qπ(s,π(s))≤amaxQπ(s,a)=Qπ(s,π′(s))Vπ(s)≤Qπ(s,π′(s))=E[rt+Vπ(st+1)∣st=s,at=π′(st)]≤E[rt+Qπ(st+1,π′(st+1))∣st=s,at=π′(st)]=E[rt+rt+1+Vπ(st+2)∣...]≤E[rt+rt+1+Qπ(st+2,π′(st+2))∣...]=...≤Vπ′(s)1.3 训练技巧
下面介绍几个 DQN 中一定会用到的技巧 。
1.3.1 目标网络（target network）
第一个技巧是目标网络（target network） 。
根据 Q 函数：
Q
π
(
s
t
,
a
t
)
=
r
t
+
Q
π
(
s
t
+
1
,
π
(
s
t
+
1
)
)
Q^{\pi}(s_t, a_t) = r_t + Q^{\pi}(s_{t+1}, \pi(s_{t+1}))
Qπ(st,at)=rt+Qπ(st+1,π(st+1))其中 ，等号左侧是网络的输出 ，右侧是目标 ，但是由于目标中含有 Q 函数 ，因此目标一直在变 ，会给训练带来困难 。
解决办法是把其中一个 Q 网络（通常是等号右侧的目标网络）固定住 ，最小化模型输出与目标之间的均方误差（mean square error） ，当等号左侧的 Q 网络更新过几次之后 ，再用更新过的 Q 网络去替换目标网络 ，继续迭代 。如下图所示：
1.3.2 探索（exploration）
第二个技巧是探索（exploration） 。
如果在某一状态下 ，所有动作均未被采取过 ，此时采取某个动作得到了正向的激励 ，会导致后续出现此状态时只采取这个动作 ，而不去探索其他的动作：
这个问题就是探索-利用窘境（exploration-exploitation dilemma）问题 。
解决方法有两种：
ϵ
\epsilon
ϵ 贪心（epsilon greedy）和玻尔兹曼探索（Boltzmann exploration） 。ϵ
\epsilon
ϵ贪心方法如下：
玻尔兹曼探索的公式如下：
P
(
a
∣
s
)
=
e
Q
(
s
,
a
)
∑
a
e
Q
(
s
,
a
)
P(a | s) = \frac {e^{Q(s, a)}} {\sum_a e^{Q(s, a)}}
P(a∣s)=∑aeQ(s,a)eQ(s,a)该方法有点像策略梯度 ，即根据 Q 函数定一个动作的概率分布 。Q 值越大 ，采取该动作的概率越高 ，而指数运算使得概率不会为 0 ，即对于 Q 值小的动作也不代表不能尝试 。
1.3.3 经验回放（experience replay）
第三个技巧是经验回放（experience replay） ，如下图所示：
经验回放有两个好处：
其一 ，实际在做强化学习时 ，往往最耗时的步骤是与环境做互动 ，训练网络反而是比较快的（用 GPU 训练其实很快） 。用回放缓存区可以减少与环境做互动的次数 ，因为在训练时 ，经验不需要全部来自于某一个策略 。一些过去的策略所得到的经验可以放在缓存区里被使用很多次 ，这样的采样利用率是比较高效的 。
其二 ，在训练网络时 ，我们希望一个批次里面的数据越多样越好 。如果数据都是同样性质的 ，性能会比较差 。如果数据缓存区里面的经验来自于不同的策略 ，容易满足多样性 。
这里指的说明的是 ，缓存区中的经验数据 ，即便使用的策略
π
\pi
π 与当前策略不同 ，也没有影响 。原因是 ，我们每次迭代所使用的采样经验是基于一个状态 ，而不是一个轨迹（trajectory） ，所以不受 off-policy 的影响 。1.4 算法流程
2. 进阶技巧
2.1 double DQN
在原始 DQN 算法中 ，由于网络存在误差 ，被高估的动作会被反复选择 ，因此 Q 值经常被高估 。
为了解决这个问题 ，可同时使用两个网络 ，一个网络
Q
Q
Q 用于更新参数选择动作 ，另一个固定不动的网络Q
′
Q^\prime
Q′用作目标网络计算 Q 值 ，即为 double DQN：
Q
(
s
t
,
a
t
)
=
r
t
+
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！