引入蒙特卡洛方法例子

   以抛硬币为例,将结果(正面朝上或反面朝上)表示为作为随机变量 XXX ,如果正面朝上则 X = + 1X=+1X=+1 ,如果反面朝上,则 X = − 1X=-1X=1,现在要计算 E [ X ]E[X]E[X]
  我们通常很容易想到直接用定义来计算,因为我们知道正面朝上和反面朝上的概率都是为 0.5 ,显然我们根据模型知道的结果,因此我们把这种方法称为 基于模型 的计算,如下图。

  但是,我们通常是不知道模型参数的,那么我们能不能在不知道模型参数的情况下去计算呢?答案是肯定的。以抛硬币为例,可以抛硬币很多次,然后将结果求平均,这就是蒙特卡洛的思想。

蒙特卡洛方法:基础算法

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

   在策略迭代中, q π k( s , a )q_{πk}(s,a)qπk(s,a) 是依赖模型来计算的,那么还有其他不依赖于模型的方法吗?用 q π k( s , a )q_{πk}(s,a)qπk(s,a) 定义计算,即通过大量采样 g ( s , a )g(s,a)g(s,a) 来计算。

  我们来看一下这个算法的伪代码:

MC Basic 算法基本介绍

  policy iteration 算法怎么转变成为 model-free 呢?我们知道 policy iteration 有策略评估和策略提升两步,然后 policy improvement 针对每一个状态 sss 展开得到如下式子,我们可以很容易知道这里边非常核心的一个量就是这个 q π k( s , a )q_{πk}(s,a)qπk(s,a)

 我们要计算 q π k( s , a )q_{πk}(s,a)qπk(s,a) 有两种方法,一种是依赖与模型的,就是 value iteration 算法所用的;另一种就是不依赖与模型的,而是根据 action value 最原始的定义,这就是蒙特卡洛算法的核心。

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

实例:MC Basic 算法

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


 如上图所示,给出的策略并不是最好的,现在我们使用 MC Basic 算法找到最优策略。MC Basic 算法与 policy iteration 一样分为 策略评估策略优化 两步。我们很容易知道上例共有 454545 ( s , a )(s,a)(s,a) , 9 s t a t e sstatesstates × 5 a c t i o n sactionsactions ,现在我们以 s1 s_1s1 的 5 个 a c t i o nactionaction 为例进行讲解。

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

步骤2:策略优化

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

MC Exploring Starts 算法

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

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

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


这样我们就可以同时得到在当前的 episode 中其他 状态-动作 的 qπ q_πqπ ,这其中也有两种方法,first-visit 和 every-visit 。first-visit 是指若有重复的 状态-动作 出现,那么只用第一次出现的去计算 qπ q_πqπ ;every-visit 会对每次出现的的 状态-动作 都会去进行一次计算 qπ q_πqπ

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

综上,我们得到 MC Exploring Starts 算法 的伪代码,如下:

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

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

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

   soft policy 我们是用什么来表示呢?这里我们用 ε − G r e e dε-GreedεGreed policy ,其数学表达式如下:


在任意一个状态 sss 都有一个greedy action (所对应的 最大的 qπ( s , a∗)q_π(s,a^*)qπ(s,a)),这时候的 ε − g r e e d yε -greedyεgreedy 就会给这个greedy action 一定的选择概率。选择 greedy action 的概率始终比其它的任何一个action 的概率都是要大的。

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

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

   ε − g r e e d yε -greedyεgreedy 并不是在所有可能的策略当中去找,而是在 ∏ε ∏_εε 中找,如下图:


其伪代码如下: