强化学习（值函数近似）

本文首先介绍了值函数近似（Value Approximation），然后分别结合 SARSA 和 Q-Learning 给出了两种 Q 函数近似的方法。通过分析线性函数作为估计函数的局限性，自然引入神经网络来进行非线性函数近似，引出了基于深度学习的 Q 函数估计网络：Deep Q-Network（DQN）。

1. 引言
2. 状态价值函数近似
3. 状态动作价值函数近似
- 3.1. SARSA 值函数近似
- 3.2. Q-Learning 值函数近似
4. Deep Q-Learning（DQN）

1. 引言

前面介绍的 TD 算法都仅针对对离散的（表格形式的）状态和动作进行研究，但实际应用中的场景可能会很复杂，很难定义出离散的状态；即使能够定义，数量也非常大，无法用数组存储。

对于强化学习来说，很多实际应用问题的输入数据是高维的，如图像，声音，算法要根据它们来选择一个动作执行以达到某一预期的目标。比如，对于自动驾驶算法，要根据当前的画面决定汽车的行驶方向和速度。经典的强化学习算法如 Q-Learning 需要列举出所有可能的情况（称为状态，这是对当前所处环境的抽象），然后进行迭代。 Q-Learning 的经典实现是列举出所有的状态和动作，构建 Q-Table，这是一个二维的表，然后迭代计算各种状态下执行各种动作的预期回报的最大值。对于高维的输入数据，显然是不现实的，因为如果直接以原始数据作为状态，维数太高，而且状态数量太多。

另一种方案是用一个函数来逼近价值函数，函数的输入是原始的状态数据，函数的输出是价值函数值。在有监督学习中，我们用神经网络来拟合分类或回归函数，因此当然也可以用神经网络可来拟合强化学习中的价值函数。

2. 状态价值函数近似

给定策略 $\pi$，假设 $v_\pi(s)$ 和 $\hat{v}_\pi(s,w)$ 分别为状态 $s$ 的价值函数与其函数估计。我们的目标是找到最优的参数 $w$，使得在任意状态 $s$ 下，状态价值函数的估计 $\hat{v}(s,w)$ 都接近其真实值。

这本质上是一个策略估计问题，具体可分为以下两步：

定义目标函数；
找到合适的算法优化这个目标函数；
确定状态价值函数的估计 $\hat{v}(s,w)$ 的具体实现方式（线性？非线性？神经网络？）。

2.1. 目标函数

很显然，我们希望所有状态的状态价值函数的估计 $\hat{v}(s,w)$ 接近其真实值，这是一种距离度量，那么目标函数设计为

\[J(w) = \mathbb{E}_{\mathcal{S}}[(v_\pi(s)-\hat{v}(s,w))^2] = \Vert v_\pi - \hat{v} \Vert^2_D\]

$D$ 为状态的分布 $D_\pi$，则上式还可写为 $(v_\pi - \hat{v})^\top D (v_\pi - \hat{v})$

下面讨论如何采取合适的近似方法消除期望符号。

一种直觉方法是对所有状态进行平均。如果我们认为所有状态的权重都相同，那么采用 均匀分布（uniform distribution）进行加权，目标函数可以改写为

\[J(w) =\textcolor{red}{\frac{1}{\vert\mathcal{S}\vert}}\sum_{s\in\mathcal{S}} (v_\pi(s)-\hat{v}(s,w))^2\]

但在强化学习中，很明显状态的重要性是不一样的，比如 Grid World 场景中的终点状态和靠近终点的状态显然更加重要，而远离终点的某些状态可能没那么重要。因此，我们需要采用 平稳分布（stationary distribution）进行加权，目标函数改写为

\[J(w) = \sum_{s\in\mathcal{S}} \textcolor{red}{d_\pi(s)} (v_\pi(s)-\hat{v}(s,w))^2\]

其中，

$d_\pi(s)$ 为策略 $\pi$ 下马尔可夫过程的平稳分布，其定义为 $d_\pi(s)\geq 0,\; \sum_{s\in\mathcal{S}}d_\pi(s) = 1$；
- 平稳分布刻画了马尔可夫过程长期迭代后，各个状态出现的（被访问的）概率；
- 平稳分布描述了马尔可夫过程的长期行为（long-run behaviour）；
- 马尔可夫链可能存在唯一平稳分布，无穷多个平稳分布，或不存在平稳分布；
上述目标函数是一个带权重的均方误差，某个状态的出现概率越大，其误差的权重越大。

根据上述定义，策略 $\pi$ 下经过长马尔可夫采样回合后，假设状态 $s$ 被采样到了 $n_\pi(s)$ 次，平稳分布可由下式估计

\[d_\pi(s) \approx \frac{n_\pi(s)}{\sum_{s^\prime\in\mathcal{S}}n_\pi(s^\prime)}\]

从其经过长期状态转移后的不变性的角度考虑，已知状态转移矩阵 $P_\pi = p(s^\prime \vert s, a)$，平稳分布必然满足如下等式

\[d_\pi^T = d_\pi^T P_\pi\]

也即，平稳分布就是状态转移矩阵特征值为 1 的特征向量。

2.2. 优化算法

由于我们希望最小化上述目标函数，很自然想到使用 梯度下降法

\[w_{k+1} = w_k - \alpha_w \nabla J(w_k)\]

其中梯度为

\[\begin{aligned} \nabla_w J(w) &= \nabla_w\mathbb{E}[(v_\pi(s)-\hat{v}(s,w))^2]\\ &= \mathbb{E}[\nabla_w(v_\pi(s)-\hat{v}(s,w))^2]\\ &= -2\mathbb{E}[(v_\pi(s)-\hat{v}(s,w))\nabla_w\hat{v}(s,w)] \end{aligned}\]

为了避免在真实梯度计算中计算期望，很自然想到采用随机梯度代替真实梯度，即

\[\begin{aligned} w_{t+1} &= w_t + 2\alpha_t\mathbb{E}[(v_\pi(s)-\hat{v}(s,w))\nabla_w\hat{v}(s,w)]\\ \Rightarrow w_{t+1} &= w_t + 2\alpha_t(v_\pi(s_t)-\hat{v}(s_t,w_t))\nabla_w\hat{v}(s_t,w_t) \end{aligned}\]

注意到，实际使用中，上述梯度下降迭代式要求状态价值函数 $v_\pi(s_t)$ 已知，但我们本身就是在做状态价值函数估计，所以肯定不可能提前知道其真值。因此，我们需要将其替换为某种估算形式，具体方式包括：

采用 MC 的方式迭代优化，被称为 MC with Value Approximation：
\[w_{t+1} = w_t + 2\alpha_t(\textcolor{red}{G_t}-\hat{v}(s_t,w_t))\nabla_w\hat{v}(s_t,w_t)\]
采用 TD 的方式迭代优化，被称为 TD with Value Approximation：
\[w_{t+1} = w_t + 2\alpha_t[\textcolor{red}{r_{t+1}+\gamma \hat{v}_\pi(s_{t+1},w_t)}-\hat{v}(s_t,w_t)]\nabla_w\hat{v}(s_t,w_t)\]

严格来说，采用 TD 的方式迭代优化后，求解的问题不再是原始目标（称其为 True Value Error）函数的最小化，而是优化 Projected Bellman Error。此处不再展开，可参考《Mathmatical Foundations of Reinforcement Learning》。

2.3. 估计函数设计

2.3.1. 采用线性函数

早期广泛使用线性函数作为状态值函数的估计方法

\[\hat{v}(s,w) = aw_1+w_2 = \underbrace{[s,1]}_{\phi^\top(s)} \underbrace{\begin{bmatrix} w_1\\w_2 \end{bmatrix}}_{w}= \phi^\top(s)w\]

可以看出，$\hat{v}(s,w)$ 是关于 $w$ 的线性函数，$\phi(s)$ 是特征向量，可以是一组多项式基、傅里叶基、…等等，但合适的基比较难选择。

从模式识别的角度，这里的线性函数本质上是设计一组能够反应状态价值函数特征的向量，且维数要小于原始状态价值函数的维数，后面的实例可以更好的反映这一点。

线性函数估计的梯度为

\[\nabla_w \hat{v}(s,w) = \nabla_w [\phi^\top(s)w] = \phi(s)\]

将上述两式代入前述 TD 形式的迭代优化式中，有

\[w_{t+1} = w_t + \alpha_t[r_{t+1}+\gamma \textcolor{red}{\phi^\top(s_{t+1})w_t}-\textcolor{red}{\phi^\top(s_t)w_t}] \textcolor{red}{\phi(s_t)}\]

上述迭代式可被称为 TD-Linear。

更加特殊的情况下，我们选择如下线性函数

\[\phi(s) = e_s\in\mathbb{R}^{\vert S \vert}\]

其中 $e_s$ 是一个第 $s$ 个分量为 1，其余分量为 0 的向量（也即独热向量），那么

\[\hat{v}(s,w) = e_s^\top w = w(s)\]

就相当于取到 $w$ 的第 $s$ 个分量用来对 $v_\pi(s)$ 进行估计。将其代入 TD-Linear 有

\[w_{t+1} = w_k + \alpha_k[r_{t+1}+\gamma \textcolor{red}{w(s_{t+1})}-\textcolor{red}{w(s_t)}] \textcolor{red}{e_{s_t}}\]

注意到 $e_{s_t}$ 是一个第 $s_t$ 个分量为 1，其余分量为 0 的向量，那么上面的向量等式中，只有分量为 1 的那个（行）等式有意义，把这行提取出来有

\[w_{t+1}(s_t) = w_t(s_t) + \alpha_t[r_{t+1}+\gamma w_t(s_{t+1}) - w_t(s_t)]\]

可以看出，只要把 $w$ 换成 $v$，上式与前述 TD 方法的迭代式一模一样。也就是说，（对表格性任务而言）TD 方法与采用独热函数的值函数估计等价。

2.3.2. 线性函数实例分析

下面通过一个 Grid World 实例来表明，采用线性函数估计能够降低状态价值函数估计的参数个数。在实例中，采取均匀随机分布的策略 $\pi(a\vert s) = 0.2,\forall s,a$，我们对所有 25 个状态的价值函数进行估计，本质是一个策略评估过程。实例中用到的参数为 $r_{\text{forbidden}}=r_{\text{boundary}}=-1,r_{\text{target}}=1, \gamma = 0.9$。

我们首先使用动态规划方法，得到在该策略下，每个状态的真实最优状态价值函数，如图所示。中间子图表明了二维情况下的各个状态价值函数，右侧子图则将其形象展示到了三维空间中：

接着我们采用线性函数进行价函数估计，通用实验设置如下：

采样 500 个 episodes；
每个 episode 包含 500 步，初始状态-动作均匀随机选取；

下面开始实验：

采用独热函数的值函数估计（Tabular TD）

可以看出，随着迭代次数逐渐增加，价值函数估计值与真实值间的均方根误差收敛（右侧子图），估计结果（中间子图）逐渐逼近真实值（左侧子图）。

独热函数本质上是采用与状态个数同阶的线性函数估计，因此当然能够逼近最优值。
采用三阶线性函数的值函数估计

注意到该实例中状态可以坐标形式给出：$s={x,y}$，那么设计线性函数为
\[\phi(s) = [1, x, y]^\top \in \mathbb{R}^3\]
则状态价值函数估计值为一个平面
\[\hat{v}(s,w) = \phi^\top(s)w = [1,x,y]\begin{bmatrix} w_1\\w_2\\w_3 \end{bmatrix} = w_1+w_2x+w_3y\]
最终结果为

可以看出，收敛后价值函数估计值与真实值间的均方根误差存在一个常值偏差（右侧子图），估计结果（中间子图）的趋势和真实值（左侧子图）相同，但因为本质上是用一个平面估计非平面，因此近似能力有限，必然存在误差。
采用高阶性函数的值函数估计

采用
\[\begin{aligned} \phi(s) &= [1,x,y,x^2,y^2,xy]^\top\in\mathbb{R}^6\\ \phi(s) &= [1,x,y,x^2,y^2,xy,x^3,y^3,x^2y,xy^2,]^\top\in\mathbb{R}^{10} \end{aligned}\]
则状态价值函数估计值为一个二次/三次曲面，最终结果为

二次曲面：

三次曲面：

可以看出，随着参数个数的增多，其曲面的拟合能力越好。同时也注意到，即使继续增加阶数也不一定能保证完全消除估计误差，因为线性函数结构本身能力存在限制，这也是为什么如今更加广泛采用神经网络来估计值函数，因为神经网络从理论上来说可以近似任意一个非线性函数。

2.3.3. 采用神经网络

目前被广泛使用的是神经网络作为一个非线性估计函数，其输入为状态 $s$，输出为 $\hat{v}(s,w)$，其中 $w$ 是神经网络的权重参数。关于神经网络估计函数这里不再展开介绍，后续对状态-动作价值函数进行估计时会详细介绍。

3. 状态动作价值函数近似

前面介绍 TD 方法时，我们首先以状态价值函数（V 函数）为例引入了基本的 TD 思想，然后将其推广至状态动作价值函数（Q 函数），并结合不同的策略改进方法，分别得到 SARSA 和 Q-Learning 两种具体的时序差分方法。

这一节我们将采用类似的思想，将前述介绍的状态价值函数近似的基本思想，分别与 SARSA 和 Q-Learning 结合。

3.1. SARSA 值函数近似

直接将状态价值函数近似的梯度下降迭代式中的 $v$ 替换为 $q$ 我们就得到

\[w_{t+1} = w_t + \alpha_t[r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1};w_t)-\hat{q}(s_t,a_t;w_t)]\nabla_w\hat{q}(s_t,a_t;w_t)\]

结合策略改进算法，形成伪代码如下：

Initialize $Q(s,a)$ arbitrarily, choose start state $s$, given a behaviour policy $\pi_t$ (e.g., $\varepsilon$-greedy)
Repeat (for each episode)
- Repeat (if current $s_t$ is not terminal state)
  - collect experience:
    - choose action $a_t$ at $s_t$ following $\pi_t(s_t)$
    - Take action $a$, get $r$, transfer to $s_{t+1}$
    - choose action $a_{t+1}$ at $s_{t+1}$ following $\pi_t(s_{t+1})$
  - parameter update:
    - $w_{t+1} = w_t + \alpha_t[r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1};w_t)-\hat{q}(s_t,a_t;w_t)]\nabla_w\hat{q}(s_t,a_t;w_t)$
    - ${s_t\leftarrow}s_{t+1}; a_t\leftarrow a_{t+1}$
  - policy improvement:
    - (update same $\varepsilon$-greedy as target policy)
    - $\pi_{t+1}(a\vert s) = 1-\frac{\varepsilon}{\vert \mathcal{A} \vert}(\mathcal{A}-1)$ if $a=\arg\max_a \textcolor{red}{\hat{q}(s,a;w_t)}$
    - $\pi_{t+1}(a\vert s) = \frac{\varepsilon}{\vert \mathcal{A} \vert}$ otherwise
    - $t \leftarrow t+1$

上述伪代码中标红部分即为 SARSA 值函数近似方法，与传统 SARSA 方法不同的地方。

设计一个采用 5 阶傅里叶基函数函数的 SARSA 值函数近似方法，在 Grid World 实例下的训练结果。其中实例设置为： $r_{\text{boundary}}=r_{\text{forbidden}}=-10,r_{\text{target}}=1,\alpha=0.001,\gamma=0.9$。从左上角初始状态出发，迭代500步，结果如下图所示

3.2. Q-Learning 值函数近似

同样直接将状态价值函数近似的梯度下降迭代式中的 $v$ 替换为 $q$ 我们就得到

\[w_{t+1} = w_t + \alpha_t[r_{t+1}+\gamma \textcolor{red}{\max_{a\in\mathcal{A}(s_{t+1})}}\hat{q}(s_{t+1},a;w_t)-\hat{q}(s_t,a_t;w_t)]\nabla_w\hat{q}(s_t,a_t;w_t)\]

结合策略改进算法，形成伪代码如下（注意其策略评估迭代式并没有直接照搬上面的式子，而是将取最大 $q$ 函数部分放到经验采集环节）：

Initialize $Q(s,a)$ arbitrarily, choose start state $s$, given a behaviour policy $\pi_b$ (e.g., $\varepsilon$-greedy, uniform, human, etc)
Repeat (for each episode):
- Repeat (if $s$ is not terminal state):
  - collect experience:
    - choose action $a_t$ at $s_t$ following $\pi_t(s_t)$
    - Take action $a$, get $r$, transfer to $s_{t+1}$
    - choose $a_{t+1}= \arg\max_a \textcolor{red}{\hat{q}(s_{t+1}, a;w_t)}$
  - parameter update:
    - $w_{t+1} = w_t + \alpha_t[r_{t+1}+\gamma \hat{q}(s_{t+1},a_{t+1};w_t)-\hat{q}(s_t,a_t;w_t)]\nabla_w\hat{q}(s_t,a_t;w_t)$
  - policy improvement:
    - (update greedy policy as target policy)
    - $\pi_{t+1}(a\vert s) = 1$ if $a=\arg\max_a \textcolor{red}{\hat{q}(s,a;w_t)}$
    - $\pi_{t+1}(a\vert s) = 0$ otherwise
    - ${s\leftarrow}s^\prime; a\leftarrow a^\prime$
  - $t \leftarrow t+1$

上述伪代码中标红部分即为 Q-Learning 值函数近似方法，与传统 Q-Learning 方法不同的地方。

设计一个采用 5 阶傅里叶基函数的 Q-Learning 值函数近似方法（采样 on-policy 而不是上面介绍的 off-policy 版本），在 Grid World 实例下的训练结果。其中实例设置为： $r_{\text{boundary}}=r_{\text{forbidden}}=-10,r_{\text{target}}=1,\alpha=0.001,\gamma=0.9$。从左上角初始状态出发，迭代500步，结果如下图所示

可以看出，即使采用 on-policy 的 Q-Learning 也比 SARSA 更激进，收敛速度更快（因为里面的第二次动作采样使用 greedy 策略）。

4. Deep Q-Learning（DQN）

前面我们使用线性函数来做值函数近似，其本质是从高维数据中抽象出特征，作为状态，然后用强化学习建模，但这种做法很大程度上依赖于人工特征的设计（也即线性函数基的选取）。

因此，更加广泛的做法是使用一个非线性函数——乃至神经网络——来做值函数近似。Deep Q-Learning（原文称为 Deep Q-Network，DQN）就是源于上述思想，它也是强化学习领域最早且最成功将深度神经网络引入强化学习的尝试之一。

DQN 由DeepMind公司在2013年提出，2015年其改进型发表在Nature上。这种方法用卷积神经网络拟合价值函数，一般是Q函数。网络的输入为原始场景数据，如游戏的画面图像，输出为在这种场景下执行各种动作时所能得到的Q函数的极大值。

如果使用一个神经网络来做值函数近似，可以有以下两种形式：

       +----+ ---->Q(s,a1)  |         +----+
s ---> |f(θ)| ---->Q(s,a2)  |   s --->|f(θ)| ---->Q(s,ai)
       |    | ---->...      |  ai---> |    | 
       +----+ ---->Q(s,an)  |         +----+

那么应该采取哪种网络形式呢？

上面两种形式都可能出现，但一般而言，DQN 采用左边形式。因为：

左边形式：
- DQN 需要找到 $\max_a q(s,a)$，左边输入一次就能得到所有动作的价值，而右边输入则需要多次输入，增加了计算复杂度；
- 强化学习问题可能包含大量的动作选项。将动作作为网络输入会使网络的复杂度急剧增加，不利于训练和收敛。相反，通过仅输入状态，网络可以更专注地学习状态与价值之间的关系，而不必考虑如何直接处理动作空间的复杂性。
右边形式：
- 有时候，将动作作为网络输入是有必要的，比如在某些连续动作空间中，动作空间的维度可能比状态空间的维度还要高。

4.1. 损失函数

神经网络的损失函数用 Q-Learning 的 TD Error 构造，是神经网络的输出值与 Q 函数一步估计值之间的误差

\[L(\theta) = \mathbb{E}[(r+\gamma \mathop{\text{max}}\limits_{a^\prime} q(s^\prime,a^\prime;\textcolor{red}{\theta})-q(s,a;\textcolor{red}{\theta}))^2]\]

这个损失函数之所以能够成立的原因，是因为其本质上是在求解 $Q$ 函数形式的贝尔曼最优方程（前述马尔可夫决策4.7章节有过介绍）

\[q(s,a) = \mathbb{E}[R_{t+1}+\gamma \max_a q(s_{t+1},a)\vert s,a], \forall s,a\]

那么在期望形势下，上面的损失函数自然应该趋向于零。

4.2. 优化方法

神经网络的损失函数自然该采用梯度下降法求解，梯度下降要计算损失函数的梯度，但注意到，损失函数中有两项都包含网络参数 $\theta$，其中 TD Target 含参部分还含有求最大值操作，这个梯度求解比较困难，因此引出第一个技巧：分离拷贝。

另一方面，和 Q-Learning 类似，DQN 通过执行动作来生成经验数据 $S_t, A_t, R_{t+1},S_{t+1}$ 作为样本来进行训练的。具体而言，给定一个状态，用当前的神经网络进行预测，得到所有动作的 Q 函数，然后按照策略选择一个动作执行，得到下一个状态以及回报值，以此构造训练样本。

从监督学习的角度，一般要求训练样本之间是相互独立的，但在强化学习中，一次采样得到的序列中，取出的经验数据是前后高度相关。为了解决训练样本之间存在相关性，DQN 采用了经验回放机制。

下面分别介绍上述两个技巧。

4.2.1. 分离拷贝

分离拷贝指的是在求损失函数梯度的过程中，短时间内冻结 TD Target 中的网络权重参数，此时我们假设被冻结的参数为 $\theta_T$，那么损失函数就可以写为如下形式：

\[L(\theta) = \mathbb{E}[(\underbrace{r+\gamma \mathop{\text{max}}\limits_{a^\prime} q(s^\prime,a^\prime;\textcolor{red}{\theta_T})}_{\text{TD Target}}-q(s,a;\theta))^2]\]

此时梯度只与最后一项有关，可求解得到

\[\nabla_\theta L(\theta) = -[ r+\gamma \max_{a^\prime}q( s^\prime,a^\prime;\textcolor{red}{\theta_T} ) -q( s,a;\theta ) ] \nabla _{\theta}q( s,a;\theta )\]

相应的网络参数更新式为

\[\theta \leftarrow \theta - \alpha \nabla_\theta L(\theta)\]

上述过程中，$\theta_T$ 只能冻结较短的时间，否则 TD Target 长时间得不到更新，梯度下降会偏离最优方向，导致算法失效。因此我们每隔一段时间就要对 $\theta_T$ 进行一次更新。

DQN 采用的分离拷贝思想就源于此，在训练开始时刻设计两个 Q-Network 而不是一个，他们的参数分别为 $\theta,\theta_T$，其中被持续更新的网络称为 主网络，被周期性冻结的网络称为 目标网络。

主网络：$\hat{q}(s,a;\theta)$
目标网络：$\hat{q}(s,a;\theta_T)$

初始时刻二者相等。每隔一段时间，直接将主网络较新的网络参数，直接拷贝给目标网络参数，然后再次冻结目标网络，继续更新主网络，如此循环直至训练结束。示意图如下：

4.2.2. 经验回放（experience replay）

经验回放的具体做法是，训练时不再沿着采样的顺序逐个经验数据训练，而是先把经验数据存储到一个集合 $\mathcal{B}\doteq { (s,a,r,s^\prime) }$，称其为 回放缓冲（replay-buffer）。训练 DQN 时，每次从这个集合中均匀随机（uniformly）抽取出部分样本作为 mini-batch 训练样本，以此打破样本之间的相关性。

经验回放同样可以用于原始 Q-Learning 算法，因为它本身也是 off-policy 方法，行为策略和目标策略不一致。可以先用行为策略采样一批经验数据，然后再用目标策略进行训练。甚至引入经验回放后，可以进一步提高 Q-Learning 的数据利用效率，因为一组经验样本可能会被抽取和使用很多次。

4.3. 算法流程

DQN 的伪代码如下：

Given a behaviour policy $\pi_b$ (e.g., $\varepsilon$-greedy, uniform, human, etc)
Store experience samples generated by $\pi_b$ in replay buffer $\mathcal{B}={(s,a,r,s^\prime)}$
Initialize two network with parameters $\theta,\theta_T$ randomly
Repeat (for each iteration):
- Uniformly draw a mini-batch of $N$ samples from $\mathcal{B}$
- For each sample $(s,a,r,s^\prime)$ in the mini-batch:
  - Compute TD Target: $y=r+\gamma \max_{a^\prime} \hat{q}(s^\prime,a^\prime;\theta_T)$
  - Compute TD Error: $\delta = y-\hat{q}(s,a;\theta)$
  - Compute loss: $L(\theta) = \frac{1}{2}\delta^2$
  - Update $\theta$ by minimizing $L(\theta)$
- $\theta_T \leftarrow \theta$ every $C$ iterations
Get greedy policy from $\hat{q}(s,a;\theta)$

4.4. 实例分析

下面我们使用 DQN 算法来解决一个简单的 Grid World 问题，我们希望得到所有状态下的最优策略，实例设置如下：

只采样 1 个episode，智能体达到目标状态后继续采样；
该 episode 设置为 1000 步，采样 1000 步后停止；
行为策略采用 $\pi(a\vert s) = 0.2,\forall s,a$ 策略；
使用单隐层的浅层网络作为非线性近似器来估计 $\hat{q}(s,a;\theta)$，隐层有 100 个神经元。

仿真结果如下：

可以看出，

图（a）：初始均匀随机策略；
图（b）：经过 1000 步采样得到的数据已经基本覆盖了所有的状态动作对；
图（d）：训练 DQN，其损失函数能够收敛，表明其很好地拟合了已有样本；
图（c）：基于 DQN 的值函数估计给出的策略确实是最优策略；
图（e）：DQN 对所有值函数的估计也收敛到真实值函数。

将迭代步长降低到 100 步，相当于样本数量减少至原来的十分之一，结果如下：

可以看出，

图（b）：经过 100 步采样得到的数据难以所有的状态动作对；
图（d）：训练 DQN，其损失函数能够收敛，表明其很好地拟合了已有样本；
图（c）：基于 DQN 的值函数估计给出的策略远不是最优策略；
图（e）：DQN 对所有值函数的估计无法收敛到真实值函数。

上述结果表明，即使 DQN 很强大，数据量不够或者采样不充分也没法保证其效果。

4.5. 过高估计（Double DQN）

DQN 算法在深度强化学习领域取得了不俗的成绩，不过其并不能保证一直收敛，研究表明这种估计目标价值的算法过于乐观的高估了一些情况下的行为价值（主要原因在于 max 操作），导致算法会将次优行为价值一致认为最优行为价值，最终不能收敛至最佳价值函数。

为了解决这个问题，Double Q-learning 率先使用了两个值函数进行解耦，其互相随机的更新两个值函数，并利用彼此的经验去更新网络权重 $\theta$ 和 $\theta_T$。对应的损失函数为

\[L(\theta) = \mathbb{E}[(r+\gamma \textcolor{blue}{q(s^\prime,\textcolor{red}{\mathop{\text{argmax}}\limits_{a^\prime}q(s^\prime,a^\prime,\theta)};\theta_T)}-q(s,a;\theta))^2]\]

其可拆分为如下两个等式

\[\begin{aligned} L(\theta) &= \mathbb{E}[(r+\gamma \textcolor{blue}{q(s^\prime,\textcolor{red}{a^\prime};\theta_T)}-q(s,a;\theta))^2]\\ \textcolor{red}{a^\prime} &=\mathop{\text{argmax}}\limits_{a^\prime}q(s^\prime,a^\prime,\theta) \end{aligned}\]

其网络示意图如下：

带来的效果如下：