强化学习：蒙特卡洛方法(MC)-Toy模板网

这篇具有很好参考价值的文章主要介绍了强化学习：蒙特卡洛方法(MC)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引入蒙特卡洛方法例子

以抛硬币为例，将结果(正面朝上或反面朝上)表示为作为随机变量 $X$ ，如果正面朝上则 $X = + 1$ ，如果反面朝上，则 $X = - 1$ ，现在要计算 $E [X]$ 。
我们通常很容易想到直接用定义来计算，因为我们知道正面朝上和反面朝上的概率都是为 0.5 ，显然我们根据模型知道的结果，因此我们把这种方法称为基于模型的计算，如下图。
强化学习：蒙特卡洛方法(MC)
但是，我们通常是不知道模型参数的，那么我们能不能在不知道模型参数的情况下去计算呢？答案是肯定的。以抛硬币为例，可以抛硬币很多次，然后将结果求平均，这就是蒙特卡洛的思想。

蒙特卡洛方法：基础算法

理解该算法的关键是理解如何将基于模型的算法转化为无模型算法。
通过前面学习，我们知道策略迭代有策略评估和策略更新两步，其中一个关键量为 $q_{πk}(s,a)$ ，而 $q_{πk}(s,a)$ 我们是根据模型来计算的。
强化学习：蒙特卡洛方法(MC)

在策略迭代中， $q_{πk}(s,a)$ 是依赖模型来计算的，那么还有其他不依赖于模型的方法吗？用 $q_{πk}(s,a)$ 定义计算，即通过大量采样 $g (s, a)$ 来计算。
强化学习：蒙特卡洛方法(MC)
我们来看一下这个算法的伪代码：

MC Basic 算法基本介绍

policy iteration 算法怎么转变成为 model-free 呢？我们知道 policy iteration 有策略评估和策略提升两步，然后 policy improvement 针对每一个状态 $s$ 展开得到如下式子，我们可以很容易知道这里边非常核心的一个量就是这个 $q_{πk}(s,a)$ 。
强化学习：蒙特卡洛方法(MC)
我们要计算 $q_{πk}(s,a)$ 有两种方法，一种是依赖与模型的，就是 value iteration 算法所用的；另一种就是不依赖与模型的，而是根据 action value 最原始的定义，这就是蒙特卡洛算法的核心。

强化学习：蒙特卡洛方法(MC)

我们来看一下蒙特卡洛计算 action value 的过程。用 $g (s, a)$ 表示在任意状态 $s$ 下根据策略 $π_k$ 采取行为 $a$ 得到一个 episode 的 return ， $g (s, a)$ 是 $G_t$ 的一个采样。如果我们有很多个 $g (s, a)$ ，那么我们可以根据定义求解得到 $q_{πk}(s,a)$ ，如下图：

强化学习：蒙特卡洛方法(MC)

实例：MC Basic 算法

下面我们通过例子来进一步学习 MC Basic，尽管 MC Basic 实际应用效率很低，但这个算法对于后面理解基于蒙特卡洛的 model-free 的强化学习算法是非常关键的。

强化学习：蒙特卡洛方法(MC)
如上图所示，给出的策略并不是最好的，现在我们使用 MC Basic 算法找到最优策略。MC Basic 算法与 policy iteration 一样分为 策略评估和策略优化 两步。我们很容易知道上例共有 $45$ 个 $(s, a)$ , 9 $s t a t es$ × 5 $a c t i o n s$ ，现在我们以 $s_1$ 的 5 个 $a c t i o n$ 为例进行讲解。

步骤1：策略评估
由于给定的例子环境是确定的，在给定的策略下每一条路径都是相同的，所以我们只采样一次。采样结果如下：

强化学习：蒙特卡洛方法(MC)

步骤2：策略优化

由第一步可知， $q_{π0}(s_1,a_2)$ = $q_{π0}(s_1,a_2)$ 是求得的最大值，因此我们可以任意选一个，从而得到最优策略。

MC Exploring Starts 算法

前面的 MC Basic 算法虽然算法原理比较清晰易懂，但缺点是不实用，而 MC Exploring Starts 算法是对 MC Basic 算法的推广，变得更加实用。那我们是怎么实现的呢？

首先，我们引进 visit ，指 episode 中每出现一个状态-动作时，就称为对状态-动作进行了一次访问。在网格世界中，遵循策略 $π$ 我们会得到一个 episode 如下图：

强化学习：蒙特卡洛方法(MC)

在 MC Basic 当中我们用的策略 Initial-visit ，即对于上例，我们只考虑 $s_1,a_2)$ ，用后面的 return 来计算 $q_π(s_1,a_2)$ ，我们可以发现这样对数据的使用效率并未充分利用，因为 $s_1,a_2)$ 后面的我们仍然可以看成一个 episode ，如下图：

强化学习：蒙特卡洛方法(MC)
这样我们就可以同时得到在当前的 episode 中其他状态-动作的 $q_π$ ，这其中也有两种方法，first-visit 和 every-visit 。first-visit 是指若有重复的状态-动作出现，那么只用第一次出现的去计算 $q_π$ ；every-visit 会对每次出现的的状态-动作都会去进行一次计算 $q_π$ ；

MC Exploring Starts 算法除了充分利用数据外，还能高效更新策略。MC Basic 算法中，要得到所有的 episode 后才能进行更新策略，而 MC Exploring Starts 算法是每得到一个 episode 就立刻进行更新策略，这样效率就能大大提升。

综上，我们得到 MC Exploring Starts 算法的伪代码，如下：
强化学习：蒙特卡洛方法(MC)

MC ε ε ε-Greed 算法: without Exploring Starts

MC Exploring Starts 算法中 Exploring Starts 条件是必要的，Exploring 表示从每个 $(s, a)$ 出发会得到相应的 episode ，再根据后边生成的这些 reward 来估计 return，然后进一步估计 action value 。而 action-value 有两种方式得到，一种是从当前状态开始，另一种是从其他状态开始经过当前状态，若采取第二种方法则存在一种情况，就是如果恰恰有一个 state-action 它没有被访问到，而这个 action 恰恰又可能是最优的，为了得到最优的，我们还是要确保每一个 $(s, a)$ 都能够被访问到，这就是 Starts 的含义。

那我们能不能去掉 MC Exploring Starts 算法中的 Exploring Starts 条件呢？方法是引入 soft policy ， soft policy 指对每一个action 都有可能去做选择。在 soft policy 下，一个足够长的 episode 就可以确保能访问到每个 $(s, a)$ ，因此我们只需要从一个或者几个 $(s, a)$ 出发就能访问到其他所有的 $(s, a)$ ，这样我们就可以去掉 Exploring Starts 这个条件了。

soft policy 我们是用什么来表示呢？这里我们用 $ε - G ree d$ policy ，其数学表达式如下：

强化学习：蒙特卡洛方法(MC)
在任意一个状态 $s$ 都有一个greedy action (所对应的最大的 $q_π(s,a^*)$ )，这时候的 $ε - g ree d y$ 就会给这个greedy action 一定的选择概率。选择 greedy action 的概率始终比其它的任何一个action 的概率都是要大的。

使用 $ε - g ree d y$ 的原因是他能够去平衡 exploitation 和 exploration ，即平衡充分利用数据与探索。当 $ε = 0$ 时，算法就会变得少探索，数据利用较充分；当 $ε = 1$ 时，它成为一个均匀分布，探索较多，而数据利用较低。

现在，我们来看一下 $ε - g ree d y$ 与 MC-based RL 算法是怎么结合的。在 MC Basic 和 MC Exploring Starts 这两个算法中，策略更新的方法是求出每个行为对应的 $q_{πk}(s,a)$ ，并在所有可能的策略当中去选择最大的 $q_{πk}(s,a)$ 对应的 action 作为新的策略，如下图：