强化学习（五） – 时序差分学习(Temporal-Difference Learning)及其实例—-Sarsa算法, Q学习, 期望Sarsa算法

强化学习（五） – 时序差分学习（Temporal-Difference Learning）及其实例

• • 5.1 TD预测
  • • 例5.1 回家时间的估计
  • 5.2 TD预测方法的优势
  • • 例5.2 随机移动

• 5.3 TD(0)最优性
• • 例5.3：批量更新下的随机行走
  • 例5.4: You are the Predictor
• 5.4 Sarsa:策略 TD控制
• • 例 5.5 Windy Gridworld
• 5.5 Q-学习: Off-policy TD 控制
• • 例5.6: Cliff Walking
• 5.6 期望Sarsa算法
• 5.7 最大化偏差和双重学习
• • 例5.7: 最大化偏差实例

• 5.8 游戏、后状态和其他特殊情况
• 5.9 实例:悬崖寻路
• • 5.9.1 Part 1: TD Control: Sarsa
  • 5.9.2 Part2: TD Control: Q-learning
  • 5.9.3 Part 3: TD Control: Expected Sarsa
  • 5.9.4 完整程序

 如果非要找出一种思想作为强化学习的核心和新意，那无疑是时序差分学习(Temporal-Difference Learning) 或者称为 时序差分迭代法,以下简称为TD。TD学习是蒙特卡洛思想和动态编程（DP）思想的结合。与蒙特卡洛方法一样，TD方法可以直接从原始经验中学习，而不需要环境的动态模型。和DP一样，TD方法部分地根据其他学习到的估计值更新估计值，而不需要等待最终的结果（它们是引导式的）。TD、DP和蒙特卡洛方法之间的关系是强化学习理论中一个反复出现的主题。

像往常一样，我们首先关注策略评估或预测问题，即估计给定策略π 的价值函数v π的问题。 对于控制问题（寻找最优策略），DP、TD和蒙特卡洛方法都使用了广义策略迭代（GPI）的一些变化。方法中的差异主要是它们在预测问题上的方法差异。

5.1 TD预测

TD和蒙特卡洛方法都是利用经验来解决预测问题。给定某个策略π ππ之后的一些经验，两种方法都会对该经验中出现的非终端状态S t 更新其对v π 的估计V 。粗略地讲，蒙特卡洛方法要等到访问后的回报率已知，然后将该回报率作为V ( S t ) 的目标。一个适用于非稳态环境的简单的每次访问蒙特卡洛方法是

Tabular TD(0) for estimating v π 

粗略地讲，蒙特卡洛方法使用对(5.3)的估计作为目标，而DP方法使用对(5.4)的估计作为目标。蒙特卡洛目标是一个估计值，因为(5.3)中的预期值是不知道的；用一个样本收益来代替实际预期收益。DP目标是一个估计值，不是因为预期值(期望值假设完全由一个环境模型提供)，而是因为v π ( S t + 1 ) 不知道，而使用当前的估计值V ( S t + 1 ) 来代替。TD目标是一个估计值，原因有二：它对(5.4)中的预期值进行采样，并且它使用当前估计值V 代替真实的v π  。因此，TD方法结合了蒙特卡洛的采样和DP的引导。正如我们将看到的那样，这可以使我们在获得蒙特卡洛和DP方法的优点方面有更好的结果。

上图为tabular TD(0)的备份图。备份图顶部的状态节点的值估计是根据从它到紧接着的状态的一个样本转换来更新的。我们把TD和蒙特卡洛更新称为样本更新，因为它们涉及到向前看一个样本的后续状态（或状态动作对），利用后续状态的值和沿途的回报来计算一个备份值，然后相应地更新原始状态（或状态动作对）的值。样本更新与DP方法的预期更新不同的是，它们是基于单个样本继任者，而不是基于所有可能的继任者的完整分布。

 最后，请注意，TD(0)更新中括号内的量是一种误差，衡量S t 的估计值与较好的估计值R t + 1 + γ V ( S t + 1 )之间的不同。这个量称为TD误差，在整个强化学习中以各种形式产生。

请注意，每次的TD误差是当时所做估计的误差。因为TD误差取决于下一个状态和下一个奖励，所以它实际上要到一个时间步骤之后才能得到。也就是说，δ t 是V ( S t ) 中的误差，在时间t + 1 时可用。另外要注意的是，如果数组V VV在事件中不发生变化（因为在蒙特卡洛方法中不发生变化），那么蒙特卡洛误差可以写成TD误差之和。

 如果V 在周期中被更新(就像TD(0)中那样)，那么这个标识就不准确，但是如果步长很小，那么它仍然可以保持大约不变。这种同一性的推广在时间差异学习的理论和算法中起着重要的作用。

例5.1 回家时间的估计

每天当你下班开车回家时，你会试着预测回家需要多长时间。当你离开你的办公室时，你会记下时间、星期几、天气以及其他任何可能相关的事情。假设在这个星期五，你正好在6点钟离开，你估计需要30分钟才能到家。当你到达你的车时，已经是6:05，你注意到开始下雨了。交通状况在雨中的速度往往比较慢，所以你重新估计从那时起需要35分钟，也就是总共40分钟。15分钟后，你按时完成了高速公路部分的行程。当你驶入一条二级公路时，你将你估计的总行程时间缩短到35分钟。不幸的是，此时你被一辆缓慢的卡车卡在后面，而且道路太窄，无法通过。最后你不得不跟着卡车走，直到6点40分转入你住的小街。三分钟后，你就到家了。因此，状态、时间和预测的顺序如下。

本例中的回报是每段旅程的经过时间。是不经过折扣的(γ = 1 )，因此每个状态的返回值为从该状态出发的实际时间。每个状态的值是预计的走时。第二列数字给出了当前遇到的每个状态的估计值。查看蒙特卡洛方法操作的一个简单方法是绘制预测的总时间（最后一列）在序列上，如图5.1（左）。红色箭头显示了恒定α-MC方法(5.1)推荐的预测变化，对于α = 1 。

图5.1 蒙特卡洛方法（左）和TD方法（右）在开车回家的例子中估值的变化。

这些恰恰是每个状态下的估计值（预测走时）与实际返回值（实际走时）之间的误差。例如，当你从高速公路出来时，你认为回家只需要多花15分钟，但事实上却花了23分钟。此时应用公式(5.1)，确定出高速路后估计的走的时间的增量。此时的误差，G t − V ( S t ) ，为8分钟。假设步长参数α αα为1/2。那么，由于这次经历，预测出高速路后的走车时间将向上修正4分钟。在这种情况下，这个变化可能太大，卡车很可能只是一个不走运经历。无论如何，这个变化只能在通常是离线的，也就是到家之后才能进行。只有在这个时候，你才知道任何的实际回报。

是否要等到知道最终结果后才能开始学习？假设在另一天，你在离开你的办公室时又估计到开车回家需要30分钟，但随后你又陷入了大规模的交通堵塞。离开办公室的25分钟后，你还在高速公路上碰碰运气。你现在估计还需要25分钟才能到家，总共需要50分钟。当你在路上等待时，你已经知道你最初估计的30分钟太乐观了。你一定要等到回家后再增加你对初始状态的估计吗？根据蒙特卡洛方法，你必须这样做，因为你还不知道真实的收益。

 另一方面，根据TD方法，你会立即知道，将你的初始估计从30分钟转向50分钟。事实上，每个估计都会向紧随其后的估计转移。回到我们第一天的驾驶，图5.1（右）显示了TD规则（5.2）所推荐的预测的变化（这些是规则所做的变化，如果α = 1）。每个误差都与预测随时间的变化成正比，即与预测的时间性不同成正比。

 除了让你在路上等待时有事情可做外，还有几个计算上的原因，为什么基于你当前的预测进行学习，而不是等到终止时才知道实际的回报是有利的。我们将在下一节简要讨论其中的一些原因。

5.2 TD预测方法的优势

TD方法在一定程度上根据其他估算数据更新估算。他们从估算中进行估算–他们是自举的。这是件好事吗？与蒙特卡洛和DP方法相比，TD方法有什么优势？发展和回答这样的问题将需要本书的其余部分和更多的时间。在本节中，我们简要地预测一些答案。

很明显，TD方法比DP方法有一个优势，因为它们不需要环境、回报和下一状态概率分布的模型。

与蒙特卡罗方法相比，TD方法的下一个最明显的优势是它们自然地以在线、完全增量的方式实现。使用蒙特卡洛方法，人们必须等到一个事件结束，因为只有到那时才知道回报，而使用TD方法，人们只需要等待一个时间步。这往往是一个关键的考虑因素。有些应用有非常长的事件，因此将所有学习延迟到事件结束太慢。另一些应用是持续的任务，根本没有事件。最后，一些蒙特卡洛方法必须忽略或打折采取实验行动的事件，这会大大减慢学习速度。TD方法对这些问题的敏感性要小得多，因为它们从每个过渡中学习，而不管后续行动是什么。

但是TD方法正确吗?当然，不用等待一个实际的结果，从一个猜测中学习下一个猜测是很方便的，但我们还能保证收敛到正确的答案吗?可喜的是，答案是肯定的。对于任何固定策略的定量策略，TD(0)被证明收敛于v π 的定量策略，如果它足够小，则其均值收敛于常数步长参数;如果步长参数按照通常的随机逼近条件减小，则其概率为1。大多数收敛证明只适用于上述(5.2)算法的基于表的情况，但也有一些适用于一般线性函数逼近的情况。

如果TD和蒙特卡洛方法都渐进地收敛到正确的预测，那么接下来的问题自然是 “哪种方法最先到达那里？” 换句话说，哪种方法学习得更快？哪种方法能更有效地利用有限的数据？目前，这是一个开放性的问题，因为没有人能够在数学上证明一种方法比另一种方法收敛得更快。事实上，我们甚至不清楚什么是最合适的形式化的方式来表达这个问题！然而，在实践中，TD方法的收敛速度比其他方法快。然而，在实践中，TD方法通常被发现在随机任务上比常数-α ααMC方法收敛得更快，如例5.2所示。

例5.2 随机移动

在本例中，我们实证地比较了TD(0)和常数-α \alphaα MC应用于以下马尔可夫奖励过程的预测能力:

马尔科夫奖励过程(Markov reward process)，或MRP，是一个没有行动的马尔科夫决策过程。我们在关注预测问题时，经常会用到MRP，在这个问题中，不需要区分由于环境造成的动态和由于智能体造成的动态。在这个MRP中，所有的事件都从中心状态C开始，然后在每一步上以相等的概率向左或向右前进一个状态。事件在极左或极右终止。当一个事件在右边终止时，会发生+1的奖励，其他奖励都是零。例如，一个典型的事件可能由以下状态和奖励序列组成。C , 0 , B , 0 , C , 0 , D , 0 , E , 1 。因为这个任务是不折现的, 每个状态的真实值是在右边终止的概率, 如果从这个状态开始。 因此，中心状态的真值为v π ( C ) = 0.5。所有状态A到E的真值为1/ 6  ,2/ 6  ,3/ 6  ,4/ 6 和5/ 6 。

 上面的左图显示了在TD(0)的单次运行中，经过不同次数事件后学习到的值。100次后的估计值与真实值非常接近–在步长参数不变的情况下（本例中α = 0.1 ），这些值会根据最近的结果而无限扩大。右图显示了两种方法在不同的α 值下的学习曲线，所显示的性能衡量标准是所学的价值函数和真实价值函数之间的均方根（RMS）误差，在五种状态中求平均值，然后在100次运行中求平均值。在所有情况下，对于所有的s，近似值函数都被初始化为中间值V ( s ) = 0.5 ，TD方法在这个任务上始终优于MC方法。

5.3 TD(0)最优性

假设只有一定量的经验，比如10个事件或100个时间步骤。在这种情况下，增量学习方法的一个常见方法是重复呈现经验，直到方法收敛到一个答案。给定一个近似的价值函数V，对于每一个访问非终结状态的时间步t tt，都会计算由（5.1）或（5.2）确定的增量，但价值函数只改变一次，即所有增量之和。然后用新的价值函数再次处理所有可用的经验，产生新的总体增量，以此类推，直到价值函数收敛。我们之所以称之为批更新，是因为只有在处理完每一批完整的训练数据后才会进行更新。 

在批量更新中，只要将α选择为足够小，TD(0)就确定性地收敛到单个答案，而与步长参数α αα无关。 在相同条件下，常数α αα-MC方法也可以确定地收敛，但是得出的答案是不同的。 了解这两个答案将有助于我们了解这两种方法之间的区别。 在正常更新下，这些方法不会一直移动到它们各自的批处理答案，但是从某种意义上说，它们会朝着这些方向采取步骤。 在尝试全面理解这两个答案之前，对于所有可能的任务，我们首先来看几个示例。

例5.3：批量更新下的随机行走

批量更新版本的TD(0)和常数-α MC被应用于随机行走预测例子(例5.2)，如下所示。在每一个新的事件之后，所有到目前为止看到的事件都被视为一个批次。它们被反复呈现给算法，无论是TD(0)还是常数-α MC，当α足够小时，值函数收敛。然后将得到的值函数与v π进行比较，并绘制出跨越五种状态的平均均方根误差(以及跨越整个实验的100次独立重复)，得到图5.2所示的学习曲线。注意，批量TD法始终优于批量蒙特卡洛法。

在批量训练下，常数-α αα MC收敛到的值V ( s ) V(s)V(s)是访问每个状态s ss后所经历的实际重新转折的样本平均数，这些是最佳估计值，因为它们最大限度地减少了来自训练集中实际收益的均方误差。在这个意义上，令人惊讶的是，根据右图所示的均方根误差测量，批式TD方法能够表现得更好。为什么批量TD能够比这个最优方法表现得更好呢？答案是蒙特卡洛方法只有在有限的情况下才是最优的，而且是在有限的情况下。即TD是最优的，与预测收益更相关。

图5.2：批量训练下TD(0)和常数-α MC在随机行走任务上的表现。

例5.4: You are the Predictor

现在把你自己放在一个未知马尔科夫回报过程的预测者的角色中。假设你观察了以下八个事件:

A, 0, B, 0                           B, 1
B, 1                                 B, 1
B, 1                                 B, 1
B, 1                                 B, 0

这意味着第1个情节从状态A开始，过渡到B，奖励为0，然后从B终止，奖励为0，其他7个情节更短，从B开始，立即终止。给出这批数据，你会说什么是最佳预测，估计值V ( A ) V(A)V(A)和V ( B ) V(B)V(B)的最佳值？大家可能都会同意，V ( B) 的最佳值是3 /4 ，因为在B状态的8次中，有6次过程立即终止，返回值为1，另外两次在B状态下，过程立即终止，返回值为0。

但是，给定这些数据的估计值V ( A ) 的最优值是多少呢？这里有两个合理的答案。一种是观察到该过程100%的时间都处于状态A，它立即遍历到B(奖励为0)；由于我们已经决定B的值为3 /4 ，因此A也必须有值3 /4 。观察这个答案的一种方式是，它是基于先对马尔科夫过程建模，在本例中如右图所示，然后计算给定模型的正确估计，在本例中确实给出了V ( A ) = 3 /4 。这也是批量TD(0)给出的答案。

另一个合理的答案是简单地观察到我们已经见过一次A，而后面的回报率是0，因此我们估计V ( A ) V(A)V(A)为0，这也是批量蒙特卡洛方法给出的答案。注意，这也是在训练数据上给出最小平方误差的答案。事实上，它在数据上给出了零误差。但我们还是希望第五个答案会更好。如果这个过程是马尔科夫过程，我们期望第五个答案在未来的数据上会产生更低的误差，即使蒙特卡洛答案在现有数据上更好。

5.4 Sarsa:策略 TD控制

现在我们来谈谈控制问题中TD预测方法的使用。像往常一样，我们遵循广义策略迭代(GPI)的模式，只是这次在评估或预测部分使用TD方法。与Monte Carlo方法一样，我们面临着平衡探索和利用的需要，同样方法也分为两大类：on-policy和off-policy。在本节中，我们介绍一种on-policy TD控制方法。

第一步是学习一个动作值函数而不是状态值函数。特别是，对于一个on-policy方法，我们必须估计当前行为策略π 和所有状态s 和动作a 的q π ( s ， a ) )。这可以使用上面描述的学习v π 的基本相同的TD方法来完成。回想一下，一个事件由状态和状态动作对的交替序列组成。

在上一节中，我们考虑了从状态到状态的转换，并学习了状态的值。现在我们考虑从状态-动作对到状态-动作对的转换，并学习状态-动作对的值。形式上这些情况是相同的：它们都是具有奖励过程的马尔科夫链。保证TD(0)下状态值收敛的定理也适用于相应的动作值算法。

如果S t + 1      是终端状态，那么Q ( S t + 1 , A t + 1 ))被定义为零。这个规则使用事件五元组的每一个元素，( S t , A t , R t + 1 , S t + 1 , A t + 1 ) ，这些元素构成了从一个状态动作对到下一个状态动作对的转换。这个五元组合定义了该算法的名称 “Sarsa” 。Sarsa的备份图如下图所示。

基于Sarsa预测法设计一个on-policy控制算法是很直接的。与所有的on-policy方法一样，我们不断估计行为策略π 的q π，同时改变策略π 相对于q π 的贪婪程度。Sarsa控制算法的一般形式在下面给出。Sarsa算法的收敛特性取决于策略对q qq的依赖性质，例如，可以使用ε -贪婪或ε-柔性策略。只要所有的状态-行动对被访问的次数是有限的，并且策略在极限范围内收敛到贪婪策略（例如，可以通过设置ε = 1 t 来安排使用ε εε-贪婪策略），Sarsa就会以概率1收敛到最优策略和行动值函数。

Sarsa (on-policy TD control) for estimating Q ≈ q ∗ 

例 5.5 Windy Gridworld

下面的插图是一个标准的网格世界，有起始状态和目标状态，但有一个不同：网格中间有一个向上的风。动作是标准的四种–上、下、右、左–但在中间区域，下一个状态会被 “风 “向上移动，风的强度因列而异。风的强度在每一列下面给出，以向上移动的单元格数为单位。举例来说，如果你在目标的右边一格，那么向左移动就会到目标上方的单元格。这是一个未折现的偶发任务，奖励为-1，直到达到目标状态。

上图显示了将ε-greedy Sarsa应用于这个任务的结果，ε = 0.1 ， α = 0.5 ε=0.1，α=0.5ε=0.1，α=0.5，所有s ， a s，as，a的初始值Q ( s ， a ) = 0 Q(s，a)=0Q(s，a)=0，图的斜率越来越大，说明随着时间的推移，目标的达成速度越来越快。

到了8000个时间步，贪婪的策略早已是最优的了（插图中显示了它的轨迹）；继续ε εε-贪婪的探索使平均事件长度保持在17步左右，比最小值15步多了两步。需要注意的是，蒙特卡洛方法在这里不能轻易使用，因为不能保证所有策略的终止。如果曾经发现一个策略导致智能体保持在相同的状态，那么下一个事件将永远不会结束。在线学习方法（如Sarsa）不会有这个问题，因为它们在事件中很快就会知道这样的策略很差，然后换成其他的策略。

5.5 Q-学习: Off-policy TD 控制

强化学习的早期突破之一是开发了一种非策略TD控制算法，称为 (Q-学习)Q-learning (Watkins, 1989),也被称为Sarsamax算法，定义为

在这种情况下，学习到的行动值函数Q直接逼近最优行动值函数q ∗  ，与所遵循的策略无关。这极大地简化了算法的分析，并实现了早期收敛证明。该策略仍然具有影响，因为它决定了哪些状态动作对被访问和更新。然而，正确收敛所需要的是所有的对继续更新。正如我们在之前中所观察到的那样，这是一个最小的要求，即任何保证在一般情况下发现最优行为的方法都必须要求它。在这一假设和步长参数序列的通常随机近似条件的变体下，Q已经被证明以概率1收敛到q ∗  。Q学习算法的程序形式如下所示。

Q-learning (off-policy TD control) for estimating π ≈ π ∗ 
 

Q-learning的备份图是什么？公式(5.8)更新一个状态动作对，所以顶层节点，也就是更新的根节点，一定是一个小的、填充的动作节点。更新也是从动作节点出发，在下一个状态中所有可能的动作上最大化。因此，备份图的底部节点应该是所有这些动作节点。最后，我们取这些 “下一个动作 “节点的最大值，用一条弧线穿过它们,见图(5.3)左。

例5.6: Cliff Walking

利用我们之前使用的悬崖寻路的例子,来比较Sarsa和Q-learning，突出了on-policy(Sarsa)和off-policy(Q-learning)方法之间的区别。

考虑右图所示的网格世界。这是一个标准的未计数的偶发任务，有开始和目标状态，以及通常的导致上、下、右、左运动的动作。奖励是-1，除了进入那些标有 “Cliff “的区域。进入这些区域会产生- 100的奖励，并让智能体立即回到起点。

上图显示了Sarsa和Q-学习方法在ε-greedy动作选择，ε = 0.1 ε=0.1ε=0.1的情况下的性能。在初始瞬态之后，Q-学习学习最优策略的值，即沿着悬崖的边缘右行。不幸的是，由于ε εε-greedy行动选择的原因，这重新导致其偶尔会掉落悬崖。另一方面，Sarsa将动作选择考虑在内，并学习通过网格上部的较长但较安全的路径。虽然Q-learning实际上学习了最优策略的值，但其在线性能比学习迂回策略的Sarsa差。当然，如果逐渐减小ε εε，那么两种方法都会渐渐收敛到最优策略。

5.6 期望Sarsa算法

考虑一下类似于Q-learning的学习算法，除了它使用了期望值，而不是下一个状态-动作对的最大值，考虑到每个动作在当前策略下的可能性。也就是说，考虑具有如下更新规则的算法

但这要遵循Q学习模式。 给定下一个状态S t + 1，此算法确定性地沿与期望Sarsa算法相同的方向移动，因此将其称为期望Sarsa算法(Expected Sarsa)。 其备份图如图5.4右侧所示。

图5.3：：Q-learning和预期Sarsa的备份图。

期望Sarsa算法在计算上比Sarsa算法更为复杂，但作为回报，由于A t + 1 的随机选择，它消除了方差。 如果有相同的经验，我们可能会期望它的性能比Sarsa好一些，并且确实如此。 图5.4显示了与Sarsa和Q学习相比，使用期望Sarsa算法进行的悬崖寻路实例的摘要结果。

图5.4:TD控制方法在崖上行走任务的过渡和渐近性能作为一个功能的。所有的算法都使用了一种贪婪策略，使算法的候选识别率= 0.1。渐近性能是超过100,000集的平均值，而中间性能是前100集的平均值。这些数据分别是中间和渐近情况下超过50,000次和10次运行的平均值。实心圆圈表示每种方法的最佳过渡性能。改编自van Seijen等人(2009)。

此外，在步长参数α的宽范围内，Expected Sarsa比Sarsa有明显的改进。 在悬崖寻路中，状态转换都是确定性的，所有的随机性都来自于策略，在这种情况下，Expected Sarsa可以安全地设置α = 1 α=1α=1，而不会出现任何渐进性能的下降,

而Sarsa只有在α的小值下才能长期表现良好，在这个值下短期性能很差。在这个例子和其他例子中，Expected Sarsa比Sarsa有一致的经验优势。

在这些悬崖寻路的结果中，期望Sarsa算法使用on-policy算法，但在一般情况下，它可能会使用一个与目标策略π ππ不同的策略来产生行为，在这种情况下，它就变成了一个off-policy算法。例如，假设π ππ是贪婪的策略，而行为更多是探索性的；那么Expected Sarsa正是Q-learning。在这个意义上，Expected Sarsa 归纳和概括了 Q-learning，同时可靠地改进了 Sarsa。除了少量的额外计算成本外，Expected Sarsa可能会完全主导其他两种比较著名的TD控制算法。

5.7 最大化偏差和双重学习

到目前为止，我们所讨论的所有控制算法在构建其目标策略时都涉及到最大化。例如，在Q-learning中，目标策略是给定当前动作值的贪婪策略，它用最大值来定义，而在Sarsa中，策略通常是ε -贪婪的，这也涉及到一个最大化操作。在这些算法中，对估计值的最大值被隐含地用作最大值的估计，这可能会导致一个明显的正偏差。为了了解原因，考虑一个单一的状态s ，其中有许多动作a ，它们的真值q ( s ， a ) 都是零，但它们的估计值Q ( s ， a ) 是不确定的，因此分布在一些高于零和一些低于零的地方。真值的最大值为零，但估计值的最大值为正，即为正偏。我们把这种最大化偏差称为最大化偏差。

例5.7: 最大化偏差实例

图5.5：Q-learning和双Q-learning在简单的偶发MDP上的比较（如插图所示）。Q-learning最初学习采取左边行动的频率比采取右边行动的频率高得多，并且总是比ε-greedy行动选择所强制执行的5%最小概率（ε=0.1）高出很多。相反，双Q学习基本上不受最大化偏差的影响。这些数据是10000次运行的平均值。最初的行动值估计为零。ε-greedy行动选择中的任何平局都被随机打破。

图5.5所示的小型MDP提供了一个简单的例子，说明最大化偏差如何损害TD控制算法的性能。MDP有两个非终端状态A和B，事件总是从A开始，在左和右两个动作之间进行选择。右边的动作立即过渡到终端状态，奖励和返回为零。左边的行动过渡到B，奖励也是零，从这里有许多可能的行动，所有这些行动都会导致立即终止，奖励从均值-0.1和方差1.0的正态分布中抽取。因此，任何以左为起点的轨迹的期望回报都是-0.1，因此在状态A中采取左总是一个错误。尽管如此，我们的控制方法可能会因为最大化偏差而偏向于左，使得B看起来有一个正值。

图5.5显示，Q-learning与ε -greedy动作选择最初学习到的是在这个例子上强烈偏向左的动作。即使在渐近状态下，Q-learning采取左侧动作的频率也比我们参数设置下的最优值（ε = 0.1 ， α = 0.1 ， γ = 1 ）多出约5%。

是否有避免最大化偏差的算法？首先，考虑一个老虎机的例子，在这个情况下，我们有许多行动中每个行动的价值的嘈杂估计，作为每个行动的所有游戏中收到的奖励的样本平均数获得。正如我们上面所讨论的那样，如果我们将估计值的最大值作为真实值的最大值的估计，就会有一个正的最大化偏差。一种看待这个问题的方法是，它是由于使用相同的样本（剧本）来确定最大化的动作和估计它的值。假设我们把游戏分成两组，用它们来学习两个独立的估计，称它们为Q 1 ( a ) 和Q 2 ( a ) ，每一个都是对真值q ( a ) q(a)q(a)的估计，对于所有a ∈ A.我们可以用一个估计，比如Q 1 ，来确定最大化动作A ∗ = arg max ⁡ a Q 1 ( a ) ，而另一个Q 2 ，则提供其价值的估计，Q 2 ( A ∗ ) = Q 2 ( arg max ⁡ a Q 1 ( a ) ) 。

这个估计值将是无偏的，即E [ Q 2 ( A ∗ ) ] = q ( A ∗ )。我们也可以重复这个过程，将两个估计的作用反过来，得到第二个无偏估计Q 1 ( arg max ⁡ a Q 2 ( a ) ) 。这就是双重学习的思想。需要注意的是，虽然我们学习了两个估计，但每次播放时只更新一个估计；双重学习使内存需求增加了一倍，但并没有增加每一步的计算量。

双重学习的思想很自然地扩展到全MDP的算法。例如，类似于Q-learning的双重学习算法，称为Double Q-learning，将时间步数一分为二，也许在每一步上都要抛出一枚硬币。如果硬币出现的是人头，更新就是

如果硬币出现的是反面，那么同样的更新，把Q 1 和Q 2 调换一下，这样Q 2 就更新了。这两个近似值函数完全对称处理。行为策略可以使用这两种行动值估计。例如，双Q学习的ε-greedy策略可以基于两个行动值估计的平均值（或总和）。

双Q学习的完整算法在下面的方框中给出。这是用于产生图5.5中结果的算法。在那个例子中，双学习似乎消除了最大化偏差带来的危害。当然还有双版本的Sarsa和Expected Sarsa。

Double Q-learning, for estimating Q1 ≈ Q2 ≈ q∗

5.8 游戏、后状态和其他特殊情况

在本书中，我们试图对一类广泛的任务提出统一的方法，但当然总有一些特殊的任务最好用专门的方法来处理。例如，我们的一般方法涉及学习一个动作值函数，它学习的东西更像一个状态值函数。如果我们仔细观察这个例子，就会发现，在那里学到的函数既不是动作值函数，也不是通常意义上的状态值函数。传统的状态值函数评估的是智能体可以选择行动的状态，但井字棋中使用的状态值函数评估的是智能体下棋后的棋盘位置。让我们把这些后状态以及在这些状态上的值函数称为后状态值函数。当我们知道环境动态的一个初始部分，但不一定知道全部动态时，后状态是有用的。例如，在棋局中，我们通常知道我们的棋步的直接影响结果。我们知道每一步可能的棋步的结果是什么，但不知道我们的对手将如何回复。后状态值函数是利用这种知识，从而产生一种更有效的学习方法的自然方法。

从井字游戏的例子可以看出，用后状态设计算法更有效的原因。传统的动作-价值函数会从位置和动作映射到价值的估计。但许多位置和移动对产生的结果位置是相同的，就像下面的例子。

在这种情况下，位置-动作对是不同的，但产生了相同的 “后状态”，因此必须具有相同的值。传统的动作值函数必须分别评估这两个对子，而后状态值函数则会立即平等地评估这两个对子。任何关于左边的位置-动作对的学习都会立即转移到右边的对子上。后状态出现在许多任务中，不仅仅是游戏。例如，在排队任务中，有一些动作，如将顾客分配给服务器，拒绝顾客，或丢弃信息。在这种情况下，这些动作实际上是以其直接的效果来定义的，这些效果是完全已知的。

 我们不可能描述所有可能的专门问题和相关的专门学习算法的种类。但是，本书所发展的原则应该是广泛适用的。例如，后状态方法仍然可以用广义的策略迭代来恰当地描述，策略和（后状态）值函数的交互方式基本相同。在许多情况下，人们仍然会面临在on-policy和off-policy方法之间的选择，以管理持久探索的需要。

5.9 实例:悬崖寻路

本节继续使用在马尔可夫决策中使用过的例子,悬崖寻路实例.该实例的介绍可以参照本节例5.6.

5.9.1 Part 1: TD Control: Sarsa首先我们使用Sarsa算法来运行这个实例.

Sarsa (on-policy TD control) for estimating Q ≈ q ∗ 

import sys
import gym
import numpy as np
import random
import math
from collections import defaultdict, deque
import matplotlib.pyplot as plt

from plot_utils_TD import plot_values


# Part 1: TD Control: Sarsa
def update_Q_sarsa(alpha, gamma, Q, state, action, reward, next_state=None, next_action=None):
    """ Return updated Q-value for the most recent experience. """
    current = Q[state][action]  # estimate in Q-table (for current state, action pair)
    # 得到下一个时间步的状态-动作对的值
    Qsa_next = Q[next_state][next_action] if next_state is not None else 0
    target = reward + (gamma * Qsa_next)  # construct TD target
    new_value = current + (alpha * (target - current))
    return new_value


def epsilon_greedy(Q, state, nA, eps):
    """
    为提供的状态选择epsilon-贪婪动作
    :param Q: (dictionary)动作价值函数
    :param state: (int)当前状态
    :param nA: (int)环境中的动作数
    :param eps: epsilon
    """
    if random.random() > eps:  # 选择概率为epsilon的贪婪动作
        return np.argmax(Q[state])
    else:
        return random.choice(np.arange(env.action_space.n))


def sarsa(env, num_episodes, alpha, gamma=1.0, plot_every=100):
    nA = env.action_space.n  # 动作的数量
    Q = defaultdict(lambda: np.zeros(nA))  # 初始化数组的空字典

    # 性能监控
    tmp_scores = deque(maxlen=plot_every)
    avg_scores = deque(maxlen=num_episodes)
    for i_episode in range(1, num_episodes+1):
        # 过程跟踪
        if i_episode % 100 == 0:
            print("\rEpisode {}/{}".format(i_episode, num_episodes), end="")
            sys.stdout.flush()
        score = 0  # 初始化分数
        state = env.reset()  # 开始一个事件

        eps = 1.0 / i_episode   # set value of epsilon
        action = epsilon_greedy(Q, state, nA, eps)   # epsilon-greedy action selection

        while True:
            next_state, reward, done, info = env.step(action)   # take action A, observe R, S'
            score += reward  # 给智能体的分数中添加奖励
            if not done:
                next_action = epsilon_greedy(Q, next_state, nA, eps)   # epsilon-greedy action
                Q[state][action] = update_Q_sarsa(alpha, gamma, Q, state, action, reward, next_state, next_action)

                state = next_state  # S <- S'
                action = next_action  # A <- A'

            if done:
                Q[state][action] = update_Q_sarsa(alpha, gamma, Q, state, action, reward)
                tmp_scores.append(score)  # append score
                break
        if (i_episode % plot_every == 0):
            avg_scores.append(np.mean(tmp_scores))

    # plot performance
    plt.plot(np.linspace(0, num_episodes, len(avg_scores), endpoint=False), np.asarray(avg_scores))
    plt.xlabel('Episode Number')
    plt.ylabel('Average Reward (Over Next %d Episodes)' % plot_every)
    plt.show()
    # print best 100-episode performance
    print(('\nBest Average Reward over %d Episodes: ' % plot_every), np.max(avg_scores))
    return Q


if __name__ == "__main__":
    env = gym.make('CliffWalking-v0')

    print(env.action_space)
    print(env.observation_space)

    '''Part 1: TD Control: Sarsa'''
    # 得到估计的最优策略和相应的行动-价值函数
    Q_sarsa = sarsa(env, 20000, .01)

    # 输出估计的最优策略
    policy_sarsa = np.array([np.argmax(Q_sarsa[key]) if key in Q_sarsa else -1 for key in np.arange(48)]).reshape(4, 12)
    print("\nEstimated Optimal Policy (UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, N/A = -1):")
    print(policy_sarsa)

    # 绘制估计的最优状态价值函数
    V_sarsa = ([np.max(Q_sarsa[key]) if key in Q_sarsa else 0 for key in np.arange(48)])
    plot_values(V_sarsa)

估计的最优策略:

Estimated Optimal Policy (UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, N/A = -1):
[[ 1  1  1  1  1  1  1  1  1  1  1  2]
 [ 1  0  1  1  1  1  1  2  1  1  2  2]
 [ 1  1  1  1  1  1  1  1  1  1  1  2]
 [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]]

平均回报:

 估计的最优状态价值函数:

5.9.2 Part2: TD Control: Q-learning

def update_Q_sarsamax(alpha, gamma, Q, state, action, reward, next_state=None):
    """ Return updated Q-value for the most recent experience """
    current = Q[state][action]  # estimate in Q-table (for current state, action pair)
    Qsa_next = np.max(Q[next_state]) if next_state is not None else 0  # value of next state
    target = reward + (gamma * Qsa_next)  # construct TD target
    new_value = current + (alpha * (target - current))  # get updated value
    return new_value


def q_learning(env, num_episodes, alpha, gamma=1.0, plot_every=100):
    """
    Q-Learning - TD Control
    :param num_episodes: (int) number of episodes to run the algorithm
    :param alpha: (float)learning rate
    :param gamma: (float)discount factor
    :param plot_every: (int) number of episode to use when calculating average score
    """
    nA = env.action_space.n  # number of actions
    Q = defaultdict(lambda: np.zeros(nA))  # initialize empty dictionary of arrays

    # monitor performance
    tmp_scores = deque(maxlen=plot_every)  # deque for keeping track of scores
    avg_scores = deque(maxlen=num_episodes)  # average score every plot_every episodes

    for i_episode in range(1, num_episodes+1):
        # monitor process
        if i_episode % 100 == 0:
            print("\rEpisode {}/{}".format(i_episode, num_episodes), end='')
            sys.stdout.flush()
        score = 0
        state = env.reset()
        eps = 1.0 / i_episode

        while True:
            action = epsilon_greedy(Q, state, nA, eps)
            next_state, reward, done, info = env.step(action)
            score += reward
            Q[state][action] = update_Q_sarsamax(alpha, gamma, Q, state, action, reward, next_state)

            state = next_state
            if done:
                tmp_scores.append(score)
                break
        if (i_episode % plot_every == 0):
            avg_scores.append(np.mean(tmp_scores))

    # plot performance
    plt.plot(np.linspace(0,num_episodes,len(avg_scores),endpoint=False), np.asarray(avg_scores))
    plt.xlabel('Episode Number')
    plt.ylabel('Average Reward (Over Next %d Episodes)' % plot_every)
    plt.show()
    # print best 100-episode performance
    print(('Best Average Reward over %d Episodes: ' % plot_every), np.max(avg_scores))
    return Q

if __name__ == "__main__":
    env = gym.make('CliffWalking-v0')

    '''Part 2: TD Control: Q-learning'''
    # obtain the estimated optimal policy and corresponding action-value function
    Q_sarsamax = q_learning(env, 5000, .01)

    # print the estimated optimal policy
    policy_sarsamax = np.array(
        [np.argmax(Q_sarsamax[key]) if key in Q_sarsamax else -1 for key in np.arange(48)]).reshape((4, 12))

    print("\nEstimated Optimal Policy (UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, N/A = -1):")
    print(policy_sarsamax)

    # plot the estimated optimal state-value function
    plot_values([np.max(Q_sarsamax[key]) if key in Q_sarsamax else 0 for key in np.arange(48)])

估计的最优策略:

Estimated Optimal Policy (UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, N/A = -1):
[[ 0  1  0  1  2  0  1  1  1  1  2  3]
 [ 1  1  1  1  0  1  2  2  3  2  1  2]
 [ 1  1  1  1  1  1  1  1  1  1  1  2]
 [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  0]]
Episode 5000/5000Best Average Reward over 100 Episodes:  -13.02

平均回报:

估计的最优状态价值函数:

5.9.3 Part 3: TD Control: Expected Sarsa

根据公式(5.9)

# Part 3: TD Control: Expected Sarsa
def update_Q_expsarsa(alpha, gamma, nA, eps, Q, state, action, reward, next_state=None):
    """Returns updated Q-value for the most recent experience."""
    current = Q[state][action]         # estimate in Q-table (for current state, action pair)
    policy_s = np.ones(nA) * eps / nA  # current policy (for next state S')
    policy_s[np.argmax(Q[next_state])] = 1 - eps + (eps / nA) # greedy action
    Qsa_next = np.dot(Q[next_state], policy_s)          # get value of state at next time step
    target = reward + (gamma * Qsa_next)                # construct target
    new_value = current + (alpha * (target - current))  # get updated value
    return new_value


def expected_sarsa(env, num_episodes, alpha, gamma=1.0, plot_every=100):
    """Expected SARSA - TD Control

    Params
    ======
        num_episodes (int): number of episodes to run the algorithm
        alpha (float): step-size parameters for the update step
        gamma (float): discount factor
        plot_every (int): number of episodes to use when calculating average score
    """
    nA = env.action_space.n  # number of actions
    Q = defaultdict(lambda: np.zeros(nA))  # initialize empty dictionary of arrays

    # monitor performance
    tmp_scores = deque(maxlen=plot_every)  # deque for keeping track of scores
    avg_scores = deque(maxlen=num_episodes)  # average scores over every plot_every episodes

    for i_episode in range(1, num_episodes + 1):
        # monitor progress
        if i_episode % 100 == 0:
            print("\rEpisode {}/{}".format(i_episode, num_episodes), end="")
            sys.stdout.flush()

        score = 0  # initialize score
        state = env.reset()  # start episode
        eps = 0.005  # set value of epsilon

        while True:
            action = epsilon_greedy(Q, state, nA, eps)  # epsilon-greedy action selection
            next_state, reward, done, info = env.step(action)  # take action A, observe R, S'
            score += reward  # add reward to agent's score
            # update Q
            Q[state][action] = update_Q_expsarsa(alpha, gamma, nA, eps, Q, state, action, reward, next_state)
            state = next_state  # S <- S'
            if done:
                tmp_scores.append(score)  # append score
                break
        if (i_episode % plot_every == 0):
            avg_scores.append(np.mean(tmp_scores))

    # plot performance
    plt.plot(np.linspace(0, num_episodes, len(avg_scores), endpoint=False), np.asarray(avg_scores))
    plt.xlabel('Episode Number')
    plt.ylabel('Average Reward (Over Next %d Episodes)' % plot_every)
    plt.show()
    # print best 100-episode performance
    print(('Best Average Reward over %d Episodes: ' % plot_every), np.max(avg_scores))
    return Q

if __name__ == "__main__":
    env = gym.make('CliffWalking-v0')

    '''Part 3: TD Control: Expected Sarsa'''
    # obtain the estimated optimal policy and corresponding action-value function
    Q_expsarsa = expected_sarsa(env, 5000, 1)

    # print the estimated optimal policy
    policy_expsarsa = np.array(
        [np.argmax(Q_expsarsa[key]) if key in Q_expsarsa else -1 for key in np.arange(48)]).reshape(4, 12)
    print("\nEstimated Optimal Policy (UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, N/A = -1):")
    print(policy_expsarsa)

    # plot the estimated optimal state-value function
    plot_values([np.max(Q_expsarsa[key]) if key in Q_expsarsa else 0 for key in np.arange(48)])

估计的最优策略:

Estimated Optimal Policy (UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, N/A = -1):
[[ 0  1  1  2  0  1  1  2  1  2  1  2]
 [ 1  1  1  1  1  1  1  1  1  1  1  2]
 [ 1  1  1  1  1  1  1  1  1  1  1  2]
 [ 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  0]]

平均回报:

估计的最优状态价值函数:

5.9.4 完整程序

程序整合如下,较以上代码更新了部分注释.

import sys
import gym
import numpy as np
import random
import math
from collections import defaultdict, deque
import matplotlib.pyplot as plt

from plot_utils_TD import plot_values


# Part 1: TD Control: Sarsa
def update_Q_sarsa(alpha, gamma, Q, state, action, reward, next_state=None, next_action=None):
    """
    返回根据当前位置的最新的Q表值
    :param alpha: 学习率
    :param gamma: 折扣率
    :param Q: Q表
    :param state: 当前状态
    :param action: 当前动作
    :param reward: 回报
    :param next_state: 下个时间步的状态
    :param next_action: 下个时间步的动作
    :return: 新的Q值
    """
    current = Q[state][action]  # 在Q表中的预测 (对于当前的状态-动作对)
    # 得到下一个时间步的状态-动作对的值
    # 详情参考公式(5.7)
    Qsa_next = Q[next_state][next_action] if next_state is not None else 0
    target = reward + (gamma * Qsa_next)  # 构建TD目标
    new_value = current + (alpha * (target - current))
    return new_value


def epsilon_greedy(Q, state, nA, eps):
    """
    为提供的状态选择epsilon-贪婪动作
    :param Q: (dictionary)动作价值函数
    :param state: (int)当前状态
    :param nA: (int)环境中的动作数
    :param eps: epsilon
    """
    if random.random() > eps:  # 选择概率为epsilon的贪婪动作
        return np.argmax(Q[state])
    else:
        return random.choice(np.arange(env.action_space.n))


def sarsa(env, num_episodes, alpha, gamma=1.0, plot_every=100):
    nA = env.action_space.n  # 动作的数量
    Q = defaultdict(lambda: np.zeros(nA))  # 初始化数组的空字典

    # 性能监控
    tmp_scores = deque(maxlen=plot_every)  # 建立关于分数双向队列对象
    avg_scores = deque(maxlen=num_episodes)  # 建立平均分数的双向队列对象
    for i_episode in range(1, num_episodes+1):
        # 过程跟踪
        if i_episode % 100 == 0:
            print("\rEpisode {}/{}".format(i_episode, num_episodes), end="")
            sys.stdout.flush()
        score = 0  # 初始化分数
        state = env.reset()  # 开始一个事件

        eps = 1.0 / i_episode   # 设置epsilon的值
        action = epsilon_greedy(Q, state, nA, eps)   # 采取 epsilon-贪婪动作

        while True:
            next_state, reward, done, info = env.step(action)   # take action A, observe R, S'
            score += reward  # 给智能体的分数中添加奖励
            if not done:
                next_action = epsilon_greedy(Q, next_state, nA, eps)   # 采取 epsilon-贪婪 动作
                Q[state][action] = update_Q_sarsa(alpha, gamma, Q,
                                                  state, action, reward, next_state, next_action)  # 更新Q表

                state = next_state  # S <- S'
                action = next_action  # A <- A'

            if done:
                Q[state][action] = update_Q_sarsa(alpha, gamma, Q, state, action, reward)
                tmp_scores.append(score)  # 添加分数
                break
        # 更新平均分数
        if (i_episode % plot_every == 0):
            avg_scores.append(np.mean(tmp_scores))

    # plot performance
    plt.plot(np.linspace(0, num_episodes, len(avg_scores), endpoint=False), np.asarray(avg_scores))
    plt.xlabel('Episode Number')
    plt.ylabel('Average Reward (Over Next %d Episodes)' % plot_every)
    plt.show()
    # print best 100-episode performance
    print(('\nBest Average Reward over %d Episodes: ' % plot_every), np.max(avg_scores))
    return Q


# Part2: TD Control: Q-学习
def update_Q_sarsamax(alpha, gamma, Q, state, action, reward, next_state=None):
    """ Return updated Q-value for the most recent experience """
    current = Q[state][action]  # estimate in Q-table (for current state, action pair)
    Qsa_next = np.max(Q[next_state]) if next_state is not None else 0  # 选择最大状态价值
    target = reward + (gamma * Qsa_next)  # 构建 TD 目标
    new_value = current + (alpha * (target - current))  # get updated value
    return new_value


def q_learning(env, num_episodes, alpha, gamma=1.0, plot_every=100):
    """
    Q-Learning - TD Control
    :param num_episodes: (int) number of episodes to run the algorithm
    :param alpha: (float)学习率
    :param gamma: (float)折扣率
    :param plot_every: (int) 在计算平均分数时使用的集数
    """
    nA = env.action_space.n  # 动作数
    Q = defaultdict(lambda: np.zeros(nA))  # 初始化数组的空字典

    # monitor performance
    tmp_scores = deque(maxlen=plot_every)  # 记录分数的deque
    avg_scores = deque(maxlen=num_episodes)  # 每固定集的平均得分

    for i_episode in range(1, num_episodes+1):
        # monitor process
        if i_episode % 100 == 0:
            print("\rEpisode {}/{}".format(i_episode, num_episodes), end='')
            sys.stdout.flush()
        score = 0
        state = env.reset()
        eps = 1.0 / i_episode

        while True:
            action = epsilon_greedy(Q, state, nA, eps)
            next_state, reward, done, info = env.step(action)
            score += reward
            Q[state][action] = update_Q_sarsamax(alpha, gamma, Q, state, action, reward, next_state)

            state = next_state
            if done:
                tmp_scores.append(score)
                break
        if (i_episode % plot_every == 0):
            avg_scores.append(np.mean(tmp_scores))

    # plot performance
    plt.plot(np.linspace(0,num_episodes,len(avg_scores),endpoint=False), np.asarray(avg_scores))
    plt.xlabel('Episode Number')
    plt.ylabel('Average Reward (Over Next %d Episodes)' % plot_every)
    plt.show()
    # print best 100-episode performance
    print(('Best Average Reward over %d Episodes: ' % plot_every), np.max(avg_scores))
    return Q


# Part 3: TD Control: Expected Sarsa
def update_Q_expsarsa(alpha, gamma, nA, eps, Q, state, action, reward, next_state=None):
    """
    返回根据当前位置的最新的Q表值
    :param alpha: 学习率
    :param gamma: 折扣率
    :param nA: 动作数
    :param eps: epsilon
    :param Q: Q表
    :param state: 当前状态
    :param action: 当前动作
    :param reward: 回报
    :param next_state:下个状态
    """
    current = Q[state][action]         # estimate in Q-table (for current state, action pair)

    policy_s = np.ones(nA) * eps / nA  # 当前的政策(for next state S')
    policy_s[np.argmax(Q[next_state])] = 1 - eps + (eps / nA)  # 贪婪动作
    Qsa_next = np.dot(Q[next_state], policy_s)          # 获取下一时刻状态的值

    target = reward + (gamma * Qsa_next)                # 目标构建
    new_value = current + (alpha * (target - current))  # 获得更新后的值
    return new_value


def expected_sarsa(env, num_episodes, alpha, gamma=1.0, plot_every=100):
    """Expected SARSA - TD Control

    Params
    ======
        num_episodes (int): number of episodes to run the algorithm
        alpha (float): step-size parameters for the update step
        gamma (float): discount factor
        plot_every (int): number of episodes to use when calculating average score
    """
    nA = env.action_space.n  # number of actions
    Q = defaultdict(lambda: np.zeros(nA))  # initialize empty dictionary of arrays

    # monitor performance
    tmp_scores = deque(maxlen=plot_every)  # deque for keeping track of scores
    avg_scores = deque(maxlen=num_episodes)  # average scores over every plot_every episodes

    for i_episode in range(1, num_episodes + 1):
        # monitor progress
        if i_episode % 100 == 0:
            print("\rEpisode {}/{}".format(i_episode, num_episodes), end="")
            sys.stdout.flush()

        score = 0  # initialize score
        state = env.reset()  # start episode
        eps = 0.005  # set value of epsilon

        while True:
            action = epsilon_greedy(Q, state, nA, eps)  # epsilon-greedy action selection
            next_state, reward, done, info = env.step(action)  # take action A, observe R, S'
            score += reward  # add reward to agent's score
            # update Q
            Q[state][action] = update_Q_expsarsa(alpha, gamma, nA, eps, Q, state, action, reward, next_state)
            state = next_state  # S <- S'
            if done:
                tmp_scores.append(score)  # append score
                break
        if (i_episode % plot_every == 0):
            avg_scores.append(np.mean(tmp_scores))

    # plot performance
    plt.plot(np.linspace(0, num_episodes, len(avg_scores), endpoint=False), np.asarray(avg_scores))
    plt.xlabel('Episode Number')
    plt.ylabel('Average Reward (Over Next %d Episodes)' % plot_every)
    plt.show()
    # print best 100-episode performance
    print(('Best Average Reward over %d Episodes: ' % plot_every), np.max(avg_scores))
    return Q


if __name__ == "__main__":
    env = gym.make('CliffWalking-v0')

    print("Action space:{}".format(env.action_space.n))
    print("Observation space : {}".format(env.observation_space.n))

    '''Part 1: TD Control: Sarsa'''
    # 得到估计的最优策略和相应的行动-价值函数
    Q_sarsa = sarsa(env, 5000, .01)
    print(Q_sarsa.items())

    # 输出估计的最优策略
    policy_sarsa = np.array([np.argmax(Q_sarsa[key]) if key in Q_sarsa else -1 for key in np.arange(48)]).reshape(4, 12)
    print("\nEstimated Optimal Policy (UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3, N/A = -1):")
    print(policy_sarsa)

    # 绘制估计的最优状态价值函数
    V_sarsa = ([np.max(Q_sarsa[key]) if key in Q_sarsa else 0 for key in np.arange(48)])
    plot_values(V_sarsa)

    '''Part 2: TD Control: Q-learning'''
    # obtain the estimated optimal policy and corresponding action-value function
    Q_sarsamax = q_learning(env, 5000, .01)

    # print the estimated optimal policy
    policy_sarsamax = np.array(
        [np.argmax(Q_sarsamax[key]) if key in Q_sarsam