基于函数逼近的同轨策略预测
0. 简介
函数逼近法：使用同轨策略数据来估计状态价值函数，即从已知的策略$\pi$生成的经验来近似一个价值函数$v_\pi$。
特殊的是，近似的价值函数不再表示成一个表格，而是一个具有权值向量$\mathbf w\in \mathbb{R}^d$的参数化函数$\hat v(s,\mathbf w)\approx v_\pi(s)$
其中，$\hat v(s,\mathbf w)$是基于权值$\mathbf w$来估计$v(s)$，$v_\pi(s)$是基于策略$\pi$来估计$v(s)$，且$\mathbf w$的维度远小于状态数量，改变一个权值$w(i)$将会改变很多$v(s)$。
1. 价值函数逼近
用符号$s\mapsto u$表示一次单独的更新，$u$表示$s$的估计价值朝向的更新目标。
MC：$V(S_t)\gets V(S_t)+\alpha[G_t-V(S_t)]$
TD(0)：$V(S_t)\gets V(S_t)+\alpha [R_{t+1}+\gamma V(S_{t+1})-V(S_t)]$
例如，在蒙特卡洛方法中是$S_t\mapsto G_t$，TD(0)中是$S_t\mapsto R_{t+1}+\gamma \hat v(S_{t+1},\mathbf{w}_t)$，n步TD方法中是$S_t\mapsto G_{t:t+n}$
将每一次更新解释为给价值函数指定一个理想的“输入-输出”样本。更新$s\mapsto u$意味着状态$s$的估计价值需要更接近更新目标$u$。
到目前为止实际使用的更新：$s$的估计价值只是向$u$的方向移动了一定比例，其他状态的估计价值保持不变。
现在使用任意复杂的方法进行更新，在$s$上进行的更新会泛化，使得其他状态的估计价值同样发生变化。
2. 预测目标$(\overline{\mathbf{VE}})$
一个状态的更新会影响到许多其他状态，不可能让所有状态的价值函数完全正确，需要给出哪些状态是我们最关心的。
指定一个状态的分布$\mu(s)\geq0,\sum_s \mu(s)=1$来表示对每个状态$s$的误差的重视程度。
均方价值误差：
$\overline{\mathbf{VE}}(\mathbf w)\doteq
\mathbb E_\mu [(v_\pi(s)-\hat v(s,\mathbf w))^2]=
\sum_{s\in S} \mu(s)[v_\pi(s)-\hat v(s,\mathbf w)]^2.$
将一个状态$s$的误差表示为近似价值函数$\hat v(s,\mathbf w)$和真实价值函数$v_\pi(s)$的差的平方。
通常情况下，将在状态$s$上消耗的计算时间的比例定义为$\mu(s)$，可理解为状态$s$被采样到的概率。
在同轨策略训练中称为同轨策略分布，在持续性任务中，同轨策略分布是$\pi$下的平稳分布。
在分幕式任务中，令$h(s)$表示从状态$s$开始一幕交互序列的概率，令$\eta(s)$表示$s$在单幕交互中消耗的平均时间（时刻步数）。“在状态$s$上消耗的时间”指，由$s$开始的一幕序列，或发生了一次由$\overline s$到$s$的转移。
$\eta(s)=h(s)+\sum_{\overline s} \eta(\overline s) \sum_a \pi(a|\overline s)p(s|\overline s ,a)$
同轨策略分布被定义为其归一化的时间消耗比例$\mu(s)=\frac{\eta(s)}{\sum_{s’}\eta(s’)}$
最理想的目标是对于所有可能的$\mathbf{w}$找到一个全局最优的权值向量$\mathbf{w}^*$，满足$\overline{\mathbf{VE}} (\mathbf{w}^*)\leq\overline{\mathbf{VE}}(\mathbf w)$，对于复杂的函数逼近模型，转而求局部最优。
3. 随机梯度和半梯度方法
定义了目标函数$\overline{\mathbf{VE}}(\mathbf w)$，现在要最小化目标函数并得到近似最优解$\mathbf w^*$
$\arg\min_w \overline{\mathbf{VE}}(\mathbf w)\Longrightarrow \mathbf w^*\Longrightarrow v(s,\mathbf w^*)$
随机梯度下降
随机梯度下降(SGD)：一类函数逼近方法，适用于在线强化学习。SGD方法对于每一个样本，将权值向量朝着能够减小这个样本的误差方向移动。$x_{t+1}=x_t+\alpha p$，此处$\alpha$是步长，$p$是方向向量。
权值向量$\mathbf w \doteq(w_1,w_2,…,w_d)^\mathtt T$，$\mathbf w_t$为每个时刻的权值向量。
观察到新样本$S_t\mapsto v_\pi(S_t)$，样本包括状态$S_t$和其在给定策略下的真实价值。
$\begin{align}
\mathbf{w}_{t+1} \doteq& \mathbf w_t-\frac1 2 \alpha \nabla[v_\pi(S_t)-\hat v(S_t,\mathbf w_t)]^2\\
=& \mathbf w_t+\alpha[v_\pi(S_t)-\hat v(S_t,\mathbf w_t)]\nabla\hat v(S_t,\mathbf w_t)
\end{align}$
随机体现在：更新仅仅依赖于一个样本来完成，该样本很有可能是随机选择的。
更新公式中，对于真实值$v_\pi(S_t)$是未知的，用$U_t$近似取代$v_\pi(S_t)$
这就得到了用于进行状态价值函数预测的通用 SGD 方法：
$\mathbf{w}_{t+1}
= \mathbf w_t+\alpha[U_t-\hat v(S_t,\mathbf w_t)]\nabla\hat v(S_t,\mathbf w_t)$
如果$U_t$是个无偏估计，即$\mathbb E[U_t|S_t=s]=v_\pi(S_t)$，在$\alpha$的下降满足随机近似条件的情况下，$\mathbf w_t$一定会收敛到一个局部最优解。
使用MC中的$G_t$作为其无偏估计，得到如下MC-SGD更新：
$\mathbf{w}_{t+1}
= \mathbf w_t+\alpha[G_t-\hat v(S_t,\mathbf w_t)]\nabla\hat v(S_t,\mathbf w_t)$
对应算法伪代码如下：
半梯度方法
如果使用$v_\pi(S_t)$的自举估计值作为$U_t$，则无法保证收敛性。
因为n步回报$G_{t:t+n}$或DP目标$\sum_{a\; s’,r}\pi(a|S_t)p(s’,r|S_t,a)[r+\gamma\hat v(s’,\mathbf w_t)]$都取决于权值向量$\mathbf w_t$的当前值，意味着这些近似是有偏的。
使用TD(0)，令$v_\pi(S_t)\approx R_{t+1}+\gamma \hat v(S_{t+1},\mathbf w)$，带入到更新公式
$\begin{align}
\mathbf{w}_{t+1} =& \mathbf w_t-\frac1 2 \alpha \nabla[v_\pi(S_t)-\hat v(S_t,\mathbf w_t)]^2\\
=& \mathbf w_t-\frac1 2 \alpha \nabla[R_{t+1}+\gamma \hat v(S_{t+1},\mathbf w)-\hat v(S_t,\mathbf w_t)]^2\\
=& \mathbf w_t+\alpha[R_{t+1}+\gamma \hat v(S_{t+1},\mathbf w)-\hat v(S_t,\mathbf w_t)][\nabla\hat v(S_t,\mathbf w_t)-\gamma \nabla\hat v(S_{t+1},\mathbf w)]\\
\approx&\mathbf w_t+\alpha[R_{t+1}+\gamma \hat v(S_{t+1},\mathbf w)-\hat v(S_t,\mathbf w_t)]\nabla \hat v(S_t,\mathbf w_t)
\end{align}$
此处在最后一步省略了梯度$\nabla\hat v(S_{t+1},\mathbf w)$，故称为半梯度方法。
同时由于真实值的估计由自举法得到，因此semi-SGD真实值$v_\pi(S_t)$估计是有偏的，而且忽略了对预测函数$\overline{\mathbf{VE}}$的影响
半梯度方法的优点：学习速度比较快；支持在线学习。具有计算优势。
半梯度TD(0)算法伪代码：
4. 线性方法
近似函数$\hat v(\cdot,\mathbf w)$是权值向量$\mathbf w$的线性函数。
对应于每个状态$s$，存在一个和$\mathbf w$相同维度的实向量$\mathbf x(s)\doteq(x_1(s),x_2(s),\ldots,x_d(s))^{\mathrm T}$。线性近似的状态价值函数可以写作$\mathbf w$和$\mathbf x(s)$的内积$\hat v(s,\mathbf w)\doteq \mathbf w^\mathrm T \mathbf x(s) \doteq \sum_{i=1}^{d}w_ix_i(s)$
在这种情况下，我们称近似价值函数是依据权值线性的，或者简单地说是线性的。
向量$\mathbf x(s)$表示$s$的特征向量。$\mathbf x(s)$的每一个分量$x_i(s)$是一个函数$x_i:S\rightarrow \mathbb R$。状态$s$对应的函数值$x_i(s)$称作$s$的特征。对于线性方法，特征被称作基函数，因为它们构成了可能的近似函数集合的线性基。构造$d$维特征向量来表示一个状态与选择一组$d$个基函数是相同的。
SGD在线性情况下：
$\nabla\hat v(s,\mathbf w)=\mathbf x(s)$，
$\mathbf w_{t+1}\doteq \mathbf w_t+\alpha [U_t-\hat v(S_t,\mathbf w_t)]\mathbf x(S_t)$
在线性情况下，函数只存在一个最优值，因此保证收敛到或接近局部最优值的任何方法也都自动保证收敛到或接近全局最优值。
TD(0)在线性函数的情况下逼近收敛，权值向量也不是收敛到全局最优，而是靠近局部最优的点。每个时刻t的更新是：
$\begin{align}
\mathbf{w}_{t+1}
\doteq& \mathbf w_t+\alpha[U_t-\hat v(S_t,\mathbf w_t)]\nabla\hat v(S_t,\mathbf w_t)\\
=& \mathbf w_t+ \alpha (R_{t+1}+\gamma\mathbf w_t^\mathrm T \mathbf x_{t+1}-\mathbf w_t^\mathrm T\mathbf x_t)\mathbf x_t\\
=& \mathbf w_t+ \alpha (R_{t+1}+\gamma\mathbf x_{t+1}^\mathrm T \mathbf w_t-\mathbf x_t^\mathrm T\mathbf w_t)\mathbf x_t\\
=& \mathbf w_t+ \alpha (R_{t+1}\mathbf x_t
-(\mathbf x_t-\gamma \mathbf x_{t+1})^\mathrm T \mathbf w_t\mathbf x_t)\\
=& \mathbf w_t+ \alpha (R_{t+1}\mathbf x_t
-\mathbf x_t(\mathbf x_t-\gamma \mathbf x_{t+1})^\mathrm T \mathbf w_t)\\
\end{align}$
简写$\mathbf x_t=\mathbf x(S_t)$
一旦系统到达稳定状态，对于任意给定的$\mathbf w_t$，下一个更新的权值向量的期望可以写作$\mathbb E[\mathbf w_{t+1}|\mathbf w_t]=\mathbf w_t+\alpha(\mathbf b-\mathbf A \mathbf w_t)=\mathbf w_{t+1}$
其中，$\mathbf b \doteq \mathbb E[R_{t+1}\mathbf x_t]\in\mathbb R^d$，$\mathbf A\doteq \mathbb E[\mathbf x_t(\mathbf x_t-\gamma \mathbf x_{t+1})^\mathrm T]\in \mathbb R^d \times\mathbb R^d$
如果系统收敛，必须收敛于满足下式的权值向量 $\mathbf w_{TD}$
$$
\begin{aligned}
& \mathbf b-\mathbf A\mathbf w_{TD} =0 \\
\Rightarrow &\mathbf b=\mathbf A\mathbf w_{TD}\\
\Rightarrow &\mathbf w_{TD}\doteq\mathbf A^{-1}\mathbf b
\end{aligned}
$$
这个量被称为TD不动点。
线性半梯度TD(0)最终收敛到TD不动点$\mathbf w_{TD}$，且该不动点对应的预测误差上界如下：$\overline{\mathbf{VE}}(\mathbf w_{TD})\leq \frac{1}{1-\gamma}\min_{\mathbf w}\overline{\mathbf{VE}}(\mathbf w_{MC})$，即TD法的渐进误差不超过MC最小误差的$\frac1{1-\gamma}$倍，当$\gamma \rightarrow 1$时，$\frac1{1-\gamma}\rightarrow \infty \Rightarrow \overline{\mathbf{VE}}(\mathbf w_{TD}) \rightarrow \infty$。TD学习快，但有偏。
5. 线性方法的特征构造
$\hat v(s,\mathbf w)\doteq \mathbf w^\mathrm T \mathbf x(s) \doteq \sum_{i=1}^{d}w_ix_i(s)$
讨论特征$\mathbf x(s)$的构造，考虑因素：
多项式基
状态通过数字表达，例如位置和速度。
假设一个状态$s$对应$k$个数字分量$s_1,s_2,\ldots,s_k$，每一个$s_i\in\mathbb R$。对这个$k$维的状态空间，每一个$n$阶多项式基特征$x_i$可以写作$x_i(s)=\Pi_{j=1}^ks_j^{c_{i,j}}$，$c_{i,j}$是集合$\{0\;1\, …\, n\}n\geq0$中的一个整数。用于$k$维状态的$n$阶多项式基特征，含有$(n+1)^k$个不同的特征。
缺点：$n$阶多项式基的特征随着状态空间维数呈指数增长。
练习9.3
特征向量$\mathbf x(s)=(1,s_1,s_2,s_1s_2,s_1^2,s_2^2,s_1s_2^2,s_1^2s_2,s_1^2s_2^2)$中的$n$和$c_{i,j}$分别是多少？
$n=2$
$ C= \left ( \begin{array}{ll} 0& 0\\ 1& 0\\ 0& 1\\ 1& 1\\ 2& 0\\ 0& 2\\ 1& 2\\ 2& 1\\ 2& 2\\ \end{array} \right)$
傅里叶基
傅里叶方法考虑使用sin，cos函数来作为基函数，如果将T设为原来的两倍，便能在半周期$[0,\frac T 2]$内，只用cos或只用sin作为基函数，但sin函数的线性组合往往是基函数，容易在原点处不连续，所以一般考虑用cos作为基函数。
一维状态
$x_i(s)=\cos(i\pi s),s\in[0,1]$
其中，$i=0,1,…,n$
k维状态
假设每个状态$s$对应一个$k$维向量，$\mathbf s=(s_1,s_2,\ldots,s_k)^\mathrm T,s_i\in[0,1]$。$n$阶傅里叶余弦基的第$i$个特征可以写作$x_{i}(s)=\cos \left(\pi \mathbf{s}^{\mathrm{T}} \mathbf{c}^{i}\right)$
其中：
$\mathbf c^i=(c^i_1,c^i_2,\ldots,c^i_k)^\mathrm T$
$c^i_j\in\{0,\ldots,n\}$表频率
$j=1,\ldots,k$
$i=1,\ldots,(n+1)^k$
这样就对于$(n+1)^k$种可能的每一个整数向量$\mathbf c^i$定义了一个特征。内积$\mathbf s^\mathrm T\mathbf c^i$的作用是把$\{0,\ldots,n\}$中的一个整数赋给$s$中的每一维。
粗编码
将特征表示为在状态空间中的圆。
如果状态在圆内，则对应特征为1，称作出席；否则特征为0并称作缺席。
上图中，$S$被三个特征覆盖，即$x_i(S)=x_j(S)=x_k(S)=1$，而相邻状态$S’$被两个特征覆盖，即$x_z(S)=x_k(S)=1$，因此$S$和$S’$在特征$x_k(S)$上重叠。一旦$v(S)$被更新，对应$w_i,w_j,w_k$均被更新，而$v(S’)$的组成部分中含有$w_k$，因此也被间接更新。通过特征来训练权重。
特征受大小和形状影响，形状包括：
实验表明：
特征较小的在少样本下性能差，容易出现多个陡峰；
特征较大的在少样本下性能稳定；
无论特征大小，在大样本下渐进性能都很好，差别不大。
原因是：更新某个$v(S)$时，由于特征太小，只更新了自己；而当特征太大时，则同时更新了所有。
瓦片编码
瓦片编码是一种用于多维连续空间的粗编码，具有灵活并且计算高效的特性。
特征的感受野组成了状态空间中的一系列划分，每个划分被称为一个覆盖(tiling)，划分中的每一个元素被称为一个瓦片(tile)。例如二维空间中最简单的划分就是左侧均匀网络，其中瓦片是正方形。如果使用单一的划分，那么白点所示的状态就会被它所处的瓦片这一单一特征所表达。通过对瓦片进行一定比例的偏移，以保证不同的覆盖有重叠。偏移需要保证能够完整覆盖状态空间。
右图包含4个覆盖，白点表示状态在每个覆盖中都只位于一个瓦片内。4个瓦片代表了这个状态发生时会激活的4个特征。特征向量$\mathbf x(s)$对应每个覆盖中的每一个瓦片有一个分量，总共有444=64个分量。
优点：由于是整体空间的划分，所以任何状态在每一 时刻激活的特征的总数是相同的。每一个覆盖中有且只有一个特征被激活，所以特征的总数总是等于覆盖的个数。
偏移影响泛化能力：
当每个tiling是按某个方向均匀偏移时，则最终产生的覆盖是对称的或按某个方向堆叠，此时当某个状态更新时，泛化会沿该方向进行其他状态的更新，导致泛化不均匀。而当tiling是在状态空间周围均匀堆叠时，产生的泛化即是均匀的。
瓦片的形状也决定了渐进近似的分辨率和粒度：
通过哈希编码可以在忽略不计的内存损失下大幅降低内存需求
径向基函数
径向基函数（RBF）是粗编码在连续特征上的推广，之前粗编码采用0,1布尔编码特征，覆盖状态的所有特征均为1，其余为0；而在RBF中，特征值是反映了特征在该状态上的覆盖程度的连续值，可以是[0,1]区间的任意值。
典型的径向基函数特征$x_i$，有如下高斯函数，特征值只取决于状态$s$和特征的中心状态$c_i$的距离，并与特征的宽度$\sigma_i$相关。
$x_i(s)\doteq \mathtt{exp}(-\frac{\Vert s-c_i\Vert^2}{2\sigma_i^2})$
缺点：计算复杂度过高；需要大量手动调参；高维状态性能下降
6. 手动选择步长参数
随机近似理论$\sum_{n=1}^{\infty} \alpha_{n}(a)=\infty \text { 且 } \sum_{n=1}^{\infty} \alpha_{n}^{2}(a)<\infty \text {. }$
7 非线性函数逼近：人工神经网络
ANN的计算单元是半线性的，首先求加权和，然后通过激活函数，得到单元输出。
激活函数一般为S形（例如logistic函数）、整流或阶梯函数。
然而，如果 ANN 拥有一个隐层，并且这个隐层包含足够多数量的 sigmoid激活单元，则这个 ANN 可以在网络输入空间的一个紧凑区域内以任意精度逼近任意的连续函数 。具有非线性激活函数才能用网络逼近输入输出映射关系，线性激活函数则不可以。ANN根据随机梯度下降法来更新权重。在包含隐层的ANN的梯度最有效的是反向传播算法。
对于深度ANN，网络结构越复杂效果不一定越好，因为复杂的网络结构中参数更多，很难避免过拟合的现象。（过拟合：网络难以泛化到训练数据没有的情况）
- 防止过拟合——随机丢弃法（Dropout）
在训练时，网络中的单元包括对应的连接会被随机丢弃，测试阶段这些网络的结果组合在一起。
- 批量块归一化
在深度ANN中，将较深的层的输出在输入给下一层之前归一化。小批次的数据集相对于总体的数据集来说是给网络带来的了一些噪声，这些噪声的存在在一定程度上防止了过拟合。
- 深度残差学习
在深度 ANN 中，可以将若干隐层组成 个模块，通过在模块旁边加入”捷径连接” (或称”翻越连接” )来学习一个残差函数。这些连接将模块的输入直接送给它的输出，且没有增加额外的权值。
8 最小二乘时序差分（LSTD）
通过估计A, b计算TD不动点。
$\mathbf{w}_{\mathrm{TD}}=\mathbf{A}^{-1} \mathbf{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}$
$\widehat{\mathrm{b}}_{t} \doteq \sum_{k=0}^{t-1} R_{t+1} \mathbf{x}_{k}$
$\varepsilon \mathbf{I}$可以保证$\widehat{\mathbf{A}}_{t}$总是可逆的。两个估计没有除以t是因为在$\mathbf{w}_{\mathrm{TD}}$的计算公式中抵消了。
- 复杂度
两个估计量可用增量式计算，保持每次计算时间在常数复杂度内。而$\widehat{\mathbf{A}}_{t}$的更新需要计算外积，计算复杂度和空间复杂度都为$O(d^2)$。$\widehat{\mathbf{A}}_{t}$的逆计算复杂度为$O(d^3)$，我们可以用sherman-morrison公式降低计算复杂度。
sherman-morrison公式：$\left(A+u v^{T}\right)^{-1}=A^{-1}-\frac{A^{-1} u v^{T} A^{-1}}{1+v^{T} A^{-1} u}$
带入得到$\begin{aligned}
\widehat{\mathbf{A}}_{t}^{-1} &=\left(\widehat{\mathbf{A}}_{t-1}+\mathbf{x}_{t-1}\left(\mathbf{x}_{t-1}-\gamma \mathbf{x}_{t}\right)^{\top}\right)^{-1} \\
&=\widehat{\mathbf{A}}_{t-1}^{-1}-\frac{\widehat{\mathbf{A}}_{t-1}^{-1} \mathbf{x}_{t-1}\left(\mathbf{x}_{t-1}-\gamma \mathbf{x}_{t}\right)^{\top} \widehat{\mathbf{A}}_{t-1}^{-1}}{1+\left(\mathbf{x}_{t-1}-\gamma \mathbf{x}_{t}\right)^{\top} \widehat{\mathbf{A}}_{t-1}^{-1} \mathbf{x}_{t-1}}
\end{aligned}$
但其复杂度$O(d^2)$仍高于$O(d)$，是否使用LSTD计算花费取决于d有多大，是否值得。
LSTD不需要设置步长，但$\varepsilon$的设置仍是我们需要考虑的，太小逆的变化大，过大学习过程会很慢。
LSTD没有遗忘机制，在控制应用中其与遗忘机制的方法相结合，这时其不需设置步长的优势就消失了。
9基于记忆的函数逼近
它们仅仅在记忆中保存看到过的训练样本(至少保存样本的子集)而不更新任何的参数。每当需要知道查询状态的价值估计值时，就从记忆中检索查找出一组样本，然后使用这些样本来计算查询状态的估计值。这种方法有时被称为拖延学习 (lazy learning) ，因为处理训练样本被推迟到了系统被查询的时候。
基于记忆的函数逼近是非参数化方法的主要例子。与参数化方法不同，非参数化方法逼近函数的形式不局限于一个固定的参数化的函数类(例如线性函数或者多项式函数) 而是由训练样本本身和一些将它们结合起来为查询状态输出估计值的方法共同决定。当更多的训练实例在记忆中积累时，我们希望非参数化方法可以对任何目标函数生成更加精确的估计。
不同的方法间的主要区别在于如何选择和使用储存下来的训练样本以回应查询操作。
- 局部学习法
使用查询某个状态的相邻的状态来估计其价值函数的近似值。该方法从记忆中检索出一组和查询状态最相关的训练样本，相关性取决于状态之间的距离：训练样本和查询状态越靠近，我们就认为它们越相关，而状态之间的距离可以用许多不同的方法来定义。在查询状态得到它的价值估计后，这个局部的近似就被舍弃了。
- 最近邻居法
它简单地在记忆中找到与查询状态最相近的实例，并且将该最近邻样本的价值返回作为查询状态的价值近似。加权平均法则检索一组最近的样本，然后返回目标值的加权平均值，而权值一般随着状态与查询状态之间的距离增加而下降。局部加权回归通过参数化的近似方法拟合一个曲面，该曲面会最小化加权误差，这里误差的权值取决于和查询状态之间的距离。
基于记忆的方法vs参数化方法
基于记忆的局部近似可以将函数逼近集中在真实或者模拟轨迹中的访问过的状态的局部邻域。全局近似估计是没有必要的，因为状态空间中的许多区域永远不会(或者几乎不会)被访问到。基于记忆的方法允许智能体对于当前状态、邻域的价值估计有即时的影响，而参数化方法则需要不断增量式地调整参数来获得全局近似。
在基于记忆的方法中如何快速查询与搜索非常重要。加速近邻搜索的方法一种是使用并行计算机或者特制硬件，另一种是使用特殊的多维数据结构储存训练数据。其中一种数据结构是k-d树，它递归地将k维空间划分成二叉树节点可以表示的空间。可以排除空间中大片无关区域。
10 基于核函数的函数逼近
而权值往往基于 s’ 和查询状态s之间的距离。分配权值的函数我们称之为核函数，或者简称为核。更一般地，权值不是一定取决于距离，也可以基于一些其他衡量状态之间的相似度的方法。
核函数回归是一种基于记忆的方法，它对记忆中储存的所有样本的对应目标计算其核函数加权平均值，并将结果返回给查询状态。如果$\mathcal{D}$是一组储存的样本，而 g(s’) 表示储存样本中状态s’的目标结果，那么核函数回归会逼目标函数 ，在这种情况中，基于$\mathcal{D}$的价值函数表示为：
$\hat{v}(s, \mathcal{D})=\sum_{s^{\prime} \in \mathcal{D}} k\left(s, s^{\prime}\right) g\left(s^{\prime}\right)$
普通加权平均法只有当s和s’相邻时$k(s,s’)$的值才不为0。
RBF函数逼近——常用的核函数
可以用线性参数化方法的“去除法”，也可以用基于记忆样本的非参数化方法。
任何线性参数化回归方法，状态由特征向量$\mathbf{x}(s)=\left(x_{1}(s), x_{2}(s), \ldots, x_{d}(s)\right)^{\top}$表示的，都可以被重塑为核函数回归，在这里 k(s，s’) 是状态s’的特征向量内积，即
$k\left(s, s^{\prime}\right)=\mathbf{x}(s)^{\top} \mathbf{x}\left(s^{\prime}\right)$
11 深入了解同轨策略学习：“兴趣”与“强调”
在某些场景中，某些状态比其他状态更感兴趣。例如在带折扣的分幕式问题中，对可以精确估计价值的早期状态更感兴趣，因为那些后期状态获得的收益由于折扣的存在对初始状态的价值贡献不大。在估计动作价值函数中，精确地去估计那些比起贪心动作要差很多的动作的价值函数并不那么重要。我们需要更加专注于有用的函数逼近。
兴趣值：$I_t$表示我们在t时刻有多大兴趣估计一个状态的价值。该值在0-1之间，越大越有兴趣。
强调值：$M_t$这个标量会被乘上学习过程中的更新量，决定了再t时刻强不强调“学习”。
将$\mathbf{w}_{t+n} \doteq \mathbf{w}_{t+n-1}+\alpha\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), 0 \leqslant t<T$用更一般的形式代替。
$\begin{array}{c}
\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), 0 \leqslant t<T
\end{array}$
$M_{t}=I_{t}+\gamma^{n} M_{t-n}, 0 \leqslant t<T$
用梯度蒙特卡洛算法没有考虑兴趣值与强调值，$w=(w_1,w_2)^T$将收敛到（3.5，1.5），与真实值有误差。但使用兴趣值和强调值的方法，将$w_1$兴趣值设置1，其余设置为0，则会正确学习第一个状态的价值。用两步半梯度结合兴趣值与强调值能收敛到$w=(4,2)$。