本书第五章就已经讲解过分别使用on-policy和off-policy方法来解决GPI框架里固有的explore和exploit的矛盾。前两章已经讲了on-policy情形下对于函数近似的拓展，本章继续讲解off-policy下对函数近似的拓展，但是这个拓展比on-policy时更难更不同。在第六第七章中讲到的off-policy方法可以拓展到函数近似的情况下，但是这些方法在半梯度法下不能像在on-policy下一样良好地收敛。这一章我们将会讨论收敛的问题并且更进一步观察线性函数近似的理论。介绍一个可学习性（learnability）的概念以及讨论能够在off-policy下提供更强收敛性的新算法。
函数近似下的off-policy算法主要有两个难点。第一个在网格形式下就有，另一个是源自函数近似方法。第一个难点就是对于更新目标的修正，另一个就是解决更新的分布的问题。第五章和第七章的方法以及可以解决第一个修正更新目标的问题，尽管这些方法会带来很大的方差但是在网格下和函数近似下都是必不可少的。这些方法到函数近似的拓展就可以解决第一个难点。
第二个在函数近似off-policy算法中的难点需要额外的方法来解决，因为off-policy下产生的更新分布不是根据on-policy分布。而on-policy分布对于半梯度方法的稳定性很重要。大致两种方法可以解决这个问题。第一种是再次使用importance sampling的方法将更新的分布变形至on-policy的分布，这样就能够保证（线性逼近下）半梯度法的收敛性。另一种方法是使用真正的不需要依赖特定分布就保证收敛的梯度下降法。我们这两种方法都提供了。
11.1 Semi-gradient Methods
先进行描述如何把先前表格型off-policy情形下的算法改编为半梯度法。这些方法解决了off-policy下的第一个难题也就是更新目标的修正。这些方法在某些情形下会发散，但是依然能够成功使用。首先记住这些方法能够在表格情形下保证收敛至渐进无偏的值，而表格情形是函数逼近的一种特殊情况。所以依然有可能将这些算法与某些特征选择方法结合来达到类似的收敛效果。
为了将第七章中很多off-policy算法改编为半梯度的形式，我们只需要简单的把对于一个值函数列表的更新改编为对近似函数和其梯度的使用以及对参数
的更新。每一步中的importance sampling ratio为：
比如一步状态值函数算法也就是半梯度off-policy TD(0)算法的更新和on-policy形式的更新没有什么不同，除了增加了采样比重：
其中误差
可以分为episodic和continuing两种情形：
而对于使用动作值函数的情况，一步算法是半梯度Expected Sarsa算法：
这个算法没有使用importance sampling。对于表格形式下这很好理解，因为只学习了一个动作
的值函数，而不需要考虑其它动作。使用函数逼近这个概念就不那么清晰，因为可能有不同的状态动作对会改变当前值函数的估计，而这些对需要被不同对待。
在这些算法的多步形式中，状态值函数和动作值函数算法都需要importance sampling。比如n步半梯度expected Sarsa算法：
其中反馈也有episodic和continuing两种形式（感觉此处有误，个人感觉这似乎不是expected Sarsa而是普通Sarsa）：
这里写的不太规范因为最后t+n可能大于T。
以及第七章还有一种不需要importance sampling的算法：n步tree-backup算法。它的半梯度法如下：
11.2 Examples of Off-policy Divergence
这节开始讨论第二个off-policy使用函数近似下的难题，也就是更新的分布不同于on-policy的分布。描述了一些指导性的反例来说明半梯度法和其它一些算法的不稳定性和发散性。
例子描述略过。结论是，参数更新的稳定性和步长参数无关，只需要步长是大于0。更大或者更小的步长只会影响参数w走向无穷大的速度而不是它是否会发散。
例子中的关键部分就是这个状态的转移一直重复的发生而没有在其它转移上进行过更新。这是一种off-policy下可能的情况，因为行为策略可能在别的转以上都选择了目标策略不会选择的动作。这个简单的例子说明了off-policy发散的原因，但是它并不完全，这只是一个MDP过程的片段。还有个例子叫做Baird's counterexample的使用状态值函数V的例子。这个例子说明了只要是bootstrapping和半梯度法函数近似在不遵循on-policy分布的时候进行结合，那么参数都不会收敛。
对于Q-learning来说也有一个表示其发散的例子。而Q-learning如果收敛那么他就是最能够保证收敛的control算法。因此进行了一些修补，只要是使用和目标策略足够相近的策略就可以保证参数收敛比如动作策略是目标策略的
-greedy策略。目前还没有发现在这种情况下Q-learning会发散。
那么我们改变策略，并不是每一步仅进行一次值函数更新而是每一步都找到一个最好的最小平方差的值函数估计。但是这样依然不能够保证稳定性。
11.3 The Deadly Triad
目前讨论的不稳定性和发散的风险都来源于对以下三个元素的组合，因此叫它们deadly triad：
- 函数近似：一种强大可拓展对于有着超过存储和计算极限大小的函数空间的问题的泛化方式。
- 自举：使用当前的估计值来组成更新目标值，而不是仅仅依赖完整的奖励值序列（如MC方法那样）。
- off-policy 训练：在一个不同于目标策略下的分布的转移上进行训练。比如DP算法遍历每个状态而不关心当前目标策略。
需要提到这个风险不是因为control算法或者GPI。这个风险的原因很难分析，但是不论如何简单的例子，只要使用了这三种元素的组合那么就会导致不稳定。也不是来源于环境的不确定性或者学习算法，因为它对于知道了所有环境模型细节的DP算法依然严重。如果只使用这三个元素之二，那么这种不稳定性就可以避免。因此来看看可以放弃哪一项。
对于function approximation来说是这三个元素里最清楚的不能被放弃的一个。我们需要能够延伸到大型问题以及更有表现力的算法。
不使用bootstrapping是有可能的，只不过牺牲了计算效率和数据效率。使用MC方法需要记录每次转移的细节和最后中止状态的奖励。而使用boostrap和eligibility traces可以立刻处理产生的数据，能够节省很多空间和通信。而放弃bootstrapping在数据效率方面的损失也是巨大的。bootstrapping能够带来更快速的学习因为它能够利用状态的属性以及识别一个状态的能力。另一方面bootstrapping能够修补状态表示较差和其带来的更差的泛化表示的问题。一个较差的状态表示也会导致偏差，这就是bootstrapping算法会导致更差的渐进逼近上限的原因。
而最后，off-policy学习。常常on-policy就已经够用了。对于不需要环境模型的强化学习算法，可以直接使用Sarsa算法而不是Q-learning算法。off-policy将行为从目标函数中分隔开，这可以看成一种方便但不是必须的。不过off-policy在很多其他方面很有作用。
11.4 Linear Value-function Geometry
为了更好的理解off-policy学习的稳定性难题，可以更加抽象的思考值函数逼近而不考虑学习算法。可以想象所有可能的状态值函数的一个空间，所有的函数都是从状态到实数值v的映射：
。大部分的值函数都不表示一个策略，更重要的是大部分的值函数不能够使用函数逼近器来表示，因为使用了比状态世纪少了很多的参数。
考虑有三个状态
和两个参数
。因此可以把所有的值函数当做是一个三维空间的点。而每个参数向量就是一个二位空间的一个点，同样也是对于每个状态赋予值的值函数
。普通的值函数和参数空间表示的值函数关系很复杂，但这里我们只考虑线性值函数逼近的情况，因此只是一个简单的平面，如同下图。
考虑一个固定策略
，其真值
比较复杂无法在参数平面中表示，用在平面上方的一个点表示。那么哪个能够使用参数表示的函数是最接近这个真实函数的？这个问题有好几个不同的答案。首先需要一个测量两种函数之间距离的方法。定义了一个距离范数：
，那么
就可以简单的使用
表示。定义一个投影操作
来将任意的值函数投影到在我们定义的范数意义上最接近的可以在参数平面表示的值函数投影：
距离真值函数最近的投影即为上式所述。这是使用MC方法渐进得到的结果，虽然收敛很慢。
使用TD算法会得到另外的答案。回忆起贝尔曼等式中值函数为：
只有真正的值函数才能满足上述等式。因此如果使用近似值函数来替换等式中的v，左边和右边的差值可以看作是近似值与真实值之间的差值，我们叫做在状态s时的Bellman error：
Bellman error是TD error的期望值。每一个状态上的bellman error写为一个向量则叫做Bellman error vector。这个向量的总的范树叫做最小均方Bellman误差：
总的来说不可能使这个误差值归为0，但是对于线性函数逼近来说有一个唯一的系数w使得其最小。这个在参数平面上的点一般是和最小化的点不同。贝尔曼误差向量在上图中也有表示，它作为对近似值函数实施Bellman operator 
得到。贝尔曼操作符定义为：
对于v来说贝尔曼误差向量可以写作
。如果对参数平面的点实施bellman operator那么一般会得到一个平面外的点。最终会慢慢收敛到真值函数，也是唯一一个对于Bellman operator的不动点：
这也是bellman等式的另一种写法。
我们比较关注Bellman error vector投影到参数平面的结果。这个结果的范数值是另一种评估近似值函数误差的方式。对于任意的近似值函数v，我们定义一个最小均方投影贝尔曼误差：
对于线性近似函数总有一个近似的值函数
为0。这也就是之前说的TD不动点
。之前也说道，这个点在半梯度TD算法off-policy训练下不总是稳定的。一般也会与最小化
和的点不同。
11.5 Gradient Descent in the Bellman Error
现在考虑最小化这些误差的方法，一般使用随机梯度下降法。这些方法在期望上一直是在往目标函数减小的方向移动因此一般能够获得较好的收敛性。这些本书中已经描述的方法里，只有MC方法中使用的是真正的SGD算法。这个算法在on-policy和off-policy下都能够稳定的收敛，尽管收敛速度可能比使用了自举的半梯度法更慢。但是使用了自举的并不是真正的SGD法。半梯度法有可能在off-policy下发散，但是真正的SGD不会。
我们考虑目标函数Bellman error的起源和限制。尽管这个误差经常使用，但我们得出的结论是这是个错误而且不会产生好的学习算法。首先考虑的不是Bellman error而是更直接的TD error。考虑直接把TD error平方的期望值作为目标函数，那么一个可能的函数叫做最小均方TD误差：
最后一个等式是SGD方法需要的形式。那么使用标准的SGD方法得到参数的更新迭代为：
可以看到除了最后一项前面的和半梯度下降TD算法一样。这里它变成了真正的SGD算法并且有很好的收敛性保证。把这个算法叫做naive residual-gradient算法。尽管它能保证收敛但不能保证收敛到需要的地方。
还有个更好的方法似乎可以是直接最小化Bellman error。因此可以尝试重复之前的推导：
这个更新和采样的方式叫做residual-gradient algorithm。如果只是简单地在所有的期望的部分使用采样值替代，那么这个等式会退化到naive residual-gradient算法。这个方式会是naive的原因在于等式中前后两项都有下一状态
的值函数。为了得到这个结果的无偏采样，需要下一状态的两个独立的估计值，但是在正常的与环境交互的过程中只能得到一个。这里有两种方式来使得这个方法起效。一是在确定性的环境中使用，因为对于确定性环境来说，两次采样下一状态的值肯定是一样的。另一种方式是从当前状态中得到下一状态的两个独立估计值。这在与环境真实交互的时候是不可能的，但是在仿真环境里是可能的。作为一个真正的SGD方法，这个算法会在线性和非线性情况下都收敛。而在线性情况下，收敛结果一定会是能够最小化的点。
但是这个方法的收敛性依然有三个不太让人满意的地方。第一就是实际经验中这个方法很慢，比半梯度法慢得多。第二个地方就是算法似乎依然会收敛到错误的值。第三点下一节说。
11.6 The Bellman Error is Not Learnable
这一章所说的可学习性的概念和机器学习中常用的不一样。机器学习里说的可学习是只能够高效学习，意味着能够从样例中在多项式时间内完成学习而不是指数级时间。但是在这里，科学系性质的是是否能够学习到，而不关心样例的数量或者时间。结果是强化学习中很多明显关注的量都不能够从有限数量的经验数据中学习到。这些量定义的很好而且能够根据环境内部结构的给定值时得到，但是不能够从观察到的特征向量动作和奖励序列中计算出或者估计到。所以说他们是不可学习的。从这个意义上Bellman error目标函数是不可学习的。
举了个栗子（略）。栗子说明了没有办法学习出MDP是否是确定性的以及状态数量。同样也说明了是不可学习的。但是虽然是这样，但是拥有相同数据分布的MDP也会拥有相同的最优参数。因此依然是个有用的目标，因为最小化这个目标的参数是可学习的。
再介绍个确定可以学习的目标函数，那就是每个反馈与值估计之间的均方误差：
可以看出除了后面一项方差，两个目标函数是一样的，因此也会拥有一样的最优参数解。
然后回到。这个值像一样可以MDP的知识中得到但是不能够从数据中学习到。但是它不像的地方是它的最小值解也是不可学习的。我们也考虑了另外的使用自举的目标函数PBE和TDE，他们是可以学习的，他们的最优解一般和互相之间都是不一样的。
因此是不可学习的，这使得只能用于基于模型的设定中。residual-gradient算法只能够最小化因为它能够允许采样两次同一状态的不同值，而且必须是同一状态而只是状态特征向量相同的状态。因此并没有办法可以做到。所以最小化需要首先能够取得MDP的一些固有属性。这是个很重要的限制。因此我们更多关注。
11.7 Gradient-TD Methods
现在考虑使用SGD算法最小化。作为一个真SGD方法，Gradient-TD方法即使在off-policy训练和非线性函数逼近下都拥有较好的收敛特性。线性情况下有一个特殊的解，TD固定点，在这个点为0。这个解可以通过使用最小平方的方法接触，但是这是个平方复杂度的方法。因此我们选择使用SGD方法，可以得到线性复杂度和收敛特性。Gradient-TD法距离达到这个目标很接近，只需要一个线性大致两倍的计算复杂度。
为PBE目标函数推导SGD方法（线性情况），可以先把目标函数写为矩阵形式：
目标相对于系数w的梯度为：
为了把其变为SGD方法，我们需要进行某些量的采样并将其当做它的期望值。上面的三个变量矩阵都可以写成期望的形式：
这也就是半梯度法TD(0)更新部分的期望。前一项是这个更新的转置，得到：
最终中间一个因子是下面的量的逆，即：
于是把上述公式进行替代得到：
我们不能将式子中的每个值进行采样然后相乘，这样会得到有偏的估计值。有个想法是将这三个期望值分别进行估计之后再将他们组合起来得到梯度的无偏估计。这可以使用，但是需要大量的计算资源，特别是对于前两项期望的存储。
考虑独立存储某些估计值然后将它们同采样值进行组合是一个好的方法并且也用在了Gradient-TD法里。Gradient-TD法估计并存储前两项的积。这些银子是个dxd的矩阵和一个d维向量，所以他们的积是一个d维向量，就和参数w一样。因此得到v：
这在线性监督学习里很常见。标准的SGD方法渐进地找到能够最小化期望平方误差
的向量v。也叫作最小平方均值规则（LMS）：
我们可以使用这个方法达到每步线性复杂度的存储和更新。
因此在有了存储的v的情况下，使用SGD算法更新参数的公式为：
这个算法叫做GTD2.如果其中的内积首先计算过，那么整个算法就是线性复杂度。
而还有一个稍微改进的算法可以在使用v之间更多一些分析之后得到，也就是：
同样在计算内积之后是个线性复杂度的方法。这个算法可以叫做TDC或者GTD(0)。
GTD2和TDC算法都包含了两个部分的算法，更新w的部分和更新v的部分。前一个部分依赖于第二部分的完成，而第二部分的计算不收到第一部分的影响。这种非对称依赖性叫做cascade。我们在cascade里一般假设第二部分的计算比第一部分更快。这些方法的收敛性证明里更能看出这一点。
Gradient-TD算法目前是研究最充分而且广泛使用的稳定的off-policy的算法。在这之上还有很多研究。
11.8 Emphatic-TD Methods
然后我们转到第二个最主要的能够获得简单高效的带函数逼近的off-policy学习的策略。线性半梯度TD算法在on-policy分布下高效而稳定。但是在off-policy学习中，我们重新为每个状态转移使用importance sampling赋予权重，但是状态分布依然是行为策略下的分布。一个简单的想法是能够重新赋予每个状态权重，这样就能把反馈改变至符合on-policy的分布。这样之后就能够使用on-policy下的方法得到稳定而收敛的结果。这就是Emphatic-TD方法。
实际上on-policy distribution是个不那么正确的概念，因为可以有很多个on-policy的分布，每一个都能够保证算法收敛。考虑一个undiscounted的episodic问题。每个episode结束的方式是由环境转移概率决定的，但是episode有可能有不同的起始方式。无论episode是如何开始的，如果所有的状态转移都是根据目标策略，那么状态分布就是一个on-policy分布。
如果是一个有discounting的情况，那么它可以被看作是一个目标状态的部分或者概率结束。比如如果
，那么我们可以认为每一步都有0.1的概率到达结束状态然后立即从下一状态重新启动。这种思考discounting的方式有个更一般的概念叫做pseudo termination，也就是一个不会影响状态转移序列的终止状态。但是它会影响学习过程以及正在学习的量。这种伪结束状态的方式对于off-policy来说是很重要的。因为重启是可选的，而且中止状态让我们不需要维持让每个状态转移都在当前策略分布下。也就是说，如果我们不把新状态看作是重启，那么discounting会迅速带给我们一个有限值的on-policy分布。（？？？？）
一步Emphatic-TD算法如下：
这个算法理论上会收敛到最优解，但是实际上并不会。因为方差太大。
11.9 Reducing Variance
off-policy学习算法本质上就会带来比on-policy方法更大的方差。因为我们有很多在期望形势下很稳定的算法，因此我们想要找到减少方差的方法。因为off-policy方法会使用到相对概率，而相对概率是独立的，虽然他们的期望值是1但实际上的值会有很大的方差。因为相对概率会乘以更新步长，因此有时候会进行特别大的更新，这是不应该的。依赖平均梯度的SGD方法效果很好，但是直接使用一个梯度采样的经常会不稳定。
第五章看到了使用weighted Importance sampling能够带来比ordinary importance sampling算法更低的更新方差。但是将其应用到函数逼近里是很困难的，而且可能需要线性时间复杂度。
Tree Backup算法表明不使用Importance Sampling更新off-policy算法是可行的。
另外，还有的策略是允许目标策略部分根据行为策略来定，这样就不会导致两个策略有很大的出入也就不需要相对概率。
11.10 Summary
off-policy学习是一个很大的挑战。表格形式的Q-learning算法让off-policy看起来很容易，而且也有expected Sarsa和tree backup这种延伸算法。但是这一章我们可以看到这种延伸对于函数逼近来说会带来更多的挑战而且迫使我们深入对强化学习算法的理解。
使用off-policy方法的愿意之一是给出解决exploit和explore矛盾更灵活的方法。另一个原因是将学习过程从行为策略中解放，而且避免目标策略的tyranny。TD学习方法可以使用一个数据流来并行学习多个经验。但是不是所有的情形下都适用。
这张我们把挑战分为两个部分。第一部分是从行为策略中得到更新目标。这可以直接使用在表格情形下得到的方法，尽管会增加方差和拖慢学习速度。
另一个部分是半梯度TD法在利用自举时带来的不稳定性。尝试了几种方法。第一是直接使用真正的SGD方法而非半梯度法。但是我们得出结论这个方法在很多情形下不适用。而且也是不可能得出结果的，因为的梯度是不能只通过特征向量的经验而不使用MDP内部特性来学习得到。第二种是在Bellman error的投影上使用SGD法，也就是Gradient-TD方法。这个方法中的梯度是可以学习的。复杂度是线性。第三是最新的解决方法，也就是Emphatic-TD法，重新定义了reweighting更新的方法。这样能够保存那些使得on-policy学习能够在简单的半梯度法下保持稳定的特性。
这个部分依然有很多研究潜力。