type
status
password
date
slug
summary
category
URL
tags
icon
与蒙特卡洛（MC）算法类似，时序差分（TD）算法也是无模型的，但其增量形式使其具备一些优势。实际上，TD算法可被视为求解贝尔曼方程或贝尔曼最优性方程的特殊随机算法。由于本章介绍了很多的TD算法，我们首先对这些算法进行综述并阐明它们之间的关系。
- 7.1节介绍了最基本的时序差分（TD）算法，该算法可用于估计给定策略的状态价值。在研究其他TD算法之前，首先理解这个基本算法非常重要。
- 7.2节介绍了Sarsa算法，该算法可用于估计给定策略的动作价值。此算法可与策略改进步骤相结合以找到最优策略。通过用动作价值估计替换状态价值估计，可以很容易地从7.1节的时序差分（TD）算法得到Sarsa算法。
- 7.3节介绍了n - 步Sarsa算法，它是Sarsa算法的一种推广。将会表明Sarsa算法和蒙特卡洛（MC）算法是n-步Sarsa算法的两种特殊情况。
- 7.4节介绍了Q-learning算法，它是最经典的强化学习算法之一。其他时序差分（TD）算法旨在求解给定策略的贝尔曼方程，而Q-learning旨在直接求解贝尔曼最优性方程以获得最优策略。
- 7.5节对本章介绍的时序差分（TD）算法进行了比较，并提供了一个统一的观点。
7.1 状态价值的时序差分（TD）算法
时序差分（TD）算法通常指一大类强化学习算法。例如，本章介绍的所有算法都属于TD算法的范畴。然而，本节中的TD算法特指一种用于估计状态价值的经典算法。
7.1.1算法描述
给定一个策略，我们的目标是对所有的估计。假设我们有一些按照生成的经验样本。这里，表示时间步。以下的TD算法可以使用这些样本来估计状态价值：
其中。这里，是在时刻对的估计值；是时刻下的学习率，且要求且。
应当注意的是，在时刻，只有被访问的状态的值得到更新。如式（7.2）所示，未被访问的状态的值保持不变。为简单起见，式（7.2）经常被省略，但应牢记这一点，如果没有这个式子，该算法在数学上是不完整的。
特别地，要求每个状态 - 动作对必须被访问无限次（或足够多次）。
7.1.2 时序差分（TD）算法的推导
贝尔曼方程
初次见到时序差分（TD）算法的读者可能会疑惑为什么它要这样设计。实际上，它可被视为一种用于求解贝尔曼方程的特殊随机逼近算法。要明白这一点，首先回顾一下状态价值的定义：
这是因为。式（7.4）是贝尔曼方程的另一种表达形式。它有时被称为贝尔曼期望方程。
时序差分（TD）算法
通过应用Robbins-Monro算法（第6章）求解式（7.4）中的贝尔曼方程就可以推导出（7.1）式中的时序差分（TD）算法。
- 对于状态，我们定义一个函数为：
- 然后，（7.4）式等价于
- 我们的目标是使用Robbins - Monro算法求解上述方程以得到。由于我们能够得到和，它们分别是和的样本，我们能够得到的的含噪观测值为：
因此，用于求解的Robbins-Monro算法（6.2节）为：
其中是在时刻对的估计值，是学习率。
（7.5）式中的算法与（7.1）式中的时序差分（TD）算法有相似的表达式。唯一的区别在于（7.5）式的右侧包含，而（7.1）式包含。这是因为（7.5）式旨在仅通过假设其他状态的状态价值已知来估计的状态价值。如果我们想要估计所有状态的状态价值，那么右侧的应该被替换为。这样，（7.5）式就与（7.1）式完全相同了。然而，这样的替换仍然能确保收敛吗？答案是肯定的，这将在后面的定理7.1中得到证明。——是包含噪声的
7.1.3 性质分析
如下讨论 TD 算法的一些重要特性。首先，我们仔细地研究 TD 算法的表达式。特别是，（7.1）可以被描述为
其中被称为时序差分目标，被称为时序差分误差。可以看出，新的估计值是当前估计值和时序差分误差的组合。
7.1.3.1 为什么被称为时序差分目标呢？
这是因为是算法试图使趋近的目标值。要明白这一点，从（7.6）式两边同时减去可得：
对上述等式两边取绝对值得到
由于是一个小的正数，我们有。于是可得
上述不等式很重要，因为它表明新值比旧值更接近。因此，该算法在数学上驱使趋向于。这就是为什么被称为时序差分（TD）目标。
7.1.3.2 时序差分（TD）误差该如何解释呢？
首先，这个误差被称为时序差分是因为反映了两个时间步和之间的差异。其次，当状态价值估计准确时，从期望的意义上讲，TD误差为零。要明白这一点，当时，TD误差的期望值为
因此，TD（时序差分）误差不仅反映了两个时间步之间的差异，更重要的是，还反映了估计值与真实状态价值之间的差异。
在更抽象的层面上，TD误差可被解释为新息（innovation），它表示从经验样本中获取的新信息。TD算法的基本思想是根据新获取的信息来修正我们当前对状态价值的估计。新息在许多估计问题（如卡尔曼滤波[33, 34]）中是非常重要的。
7.1.3.3 TD算法仅估计状态价值
式（7.1）中的时序差分（TD）算法只能估计给定策略的状态价值。要找到最优策略，我们仍然需要进一步计算动作价值，然后进行策略改进。这将在7.2节介绍。然而，本节介绍的TD算法非常基础，对于理解本章中的其他算法非常重要。
7.1.3.4 TD learning与MC learning
第三，虽然时序差分学习和蒙特卡洛（MC）算法都是无模型的，但它们各自的优缺点是什么呢？答案总结在表7.1中。
TD learning | MC learning |
增量式：时序差分（TD）学习是增量式的。它可以在收到一个经验样本后立即更新状态/动作价值。 | 非增量式：蒙特卡洛（MC）学习是非增量式的。它必须等到一个回合（episode）结束后收集经验样本。这是因为它必须计算该回合的折扣回报（discounted return）。 |
持续型任务：由于时序差分（TD）学习是增量式的，所以它能够处理回合型（episodic）和持续型任务。持续型任务可能没有终止状态。 | 回合制任务：由于蒙特卡洛（MC）学习是非增量式的，它只能处理在有限步数后终止回合的回合制任务。 |
Bootstrapping：时序差分（TD）学习存在Bootstrapping现象，因为状态/动作价值的更新依赖于该值之前的估计值。因此，时序差分学习需要对这些值进行初始猜测。 | Non-bootstrapping：蒙特卡洛（MC）方法不是Bootstrapping的，因为它可以直接估计状态/动作价值而无需初始猜测。 |
Low estimation variance：时序差分（TD）的估计方差低于蒙特卡洛（MC）的估计方差，因为它涉及更少的随机变量。例如，为了估计一个动作价值，Sarsa（同策略的时序差分学习算法）只需要三个随机变量的样本：、、。 | High estimation variance：蒙特卡洛（MC）的估计方差较高，因为它涉及许多随机变量。例如，要估计，我们需要的样本。假设每个回合（episode）的长度为。假定每个状态的动作数量与相同。那么，在一个soft policy下有种可能的回合。如果我们仅仅使用少数几个回合来进行估计，估计方差很高就不足为奇了。 |
7.1.4 收敛性分析
如下给出式（7.1）中时序差分（TD）算法的收敛性分析。
定理7.1（时序差分学习的收敛性）：给定一个策略，通过式（7.1）中的时序差分算法，对于所有，如果且，那么当时，依概率1收敛于。
下面给出关于的一些说明。首先，且这一条件必须对所有都成立。注意，在时刻，如果状态正在被访问，则，否则。这一条件要求状态被访问无限次（或足够多次）。这就要求要么是探索开始（exploring starts）条件，要么是探索性策略，以便每个状态 - 动作对都有可能被多次访问。其次，在实践中，学习率通常被选为一个小的正常数。在这种情况下，这一条件不再成立。当为常数时，仍然可以证明该算法在期望意义上是收敛的[24，1.5节]。
定理7.1的证明
我们基于第6章中的定理6.3来证明收敛性。为此，我们首先需要构建一个如定理6.3中的随机过程。考虑任意状态。在时刻，由式（7.1）中的时序差分（TD）算法可得：
估计误差定义为
其中是策略下状态的状态价值。从（7.7）式两边减去可得：
从（7.8）式两边减去可得：
其表达式与（7.9）式相同，只是且。因此，不管与否，我们得到如下统一表达式：
这就是定理6.3中的过程。我们的目标是表明定理6.3中的三个条件得到满足，从而该过程收敛。
第一个条件如定理7.1中所假设的那样是成立的。接下来我们证明第二个条件是成立的。即，对于所有，。在此，表示历史信息（见定理6.3中的定义）。由于马尔可夫性，一旦给定，或者就不依赖于历史信息。因此，我们有。对于，我们有。于是，很显然可以看到
当时，我们有
由于，上述等式意味着
于是有
因此，在时刻，由（7.10）式和（7.11）式可知，对于所有，不管与否，都有。因此，
这就是定理6.3中的第二个条件。最后，关于第三个条件，
当时，我们有，当时，。由于是有界的，第三个条件可以毫无困难地被证明。
7.2 动作价值的时序差分（TD）算法：Sarsa算法
7.1节介绍的时序差分（TD）算法只能估计状态价值。本节将介绍另一种名为Sarsa的时序差分算法，它可以直接估计动作价值。估计动作价值很重要，因为它可以与策略改进步骤相结合来学习最优策略。
7.2.1 算法描述
给定一个策略，我们的目标是估计动作价值。假设我们有一些按照生成的经验样本：。我们可以使用以下Sarsa算法来估计动作价值：
其中，是学习率，且。这里，是的估计值。在时刻，只有的值被更新，而其他的值保持不变。
特别地，要求每个状态 - 动作对必须被访问无限次（或足够多次）。
Sarsa算法的一些重要性质讨论如下：
- 为什么这个算法被称为“Sarsa”呢？这是因为该算法的每次迭代都需要。Sarsa是“状态 - 动作 - 奖励 - 状态 - 动作（state - action - reward - state - action）”的缩写。Sarsa算法最初是在[35]中被提出的，它的名字是由[3]创造的。
- 为什么Sarsa要这样设计呢？人们可能已经注意到Sarsa与式（7.1）中的TD算法相似。实际上，通过用动作价值估计代替状态价值估计，就可以很容易地从TD算法得到Sarsa算法。
7.2.3 推导
从数学上讲，Sarsa做了什么呢？与式（7.1）中的TD算法类似，Sarsa是一种用于求解给定策略的贝尔曼方程的随机逼近算法：
式（7.13）是以动作价值表示的贝尔曼方程。证明见 Box 7.3。
Box7.3: 证明（7.13）是贝尔曼方程
如2.8.2节所述，以动作价值表示的贝尔曼方程为
该方程建立了动作价值之间的关系。由于
（7.14）式可重写为
根据期望值的定义，上述方程等价于（7.13）式。因此，（7.13）式是贝尔曼方程。
推导
因为所以可以得到下式
- 对于动作价值，我们定义一个函数为：
- 然后，令上式等于0：
- 我们的目标是使用Robbins - Monro算法求解上述方程以得到。由于我们能够得到和，它们分别是和的样本，我们能够得到的的含噪观测值为：
- 因此，用于求解的Robbins-Monro算法（6.2节）为：
Sarsa算法收敛分析
Sarsa算法收敛吗？由于Sarsa是式（7.1）中TD算法的动作价值版本，其收敛结果与定理7.1相似，如下所示。
定理7.2（Sarsa的收敛性）：给定一个策略，通过式（7.12）中的Sarsa算法，对于所有的，如果且，那么当时，依概率1收敛到动作价值。
证明与定理7.1的证明类似，在此省略。且这个条件应对所有的都成立。特别地，要求每个状态 - 动作对必须被访问无限次（或足够多次）。在时刻，如果，那么；否则，。
7.2.2 通过Sarsa学习最优策略
式（7.12）中的Sarsa算法只能估计给定策略的动作价值。为了找到最优策略，我们可以将其与策略改进步骤相结合。这种组合也常被称为Sarsa，其实现过程如算法7.1所示。
如算法7.1所示，每次迭代有两个步骤。第一步是更新被访问的状态 - 动作对的值。第二步是将策略更新为一个- 贪婪（- greedy）策略。值更新步骤只更新在时刻被访问的单个状态 - 动作对。之后，立即更新的策略。因此，在更新策略之前，我们并没有充分评估给定的策略。这是基于广义策略迭代（generalized policy iteration）的思想。此外，策略更新后，会立即使用该策略来生成下一个经验样本。这里的策略是- 贪婪策略，所以它具有探索性。
举例
图7.2展示了一个模拟示例以演示Sarsa算法。与本书中我们看到的所有任务不同，这里的任务旨在找到从一个特定起始状态到目标状态的最优路径。它并非旨在找到针对所有状态的最优策略。在实践中经常会遇到这种任务，其中起始状态（例如家）和目标状态（例如工作场所）是固定的，我们只需要找到一条连接它们的最优路径。这个任务相对简单，因为我们只需要探索靠近路径的状态，而不需要探索所有状态。然而，如果我们不探索所有状态，最终的路径可能是局部最优而非全局最优。
下面将讨论模拟设置和模拟结果。
- 模拟设置：在这个示例中，所有的回合（episode）都从左上角的状态开始，并在目标状态终止。奖励设置为，，。此外，对于所有的，，。对于所有的，动作价值的初始猜测为。初始策略为均匀分布：对于所有的，。
- 学习到的策略：图7.2中的左图展示了通过Sarsa算法学习到的最终策略。可以看出，这个策略能够成功地从起始状态引导至目标状态。然而，其他一些状态的策略可能不是最优的。这是因为其他状态没有被充分探索。
- 每个回合的总奖励：图7.2中右上角的子图展示了每个回合的总奖励。这里，总奖励是所有即时奖励的无折扣总和。可以看出，每个回合的总奖励逐渐增加。这是因为初始策略不好，所以经常得到负奖励。随着策略变得更好，总奖励会增加。
- 每个回合的长度：图7.2中右下角的子图显示每个回合的长度逐渐下降。这是因为初始策略不好，在到达目标之前可能会走很多弯路。随着策略变得更好，轨迹的长度会变短。值得注意的是，一个回合的长度可能会突然增加（例如第460个回合），相应的总奖励也会急剧下降。这是因为策略是-贪婪策略，它有一定几率采取非最优动作。解决这个问题的一种方法是使用逐渐收敛到零的衰减值。
7.6 Sarsa算法变体——Expected Sarsa
Box7.4 Expected Sarsa给定一个策略，其动作价值可以通过期望Expected Sarsa来评估，这是Sarsa算法的一个变体。Expected Sarsa算法为：是策略下的期望值。Expected Sarsa算法的表达式与Sarsa算法的表达式非常相似。它们仅在时序差分（TD）目标方面有所不同。具体而言，Expected Sarsa算法中的TD目标是，而Sarsa算法中的TD目标是。由于该算法涉及一个期望值，所以被称为Expected Sarsa算法。尽管计算期望值可能会稍微增加计算复杂度，但从减少估计方差的意义上讲是有益的，因为它将Sarsa中的随机变量从减少到了。与式（7.1）中的时序差分（TD）算法类似，Expected Sarsa算法可被视为求解以下方程的随机逼近算法：其中
7.6.1 推导
我们回顾一下动作价值的定义
通过应用Robbins-Monro算法（第6章）求解式（7.151）中的贝尔曼方程就可以推导出（7.15）式中的Expected Sarsa算法。
- 对于动作价值，我们定义一个函数为：
- 然后，令上式等于0：
- 我们的目标是使用Robbins - Monro算法求解上述方程以得到。由于我们能够得到和，它们分别是和的样本，我们能够得到的的含噪观测值为：
注意与sarsa算法相比。Excepted sarasa算法中的比sarasa算法中的的噪声更小。
- 因此，用于求解的Robbins-Monro算法（6.2节）为：
其中是在时刻对的估计值，是学习率。
- 将上式代入式 (7.15.4) 可得
7.3 动作价值的时序差分（TD）算法：n步Sarsa算法
本节介绍n步Sarsa算法，它是Sarsa算法的一种扩展。我们将会看到Sarsa算法和蒙特卡洛（MC）学习是n步Sarsa算法的两种极端情况。
回想一下动作价值（action value）的定义：
其中是满足的折扣回报（discounted return）。实际上，也可分解成不同的形式：
应当注意的是，，其中上标仅仅表示的不同分解结构。将的不同分解形式代入（7.16）中的会得到不同的算法。
- 当时，我们有
用于求解此方程的相应随机逼近算法为
这就是（7.12）中的Sarsa算法。
- 当时，我们有
用于求解此方程的相应算法为
其中是的一个样本。实际上，这就是蒙特卡洛（MC）学习算法，它使用从开始的一个回合（episode）的折扣回报来近似的动作价值。
- 对于一般的值，我们有
用于求解上述方程的相应算法为
该算法被称为n步Sarsa算法。
总之，n步Sarsa是一种更通用的算法，因为当时它就变成（单步）Sarsa算法，而当时（通过设置）它就变成蒙特卡洛（MC）学习算法。要实现式（7.17）中的n步Sarsa算法，我们需要经验样本。由于在时刻时还没有收集到，我们必须等到时刻才能更新的值。为此，式（7.17）可以被重写为
其中是在时刻时对的估计值。
由于n步Sarsa算法将Sarsa算法和蒙特卡洛学习算法作为两种极端情况包含在内，所以n步Sarsa算法的性能介于Sarsa算法和蒙特卡洛学习算法之间就不足为奇了。
特别是，如果选择较大的，n步Sarsa算法就接近蒙特卡洛学习算法：估计值具有相对较高的方差，但偏差较小。如果选择较小的，n步Sarsa算法就接近Sarsa算法：估计值具有相对较大的偏差，但方差较低。
最后，这里介绍的n步Sarsa算法仅仅用于策略评估。它必须与策略改进步骤相结合才能学习到最优策略。其实现方式与Sarsa算法类似，在此省略。感兴趣的读者可以查阅[3，第7章]以获取关于多步时序差分学习（multi - step TD learning）的详细分析。
7.4 最优动作价值的时序差分（TD）算法：Q-learning
在本节中，我们将介绍Q-learning算法，这是最经典的强化学习算法之一[38, 39]。回想一下，Sarsa只能估计给定策略的动作价值，并且必须与策略改进步骤相结合才能找到最优策略。相比之下，Q-learning能够直接估计最优动作价值并找到最优策略。
7.4.1 算法描述
Q-learning算法如下：
其中。在此，是最优动作价值的估计值，是的学习率。
Q-learning的表达式与Sarsa的表达式相似。它们仅在时序差分（TD）目标方面有所不同：Q-learning的TD目标是，而Sarsa的TD目标是。此外，给定，Sarsa在每次迭代中需要，而Q-learning仅需要。
为什么Q-learning被设计成式（7.18）这样的表达式呢？从数学上讲它做了什么呢？Q-learning是一种用于求解以下方程的随机逼近算法：
这是以动作价值（action values）表示的贝尔曼最优性方程（Bellman optimality equation）。其证明在框7.5中给出。Q-learning的收敛性分析与定理7.1相似，在此省略。更多信息可在[32, 39]中找到。
证明（7.19）是贝尔曼最优性方程。
根据期望的定义，（7.19）可被重写为
对等式两边取最大值得到
通过记，我们可以将上述方程重写为
这显然是第三章中介绍的基于状态价值（state values）的贝尔曼最优性方程。
7.4.2 离线策略（off-policy）与在线策略（on-policy）
接下来我们引入两个重要概念：在线策略（on - policy）学习和离线策略（off - policy）学习。
与其他时序差分（TD）算法相比，Q-learning略显特殊之处在于Q-learning是离线策略的，而其他算法是在线策略的。
在任何强化学习任务中都存在两种策略：行为策略（behavior policy）和目标策略（target policy）。行为策略是用于生成经验样本的策略。目标策略是不断更新以收敛到最优策略的策略。当行为策略与目标策略相同时，这种学习过程被称为在线策略学习。否则，当它们不同时，学习过程被称为离线策略学习。
离线策略学习的优势在于，它可以基于其他策略（例如，可能是由人类操作员执行的策略）生成的经验样本来学习最优策略。作为一个重要的情况，可以选择行为策略具有探索性。例如，如果我们想要估计所有状态 - 动作对的动作价值，我们必须生成足够多次访问每个状态 - 动作对的回合（episode）。虽然Sarsa使用-贪婪（-greedy）策略来保持一定的探索能力，但的值通常较小，因此探索能力有限。相比之下，如果我们能够使用具有强探索能力的策略来生成回合，然后使用离线策略来学习最优策略，学习效率将显著提高。
要确定一个算法是在线策略的还是离线策略的，我们可以考察两个方面。第一个是算法旨在解决的数学问题。第二个是算法所需的经验样本。
online/offline：另一个可能与在线策略/离线策略相混淆的概念是在线/离线。
在线学习指的是智能体（agent）在与环境交互的同时更新值和策略的情况。离线学习指的是智能体使用预先收集的经验数据来更新值和策略而无需与环境交互的情况。如果一个算法是在线策略的，那么它可以以在线的方式实现，但不能使用由其他策略生成的预先收集的数据。如果一个算法是离线策略的，那么它可以以在线或离线的方式实现。
Sarsa算法是在线策略（on-policy）算法。
原因如下。Sarsa在每次迭代中有两个步骤。第一步是通过求解其贝尔曼方程（Bellman equation）来评估策略。为此，我们需要由生成的样本。因此，是行为策略。第二步是基于的估计值得到一个改进的策略。结果，是不断更新并最终收敛到最优策略的目标策略。因此，行为策略和目标策略是相同的。
从另一个角度来看，我们可以检查算法所需的样本。Sarsa在每次迭代中所需的样本包括。下面将说明这些样本是如何生成的：
可以看出，行为策略是在状态下生成动作以及在状态下生成动作的策略。Sarsa算法旨在估计被记为的策略的动作价值，是目标策略，因为它在每次迭代中基于估计值得到改进。实际上，与相同，因为对的评估依赖于样本，其中是按照生成的。换句话说，Sarsa所评估的策略就是用于生成样本的策略。
Q-learning是离线策略（off-policy）的
根本原因在于Q-learning是一种用于求解贝尔曼最优性方程（Bellman optimality equation）的算法，而Sarsa是用于求解给定策略的贝尔曼方程（Bellman equation）的算法。在求解贝尔曼方程时能够评估相关策略，而求解贝尔曼最优性方程能够直接生成最优值和最优策略。
特别是，Q-learning在每次迭代中所需的样本是。下面将说明这些样本是如何生成的：
可以看出，行为策略是在状态下生成动作的策略。Q-learning算法旨在估计的最优动作价值。这个估计过程依赖于样本。生成的过程不涉及，因为这是由系统模型（或者通过与环境交互）决定的。因此，对的最优动作价值的估计不涉及，并且我们可以使用任何在状态下生成动作。此外，这里的目标策略是基于估计出的最优值得到的贪婪策略（算法7.3）。行为策略不必与相同。
蒙特卡洛（MC）学习是在线策略（on-policy）学习
蒙特卡洛（MC）学习是在线策略（on-policy）学习。原因与Sarsa算法的类似。待评估和改进的目标策略与生成样本的行为策略相同。
7.4.3 实施
由于Q-learning是离线策略的，所以它既可以按照在线策略方式也可以按照离线策略方式来实现。
Q-learning的在线策略版本如算法7.2所示。这种实现方式与算法7.1中的Sarsa算法的实现方式类似。在此，行为策略与目标策略相同，都是- 贪婪策略。
离线策略版本如算法7.3所示。行为策略可以是任何策略，只要它能够生成足够的经验样本即可。当具有探索性时通常是有利的。在此，目标策略是贪婪（greedy）策略而非- 贪婪策略，因为它不用于生成样本，所以不需要具备探索性。此外，这里给出的Q-learning的离线策略版本是离线实现的：首先收集所有的经验样本，然后再进行处理。
7.4.4 示例说明
接下来我们给出一些示例来演示Q-learning。
- 第一个示例如图7.3所示。它展示了在线策略（on - policy）Q-learning。这里的目标是找到从起始状态到目标状态的最优路径。图7.3的说明文字中给出了设置情况。可以看到，Q-learning最终能够找到一条最优路径。在学习过程中，每个回合（episode）的长度缩短，而每个回合的总奖励增加。
- 第二组示例如图7.4和图7.5所示。它们展示了离线策略（off - policy）Q-learning。这里的目标是为所有状态找到一个最优策略。奖励设置为：边界奖励，目标奖励。折扣率。学习率。
- 真实值（基准事实）：为了验证Q-learning的有效性，我们首先需要知道最优策略和最优状态价值的真实值（基准事实）。这里，真实值（基准事实）是通过基于模型的策略迭代算法得到的。真实值（基准事实）在图7.4（a）和（b）中给出。
- 经验样本：行为策略具有均匀分布：在任何状态下采取任何行动的概率都是0.2（图7.4（c））。生成了一个包含100,000步的单回合（图7.4（d））。由于行为策略具有良好的探索能力，该回合多次访问了每个状态 - 动作对。
- 学习结果：基于行为策略生成的回合，Q-learning所学到的最终目标策略如图7.4（e）所示。这个策略是最优的，因为如图7.4（f）所示，估计的状态价值误差（均方根误差）收敛到零。此外，可能会注意到，所学的最优策略与图7.4（a）中的并不完全相同。实际上，存在多个具有相同最优状态价值的最优策略。
- 不同的初始值：由于Q-learning采用自举（bootstraps）方式，算法的性能取决于对动作价值的初始猜测。如图7.4（g）所示，当初始猜测接近真实值时，估计值大约在10,000步内收敛。否则，收敛需要更多的步数（图7.4（h））。然而，这些图表明，即使初始值不准确，Q-learning仍然能够快速收敛。
- 不同的行为策略：当行为策略不具有探索性时，学习性能会显著下降。例如，考虑图7.5所示的行为策略。它们是或的- 贪婪策略（图7.4（c）中的均匀策略可以看作是的- 贪婪策略）。结果表明，当从1降低到0.5，再降低到0.1时，学习速度显著下降。这是因为策略的探索能力较弱，因此经验样本不足。
7.5 统一的观点
到目前为止，我们已经介绍了不同的时序差分（TD）算法，如Sarsa算法、n步Sarsa算法和Q-learning算法。在本节中，我们将引入一个统一的框架来容纳所有这些算法以及蒙特卡洛（MC）学习算法。
特别是，（用于动作价值估计的）时序差分算法可以用一个统一的表达式来表示：
其中是时序差分（TD）目标。不同的时序差分算法有不同的。表7.2给出了一个总结。蒙特卡洛（MC）学习算法可被视为（7.20）的一种特殊情况：我们可以设置，然后（7.20）就变为。
算法（7.20）可被视为用于求解一个统一方程的随机逼近算法。这个方程随着的不同而有不同的表达式。这些表达式在表7.2中进行了总结。可以看出，除了Q-learning旨在求解贝尔曼最优性方程之外，所有这些算法都旨在求解贝尔曼方程。
7.6 总结
本章介绍了一类重要的强化学习算法，即时序差分（TD）学习算法。我们介绍的具体算法包括Sarsa算法、n步Sarsa算法和Q-learning算法。所有这些算法都可被视为用于求解贝尔曼方程或贝尔曼最优性方程的随机逼近算法。
本章介绍的时序差分算法（除Q-learning算法外）用于评估给定策略。即从一些经验样本中估计给定策略的状态/动作价值。结合策略改进，它们可用于学习最优策略。此外，这些算法是在线策略（同策略）算法：目标策略被用作行为策略来生成经验样本。
与其他时序差分算法相比，Q-learning算法略显特殊，因为它是离线策略算法。在Q-learning中，目标策略可以不同于行为策略。Q-learning是离线策略算法的根本原因在于，Q-learning旨在求解贝尔曼最优性方程，而非给定策略的贝尔曼方程。
值得一提的是，有一些方法可以将在线策略（同策略）算法转换为离线策略算法。重要性采样（Importance Sampling）就是一种被广泛使用的方法[3, 40]，并且将在第10章介绍。最后，本章介绍的时序差分（TD）算法有一些变体和扩展[41 - 45]。例如，TD(λ)方法为时序差分学习提供了一个更通用、更统一的框架。更多信息可在[3, 20, 46]中找到。
7.7 问答
- 问：时序差分（TD）学习中的“TD”一词是什么意思？ 答：每个时序差分算法都有一个时序差分误差，它表示新样本与当前估计值之间的差异。由于这种差异是在不同的时间步之间计算的，所以被称为时序差分（temporal - difference）。
- 问：时序差分学习中的“学习”一词是什么意思？ 答：从数学的角度来看，“学习”仅仅意味着“估计”。即从一些样本中估计状态/动作价值，然后基于估计值得到策略。
- 问：虽然Sarsa能够估计给定策略的动作价值，但它如何用于学习最优策略呢？ 答：为了得到一个最优策略，价值估计过程应该与策略改进过程相互作用。也就是说，在一个值被更新之后，相应的策略应该被更新。然后，更新后的策略生成新的样本，这些样本可再次用于估计值。这就是广义策略迭代的思想。
- 问：为什么Sarsa将策略更新为-贪婪策略呢？ 答：这是因为该策略也用于生成用于价值估计的样本。因此，它应该具有探索性以生成足够的经验样本。
- 问：虽然定理7.1和7.2要求学习率逐渐收敛到零，但为什么在实践中它经常被设置为一个小常数呢？ 答：根本原因是待评估的策略一直在变化（或者称为非平稳的）。特别是，像Sarsa这样的时序差分学习算法旨在估计给定策略的动作价值。如果策略是固定的，使用递减的学习率是可以接受的。然而，在最优策略学习过程中，Sarsa旨在评估的策略在每次迭代后一直在变化。在这种情况下，我们需要一个恒定的学习率；否则，递减的学习率可能太小而无法有效地评估策略。虽然恒定学习率的一个缺点是价值估计最终可能会波动，但只要恒定学习率足够小，这种波动是可以忽略的。
- 问：我们应该学习所有状态的最优策略还是部分状态的最优策略呢？ 答：这取决于任务。可能有人会注意到，本章中考虑的一些任务（例如，图7.2）不需要找到所有状态的最优策略。相反，它们只需要找到从给定起始状态到目标状态的最优路径。这种任务对数据要求不高，因为智能体（agent）不需要充分多次访问每个状态 - 动作对。然而，必须注意的是，所得到的路径不能保证是最优的。这是因为如果没有充分探索所有的状态 - 动作对，可能会错过更好的路径。不过，只要有足够的数据，我们仍然可以找到一条较好的或者局部最优的路径。
- 问：为什么Q-learning是离线策略（off - policy）的，而本章中的其他所有时序差分（TD）算法都是在线策略（on - policy）的呢？ 答：根本原因是Q-learning旨在求解贝尔曼最优性方程，而其他时序差分算法旨在求解给定策略的贝尔曼方程。详情可在7.4.2节找到。
- 问：为什么Q-learning的离线策略版本将策略更新为贪婪（greedy）策略而不是-贪婪（-greedy）策略呢？ 答：这是因为目标策略不需要生成经验样本。因此，它不需要具有探索性。