5.2-MC Basic:最简单的基于蒙特卡洛的算法
本节介绍第一个基于蒙特卡洛(MC)的强化学习算法。该算法可以通过修改上一章介绍的策略迭代算法得到，即将其中的基于模型的模型策略评估步骤替换为一个无需模型的策略估计步骤；此外该算法可以帮助我们理解究竟如何使用数据代替模型来实现强化学习，这也是本章后续算法的直接基础。
5.2.1 将策略迭代算法转化为无模型方法¶
在上一章我们详细介绍过，策略迭代算法的每次迭代包含两个步骤(见第\(4.2\)节)。第一步是策略评估，其目的是通过求解方程\(v_{\pi_k} = r_{\pi_k} + \gamma P_{\pi_k}v_{\pi_k}\)来计算\(v_{\pi_k}\)。第二步是策略改进，其目的是计算贪婪策略\(\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}\]值得注意的是，因为\(q_{\pi_k}(s,a)\)是一个期望值，所以可以通过蒙特卡洛方法用数据进行估计。首先，从\((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).\tag{5.2}\]根据大数定律，如果\(n\)足够大，上面的近似将会足够精确。
基于蒙特卡洛的强化学习的基本思想是使用\((5.2)\)来估计行动值，从而代替策略迭代算法中需要模型的模块。
5.2.2 MC Basic算法¶
有了上一节的准备，下面介绍MC Basic算法。
从初始策略\(\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}\)的新策略。即\(\pi_{k+1}(a_{k}^{*}|s)=1\)，其中\(a_{k}^{*}=\arg\max_{a}q_{k}(s,a)\)。
MC Basic算法的伪代码在算法\(5.1\)中给出，它与策略迭代算法非常相似，唯一的区别在于它直接从经验样本中估计行动值，而策略迭代需要用模型先计算状态值再计算行动值。需要注意的是，MC Basic算法是直接估计行动值。否则，如果它先估计状态值，那么仍然需要利用\((5.1)\)将状态值转换到行动值，而\((5.1)\)还是需要模型的，因此MC Basic是直接估计行动值。
Note
注: 与策略迭代相比，第一步有所不同，即对于行动值的估计有所不同，而第二步是相同的
由于策略迭代是收敛的，因此在给定足够样本的情况下，MC Basic算法是可以确保收敛的。也就是说，对于每个\((s,a)\)，假设从\((s,a)\)开始有足够多的回合，那么这些回合回报的平均值可以准确地近似\((s,a)\)的行动值。在实际应用中，通常无法为每以一个\((s,a)\)收集足够多的回合，此时行动值的近似可能并不准确。不过该算法仍然可以正常运行。这与截断策略迭代或者广义策略迭代的思想类似：每一个行动值不需要非常准确地估计。
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\)，有五种可能的行动。我们需要从\((s_1, a_1),(s_1,a_2),...,(s_1,a_5)\)开始执行当前策略\(\pi_0\)，得到足够多且足够长的回合，不过因为这个示例是确定性的，多次运行将得到相同的回合，因此只需要对每个行动收集一个回合。
-
从\((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}.\]
通过比较上面五个行动值，我们发现：
相比其他行动值是最大值。因此，可以得到新的策略是选择\(a_2\)或者\(a_3\)：
很明显，在状态\(s_1\)处选择\(a_2\)或\(a_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算法在使用不同回合长度下得到的最终结果。其中状态值是通过MC Basic算法得给出的行动值计算得到的。当设置的回合的长度过短时，用MC Basic算法得到的策略和价值都不是最优的(见图\(5.4(a)-(d)\))。在回合长度为\(1\)的极端情况下，此时仅与目标相邻的状态有非零值，所有其他状态的值都为\(0\)(图\(5.4(a)\))，这是因为每个回合都太短而无法达到目标从而获得正奖励(见图\(5.4(a)\))。随着回合长度的增加，得到的策略和价值估计会逐渐接近最优值(见图\(5.4(h)\))。
其次，随着回合长度的增加，出现了一种有趣的现象：距离目标较近的状态会比距离目标较远的状态更早拥有一个非零值。原因如下：智能体从某个状态出发至少需要经过一定数量的步数才能到达目标状态；如果回合长度小于需要的最小步数，那么回报一定为0，估计的状态值也是0。在这个例子中，回合长度必须不少于\(15\)步，这是从左下角状态出发到达目标状态所需的最少步数。虽然每个回合必须足够长，但是也不需要无限长。如图\(5.4(g)\)所示，当回合长度为\(30\)时，该算法已经可以找到最优策略，尽管此时的价值估计还不是最优的。
上述分析涉及一种重要的奖励设计问题，即稀疏奖励 (sparse reward)。稀疏奖励指的是除非到达目标，否则无法获得任何正奖励。稀疏奖励要求回合必须到达目标。当状态空间比较大或者系统随机性比较强时，在一个回合内到达目标的概率是比较低的。因此，稀疏奖励降低了学习效率。解决这个问题的一个简单方法是设计非稀疏奖励或者稠密奖励。例如，在上述网格世界中，我们可以重新设计奖励，使得智能体在靠近目标时就可以获得少量的正奖励。通过这种方式，可以在目标周围形成一个“吸引场”,从而更容易地找到目标。感兴趣的读者可以查看更多关于稀疏奖励的文献[17,18,19]。
图\(5.4\): 当给定不同的回合长度时，MC基本算法所获得的策略和状态值。