强化学习研究决策制定和控制，以及一个进行决策的 agent 如何学会在一个未知环境中采取最优行动。深度强化学习研究如何在强化学习算法中使用神经网络，使得无需进行人工特征工程直接学习从原始感知数据到原始行动输出的映射变得可能。
本文讲解深度强化学习技术。受众是那些已经有了一定的机器学习基础，如监督学习、神经网络和强化学习基础的读者。
本教程和已有的强化学习教程的比对
已有的强化学习（RL）课本没有给出足够的关于如何使用函数近似的指导；基本上都是聚焦在离散状态空间的领域。而且，现有 RL 课本并没有对无导数优化和策略梯度方法给出充分讲述，而这些技术在很多的任务上都是相当重要的。
我对强化学习没有任何经验。我可以从何处开始学习？
现在有几个大学课程给出了免费的视频教程：
或者，你可能想要从课本学习：
我是否有理解这个教程的基础？
我们假设读者有下面的预备知识：
- 如何训练神经网络进行回归和分类
- 熟悉基本的 MDP、值迭代和策略迭代
目录：
1 预备知识、符号和术语
强化学习包含一个 agent 和一个环境：每个时间步，agent 会选择一个行动，然后环境会返回给 agent 一个收益然后转换到下一个状态。在标准设置中，agent 和环境的交互被划分成一系列 回合（episode） 的序列。在每个回合，初始状态 $s_0$ 从分布 $\mu(s_o)$ 中采样出来。每个时间步，agent 随机或者确定地选择出一个行动；我们记此作 $a_t \sim \pi(a_t|s_t)$ 表示行动是根据概率分布 $\pi$ 采样出来的。下一个状态和收益根据转换概率分布 $R(s_{t+1}, r_t | s_t, a_t)$。这个过程持续进行直到 终止 状态达到，此时该回合结束。其过程可以写成下面的形式：
$s_0 \sim \mu(s_0)$
$a_0 \sim \pi(a_0|s_0)$
$s_1, r_0 \sim P(s_1, r_0 | s_0, a_0)$
$a_1 \sim \pi(a_1 | s_1)$
$s_2, r_1 \sim P(s_2, r_1 | s_1, a_1)$
…
$a_{T-1}, r_{T-1}\sim \pi(a_{T-1} | s_{T-1})$
$s_T, r_{T-1} \sim P(s_T|s_{T-1},a_{T-1})$ ($s_T$ 是一个终止状态)
上面的定义是在 全-可观察设定下的，这种情形下的 agent 能够获得系统的全部状态。在 部分-可观察设定下，agent 只能在每个时间步获得一个观察(y)，这个观察可能是一个状态的噪声和不完全的信息。agent 可以将许多前期时间步信息进行组合，所以行动 $a_t$ 依赖于前期历史 $(y_0, a_0,y_1, a_1,\dots,y_{t-1}, a_{t-1},y_t)$；我们将历史记作 $h_t$。
$s_0, y_0 \sim \mu(s_0)$ (初始状态和观察)
$a_0 \sim \pi(a_0|h_0)$
$s_1, y_1, r_0 \sim P(s_1, y_1, r_0 | s_0, a_0)$
$a_1 \sim \pi(a_1 | h_1)$
$s_2, y_2, r_1 \sim P(s_2, y_2, r_1 | s_1, a_1)$
…
$a_{T-1} \sim \pi(a_{T-1} | h_{T-1})$
$s_T, y_T, r_{T-1} \sim P(s_T, y_T, r_{T-1}|s_{T-1},a_{T-1})$ ($s_T$ 是一个终止状态)
如果我们称历史 $h_t$ 为系统的状态，那么这个部分-可观察设定等价于 全-可观察设定。因此，能够应用在 全-可观察设定下的 RL 算法同样能应用在 部分-可观察设定中，而无需做任何大的变动——所以，对算法的讨论就可以假设在全-可观察设定下。参考[BertsekasVol1] 对部分-可观察 MDP 如何规约到 MDP 的更加形式化的讨论。
在实际应用中，不适用整个原始的行动和观察的历史数据，agent 使用一个循环神经网络（RNN）将观察历史编码为一个定长向量 $h_t$，你可以将这个向量看成是 agent 的“短期记忆(short-term memory)”。
为了更加方便的表述问题，我们给出下面的包含将会使用到的符号的表格。
s 状态
a 行动
r 收益
y 观察
$\tau$ 轨迹
$\pi$ 策略
$\theta$ 策略参数
R 总收益
$\hat{A}$ 平均估计
V 状态-值函数
P 转换概率
2 黑盒优化和交叉熵方法
很多强化学习问题可以被描述为下面的优化问题：
$\mathrm{maximize}_{\theta} E[R|\theta]$，其中 $R$ 是一个回合的总收益，行动是根据策略 $\pi(a_t|s_t;\theta)$ 选择出来的。
（注意到我们可以仅仅使用一个确定的策略 $a_t = \pi(s_t, \theta)$；但是上面的随机形式是可以推广使用的。）
最简单的方式就是把整个问题看做一个关于策略参数 $\theta$ 的“黑盒”优化问题。也就是说，我们有一个参数向量 $\theta$ 包含所有 agent 的参数，我们可以得到目标函数 $E[R|\theta]$ 的带噪声的评价（evaluation）。我们称此为 黑盒 优化问题因为我们并不假设任何关于目标计算的知识，或者这是一个连续函数；我们仅仅通过在不同的输入 $\theta_1, \theta_2,\dots$ 进行查询来学习这个函数。黑盒优化可以用下面一般的形式描述：
$\max_\theta E_\zeta[f(\theta,\zeta)]$
其中我们通过重复提供参数 $\theta_i$ 来获得关于函数 $f$ 的信息；然后采样出未观察噪声随机变量 $\zeta_i$，获得值 $f(\theta_i, \zeta_i)$。（如果是在计算机模拟中计算 $f$，$\zeta$ 可以对应于随机数生成器。）
在 RL 设定中，因为 $\theta$ 是维度很高，黑盒方法（或者无导数优化算法）通常比其他 RL 算法（探索问题结构型的）低效。但是，在实际应用中，在小的问题上常常表现得很好，也是最为容易实现的算法。
交叉熵方法（CEM）是简单的黑盒优化算法。CEM 通过重复更新在候选参数向量 $\theta$ 上的高斯分布的均值和方差进行。
最简单的算法描述如下：
Algorithm 1: 交叉熵方法 CEM
初始化 $\mu\in \mathbb{R}^d$,$\sigma\in \mathbb{R}^d$
迭代 $= 1,2,\dots$
采样 $n$ 样本 $\theta_i\sim N(\mu, diag(\sigma))$
对每个样本执行噪声的评价 $f(\theta_i, \zeta_i)$
选择前 $p\%$ 样本 (e.g. $p=20$)，称为“精英集合（elite set）”
用精英集合拟合一个高斯分布，使用对角协方差，得到新的 $\mu,\sigma$
返回最终的 $\mu$
更多细节和实践中的提升可以在[SzitaLorincz06]中找到。在 RL 设定中，我们通过对一个或者更多的回合执行策略参数化评价 $f(\theta_i, \zeta_i)$ ，并计算总收益。
2.1 练习
(实践 ) 实现交叉熵方法，将其应用在CartPole 环境中。
(实践 ) 将其应用在 Swimmer 环境中，这是一个连续行动空间的情形。尝试人工增加方差和逐步降低噪声为 0，如[SzitaLorincz06]
(理论 *) CEM 的一个弱点是精英集合中的元素可能已经碰巧选中，如幸运地成为 $\zeta$ 的样本。 实际上，这会让 $\theta$ 在 $f$ 中产生高方差。所以，CEM 不会收敛到一个 $\eta(\theta) = E_{\zeta}[f(\theta, \zeta)]$ 的局部最大值点。
解释为何 CEM 不能收敛到 $\eta(\theta)$ 的局部最大值点
证明如果 $f$ 是确定性的（即，如果不依赖于噪声 $\zeta$），那么 CEM 不会收敛到一个局部最大值点
在随机情形下，什么目标函数让 CEM 收敛到一个局部最优值点？
你能不能设计出一个算法通过在多个不同的 $ \theta$ 处评价同样的噪声样本 $\zeta$ 在多个不同的 $ \theta$ 处解决这个问题？
更多的信息参见[GoschinWeinsteinLittman13]
2.2 笔记
你可能会想为何 CEM 叫这个名字。该名称最早来自积分估计的一种方法，你可以参考[Owen14]的第 10 章。
3 策略梯度
策略梯度算法通过梯度下降进行优化。就是说，通过重复计算策略的期望回报梯度的噪声估计，然后按照梯度方向来更新策略。该方法比其他 RL 方法（如 Q-学习）更有利主要是我们可以直接优化感兴趣的量——策略的期望总收益。该类方法由于梯度估计的高方差长期被认为不太实用，直到最近，[SchulmanEtAl15]和 [MnihEtAl16]等工作展示了神经网络策略在困难的控制问题上的采用策略梯度方法的成功应用。
3.1 直觉解释
你可能比较熟悉概率模型的监督学习，其中目标是最大化给定输入(x) 时的输出 (y) 的对数概率。
$\max_{\theta} \sum_{n=1}^{N}\log p(y_n|x_n;\theta)$
策略梯度方法通常需要假设一个随机策略，该策略给出了对每个状态 (s) 的行动 (a) 上的概率分布；我们将此分布写作 $\pi(a|s;\theta)$。
如果我们知道对每个状态正确的行动 $a^*$，我们可以简单地最大化监督学习的目标函数：
$\max_{\theta} \sum_{n=1}^{N}\log p(a^*_n|s_n;\theta)$
然而，我们并不知道正确的行动。相反，我们会尝试对行动好坏进行粗略的猜测，试着去增加好的行动的概率。更加具体地讲，假设我们刚收集完 agent 和环境一个 agent 和环境回合的交互，所以我们有了一个状态、行动和收益的序列：$\tau = (s_0, a_0, r_0,s_1, a_1, r_1,\dots,s_{T-1}, a_{T-1}, r_{T-1},s_T)$。令 $R$ 表示收益的和：$R=\sum_{t=0}^{T-1} r_t$。最简单的策略梯度公式就是：
$\hat{g} = R\nabla_\theta \log(\prod_{t=0}^{T-1}\pi(a_t|s_t;\theta)) = R\nabla_\theta \sum_{t=1}^{T} \log \pi(a_t|s_t;\theta)$
使用这个梯度的估计 $\hat{g}$，我们可以用一个梯度上升的步骤，$\theta\leftarrow \theta+\alpha \hat{g}$ 进行策略的更新，其中 $\alpha$ 为学习率。我们会收集所有的回合，对那个回合中所有的行动的对数概率按照回合的总收益 $R$ 为比例进行增加。换言之，如果我们收集了大量的回合数据，其中一些是好的（凭借运气），另外一些是差的。我们本质上是在进行监督学习——最大化好的回合的概率。
尽管我们现在还没有给出对上述策略梯度公式的数学上的验证，但实际上已经给出了一个对策略梯度的无偏估计。
$E[\hat{g}]=\nabla_\theta E[R]$
策略梯度定义为右式的策略期望总收益的梯度。
如果我们用充足的样本（充足的回合），那么就可以任意精度计算出策略梯度。然而，估计量 $\hat{g}$ 通常噪声很大，即有很高的方差。你可以想象，这里存在很大的提升空间。与其提高好的轨迹（trajectory）的概率，我们应该提高好的行动的概率，也就是说，我们应试着去推断哪些行动影响轨迹的好坏。
有一系列形如下式的策略梯度估计量：
$\hat{g} = \nabla_\theta \sum_{t=1}^{T} \hat{A_t}\log \pi(a_t|s_t;\theta)$
其中 $\hat{A_t}$ 是行动 $a_t$ 的有利度 (advantage)的估计——比平均值好还是坏的程度。
下面的有利度估计量更有效率，也更常见：
$\hat{A}_t=r_t + \gamma r_{t+1}+\gamma^2 r_{t+2} + \dots - V(s_t)$
其中 $\gamma$ 是折扣因子，$V(s_t)$ 是 状态-值 函数 $E[r_t+\gamma r_{t+1} + \gamma^2 r_{r+2}|s_t]$ 的近似。$\gamma$ 用来定义一个有效时间区域，其中你忽略所有可能的超过未来 $1/(1-\gamma)$ 的时间步的影响。关于有效度和时间区域更加详细的解释参见[SchulmanEtAl15]。
3.2 更加形式化的解释
推导策略梯度公式的最简单的方式是使用打分函数梯度估计量，这是估计期望梯度的通用方法。我们接着将此想法用在计算期望收益的梯度上。假设 $x$ 是一个随机变量，其概率密度是 $p(x|\theta)$，即概率密度依赖于参数向量 $\theta$。$f$ 是一个标量值函数（就是收益），我们想要计算 $\nabla_\theta E_x[f(x)]$。我们得到了下面的等式：
$\nabla_\theta E_x[f(x)] = E_x[\nabla_\theta \log p(x|\theta) f(x)]$
这个方程是可以根据将期望转写成积分形式获得的：
$\nabla_{\theta} E_{x}[f(x)] = \nabla_{\theta} \int \mathrm{d}x\ p(x | \theta) f(x) = \int \mathrm{d}x \nabla_\theta p(x|\theta) f(x) =\int \mathrm{d}x\ p(x|\theta) \nabla_\theta \log p(x|\theta) f(x)= E_x[\nabla_\theta \log p(x|\theta) f(x)]$
使用这个估计量，我们就可以采样 $x \sim p(x|\theta)$，然后计算方程的左式（对 $N$ 个样本进行平均）来获得梯度的估计（在 $N \rightarrow \inf$ 时准确度更高）。就是说，我们采样 $x_1, x_2, \dots, x_N \sim p(x|\theta)$，然后使用下面的梯度估计 $\hat{g}$
$\hat{g} = \frac{1}{N} \sum_{n=1}^{N} \nabla_\theta \log p(x_i|\theta)f(x_i)$
为了在强化学习中使用这个思想，我们需要用到随机策略。这意味着在每个状态 $s$，我们的策略给出了一个行动上的概率分布，记作 $\pi(a|s)$。因为策略同样有一个参数向量 $\theta$，我们就常写成 $\pi(a|s, \theta)$。
在后续讨论中，轨迹 $\tau$ 代表状态和行动的序列，即 $\tau \equiv (s_0, a_0, s_1, \dots, s_T)$。令 $p(\tau | \theta)$ 表示在策略参数 $\tau$ 下整个轨迹 $\tau$ 的概率，令 $R(\tau)$ 为整个轨迹的总收益。
然后打分函数估计量给出了
$\nabla_\theta E_{\tau} [R(\tau)] = E_{\tau} [\nabla_\theta \log p(\tau|\theta)R(\tau)$
我们只需要采样轨迹 $\tau$，然后使用上面的公式计算策略梯度估计量。现在，我们需要显式地写出 $\log p(\tau|\theta)$ 来推导出一个实用的公式。使用概率的链式法则，我们得到
$p(\tau|\theta) = \mu(s_0)\pi(a_0|s_0,\theta)P(s_1|s_0, a_0)\pi(a_1|s_1,\theta)P(s_2|s_1, a_1)\dots\pi(a_{T-1}|s_{T-1},\theta)P(s_T|s_{T-1}, a_{T-1})$
这里 $\mu$ 是初始状态分布。我们对其取对数后，就得到一个和式，关于 $\theta$ 求导，$P(s_t|s_{t-1}, a_{t-1})$ 和 $\mu$ 一样就被消去了。我们得到
$\nabla_\theta E_{\tau}[R(\tau)] = E_{\tau}[\sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t,\theta) R(\tau)]$
这个公式非常厉害，因为我们可以不许知道系统动态知识（由转换概率 $P$ 确定的）来计算策略梯度。直觉解释是我们收集了一个轨迹，然后与其总收益的好的程度（goodness）成比例提升概率。即，如果收益 $R(\tau)$ 非常高，我们应该按照在参数空间中提高 $\log p(\tau|\theta)$ 方向进行移动。
因此，通过一些数学推理，我们推导出一个更好（更低方差）的策略梯度估计。令 $r_t$ 表示在时间步 $t$ 的收益，令 $b(s_t)$ 表示基准函数，该基准函数计算出状态-值函数的某个近似，即 $b(s) \approx V^{\pi}(s) = E_{\tau} [\sum_{u=t}^{T}r_u|s_t = s]$（从状态 $s$ 开始，未来收益的期望和）。改进的策略梯度公式如下：
$\nabla_\theta E_{\tau}[R(\tau)] = E_\tau [\sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t,\theta) (\sum_{u=t}^{T}r_u - b(s_t))]$
如果轨迹非常长，那么上述公式会有较大的方差。因此人们通常使用一个折扣因子，这样可以引入偏差来降低方差。这时，策略梯度有偏估计公式就是
$\nabla_\theta E_{\tau}[R(\tau)] \approx E_\tau [\sum_{t=0}^{T-1} \nabla_\theta \log \pi(a_t|s_t,\theta) (\sum_{u=t}^{T}\gamma^{u-t} r_u - b(s_t))]$
其中 $b(s_t)$ 就是对收益折扣和的近似 $b(s) \approx E_{\tau} [\sum_{u=t}^{T}\gamma^{u-t} r_u|s_t = s]$。
3.3 实现注意事项
有一种方便的方法计算策略梯度，就是对许多时间步使用你喜欢的自动微分软件进行批量操作。定义 $L(\theta) = \sum_{t=0}^{T-1} \log \pi(a_t|s_t, \theta) \dot A_t$，其中 $A = (\sum_{u=t}^{T} r_u-b(s_t))$。这里 $A$ 表示有效度，因为它度量了回报超过期望值多少。这仅仅是不含梯度的上面策略梯度公式。你可以在程序中定义损失函数 $L$ 。然后关于其参数进行微分，你就能得到策略梯度了！注意，不用花费长时间的总和，我们就能对 $\log \pi(a_t|s_t,\theta)$ 进行向量化计算（该向量长度为 $T$ ）然后与一个同样长度为 $ T$ 的有效度的向量进行内积。
3.4 参数化策略
我们已经抽象式描述策略为 $\pi(a|s,\theta)$。我们如何使用一个神经网络进行表示？我们仅仅需要将 $s$ 映射到某个向量 $\mu$ 上，向量描述了行动 $a$ 上的分布。例如，
如果 $a$ 来自一个离散的集合，那么我们设计一个神经网络将 $s$ 到一个概率向量上。（我们一般在神经网络的最后层使用一个 softmax 激活函数）这完全就是我们用来进行分类器学习的形式。
如果 $a$ 是连续的，那么我们可以将 $s$ 映射到一个高斯分布的均值和方差上。一般情况我们使用一个不依赖于 $s$ 的对角协方差。
如果 $a$ 是二值的，那么我们可以使用一个单个输出的网络，表示输出 1 的概率。
3.5 练习
实现一个策略梯度算法将其应用在 CartPole 环境中。比较下面的变体：
$\hat{A_t} = R$
$\hat{A_t} = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots -V(s_t)$，包含（不包含）折扣因子和基准（共有 4 中情形）
将其应用在 Swimmer 环境中
改变问题 1 和 2 的实现，使用不同的 SGD 变体，包含 momentum、RMSProp 和 Adam
4 自然策略梯度和信任区间方法
5 Q-学习
到现在为止，我们讨论的都是策略优化的技术，不管是黑盒优化还是基于梯度的方法。另外一种不同的方法是估计一个衡量所有可能的行动好坏的函数，使用这个函数来定义策略。回想一下最优的状态-值函数 $V^*(s)$ 衡量了在最优策略下状态的好坏，最优状态-行动值函数 $Q^*(s,a)$ 给出了在状态 $s$ 执行行动 $a$ 时的好坏的衡量。
$V^*(s)= E[r_0 +\gamma r_1 + \gamma^2 r_2 + \dots |s_0 = s, \pi^*]$
$Q^*(s,a)= E[r_0 +\gamma r_1 + \gamma^2 r_2 + \dots |s_0 = s, a_0 = a, \pi^*]$
（稍微解释一下上面的表述，在 $V^*$ 中，我们以开始状态 $s$ 为 $s_0$，依照 $\pi^$ 选择出的连续的变量 $a_0, r_0, s_1, a_1, r_1, \dots$ 序列，在这个序列上取期望。）$Q^$ 更加适合我们对系统的动态模型没有知识的设定，这个原因后面会解释清楚。
本节会讨论学习 Q-函数的算法。最优 Q-函数（$Q^*$）满足下面的 Bellman 方程
$Q^*(s,a) = E_{s’}[r(s,a,s’) + \gamma V^*(s)] = E_{s’}[r(s,a,s’) + \gamma \max_{a’} Q^*(s,a’)]$
我们可以使用下面的值迭代（value iteration）算法迭代更新 Q-函数，收敛到 $Q^*$。
Algorithm 2: Q-值迭代
初始化 $Q^{(0)}$
对 $n = 1,2,\dots$
对 $(s,a)\in S\times A$ （所有状态行动对）
$Q^{(n)}(s,a) =E_{s’}[r(s,a,s’) + \gamma \max_{a’} Q^{(n-1)}(s,a’)]$ ()
最优 Q-函数（即，最优策略的 Q-函数）是更新 () 式的不动点，更严格点说，这是一个收缩（contraction），其误差指数级下降 $||Q^{(0)}-Q^*|| \propto \gamma^n$。
最优 Q-函数可用来引出一个形式——back-up 操作符 T，将 Q-函数映射到一个更新版本 TQ 上，定义如下：
$[TQ](s,a) = E_{s’}[r(s,a,s’) + \gamma \max_{a’} Q(s,a’)]$
这个被定义为 backup 操作符因为它使用向前看一步（对 $s’$ 求期望）更新了 Q-值——也就是说，它让信息按照时间回流。使用backup 操作符，Q-值迭代对 $(s,a)$ 的循环可以简洁地写作 $Q^{(n)} = TQ^{(n-1)}$。
如果我们知道准确的转换模型和系统的收益函数，我们就可以仅计算准确的关于 $s’$ 的期望。为了准确计算目标值，我们需要对 $s’$ 求期望，就必须能够获取转换模型和收益函数的信息。但是，给定一个状态、行动、收益和下一状态 $(s_t, a_t, r_t, s_{t+1}’)$ 的转换，我们可以构造出一个 $[TQ](s_t,a_t)$ 的无偏估计。然后我们可以给 $Q(s,a)$ 噪声估计了目标值 $[TQ](s,a) = E_{s’} [r(s,a,s’) + \gamma \max_{a’} Q^{(n-1)}(s’, a’)]$。我们称这个噪声估计为 $\hat{TQ}$，定义如下
$\hat{TQ}_t = r_t + \gamma \max_{a’} Q(s_{t+1},a’)$
因为这是无偏估计，
$E_{s_{t+1}} [\hat{TQ}_t|s_t,a_t] = TQ(s_t,a_t)$
注意 $\hat{TQ}$ 不依赖于我们在状态 $s_{t+1}$ 时采取的行动，因此，这个无偏性不依赖于我们执行的策略，所以我们有很多的自由来考虑使用什么策略来收集数据。使用这些估计量，我们可以设计出下面的算法，收集批量的数据然后使用值迭代更新 Q-函数。由于不管采取何种策略都能够获得一个无偏估计，很多模型未知的情况下，基于 Q-函数的算法比之基于 V-函数的算法常常更受青睐。（如果模型已知，我们可以存储 V-函数来定义 Q-函数。）
Algorithm 3: 基于模拟的 Q-值迭代
初始化 $Q^{(0)}$
对 $n = 1,2,\dots$
和环境交互 T 个时间步，通过从某种策略 $\pi^{(n-1)}$ 中选择行动获得轨迹 $(s_0, a_0, s_1, a_1,\dots,s_T)$ （如果是一个按照回合进行的任务，可能会包含多个回合）
$Q^{(n)} = \mathrm{minimize}_{Q} \sum_{t=1}^{T} ||Q(s_t,a_t) - \hat{TQ}||^2$，其中 $\hat{TQ}$ 使用当前 Q-函数 $Q^{(n-1)}$ 算出
在第 n 次迭代时该选择什么策略 $\pi^{(n-1)}$？由于 $\hat{TQ}$ 的无偏性，任何能够充分访问状态-值对的策略都能够给出所有目标 Q-值 $[TQ](s,a)$ 一致的估计，就是说，若用无穷多的数据就能够给出正确的 $[TQ](s,a)$。典型方法是使用 $\epsilon$-贪婪策略，按照概率 $\epsilon$ 随机行动，按照概率 $1-\epsilon$ 使用 $\mathrm{arg max}_{a} Q(s,a)$。随机行动概率 $\epsilon$ 通常从 $1$ 缓慢退火为 $0$。
算法 3 是一种批式算法：批式强化学习算法在收集数据和使用这个数据执行参数更新两步交替进行。这和在线算法有所不同，在线算法在数据收集的同时增量更新。我们能不能将 $n=1$ 设计一个在线算法？可以，但是我们需要作出小的调整来限制在每个迭代对 Q 更新的大小（现在只有一个时间步）。通常，我们通过混合有噪声的估计和当前值计算目标 Q-值，混合比例 $\alpha\in(0,1)$。
$\hat{TQ}_t = (1-\alpha)Q(s_t, a_t) + \alpha(r_t + \gamma \max_{a’} Q(s_{t+1},a’))$
$Q(s_t,a_t) \leftarrow \hat{TQ}_t$
这个算法称为 Watkins Q-学习算法[WatkinsDayan92]。给定合适的将 $\alpha$ 下降到 0 的设计，并给定能够访问所有状态-行动对无穷多次的策略（如使用 $\epsilon$-贪婪策略），这个算法能够保证收敛到最优策略。[JaaJorSingh94] 给出了一个简洁的分析。然而在现实应用中，这个算法需要相当大的时间步数。
前面我们讨论了 Q-函数 $Q(s,a)$。如果状态空间和行动空间是离散的（有限集合），那么最为直接的方式是使用一个 Q 函数表，将 Q-函数作为一个数组存放，每个 $(s,a)$ 对都有一个位置。而如果状态空间巨大或者是无穷的，这显然是不太现实的选择，所以我们需要找一个函数的近似方法，如神经网络，来表示 Q-函数。
我们记 $Q_\theta$ 为由参数向量 $\theta$ 参数化的 Q-函数。存在至少两个合理的方法来参数化 Q-函数：
网络以 $(s,a)$ 为输入，以标量 Q-值为输出。
网络将 $s$ 映射到某个参数向量 $\mu$，这个可以和行动组合来获得标量 Q-值。
实际情形下，第二种方式工作得更好，也得到了更加有效的算法。类比于我们前面对参数化策略的讨论，我们可以定义依赖于行动空间的 Q-函数的不同的参数化方式。
如果 $a$ 来自一个离散集合，那么我们设计一个神经网络将 $s$ 映射到一个 Q-值的向量
如果 $a$ 是连续的，那么我们可以使用一个神经网络将 $s$ 映射到一个二次函数的中心，其curvature，产生 Q-值 $Q(s,a) = ||(a-\mathrm{center}) \odot \mathrm{curvature}||^2$。参见[GuEtAl16]。
给定该参数化 Q-函数，我们可以运行 Q-值迭代算法，优化的步骤变成：
$\theta^{(n)} = \mathrm{minimize}_\theta \sum_t ||Q_\theta(s_t, a_t) - \hat{TQ}_t||^2$
这个算法被称为 神经网络拟合 Q-迭代（Neural-Fitted Q-Iteration） [Riedmiller05]。
最近，Mnih 等人提出了这个算法的变体版本，将数据采集纳入 Q-函数更新[MnihEtAl13]。他们使用了一个 目标网络，类似于前面的 Q-函数 $Q^{(n-1)}$。他们还使用了一个 回放缓冲区 （replay buffer），包含最近一些 Q-函数收集到的数据，而在算法 3 中，只是使用了 $Q^{(n-1)}$ 采集的数据来拟合 $Q^{(n)}$。
5.1 练习
实现 Watkins Q-学习算法，应用在 toy_text gym 环境中。你还可以使用策略迭代来计算最优解，比较一下性能。（注意这些环境给出了方便的转换模型和收益函数）
应用批式 Q-值迭代算法或者 DQN 在 classic_control 环境中。
应用批式 Q-值迭代算法或者 DQN 在 mujoco 环境中，使用一个二次的 Q-函数。
6 引用
[BertsekasVol1] Bertsekas, Dynamic Programming and Optimal Control, Volume I.
[SzitaLorincz06] (1, 2) Szita and Lorincz, Learning Tetris with the Noisy Cross-Entropy Method.
[SchulmanEtAl15] (1, 2) Schulman, Moritz, Levine, Jordan, Abbeel, High-Dimensional Continuous Control Using Generalized Advantage Estimation. http://arxiv.org/abs/1506.02438
[MnihEtAl13] Mnih et al., Playing Atari with Deep Reinforcement Learning. http://arxiv.org/abs/1312.5602
[MnihEtAl16] Mnih et al., Asynchronous Methods for Deep Reinforcement Learning.http://arxiv.org/abs/1602.01783
[Owen14] Owen, Monte Carlo theory, methods and examples. http://statweb.stanford.edu/~owen/mc
[GoschinWeinsteinLittman13] Goschin, Weinstein, Littman, The Cross-Entropy Method Optimizes for Quantileshttp://jmlr.org/proceedings/papers/v28/goschin13.pdf
[GuEtAl16] Gu et al., Continuous Deep Q-Learning with Model-based Accelerationhttp://arxiv.org/abs/1603.00748
[Riedmiller05] Riedmiller. Neural fitted Q iteration—first experiences with a data efficient neural reinforcement learning method.
[JaaJorSingh94] Jaakkola, Jordan, and Singh. On the convergence of stochastic iterative dynamic programming algorithms.
[WatkinsDayan92] Watkins, Dayan. Q-learning.
[KakadeLangford02] Kakade & Langford, Approximately optimal approximate reinforcement learning
[Kakade01] Kakade, Sham. A Natural Policy Gradient
.
，我们可以简单地最大化监督学习的目标函数：
. 令 
表示收益的和：
. 最简单的策略梯度公式就是：
，我们可以用一个梯度上升的步骤，
进行策略的更新，其中 
为学习率. 我们会收集所有的回合，对那个回合中所有的行动的对数概率按照回合的总收益 
是行动 
的有利度 (advantage)的估计——比平均值好还是坏的程度.
是折扣因子，
的近似. 
的时间步的影响. 
，那么我们如何使用一个神经网络进行表示？实际上，我们仅仅需要将 
映射到某个向量 
上，向量描述了行动 
上的分布. 例如，
的深度神经网络 
来表示策略，定义目标函数为总折扣奖励
的方向
的值函数 
) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order (usually to optimize program flow). This involves 
