DQN 以及其改进
在原版Q-learning算法中，Q网络的优化目标为：
\[ Y_{t}^{\mathrm{Q}} \equiv R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a ; \boldsymbol{\theta}_{t}\right) \]
基于此优化目标建立均方误差损失函数，优化迭代式如下：
\[ \boldsymbol{\theta}_{t+1}=\boldsymbol{\theta}_{t}+\alpha\left(Y_{t}^{\mathrm{Q}}-Q\left(S_{t}, A_{t} ; \boldsymbol{\theta}_{t}\right)\right) \nabla_{\boldsymbol{\theta}_{t}} Q\left(S_{t}, A_{t} ; \boldsymbol{\theta}_{t}\right) \]
与原版（2013年）发布的Deep Q-learning算法相比，与2015年发布的Deep Q-learning算法对原版算法进行了改进。2015年的改进版本DQN有两个较为重要的特点：目标网络的使用以及经验回放池的引入。目标网络与原版网络具有相同的结构，令原版网络的参数为\(\theta_{t}\)，目标网络的参数为\(\theta_{t}^{-}\)，则改进后的DQN的优化目标为：
\[ Y_{t}^{\mathrm{DQN}} \equiv R_{t+1}+\gamma \max _{a} Q\left(S_{t+1}, a ; \boldsymbol{\theta}_{t}^{-}\right) \]
其中目标网络每\(\tau\)步从原网络复制参数，并在剩下的时间步中保持不变。
DQN算法的缺陷
上述两种Q网络的优化目标都存在一定缺陷，即使用同一个网络的value来选择和评价action。在\(Y_{t}^{\mathrm{Q}}\)中，使用原始Q网络根据max策略选择action，并使用同一个网络的值对此action进行评价；在\(Y_{t}^{\mathrm{DQN}}\)中进行的是相同的操作，只是其发生在目标Q网络中。这种情况下通常会选择过估计的value值，从而对整个网络的Q值进行过分乐观估计。为了解决上述问题，Double DQN对action选择以及评估进行了解耦，使用当前网络选择最优action，并使用目标网络计算对应value。改进后的优化目标为：
\[ Y_{t}^{\text {DoubleQ }} \equiv R_{t+1}+\gamma Q\left(S_{t+1}, \operatorname{argmax} Q\left(S_{t+1}, a ; \boldsymbol{\theta}_{t}\right) ; \boldsymbol{\theta}_{t}^{\prime}\right) \]
过优估计
首先我们有公式：
\[ E\left(\max \left(y_{1}, y_{2}, \ldots\right)\right) \geq \max \left(E\left(y_{1}, y_{2}, \ldots\right)\right) \]
直观描述为对一系列数求最大值再求平均通常比先求平均值再求最大值要大。
由于Q-learning算法通常以拟合Bellman最优函数为目标：
\[ Q_{\pi}(s, a)=R(s, a)+\gamma \mathbb{E}_{s^{\prime} \sim p(s, a)}\left[\max _{a^{\prime}} Q_{\pi}\left(s^{\prime}, a^{\prime}\right)\right] \]
但理想情况下\(Q_{\pi}(s, a)\)的值应该等同于下式：
\[ Q_{\pi}(s, a) = \mathbb{E}(R(s, a)) + \gamma \mathbb{E}_{s^{\prime} \sim p(s, a)}\left[\max_{a^{\prime} \sim \pi} \mathbb{E}[Q_{\pi}\left(s^{\prime}, a^{\prime}\right)]\right] \]
即理想情况下应该先求出对于可能出现的状态\(s^{\prime}\)以及可能的动作\(a^{\prime}\)的Q值的期望，再对期望求最大值并根据\(s^{\prime}\)出现的概率求总期望。根据上面的不等式有：
\[ \mathbb{E}[\max _{a^{\prime}} Q_{\pi}\left(s^{\prime}, a^{\prime}\right)] \geq \max_{a^{\prime} \sim \pi} \mathbb{E}[Q_{\pi}\left(s^{\prime}, a^{\prime}\right)] \]
因此Q-learning对于最优函数的拟合总会出现乐观估计。
算法流程
参考Pinard的博客。
具体Python实现参考我的github。