5.4-MC-Greedy算法

下面进一步推广MC Exploring Starts，使其不再依赖于Exploring Starts这个条件。为此，我们需要引入软策略 (soft policy)。如果一个策略能在任意状态下有非零概率选择任意行动，那么该策略称为软策略。给定一个软策略，即使只有一个回合，只要这个回合足够长，它就会多次访问每个状态-行动对。此时，我们不再需要从不同状态-行动出发的很多回合，从而避免Exploring Starts这个条件。

Note

注: 为什么要引入soft policy？

采用软策略的话，从一个\((s,a)\)出发，如果回合很长的话，能够确保任何一个\(s\)和\(a\)都可以被该回合访问到。一些足够长的回合就可以访问所有的\((s,a)\)。从而不需要大量的回合即可，只需要从一个或者几个出发，这样就能移除exploring starts条件。

5.4.1 \(\varepsilon\)-greedy策略

Note

注: 策略分为deterministic和stochastic两种，之前讲的Greedy策略就是deterministic，而现在要讲的软策略和\(\varepsilon\)-Greedy都是stochastic的。

一种常见的软策略是\(\varepsilon\)-Greedy策略。具体来说，假设\(\varepsilon\in[0,1]\)，相应的\(\varepsilon\)-Greedy策略具有以下形式：

\[\left.\pi(a|s)=\left\{\begin{array}{ll}1-\frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1),&\text{for the greedy action,}\\\\\frac{\varepsilon}{|\mathcal{A}(s)|},&\text{for the other}|\mathcal{A}(s)|-1\mathrm{actions,}\end{array}\right.\right.\]

其中\(|\mathcal{A}(s)|\)表示与状态\(s\)相关联的行动数量。\(\varepsilon\)-Greedy是随机性策略，它选择具有最大行动值的行动的概率最高，而选择其他行动的概率都相同。在上式中，选择具有最大行动值行动的概率大于选择其他行动的概率，因为：

\[1-\frac{\varepsilon}{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1)=1-\varepsilon+\frac{\varepsilon}{|\mathcal{A}(s)|}\geq\frac{\varepsilon}{|\mathcal{A}(s)|}\]

对于任意\(\varepsilon\in[0,1]\)都成立。

当\(\varepsilon=0\)时，\(\varepsilon\)-Greedy策略变为普通的贪婪策略，此时策略的探索性最弱。当\(\varepsilon = 1\)时，采取任何行动的概率都等于\(\frac{1}{|\mathcal{A}(s)|}\)，此时策略的探索性最强。

由于\(\varepsilon\)-Greedy策略是随机性的，那么如何根据这样的策略选择行动呢?我们可以首先按照均匀分布在\([0,1]\)生成一个随机数\(x\)。如果\(x \geq \varepsilon\),那么选择最大行动值行动；如果\(x < \varepsilon\)，则以概率 \(\frac{1}{|A(s)|}\) 从\(A(s)\)中随机选择一个行动(此时可能再次选择到最大价值的行动)。通过这种方式，选择最大价值行动的总概率是 \(1 - \varepsilon + \frac{\varepsilon}{|A(s)|}\)，而选择其他行动的概率是 \(\frac{\varepsilon}{|A(s)|}\)。

5.4.2 算法描述

下面将\(\varepsilon\)-Greedy策略融合到MC Exploring Starts算法中，下面将\(\varepsilon\)-Greedy策略融合到MC Exploring Starts算法中，可以得到新的MC \(\varepsilon\)-Greedy算法，该算法已经不再依赖于Exploring Starts的条件。

我们只需将MC Exploring Starts算法中策略改进步骤中的Greedy改为\(\varepsilon\)-Greedy即可。具体来说，在MC Exploring Starts算法中，策略改进步骤旨在选择如下的Greedy策略：

\[\pi_{k+1}(s) = \arg \max_{\pi \in \Pi} \sum_{a} \pi(a|s) q_{\pi_k}(s, a),\tag{5.4}\]

其中\(\Pi\)表示所有可能策略的集合。我们知道\((5.4)\)的最优解是一个贪婪策略：

\[\pi_{k+1}(a|s) = \begin{cases}1, & \text{if } a = a^*; \\0, & \text{if } a \neq a^*;\end{cases}\]

其中\(a^* = \arg \max_a q_\pi(s, a)\)。

现在，策略改进步骤需要改成：

\[\pi_{k+1}(s) = \arg \max_{\pi \in \Pi_\varepsilon} \sum_{a} \pi(a|s) q_{\pi_k}(s, a),\tag{5.5}\]

其中\(\Pi_\varepsilon\)表示所有\(\varepsilon\)-Greedy策略的集合，给定\(\varepsilon\)的值。通过这种方式，我们强制把策略限制为\(\varepsilon\)-Greedy。方程\((5.5)\)的解不难得到：

\[\pi_{k+1}(a|s) = \begin{cases}1 - \frac{|A(s)| - 1}{|A(s)|} \varepsilon, & \text{if } a = a^*; \\\frac{\varepsilon}{|A(s)|}, & \text{if } a \neq a^*;\end{cases}\]

其中\(a^* = \arg \max_a q_{\pi_k}(s, a)\)。

通过上述改动，我们获得了另一个算法，称为MC \(\varepsilon\)-Greedy算法。由于\(\varepsilon\)-Greedy策略具有一定的探索性，这样就不需要有多个回合从每一个状态-行动出发了。算法\(5.3\)给出了其伪代码。

Note

注: 简而言之，这里就是把最大的概率给Greedy行动，而剩下的所有行动会给一个相同较小的概率。

如果在策略改进步骤中用\(\varepsilon\)-Greedy策略取代Greedy策略，我们还能保证得到最优策略吗？当给定足够多的样本时，算法总是可以收敛在集合\(\Pi_\varepsilon\)中最优的策略；不过，该策略仅在\(\Pi_\varepsilon\)中为最优，但在\(\Pi\)中可能并非最优(因为前者是后者的子集)。所以，\(\varepsilon\)的引入实际上是增加了策略的探索性，而牺牲了策略的最优性。不过如果\(\varepsilon\)足够小，那么在\(\Pi_\varepsilon\)中的最优策略将接近于在\(\Pi\)中的最优策略。

算法\(5.3\):MC \(\varepsilon\)-Greedy(MC exploring starts的变体)

5.4.3 示例

考虑图\(5.5\)所示的网格世界例子。这里的目标是为每个状态找到最优策略。在MC \(\varepsilon\)-Greedy算法的每次迭代中，生成一个包含一百万步的回合。这里考虑了仅包含一个回合的特殊情况。我们设定\(r_\text{boundary} = r_\text{forbidden} = −1,r_\text{target} = 1\)，以及\(\gamma= 0.9\)。

如图\(5.5\)所示，初始策略是一种均匀策略，采取任何行动的概率均为\(0.2\)。\(\varepsilon=0.5\)的最优\(\varepsilon\)-Greedy策略可以在两轮迭代后获得。尽管每次迭代仅使用一个回合，但因为所有状态-行动对都在这个回合中访问到了，所以它们的价值可以被准确估计。

图\(5.5\)：基于单个回合的MC \(\varepsilon\)-Greedy算法的演化过程。

Note

注: 图中\((a)\)是最初的策略，这个策略并不好，因为在每一步都有相同的概率去选择所有action，那么经过一个策略生成一个一百万步的回合，然后更新策略，就得到了\((b)\)中的策略，我们可以发现，在一些状态下，智能体会保持不动，因此我们再进行一次更新，如果只看绿色箭头最长的action(代表概率最大的action)，那么其相对于\((b)\)来说较为合理，从任何一点出发均可以到达目标，但是它们仍然会穿越过障碍物，从这个意义上来讲，这个策略还不是最优的，所以\(\varepsilon\)-Greedy通过牺牲最优性而获得了一些探索性。

---

评论