Deep Q-Learning
Deep Q-Learning，简称 DQN
- DQN 在 Q-Learning 的基础上，添加神经网络 Q 来计算价值函数
- 网络 Q 的输入为状态向量 $\phi(S)$，输出是所有动作在该状态下的动作价值
- DQN 通过引入网络 Q 来代替原始 Q-Learning 的 Q 表；解决了Q-Learning 只能适用于离散状态空间的局限性；因此 DQN 可用来解决连续状态下离散动作的问题
DQN 算法步骤
- 随机初始化网络 $Q$ 的参数 $w$，并清空经验回放集合 $D$
- 假设时刻 $t$ 的状态为 $S_{t}$，计算状态对应的特征向量 $\phi(S_{t})$
- 特征向量 $\phi(S)$ 输入网络 $Q$，得到该状态下所有动作对应的 $Q$ 值
- 根据 $\epsilon$ -贪婪算法和上一步中的 $Q$ 值输出，选择动作 $A_{t}$
- 执行动作 $A_{t}$，得到新状态的特征向量 $\phi(S_{t+1})$ 、奖励 $R_{t+1}$ 和终止状态 $is\_end$
- 将五元组 ${\phi(S_{t}),A_{t},R_{t+1},\phi(S_{t+1}),is\_end }$ 存入经验回放集合 $D$
- 从集合 $D$ 中采样 $m$ 个样本，其中第 $j$ 个样本的五元组 ${\phi(S_j),A_j,R_j,\phi(S'_j),is\_end_j}$， 以 $\gamma$ 为衰减因子，计算样本对应的预期 Q 值： $$
y_j= \begin{cases} R_j& {is\end_j; is ;true} \\ R_j + \gamma\max\{a'}Q(\phi(S'_j),A'_j,w) & {is\end_j ;is; false} \end{cases} $$ 8. 假设损失函数为均方差损失：$Loss=\frac{1}{m}\sum\limits\{j=1}^m(y_j-Q(\phi(S_j),A_j,w))^2$；DQN 主要用采样到的 $m$ 个样本进行批量梯度反向传播，来更新网络 $Q$ 的所有参数 $w$ 9. 以 $\alpha$ 作为步长，更新价值函数 $q_{\pi}(S_{t},A_{t})=q_{\pi}(S_{t},A_{t})+\alpha \delta_{t}$ 10. 重复步骤 2~9，直到状态 $S_{t+1}$ 为终止状态，即完成一次迭代
DQN 算法总结与分析：
- DQN 算法引入了经验回放和目标网络，在实际应用时表现出色
- 为了算法较好的收敛，探索率 $\epsilon$ 需要随着迭代过程变小（前期鼓励探索）
- DQN 的价值估计依赖网络 $Q$，因此网络设计与是否收敛对 DQN 影响较大
- DQN由于对价值函数做了近似表示，因此有了解决大规模强化学习问题的能力
在 2013 年的 NIPS 研讨会上，DeepMind 团队首次展示了 DQN 强化学习算法，其通过 CNN 网络接受像素输入来玩转各种雅达利（Atari）游戏，由此拉开了深度强化学习的序幕
Nature DQN
DQN 的问题：
- DQN 依赖 Q 网络来计算目标 Q 值 $y_j=R_j + \gamma\max_{a'}Q (\phi (S'_j), A'_j, w)$
- 而 $y_j$ 又会参与损失函数的计算，并借助损失函数更新 Q 网络的参数 $w$
- 因此 $w$ 和 $y_{i}$ 之间存在循环依赖，这种强相关性不利于网络训练的收敛
Nature DQN 的改进思路：
- 使用两个 Q 网络减少目标Q值 $y_{i}$ 和更新网络参数 $w$ 之间的依赖关系
- 两个 Q 网络的结构是完全一样的，并且二者之间会定期进行参数的同步
- 第一个 Q 网络用来选择动作，更新模型参数，被称为当前网络
- 第二个 Q 网络用于计算目标Q值，被称为目标网络；目标网络不单独进行参数的更新，而是每隔一段时间从当前网络复制参数，即通过延时更新来减少目标Q值与当前Q值
Nature DQN 依然存在局限性，部分问题将在后续算法中得到修复
Double DQN
DQN 和 Nature DQN 存在的问题：
- 目标Q值的计算依赖贪婪法：$y_j=R_j + \gamma\max_{a'}Q (\phi (S'_j), A'_j, w)$
- 使用 $max$ 贪婪法能在训练前期加速 Q 值的收敛，但容易过犹不及
- 过度估计(Over Estimation)，即最终的算法模型有很大的偏差（bias）
Double DQN（简称 DDQN）的改进思路：
- 通过解耦目标 Q 值的计算和动作选择这两步，来消除过度估计问题
- 除了目标 Q 值的计算，DDQN 的算法流程和 Nature DQN 基本一致
DDQN 中目标 Q 值的计算（非终止状态 $is\end_j = false$）： $$y_j = R_j + \gamma Q'(\phi(S'_j),\arg\max\{a'}Q(\phi(S'_j),a,w),w')$$
- DDQN 会先在当前网络 $Q$ 中找到最大 $Q$ 值对应的动作 $a'$
- 然后利用这个动作 $a'$ 代入目标网络 $Q'$ 来计算目标 Q 值
其他 DQN 改进
Prioritized Replay DQN：
- DQN 和 DDQN 等模型都是通过经验回放来实现等权重的采样
- Prioritized Replay DQN 引入额外的样本权重来调整采样优先级
- 样本权重参数 $w$ 由 TD 误差 $|\delta(t)|$ 归一化得到，二者呈正比关系；TD 误差越大的样本，反向传播的作用越大，因此采样优先级更高
- 同时 Prioritized Replay DQN 的损失函数（考虑样本权重 $w$）更新如下：
$$ \frac{1}{m}\sum\limits_{j=1}^mw_j(y_j-Q(\phi(S_j),A_j,w))^2 $$
在实际应用中，Prioritized Replay DQN 引入二叉树结构来方便采样过程；而采样优先级的考虑，也使得Prioritized Replay DQN 的收敛速度高于 DQN
Dueling DQN：
- 主要通过优化神经网络结构来改善 DQN 的表现
- Dueling DQN 的神经网络可表示为： $$Q(s,a, w, \alpha, \beta) = V(s,w,\alpha) + A(s,a,w,\beta)$$
- 其中 $w$ 是公共参数，$\alpha$ 是价值函数 $V$ 的独有参数，$\beta$ 是优势函数（Advantage Function）$A$ 的独有参数；价值函数仅与状态 $s$ 有关，与动作 $a$ 无关；优势函数同时与状态 $s$ 和动作 $a$ 有关
- Dueling DQN 在网络层面对状态和价值的学习进行解耦，能够更高效地学习状态价值函数，理解不同动作的差异性，适用于动作空间较大的场景，一般实践效果优于 DQN
参考：
强化学习（八）价值函数的近似表示与 Deep Q-Learning
强化学习（九）Deep Q-Learning 进阶之 Nature DQN
强化学习（十）Double DQN (DDQN)