论文 Learning to act by predicting the future
这篇论文提出的 DFP (Direct Future Prediction) 赢得了2016年 Virtual Doom AI Competition 的 “Full Deathmatch” 环节的比赛。Virtual Doom 是一个对战性的第一人称射击型游戏，根据玩家击杀数判定胜负。为了体现出模型的泛化能力， 训练过程中使用的地图不在比赛过程中出现。DFP的性能超出了第二名（Deep LSTM Q-Network）50%，并且其模型以及训练数据更加简洁，表现出了DFP模型的优越性。
机器学习问题可以分为监督学习问题，无监督学习问题以及强化学习问题。监督学习主要是学习一个输入到输出的映射函数，无监督学习更加关注如何挖掘数据本身的隐含结构，强化学习是一个面向目标的策略学习问题。
因此采用强化学习的方法使得机器人在Deathmatch游戏中表现良好十分合适。因为这是一个直接面向目标的问题 （在游戏中取得最大的击杀数）。所以 DQN 以及 A3C 这样的算法应运而生，并且取得了巨大的成功。但是这篇论文提出了一个不同的观点。它引用了Jordan & Rumelhart (1992) 这篇论文中提出的一个观点：
对于一个可以与环境进行交互的学习问题，如果环境提供的反馈是稀疏的标量 （例如，对于一个五子棋问题，反馈只在最后胜负已分时给出，并且只是一个类似+1，-1的标量反馈），采用传统的强化学习算法会十分有效；但是如果环境给出的反馈是一个即时密集的多维度反馈 （在短时间内具有很大的信息比特率），监督学习算法更具优势。
由于监督学习方面的研究已经非常成熟，最近十分火热的深度学习更是在很多方面都取得了很好的结果，因此，如果我们能够把强化学习问题在某种程度上转化为一个监督学习问题，可以使得问题的求解大大简化。
那么现在的问题是，我们要如何设计模型，从而可以得到一个监督信号呢？可以想到，我们唯一拥有的数据就是机器人通过与环境的交互得到的状态转移 （对于游戏来说就是玩家在游戏中采取不同的行为得到的环境的反馈，例如，玩家使用一个血包可以是的生命值回复；向左转可以使得画面发生变化等等）。我们可以对这些数据进行特殊的设计，从而能够满足我们的要求。
具体来说，我们不再简单使用传统强化学习问题中单一的状态 （例如游戏中的一帧画面）与对应的回报。我们把单一的状态拆分开来，对于原始的图像，声音等信息原样保留，形成一个 ”感觉输入流 (sensory input stream)“ ，很明显它是一个高维的变量；另外，我们从这些原始的信息中提取出能够代表我们学习目标的测度 （例如健康度，剩余弹药数以及击杀数等），形成一个 ”测度流 (measurement stream)“ ，它是一个低维的变量 （因为只包含几个重要的变量）。注意，这里的stream不是代表了好几个时间步，而是代表它是多个测度的一个集合。
这样做有什么好处呢？一个传统的强化学习问题，其训练对象就是最大化一个关于reward的函数。一般reward都是人为给定的 （还是拿五子棋举例，最后玩家赢了，回报就是一个正数， 反之就是负数），但是这就使得学习问题的方差变得很大，训练过程十分不稳定，收敛速度慢，甚至可能不收敛。因此，我们希望reward的值不要过于随机化，能够通过某些监督信号来减少其方差。这里就可以体现出我们之前进行状态分解的优势。我们可以将reward表示成 measurement stream 的函数，由于measurement是agent与真实环境进行交互时得到的，属于一种监督信号，这很好的满足了我们的需求。所以最后我们的训练对象由最大化一个关于reward的函数变成了最大化一个关于measurement stream的函数。而这个measurement stream可以认为是传统强化学习问题中的reward。
模型
现在我们正式地定义DFP模型。在每一个时间步$t$，agent接收一个观察 （转移到一个状态）$O_t$, 根据这个观察 （状态）的某些固有属性从可行的动作集合中选取一个动作执行。$O_t$详细定义如下：
$$
\mathbf{o}_t = (\mathbf{s}_t, \mathbf{m}_t)
$$
整个状态转移过程中，我们希望最大化目标，前面提到了，它是关于measurement stream的函数：
$$
\mathbf{f} = (\mathbf{m}_{t+\tau_1}-\mathbf{m}_t, \cdots, \mathbf{m}_{t+\tau_n}-\mathbf{m}_t)
$$
$\tau_1, \cdots, \tau_n$ 代表与当前时间步$t$的一个偏差。至于为什么不直接最大化measurement stream而是最大化一个差值，我认为作者可能是有如下考虑：
- 借鉴了n-step Q-learning 的做法。
- 由于模型是为了预测当前时间步$t$的measurement stream，因此优化对象中应该包含当前的measurement stream。
最后，
$$
\mathbf{Goal} \; = \; u(\mathbf{f};\mathbf{g})
$$
一般线性函数即可满足我们的需求，即
$$
u(\mathbf{f};\mathbf{g}) = \mathbf{g}^{\text{T}}\mathbf{f}
$$
注意到现在我们的问题变成了一个监督学习的问题。为了训练模型，我们需要预测目标，然后再与真实的目标比较，通过最小化误差来进行学习。那么我们现在定义这个预测过程。注意到，由于目标只是measurement stream的函数，而且参数一般都是确定的，不需要进行学习。因此，我们的预测对象是measurement stream而不是目标。下面我们定义一个预测器F:
$$
\mathbf{p}_t^a = F(\mathbf{o}_t, a, \mathbf{g};\theta)
$$
注意，这里的$\text{g}$和(4)中是不一样的，它代表目标。$p_t^a$代表在$t$时间步下，执行行为$a$所得到的reward，也即measurement stream。
当训练完成的时候，我们就要用这个预测器F进行决策，策略定义如下：
$$
a_t = {\arg\max}_{a \in \mathcal{A}} \mathbf{g}^{\text{T}}F(\mathbf{o}_t, a, \mathbf{g};\theta)
$$
注意到，模型实际训练的过程中采用的是$\varepsilon\text{-greedy}$策略。这里可以看出，在训练过程中或者测试过程中，我们要手动的计算出$u(\text{f};\text{g})$的值。下面我们详细的剖析模型的训练过程。
模型训练
对于传统的强化学习算法，例如Q-learning，其训练过程是一个在线学习的过程，也即其训练集是一个一个进行输入的，每输入一次都进行一次参数的更新。由于Q-learning以及DFP都是采用了MC (Monte Carlo) 策略，这种训练过程可能十分不稳定 （由于训练最开始时我们的训练数据是通过一个随机策略与环境交互产生的），致使收敛速度很慢，需要很多的episodes进行训练。这里采用了和DQN (Deep Q-Network) 相同的 experience replay技术。具体来说，就是保存每次agent与环境交互后产生的数据对
$\langle \mathbf{o}_i, a_i, \mathbf{g}_i, \mathbf{f}_i \rangle$ 到数据集$\mathcal{D}$中，即$\mathcal{D} = \{\langle \mathbf{o}_ i, a_i, \mathbf{g}_i, \mathbf{f}_i \rangle \}_{i=1}^N$. 注意这里的$N$个数据对并不是直接顺序产生的，而是从当前episode中到当前时间步时，所有的数据对中选取最近的$M$个，再从其中随机抽样$N$个。另外，每隔k步才进行一次参数的更新，因为$\mathbf{f}$的计算需要考虑到32个时间步之后的数据，因此$k \ge 32$（实验部分将详细介绍）。DQN 给出了具体的实现：
另外需要注意的是
有了训练集，我们现在定义w代价函数：
$$
\mathcal{L}(\theta) = \sum_{i=1}^{N} |F(\mathbf{o}_i, a_i, \mathbf{g}_i;\theta) - \mathbf{f}_i|^2
$$
我们来对比一下 DQN 的代价函数：
$$
L_i(\theta_i)= \mathbb{E}_{s, a \sim \rho(\cdot)} \left[ y_i - Q(s, a;\theta_i) \right],
$$
其中$y_i = \mathbb{E}_{s^{\prime} \sim \varepsilon}[ r + \gamma \max_{a^{\prime}} Q(s^{\prime}, a^{\prime};\theta_{i-1}) ]$ 。
这里的$y_i$是上一次模型的输出，其值随着更新次数的增加也在不断变化。因此从这里也能看出DFP是一个监督学习算法。
训练过程中我们为了解决报告最开始提出的目标随着时间发生改变的问题，采用了两种目标进行测试：
- 目标向量$\mathbf{g}$ （不是目标）在整个训练过程中不变
- 目标向量在每个episode结束时随机变化
网络结构
下图是DFP模型的网络结构：
从图中可以看出，该网络有三个输入模块。一个感知模块$S(s)$，一个测度模型$M(m)$以及一个目标模块$G(g)$。在实验中，$s$代表一张图片，$S$代表一个卷积神经网络。测度模块以及目标模块都是由一个全连接神经网络构成。三者的输出连接在一起，形成一个联合的输入表示，供后续算法使用：
$$
\mathbf{j} = J(\mathbf{s, m, g}) = \langle S(\mathbf{s}), M(\mathbf{m}), G(\mathbf{g}) \rangle
$$
DFP网络采用了DQN的做法，一次性输出所有action对应的measurement stream。但是我们希望能够着重关注对action之间差异的学习。因此采用了Wang et al. (ICML 2016) 这篇文章中才去的做法，将预测模块分为两个stream，一个期望stream $E(\text{j})$ 以及一个action stream $A(\text{j})$。注意这两个stream都是一个全连接的神经网络。期望stream的目标是预测所有action能够获得的measurement stream的期望。Action stream关注不同action之间的差异。其中，$A(\text{j}) = \langle A^1(\text{j}), \cdots, A^{w}(\text{j}) \rangle$，$w = |\mathcal{A}|$代表所有可能action的个数。同时我们还在加入了一个正则化层：
$$
\overline{A^{i}}(\mathbf{j}) = A^{i}(\mathbf{j}) - \frac{1}{w}\sum_{k=1}^{w} A^{k}(\mathbf{j})
$$
正则化层对每一个action的预测值减去了所有action预测值的期望，这样就强制期望stream去学习这个期望，这样action stream就可以着重关注不同action之间的差异。最后，网络的输出如下：
$$
\mathbf{p} = \langle \mathbf{p}^{a_1}, \cdots, \mathbf{p}^{a_w} \rangle = \langle \overline{A^1}(\mathbf{j})+E(\mathbf{j}), \cdots, \overline{A^w}(\mathbf{j})+E(\mathbf{j}) \rangle
$$
为了验证网络中使用的三个辅助结构（measurement stream输入，expectation-action分解以及action正则化层）的作用，我们进行了测试。我们基于D3场景（下面实验部分提及）随机产生了100个地图场景用以训练。同时采用basic网络 （下面实验部分提及），最后的实验结果如下：
可以看出，expectation-action分解的作用最大，同时我们设计的measurement stream也是十分重要的。
实验及结果
具体的实验场景见下图：
在前两个场景中，agent可以采取三个动作，向前移动、向左转、向右转。这样一共就有8种动作组合。采用的测度只有一种，就是血量。在后两个场景中，agent可以采取八个动作组合，分别是向前移动、向后移动、向左转、向右转、向左扫射，向右扫射、奔跑以及射击。这样一共就有256个动作组合。采用的测度一共有三种，血量，弹药数以及击杀数。这里我认为存在一个可以改进的地方，应该排除掉不合理的动作组合，例如同时向左转以及向右转。这样可以减少搜索空间，加速收敛，同时可以提高策略的质量。
实验中网络的结构与DQN的结构十分类似，参数也尽可能相近，就是为了比较起来比较公平。具体来说，实验中采用了两种网络，basic以及large，结构相同，但是参数数量不同：
Basic网络的参数与DQN比较接近，以便比较。两个网络在所有的非终止层后都加入了一个非线性层，采用的激活函数为Leaky ReLU，具体函数为：
$$
\mathbf{LReLU}(x) = \max(x, 0.2x)
$$
参数初始化方法采用了He Initialization，代码实现如下：
|
|
Agent以episode为单位进行训练和测试。每一个episode拥有525个时间步（大约一分钟），如果agent死亡那么episode也会终止。同时将时间偏置$\tau_1, \cdots, \tau_n$设置为1, 2, 4, 8, 16, 32。最后结果表明只有最新的三个时间步（8, 16, 32）对结果有贡献，贡献比例为 1:1:2。
另外，输入图像被转换成灰度图像，measurement stream并不是直接输入，而是进行了正则化 （除以标准差）。同时，我们还在训练以及测试过程中使用frame skipping技术。Agent每隔4帧采取一次action。这些被忽略的帧所采取的action与其之后的帧的action一致，相当于进行了一次简单的复制。另外，由于人类的反应速度肯定是比不上计算机的，因此fram skipping使得agent的行为更加接近人类。
对于之前提到的experience replay技术，实验中将M值设为20000， N设为64，k也设为64（$\ge32$）。同时为了能够更高效的获得训练集$\mathcal{D}$，我们同时采用8个agent并行运行。训练时采用的梯度下降算法为Adam算法，参数设置如下：$\beta_1=0.95, \;\beta_2=0.999,\;\varepsilon=10^{-4}$。Basic网络训练了800,000次mini-batch迭代，large网络训练了2,000,000次。算法实现https://github.com/IntelVCL/DirectFuturePrediction。
下面介绍我们的baselines。我们同三个算法进行了比较：DQN (Mnih et al., 2015), A3C (Mnih et al., 2016), 以及 DSR (Kulkarni et al., 2016b)。DQN由于其在Atari游戏上的优异效果成为了视觉控制的标准baseline。A3C更是这个领域中的最好的算法。DSR也在Virtual Doom平台上进行了实验。所以我们挑选了这三个具有代表意义的算法。
对于这三个算法我们都使用了Github上的开源实现：DQN (https://github.com/kuz/DeepMind-Atari-Deep-Q-Learner) 、DSR (https://github.com/Ardavans/DSR), 以及 A3C (https://github.com/muupan/async-rl)。前两个都是作者提供的源码，最后的A3C是一个独立开发者的个人实现。
对于DQN以及DSR我们测试了三个学习速率：默认值（0.00025），0.00005以及0.00002。其他参数直接采用默认值。对于A3C算法，为了训练更快，前两个任务我们采用了5个学习速率 ({2, 4, 8, 16, 32} · $10^{-4}$)。后两个任务我们训练了20个模型，每个模型的学习速率从一个范围从$10^{-4}$到$10^{-2}$的log-uniform分布中进行采样，$\beta$值（熵正则项）从一个范围从$10^{-4}$到$10^{-}$的lo1g-uniform分布中进行采样。结果选取最好的。
最终结果如下所示：
在前两个游戏场景中，模型尝试最大化血量；在后两个场景中尝试最大化血量、弹药数以及击杀数的一个线性组合，参数为0.5, 0.5, 1。因为游戏更加侧重于通过击杀数判断胜负。所有的数据都是对三次训练结果进行平均，曲线图采样点的个数为$3 \times 50,000$。可以看出，DFP模型取得了最好的结果。其中DSR算法由于训练速度过慢，所以我们只在D1场景（也进行了将近10天的训练）进行了测试。
下面进行模型泛化能力的测试，我们基于D3以及D4两个场景分别随机产生100个随机场景。其中90个用于训练，剩下10个用于测试。最后结果如下：
其中最后一列采用了large网络。可以看出，从复杂场景训练之后，在简单场景上的泛化能力往往不错，虽然两者规则不同。但是反之则不可以。
接下来进行学习变化目标能力的测试。结果见下图：
其中采用第二列的策略时，agent并不知道每一个measurement的相对重要性；最后一列，agent事先并不知道哪一个measurement是不需要考虑的。但是最后测试时，效果都很好，而且在固定目标策略没有见过的目标上的效果要更好。说明DFP模型对于变化目标的学习能力优异。
最后我们单独对measurement stream时间偏置的重要性进行测试，我们采用的是D3-tx训练集，最后结果如图：
相比较而言，采用更多的时间偏置可以达到更好的效果。
总结
现在强化学习问题关注的重点还是在value function的估计上，深度强化学习模型一般采用一个深度网络直接对value function进行估计。这篇论文的创新点在于，在使用深度网络之前，对value function进行了两次额外的映射。第一次是用measurement stream来代替reward，使得reward具有更强的状态表示能力；其次，对measurement stream再次进行了一个函数映射，采用了时间偏置，借鉴了n-step Q-learning的思想。最后，再将输出作为深度网络的输入，进行value function的估计。最后的实验结果证明这种想法是有其正确性的。