强化学习读书笔记（10）| On-policy Prediction with Approximation（下）

本讲将继续学习使用on-policy的数据对状态值函数进行逼近，也就是在策略π下估计值函数vπ。

手动选择步长参数

Selecting Step-Size Parameters Manually

非线性函数近似：人工神经网络

Nonlinear Function Approximation: Artificial Neural Networks

前面讲了线性值函数近似方法，还介绍了很多构造特征的方法。即使采用线性模型，在合适的特征表征下也能得到不错的近似效果，但是非线性的函数表达能力更强。本节介绍一种常用的非线性函数近似模型，即人工神经网络（artificial neural network, ANN）。

ANN广泛地用于非线性函数拟合，它是由很多具有神经元性质的单元互相连接构成的网络。ANN已经有很长的历史了，深层神经网络，也就是深度学习，近年来展现出了很强的能力，在ML包括RL领域都涌现了基于深度学习的很多优秀的算法。

前馈ANN是最基本的NN结构。它的形式如下：

神经网络的权重学习

不管ANN用于上面哪一种情形，我们都需要知道权重的变化是如何影响到网络的输出，也就是要知道目标函数关于网络权重参数的偏导数，这实际上就是SGD的方法。具体来说，在ANN中，我们使用反向传播算法来更新权重，即BP算法。在前向过程中，我们会计算每个神经元的激活（输出）。反向过程就是计算偏导数。利用BP算法，浅层的ANN表现较好，但是对于深层的NN就有一些问题，这其中最大的问题就是过拟合。

如何解决NN的过拟合？

为什么会过拟合呢？过拟合就是模型在训练集上表现很好，但是在测试集上表现很糟糕，泛化能力很差。Deep NN强大的能力，很容易使我们训练的模型在训练集上得到接近于0的误差，那么自然就容易过拟合了。为了防止过拟合的出现，以及更好地训练深度神经网络，通常有以下方法：

• 提前结束训练
• 加入正则项，约束模型的复杂度
• 参数共享
• dropout，使一些连接失效，从而减少参数
• 批标准化
• 残差学习

这些内容不是本文关注的重点，感兴趣的读者可以参考其它资料继续学习。我们只关注ANN在RL中的应用。尽管目前的RL理论只限于表格型或者线性函数近似方法，但是在实际应用中，ANN和RL相结合确实获得了不错的效果。我们在16章会介绍一些相关工作。

最小二乘TD算法（LSTD）

Least-Squares TD

LSTD方法是否适用，要根据问题的维度d、是否需要快速学习等因素决定，毕竟LSTD复杂度比TD高很多。而且，LSTD不需要设置更新步长，这是一个优势；但是LSTD需要设置参数ε，其必须选择不大不小的合理数值；此外LSTD没有更重视最近数据的考虑，因此无法遗忘历史数据，在RL中这不是好的性质，因此不得不引入额外的遗忘机制。

基于记忆的函数近似

Memory-based Function Approximation

前面讲的都是通过参数化的方法来逼近值函数，但是基于记忆的方法不同，它们只需要保存算法访问过的训练样本（的一部分），而不需要更新任何参数。当需要查询某个状态的估计值的时候，利用记忆中的过往样本来计算出这个状态的值即可。这个方式有时也称为lazy learning，因为知道系统需要输出时才对训练样本进行处理。

和参数化方法不同，基于记忆的方法的近似函数并不局限于一类固定参数的函数，而是由训练样本来决定。通过组合过往的训练样本，来输出查询状态的状态值。训练样本越多，非参数化方法的结果就越精确。

有很多种基于记忆的算法。例如local-learning的算法，通过利用查询状态附近的邻近样本来逼近值函数。从样本中先提取出和查询状态相近的样本，然后可以根据距离赋予权重，之后组合这些邻近样本给出查询结果，随后丢弃。最简单的基于记忆的方法叫做最近邻居法，该方法直接返回需要查询状态最接近的状态的结果。稍微复杂点的方式就是抽取一堆比较邻近的样本，然后输出它们的加权平均。

作为非参数化的方法，基于记忆的算法相对参数化方法有很多优点：比如随着数据增多，精准度会越来越高；而且非参数法更适应强化学习算法，例如在Trajectory sampling中，非参数化的结果可以更关注那些真实轨迹中访问过的状态；此外，非参数法可以使样本对于邻近状态的影响更为直接，而不像参数法那样需要增量式调整参数来得到全局近似。

避免全局近似也是一个解决维度灾难的好方法。非参数法存储n个样本只需要正比于n的空间，而对于有k维的样本空间，参数法需要解决指数级的参数或者状态空间。

基于记忆的方法也有一些缺点。比如当样本集不断增大的时候，如何有效的在样本集搜索找到最近邻点构成的集合。有一些方法来解决这些问题，比如并行计算。后者使用特别的数据结构来存储训练集，比如k-d树。

基于核的函数近似

Kernel-based Function Approximation

深入了解On-policy 学习：Interest和Emphasis

Looking Deeper at On-policy Learning: Interest and Emphasis

State Aggregation on the 1000-state Random Walk（续）

本讲我们继续借助random walk例子，来实战演练线性方法的特征构造问题。

回顾：考虑1000个状态的random walk，从左到右编号1到1000，并且所有episode在中心附近开始，即状态500。状态转换从当前状态到其两边各100个邻近状态中的一个，以相同概率。如果当前状态接近边缘，那么在它的那一侧可能少于100个相邻状态。在这种情况下，没有的状态的概率都会进入终止方的概率。左边的终止产生奖励-1，右边的终止产生+1的奖励，所有其他过渡零奖励。

代码编写

Tile coding value function

Polynomial / Fourier-based value function

实验结果

小结

为了效果更好，常将状态转化为一些特征，并把这些特征乘权重相加，构成基于特征的线性拟合器。如何选择特征则要结合具体问题的领域先验知识，可以选择多项式、傅里叶、粗糙编码、瓦片编码、径向基函数等特征。LSTD是数据利用最高效的TD预测方法，但是需要和权重数量平方关系的计算复杂度；非线性方法包括ANN拟合器，近年来由于深度学习的发展展现出了很强的潜力。

参考资料：

[1] R.Sutton et al. Reinforcement learning: An introduction , 1998

[2]https://blog.csdn.net/qq_25037903/article/details/82627226

[3]https://zhuanlan.zhihu.com/c_1060499676423471104

[4]https://blog.csdn.net/u013695457/article/details/90721961

[5]https://github.com/ShangtongZhang/reinforcement-learning-an-introduction