多智能体强化学习第一篇—Deep Q-learning
Q-learning 算法
强化学习问题一般以马尔可夫过程为问题背景，将问题建模为(
S
,
A
,
P
,
r
,
γ
S,A,P,r,\gamma
S,A,P,r,γ) 形式，其中
S
S
S为状态空间，
A
A
A为动作空间，
P
P
P为状态转移函数，
r
r
r为收益函数。agent通过在某个状态选择某个动作与环境进行交互，使得环境发生动态演变，agent可以获取相应的收益。强化学习问题的目标就是找到一组最优的动作序列
π
\pi
π，使得agent得到的最终收益最大。
一种很自然的想法便是，对于特定的一个状态，我给定每一个动作一个值去表示该动作的价值，那么在状态推演的过程中，我在每一次的状态上都选择价值最大的动作，那么在整个的推演过程中所获得的最终收益就会最大，这变产生的value-base的学派，该学派以价值函数为关键点，用Q函数来表示状态-动作价值，即
Q
π
(
s
,
a
)
Q_\pi(s,a)
Qπ(s,a)表示策略
π
\pi
π在状态s时动作a的价值。
因为强化学习的目标是最大化收益函数，并且马尔可夫过程是一个动态推演过程，设计到时序的问题，所以有两个公式可以作为收益函数的表示方法。以有限时间步长为例，一种表示形式是平均收益奖励函数,即
R
π
=
E
[
r
1
+
r
2
+
⋯
+
r
T
T
∣
π
]
R_\pi=E[\frac{r_1+r_2+\cdots+r_T}{T}|\pi]
Rπ=E[Tr1+r2+⋯+rT∣π],另一种是带有折扣因子的奖励函数,即
R
π
=
E
[
r
1
+
γ
r
2
+
γ
2
r
3
+
⋯
+
γ
T
−
1
r
T
∣
π
]
R_\pi=E[r_1+\gamma r_2 + \gamma ^{2}r_3+\cdots+\gamma^{T-1}r_T|\pi]
Rπ=E[r1+γr2+γ2r3+⋯+γT−1rT∣π],其中折扣因子的存在有两个作用，一是为了更加看重当前收益，降低未来收益的重要性，二是为了当T趋于无穷大时，收益函数保持收敛。由马尔可夫控制动态理论，最大化全程收益等价于最大化每一个时刻后的收益，所以动作价值函数定义为
Q
π
(
s
t
,
a
t
)
=
E
[
r
t
+
1
+
γ
r
t
+
2
+
⋯
+
γ
T
−
t
−
1
r
T
∣
π
]
Q_\pi(s_t,a_t)=E[r_{t+1}+\gamma r_{t+2}+\cdots+\gamma ^{T-t-1}r_{T}|\pi]
Qπ(st,at)=E[rt+1+γrt+2+⋯+γT−t−1rT∣π]。
Q-learning是一种model-free的方法，动态迭代的方法使得
Q
t
Q_t
Qt逐步趋近于
Q
∗
Q^*
Q∗，迭代公式为
Q
t
+
1
(
s
t
,
a
t
)
=
Q
t
(
s
t
,
a
t
)
+
α
(
r
t
+
1
+
γ
Q
t
(
s
t
+
1
,
a
t
+
1
)
−
Q
t
(
s
t
,
a
t
)
)
Q_{t+1}(s_t,a_t) = Q_t(s_t,a_t)+\alpha(r_{t+1}+\gamma Q_t(s_{t+1},a_{t+1})-Q_t(s_t,a_t))
Qt+1(st,at)=Qt(st,at)+α(rt+1+γQt(st+1,at+1)−Qt(st,at))
其中
α
\alpha
α为学习率。
Q-learning算法的收敛性已被证明。随着t的不断增大，最终
Q
t
(
s
t
,
a
t
)
Q_t(s_t,a_t)
Qt(st,at)会收敛到最优状态-动作价值函数
Q
∗
(
s
t
,
a
t
)
Q^*(s_t,a_t)
Q∗(st,at)。其中
Q
∗
(
s
t
,
a
t
)
=
m
a
x
π
Q
π
(
s
t
,
a
t
)
Q^*(s_t,a_t)=max_\pi Q_\pi(s_t,a_t)
Q∗(st,at)=maxπQπ(st,at)满足贝尔曼方程：
Q
∗
(
s
t
,
a
t
)
=
E
[
r
t
+
1
+
σ
Q
∗
(
s
t
+
1
,
a
t
+
1
)
]
Q^*(s_t,a_t)=E[r_{t+1}+\sigma Q^*(s_{t+1},a_{t+1})]
Q∗(st,at)=E[rt+1+σQ∗(st+1,at+1)]
Q
∗
Q^*
Q∗对应的最优策略记为
π
∗
\pi^*
π∗。
通常使用Q-learning算法的方法是建立一个Q表格，以状态为纵索引，以动作为索引。Q表格用来存储状态-动作价值，每一次迭代便对表格内的内容进行更新，Q-learning算法的局限性便由此产生，当状态空间和动作空间过于庞大时，表格所占据的内存便会很大，并且遍历表格需要更大的复杂度，如果每一个状态的动作集合不同，那么表格中也会存储很多无效值，造成内存的浪费。深度Q-learning算法会很好的解决这个问题。
Deep Q-learning算法
Deep Q-learning算法用神经网络拟合状态-动作价值函数，可以实现端对端的训练。
Deep Q-learnig的拥有两个网络结构，一个是用来训练的预测网络
Q
(
s
,
a
;
θ
)
Q(s,a;\theta)
Q(s,a;θ),一个是用来拟合真实值的目标网络
Q
(
s
,
a
;
θ
^
)
Q(s,a;\hat{\theta})
Q(s,a;θ^),利用
L
(
θ
)
=
E
[
(
r
t
+
1
+
σ
Q
(
s
t
+
1
,
a
t
+
1
;
θ
^
)
−
Q
(
s
t
,
a
t
)
)
2
]
L(\theta)=E[(r_{t+1}+\sigma Q(s_{t+1},a_{t+1};\hat{\theta}) - Q(s_t,a_t))^2]
L(θ)=E[(rt+1+σQ(st+1,at+1;θ^)−Q(st,at))2]作为优化函数对网络进行反向传播进行训练。下图为DQN网络的代码结构：
Deep Q-learning有如下两个创新点：
一 replay buffer网络使用一个buffer存储agent与环境的交互样本，在训练时，随机从buffer中采样，这样的优点有：1.可以提高样本的利用率 2.可以避免样本之间的强相关性，因为深度学习的训练要求样本集是独立同分布的，而强化学习的样本具有强烈的时序性，所以将样本数据放在buffer中进行打乱采样，可以对网络进行有效的训练
二 target network 上面说到DQN有两个网络架构：预测网络和目标网络，因为深度学习的训练要求label是固定不变的，所以在DQN中要求目标网络的参数更新速度慢于预测网络，通常几十个epoch才更新一次target network，这样才会使得网络的训练更加稳定。