在本次学习中，我们主要进行预测，也就是根据策略估计值函数，关于控制（提升策略）将放在后一章。
我们的题目是基于近似的预测，什么是近似呢，就是我们不在把状态值函数表示成一个表格，而是一个向量$\textbf w$，$\hat v(s,w) \approx v_\pi(s)$。$\hat v(s,w)$是估计值，它是状态$s$和参数$w$的函数。如果这个函数是一个线性函数，那么w就是状态特征向量的权重；如果是一个神经网络，w就是网络的权重系数；如果是一个决策树，w就是分支的阈值和叶子节点的值。但是一般来说参数w的维度d远远小于状态数$\mid S\mid$，我们只需要存储d个参数，就能获取所有状态的值。但是同样一个参数的改变会影响很多状态的值，这种泛化性使我们处理的难点和重点。
值函数近似的一个好处是，它可以处理部分可观测MDP问题（PROMDP）。部分可观测就是我们只清楚部分状态的值，值函数近似就是用部分的值估计整个状态空间的值，因此适用于PROMDP问题。
1. 值函数近似
| 目前为止我们所学习的预测问题，都可以总结为当前的值函数朝着一个特定状态$s$的备份至$u$更新，即更新目标。使用$s \mapsto u$表示，我们分析一下之前学习的各种算法，基于MC更新的目标为：$S_t \mapsto G_t$，表示更新目标为采样累计回报；基于TD(0)的更新目标为：$S_t \mapsto R_{t+1} + \gamma \hat{v}(S_{t+1}, w_t)$，表示使用一个观测值加上估计值；基于n-step的更新目标为：$S_t \mapsto G_{t:t+n}$，表示使用n个观测值加上估计值；基于DP的更新目标为：$s \mapsto \mathbb{E}\pi [R{t+1} + \gamma \hat{v} (S_{t+1}, w_t) | S_t =s]$。 |
执行备份$s \mapsto u$的目的是使$s$当前的估计值更加接近目标$u$，实际上，$s$为输入，估计值为输出，$u$是标记，这就构成了监督学习的训练样本。当我们的目标$u$为数字时，这个过程就称为函数近似。
将每一步更新都看作是监督学习的训练样本，我们就可以使用许多现成的值函数近似方法来解决值函数预测问题，例如神经网络、决策树、多元回归等等。但是，并不是所有的值函数近似方法都适用于强化学习，因为基本上所有的函数近似方法都假设训练集是静态的。但是在强化学习中，样本是通过和环境交互获得的，是逐渐增加的，所以我们的算法能够从增量式获得的样本中学习。另外，强化学习中的函数近似方法需要具备处理非静态目标的特性，因为我们的更新目标是一直变化的，任何不能处理非静态性的方法都不适用于RL。
2. 预测目标
如果使用值函数近似，我们需要知道什么样的近似是好的。在监督学习中，我们一般称它为损失函数；在值函数近似中，我们称之为值误差（value error, $\overline{VE}$）。
在基于表格的值函数预测中，我们不需要损失函数，因为我们学习的值完全可以和真实值一模一样，而且每个状态的值不影响其它状态，不存在耦合。
但是对于值函数近似，一个状态的更新会影响其它状态（不再是一对一关系），而且既然是近似，我们不可能让预测值和真实值完全一样。在值函数近似中，参数$w$的数目远远小于状态的数量，所以一个状态的值准确就意味着其他状态值与预测值误差更大。
综上，我们需要声明一个损失函数，定义什么样的状态我们更重视，什么样的近似误差满足我们的要求。
在机器学习中，我们知道最简单的误差指标就是均方误差，我们估计的值为$\hat{v}(s, {w})$，真实值为$v_\pi(s)$，那么均方误差定义为$\frac{1}{n} \sum_{s \in \mathcal{S}} \left[ v_\pi(s) - \hat{v} (s, w) \right ]^2$。但是在这个公式中，我们对于所有状态的重视程度是一样的所以每个样本误差的权重都相等，为$\frac{1}{n}$，但是在实际中，我们要区别出我们更重视的状态，我们使用一个状态分布$\mu(s)$来表示我们对状态$s$的关注程度，其满足$u(s) \geq 0, \sum_s u(s) =1$，我们得出加权中的均方误差为：
\[\overline{VE} (w) = \sum_{s \in \mathcal{S}} u(s) \left[ v_\pi(s) - \hat{v} (s, w) \right ]^2 \tag{2-1}\]公式2-1就是加权后的均方误差，其中$\mu(s)$是怎样定义的呢，一个合适的方法就是根据状态的访问评率来确定其权重，状态出现越频繁，我们认为它越重要。访问频率和策略有关，对于在策略方法来说，$\mu(s)$就是在策略分布，对于连续任务来说，在策略分布就是策略$\pi$状态的静态分布。
对于episode任务（间断性任务），其在策略分布和episode初始状态的选择有关，我们用$h(s)$表示每个episode初始状态$s$的分布，用$\eta(s)$表示每个episode中在状态$s$停留的平均时间，这个时间包括两种情况：
- 这个状态和初始状态一样
- 从别的状态转移到当前状态
综上，状态s的平均逗留时间为：
\[\eta(s)=h(s)+\sum_{\bar{s}} \eta(\overline{s}) \sum_{a} \pi(a | \overline{s}) p(s | \overline{s}, a), \text { for all } s \in \mathcal{S} \tag{2-2}\]通过公式2-2，可以求出每个状态所占时间的百分比：
\[\mu(s)=\frac{\eta(s)}{\sum_{s^{\prime}} \eta\left(s^{\prime}\right)}, \text { for all } s \in \mathcal{S} \tag{2-3}\]在上面的学习中，我们使用权重均方误差作为损失函数，但是我们不能肯定，通过最小化损失函数，一定能够得到一个更好的策略。而且通过求解值函数来求解策略的手段，也并不是唯一的，研究者对此也有争议。但是总的来说，使用均方误差作为值函数近似的损失函数在一定程度上是合理的。
通过定义了值误差，我们现在的目的就是求解w以最小化误差，最好的情况是我们得到一个全局最优解，即得到权重向量$w^\ast$，使得对于任意的$w$都有$\overline{VE}(w^*) \leq \overline{VE}(w)$，但是实际上，只有在某些情况下才能得到最优解，例如线性的近似器（approximator），对于其他复杂的近似器，如神经网络、决策树，一般情况下我们只能得到局部最优解。在RL中，很多方法都不能保证收敛到最优，甚至不能保证收敛到最优解的一个区间内。
3. 随机梯度与半梯度方法
随机梯度下降算法是机器学习中常用的优化算法之一，因为获取一个样本更新一次，所以很适合在线的强化学习中的函数近似问题。
对于参数优化问题，对于每一个观测的样本，都沿着能够最大的减小误差的方向调整一小步权重：
\[\begin{align} \mathbf{w}_{t+1} & \doteq \mathbf{w}_{t}-\frac{1}{2} \alpha \nabla\left[v_{\pi}\left(S_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right]^{2}\\ &=\mathbf{w}_{t}+\alpha\left[v_{\pi}\left(S_{t}\right)-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t}\right) \tag{3-1}\end{align}\]公式3-1实际上就是对损失函数，或者叫做误差值求导，然后使用梯度更新的思想，对近似器的权重进行更新。
对于一个函数参数是向量的参数，对向量求导就是函数对于向量的每个分量求偏导，即：
\[\nabla f(\mathbf{w}) \doteq\left(\frac{\partial f(\mathbf{w})}{\partial w_{1}}, \frac{\partial f(\mathbf{w})}{\partial w_{2}}, \ldots, \frac{\partial f(\mathbf{w})}{\partial w_{d}}\right)^{T} \tag{3-2}\]随机梯度下降中的随机指的是我们基于单个样本，或者批样本，，但是都是随机选择的。
在公式3-1中，实际上$v_\pi(S_t)$是未知的，它是我们最终的目标，我们在更新时使用近似值$U_t$来表示它，$U_t$的选择有几种方式，分别对应到之前DP、MC、TD方法，如果是MC方法，通过采样均值的方法估计$U_t$，是一个无偏估计，我们可以得到基于MC的值预测方法，叫做梯度MC算法，伪代码如下：
在使用MC方法估计目标时，使用的是采样回报均值的方法得到$G_t$，然后带入公式3-1，不断进行迭代更新。
| 上面估计$U_t$的方法是MC的，也就是基于采样回报均值的方法；如果是TD或DP的，他们都通过自举来估计更新目标，例如n-step中的$G_{t:t+n}$，或者是DP中的$\sum_{a, s^{\prime}, r} \pi\left(a | S_{t}\right) p\left(s^{\prime}, r | S_{t}, a\right)\left[r+\gamma \hat{v}\left(s^{\prime}, \mathbf{w}_{t}\right)\right]$，由于自举使用当前的权重进行更新，但是当前的权重不是最优的，那计算的更新目标也是有偏的。 |
在公式3-1中，更新的目标$U_t$必须是独立与$w_t$的，但是对于自举的方式，更新目标也是通过权重估计的，这种情况下，公式3-1不是一个真正的梯度下降，因为没有考虑权重对于$U_t$的影响，相当于只考虑了部分梯度，这样的方法为半梯度方法。
半梯度方法在收敛特性上没有梯度方法鲁棒，但是当近似器为线性时，收敛也能够保证。而且这种自举的方式，使得半梯度方法能够在线、更快的学习。
下面来看一下使用半梯度方法，以TD(0)为例来估计$U_t$的伪代码：
通过伪代码可以发现，在线的更新方式会使得计算更加方便。
状态聚合指的是对于一组状态共用一个估计值，与权重向量w的一个分量有关，当某个组的一个样本被更新，只会影响到当前组，跟其他组没有关系，也就是其他组的梯度值为0。状态聚合是SGD的一个特例。
4. 线性方法
对于值函数近似的近似器，我们可以有不同的选择，例如线性模型，以及非线性模型如神经网络、决策树等等。
下面我们来学习线性方法：
线性方式就是说对于值近似函数$\hat{v}(s, \mathbf{w})$是一个线性函数，其实就是对于任意一个状态$s$，存在特征向量，维度和$w$一样，线性的近似器就是$w$和$s$特征的内积：
\[\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}^{\top} \mathbf{x}(s) \doteq \sum_{i=1}^{d} w_{i} x_{i}(s) \tag{4-1}\]$\mathbf{x}(s)$叫做状态$s$的特征向量，特征向量中的每个分量$x_i$都是从状态$s$到$\Bbb R$的一个映射，对于线性方法，每个特征映射实际上是一个基函数，定义了值函数空间的一组基，构造特征向量的过程就是选择基函数的过程。对于传统的ML来说，特征工程直接关乎模型的表现。在神经网络中比较流行端到端的方法。
对于线性模型，对权重的导数为：
\[\nabla \hat{v}(s, \mathbf{w})=\mathbf{x}(s)\tag{4-2}\]通过公式4-2，可以更新公式3-1：
\[\mathbf{w}_{t+1} \doteq \mathbf{w}_{t}+\alpha\left[U_{t}-\hat{v}\left(S_{t}, \mathbf{w}_{t}\right)\right] \mathbf{x}\left(S_{t}\right) \tag{4-3}\]公式4-3就是线性模型的更新公式。
在策略自举的方法能够被证明是收敛的，此处不再进行详细证明。
在第3小节中，我们给出了半梯度TD(0)算法的预测过程伪代码，现在我们扩展一下，将TD(0)扩展到n-step，伪代码如下：
实际上，相比于TD(0)，增加了观测多个回报值的过程。
5. 线性方法的特征构造
这一节我们学习点特征工程的东西，如何根据具体的状态来构造特征，对于算法的性能影响非常大，下面来看几个特征构造方法：
- 多项式
很多状态在仿真环境中都表示为数字，我们可以类比为回归问题，回归问题中比较常用的特征之一就是多项式。
假如当前的状态$s$是一个二维数组，即$s_1 \in \mathbb{R}$和$s_2 \in \mathbb{R}$，我们自然而然就可以用这两个维度的数值表示状态$s$的特征，$\mathbf{x}(s) = (s_1, s_2)^\top$。但是这样的特征无法表征两个维度之间的关系，如果两个值都为0，那么最终的特征就为0了，针对这两个问题，引入常数项和耦合项，为$\mathbf{x}(s)=\left(1, s_{1}, s_{2}, s_{1} s_{2}\right)^{\top}$，当然，我们可以使用高维特征$\mathbf{x}(s)=\left(1, s_{1}, s_{2}, s_{1} s_{2}, s_{1}^{2}, s_{2}^{2}, s_{1} s_{2}^{2}, s_{1}^{2} s_{2}, s_{1}^{2} s_{2}^{2}\right)^{\top}$。使用这样的特征，我们就可以表示任意的二次函数，但是我们的值函数近似器仍然是线性的，我们也可以将特征推广到$k$维$n$阶的多项式，这就是一般的多项式的定义。
理解了多项式的含义，如何进行构造呢？
假设我们的特征向量是k维的数值向量，即$s_{1}, s_{2}, \dots, s_{k}$，所以一个n阶的多项式基特征$x_i$表示为：
\[x_{i}(s)=\Pi_{j=1}^{k} s_{j}^{c_{i, j}} \tag{5-1}\]公式5-1中，$c_{i,j}$是集合${0,1, \ldots, n}$中的一个整数。
从理论上说，更高阶的多项式基可以获得更加复杂的函数，进而获得更加精确的近似效果，但是特征的维度随着状态维度指数次增长，因此在一般情况下，仅选择部分特征来作为函数近似的输入。其中的选择可以考虑先验知识，或者用一些特征选择的方法。
- 傅里叶基
什么是傅里叶级数：对于一个任意的周期函数都可以分解为无穷个不同频率正弦波和余弦波信号的叠加。
尽管我们的值函数不是周期函数，但是对于有限区间（区间长度为$\tau$）的非周期函数，我们可以通过复制的方式将它变成一个周期函数，每个周期的长度就等于区间长度$\tau$。
根据$\tau$与值函数区间的关系，分为以下两种情况:
- 如果$\tau$是值函数区间长度的2倍，我们可以仅关注区间$[0,\frac{\tau}{2}]$，目标函数是偶函数，我们仅使用余弦特征就可以了
- 如果目标函数是奇函数，仅使用正弦特征就可以了
因此，当$\tau=2$时，我们就可以近似区间$[0,1]$上的值函数，我们就可以得到一个一维n-阶的傅里叶余弦基，包含$n+1$个特征，为：
\[x_{i}(s)=\cos (i \pi s), \quad s \in[0,1] \tag{5-2}\]公式5-2中，$i=0,\ldots,n$。$i=0$就是第一个特征，$i=1,2,3,4$时对应特征如下：
当$i=n$时，我们就可以获得傅里叶基。
下面我们来看一下如何构造傅里叶基
假设我们的状态s是k维的数值向量$s=(s_1,s_2,\ldots,s_k)^T,s_i\in [0,1]$，那么$n$阶的傅里叶余弦基的特征$x_i$可以表示为：
\[x_{i}(s)=\cos \left(\pi \mathbf{s}^{\top} \mathbf{c}^{i}\right) \tag{5-3}\]公式5-3中，$\mathbf{c}^{i}=\left(c_{1}^{i}, \ldots, c_{k}^{i}\right)^{\top}$，其中每一个分量$c_j^i$都可能取到0到n中的任意一个整数，因此和多项式基一样，也有$(n+k)^k$个特征。
- Coarse coding
当我们的状态空间连续时，我们可以用相互重叠的区域覆盖状态空间。如果某个状态落在了某个区域内，则对应的值为1，否则为0。通过这种手段，我们可以将一个状态转换成一个只包含0、1值的向量，称之为二值特征。
对于一个状态来说，二值特征可以表示当前状态在哪个区域里，进而粗略编码当前状态的位置，这种使用相互重叠的区域进行状态编码的方式叫做coarse coding。
在上图中，对于状态s和s’，一种有13个园，从0开始编号。s处于三个圆的交界处，假设对应圆的编号为1,2,3，s‘位于3,4圆的交界处。因此状态s的特征向量为：$\mathbf{x}(s) = (0, 1,1,1,0, \dots, 0)^\top _{10\times 1}$，对于s’有$\mathbf{x}(s’) = (0, 0,0,1,1, \dots, 0)^\top _{10\times 1}$。
类似于上面的例子，可以把状态表示成一个二值向量，并且可以泛化，例如s与s’，他们拥有共同的圆，这样可以基于相似性实现某些特性的泛化。
首先介绍一个概念，感受野：某个状态的影响范围，在本例中表示某个状态所在圆的并集。
coarse coding编码了状态的位置，其泛化能力与感受野的大小、形状和密度有关。下图表示感受野的不同情况：
上图最左面的感受野比较小，说明泛化的范围也比较小。中间的图感受野比较大，泛化能力也更大一些；右面的感受野非对称，在纵轴上呈现细长状，因此在纵轴上的泛化能力更好。
通常来说，感受野越大，泛化的范围越大，会同时影响值函数近似的分辨率。所以，如何选择感受野的大小和形状呢？
实际上，在初期，近似性能会受到感受野的影响较大，最终的近似效果更多由特征数量决定。
- 堆编码
堆编码是Coarse coding的一种，是coarse coding在多维连续空间的扩展。它灵活并且计算效率高，可能是最实用流行的特征表示方法。
堆编码中特征的感受野被表示成很多个划分，每一个划分叫做一个tiling，tiling中的每一个元素叫做tile。
上图中，一个tiling决定了这个区域所有状态的特征值，相应的一个tile就是这个tiling中的一个激活单元。coarse coding使用一个圆表示，这里使用正方形表示，且无重叠。为了达到和coarse coding相似的效果，应该使用多个tiling，相互之间有一定的偏移。如右上角所示，有4个tiling，对于一个状态，4个tiling中相应区域会同时激活。
堆编码中二值向量的表征形式在计算上有优势，加入我们有n个tiling，那么对于二值特征向量来说只有n个值是1，其他的都是0，因为tiling不重叠，每个tiling只有一个位置对应。因此在计算线性近似值函数$\hat{v}(s, \mathbf{w}) \doteq \mathbf{w}^{\top} \mathbf{x}(s) \doteq \sum_{i=1}^{d} w_{i} x_{i}(s)$时，只需要计算n个相应激活位置的权重向量之和就可以了，比执行d次乘积加和运算要高效的多。
堆编码的泛化方式和coarse coding类似，处于同一tile的状态会泛化，并且堆编码的泛化还和不同tiling之间的偏移方式有关。
在堆编码中，影响泛化的因素有以下几个：
-
tiling的偏置方式
如果tiling的偏移在每个维度上都是均匀对称的，那么更倾向于对角方向泛化；
如果tiling的偏置是任意的，非对称的，泛化也会以更加合理的方式，以状态为中心，各向同性
-
tiling的数量
tiling的数量和tile的个数决定了近似函数的分辨率和渐进误差
-
tile的形状
tile的形状决定了泛化的本质特性
- 径向基函数
径向基函数（RBFs）是coarse coding对于连续实值特征的一个自然拓展。在coarse coding中，每个特征表示为0或者1，它可以是任何区间[0,1]之间的实数。
一个典型的RBF特征就是高斯函数，表示为：
\[x_{i}(s) \doteq \exp \left(-\frac{\left\|s-c_{i}\right\|^{2}}{2 \sigma_{i}^{2}}\right)\tag{5-4}\]公式5-4中，$c_i$表示该维度上特征的中心或者均值，$\sigma_i$是特征的宽度或者标准差。
其中，$\left|s-c_{i}\right|^{2}$是为了衡量状态之间的相似程度，我们可以根据问题选择任何适合的距离度量准则，例如马氏距离、欧氏距离、KL散度、海明距离、余弦角、切比雪夫距离等等。
上图中有三个高斯函数，每个高斯函数类似于coarse coding中的一个圆。在coarse中如果一个状态在某个圆中，特征值就为1，反之为0。我们把圆拉成一条线，变成一个函数，状态值就是高斯函数的函数值，相当于把离散的0,1变成[0,1]区间。
RBF的优点在于它能够产生可微的近似函数，在某些情况下很有价值；但是早更多的时候，反而导致计算复杂度增加，在高维特征上变现并不好。
6. 步长参数$\alpha$的选择
步长选择比较经典的是选择$a_t=\frac{1}{t}$，但是比较适用于之前学习的表格型MC方法，却并不适用TD方法、非静态问题和任何使用函数近似的方法。
对于一些线性方法，可以使用迭代最小二乘法来设置最优矩阵步长参数，这样方法也适用于LSTD。
对于函数近似的情况，没有明确的关于一个状态更新经验次数的说法，但是对于线性函数近似，有一些经验结论。假设对于一些很相似的特征向量我们希望经过$\tau$次经验更新收敛到期望目标。那么选择步长参数的表达式为：
\[\alpha \doteq\left(\tau \mathbb{E}\left[\mathbf{x}^{\top} \mathbf{x}\right]\right)^{-1} \tag{6-1}\]在公式6-1中，x是输入向量中的一个随机向量，当x变化不大时，上述方法变现最好，因为$\mathbf{x}^{\top} \mathbf{x}$是一个常数。
7. 非线性函数近似：人工神经网络
除了线性的值函数近似器，还有一些非线性的近似器，人工神经网络（ANN）就是其中一种。现在神经网络，特别是深度学习非常流行，在这里仅介绍ANN。
上图就是一种简单的前向神经网络，其中有一个输入层，两个隐藏层，一个输出层，所以是一个3层神经网络（隐藏+输出）。每个神经元中都先进行线性拟合，然后使用非线性函数处理。例如sigmoid、tanh、relu等。
为什么ANN比线性函数强大？理论上证明没有隐藏层的ANN可以表示一小部分函数，但是仅有一个隐藏层的ANN就可以近似任何连续函数，怎么样，是不是很强大。
在RL中，我们可以将ANN看做一个函数，即函数近似器。可以使用它来学习值函数，即最小化TD误差、最大化期望回报、直接在策略网络中用于策略梯度算法中。
在ANN 的训练中，同样使用SGD算法，即反向传播过程，通过梯度更新权重。
当然，在训练中可能会遇到过拟合，可以采用一些正则化方法进行处理，在此不详细赘述。
8. 最小二乘TD算法（LSTD）
回顾一下基于线性近似的TD(0)算法，在线性近似情况下，线性模型的权重系数逐渐收敛于TD不动点，即：
\[\mathbf{w}_{\mathrm{TD}}=\mathbf{A}^{-1} \mathbf{b}\\ \mathbf{A} \doteq \mathbb{E}\left[\mathbf{x}_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right)^{\top}\right] \quad \text { and } \quad \mathbf{b} \doteq \mathbb{E}\left[R_{t+1} \mathbf{x}_{t}\right]\tag{8-1}\]公式8-1中，权重会收敛于TD不动点，且其中的A与b的估计都依赖于当前时刻的状态和回报，每个时刻都估计一次，我们的算法也是迭代执行的。
但是我们能不能不进行迭代求解，而是直接估计A和b，然后得到最终的权重，即TD不动点。最小二乘TD算法就可以做到。
LSTD利用所有的样本估计A和b，公式为：
\[\widehat{\mathbf{A}}_{t} \doteq \sum_{k=0}^{t-1} \mathbf{x}_{k}\left(\mathbf{x}_{k}-\gamma \mathbf{x}_{k+1}\right)^{\top}+\varepsilon \mathbf{I}, \quad \widehat{\mathbf{b}}_{t} \doteq \sum_{k=0}^{t-1} R_{k+1} \mathbf{x}_{k} \tag{8-2}\]在公式8-2中，$\cal I$是单位矩阵，$\epsilon$是一个很小的常数，作用是保证A是可逆的。公式中的A和b都是t次估计的和。正常操作求期望应该就均值，也就是说$\widehat A$和$\widehat b$应该除以t，但是我们最终求解的是权重w，是由两者相乘得到的（公式8-1），因此会抵消掉，所以不用除以t。
LSTD算法的样本效率高，但是计算量也很大，对于半梯度的TD(0)来说每一步需要的内存大小是O(d)，对于LSTD而言，随着t的增大，公式8-2的计算越来越复杂，需要从头开始算。我们可以使用公式8-1 的增量式实现，这样每一步的更新不需要从头开始，但是每一步估计$\widehat A$都是一个矩阵更新，时间复杂度和空间复杂度都是O($d^2$)。而且在公式8-2中，求矩阵逆操作的时间复杂度是O($d^3$)，不过对于特殊形式的矩阵，求逆也可以增量式实现，公式为：
\[\begin{aligned} \widehat{\mathbf{A}}_{t}^{-1} &=\left(\widehat{\mathbf{A}}_{t-1}+\mathbf{x}_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right)^{\top}\right)^{-1} \\ &=\widehat{\mathbf{A}}_{t-1}^{-1}-\frac{\widehat{\mathbf{A}}_{t-1}^{-1} \mathbf{x}_{t}\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right)^{\top} \widehat{\mathbf{A}}_{t-1}^{-1}}{1+\left(\mathbf{x}_{t}-\gamma \mathbf{x}_{t+1}\right)^{\top} \widehat{\mathbf{A}}_{t-1}^{-1} \mathbf{x}_{t}} \end{aligned} \tag{8-3}\]公式8-3仅涉及矩阵向量乘积或者向量乘积，时间复杂度仅是O(d^2)，看一下LSTD的伪代码：
LSTD算法相比较半梯度TD(0)算法，可以看做牺牲了时间复杂度提高了样本效率。
9. 基于记忆的函数近似
主要思想是根据存储在内存中的已知数据求解未知点的值。
首先对于模型是否有参数，对函数近似方法分个类：
-
参数方法
优化的模型是一个含参数的函数，我们的目的就是求解函数的参数，对于输入，使用参数处理得到输出
线性方法就是参数方法，我们使用样本更新参数，最终得到的是模型的参数
-
非参数方法
没有明确的参数，预测的方法就是相似的输入具有相似的输出，一般根据预测点附件的样本推测值，有点像聚类
回到主题，基于记忆的函数近似方法跟之前的方法不同，在前期，我们将训练样本，也就是轨迹存储起来，不作任何处理；在后期需要预测状态值时，从记忆（内存）中拿出一部分样本用来计算尺一个估计值。这种在预测时才处理数据的方法，称作lazy learning。
基于记忆的函数近似方法属于非参数方法，没有明确的模型和参数，所以也不限于函数的类型，线性函数或者多项式都可以。非参数方法的输出取决于样本自身，当我们收集的样本越多时，我们希望非参数方法能够不断提高目标函数的近似精度，也就是准确率。
既然我们使用内存中的样本估计预测值，就会有以下两个问题：
- 如何进行样本的选择
- 如何使用选择的样本估计值
这两个条件是基于记忆的函数近似方法的核心，不同的方法会形成不同的算法。
方法之一就是局部学习方法。局部学习方法就是基于一定的距离准则找到距离state最近的一个或多个样本，距离越近表示这些样本和state相关性越高，进而可以使用这些样本估计state的值。最简单的就是近邻方法。
最近邻方法就是一最近样本点的值作为state的输出。
加权均值方法就是选择一个最近邻样本的集合，使用他们的值的加权和作为state的值，权重大小由距离决定。
局部加权回归（LWR）是在近邻集合上利用参数近似方法拟合一个曲面，然后使用拟合曲面评估state的值。
基于集记忆方法有哪些优势呢？
- 非参数方法的优势：不限于提前声明的函数形式
- 基于记忆的局部近似方法适用于RL。因为状态空间很大时，我们关注的可能仅是一部分区域，局部方法就能够采样到我们关心的区域，已达到近似效果
- 基于记忆方法中的经验会立即对当前状态领域产生作用
- 局部近似方法可以一部分解决维度灾难
基于记忆的方法要存储所有的样本，如何有效的搜集到相关样本或者样本集合，是其劣势之一，也是研究点。
10. 基于核的函数近似
在第9小节的基于记忆的函数近似中，我们提到了加权均值法和局部加权回归。其中比较重要的一个点就是计算权重，我们只知道这个权重应该于距离成反比，但是具体怎样计算呢？
实际上可以通过核函数计算权重，核函数是一个映射$k:\mathcal{S} \times \mathcal{S} \mapsto \mathbb{R}$，它可以将两个函数映射成一个实数，实数的大小反映了两个状态的相关性。
换个角度，核函数$k(s,s’)$代表了从状态s’到s泛化强度的度量，是一种很广泛的泛化机制，核函数就是均匀分布经过非对称偏移得到。
核回归是一种基于记忆的核加权均值方法，假设D是存储的样本，$g(s’)$表示D中某个状态s’的目标值，核回归通过下面的公式近似目标函数：
\[\hat{v}(s, \mathcal{D})=\sum_{s^{\prime} \in \mathcal{D}} k\left(s, s^{\prime}\right) g\left(s^{\prime}\right) \tag{10-1}\]第9小节的加权均值法可以看做核回归的一个特例，相当于在s的邻域中采取到非0值。
一个常用的核函数是高斯径向基函数（RBF），目标函数表示为RBF加权和的形式，这个权重通过随机梯度或者半梯度学习得到。在核回归中，RBF仅仅作为核函数，目标函数通过公式10-1计算，是一种基于记忆的非参数方法。
11. 深入在策略学习：Interest and Emphasis
在前面几节学习的权重迭代算法中，我们平等的对待每一个样本状态，而在某些实际情况中，我们应该更关心某些状态。在函数近似资源有限的情况下，如果能够更加有导向性的重视关键状态的值估计，可以提升函数近似的效果。
这种重要性我们使用一种度量指标，一个非负的标量测度$I_t$，叫做interest。表示在t时刻对于精确近似状态或者动作值的兴趣。其中为0表示完全不关心，1表示十分关心。还引入了一个随机变量$M_t$，叫做emphasis，表示每一步对于状态的强调度。
根据$M_t$，我们可以更新公式3-1：
\[\mathbf{w}_{t+n} \doteq \mathbf{w}_{t+n-1}+\alpha M_{t}\left[G_{t : t+n}-\hat{v}\left(S_{t}, \mathbf{w}_{t+n-1}\right)\right] \nabla \hat{v}\left(S_{t}, \mathbf{w}_{t+n-1}\right), \quad 0 \leq t<T \tag{11-1}\]公式11-1中的$M_t$通过$I_t$进行迭代更新：
\[M_{t}=I_{t}+\gamma^{n} M_{t-n}, \quad 0 \leq t<T \tag{11-2}\]通过引入interest与emphasis，相当于在每个状态上认为增加了bias，从而使某些状态获得更好的近似效果，但是同理某些状态的近似误差更大了。
上述内容主要参考《Reinforcement Learning An Introduction》一书。
