当前位置：首页 > news >正文

强化学习-蒙特卡洛方法

news 来源：原创 2025/8/5 20:55:45

强化学习-数学理论

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

文章目录

强化学习-数学理论
一、蒙特卡洛方法理论(Monte Carlo, MC)
二、MC Basic
- 2.1 算法拆解
- 2.2 MC Basic算法
三、MC Exploring Starts
- 3.1 算法拆解
- - 3.1.1 高效利用数据
  - 3.1.2 高效更新策略
- 3.2 MC Exploring Starts算法
- 3.3 为什么必须要有exploring starts这个条件呢？
四、MC Epsilon-Greedly
- 4.1 soft policy理论
- 4.2 $\varepsilon$ -greedy policy（soft policy的一种）
- 4.3 MC Epsilon-Greedly算法
- - 4.3.1 如何将 $\varepsilon$ -greedy policy引入MC Basic？
  - 4.3.2 MC Epsilon-Greedly算法伪代码
总结
- 内容小结
- 参考资料

一、蒙特卡洛方法理论(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\times0.5 + (-1)\times0.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}{\overset{N}\Sigma}x_j$ 。这个思想就是 Monte Carlo estimation。

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

二、MC Basic

2.1 算法拆解

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

policy iteration算法有如下两部分：

$\begin{cases} policy\ evaluation:\ v_{\pi_k}=r_{\pi_k}+ \gamma P_{\pi_k} v_{\pi_k}\\ value\ improvement:\ \pi_{k+1}=argmax_\pi(r_\pi+\gamma P_\pi v_k) \end{cases}$

policy improvement的elementwise form如下：

$\begin{aligned} \pi_{k+1}(s)=\underset{\pi}{argmax}\underset{a}\Sigma\pi(a|s)\underbrace{[\underset{r}\Sigma p(r|s,a)r+\gamma\underset{s'}\Sigma p(s'|s,a)\textcolor{red}{v_k(s')}]}_{\textcolor{red}{q_{\pi_k}(s,a)}}, \quad s\in S \end{aligned}$
算法的关键在于如何计算 $\textcolor{red}{q_{\pi_k}(s,a)}$ !

同样求解 $\textcolor{red}{q_k(s,a)}$ 有如下两种方式：

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

如何基于数据去求解 $\textcolor{red}{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)\}$ ，那么根据Monte Carlo estimation思想我们可以得到：
$q_k(s,a) = \mathbb E[G_t|S_t=a,A_t=a] \approx\frac{1}{N}\underset{i=1}{\overset{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\overset{a_2}\rightarrow s_2\overset{a_4}\rightarrow s_1\overset{a_2}\rightarrow s_2\overset{a_3}\rightarrow s_5\overset{a_1}\rightarrow ...$
这里引入一个新的概念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 $\varepsilon$ -greedy policy（soft policy的一种）

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

4.3 MC Epsilon-Greedly算法

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

先前，MC Basic和MC Exploring Starts算法在解决policy improvement时，计算公式如下：
$\pi_{k+1}(s)=\underset{\pi \in \Pi}{argmax}\underset{a}\Sigma\pi(a|s)q_{\pi_k}(s,a)$
这里的 $\Pi$ 代表了所有可能的policy。最大策略计算方式如下：
$\pi(a|s) = \begin{cases}1，&a=a_k^*，\\ 0, &a \neq a_k^*， \end{cases}$
这里 $a_k^*=argmax_a q_{\pi_k}(s,a)$ .

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

$\pi(a|s) = \begin{cases}1-\frac{|\mathcal A(s)|-1}{|\mathcal A(s)|}\varepsilon, &a=a_k^* \\ \frac{1}{|\mathcal A(s)|}\varepsilon, &a\neq a_k^* \end{cases}$

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。

参考资料

蒙特卡洛方法视频版