[人工智能]自然语言处理（八）：使用深度强化学习玩雅达利

论文名称：Playing Atari with Deep Reinforcement Learning
论文地址：http://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

相关论文：Human-level control through deep reinforcement learning
论文地址：https://storage.googleapis.com/deepmind-data/assets/papers/DeepMindNature14236Paper.pdf

强化学习在自然语言处理的文本生成方向上有不少的应用，本篇博客主要涉及对强化学习原理的解析。
《Playing Atari with Deep Reinforcement Learning》是2013年DeepMind发表在NIPS上的论文，为深度强化学习的开山之作，主要讲解了如何基于游戏数据帧（一幅幅游戏图像），使用深度强化学习在游戏上通关。《Human-level control through deep reinforcement learning》是对上一篇论文的改进，2015年发表于nature。

一、强化学习的基本原理

1.什么是强化学习

我们给出一堆红苹果和青苹果的照片（每张照片中只有一个苹果），通过图像识别能够辨别图片中苹果的红绿，因为我们事先已经对苹果的照片进行了标注。比如红苹果标记为1，青苹果标记为0，机器从我们事先标记的照片中学得信息，再用于别的苹果照片（监督学习）。但是这样存在一个问题，这些苹果的初始标注是怎么来的，没有初始标注如何学习标注同类物体的能力？我们人类在与环境不断的交互，不断的进行试错才学习得到辨别物体的能力。强化学习能从无标注的某类物体中学习知识，并能由此采取利益最大化的决策。
强化学习与我们人类的学会走路方式相似，一开始跌跌撞撞，在摔倒这个疼的环境反馈下，我们走下一步会越来越好。作用机制如下图所示，我们先观察环境状态(state)，然后采取行动(action)，获得反馈（reward）。通过上一步的行动，我们进入新环境，根据reward中学到的知识采取下一步动作。可以这么认为，强化学习就是智能体（agent）在与环境的交互过程中通过学习策略以达成回报最大化或实现特定目标的过程。

2.强化学习的要素

（1）环境状态$\mathrm{S}$，$t$时刻环境状态为$S_t$。
（2）个体(例子中是人，也可以是其它，通常称为agent智能体）的动作A，$t$时刻采取的动作为$A_t$。
（3）环境的奖励的$\mathrm{R}$，$t$时刻在环境状态$S_t$，采取$A_t$动作,获得的奖励$R_{\mathrm{t}+1}$(某个动作采取后，下一时刻才能获得回报）。奖励可为正奖励和负奖励（惩罚）。
（4）个体的策略(policy)π，是个体采取动作的根据。$\pi (a|s)=P(A_t=a|S_t=s)$表示在$t$时刻状态$S_t$下，个体根据π策略采取动作$A_t$的概率，一般最大概率动作就是我们采取的下一步动作。
（5）个体在策略π和状态$\mathrm{S}$时，采取行动后的价值（value），一般用$v_{\pi }(s)$表示。虽然我们已经有了一个延时奖励$R_{\mathrm{t}+1}$，但是很多情况下我们不能仅仅只看当前的回报。比如我们的目标是让我们生活舒适，现在我们拿了一万块钱工资，前几天大吃大喝会让我们相当舒服，但后边的日子就会相当难受。即我们不能仅仅考虑下一步的奖励，还得考虑后续的奖励。$v_{\pi }(s)$可用公式表示：

$$v_{\pi }(s)=E_{\pi }(R_{t+1}+\gamma R_{t+2}+\gamma 2R_{t+3}+...\mid S_t=s)=E_{\pi }(R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s)$$

$E_{\pi }$表示的是后n步的数学期望；$\gamma$是奖励衰减因子，在[0,1]区间。$\gamma$=0为只考虑下一步的贪心算法，$\gamma$=1后续n步和下一步的同等重要。$\gamma$一般取(0,1)，表示下一步的奖励最重要，但是其他后续奖励同样不可忽略。
（6）动作价值函数$q_{\pi }(s,a)$，表示在每个状态s下采取动作a带来的价值影响，计算公式如下：
$$q_{\pi }(s,a)=E_{\pi }(G_t|S_t=s,A_t=a)=E_{\pi }(R_{t+1}+\gamma R_{t+2}+\gamma R_{t+3}+...|S_t=s,A_t=a)=E_{\pi }(R_{t+1}+\gamma {\mathrm{q}}_{\pi }(S_{t+1},A_{t+1})|S_t=s,A_t=a)$$
（7）状态转换机，在状态s下采取动作a,转到下一个状态s′的概率，表示为${\mathrm{P}}_{s{s}^{\prime }}^a$。
（8）探索率?，我们在行动时一般会采取最有利的，但是这样也会导致一些陌生的行动方式没有被我们考虑到。此时我们有一定的概率采取别的行动，该概率为?。一般来说，随着时间推移?会越来越小，表示我们的行动已经逐渐利益最大化，采取别的行动对我们效益逐渐减小。

3.计算方法

实际中，强化学习的建模非常复杂，需要引入马尔科夫过程。我们假设某个状态s转移到下一个状态s’不与之前的状态产生关系，即某一状态仅与上一状态有关（马尔科夫性）。
在状态s下采取动作a，转移到下一个状态s’的概率计为${\mathrm{P}}_{s{s}^{\prime }}^a$，用公式表示为：
$${\mathrm{P}}_{s{s}^{\prime }}^a=E(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$$
假设在状态s时采取动作仅与当前状态s有关（同样是马尔科夫性），公式表示为：
$$\pi (a|s)=P(A_t=a|S_t=s)$$
根据动作价值函数$q_{\pi }(s,a)$和状态价值函数$v_{\pi }(s)$的定义，容易得到他们之间的转化关系公式：
$$v_{\pi }(s)=\sum _{a\in A}\pi (a|s)q_{\pi }(s,a)$$
反过来，我们也容易得到状态价值函数$v_{\pi }(s)$表示动作价值函数$v_{\pi }(s)$:
$$q_{\pi }(s,a)=R_s^a+\gamma \sum _{s\prime \in S}{P}_{ss\prime }^a{v}_{\pi }(s\prime )$$
其实两个公式可以用一句话概括：某一个状态的价值可以用该状态下所有动作的价值表述；某一个动作的价值可以用该状态后续状态的价值表达。
价值函数$v_{\pi }(s)$公式的变体:
$$v_{\pi }(s)=\sum _{a\in A}\pi (a|s)(R_s^a+\gamma \sum _{s\prime \in S}{P}_{ss\prime }^a{v}_{\pi }(s\prime ))$$
动作价值函数$v_{\pi }(s)$的变体：
$$q_{\pi }(s,a)=R_s^a+\gamma \sum _{s\prime \in S}{P}_{ss\prime }^a\sum _{a^{\prime }\in A}\pi (a^{\prime }|s^{\prime })q_{\pi }(s^{\prime },a^{\prime })$$

4.最优价值函数

强化学习的关键在于找到一个最优策略，让智能体与环境的交互过程中获得最大收益，我们记这个最优策略为${\pi }^{?}$。
寻找最优策略也就是找最优价值函数，我们记录该函数为$v_{?}(s)$，计算方法如下：
$$v_{?}(s)=\underset{\pi }{\max }{v}_{\pi }(s)$$
同理可得最优策略函数:
$$q_{?}(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a)$$
最优策略，基于动作价值函数我们可以定义为：
$${\pi }_{?}(a|s)=\{{}_{0\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}}^{1ifa=\underset{a\in A}{\mathrm{argmax}}q?(s,a)}$$
利用状态价值函数和动作价值函数之间的关系，可得最优状态价值函数：
$$v_{?}(s)=\underset{a}{\max }{q}_{?}(s,a)$$
反过来，最优动作价值函数为:
$$q_{?}(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in s}{P}_{s{s}^{\prime }}^a{v}_{?}(s^{\prime })$$
最优状态价值函数$v_{?}$公式的变体:
$$v_{?}(s)=\underset{a}{\max }(R_s^a+\gamma \sum _{s^{\prime }\in s}{P}_{s{s}^{\prime }}^a{v}_{?}(s^{\prime }))$$
最优动作价值函数$q_{?}(s,a)$公式的变体：
$$q_{?}(s,a)=R_s^a+\gamma \sum _{s^{\prime }\in s}{P}_{s{s}^{\prime }}^a\underset{a^{\prime }}{\max }{\mathrm{q}}_{?}(s^{\prime },a^{\prime })$$

5.应用举例

状态转换图如下，设置左上、左边、中间和右边的圆圈分别为v1、v2、v3、v4，正方形为m。现在的任务是求v2到m的R之和最大化的路径。

为了方便，我们假设衰减因子$\gamma =1$,$\pi (\mathrm{a}|\mathrm{s})=0.5$。
基于公式$v_{\pi }(s)=\sum _{a\in A}\pi (a|s)(R_s^a+\gamma \sum _{s\prime \in S}{P}_{ss\prime }^a{v}_{\pi }(s\prime ))$，可以列出方程组：
v1位置：v1=0.5?(?1+v1)+0.5?(0+v2)
v2位置：v2=0.5?(?1+v1)+0.5?(?2+v3)
v3位置：v3=0.5?(0+0)+0.5?(?2+v4)
v4位置：v4=0.5?(10+0)+0.5?(1+0.2?v2+0.4?v3+0.4?v4)
解出这个方程组可以得到v1=?2.3,v2=?1.3,v3=2.7,v4=7.4, 即每个状态的价值函数如下图：

此时我们通过$v_{?}(s)$和$q_{?}(s,a)$价值公式(即每次都走最优路径，然后更新v和q），不断迭代可得到如下最终状态图，理想路径为v2->v3->v4->m。

二、深度强化学习

1.价值函数的选择

我们许多任务都通过深度学习来完成，比如图像识别和语音处理。但强化学习在之前适用于单一领域（特征手工提取）或低维数据，难以应用在高维数据领域(图像或语音等）。
难以应用的一个重要原因是价值函数难以确定，我们往往只能手工设定，无法保证准确性。自然而然有了用神经网络去拟合价值函数的想法，而这也是DeepMind论文的重点。
用神经网络预测价值有三种常见方式，如下图所示。第一种方式(左边网络)，我们输入当前状态得到当前状态的状态价值；第二种方式(中间网络)，输入状态和动作，输出动作价值；第三种方式(右边网络)，输入状态，输出每个可能动作的动作价值。

论文采用第三种方式，如下图，我们输入一张图片，输出所有可能动作的价值。其中箭头表示向某个方向移动；红色的点可以表示为射击或跳跃，不同游戏组合状态不一定相同。

2.价值函数参数的更新

一般而言，游戏角色存活越久其相对得分越高。以下图游戏为例，飞机有向敌军射击和向某一边移动两种动作，我们飞机存活的越久，得分也相应越高。

那么相应得出一个想法结论，我们设计目标价值函数时，当下一状态我们的飞机为毁灭状态，设置价值回报较低，即可达到有效更新网络的目标。记当前状态价值为$Q({\phi }_j,a_j;\theta )$，采取最优策略后下一状态价值为$Q({\phi }_{j+1},{a_{}}^{\prime };\theta )$。则我们的目标价值计算方法如下图所示($r_j$表示得分变化，比如我们多活一个状态就加1分)，当我们飞机下一状态被击毁时，价值为$r_j$，此时价值最小，表示游戏结束。我们定义损失函数为$(y_j?Q({\phi }_j,a_j;\theta ){)}^2$，通过与最小价值状态的交互，网络可不断收敛。

3.总体设计

解决了大问题，仍存在许多其它困难。
主要困难：

1. DL需要大量带标签的样本进行监督学习；RL只有reward返回值，而且伴随着噪声，延迟（过了几十毫秒才返回），稀疏（很多state的reward为0）等问题。
2. DL的样本独立；RL前后状态相关。
3. DL目标分布固定；RL的分布一直变化。比如玩一个游戏，一个关卡和下一个关卡状态分布不一致，所以我们通过一关训练的网络，到下一关又要重新训练。
4. 过往的研究表明，使用非线性网络表示值函数出现不稳定等问题。

解决办法：

1. 深度强化学习使用reward来构造标签，解决回报延迟问题(对应问题1)。
2. 通过经验池的方法解决RL前后状态相关和分布固定的问题(对应问题2和3)。我们把曾经放入训练的数据，训练后的结果和下一状态数据投入经验池，然后再从经验池随机取数据。也就是说我们不再像以前一样一关关的训练，而是不断存放我们训练过的片段，再随机抽取，零碎的训练。这部分和人类回忆机制相关联，在2015年的nature论文中甚至介绍了该机制和大脑海马体的相似之处。
3. 引入target-netword(对应问题4)，目标网络不再实时更新，而是每过一段时间将价值网络的参数复制给它。也就是说目标网络和价值网络架构完全一致，只是为了防止目标和价值关联过于亲密，而通过分隔赋值的方法，这也是2015的nature论文对2013的nips论文改进的一个地方。此处可以举一个简单的例子，有一个跳水运动员在进行训练，裁判进行评分，跳水运动员根据裁判的评分改进自己的动作。但是一开始我们并没有裁判，那该怎么办呢？我们将跳水运动员的知识灌输到一个和跳水运动员长得一模一样的克隆体身上，让他当裁判。一开始跳水运动员每次训练完，教练评完分，跳水运动员就马上将自己学到的知识传给教练。这相当于每次运动员训练完，教练马上改指标，会出现一个人既当教练又当裁判的问题，这样无法保证公平性。所以我们每隔一段时间再把运动员训练完的感悟传给教练，教练在这一段时间内评分标准不变，就可以保证公正性的问题了（后期强化学习的Actor-Critic也与之相似，但是Actor和Critic分开的更彻底）。

主要困难解决后，引入具体算法流程：
初始化replay memory D(记忆回放，也叫经验池)，容量为N用于存储训练的样本。
初始化行为价值网络函数Q的卷积神经网络，参数$\theta$随机初始化。
初始化target行为价值网络函数的卷积神经网络(简写为target-Q)，结构和Q相同，参数${\theta }_{?}$初始等于Q的参数$\theta$。
For episode=1,M do（总共训练M个回合）
初始化状态序列s1，并对其进行预处理得到4*84*84的视频帧（处理过程简写为${\phi }_1=\phi (s1)$，4代表输入数据是最后四帧，84*84表示输入图片大小）
for t=1,T do（一次最多训练T个时间片的数据，防止落入局部最优解）
以概率?（探索率）选择一个一个随机动作$a_t$，否则选择最优价值动作（此处?是衰减的，可以认为是模拟退火算法的退火率，时间越长现有网络越好，落入局部最优解概率越小，探索其它区域的概率也应越小）
执行动作$a_t$可以得到奖励$r_t$以及新图像$x_{t+1}$（比如我们让飞机向上飞，$x_{t+1}$是飞行完后的游戏图像）。游戏往前移动一帧，依然是4帧的图像，再次处理得到新的网络输入。
把（${\phi }_t$，$a_t$，$r_t$，${\phi }_{t+1}$）数据放入经验池D。
从经验池中随机抽取小批次（${\phi }_t$，$a_t$，$r_t$，${\phi }_{t+1}$）数据用于下一次训练。
使用target-Q得到目标价值$y_j$，利用损失函数$(y_j?Q({\phi }_j,a_j;\theta ){)}^2$计算loss，反向传播训练网络。
每迭代C次，将Q网络的参数复制给target-Q网络。
end
end
下图是nips论文的算法流程，nature对此进行了改进：

总结：论文构建一个全新智能体，构建深度学习Q和target-Q网络，能从高维数据中学习到知识，进行端到端的强化学习训练。在2013的NIPS论文，作者将该方法应用于7款雅达利游戏，它在其中6个游戏上优于所有之前的方法，在3个游戏上超过了人类专家。2015的nature论文，作者将该方法用于49款游戏，它在43款游戏中表现出超于之前所有强化学习算法，超过一半的游戏中智能体玩游戏的能力高于75%的人类。表现出RL强大的学习能力。