强化学习经典入门书的读书笔记系列-第九篇（1）
注1：该篇文章的内容，基本等同于专栏之前发的“函数逼近思想”。此次稍作修订发出，是为延续强化学习读书笔记系列文章，使新老读者可以重新跟着该系列继续阅读学习。望大家都能发现“强化学习”这个领域的研究乐趣。
注2：该读书笔记系列文章的参考书籍，先更改为2018年最新版“Reinforcement Learning: An Introduction”，下载地址：http://incompleteideas.net/book/bookdraft2018feb28.pdf
在开始这一篇内容之前，让我们先回顾一下前8篇所提及的内容。概括地说，前八篇所讲到的各种强化学习方法（DP、MC、TD等），有一个共同套路：即采用数据表存储每一个状态（state）的价值量（value），然后用不同的方式更新这些状态的value，直至收敛；最后根据每个状态下不同动作（action）对应的value，决定应该选择哪个状态，也就是确定了策略（policy）。尽管不同的方法之间有些小的差异，但是从本质上看是相似的。
但是从本篇开始提及的“函数近似”方法，却在本质上有了几个重大改变，也因此有了一些突出的特点。首先要说明的是：“函数近似”更像是一种思想，包含一类方法，从后面的章节就能看出来，基于这个思想，可以衍生出很多不同类型的方法。同时，该方法也正式把强化学习和机器学习联系起来，让我们可以互相借鉴两个领域的一些优势。
那么，函数近似这类方法，有什么改变？第一、对状态的价值量（value）的存储使用函数来表征，不再用数据表。第二、采用机器学习中流行的有监督训练方式来更新函数的固有参数，直至函数收敛。一旦函数训练完成，我们就自然得到了“状态x”–“状态价值量y”之间的映射关系，然后由状态价值决定策略就是顺理成章的事了。这两个改变也相应带来了显著的特点：第一、函数近似方法不需要大量的存储空间来存状态，因为函数的参数个数通常远远少于环境状态的数量（深度神经网络也许是个例外）；第二、训练出来的函数具备一定的泛化特性（这也是机器学习方法的常见特性），可以应对部分可观测的环境，这对在实际问题中应用强化学习方法是个好事，因为很多时候我们是无法穷尽所有状态的。
下面开始正式介绍这一类方法。
1 函数近似思想
1.1 什么是“函数近似”思想？
采用某种函数（线性函数或者非线性函数等等），基于小部分训练样本，来拟合价值函数的真值，比如或，使之在较大规模的测试样本上同样适用。这种思想的主要任务就是求该函数的最优参数。
1.2 为什么引进“函数近似”思想？
（1）数据表形式的价值函数有缺陷。
到目前为止，我们对强化学习问题的讨论，都局限于tabular的形式，也就是采用一张表来存储当前任务的价值函数。这张表，可以理解成python里面的字典结构，任务中所有的“状态/状态-动作”作为keys，每个“状态/状态-动作”的价值作为values。为什么这种数据表形式的强化学习会限制强化学习问题的规模呢？有如下两个原因：1、内存空间。当问题规模超大时，存储这么一张表需要的内存空间是巨大的。2、计算时间和所需数据量。当问题规模变大后，再想准确地计算这张表中的每个值，需要的时间开销是巨大的；同时，在很多实际任务中，有些状态和动作是永远不会出现的，这就导致价值函数很难准确计算。
上面这番文字提到的问题，简单总结后，就是四个字：泛化问题，即在小规模数据上获得的经验，怎么才能够在大规模的数据上也适用？
（2）参数方程形式的价值函数可以解决上述泛化问题
使用函数近似的思想，我们只需找到一组最优的参数，也就确定了最优的拟合函数。这个拟合函数既不需要存储大量的状态价值信息，也不要求看到整个状态-动作空间。只要它的参数包含了整个状态-动作空间背后的规律，那么它就可以在任何情况下都表现良好，也就是泛化能力好。
1.3 需要注意的问题
函数近似思想来源于传统的机器学习问题。将这种思想移植到强化学习问题中，自然会带来一些问题。这是因为强化学习中存在很多传统机器学习没有的特点，比如：非稳定性（包括状态分布和奖励分布的不稳定性），自举性（bootstrapping），目标的延后性。在将函数逼近思想融合到强化学习的过程中，这些问题都要考虑到并做出相应改进。
1.4 如何用函数近似思想解决on-policy prediction问题？
我们知道强化学习中存在on-policy和off-policy之分，也存在prediction和control问题之分。事实上，on-policy和off-policy的本质区别在于，更新某状态的价值量时，所使用的方法是沿用既定的策略（on-policy）还是使用新策略（off-policy）。而prediction和control问题的本质区别在于所估计的是状态价值函数，还是动作价值函数。其实这就是几种相似但又有少许不同的问题，我们本篇就从on-policy的prediction问题入手，看看函数近似思想怎么应用。
既然函数近似思想来源于传统机器学习，那么其主要步骤也跑不了机器学习那一套。在函数近似思想的定义中我们提到“这种思想的主要任务就是求该函数的参数”，如何求？分为以下三个步骤：
（1）确定价值函数的拟合模型
（2）确定待优化的目标函数
（3）确定参数的更新算法
这三个环节层层递进，初步给出我们解决on-policy prediction问题的框架，下面分别讨论。
2 确定价值函数的拟合模型
2.1 价值函数的参数方程表示
在前面几章，价值函数都是采用数据表的形式存储，一个萝卜一个坑。从这一章开始，我们开始采用参数方程的形式表示价值函数，写法：。该写法表示当权重向量为时，状态s的价值近似值。比如：可以是关于状态特征的线性函数，的每个元素表示每个特征的权重；还可以是通过神经网络建模得到的非线性函数，表示神经网络中神经元之间的连接权值。通过改变，我们可以得到各种各样的拟合函数。一般来说，的元素个数远远少于状态的数量。每改变的任意一个元素，都会影响很多状态价值的估计量。
2.2 确定训练样本
既然“函数近似”属于监督学习的技巧，那么必然需要构造训练样本，包括输入和输出。回忆一下我们之前在处理prediction问题时，总是会提到“反向更新”这个词，也就是backups。比如在蒙特卡洛算法中，backup过程是,也就是说，状态的value向着的方向更新，叫做，也叫做target；同理在TD(0)算法中，反向更新过程是：。
于是我们自然就想到，可否把反向更新中的作为一条训练样本的input和output。这种形式的样本表明状态s的价值估计应该更倾向于v，而我们最终想要得到的拟合函数，其特点也应该是倾向于把状态s的价值估计为v。因此我们确定将反向更新中的作为训练样本。
2.3 拟合模型的选择
确定了训练样本之后，原则上我们可以选择任何类型的监督学习模型来拟合训练样本。但是并非所有模型都合适，为什么呢？这就需要我们研究一下强化学习任务的特点。
强化学习任务需要实时在线学习，一边和环境交互一边学习。因此需要一个效率很高的模型，可以不断接收新增的训练样本进行快速学习。
强化学习任务需要处理”非稳态目标函数”问题。这个怎么理解？在强化学习中，特别是按照GPI流程（见第四章动态规划的4.6部分）进行value function和policy更新的情况下，经常随着变化，于是我们就要不断地逼近这个变化的。另外，就算不变，那么通过bootstrapping方法（比如DP中就用到）所产生的训练样本的目标价值也是非稳定的，同一个state，可能其目标价值是多个。
强化学习问题的上述两个特点和传统机器学习问题有所不同，因此我们选择的函数拟合模型必须得能够应付这两个特点的任务。
我们在这里先不提出具体的模型，只说明模型的必要特点，在下一篇第二部分中会讨论具体的模型。
3 确定待优化的目标函数
3.1 为什么建立目标函数
我们知道，在机器学习中，为了得到一个准确的模型，需要时刻监控该模型的训练演化过程，确保模型往好的方面进化。什么是好的方面？怎么确保呢？通常都是针对具体的任务，建立合适的目标函数（有时也叫损失函数），通过保证模型的更新始终朝着使损失函数不断减小的方向，最终可以得到一组满意的模型参数。
之所以之前我们从没设立过明确的目标函数，是因为采用数据表存储价值函数时，不需要这么一个目标函数，因为价值函数经过不断学习迭代，最终可以自动趋于收敛，得到真实值。此外，数据表存储方式下，每个状态的价值更新过程呈相互解耦关系：即A状态的价值更新后，并不影响B、C状态的价值，因为数据表的每个区域是相互隔离的。
但是，通过函数近似思想进行价值函数的估计时，这种解耦关系被打破了：A状态的价值更新后，会导致模型参数发生变化，从而间接影响其他状态的价值，因此不再有可能使所有状态的价值都达到真实值。
所以，需要制定一个目标函数，这个目标函数，决定哪些状态我们更在乎，哪些状态我们不在乎。更在乎的状态，适当提高它的价值估计精确度；不在乎的状态，适当降低它的价值估计精确度。
3.2 确定目标函数
用数学语言做上面那件事，就是定义一个概率分布,表示对每个状态价值准确度的在乎程度。同时我们用价值近似值和真值的均方差作为误差的定义。结合这两部分，我们定义目标函数如下：
MSVE全称“Mean Squared Value Error”，均方价值误差。
这里再说一下的数学含义：通常表示在目标策略下，花在状态s上的时间占总时间的比例。这时叫做“on-policy distribution”。在离散序列任务中，略有不同，不能严格地叫做“概率分布”，因为离散任务中初始状态的选择会对该分布造成一些影响。因此我们也给出离散序列任务下的定义：
其中h(s)表示状态s被选中作为初始状态的概率分布。
需要提醒大家的是，MSVE并不一定是最好的评价指标，因为我们最终的目的是利用价值函数的估计值找到最优的policy，而满足这个目的并非一定需要最小化MSVE。但是目前也并不清楚有啥更好的指标，因此还是继续选用MSVE。
3.3 求解目标函数
既然目标函数是某种误差，那么求解该函数，就是使其值变得越小越好。为了最小化MSVE，其实我们要做的就是找到全局最优解，也就是找到一个特定的，使其满足:
值得注意的是，对于简单的线性模型，这个或许容易找到，但是对于复杂的非线性模型，比如神经网络或者决策树，这个很难得到。因此在复杂非线性模型中常用的替代方案是“寻找局部最优解”，也就是找到一个，使其满足：
至此，我们介绍了基于函数近似思想拟合价值函数，进而解决强化学习问题的大框架。
从下一节开始，我们开始讨论具体的参数更新算法。这些方法主要是基于梯度下降理论。
4 确定参数更新算法
为了找到最优的参数，需要从一开始的初始值向着最优值不断迭代更新。有哪些迭代更新的算法可以采用呢？
4.1 随机梯度方法
接下来我们要讨论的参数更新算法主要基于随机梯度下降理论（SGD）。SGD方法在参数更新中的运用极其广泛，并且这类方法恰好也很适合实时在线的强化学习任务。
在梯度下降理论中，，价值拟合函数是定义在
上，关于的光滑可微函数。我们会在整个训练过程中的每个离散时间点上更新，因此我们需要一个新符号表明在每一个时间点t上的。
接下来，假定在我们的训练样本中的状态分布和上一节在MSVE那里定义的分布相同。现在我们开始着手更新，很明显的一个方法就是在观测到的训练样本上尽可能地减小误差。SGD方法会在每个随机训练样本上按照MSVE误差减小的方向更新。这里我们会用到常见的梯度运算符，关于梯度的含义我在此就不赘述了，可以查看大学数学课本。
总之，的更新如下式：
从上式可以看出，的更新量方向是沿着MSVE误差的负梯度方向的，根据梯度的定义，这个方向也是误差下降最快的方向。另外表示步长参数，控制着每次更新的幅度。
可能读者会有疑问，为什么要SGD每次沿误差方向更新一小步，而不是直接彻底消除误差呢？原因是：我们既不想要也不期待最终的价值函数能在所有状态上的误差全部为0。我们想要的是价值函数可以在不同状态的误差幅度之间获得某种平衡。如果我们在每一个观测到的状态上都彻底消除误差，那么就会发现会不断震荡，永远也找不到局部最优了。事实上，根据第二篇提到的“标准随机近似条件”，步长参数需要随着时间而不断减小的，只有满足了“标准随机近似条件”（见第二章多臂赌博机下 2.5部分），梯度下降法才能保证收敛到局部最优解。
现在我们要讨论一个很重要的问题：训练样本的output部分，即中的，如果不是真实值，怎么办？这在实际任务中很常见，因为很可能是被噪声影响的真实值，或者是其他状态反向更新后的某个。这时候，上述的更新公式就要改成如下所示，用代替：
如果是的无偏估计值，即，那么根据“标准随机近似条件”，依然可以收敛（保证步长参数需要随着时间而不断减小）。如果 U_t 不是的无偏估计值，那么就不能保证收敛。
作为的无偏估计值的一个典型案例是蒙特卡罗算法的target value：。还记得代表啥么？表示状态对应的return,即奖励值的总和（也可以是discounted sum）。因为是的无偏估计，因此梯度下降版本的蒙特卡洛价值函数估计算法是可以确定找到局部最优解的。
下面给出的是将传统蒙特卡洛算法改造成梯度下降版本蒙特卡洛算法的伪代码：
4.2 半梯度方法
说完了收敛性质特别棒的蒙特卡洛算法的target value，也就是训练样本的output，我们要来说几个收敛性质不乐观的target：就是采用自举法（bootstrapping）估计得到价值估计值。
大家想一下有哪几个算法采用自举法进行价值函数的估计？这里有两个：
（1）TD(λ)前向视角的target value：TD(λ)的前向视角采用λ-return,所以其target value是。然而，当λ
（2）DP的target value：。同样，DP中也采用了bootstrapping，它的target value也不是的无偏估计，因此该方法的梯度下降版本无法找到局部最优解。
为什么采用自举法进行价值函数估计得到的target value收敛性质不好呢？因为从的梯度更新公式可以看出，target需要和相互独立，互不影响。而这个条件一旦用了自举法就无法被满足（看下式标红部分）：
这一类target代入梯度更新公式后，得到的只是部分梯度的下降，而不是真正的梯度下降，因此把这类梯度更新方法叫做：半梯度方法（semi-gradient methods）。
我们可以看到，半梯度下降算法和梯度下降算法的形式是一样的，只是target的特点不一样。区分这两种参数更新算法的唯一指标，就是看target，即训练样本的output，是否是input（状态）真实价值的无偏估计。
半梯度方法虽然收敛性质不如真正的梯度下降方法，但是它有自己的优点：
（1）半梯度方法在线性模型下可以保证收敛。
（2）在可收敛的情形下，半梯度方法的收敛速度特别快。
（3）半梯度方法可以用在连续性任务中，不必等到序列结束。
这里给出一个半梯度方法的典型案例：semi-gradient TD(0)
第二部分预告
上文在拟合模型的部分，并没有提具体的模型。在下个部分，我们将提出第一个拟合模型—线性模型，作为的表示形式。
敬请期待！
- 发表于:
- 原文链接：http://kuaibao.qq.com/s/20180305G150T000?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
