强化学习之蒙特卡洛法

首页摘要：

动态规划是基于模型的方法，一旦模型的状态转移概率 $P_{ss’}^{a}$ 无法获得时就无法求解。这个时候不基于模型的方法——蒙特卡洛法——可以利用采样来近似求得每个状态的价值期望，这种方法整体也可以分为策略评估(在特定的策略下每个状态价值的评估)和策略改进(确定每个状态价值后对策略进行提升)两部分。

为什么会出现蒙特卡洛法

在基于动态规划的定义中，给定状态集 $S$ 、动作集 $A$ 、状态概率转移矩阵 $P$ 、回报衰减因子 $\gamma$、以及策略集 $\pi$ 就能够通过基于贪婪策略的动态规划找出最优策略（尽管是局部最优解）。当我们没有办法对环境建模时就无法得知状态概率转移矩阵 $P$ ，也就没有办法利用动态规划来进行求解。

从定义上来说，例如求解状态价值函数的期望，表达式是这样的：

$$v_{\pi}(s)=\sum_{a \in A}\pi(a|s)(r_{t+1}+\gamma \sum_{s'\in S}P_{ss'}^{a}v_{\pi}(s'))$$

其中，$\pi(a|s)$ 是我们最后要得到的策略，$v_{\pi}(s’)$ 是最后得到最优策略后要确定的状态价值函数，换句话说这个期望公式实质上是要知道状态概率转移矩阵 $P$ 才能进行求解的，如果不知道这个状态概率转移矩阵 $P$ ，怎么来求状态价值函数的期望呢？根据蒙特卡洛采样的性质，大量样本的平均可以近似变量的期望，用所有采样得到的完整 $episold$ 状态价值平均就可以近似得到它的期望值。

蒙特卡洛法策略评估

对策略评估的手段是求出状态价值函数，首先假设在一个给定策略 $\pi$ 下长度为 $T$ 的完整的

中序列为：

$$S_{1},A_{1},r_{2},S_{2},A_{2},r_{3},...S_{t},A_{t},r_{t+1},...,S_{T},A_{T},r_{T+1}$$

那么，状态价值函数可以表示为：

$$\begin{split} v_{\pi}(s)&=E_{\pi}(r_{t+1}+\gamma r_{t+2}+ \gamma^{2}r_{t+3}+...+\gamma^{T-1}r_{t+T}|S_{t}=s )\\ &=E_{\pi}(G_{t}|S_{t}=s )\\ \end{split}$$

在该$episold$ 下特定状态$s$ 的回报即：

$$G_{t}=r_{t+1}+\gamma r_{t+2}+ \gamma^{2}r_{t+3}+...+\gamma^{T-1}r_{t+T}$$

那么在不同策略下每个$episold$ 可以得到出现特定状态的回报，蒙特卡洛对该状态下所有的回报取平均作为该状态价值的期望：

$$v(s)=average(G_{t})$$

在实际应用中，同样一个状态可能在一个完整的$episold$序列中重复出现，对于这种情况存在两种方法进行计算：

（1）只计算状态$s$ 在某个$episold$ 第一次出现的回报，称之为 $first \ visit$;

（2）把所有出现状态

的回报用来计算平均值。

如果做了$N$ 次采样，那么需要保存 $N$ 个数据来做平均，为了解决存储空间，一般会采用递进累加平均值的方法来处理，状态价值计算平均值可以改写成：

$$N(S_{t})=N(S_{t})+1\\ \begin{equation} \begin{split} v(S_{t})&=v(S_{t})+\frac{1}{N(S_{t})}(G_{t}-v(S_{t}))\\ &=v(S_{t})+\alpha (G_{t}-v(S_{t})) \end{split} \end{equation}$$

类比状态价值函数的求法，动作价值函数也可以同样得到：

$$q(S_{t},A_{t})=q(S_{t},A_{t})+\alpha (G_{t}-q(S_{t},A_{t}))$$

蒙特卡洛法策略改进

蒙特卡罗法策略改进的方式和动态规划类似，都是先对策略评估其状态价值函数，再根据状态价值函数改进策略。但是存在不同的地方就是采用的策略略有区别，蒙特卡洛采用的是$\epsilon -greedy$ 贪婪策略，而动态规划采用的是基本贪婪策略。具体而言，$\epsilon -greedy$ 贪婪策略是：

$$\pi(a|s) =\begin{cases} 1-\epsilon & a= \underset{a\in A}{argmax}\, q(s,a)\\ \frac{\epsilon}{m} & others \end{cases}$$

它表示的是使得动作价值最大的动作不一定会被选择，而是以较小的概率给其他$m$ 个动作留机会。这么做是因为蒙特卡洛法通过采样得到的状态进行最优求解不一定是实际最优解，需要留个机会给模型进行探索其它可能的方式。

蒙特卡洛法流程

最后总结一下蒙特卡洛法进行强化学习的总流程，这里给出在线版(on-policy)本的过程，离线(off-policy)版本的在后续介绍。在线和离线的区别我们在后续的文章里面会讲。同时这里我们用的是every-visit,即个状态序列中每次出现的相同状态，都会计算对应的收获值。

输入:状态集$S$ 、动作集 $A$ 、即时回报$r$ 、衰减因子$\gamma$ 、探索率$\epsilon$ ；

输出:最优的动作价值函数 $q^{\star}$ 、最优策略$\pi^{\star}$ ；

1.初始化所有的动作价值$q(s,a)=0$，状态次数$N(s,a)=0$ ，采样次数$k=0$，随机初始化一个策略$\pi$

2.$k=k+1$，基于策略$\pi$ 产生完整的$episold$ 序列：

$$S_{1},A_{1},r_{2},S_{2},A_{2},r_{3},...S_{t},A_{t},r_{t+1},...,S_{T},A_{T},r_{T+1}$$

3.对于序列出现的每一对$q(S_{t},A_{t})$ ，计算其收获$G_{t}$ ，更新其计数$N(S_{t})$ 及动作价值函数：

$$G_{t}=r_{t+1}+\gamma r_{t+2}+ \gamma^{2}r_{t+3}+...+\gamma^{T-1}r_{t+T}\\ N(S_{t})=N(S_{t})+1\\ q(S_{t},A_{t})=q(S_{t},A_{t})+\alpha (G_{t}-q(S_{t-1},A_{t-1}))" alt="G_{t}=r_{t+1}+\gamma r_{t+2}+ \gamma^{2}r_{t+3}+...+\gamma^{T-1}r_{t+T}$$

4.基于新计算出的动作价值，更新当前的$\epsilon -greedy$ 贪婪策略：

$$\pi(a|s) =\begin{cases} 1-\epsilon & a= \underset{a\in A}{argmax}\, q(s,a)\\ \frac{\epsilon}{m} & others \end{cases}$$

5.如果所有的$q(S_{t},A_{t})$ 收敛，则对应的所有$q(S_{t},A_{t})$ 即为最优的动作价值函数 $q^{\star}$ 。对应的策略 $\pi(a|s)$ 即为最优策略 。否则转到第2步。

结语

蒙特卡洛法解决了动态规划需要模型参数的问题，但是它存在的问题是需要完整的$episold$ 序列，实际应用中可能没有那么多的完整$episold$ 序列，时序差分方法就是为了解决这个方法而提出来的。