【强化学习的数学原理】第05课-蒙特卡洛方法-笔记

学习资料：bilibili 西湖大学赵世钰老师的【强化学习的数学原理】课程。链接：强化学习的数学原理 西湖大学 赵世钰

一、通过例子介绍蒙特卡洛

之前提到的值迭代算法、策略迭代算法都属于model-based reinforcement learning，而蒙特卡洛方法属于model-free reinforcement learning。对于初学者来说，最难以理解的是，如何在没有模型的情况下去估计一些变量。其中有一个重要的思想就是 Monte Carlo Estimation。下面举一个例子来简要介绍 Monte Carlo Estimation。

这是一个抛硬币的例子。若正面朝上，则X=1；若反面朝上，则X=-1，目标是计算期望 E(X)。

方法一是利用 model-based 的方法来解决该问题，列出概率分布模型，然后根据模型计算期望。不过，对于现实中的大部分问题，我们无法直接这样列出概率分布模型。
`
方法二是利用 model-free 的方法，其基本思想是多次投掷硬币，采样很多次，然后对所有的采样结果求平均。用这个平均数来近似期望。

那么，这种蒙特卡洛估计是准确的吗？当采样次数N比较小的时候，该估计是不准确的；当N逐渐变大，估计变得越来越准确。（有大数定律作为理论支撑）

通过上述例子，我们可以了解蒙特卡洛的基本思想。如下图所示：

二、 MC Basic 算法介绍

MC Basic 算法是基于policy iteration策略迭代算法的，但策略迭代算法是mode-based reinforcement learning，MC Basic 算法是 model-free reinforcement learning。理解MC Basic 算法的关键是，理解如何把mode-based reinforcement learning转换成 model-free reinforcement learning。

下图简要回顾了以下 policy iteration 算法。分为policy evaluation 和 policy improvement 两部分。在 policy evaluation 中根据给定的策略计算state value，在 policy improvement 中根据刚刚算好的 state value 来更新策略，在这一步中，最重要的就是计算 $q_{{\pi }_k}(s,a)$，根据算出来的结果来选择动作 $a$ 。

有两种方法来计算 $q_{{\pi }_k}(s,a)$。
第一种是基于模型的方法，根据公式来计算。（如下图 expression 1 所示）
第二种是不需要模型的方法，回到了 $q_{{\pi }_k}(s,a)$ 最原始的定义。从状态s出发，采取动作a，得到一个return，多次采样取平均值，用平均值来近似 $q_{{\pi }_k}(s,a)$ 。

下面将详细讲解如何使用蒙特卡洛估计来计算 $q_{{\pi }_k}(s,a)$ 。从状态s出发，采取动作a，产生一个episode，得到一个return $g(s,a)$。多次进行采样，就会得到一个集合 $g^{(j)}(s,a)$ ，对集合中的所有奖励取平均值，用平均值来近似 $q_{{\pi }_k}(s,a)$。总的来说，当没有模型的时候，可以依赖于数据（data/sample/experience）来模拟模型。

下面是 MC Basic 算法的具体描述。该算法和 policy iteration 算法几乎一致，唯一的区别就是 policy iteration 算法用基于模型的方法来计算 $q_{{\pi }_k}(s,a)$ ，而 MC Basic 算法用蒙特卡洛估计来计算 $q_{{\pi }_k}(s,a)$ 。

下面是该算法的伪代码。

Highlights：
（1）MC Basic 是 policy iteration 的一个变形。
（2）MC Basic 算法虽然展示了 MC-based model-free RL 的核心，但是该算法的效率非常低。
（3）为什么MC Basic 算法估计的是 action value，而不是 state value 呢？因为 state value 是不能用来提升策略的，所以我们必须要计算 action value。那如果先估计 state value ，再由 state value 算出 action value 行不行呢？实际上也是不行的，因为由 state value 算出 action value 需要依赖下面这个公式，而下面这个公式又是一个 model based 的公式。

（4）因为policy iteration是收敛的，而 MC Basic 和 policy iteration 是几乎一致的，所以 MC Basic 也是收敛的。

三、MC Basic 算法例子

例1：MC Baxic算法

下面通过一个具体的例子来阐述MC Baxic算法。在这个例子中，有一个初始策略 ${\pi }_0$ ， 这个策略在大多数状态下都是正确的，但是在状态 $s_1$ 和状态 $s_3$ 时的策略不太好，下面对这两个状态的策略进行优化。

MC Basic 算法和policy iteration一样，分为policy evaluation和policy improvement两步。在policy evaluation中，需要求 $q_{{\pi }_k}(s,a)$，也就是说要从每个状态动作对(s,a)出发，找到每一个(s,a)的 $q_{{\pi }_k}(s,a)$。在这个例子里，有 9 state × 5 action = 45 个状态动作对。假设从每一个（s，a）出发都要有n条轨迹，那一共有 45×n 条轨迹。

以状态动作对 $(s_1,a)$ 为例。首先做policy evaluation。这个grid world中，policy 和环境都是deterministic的，所以对 $(s_1,a)$ 采样n条轨迹，得到的轨迹都是一样的，因此只要采样一条轨迹就好了。

从 $s_1$ 出发， 采取动作 $a_1$，回到状态 $s_1$ ，又采取动作 $a_1$……如此循环往复，生成了一条关于状态动作对$(s_1,a_1)$ 的轨迹。 随后求出这条轨迹对应的return。其他状态动作对的return求法也类似。

policy evaluation 之后，需要进行 policy improvement。方法和之前类似，对一个状态s，找出 $q_{{\pi }_k}(s,a)$ 中最大的那个作为新的策略即可。 policy improvement 后可以发现，此时 $s_1$ 的策略已经达到最优了。

例2：episode length对算法的影响

episode length 肯定不可能无限大，但 episode length 设置为多少比较合适呢？
当episode length=1时，只有紧挨着target area的几个格子的value是正数，其对应的策略也是正确的。其他格子的value都是0，策略也不好。
当episode length=2时，第五行第二个格子、第四个格子对应的策略也都变成了正确的。因为从这两个格子出发， 刚好走两步可以到达目标。
当episode length=3时，对于恰好走三步能够到达目标的格子，其策略也变成了最优的。
当episode length=n时，对于恰好走n步能够到达目标的格子，其策略也变成了最优的。
当episode length=15时，对于恰好走15步能够到达目标的格子，其策略也变成了最优的。此时所有的格子的策略都变成了最优的。
当继续增加episode length时，策略已经基本上不会怎么变化了，变化的主要是state value。当episode length 变为无穷大的时候，state value基本上和optimal state value接近了。

Findings：
（1）当episode length比较短的时候，只有离目标近的状态才能在短的步骤内找到正确的策略。
（2）当episode length不断增加时，离目标越来越远的状态也慢慢地达到了正确策略。
（3）episode length必须要足够长，但也不必是无限长。

四、MC Exploring Starts 算法

之前讲的 MC Basic 算法的缺陷就是效率比较低。MC Exploring Starts 是对 MC Basic 的改进。
先介绍一个概念 visit，visit 在一个episode中出现的一个状态-动作对，如下图episode中的 $(s_1,a_2)$，$(s_2,a_4)$，$(s_1,a_2)$，$(s_2,a_3)$ 等等。在 MCB 中，使用的是 Initial-visit method。意思是，对于下面这个episode，只考虑 $(s_1,a_2)$，然后用剩下的return，来估计 $(s_1,a_2)$ 的action value。

但是按照上面的计算方法也会存在问题，就是这个episode的价值没有被充分利用。这个episode除了访问 $(s_1,a_2)$，还访问了 $(s_2,a_4)$，$(s_1,a_2)$，$(s_2,a_3)$ 等等。其实也可以把这个episode从$(s_2,a_4)$开始，当做一个新的episode，估计$(s_2,a_4)$的return。下一个$(s_1,a_2)$开头的episode可以用来估计$(s_1,a_2)$的return。下一个$(s_2,a_3)$开头的episode可以用来估计$(s_2,a_3)$的return。这样就可以把有限的数据利用得非常充分。

这里面包括两种方法：first-visit 和 every-visit。在下图中的original episode中，第一次访问了 $(s_1,a_2)$，第三次还访问了 $(s_1,a_2)$。对于every-visit策略，在第一次访问 $(s_1,a_2)$ 时，用第一次访问的 $(s_1,a_2)$ 来估计其return，在第二次访问 $(s_1,a_2)$时，会用第二次访问的 $(s_1,a_2)$ 来再一次估计 $(s_1,a_2)$ 的return。但是对于first-visit策略，只是用第一次出现的$(s_1,a_2)$ 来估计其 return，后面再出现$(s_1,a_2)$ 时就不再进行估计了。

另一个要考虑的方面是：何时更新策略。有两种方法。

第一种方法：在策略评估过程中，从状态-动作对出发，收集完所有的episode，计算其均值，再用来更新策略。这正是MC Basic方法所使用的策略。该策略的问题时，agent需要等很长时间，直到所有的episode都被收集完毕后再更新策略。

第二种方法：在策略评估过程中，从状态-动作对出发，只收集一个episode，立刻就估计action value，随即进行策略更新。这样会提升效率。

但是，第二种方法每次只收集一个episode，会不会导致结果不准确呢？答案是不会。试想policy iteration策略和value iteration策略的差异，policy iteration需要经过无穷多次迭代，而value iteration每次仅需进行一次迭代即可，两种方法最终都能得到准确的结果。

Generalized policy iteration： Generalized policy iteration是一种架构，不是一种具体的算法。It refers to the general idea or framework of switching between policy-evaluation and policy-improvement processes.

下图是 MC Exploring Starts 的伪代码。主要分成两部分： Episode generation 和 Policy evaluation 、policy improvement。

在 episode generation 阶段，生成一个 episode $T:s_0,a_0,r_1,...,s_{T-1},a_{T-1},r_T$。然后在policy evaluation 和policy improvement 阶段，把episode 倒过来（这样计算效率更高），逐一计算状态-动作对的return。

为什么要exploring starts 这个条件呢？
exploring：从每一个 $(s,a)$ 出发，都要有一个episode，这样才能生成return，计算 $q(s,a)$。如果恰好有一个状态-动作对没有被访问到，那可能就会漏掉这个action，但这个action也有可能是最优的。所以说要确保每一个 $(s,a)$ 都要被访问到。

starts：要访问每一个 $(s,a)$ ，生成return这些数据，有两种方法。第一种是从 $(s,a)$ 出发构建一个episode；第二种是从其他的状态-动作对开始，经过这个 $(s,a)$，来估计 $(s,a)$的 return。但是第二种方法没法保证一定能访问到 $(s,a)$。所以可以用第一种方法，虽然比较笨，但是一定能算出 $(s,a)$的return。

五、MC Epsilon-Greedy 算法介绍

刚刚讲了 MC exploring starts 算法，但这个算法在实际中很难实现。在这一节中，我们尝试去掉exploring starts这个条件，让算法更易于实现。

方法是引入soft policy。简而言之，soft policy 是指对每一个action都有可能去做选择。之前提到过policy分为两种，第一种是deterministic policy（如 greedy policy），第二种是 stochastic policy（如：soft policy）。soft policy 是一种随机的策略。

为什么要引入 soft policy？ 如果从某一个（s，a）出发，生成的 episode 特别特别长，因为 soft policy 是探索性、随机性的，那这个 episode 如果足够长，就能够保证任何一个（s，a）都能出现在这个 episode 里面。那就可以克服 MC exploring starts 算法的缺陷了。

使用什么样的 soft policy？ 使用 $ϵ$-greedy policies。

什么是 $ϵ$-greedy policies？ 以往在策略提升的过程中，对于 $q(s,a)$ 最大的那个动作，总是赋予这个动作概率1，对其他动作赋予概率0。但在 $ϵ$-greedy policies 中，不再给$q(s,a)$ 最大的那个动作赋予概率1，也不再给其他动作赋予概率0，而是给每个动作都赋予一定的概率，具体概率大小如下图所示。其中，$ϵ$ 是 [0,1] 之间的一个数，$|A(s)|$ 是在状态s下，可能的动作数量。（这里可以给$ϵ$ 和 $|A(s)|$ 赋一个值，具象化地感受一下）$ϵ$-greedy policies 有一个性质，就是选择 greedy action 的概率一定会比选择其他动作的概率大。

为什么用 $ϵ$-greedy ？ 因为这可以达到 **exploitation 和 exploration 的平衡。 exploitation 指充分利用当前的信息， exploration 是探索未知的信息。当 $ϵ=0$ 时，策略变成贪心的，这样探索性变弱，但充分利用了已有的信息；当 $ϵ=1$ 时，策略变成均匀分布，这样探索性会变强。

如何把 $ϵ$-greedy 和 MC-based RL algorithms结合在一起？ 以往的策略如下图所示，求出 $q_{{\pi }_k}(s,a)$ 之后，选择q值最大的动作作为下一个策略（即：直接把该动作的概率设置为1，把其他动作的概率设置为0）。

但在 $ϵ$-greedy 中，我们不这么做。算出 $q_{{\pi }_k}(s,a)$ 之后，我们把最大的概率仍然赋值给greedy action，但是会给其他所有action一个相同的、比较小的概率。这样我们就得到了 MC Epsilon-Greedy 算法，和 MC Exploring Starts 相比， MC Epsilon-Greedy 算法使用的是 greedy 的策略。通过使用 MC Epsilon-Greedy 算法，我们就不再需要expoloring starts 这个条件了，无需从每一个 $(s,a)$ 出发去生成 episode。

这是该算法的伪代码。它和 MC Exploring Starts 相比几乎一模一样，除了最后那个 $\pi (a|s_t)$ 的设置。另一个比较小的区别是，该算法使用了every-visit，而 MC Exploring Starts 使用了 first-visit，目的还是为了充分利用已有的数据，在一个（s, a）出现被访问多次的时候，多次计算其 return。

六、MC Epsilon-Greedy 算法例子

（1）一个单独的episode能访问所有的状态-动作对（s，a）吗？
当 $ϵ=1$时，策略是均匀分布，因为每个状态都有5种action，所以每个action都是0.2的概率。结果如下图所示。100 steps 时，会探索到一些state，1000 steps 时，会探索到更多state，10000步时，探索到更多 state，覆盖了所有的 action。图（d）表示探索100万步时，每一个（s，a）被访问到的次数，可以看到，此时虽然只有一个episode，但每一个 state-action pair 几乎都被访问了上千次。

当 $ϵ$ 比较小时，探索能力是比较弱的。结果如下图所示。100 steps 时，会探索到一些state，1000 steps 时，会探索到更多state，但还有很多状态没被探索到，在10000步时，会探索到更多 state，但最左下角那个格子里，向下的那个action没有被探索到。图（d）表示探索100万步时，每一个（s，a）被访问到的次数，可以看到，不同 state-action pair 被访问到的次数差异非常大，很多 state-action pair 都没怎么被访问到。但相比于greedy策略来说，还是有一定的探索能力。

（2）一个例子
在每次迭代中，使用 $ϵ$ greedy 策略，仅产生一个 episode，但这个 episode 包含了100万个 step。用这一个 episode 去更新所有的 state-action pair 的 $q(s,a)$。

下图展示了运行结果。（a）表示最初策略，此时在某一个状态s，选择不同动作的概率是相同的。（b）一次迭代后，产生了新的策略，这个策略相比于（a）好一些，但是还是不够好。（c）两次迭代后，产生了新的策略，这个策略相对更好一些，但还不是最优的，因为它还有可能进入到 forbidden area。总而言之， $ϵ$ greedy 策略通过其探索性避免了 exploring starts 的要求，但是同时也失去了最优性。

下图阐释了这个算法的优缺点。优点是：有更强的探索能力。缺点是：算法牺牲了最优性。所以说，可以设置一个相对小的 $ϵ$ 值，在尽量达到最优性的同时，又不失其探索性。

（3）$ϵ$ 不宜设置得过大
下图的每一个子图中，左边表示在给定$ϵ$ 下计算出来的最优策略，右边表示最优策略的情况下对应的state value。从下图也可以看出，$ϵ$ 越小，策略的最优性越强（策略的优劣可以通过state value判断）。所以说，$ϵ$ 不宜设置得过大。或者说可以在程序一开始的时候，设置一个比较大的$ϵ$ ，随着程序的运行，$ϵ$ 慢慢减小。

七、本节课summary