强化学习-蒙特卡洛方法

强化学习-数学理论

1. 强化学习-基本概念
2. 强化学习-贝尔曼公式
3. 强化学习-贝尔曼最优公式
4. 强化学习-值迭代与策略迭代
5. 强化学习-蒙特卡洛方法

---

---

一、蒙特卡洛方法理论(Monte Carlo, MC)

  上一篇博客介绍的是model-base的方法，本篇博客开始介绍model-free的方法，model-free的核心思想是基于数据来估计出一个模型。
  如何在没有模型的情况下去进行估计，有一个重要的思想：Monte Carlo estimation。下面以抛硬币的例子为大家讲解该思想。

假设我们正在进行抛硬币游戏，将其结果用$X$来表示，结果是正面时$X=1$;结果是反面时$X=-1$，我们的目的是去求解$\mathbb{E}[X]$，有如下两种方法：

方法一：model-base
假设我们知道有一个概率模型，$p(X=1)=0.5,p(X=-1)=0.5$，那么$\mathbb{E}[X]=\underset{x}{\Sigma }xp(x)=1\times 0.5+(-1)\times 0.5=0$，然而事实上我们可能没有办法获取这么精确的概率模型。
方法二：model-free（Monte Carlo estimation）
投掷硬币很多次（做多次试验）得到很多采样结果，把所有的采样结果求平均。具体如下：假如做了N次实验，这N次实验的结果是${x_1,x_2,x_3,…,x_N}$，把结果相加再除于N得到 $\overline{\text{x}}$，当N足够大时 $\overline{\text{x}}$ 近似等于$\mathbb{E}[X]$，等式为：$\mathbb{E}[X]\approx \overline{\text{x}}=\frac{1}{N}\underset{j=1}{\stackrel{N}{\Sigma }}{x}_j$。这个思想就是 Monte Carlo estimation。

  Monte Carlo estimation思想的数学理论支撑如下图所示，相关证明这里不再给出，感兴趣的朋友可以查阅相关参考资料。

---

二、MC Basic

2.1 算法拆解

  上一篇博客我们讲过policy iteration这个算法，在上一篇中它是模型确定的，本篇的核心是如何将policy iteration转变成model-free的方法。

policy iteration算法有如下两部分：

$$\{\begin{array}{l}policyevaluation:v_{{\pi }_k}=r_{{\pi }_k}+\gamma P_{{\pi }_k}{v}_{{\pi }_k}\\ valueimprovement:{\pi }_{k+1}=argma{x}_{\pi }(r_{\pi }+\gamma P_{\pi }{v}_k)\end{array}$$

policy improvement的elementwise form如下：

$$\begin{array}{r}{\pi }_{k+1}(s)=\underset{\pi }{\mathrm{argmax}}\underset{a}{\Sigma }\pi (a|s)\underset{q_{{\pi }_k}(s,a)}{\underbrace{[\underset{r}{\Sigma }p(r|s,a)r+\gamma \underset{s^{\prime }}{\Sigma }p(s^{\prime }|s,a)v_k(s^{\prime })]}},s\in S\end{array}$$
算法的关键在于如何计算 $q_{{\pi }_k}(s,a)$!

同样求解$q_k(s,a)$有如下两种方式：

方案一：model-base
$$q_{{\pi }_k}(s,a)=\underset{r}{\Sigma }p(r|s,a)r+\gamma \underset{s^{\prime }}{p}(s^{\prime }|s,a)v_{{\pi }_k}(s^{\prime })$$
方案二：model-free【本篇博客的方法】
$$q_{{\pi }_k}(s,a)=\mathbb{E}[G_t|S_t=a,A_t=a]$$

如何基于数据去求解$q_k(s,a)$？答案：采用章节一中提到的 Monte Carlo estimation，具体步骤如下所示：

首先我们从任意的一个s和a的一个组合出发，然后根据当前的策略得到一个episode并计算出该episode对应的discounted return 为$g(s,a)$，这里的$g(s,a)$是$G_t$的一个采样。假设我们有很多这样的词啊样集合： { g ( j ) ( s , a ) } \{g^{(j)}(s,a)\} {g(j)(s,a)}，那么根据Monte Carlo estimation思想我们可以得到：
$$q_k(s,a)=\mathbb{E}[G_t|S_t=a,A_t=a]\approx \frac{1}{N}\underset{i=1}{\stackrel{N}{\Sigma }}{g}^i(s,a)$$

总之，没有数据时得有模型，没有模型时得有数据！！！

2.2 MC Basic算法

  给定一个初始策略${\pi }_0$，这个策略可能是不好的，慢慢地对其进行改进，然后在第k个iteration它包含两个步骤：

1️⃣ policy evaluation：计算出所有$(s,a)$对应的$q_{{\pi }_k}$，其计算方法是：从$(s,a)$出发得到很多的episode，求得episode的return并求平均；
2️⃣ policy improvement：在步骤一中我们得到了$q_{{\pi }_k}$，这个步骤主要求解一个最优化问题得到一个新的策略。

  伪代码如下图所示：

---

三、MC Exploring Starts

3.1 算法拆解

  该算法是MC Basic算法的一个推广，使得MC Basic算法更加高效，下面通过一个例子为大家讲解。

3.1.1 高效利用数据

在一个网格世界里，假如有一个策略$\pi$，我们可以得到一个episode，如下所示：
$$s_1\stackrel{a_2}{\to }{s}_2\stackrel{a_4}{\to }{s}_1\stackrel{a_2}{\to }{s}_2\stackrel{a_3}{\to }{s}_5\stackrel{a_1}{\to }...$$
这里引入一个新的概念visit，每出现一次state-action pair我们就认为有了一次访问。前面所讲到的MC Basic算法也叫Initial-visit method，即对于某个episode我们只考虑$(s_1,a_2)$，然后利用该episode剩下所得到的return来估计$(s_1,a_2)$的action value。因此，我们可以清楚的知道MC Basic算法的问题在于它没有充分利用这个episode，因为里面有很多的数据被浪费掉了。
如下图所示，我们可以利用episode所得的return去估计前一个$q_{\pi }(s_2,a_4)$，如此依赖就可以充分利用该episode中的数据。这里也有两种方法：

• first-visit method：如下图所示，在第三次的时候又出现了一次$(s_1,a_2)$，该方法的意思是：只要出现过一次的state-action pair 后面再次出现就不在进行估计了。
• every-visit method：与上面的方案截然相反，出现第二次时就用第二次后面的📄进行估计，出现第三次时就用第三次后面的值进行估计，如此类推。

3.1.2 高效更新策略

  上面所提到的方案是如何让数据利用更加高效，下面将为大家讲解如何让策略更新的更高效，这里也有两种方案。

第一种【原始法】：MC Basic算法在进行策略更新的时候，其原理是：收集从 state-action pair 开始的所有episode，然后使用return的平均值来近似action value。原始方案的缺点在于“要等”，要等所有的episode，这就造成了性能的低效。
第二种【改进法】：针对上述方案的缺点，该方法的核心是：我得了一个episode时就用这个episode的return立刻去估计action value，然后就直接开始改进策略，后面都采用这样及时的方法从而提高性能。该方案的支撑理论见：truncated policy iteration

3.2 MC Exploring Starts算法

  MC Exploring Starts方法的伪代码如下：

3.3 为什么必须要有exploring starts这个条件呢？

• exploring代表：指的是从每一个$(s,a)$出发都要有episode，只有这样才能用后面生成的这些return去计算$q_{\pi }(s,a)$，假设有一个state action没有被访问到，就无法确保所选的action是最优的了。
• starts代表：要访问每一个$(s,a)$从它后面能够生成reward的这些数据，有两种方案：1） 从$(s,a)$开始一个episode就是start，2）visit方法，即我从其他状态出发，得到的episode经过了$(s,a)$这个状态，但目前来说visit这个方法无法确保一定能够经过剩下的这些$(s,a)$。
• 理论上，只有对每个状态的每个 action value 都进行了很好的探索，我们才能正确地选择最优 action。否则，如果未探索某个操作，则此操作可能恰好是最佳操作，因此会错过。在实践中，exploring starts很难实现。对于许多应用程序，尤其是那些涉及与环境物理交互的应用程序，很难从每个state-action pair 对开始收集episode。

---

四、MC Epsilon-Greedly

  MC Epsilon-Greedly算法通过soft policy的方式对MC Exploring Starts算法进行改进，从而拿掉MC Exploring Starts算法中的硬性条件exploring starts。

4.1 soft policy理论

  前几章提到的greedy policy是deterministic的，而soft policy是stochastic的。如果我从一个state-action pair如$(s,a)$出发，假设后面的episode特别特别长，因为它是探索性的，因此就能够确保任何一个s和a被这个episode访问到。基于这个理论，我们就可以去掉exploring starts这个条件了。

4.2 $\epsilon$-greedy policy（soft policy的一种）

$$\pi (a|s)=\{\begin{array}{ll}1-\frac{\epsilon }{|\mathcal{A}(s)|}(|\mathcal{A}(s)|-1),& forthegreedyaction\\ \frac{\epsilon }{|\mathcal{A}(s)|},& fortheother|\mathcal{A}(s)|-1action\end{array}$$
其中$\epsilon \in [0,1]$，$|\mathcal{A}(s)|$为状态 s 的动作数量。$\epsilon$-greedy policy可以平衡 exploitation 和 exploration。从上式也可得出，当$\epsilon =0$时, policy 就是 greedy的，充分利用性强，探索性弱; 当$\epsilon =1$时, 此时策略就是随机的且其探索性就很强。

4.3 MC Epsilon-Greedly算法

4.3.1 如何将$\epsilon$-greedy policy引入MC Basic？

先前，MC Basic和MC Exploring Starts算法在解决policy improvement时，计算公式如下：
$${\pi }_{k+1}(s)=\underset{\pi \in \Pi }{\mathrm{argmax}}\underset{a}{\Sigma }\pi (a|s)q_{{\pi }_k}(s,a)$$
这里的$\Pi$代表了所有可能的policy。最大策略计算方式如下：
$$\pi (a|s)=\{\begin{array}{ll}1，& a=a_k^{\ast }，\\ 0,& a\ne a_k^{\ast }，\end{array}$$
这里$a_k^{\ast }=argma{x}_a{q}_{{\pi }_k}(s,a)$.

现在，只需要把原来的$\pi \in \Pi$用$\epsilon$-greedy policy替代即可，即$\pi \in {\Pi }_{\epsilon }$，具体公式如下所示：
$${\pi }_{k+1}(s)=\underset{\pi \in {\Pi }_{\epsilon }}{\mathrm{argmax}}\underset{a}{\Sigma }\pi (a|s)q_{{\pi }_k}(s,a)$$
这里的$\Pi$只包含一部分的策略，最大策略计算如下：

$$\pi (a|s)=\{\begin{array}{ll}1-\frac{|\mathcal{A}(s)|-1}{|\mathcal{A}(s)|}\epsilon ,& a=a_k^{\ast }\\ \frac{1}{|\mathcal{A}(s)|}\epsilon ,& a\ne a_k^{\ast }\end{array}$$

4.3.2 MC Epsilon-Greedly算法伪代码

---

总结

内容小结

• Monte Carlo estimation：将大量的数据采样求平均进行估计；
• MC Basic：基于Monte Carlo estimation思想，将policy iteration算法从model-base的方法转为model-free的方法；
• MC Exploring Starts：是对MC Basic算法的优化，从数据和策略两个方面进行优化；
• MC Epsilon-Greedly：通过soft policy的方式对MC Exploring Starts算法进行改进，拿掉了硬性条件exploring starts。

参考资料

1. 蒙特卡洛方法视频版