type
status
password
date
slug
summary
category
URL
tags
icon
在本章中，我们开始介绍不依赖系统模型的无模型强化学习算法。没有模型的情况下，就必须有一些数据；如果我们没有数据，就必须有一个模型。如果两者都没有，那么我们就无法找到最优策略。
预备知识
强化学习中的“数据”通常指的是智能体与环境的交互经验。
策略迭代算法
策略迭代也是一种迭代算法。每次迭代有两个步骤。
- 策略评估步骤（policy evaluation ）。通过计算相应的状态价值来评估给定的策略。也就是求解以下贝尔曼方程：
- 策略评估
- 解析解：
- 迭代算法：。其中表示的第次估计值。从任意初始猜测开始，可以确保当时，。具体细节可在第 2.7 节中找到。
我们在第二章中介绍了两种求解（4.3）中贝尔曼方程的方法。
- 策略改进步骤（policy improvement）。这一步用于改进策略。具体来说，一旦在第一步中计算出，就可以得到一个新的策略，如下所示：
具体来说，策略改进步骤分为以下2步
根据策略评估结果，计算动作价值：
根据动作价值，根据策略：
大数定律
对于一个随机变量，假设是一些独立同分布的样本。令为样本的平均值。那么，
以上两个等式表明是的无偏估计，并且随着增大到无穷大，它的方差减小到零。
证明
- 首先，，这里的最后一个等式是因为样本是同分布的（即）。
- 其次，，这里的第二个等式是因为样本是独立的，第三个等式是由于样本是同分布的（即）。
MC 基础算法
本节介绍第一个也是最简单的基于蒙特卡洛的强化学习算法。这个算法是通过将 4.2 节中介绍的策略迭代算法中的基于模型的策略评估步骤替换为无模型的蒙特卡洛估计步骤而得到的。
将策略迭代转换为无模型形式
在策略迭代算法的每次迭代中都有两个步骤（见 4.2 节）。第一步是策略评估，旨在通过求解来计算。第二步是策略改进，旨在计算贪婪策略。策略改进步骤的元素形式为：
必须指出的是，动作价值处于这两个步骤的核心位置。具体来说，在第一步中，计算状态价值是为了计算动作价值。在第二步中，基于计算出的动作价值生成新的策略。让我们重新考虑一下如何计算动作价值。有两种方法可用。
基于模型计算
第一种是基于模型的方法。这是策略迭代算法所采用的方法。具体来说，我们可以首先通过求解贝尔曼方程来计算状态价值。然后，我们可以通过使用来计算动作价值。
这种方法要求系统模型是已知的。
无模型计算动作价值
回想一下动作价值的定义。
它是从状态动作对开始时获得的期望回报。由于是一个期望，可以根据大数定理，通过蒙特卡洛方法进行估计。为此，从状态动作对开始，智能体可以遵循策略与环境进行交互，然后获得一定数量的episodes。假设存在个episodes，并且第个episodes的return是。那么，可以近似为
我们已经知道，如果episodes的数量足够大，根据大数定律，这个近似值将足够准确。
蒙特卡洛基本算法
现在我们准备介绍第一个基于蒙特卡洛的强化学习算法。从初始策略开始，该算法在第次迭代（）中有两个步骤。
初始化：初始。 目标：寻找最优策略。 对于第次迭代（），执行以下操作： 对于每个状态，执行以下操作： 对于每个动作，执行以下操作： 从开始，通过遵循收集足够多的episodes。策略评估：从开始的所有episodes的平均return。 策略改进：。 如果，否则。
MC Basic 算法与策略迭代算法非常相似。唯一的区别在于，它直接从经验样本中计算动作价值，而策略迭代则首先计算状态价值，然后基于系统模型计算动作价值。需要注意的是，无模型算法直接估计动作价值。否则，如果它估计的是状态价值，我们仍然需要使用系统模型从这些状态价值中计算动作价值。
由于策略迭代是收敛的，所以在有足够样本的情况下，MC Basic 也是收敛的。也就是说，对于每个，假设从开始有足够多的episodes。那么，这些episodes的return的平均值可以准确地近似的动作价值。在实际中，我们通常不会对每个都有足够多的episodes。因此，动作价值的近似可能不准确。然而，该算法通常仍然可以工作。这与Truncated policy iteration算法类似，在该算法中，动作价值也没有被准确计算。
最后，由于 MC Basic 的样本效率低，它过于简单而不具实用性。我们介绍这个算法的原因是让读者掌握基于蒙特卡洛的强化学习的核心思想。在学习本章后面介绍的更复杂的算法之前，很好地理解这个算法是很重要的。我们将会看到，通过优化 MC Basic 算法，可以很容易地得到更复杂且样本效率更高的算法。
示例
接下来我们用一个例子来展示 MC Basic 算法的实现细节。奖励设置为且。折扣率是。初始策略如图 5.3 所示。这个初始策略在状态或时不是最优的。
虽然应该计算所有的动作价值，但由于篇幅限制，我们仅给出状态 的那些动作价值。在状态 ，有五种可能的动作。对于每个动作，我们需要收集许多足够长的episodes，以便有效地近似动作价值。然而，由于这个例子在策略和模型方面都是确定性的，多次运行将产生相同的轨迹。因此，每个动作价值的估计仅需要一个episodes。
- 根据策略开始得到以下episodes。
- 从开始，episodes为。动作价值等于该episodes的折扣return。
- 从开始，episodes为。动作价值等于该episodes的折扣return。
- 从开始，episodes为。动作价值等于该episodes的折扣return。
- 从开始，episodes为 。动作价值等于该episodes的折扣return。
- 从开始，episodes为。动作价值等于该episodes的折扣return。
通过比较这五个动作值，我们可以看出
很直观的是，在状态 时选择 或 的改进策略是最优的。因此，对于这个简单的例子，我们仅通过一次迭代就可以成功地得到一个最优策略。在这个简单的例子中，初始策略对于除 和 之外的所有状态已经是最优的。因此，仅经过一次迭代，该策略就可以变为最优。当策略对于其他状态不是最优时，就需要更多的迭代。
MC Exploring Starts
接下来，我们优化蒙特卡洛基本算法以获得另一种基于蒙特卡洛的强化学习算法，该算法稍微复杂一些，但样本效率更高。
更有效地利用样本
基于蒙特卡洛的强化学习的一个难点是如何更有效地利用样本。具体来说，假设我们有一个通过遵循策略获得的样本序列：
每次一个状态-动作对出现在一个序列中时，就称其为该状态-动作对的一次visit。可以采用不同的策略来利用这些visit。
第一种也是最简单的策略是使用initial-visit。也就是说，使用整个episode来估计初始状态-动作对的动作价值。对于（5.3）中的例子，initial-visit策略仅估计（）的动作价值。蒙特卡洛基本算法采用initial-visit策略。然而，这种策略的样本利用率很低，因为该序列还访问了许多其他状态-动作对，例如（）、（）和（）。这些访问也可以用于估计相应的动作价值。特别是，我们可以将（5.3）中的序列分解为多个子序列：
在一个状态-动作对被visit后生成的轨迹可以被视为一个新的episode。这些新的episodes可以用于估计更多的动作价值。通过这种方式，episode中的状态-动作对可以被更有效地利用。
此外，一个状态-动作对在一个episode中可能被多次visit。例如，在（5.3）的episode中，（）被visit了两次。如果我们只计算第一次visit，这被称为first-visit strategy。如果我们计算一个状态-动作对的每次visit，这样的策略被称为 every-visit [20]。
就样本使用效率而言， every-visit是最好的。如果一个episode足够长，以至于它可以多次访问所有的状态-动作对，那么这个单一的episode可能足以使用every-visit来估计所有的动作价值。然而，通过every-visit获得的样本是相关的，因为从second visit开始的轨迹仅仅是从first visit开始的轨迹的一个子集。不过，如果两次visit在轨迹中相距较远，那么这种相关性就不会很强。
更有效地更新策略
基于蒙特卡洛的强化学习的另一个难点是何时更新策略。有两种策略可用。
- 第一种策略是，在策略评估步骤中，收集从相同状态-动作对开始的所有episodes，然后使用这些episodes的平均return来近似动作价值。蒙特卡洛基本算法采用了这种策略。这种策略的缺点是智能体必须等到所有episodes都被收集完后才能更新估计值。
- 第二种策略可以克服这一缺点。它使用单个episode的return来近似相应的动作价值。这样，当我们收到一个episode时，我们可以立即获得一个粗略的估计。然后，可以逐个episodes地改进策略。
由于单个episode的return不能准确地逼近相应的动作价值，你可能会想知道第二种策略是否良好。事实上，这种策略属于上一章介绍的广义策略迭代的范畴。也就是说，即使价值估计不够准确，我们仍然可以更新策略。
Exploring starts
只有当每个状态-动作对都得到充分探索时，我们才能准确地估计它们的动作价值（根据大数定律），从而成功找到最优策略。否则，如果一个动作没有得到充分探索，其动作价值可能会被不准确地估计，并且即使这个动作确实是最佳动作，策略也可能不会选择它。
因此为了探索每个状态-动作对，我们从每个状态-动作对开始生成无限数量（或足够多）的episodes。（因为episode中间的状态-动作对，不受控制；所以我们只能通过控制episode起点，从而保证每个状态-动作对都出现）
MC Basic算法和MC Exploring Starts都需要这个条件。然而，在许多应用中，这个条件很难满足，特别是那些涉及与环境进行物理交互的应用。我们能去除探索起点的要求吗？答案是肯定的，如下一节所示。
算法描述
我们可以使用 5.3.1 节和 5.3.2 节中介绍的技术来提高 MC 基本算法的效率。然后，可以得到一个名为 MC Exploring Starts的新算法。
MC Exploring Starts的细节在算法 5.2 中给出。该算法使用every-visit策略。有趣的是，在计算从每个状态-动作对开始获得的折扣回报时，该过程从结束状态开始并回溯到起始状态。这样的技术可以使计算动作价值更高效，但也使算法更加复杂。
MC -Greedy: Learning without exploring starts
接下来，我们通过去除探索起点条件来优化 MC Exploring Starts算法。这个条件实际上要求每个状态-动作对都能被充分多次访问，这也可以基于软策略来实现。
Exploring Starts条件：从不同的状态-动作对开始生成大量episodes，从而准确估计每个状态-动作对的
-greedy policies
如果一个策略在任何状态下采取任何动作都有正概率，那么这个策略就是软策略。考虑一个极端情况，即我们只有一个episode。在软策略下，一个足够长的单个episode可以多次访问每个状态-动作对（见图 5.8 中的例子）。因此，我们不需要从不同的状态-动作对开始生成大量episodes，这样就可以去除探索起点的要求。
一种常见的软策略类型是 -贪婪策略。-贪婪策略是一种随机策略，它有更高的概率选择贪婪动作，并且对采取任何其他动作都有相同的非零概率。这里，贪婪动作是指具有最大动作价值的动作。特别地，假设 。相应的 -贪婪策略具有以下形式：
其中表示与状态 相关联的动作数量。
贪心策略提供了一种平衡探索与最优性的方法。如果我们想要最优性，我们需要降低的值。然而，如果我们想要增强探索，我们需要增加的值。当 时，-贪婪策略变为贪婪策略。当 = 1 时，采取任何动作的概率等于。
采取贪婪动作的概率总是大于采取任何其他动作的概率，因为
虽然-贪婪策略是随机的，但我们如何按照这样的策略选择一个动作呢？我们可以首先按照均匀分布生成一个在区间内的随机数。如果，那么我们选择贪婪动作。如果，那么我们以的概率在中随机选择一个动作（我们可能再次选择贪婪动作）。这样，选择贪婪动作的总概率是，选择任何其他动作的概率是。
算法描述
- 策略改进步骤
其中表示所有具有给定值的-贪婪策略的集合。通过这种方式，我们强制策略为-贪婪策略。（5.5）的解是
其中。通过上述改变，我们得到了另一种算法，称为蒙特卡洛-贪婪算法（MC -Greedy）。该算法的详细内容在算法 5.3 中给出。在这里，采用每次访问策略以更好地利用样本。
如果在策略改进步骤中，贪婪策略被-贪婪策略所取代，我们还能保证获得最优策略吗？答案既是肯定的，也是否定的。说肯定，是指当有足够多的样本时，算法收敛后的策略仅仅是在所有-贪心策略（具有相同的值）中是最优的。说否定，是指该策略仅仅在中是最优的，但在中可能不是最优的。然而，如果足够小，那么中的最优策略与中的最优策略很接近。
示例
考虑图 5.5 所示的网格世界示例。目的是为每个状态找到最优策略。在蒙特卡洛-贪婪算法的每次迭代中生成一个包含一百万个步骤的episode。在这里，我们特意考虑只有一个episode的极端情况。我们设置，以及。
初始策略是一个均匀策略，采取任何行动的概率都相同，为 0.2，如图 5.5 所示。经过两次迭代，可以得到时的最优-贪婪策略。尽管每次迭代仅使用一个episode，但策略会逐渐改进，因为所有的状态-动作对都可以被访问到，因此它们的值可以被准确估计。
-贪婪策略的性质
接下来，我们基于一些有趣的例子来讨论这种权衡。这里的强化学习任务是一个 5×5 的网格世界。奖励设置为：边界奖励，禁止区域奖励，目标奖励。折扣率为。
-贪心策略的最优性
接下来我们将展示，当增加时，-贪心策略的最优性会变差。
- 首先，图 5.6(a)展示了贪心最优策略及相应的最优状态价值。一些一致的-贪心策略的状态价值如图 5.6(b)-(d)所示。这里，如果两个-贪心策略中概率最大的动作相同，则这两个策略是一致的。
随着的值增加，-贪心策略的状态价值减小，这表明这些-贪心策略的最优性变差。值得注意的是，当高达 0.5 时，目标状态的值变为最小。这是因为当较大时，从目标区域开始的智能体可能会进入周围的禁止区域，从而更有可能获得负奖励。
- 其次，图 5.7 展示了最优的-贪心策略（它们在中是最优的）。当时，该策略是贪心的，并且在所有策略中是最优的。当小到 0.1 时，最优的-贪心策略与最优贪心策略一致。然而，当增加到例如 0.2 时，得到的-贪心策略与最优贪心策略不一致。因此，如果我们想要获得与最优贪心策略一致的-贪心策略，的值应该足够小。
为什么当较大时，-贪心策略与最优贪心策略不一致呢？我们可以通过考虑目标状态来回答这个问题。在贪心情况下，目标状态下的最优策略是保持不动以获得正回报。然而，当较大时，很有可能进入禁区并获得负回报。因此，在这种情况下，目标状态下的最优策略是逃离而不是保持不动。
-贪心策略的探索能力
接下来我们说明，当较大时，-贪心策略的探索能力很强。
- 首先，考虑一个 = 1的-贪心策略（见图 5.5(a)）。在这种情况下，-贪心策略的探索能力很强，因为在任何状态下采取任何动作的概率为 0.2。从（）开始，由-贪心策略生成的一个 episode在图 5.8(a)-(c)中给出。可以看出，由于该策略具有很强的探索能力，当情节足够长时，这一个情节可以多次访问所有的状态-动作对。此外，如图 5.8(d)所示，所有状态-动作对被访问的次数几乎是相等的。
- 其次，考虑一个值为 0.5 的-策略（见图 5.6(d)）。在这种情况下，-贪心策略的探索能力比 = 1 时弱。从状态开始，由该-策略生成的一个episode如图 5.8(e)-(g)所示。虽然在 episode足够长时仍然可以访问到每一个动作，但访问次数的分布可能极其不均衡。例如，对于一个有一百万步的 episode，一些动作被访问超过 25 万次，而大多数动作仅被访问几百次甚至几十次，如图 5.8(h)所示。
上述例子表明，当减小时，-贪婪策略的探索能力会下降。一种有用的技术是最初将设置得较大以增强探索能力，然后逐渐减小它以确保最终策略的最优性[21–23]。
Q&A
- 问题1：什么是蒙特卡洛估计？ 回答：蒙特卡洛估计是指一大类使用随机样本解决近似问题的技术。
- 问题2：什么是均值估计问题？ 回答：均值估计问题是指基于随机样本计算随机变量的期望值。
- 问题3：如何解决均值估计问题？ 答案：有两种方法：基于模型的方法和无模型的方法。具体来说，如果一个随机变量的概率分布是已知的，那么可以根据其定义计算期望值。如果概率分布未知，我们可以使用蒙特卡洛估计来近似期望值。当样本数量很大时，这种近似是准确的。
- 问题4：为什么均值估计问题对强化学习很重要？ 答案：状态价值和动作价值都被定义为回报的期望值。因此，估计状态价值或动作价值本质上是一个均值估计问题。
- 问题5：无模型基于蒙特卡洛的强化学习的核心思想是什么？ 答案：核心思想是将策略迭代算法转换为无模型的算法。具体来说，策略迭代算法旨在基于系统模型计算动作价值，而基于蒙特卡洛的强化学习则用无模型基于蒙特卡洛的策略评估步骤取代策略迭代算法中的基于模型的策略评估步骤。
- 问题6： initial-visit、first-visit和every-visit策略是什么？ 答案：它们是在一个episode中利用样本的不同策略。一个episode可能会访问许多状态-动作对。initial-visit策略使用整个episode来估计初始状态-动作对的动作价值。first-visit和every-visit策略可以更好地利用给定的样本。如果每次访问一个状态-动作对时都使用episode的其余部分来估计其动作价值，这种策略称为every-visit。如果在情节中只统计一个状态-动作对第一次被访问的情况，这种策略称为first-visit。
- 问题7：什么是exploring starts？为什么它很重要？ 答案：exploring starts条件要求从每个状态-动作对开始生成无限数量（或足够多）的episodes。理论上，exploring starts条件对于找到最优策略是必要的。也就是说，只有当每个动作价值都被充分探索时，我们才能准确地评估所有动作，然后正确地选择最优动作。
- 问题8：用于避免exploring starts的思路是什么？ 答案：基本思路是使用软策略。软策略是随机的，使一个episode能够访问许多状态-动作对。这样，我们就不需要从每个状态-动作对开始生成大量的episodes。
- 问题9：-贪心策略可以是最优的吗？ 答案：答案既是肯定的也是否定的。说肯定，是指如果有足够的样本，蒙特卡洛-贪心算法可以收敛到一个最优的-贪心策略。说否定，是指收敛后的策略仅仅是在所有-贪心策略（具有相同的值）中是最优的。
- 问题10：是否有可能用一个episode访问所有的状态-动作对？ 答案：是的，有可能。如果策略是软策略（例如-贪心策略）且episode足够长。
- 问题11：蒙特卡洛基础算法（MC Basic）、蒙特卡洛探索起点算法（MC Exploring Starts）和蒙特卡洛-贪心算法（MC -Greedy）之间有什么关系？ 答案：蒙特卡洛基础算法是最简单的基于蒙特卡洛的强化学习算法。它很重要，因为它揭示了无模型基于蒙特卡洛的强化学习的基本思想。蒙特卡洛探索起点算法是蒙特卡洛基础算法的一个变体，它调整了样本使用策略。此外，蒙特卡洛-贪心算法是蒙特卡洛探索起点算法的一个变体，它去除了探索起点的要求。因此，虽然基本思想很简单，但当我们想要实现更好的性能时，就会出现复杂性。对于初学者来说，将核心思想与可能分散注意力的复杂部分区分开来是很重要的。