5.3-MC Exploring Starts算法
下面通过推广MC Basic算法来介绍另一个基于蒙特卡罗的强化学习算法：MC Exploring Starts。这个算法稍微复杂一些，但它的效率更高。
5.3.1 更有效地利用样本¶
基于蒙特卡洛(MC)的强化学习的一个重要方面是如何更有效地利用样本。具体来说，假设我们通过遵循策略\(\pi\)获得了一个回合：
上式中s和a的下标指的是状态和动作的索引，而不是时间步数。如果一个状态-行动对在一个回合中出现了一次，那么我们称该状态-动作被访问(visit)一次。有多种方法来利用这些访问。
第一种也是最简单的方法是：一个回合仅用于估计该回合最开始访问的状态-行动的行动值。例如在式\((5.3)\)中，这个回合最开始访问的是\((s1, a_2)\),那么回合只是被用来估计\((s1, a_2)\)的行动值。前面介绍的MC Basic的算法就采用了首次访问策略。
虽然这种方法很简单，但是它没有充分利用样本，因为回合还访问了许多其他的状态动作，例如\((s_2,a_4),(s_2,a_3),(s_5,a_1)\)。实际上，一个回合也可以被用于估计其他状态-动作的价值。例如，我们可以将式\((5.3)\)中的回合分解成多个子回合：
如上式所示，一个长的回合可以被看成很多个从不同状态-动作出发的子回合，因此可以估计多个不同状态-行动的行动值。通过这种方式，一个回合中的样本可以被更有效地利用。
在一个回合中，一个状态动作可能会被多次访问。例如，在式\((5.3)\)中的回合里，\((s_1,a_2)\)被访问了两次。如果我们只考虑第一次访问，这种方法被称为首次访问(first visit)。例如，以第一次出现的(si,a2)为开始的子回合会被用来估计\((s_1,a_2)\)的行动值。如果我们考虑每一次访问，则这种方法被称为每次访问(every visit)20。例如，每次出现\((s_1,a_2)\)时，以其为开始的子回合会被用来估计其动作值。
在样本使用效率方面，每次访问都利用的方法效率是最高的，如果一个回合足够长，那么它可以多次访问所有状态-动作，那么这一个回合就足以估计所有的状态-行动的行动值，此时则需要使用每次访问的方法。然而，通过这种方法获得的回报样本是相关的，因为从第二次访问开始的轨迹只是从第一次访问开始的轨迹的一部分。尽管如此，如果两次访问在轨迹中相隔很远，那么相关性也不会很强。
5.3.2 更高效地更新策略¶
除了上节介绍的高效利用样本，我们还可以更高效地更新策略。有两种更新策略的方法。
- 第一种策略是在策略评估步骤中，收集从某一个状态-行动开始的所有回合，然后使用所有回合的平均回报来近似行动值，进而再更新策略。
这种方法已经在MC Basic算法中被采用。它的一个缺点是智能体必须等到所有回合都被收集完毕后才能估计动作值。
- 第二种策略是在策略评价步骤中，收集从某一个状态-行动开始的单个回合，然后使用这个单个回合的回报来近似行动值，进而再立即更新策略。这样的好处是不需要等到收集完所有回合，而是可以在得到一个回合后立即更新值和策略。
Note
由于单个回合的回报无法准确近似相应的行动值，读者可能会怀疑第二种策略是否有效。在上一章介绍的截断策略迭代算法中，第一步做的是策略评估，在那一步中要求出当前策略的状态值，求状态值要求解贝尔曼公式，又需要无穷多步迭代，当时在那个算法中我们只做有限步迭代，虽然得不到非常精确的状态值，但这个算法仍然可行。与现在这个思想类似，用一个回合来估计行动值，这显然是不精确的，但是没关系。
5.3.3 算法描述¶
将第\(5.3.1\)节和第\(5.3.2\)节介绍的技巧融合到MC Basic算法中，我们可以得到效率更高的称为MC Exploring Starts的新算法。
算法\(5.2\)中给出了MC Exploring Starts的详细流程。该算法利用了回合中的每次访问。在计算从每个状态-动作开始获得的回报时，采用“回溯”的方式，即先从回合最后的状态-行动开始，慢慢推回最初的状态-行动，这样可以使算法更高效，这就是为什么首先引入不使用这些技巧的MC Basic算法，以揭示基于MC的强化学习的核心思想。
MC Exploring Starts算法有一个条件，即Exploring Starts条件：对每一个状态-行动，都要有足够多的回合从它出发(这里“每一个”对应了Exploring,“出发”对应了Starts)。只有这样，我们才能准确估计每一个状态-动作的价值，进而成功找到最优策略。否则，如果存在一个状态-行动，而所有的回合都没有从它出发，那么我们无法估计出该状态-行动的行动值。即使这个行动确实是最优的，但是因为它没有被访问过，所以可能刚好被错过。
Note
探索(Exploring Starts) 指的是我从每一个\((s,a)\)出发，都要有一个回合，才能估计return，进一步估计行动值，如果没有漏掉某个行动，那么这个可能是最优的，但是却没有访问到。
起始(starts) 对每个\((s,a)\)生成return有两种方法，一种是每一个\((s,a)\)开始都有一个回合，叫做 start,第二种方法是从其他\((s,a)\)开始，但也能经过当前的\((s,a)\)，那么后面的数据也可以估计当前\((s,a)\)的return，叫做 visit。
当前来看,visit方法没法确保，因为它不能保证从其他\((s,a)\)出发可以经过剩下的所有\((s,a)\)。
MC Basic和MC Exploring Starts都需要满足这一条件。然而，这个条件在许多场景中很难满足，因为我们难以确保有足够多的回合从每一个状态-行动出发。实际上，如果只是为了确保每一个状态-行动都被访问到，那么可以用下面介绍的软策略的方法。
算法\(5.2\): MC Exploring Starts(MC Basic算法的一种高效变体)