5.3-MC Exploring Starts算法

5.3 MC Exploring Starts算法

接下来，我们将MC Basic算法扩展，得到另一种基于蒙特卡洛(MC)的强化学习算法，该算法稍显复杂，但样本效率更高。

5.3.1 更有效地利用样本

基于蒙特卡洛(MC)的强化学习的一个重要方面是如何更有效地利用样本。具体来说，假设我们通过遵循策略\(\pi\)获得了一个回合：

\[s_1\xrightarrow{a_2}s_2\xrightarrow{a_4}s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_1}\ldots\tag{5.3}\]

Note

每当回合中出现一个状态-行动对时，就称为对该状态-行动对的依次访问(visit)。比如上面例子(s_1,a_2)就称为一次访问,(s_2,a_4)就称为一次访问。

其中下标指的是状态或行动的索引，而非时间步。每当一个状态-行动对在一次经历中出现时，就称为对该状态-动作对的一次访问。可以采用不同的策略来利用这些访问。

第一个也是最简单的策略是使用首次访问(initial visit)。也就是说，一个回合仅用于估计该回合开始时的初始状态-动作对的行动值。对于\((5.3)\)中的例子，首次访问策略仅估计该回合中状态-行动对\((s1, a2)\)的行动值。MC Basic算法就采用了首次访问策略。然而，这种策略并不是样本高效的，因为该回合还访问了许多其他状态-行动对，例如\((s_2,a_4),(s_2,a_3),(s_5,a_1)\)。这些访问也可以用来估计相应的行动值。特别是，我们可以将\((5.3)\)中的回合分解为多个子回合：

\[\begin{aligned}s_{1}\xrightarrow{a_{2}}s_{2}\xrightarrow{a_{4}}s_{1}\xrightarrow{a_{2}}s_{2}\xrightarrow{a_{3}}s_{5}\xrightarrow{a_{1}}\ldots&\begin{aligned}[\text{original episode}]\end{aligned}[\text{original episode}]\\s_{2}\xrightarrow{a_{4}}s_{1}\xrightarrow{a_{2}}s_{2}\xrightarrow{a_{3}}s_{5}\xrightarrow{a_{1}}\ldots&[\text{subepisode starting from }(s_2,a_4)]\\s_{1}\xrightarrow{a_{2}}s_{2}\xrightarrow{a_{3}}s_{5}\xrightarrow{a_{1}}\ldots&[\text{subepisode starting from }(s_1,a_2)]\begin{aligned}[\text{subepisode starting from }(s_1,a_2)]\end{aligned}\\s_{2}\xrightarrow{a_{3}}s_{5}\xrightarrow{a_{1}}\ldots&[\text{subepisode starting from }(s_2,a_3)]\\s_{5}\xrightarrow{a_{1}}\ldots&[\text{subepisode starting from }(s_5,a_1)]\end{aligned}\]

在访问了一个状态-行动对之后生成的轨迹可以被视为一个新的回合。这些新的回合可用于估计更多的行动值。通过这种方式，回合中的样本可以得到更有效的利用。

此外，在一个回合中，一个状态-行动对可能会被多次访问。例如，在\((5.3)\)中的回合中，\((s_1,a_2)\)被访问了两次。如果我们只计算首次访问，这种策略称为首次访问策略(first-visit)；如果我们考虑该状态-动作对在轨迹中的所有出现，累积每次的回报，则这种策略称为每次访问策略(every-visit)[20]。

在样本使用效率方面，每次访问策略(every-visit)是最好的。如果一个回合足够长，能够多次访问所有状态-行动对，那么仅凭这一回合的样本就足以使用每次访问策略来估计所有行动值。然而，每次访问策略所获得的样本之间存在相关性，因为从第二次访问开始的轨迹仅仅是第一次访问轨迹的一部分。不过，如果两次访问在轨迹中相距较远，这种相关性就不会很强。

5.3.2 更高效地更新策略

基于蒙特卡洛(MC)的强化学习的另一个方面是何时更新策略。有两种策略可供选择。

• 第一种策略是在策略评估步骤中，收集从同一状态-行动对开始的所有回合，然后使用这些回合的平均回报来近似行动值。

这种策略被采用在MC Basic算法中。这种策略的缺点是，智能体必须等到所有回合都被收集完毕后才能更新估计值。

• 第二种策略可以克服这一缺点，即利用单个回合的回报来近似相应的行动值。如此当我们获得一个回合时，就可以立即得到一个粗略的估计值。然后，我们可以在逐个回合的基础上逐步改进策略。

Note

由于单个回合的回报无法准确近似相应的行动值，人们可能会怀疑第二种策略是否有效。在上一章介绍的截断策略迭代算法中，第一步做的是 policy evaluation，在那一步中要求出当前策略的状态值，求状态值要求解贝尔曼公式，又需要无穷多步迭代，当时在那个算法中我们只做有限步迭代，虽然得不到非常精确的状态值，但这个算法仍然可行。与现在这个思想类似，用一个回合来估计行动值，这显然是不精确的，但是没关系。

5.3.3 算法描述

我们可以利用第\(5.3.1\)节和第\(5.3.2\)节中介绍的技术来提高MC Basic算法的效率，从而得到一种新的算法，称为MC Exploring Starts。

MC Exploring Starts的细节在算法\(5.2\)中给出。该算法采用了每次访问策略。有趣的是，在计算从每个状态-行动对开始获得的折现回报时，过程是从结束状态开始，逆向回到起始状态。这样的技术可以提高算法的效率，但也使得算法变得更加复杂。这就是为什么首先引入不使用这些技术的MC Basic算法，以揭示基于MC的强化学习的核心思想。

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)\)。

Question

我在学习这部分的过程中，有点疑惑，后面我会在另开一章，后面另开一章进行讲解。

探索开始(Exploring Starts)要求从每个状态-行动对开始足够多的回合。只有当每个状态-动作对都被充分探索时，我们才能根据大数定律准确估计它们的行动值，从而成功找到最优策略。否则，如果某个动作没有被充分探索，其行动值可能会被错误估计，即使该行动实际上是最佳行动，也可能不会被策略选择。MC Basic和MC Exploring Starts都需要满足这一条件。然而，在许多应用中，尤其是涉及与环境的物理交互时，这一条件很难满足。那么，我们能否去掉探索开始的要求呢？答案是肯定的，我们将在下节中进行探索。

算法\(5.2\): MC Exploring Starts(MC基本算法的一种高效变体)