8_泛化与函数逼近

第八章泛化与函数逼近翻译：金海东到目前为止，值函数的估计都是用表格来表示，每个状态或状态-动作对对应到表格中一项。这是一种特别清晰并且有意义的做法，但是这种做法只能用于状态和动作数量不多的任务，原因不仅在于大的表格会占用很多存储空间，还在于精确填满这张表格需要的计算时间和数据。换句话说，关键问题在于泛化（generalization），如何把有限状态子集上的学习经验，泛化到很大的状态子集上并且逼近得很好呢？这是一个非常重要的问题。在用到强化学习的许多任务中，大多数当前遇到的状态，以后可能再也不会遇到。在具有连续变量或者复杂感知的状态动作空间中，这种情况常常会出现。对于这种类型的任务，唯一的学习方法就是将前面经历过的状态，泛化到那些从未经历过的状态。幸运的是，人们已经大量研究过如何根据样例泛化，没有必要发明完全新的方法用于强化学习，只需将现存的泛化方法与强化学习结合起来。这种泛化通常称为函数逼近（functionapproximation），因为它从目标函数（如值函数）提取样本，并试着从样本泛化从而构造出整体的函数逼近。函数逼近是监督学习（supervisedlearning）的手段之一，监督学习是机器学习、人工神经网络、模式识别以及统计学中曲线拟合等领域的研究主题。正如本章所述，从原理上讲，这些领域研究出的任何方法，都可用于强化学习。8.1使用函数逼近的值预测与前面一样，这里也从预测问题着手研究。预测问题是指根据策略生成的经历来估计状态值函数V。本章的不同之处在于，t时刻逼近的值函数tV不是表示成一个表格，而是表示成一个带有参数向量t的函数。这意味着值函数tV完全取决于t，在不同的时间步，只有t改变tV才会跟着改变。例如，tV可能是人工神经网络计算的函数，向量t表示神经网络连接权重，通过调整权重，任意函数tV都能由这个网络来实现。或者tV可能是决策树计算的函数，其参数包含在t向量中，这些参数定义了决策树分裂结点和叶子结点的值。通常情况下，参数的数量（即t分量的个数）比状态的数量要少得多，并且改变一个参数强化学习ReinforcementLearning可以改变很多状态的估计值。因此，单个状态的值被备份，这个变化就会从该状态泛化出去从而影响到很多其他状态的值。本书把所有预测方法都描述为备份，也就是说，更新某个估计值函数，即意味着把该函数特定状态的值转换为这些状态的“备份值”。（译注：此处为update和backup的定义。更新某个函数，为update，更新某个状态，为backup。本章所有backup翻译为“备份”，update翻译为“更新”。）。这里用sv表示单个备份，其中s是被备份的状态，v是备份值或者说s的估计值要转向的目标。例如，用于值预测的DP备份为11{()|}ttttsErVsss，蒙特卡罗备份为ttsR，(0)TD备份为11()ttttsrVs，通用()TD备份为ttsR。DP实例中，备份的是任意状态s，而其他实例中，备份的是在经历（可能是模拟的经历）中遇到的状态ts。很自然可以这样理解：每次备份相当于指定了估计值函数的一个输入-输出样例。从某种意义上说，sv意味着状态s的估计值进一步接近v。因此，用于实现备份的真正更新已经不重要了：s估计值对应的表格项只是简单地向v靠拢了一小步。我们可以使用任意复杂且成熟的函数逼近方法实现备份。这些函数逼近方法的常规输入，即是它们试图逼近的函数所期望的输入-输出样例。把每次备份sv简单地看作训练样例，就能使用基于函数逼近的值预测方法。这样，我们把函数逼近方法产生的近似函数，解释为估计的值函数。以上述方式把每次备份当成常规训练样本，就能使用现存的诸多函数逼近方法进行值预测。从原理上讲，可以使用任何基于样例的监督学习方法，包括人工神经网络、决策树以及各种类型的多元回归。但是并非所有的函数逼近方法都适合在强化学习中使用，大多数高级神经网络和统计学方法都假定存在静态的用于多传递的训练集。在强化学习中，能够实现在线学习非常重要，此时它与环境或者环境模型交互。要做到这一点，要求学习方法能够从增量获得的数据中进行有效学习。此外，强化学习通常要求函数逼近方法能够处理非固定目标函数（即不断改变的目标函数）。例如在GPI控制方法中，我们希望在改变时也能学习到Q。如果训练样本的目标值是由自举方法计算的（如DP和TD方法），即使策略维持不变，这些目标值也是非固定的。如果一种学习方法处理不好非固定问题，就不太适合用于强化学习。如何测定函数逼近的性能呢，大多数监督学习寻求最小化输入分布P上的均误方差（MSE,mean-squarederror）。在值预测问题中，输入是状态，目标函数是精确的值函数V，因此，使用参数向量t的近似函数tV的均方误差是：2ttsSMESPsVsVs（8.1）泛化和函数逼近GeneralizationandFunctionApproximation其中P是表示不同状态的误差权重的分布。状态数量要比t分量个数多得多，通常不可能把所有状态的误差都降为0，因此这个分布十分重要。因此，函数逼近器的灵活性是一个难得的资源，要想得到某些状态好的逼近，必须以其他状态差的逼近为代价。误差权重分布P指定了如何在不同状态之间做平衡。P通常是抽样得到的训练样本中状态的分布，因此该分布上的状态都已经做了备份。如果希望状态在特定分布下的误差最小，比较有效的做法是采用相同分布的样本来训练函数逼近器。例如，要想误差均匀分布在整个状态集合上，有效的做法是，使用在整个状态集合上均匀分布的备份来训练近似函数逼近器，类似于一些DP方法中的穷举扫描。今后，假定状态做了备份的分布与误差权重分布P是一致的。分布用来描述：agent根据策略选择动作与环境交互时，遇到某些状态的频繁程度，我们想要逼近的就是该策略的值函数。我们把这种分布称为在-策略分布（on-policydistribution），部分理由是，这是采用在-策略控制方法的备份分布。最小化在-策略分布的误差，就是把函数逼近的重点放在那些在该策略下实际出现的状态上，忽略那些没有出现的状态。在蒙特卡罗或者TD方法中，使用在-策略分布也是得到训练样本的最简单方法。这些方法使用策略从样本经历中生成状态值备份。因为要对遇到的每个状态进行备份，获得的训练样本的分布很自然与在-策略分布一致。在-策略分布比我们后面讨论的其他分布的收敛效果更好。现在还不清楚是否应该最小化MSE。值预测有不同的潜在目标，这里最终希望通过值预测来改进策略，要做到这一点，值预测的最优目标未必是最小化MSE。由于不清楚值预测更有效的替代目标是什么，我们还是把注意力放在MSE上。MSE的理想目标是找到全局最优解（globaloptimum），即对所有可能的，存在一个参数向量*使得*()()MSEMSE。要达到这个目标，有时简单的线性函数逼近器就够用了，复杂的函数逼近器如人工神经网络和决策树却不太可行，反而会收敛到局部最优解（localoptimum），即只在*邻域的所有中，存在一个参数向量*使得*()()MSEMSE。收敛到局部最优解虽然让人不够安心，但是就非线性函数逼近器来说，这已经是典型的最好情况了。在许多用到强化学习的实际问题中，收敛到最优解甚至真正的收敛，根本不会发生。尽管如此，通过一些方法还是可以获得接近最优解的MSE。其他一些逼近方法实际上可能是发散的，其MSE在极限上趋于无穷。为了把基于值预测的各种不同强化学习方法和各种不同的函数逼近方法结合到一起，本强化学习ReinforcementLearning节描述了一个框架，该框架把前者的状态值备份作为后者的训练样本。另外本节还概述了MSE用于度量函数逼近的性能。上述各种方法涉及的面实在太广，其中许多方法很少有人做可靠的评价或建议，因此本书只关注其中一小部分，没有面面俱到。本章后面将关注基于梯度原理的函数逼近方法，特别是线性梯度-下降方法。部分原因是我们认为梯度方法揭示了关键理论要点，比较有前景，另外的原因是该方法比较简单，而本书的容量有限。如果本书有更多章节来讨论函数逼近，我们至少会把基于存储的方法和决策树方法包括进来。8.2梯度-下降方法现在详细讨论一种用于值预测的学习方法，即基于梯度-下降的函数逼近方法。梯度-下降方法是所有函数逼近方法最广泛使用的，尤其适合于强化学习。在梯度-下降方法中，参数向量是由固定个数的实数值组成的列向量((1),(2),...,())Tttttn（T表示转置），()tVs（所有sS）是t的平滑可微函数。这里假定在每个时间步t都观察到一个新样本()ttsVs。在与环境的交互中，这些状态可能是连续的，但这里假定状态是离散的。即使样本给出的是每个状态ts的真实值()tVs，学习的困难仍然存在，这是因为函数逼近所需的资源有限，解决方法也就有限。特别是，通常不存在一个使得所有状态甚至所有样本的值都正确。此外，我们还必须将其泛化到样本中没有出现的其他状态。假定出现在样本中的状态都有相同的分布P，我们试图在这些样本上最小化（8.1）式所示的MSE。这种情况下，好的对策就是在观察到的样本上最小化误差。梯度-下降方法在获取每个样本之后稍微调整参数向量，调整方向是能最大程度减少样本误差的方向：211[()()]2ttttttVsVs[()()]()tttttttVsVsVs（8.2）其中是正的步长参数，对任意函数f，()ttf表示偏导数向量：()()(),,...,(1)(2)()Tttttttfffn这个导数向量就是f关于t的梯度（gradient）。这种方法称为梯度下降（gradientdescent），因为t每次调整的步长，都与样本误差平方的负梯度有比例关系。这个方向是误差下降最快的方向。现在还不清楚为什么在梯度方向上只移动一小步，不能在这个方向上以各种方式移动并泛化和函数逼近GeneralizationandFunctionApproximation完全消除样本的误差吗？许多情况下可以这样做，但通常并不可取。要记住的是，我们并不是寻求所有状态误差都为零的值函数，只是寻求能平衡不同状态之间误差的近似函数。如果每一步都完全更正每个样本的回报值，就不可能达到状态之间的误差平衡。实际上，梯度方法在收敛过程中假定步长参数是随着时间步递减的。如果步长参数以（2.8）式标准的随机逼近条件递减，则（8.2）式梯度方法能确保收敛到局部最优。现在讨论这种情况：第t次训练样本ttsv的目标输出tv不是真实的()tVs，而是真实值的某种逼近。例如，tv可能是()tVs的一个受噪声污染版本，或者可能是上节提到的某个备份值。这种情况下，由于()tVs未知导致无法精确执行（8.2）式更新（update），但是可以用tv替代()tVs作为()tVs的近似值。这就产生了用于状态值预测的通用梯度-下降方法：1()()ttttttttvVsVs（8.3）如果tv是()tVs的无偏估计（unbiasedestimate），即在每个时间步{}()ttEvVs，且以（2.8）式标准随机逼近条件递减步长参数，就能确保t收敛到局部最优。（译注：估计量的数学期望等于被估计参数，称为无偏估计。如：设A'=g(X1,X2,...,Xn)是未知参数A的一个估计，若满足E(A')=A，则称A'为A的无偏估计量，若E(A')≠A则为有偏估计量。无偏估计是系统误差为零的估计。）例如，假定样本中的状态是使用策略与环境交互（或者模拟交互）产生的。令tR表示在每个状态ts之后得到的回报值。在蒙特卡罗备份中，一个状态的真实值是在该状态之后得到的回报值的期望，所以蒙特卡罗目标值ttvR是()tVs的无偏估计。这种情况下（8.3）式通用梯度-下降方法能收敛到()tVs的局部最优。因此，使用蒙特卡罗状态值预测的梯度-下降版本，能