潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五) 编者按：本文节选自《深度学

编者按：本文节选自《深度学习理论与实战：提高篇》一书，原文链接http://fancyerii.github.io/2019/03/14/dl-book/ 。作者李理，环信人工智能研发中心vp ，有十多年自然语言处理和人工智能研发经验，主持研发过多款智能硬件的问答和对话系统，负责环信中文语义分析开放平台和环信智能机器人的设计与研发。

以下为正文。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

本文介绍n步方法、TD-λ、Eligibility Trace和函数近似。

更多本系列文章请点击强化学习简介系列文章。更多内容请点击深度学习理论与实战：提高篇。

n步方法

MC方法是用Episode结束时的回报来作为更新目标，而TD(0)使用一步之后的回报来作为更新目标：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

根据上面的推广，我们可以定义n步回报(n-step Return)为：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

这些方法的backup diagram如下图所示。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：n步方法的backup diagram

有了n步回报之后，我们就可以n步TD学习算法的更新公式： Vt+n(St)←Vt+n?1(St)+α[Gt:t+n?Vt+n?1(St)],0≤t

下面是不同的n在一个19状态的Random Walk（由于篇幅，本书不介绍这个任务）中的对比效果如下图所示，可以看出n=1(TD)和n很大(MC)的效果都不如中间的某个n好。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：n步方法的比较

有了n步的预测，再加上ε-贪婪的策略提升，我们就可以实现n步的On-Policy策略n步SARSA算法。由于篇幅，我们就不讨论具体的算法了。同样的我们也可以使用重要性采样方法得到n步的Off-Policy算法。

TD-λλλ-回报

前面我们介绍了n步回报，不同的n有不同的效果，那么还有一种方法就是把多个n步回报进行加权平均。比如我们可以把2步回报和4步如图回报加权平均起来：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

我们甚至可以把无穷多个n步回报加权平均起来，而λ-回报就是一种无穷多个n步回报的加权方式。无穷多个怎么加权呢？

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：λ-回报

如上图所示，我们把无穷多个n步回报加权平均起来（因为当n大于T的时候， Gt:t+n就等于真实的回报Gt了。所有后面无穷项的系数都累加起来是λT?t?1 ，读者请先接受这个数字，我们后面会证明它。

从图中可以看出， 1步回报的权重是1?λ ， 2步回报的是(1?λ)λ ， 3步回报是(1?λ)λ2 ， … ，一共有无穷项：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

我们首先证明这无穷项的和是1 。这需要一个简单的无穷级数公式：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

有了这个公式之后，我们就能计算所有回报的系数和：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

注意，因为当n=T-t及其以后Gt:t+n就等于真实的回报Gt了（因为到了Episode结束）。所以从n=T-t之后的项的回报是相同的，所以可以把后面无穷项合并起来：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

因此从n=1到T-t的n步回报的权重分配如图下图所示。这样，我们可以把Gtλ写出有限项的和：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：λ-回报的权重分配

有了λλ-回报的计算公式之后，我们就可以用它得到TD-λ算法的更新目标，从而就可以进行预测了。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

这就是著名的TD-λλ算法了，根据这个算法， Gerald Tesauro在1992年设计了TD-Gammon程序，它会学习西洋双陆棋(backgammon) ，并且达到了人类顶尖高手的水平。

注意zhong这种TD-λλ算法是所谓的前向视角(Forward View)得出的，和MC一样，它要等到Episode结束才能计算，而且不能用于非Episode的任务。

另外，我们看一下λ的两个特殊值， λ=0λ=0和λ=1λ=1的特例。根据公式，当λ=0λ=0时，第二项是零，第一项只有当n=0时的系数是非零的1 ，因此变成了TD(0)算法。当λ=1λ=1时，只有第二项，因此变成了MC算法。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：Forward View

Eligibility Trace

到这为止前面所有介绍的方法都可以归为Forward View的算法，在t时刻我们往前看一步或者多步，然后得到更新的目标。如上图所示。接下来我们会介绍另外一种视角Backward View 。我们首先需要介绍一个概念Eligibility Trace ， Backward View的算法大部分都是基于这个概念。

我们来看一个Credit分配的问题（其实强化学习的本质就是要判断很久以前的某个行为/状态对未来的影响大小，当然机器学习也是分析哪些因素是某个事件发生的重要原因，但是强化学习的难点在于行为会改变未来），如下图所示，有两个行为响铃和开灯，最终导致电击事件的发生。那到底是那个行为造成的呢？也许你会说是响铃，因为响铃了很多次，根据经验，如果某个事件发生前经常有另一件事情发生，那么它们很可能存在某种联系。但也许会有人说是灯光导致电击的发生，因为它就在电击事件的前一刻发生，根据经验，离某个事件越近的事件越有可能是诱因。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：Credit分配问题

那到底哪种说法正确呢？两种都对！因此我们在分配Credit的时候要同时考虑这两个因素。把这两个综合起来就可以得到Eligibility Trace:

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

根据上面的公式， Et分为两部分，一部分来自之前的Et?1 ，但是会衰减成原来的λ倍（γ是打折因子，这里暂不讨论）；另外一部分就是当前状态是否是s 。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：Eligibility Trace示例

我们来看上图，开始是E(s)是0 ，然后连续4次St都是s ，因此E(s)不断增加，接着的状态都不是s ，因此E(s)逐渐衰减，然后又有两次的状态是s ， … 。因此我们可以把Et(s)看成状态s对于最终的结果的“责任” ，有点像之前反向传播算法的错误δδ 。这样我们就可以得到backward view的TD-λλ算法的更新如下：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

这个算法和之前的forward view实现不同，它不需要等到Episode结束就可以更新V(s)了。更新的量是δt乘以Et(s)再乘以学习率α 。因此如果Et(s)很大，那说明状态s的“责任”也很大，因此它需要更新的比较多。那些状态的s对应的Et(s)大呢？显然如果St=s ，那么它会较大，另外如果在这之前的Si=s ，那么也会有非零的值，但是i距离t越远，衰减的就越多。如果在t时刻之前状态s完全没有出现过，那么E就是0 。因为是根据当前的错误往前找“责任” ，所以就是所谓的backward view ，如下图所示。

注意：上面公式会对所有的状态都进行V(s)的更新，而不(只)是更新V(St) ，当然如果Et(s)=0 ，那么时间更新量是零。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

图：Backward View

这看起来有些道理，但是这种方法怎么就和前面的forward view是一样的效果呢？下面我们来简单的验证一下。首先来验证一种特例，当λ=0时：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

也就是只有St会有更新，其余的状态的Et(s)都是0 ，所有上式就是：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

这正是TD(0) 。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

Backward View和Forward View等价定理

这个定理我们不做证明，但我们需要“读懂”它的意思。 offline更新指的是等到一个Episode完成之后做一次更新，而不是每一步都更新，与之相反的是online更新。我们通过一个例子来说明其中的区别，假设一个Episode是：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

那么算法会对状态s更新两次，对t更新一次。如果是online的，第二次计算使用的是第一次的结果来更新：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

这里的δ1会依赖于V1(s) ， δ2会依赖于)V2(s) 。最终的效果是：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

而offline更新公式是一样的，但是δ1δ1和δ2δ2都只依赖于V1(s)V1(s) 。

关于定理，另外一点就是公式里的s是Episode里出现的所有状态。这其实s是Forward View和Backward View的区别。 Forward View在每一个时刻t只更新一个状态St的V值，因为t会影响所有后面的状态，所以它要往前看知道终止时刻T ，而Backward View一次更新所有的状态。因此offline的算法可以根据最初的值计算每个时刻的错误δt ，然后累加起来就是整个Episode对状态s的更新。

我们不证明(验证)这个定理，但是验证一个特例(λ=1) 。假设一个Episode状态s只出现了一次，并且出现在时刻k 。根据Et(s)的公式：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

因为s只在时刻k出现一次，因此k时刻前E(s)都是0 ，而k时刻是,k+1时刻是γγ ， … 。根据前面TD(1)的Backward View的算法，我们可以计算到Episode结束时关于状态s累积的错误是：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

首先我们看一下上个公式的第一个等号就是代入，最后一个等号的部分就是MC的δ 。如果第二个等号成立，那么就说明TD(1)和MC是等价的。之前的Forward View我们已经说明了MC和TD(1)是等价的，如果MC又和TD(1)的Backward View等价，那么就证明了TD(1)的Forward View和Backward View是等价的，我们来证明一下第二个等式∑t=kT?1γt?kδt=(Gk?V(Sk))如下（为了之前的习惯，我们把k换成了t）：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

上面的每一行的最后一列和前以后的第二列抵消掉，只剩下第一列，第二列的最后一个的γT?tV(ST)和第三列的第一个?V(St) 。因为V(ST)=0 ，所以就得到上面的结果。

上面只是证明了一个状态s ，因此TD(1)的Backward View是和First-Visit MC大致等价的。不完全等价的原因是MC方法是Online更新的。也存在和Online的TD Backward View的算法，它和Online的Forward View等价，我们这里不介绍了。

函数近似(Function Approximation)

前面我们介绍的都是表格(Tabular)的方法，比如Q(s,a) ，我们可以把状态看成行， action看成列，则这个表格的大小是 |S|×|A| 。这种方法只能解决状态和action空间是离散而且比较小的问题。但是很多实际的问题的状态空间和action空间都是很大甚至是连续的空间。比如我们让Agent玩一个视频弹球游戏，状态是当前时刻和之前时刻(为了能表示弹球的速度)的两帧图像。假设图像大小是80x80 ，图像是RGB的，那么状态空间的大小是256^(3×80×80) ，存储这么大的空间是不可能的。而且即使能够存下，训练时模拟的Episode也不能每种状态都见过。

对于连续的状态空间，我们可以通过量化把它变成离散的空间，比如后面我们会用到的gym里的MountainCar ，如下图所示。它的状态包括两个连续值，位置和速度，速度的范围是(-0.07,0.07) ，位置的范围是(-1.2,0.6) ，我们可以把这个范围均匀的切分为40个区间，每个区间的大小分别是0.0035和0.045 。

但是怎么量化本身就是一个复杂的问题，量化的区间太大，那么就会丢失信息，而量化的区间太小，就会使得状态空间爆炸。而且有的值不是均匀分布的，某些范围可能要用比较精细的划分而另外的范围不需要精细的划分。

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

mountain car

对于连续的复杂的问题，更好的办法是使用一个函数来近似这个表格，这就叫做函数近似方法。比如把Q(s,a)表示为参数w的函数Qw(s,a) 。这样不过|S|×|A|有多大，它的实际存储和计算只取决于参数ww和模型结构(简单的线性模型还是复杂的多层神经网络) 。

使用函数近似Q(s, a)还有一个好处就是它的泛化能力会增强，比如我们在模拟学习的时候可能没有经历过状态(0.53, 0.12) ，但是我们有类似的状态(0.54, 0.11) 。如果根据表格的方法，状态(0.53, 0.12)的值函数是未知的，但是使用函数之后就能计算出它们有近似的Value(通常的模型都是连续的函数) 。

我们来看一个简单的函数近似方法，使用函数来近似状态值函数vπ(s) ，假设函数为v^(s,w) 。那么我们可以把普通的MC求vπ(s)的方法改造成函数近似的算法：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

使用函数近似的MC算法

“真实”的Value可以用采样的Gt来近似，因此我们需要让函数v来近似Gt ，我们可以定义类似的loss函数为1/2||Gt(St)?v(St,w)||^2 ，因此对上式求梯度就得到?[Gt?v^(St,w)]?v^(St,w) ，然后使用类似梯度下降的方法乘以步长α就得到上面的更新公式。

当然，我们也可以使用TD来作为Value的近似，只需要把参数更新公式改为：

----潮科技行业入门指南 | 深度学习理论与实战：提高篇（19）—— ?强化学习简介(五)//----[ http://www.caoding.cn]

注意：TD需要计算v(St)和v(St+1)的Value ，这里用v(St和v(St+1来近似。

对于Q(s) ，输入是状态s ，输出是value；对于Q(s,a) ，输入是状态s和行为a ，输出是value 。如果行为a的空间有限比如是m个值，那么也可以采用如下图右所示的方式，让函数的输入是s ，输出m个值分别表示Q(s,a1),…,Q(s,am) 。这样做的好处是一次可以计算出多个Q(s,a) ，比如在Q-Learning中，我们需要计算maxaQ(s,a) ，需要计算状态s下采取所有不同action中得分最高的，那么这种方法就可以一次算好。