5.2-MC Basic:最简单的基于蒙特卡洛的算法
5.2- 最简单的基于蒙特卡洛的算法¶
本节介绍第一个也是最简单的基于蒙特卡洛(MC)的强化学习算法。该算法通过用无模型的MC估计步骤替换第\(4.2\)节中介绍的基于模型的策略迭代算法中的模型策略评估步骤而得到。
5.2.1 将策略迭代转化为无模型方法¶
策略迭代算法的每一步迭代包含两个步骤(见第\(4.2\)节)。第一步是策略评估，其目的是通过求解方程\(v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k}v_{\pi_k}\)来计算\(v_{\pi_k}\)。第二步是策略改进，其目的是计算Greedy策略\(\pi_{k+1} = \arg\max_{\pi} \left( r_{\pi} + \gamma P_{\pi} v_{\pi k} \right).\)。策略改进步骤的逐元素形式为
行动值\(q_{\pi_k}(s,a)\)是最核心的量。具体而言，在第一步中，状态值被计算出来，以便于计算行动值。在第二步中，基于计算出的动作值生成新的策略。计算行动值有两种方法可供选择。
-
第一种方法是基于模型的方法。这种方法在策略迭代算法所采用。具体来说，我们首先可以通过求解贝尔曼方程来计算状态值\(v_{\pi_k}\)。然后，我们可以通过使用以下公式来计算动作值：
\[q_{\pi_k}(s,a) = \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a)v_{\pi k}(s').\tag{5.1}\]这种方法要求已知系统模型\(p(r|s,a), p(s^\prime|s,a)\)。
-
第二种方法是无模型方法。回想一下，行动值的定义是
\[\begin{aligned}q_{\pi_k}(s,a) &= \mathbb{E}[G | S_t = s, A_t = a]\\&= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s, A_t = a],\end{aligned}\]这是从\((s,a)\)开始时所获得的期望回报。由于\(q_{\pi_k}(s,a)\)是一个期望值，因此可以通过第\(5.1\)节中所展示的蒙特卡洛(MC)方法进行估计。为此，从\((s,a)\)开始，智能体可以按照策略\(\pi_k\)与环境交互，然后获得一定数量的回合。假设共有\(n\)条回合，第\(i\)条回合的回报为\(g^{(i)}_{\pi_k}(s,a)\)，那么\(q_{\pi_k}(s,a)\)可以近似为：
\[q_{\pi k}(s,a) = \mathbb{E}[G | S_t = s, A_t = a] \approx \frac{1}{n} \sum_{i=1}^{n} g_{\pi_k}^{(i)}(s,a).\]我们已经知道，如果试验次数\(n\)足够大，根据大数定律，这种近似将会足够精确。
基于蒙特卡洛(MC)的强化学习的基本思想是，使用一种无模型的方法来估计动作值，如式\((5.2)\)所示，以替代策略迭代算法中基于模型的方法。
5.2.2 基于蒙特卡洛的算法¶
我们现在介绍第一个基于蒙特卡洛(MC)的强化学习算法。该算法从初始策略\(\pi_0\)开始，在第\(k\)次迭代\((k=0,1,2,...)\)中包含两个步骤。
-
步骤一. 策略评估。此步骤用于估计所有状态-动作对\((s,a)\)的\(q_{\pi_k}(s,a)\)。具体而言，对于每个\((s,a)\)，我们收集足够多的回合，并使用回报的平均值\(q_k(s,a)\)来近似\(q_{\pi_k}(s, a)\)。
-
步骤二. 策略改进。 这一步骤通过求解\(\pi_{k+1}(s)=\arg\max_\pi \sum_a\pi(a|s)q_k(s,a)\)来确定所有状态\(s\in \mathcal{S}\)下的最优策略。Greedy最优策略为\(\pi_{k+1}(a_{k}^{*}|s)=1\)，其中\(a_{k}^{*}=\arg\max_{a}q_{k}(s,a).\)。
这是基于蒙特卡洛（MC）的强化学习中最简单的算法，在本书中称为MC Basic。MC Basic算法的伪代码见算法\(5.1\)。可以看出，它与策略迭代算法非常相似，唯一的区别在于，MC Basic直接从经验样本中计算行动值，而策略迭代则是先计算状态值，再根据系统模型计算行动值。需要注意的是，这种无模型算法直接估计行动值。如果改为估计状态值，则仍需使用系统模型从这些状态值计算动作值，如式(5.1)所示。
Note
注: 与策略迭代相比，第一步有所不同，即对于行动值的估计有所不同，而第二步是相同的
由于策略迭代是收敛的，因此在给定足够样本的情况下，MC Basic算法也是收敛的。也就是说，对于每个状态-行动对\((s,a)\)，假设从\((s,a)\)开始的足够多的回合(episode)，那么这些回合回报的平均值可以很好地近似\((s,a)\)的行动值。在实际应用中，我们通常无法为每个\((s,a)\)都获得足够多的回合，因此动作值的近似可能并不准确。尽管如此，该算法通常仍然可以正常运行。这与截断策略迭代算法类似，在截断策略迭代算法中，动作值也并非精确计算得到。
MC Basic由于其样本效率较低，过于简单而难以实际应用。我们介绍这个算法的原因是想让读者掌握基于MC的强化学习中的核心思想。在学习本章后面更复杂的算法之前充分理解MC Basic是非常重要的。我们将看到，通过扩展MC Basic算法，可以很容易地获得样本效率更高的算法。
算法5.1：MC Basic算法(一种无模型的策略迭代变体)
算法\(5.1\)：MC Basis算法(一种无模型的策略迭代变体)
5.2.3 示例¶
一个简单的例子: 逐步实施¶
图\(5.3\): 一个用于说明MC Basic算法的示例。
接下来，我们通过一个例子来演示MC Basic算法的实现细节。奖励设置为 \(r_\text{boundary} = r_\text{forbidden} = −1，r_\text{target} = 1\)。折现率为 \(\gamma = 0.9\)。初始策略\(\pi_0\)如图\(5.3\)所示。该初始策略对于状态\(s_1\)或\(s_3\)并非最优策略。
Note
注: 在这个例子中有\(9\)个状态，每个状态对应\(5\)个行动，有\(45\)个状态行动对，所以要找到\(45\)个\(q_{\pi_k} (s,a)\)，假设从每一个\((s,a)\)出发都有\(N\)个回合，最后要求\(N\)条回合的平均的\(return\)，那么一共有\(45\times N\)个回合。
虽然所有行动值都应该被计算出来，但由于篇幅限制，我们仅展示了\(s_1\)的行动值。在\(s_1\)处，有五种可能的动作。对于每种动作，我们需要收集足够长的多个轨迹，以便有效地近似行动值。然而，由于这个例子在策略和模型方面都是确定性的，多次运行将生成相同的轨迹。因此，每个行动值的估计仅需要一个回合即可。
在\(\pi_0\)之后，我们可以通过分别从\((s_1, a_1),(s_1,a_2),...,(s_1,a_5)\)开始，得到以下回合。
-
从\((s_1,a_1)\)开始，该回合为\(s_1\xrightarrow{a_1}s_1\xrightarrow{a_1}s_1\xrightarrow{a_1}\ldots\)。行动值等于该回合的折现回报：
\[q_{\pi_0}(s_1,a_1)=-1+\gamma(-1)+\gamma^2(-1)+\cdots=\frac{-1}{1-\gamma}.\] -
从\((s_1,a_2)\)开始，该回合为\(s_1\xrightarrow{a_2}s_2\xrightarrow{a_3}s_5\xrightarrow{a_3}\ldots\)。行动值等于该回合的折现回报：
\[q_{\pi_0}(s_1,a_2)=0+\gamma0+\gamma^20+\gamma^3(1)+\gamma^4(1)+\cdots=\frac{\gamma^3}{1-\gamma}.\] -
从\((s_1,a_3)\)开始，该回合为\(s_1\xrightarrow{a_3}s_4\xrightarrow{a_2}s_5\xrightarrow{a_3}\ldots\)。行动值等于该回合的折现回报：
\[q_{\pi_0}(s_1,a_3)=0+\gamma0+\gamma^20+\gamma^3(1)+\gamma^4(1)+\cdots=\frac{\gamma^3}{1-\gamma}.\] -
从\((s_1,a_4)\)开始，该回合为\(s_1\xrightarrow{a_4}s_1\xrightarrow{a_1}s_1\xrightarrow{a_1}\ldots\)。行动值等于该回合的折现回报：
\[q_{\pi_0}(s_1,a_4)=-1+\gamma(-1)+\gamma^2(-1)+\cdots=\frac{-1}{1-\gamma}.\] -
从\((s_1,a_5)\)开始，该回合为\(s_1\xrightarrow{a_5}s_1\xrightarrow{a_1}s_1\xrightarrow{a_1}\ldots\)。行动值等于该回合的折现回报：
\[q_{\pi_0}(s_1,a_5)=0+\gamma(-1)+\gamma^2(-1)+\cdots=\frac{-\gamma}{1-\gamma}.\]
通过比较这五个行动值，我们发现
是最大值。因此，可以得到新的策略为：
很明显，改进后的策略在状态\(s_1\)处选择\(a_2\)或\(a_3\)是最佳的。在这个简单例子中，初始策略对于除\(s_1\)和\(s_3\)之外的所有状态来说已经是最优的，因此策略只需经过一次迭代即可达到最优。当策略对于其他状态来说不是最优时，则需要更多的迭代次数。
Note
注: 这个地方大家可以再计算一下状态\(s_3\)处的行动值，从\(a_1\)到\(a_5\)，行动值依次为\(-10,-10,8,7.29,-9\)
一个综合示例：回合长度与稀疏奖励¶
接下来，我们通过一个更复杂的例子来讨论MC Basic算法的一些性质。该例子是一个\(5\times5\)的网格世界(图\(5.4\))。奖励设置为：\(r_\text{boundary} = −1,r_\text{forbidden} = −10，r_\text{target} = 1\)。折现率为\(\gamma = 0.9\)。
首先，我们证明了回合长度(episode length)对最优策略有显著影响。具体而言，图\(5.4\)展示了MC Basic算法在不同回合长度下生成的最终结果。当每个回合的长度过短时，策略和价值估计均无法达到最优(见图\(5.4(a)-(d)\))。在回合长度为\(1\)的极端情况下，只有与目标相邻的状态才具有非零值，而其他所有状态的值均为零，因为每个回合都太短，无法达到目标或获得正奖励(见图\(5.4(a)\))。随着回合长度的增加，策略和价值估计会逐渐接近最优值(见图\(5.4(h)\))。
图\(5.4\): 当给定不同的回合长度时，MC基本算法所获得的策略和状态值。只有当每个回合的长度足够长时，状态值才能被准确估计。
随着回合长度的增加，逐渐显现出来一种现象：距离目标较近的状态会比距离目标较远的状态更早获得一个非零值。这种现象的原因是因为，智能体从某个状态出发至少需要经过一定数量的步数才能到达目标状态并获得正奖励。如果回合长度小于需要的最小步数，那么回报一定为零，状态值的估计值也会为零。在这个例子中，回合长度必须不少于\(15\)步，这是从左下角状态出发到达目标状态所需的最少步数。
上述分析表明，每个回合必须足够长，但这些回合并不一定需要无限长。如图\(5.4(g)\)所示，当回合长度为\(30\)时，算法可以找到最优策略，尽管此时的值估计尚未达到最优。
上述分析涉及一种重要的奖励设计问题，即稀疏奖励(sparse reward)。稀疏奖励是指在未达到目标时无法获得任何正奖励的情况。在这种设置下，智能体需要走过较长的回合长度才能达到目标。当状态空间较大时，这一要求很难满足，从而产生稀疏奖励问题从而降低了学习效率。解决这一问题的一种简单方法是设计非稀疏奖励。例如，在上述网格世界示例中，我们可以重新设计奖励设置，使智能体在接近目标的状态时获得较小的正奖励。这样，目标周围就会形成一个“引力场”，使智能体更容易找到目标。有关稀疏奖励问题的更多信息，可参见文献[17–19]。