之前在第一部分(Chapter01~Chapter08)讲的value function建立，是一种表格的方法(tabular method)，不管是state-value还是action-value，最终的收敛结果都是以有限的、准确的列表来存储的。这种方法是理解强化学习的基础方法，但是随着state space的扩大，传统的精确方法便被计算资源和计算时间所限制，这时，学习目标便从准确的value table变为了学习近似的value function。function approximation是value function的近似形式，之所以称之为function，是因为所有的value都是通过一个带参数的函数来近似的，函数参数是通过一部分的学习数据得到，用来在整个state space上推广。
这种思路比较像监督学习(supervised learning)。但是因为强化学习问题所引入的nonstationarity, bootstrapping, and delayed targets等特性，reinforcement learning with function approximation相较supervised learning还有很多新的问题需要讨论。本章主要讲了function approximation在on-policy的预测问题中的应用。
Value-function Approximation
value-function approximation就是使用s和一组向量w来表示state的estimate value：f(s,w)
value-function approximation有别于表格方法的参数化值函数表示方法，通过s->g作为训练样本，最小化训练误差来训练参数，通过有限的样本来拟合state空间上的value值。
We use these methods for value prediction simply by passing to them the state ->goal of each update as a training example. We then interpret the approximate function they produce as an estimated value function.
这个函数理论上可以使用任意的监督学习算法：线性模型、决策树、神经网络等。但是针对强化学习问题，对监督学习算法提出以下要求：
(1)可以随着agent和环境进行交互进行on-line学习，通过可以处理增量形式获取的数据
(2)算法可以适应变化的目标函数，因为强化学习任务经常遇到nonstationary的问题，比如基于GPI进行的control任务，target policy π经常会发生变化。
The Prediction Objective (VE)
基于function approximation的预测的目标是尽量减少estimate value和true value之间的误差，这里引入Mean Squared Value Error作为预测目标：
μ(s)是引入的误差权重，在on-policy的预测问题中称为on-policy distribution。在连续任务(continuing tasks)中，该分布是基于policy π的固定分布。
on-policy distribution是通过以下两步公式计算得到：
h(s)表示一个episode从s开始的概率，η(s) 表示一个episode出现s的概率
μ(s)是η(s)在|S|上的归一化值，μ(s)越大，则说明s出现的概率越大，s引入的value估计误差影响越大。
最小化VE并不能保证得到全局最优的function approximation，除了像简单的线性拟合函数等，但是对于复杂的监督学习模型，比如决策树，神经网络等，可能达到局部最优，也可能不会收敛。
Stochastic-gradient and Semi-gradient Methods
使用梯度下降的方法来训练得到最优的w，以及得到最优的function approximation。
通过对VE关于w求导，并使用梯度下降的思路来训练得到VE最小的w：
这个地方开始就和普通的监督学习问题不同了。考虑之前在监督学习中学习梯度下降的时候，训练时把train data直接带入下降公式训练参数即可。但是在强化学习任务中有一个问题，就是true value是未知的！那么怎么开始梯度下降？
考虑我们在第三章学过的一个公式：
如果U_t是无偏的，即E[U_t|S_t = s] = v_π(S_t)，那么梯度下降的结果会收敛到局部最优值。
下面给出梯度下降(使用SGD)的Monte Carlo方法的伪代码：
值得注意的是，如果使用DP方法或者TD方法等bootstrapping方法，上面的更新是有问题的，因为bootstrapping方法中U_t包含了后续状态的estimate，所以此时的U_t就也是w的函数了，那么这个梯度下降公式只考虑了w改变对VE的影响，却忽略了w改变对update target的影响，这种梯度下降方法称为semi-gradient方法。
尽管semi-gradient方法不能像上面提到的gradient方法那样稳定的收敛，但是在某些特定条件下(such as the linear case discussed in the next section.)这种方法更受偏爱，因为semi-gradient方法不用等待episode完成，更新速度也更快，可以说是on-line learning的，因为更新是随着agent和环境交互同时进行的，所以可以适用于continuing problem。
下面给出一种典型的semi-gradient方法，semi-gradient TD(0)方法的伪代码：
关于gradient的例子，可以参考Example 9.1: State Aggregation on the 1000-state Random Walk，注意这里采用了状态聚合的SGD方法。
Linear Methods
this section给出了一种常见的function approximation形式——linear形式：
关于semi gradient TD(0)方法的收敛性证明，可以证明这种方法收敛到w_{TD}的不动点(fixed point):
同时渐进误差VE可以达到最小VE误差的一个扩大边界范围：
给出了semi-gradient的TD(n)方法的伪代码，因为采样是on-policy的，所以和TD(n)的表格方法预测代码结构基本相似：
关于使用自举(bootstrapping)的状态聚合semi-gradient TD方法的渐进性能，以及不同n和α对VE的影响，可以参考Example 9.2: Bootstrapping on the 1000-state Random Walk
Feature Construction for Linear Methods
这一部分是本章的重点，讲了如何从给定的state构造相应的feature。直接使用state的原始数字特征，比如一个多维度的S={s1,s2,…,sn}来做特征的话，并不能有效的学习到整个|S|的value function的特性，选择合适的特征可以使得学习到的value function更有效的泛化在整个state空间上。
Polynomials基函数构造特征
多项式构造feature结构简单，并可以自然的考虑到不同维度state数值的联系，但是在大多数的强化学习任务中效果并不是很好。
Fourier Basis基函数构造特征
使用傅里叶级数表示特征的方法广泛的适用于强化学习任务，因为只要一个函数是给定的，那么它一定存在傅里叶级数展开，当然前提需要满足狄利克雷条件，一般强化学习任务构造的函数都满足这个条件。
对于有界的函数，我们可以令三角函数的基本周期τ对应区间长度，并只取区间内的三角函数的值来作为基函数。
更进一步，如果将τ设置为两倍的区间长度，那么可以只使用cos函数来作为基函数，然后只使用(0,τ/2)上的基函数来做特征。
下面给出一个1维state的Fourier基函数：
同理，多维的state构造Fourier基函数如下所示：
Coarse Coding(粗糙编码)
使用不同的state空间范围来(如1维空间对应随机长度的区间，2维空间对应随机大小和位置的圆)作为特征，对于state空间上任一点，如果落在f_n对应的空间内，则对应feature则置1，反正置0。这就是Coarse Coding的基本原理。
以二维空间为例，不同的圆的形状、尺寸、分布密度，都对所构造的粗糙编码特征的泛化性能造成影响：
以使用黑色阴影内的白色state来更新value function为例：
在narrow分布下，包含state的circle比较密集，所以泛化的范围比较小；
在broad分布下，包含state的circle覆盖范围比较大，所以泛化的范围比较大；
在Asymmetric分布下，因为circle的形状比较窄长，所以泛化会沿着特定方向。
关于Coarse Coding的例子，可以参考Example 9.3: Coarseness of Coarse Coding
Tile Coding
Tile Coding是Coarse Coding的的一种类型，这种方法通过将每个feature的感受野(receptive fields)划分为很多tile，如果训练使用的state落在对应的tile内，则对其进行更新。
使用随机的offset可以使得泛化更加均匀，如果使用统一的offset，泛化效果就会沿着对角线，泛化结果会更差一点：
Radial Basis Functions
RBF也是Coarse Coding的一种，但是这种feature构造方法并不是二值化的，而是采用了(0,1)之间的特征：
使用RBF特征产生的value function approximation更加平滑，并且是可微分的。
Selecting Step-Size Parameters Manually
这里给出关于学习步长α的直观认识：
(1)递减的α能有效收敛，但是收敛速度比较慢
(2)设置α过大，使得最近的样本占得比重提高，极限情况下α=1，这时经验值的比重为0，直接采用当前的样本值。直接消除value估计函数和样本的误差，既不利于在整个样本上达到整体误差最小，甚至有可能引起收敛曲线振荡；也不利于估计函数在状态空间上的泛化。
(3)在tabular方法中，可以近似认为，α=1/τ代表每个state的估计值是最近τ个样本的平均值。虽然在value function approximation中这种表示不太准确，但是在样本特征的长度变化不大下，有以下的经验公式，可以近似保证被最近τ个experience的平均值更新：
Nonlinear Function Approximation: Artificial Neural Networks
人工神经网络当然也可以作为近似value function，这部分主要介绍了ANN，并没有介绍具体的DeepRL，所以就不在赘述了。
Least-Squares TD
不使用梯度下降的方法，根据TD方法收敛的不动点w_TD和A矩阵以及b矩阵的关系，直接on-policy更新w_TD，注意这里是直接置更新，不是增量更新。
这种方法训练速度快，但是相应的计算成本高，尤其是求逆运算，直接求逆复杂度为O(d^3)，使用了Sherman-Morrison formula优化可以达到O(d^2)，但是和梯度下降的O(d)相比仍然很高了。
使用LSTD方法训练的伪代码如下：
Memory-based Function Approximation
lazy learning，类似监督学习中的knn，通过存储一系列样本，然后预测s的时候，取出和s相似度高的来预测，大概分为以下几种算法：
(1)nearest neighbor method:返回存储中和s最近的样本的value
(2)weighted average:返回最近的几个example的加权平均，权重是随着距离递增递减的
(3)locally weighted regression:通过参数拟合方法，使得拟合结果符合附近state整体的函数形状，即估计值可以最小化VE误差，估计之后会丢弃估计值，这是lazy learning方法的通性，即不存储估计结果。
相较于参数学习方法，memory-based方法可以提供更快的估计方法，而且估计结果随着训练数据的提升可以显著提升。因为on-policy采样的结果，可以避免全局近似，使得估计更专注于有价值的state集合。
但是memory-based算法性能同时也受到存储容量和搜索算法的影响，这些都有一些对应的加速算法。
Kernel-based Function Approximation
核函数(Kernel)是描述两个state相关度的函数，核函数可以用于memory-based方法来选取用于估计的样本state对应的weight，对应的memory-based方法为Kernel regression：
核函数描述了两个state之间的相关度，换句话说，核函数也可以表示一个state泛化到另一个state的能力。比如前面在tile Coding中的图片，state对应的深度即表示了中心state对其的泛化能力。事实上，核函数可以描述所有线性近似函数的泛化能力。
一个典型的核函数是Gaussian radial basis function (RBF) used in RBF function approximation。在memory-based方法中，RBF的中心是存储的样本，将落在state空间中的待估计s对应的RBF值作为样本weight来完成估计。
通过前面构造的feature同样可以重新构成Kernel:
这种形式的Kernel regression可以在相同训练数据情况下和参数估计价值函数达到相同的效果。
这种方法给我们一个启示：feature空间可能很大，或者说直接构造feature比较麻烦，为何不直接从数据中构造Kernel那？SVM方法就是一个很好的例子。对应很多强化学习问题来说，从feature内积得到Kernel可能是困难的，但是所有问题都是可以直接构造Kernel的，这种情况下构造Kernel然后使用Kernel regression会比构造feature使用参数近似函数方法更有效，这就是机器学习中常使用的kernel trick
Looking Deeper at On-policy Learning: Interest and Emphasis
本章到这里，我一直有一个问题，就是在VE的section，计算VE的时候，每个state的estimate都有一个对应的weight，即on-policy distribution，但是在后面的算法中并没有体现这个参数的作用。这一部分算是解决了我的一个疑问，就是不同的state训练的结果对w的影响应该是不同的，即引入了interest和emphasis的概念。
interest表示训练算法对一个state的感兴趣程度，是一个0-1的非负数。
emphasis即计算w增量时的参数，下面给出带emphasis的semi-gradient TD(n)更新公式:
对应的emphasis更新公式：
这个更新公式同时也涵盖了Monte Carlo的情况，令n=T-t，G_{t:t+n}=G_t，M_t=I_t