RL（五）蒙特卡罗算法求解强化学习

目录

• 1、蒙特卡罗算法
• 2、为什么要使用蒙特卡罗算法
• 3、蒙特卡罗法求解强化学习预测问题
• 4、蒙特卡罗法求解强化学习控制问题
• 4.1、固定策略法
• 4.2、非固定策略法
• 5、总结

1、蒙特卡罗算法

在用蒙特卡罗算法解决问题之前，我们首先要知道蒙特卡罗算法的大概内容是什么。其基本思想是：

当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。它是一种通过采样近似求解问题的方法

2、为什么要使用蒙特卡罗算法

前面讲的主要内容是整个问题可以转换成一个马尔科夫决策过程(MDP)，MDP是通过5元组：来做决策的。对于这种已知模型的情况，也就是知道了这个5元组，我们可以容易获得奖赏最大化。但是，在现实世界中，我们无法同时知道这个5元组。比如P，状态转移概率就很难知道，P不知道，我们就无法使用bellman方程来求解V和Q值。但是我们依然要去解决这个问题，所以怎么办呢?怎样转化为一个MDP的形式呢？

一个想法是，虽然我不知道状态转移概率P，但是这个概率是真实存在的。我们可以直接去尝试，不断采样，然后会得到奖赏，通过奖赏来评估值函数。这个想法与蒙特卡罗方法的思想是一致的。我们可以尝试很多次，最后估计的V值就会很接近真实的V值了。

蒙特卡罗法通过采样若干经历完整的状态序列(episode)来估计状态的真实价值。所谓的经历完整，就是这个序列必须是达到终点的。比如是否成功种出西瓜，驾车问题成功到达终点或者失败。有了很多组这样经历完整的状态序列，我们就可以来近似的估计状态价值，从而求出预测问题和控制问题。可以用如下的图来理解状态序列(episode):



episode就是经历，每条episode就是一条从起始状态到结束状态的经历。例如在走迷宫，一条episode就是从你开始进入迷宫，到最后走出迷宫的路径。

从特卡罗法法的特点来说，一是和动态规划比，它不需要依赖于模型状态转化概率。二是它从经历过的完整序列学习，完整的经历越多，学习效果越好。

3、蒙特卡罗法求解强化学习预测问题

首先假定有一个定策略π的完整有T个状态的状态序列如下：



回顾之前的价值函数$v_{\pi }\mathrm{（}s\mathrm{）}$vπ​（s）：



可以看出每个状态的价值函数等于所有该状态收获的期望，同时这个收获是通过后续的奖励与对应的衰减乘积求和得到。那么对于蒙特卡罗法来说，如果要求某一个状态的状态价值，只需要求出所有的完整序列中该状态出现时候的收获再取平均值即可近似求解，也就是：



其实通俗理解就是求平均值。

但是这样算也会出现一些问题，比如，如果一个完整的序列中某个状态出现多次，我们怎么去算它的平均值呢？这里有两种解决办法：

（1）：首次访问(first visit)。即我们只把一个完整状态中第一次出现的状态值对应的收获值纳入到平均值的计算中。如下图所示：



（2）：每次访问(every visit)。另一种是针对一个状态序列中每次出现的该状态，都计算对应的收获值并纳入到收获平均值的计算中。如下图所示：

两种方法相比较可以发现：二种方法比第一种的计算量要大一些，但是在完整的经历样本序列少的场景下会比第一种方法适用。

还有一个问题就是计算平均值的时候，我们是否必须保存所有该状态的收获值之和最后取平均。这样算原理上是可以的，但是就是比较占空间。一个较好的方法是在迭代计算收获均值，即每次保存上一轮迭代得到的收获均值与次数，当计算得到当前轮的收获时，即可计算当前轮收获均值和次数。通过下面的公式就很容易理解这个过程：



这样上面的状态价值公式就可以改写成：



这样我们无论数据量是多还是少，算法需要的内存基本是固定的 。

4、蒙特卡罗法求解强化学习控制问题

在控制问题中，最重要的就是去改进当前策略，即该怎样去选择哪些动作。在蒙特卡罗求解控制问题中需要解决的也是找到一个方法来选择不同的策略去改进当前策略。目前主要有两种不同的动作选择方式，即固定策略（On-policy）和离线策略（Off-policy）方法。

（1）固定策略法：固定策略的 思想是个体已经有一个策略，并且基于该策略进行采样，以得到的状态序列(episode）来更新函数。之后采用策略评估和策略改进对给定策略进行迭代，以获得最优策略。因为需要优化的策略基于当前给定的策略，因此也叫做固定性策略。固定算法又可以分为起点探索算法和非起点探索算法。

（2）非固定性策略：非固定性有两个策略，一个策略负责向另一个策略学习，从它那里进行采样。这里所说的另一个策略可以使实现学习到的策略，或者人为提前制定的一些较为成熟的策略方法。理解就是，在自身策略形成的价值函数基础上观察别的策略所产生的行为，以此达到学习的目的。因为优化的策略不完全基于当前的策略，所以也叫非固定策略。