跳转至

5.4-MC-Greedy算法

5.4- MC \(\varepsilon\)-Greedy算法

接下来，我们通过移除探索开始(Exploring Starts)条件来扩展MC Exploring Starts算法。这一条件实际上要求每个状态-行动对都能被访问足够多次，这也可以通过软策略来实现。

5.4.1 \(\varepsilon\)-greedy策略

如果一个策略在任何状态下采取任何行动的概率都为正(即可能选择任何一种行动)，则该策略是软策略。考虑一种极端情况，即我们只有一个回合。在这种情况下，如果采用软策略，一个足够长的回合可以多次访问每个状态-动作对(见图\(5.8\)中的例子)。因此，我们不需要从不同的状态-动作对开始生成大量回合，这时便可以移除探索开始的要求。

Note

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

一种常见的软策略是\(\varepsilon\)-Greedy策略。\(\varepsilon\)-Greedy策略是一种随机策略，它选择Greedy动作的概率较高，而选择任何其他动作的概率则相同且不为零。这里的Greedy动作是指具有最大动作值的动作。具体来说，假设\(\varepsilon\in[0,1]\)，相应的\(\varepsilon\)-Greedy策略具有以下形式：

Note

注: 为什么要引入soft policy？

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

\[\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=0\)时，\(\varepsilon\)-Greedy策略变为Greedy策略。当\(\varepsilon = 1\)时，采取任何动作的概率都等于\(\frac{1}{|\mathcal{A}(s)|}\)。

采取Greedy行动的概率总是大于采取任何其他动作的概率,因为对于任意\(\varepsilon\in[0,1]\)有

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

虽然 \(\varepsilon\)-Greedy策略是随机的，但我们如何按照这样的策略选择一个动作呢？我们可以首先按照均匀分布生成一个位于\([0,1]\)之间的随机数\(x\)。如果\(x \geq \varepsilon\)，则选择Greedy动作。如果\(x < \varepsilon\)，则以概率 \(\frac{1}{|A(s)|}\) 从\(A(s)\)中随机选择一个动作（可能会再次选择Greedy动作）。这样，选择Greedy动作的总概率是 \(1 - \varepsilon + \frac{\varepsilon}{|A(s)|}\)，而选择其他动作的概率是 \(\frac{\varepsilon}{|A(s)|}\)。

5.4.2 算法描述

为了将\(\varepsilon\)-Greedy策略集成到MC学习中，我们只需将策略改进步骤中的Greedy改为\(\varepsilon\)-Greedy即可。

特别地，MC Basic或MC Exploring Starts中的策略改进步骤旨在解决(在第一步中求解了\(q_{\pi_k}(s,a)\)，这一步要求解下面这个优化问题得到一个新的策略)

\[\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)\)的解是一个Greedy策略：

\[\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算法。该算法的详细内容在算法\(5.3\)中给出。这里采用每次访问(every-visit)的策略来更好地利用样本。

Note

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

如果在策略改进步骤中用\(\varepsilon\)-Greedy策略取代Greedy策略，我们还能保证得到最优策略吗？答案是既肯定又否定。肯定是指，当给定足够多的样本时，该算法可以收敛到一个在集合\(\Pi_\varepsilon\)中为最优的\(\varepsilon\)-Greedy策略；否定是指，该策略仅在\(\Pi_\varepsilon\)中为最优，但在\(\Pi\)中可能并非最优。然而，如果\(\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\)。

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

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

Note

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