强化学习之蒙特卡罗法

滴！小李久违上线了~原来这周要写个年终总结的…上周比完赛 丧到现在似乎情绪还是不好就拖到下周吧…补一个强化学习的知识。
——————

蒙特卡罗

基本思想

蒙特卡罗方法又叫统计模拟方法，它使用随机数（或伪随机数）来解决计算的问题，是以概率为基础的方法。

简单的例子：
假设我们需要计算一个不规则图形的面积，那么图形的不规则程度和分析性计算（比如积分）的复杂程度是成正比的。采用蒙特卡罗方法是怎么计算的呢？
首先你把图形放到一个已知面积的方框内，然后假想你有一些豆子，把豆子均匀地朝这个方框内撒，之后数这个图形之中有多少颗豆子，再根据图形内外豆子的比例来计算面积。当你的豆子越小，撒的越多的时候，结果就越精确。

上述的思想是一种通过采样近似求解问题的方法，在强化学习里面的蒙特卡罗的采样思路也大体如此。下面来看一下在强化学习它如何采样？

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

区别比较

VS 强化学习的动态规划
在动态规划中，会假设智能体已经知道关于该环境的所有信息，即完全了解 MDP（马尔可夫决策过程），而不需要和环境互动后才知道。
所以智能体知道该环境是如何决定下一状态以及如何决定奖励的。动态规划所要解决的问题就是智能体知道了环境的所有信息后，如何利用这些信息找出最优策略。
然而，蒙特卡罗法，智能体是不知道环境的动态信息的，需要和环境进行一系列的互动后才了解。它不需要对环境有完整的知识，仅仅需要经验就可以求解最优策略，这些经验可以在线获得或者根据某种模拟机制获得。
故，准确的来说，动态规划可以是一种有模型的学习，而蒙特卡罗是基于采样的模型无关的学习。

蒙特卡罗法→预测问题

预测：状态值、预测值
智能体与环境进行一系列互动的过程中，会有一系列的状态，包括动作和奖励（反馈）。此处重点探讨阶段性任务，即智能体在时间 T 遇到最终状态时，互动结束。在任何阶段，智能体的目标都是最大化期望积累奖励。

在给定一个策略后，智能体如何估算该策略的状态值和动作值？有两种方式：
1.离线策略方法(Off-Policy Method)：
用一个策略进行评估，用另一个策略来与环境进行互动。
2.异同策略方法(On-Policy Method)：
智能体通过某个策略与环境进行互动，并计算该策略的值函数。

状态值
在每个阶段中，分别计算出现某一状态（一个阶段中只出现一次）后的（折扣）回报，最后基于所有阶段取均值。该算法将状态值定义为某一状态之后的预期回报。
如果在一个阶段中，一个状态出现多次，此时有两种处理方法：
1.对所有阶段中该状态的首次经历的回报取平均值
（first MC methods）
2.对所有阶段中该状态的所有经历之后的回报取平均值
（every-visit MC methods）
举个例子：这里，我们考虑first MC methods，即在一个episode内，我们只记录s的第一次访问，并对它取平均回报。
现在我们假设有如下一些样本，取折扣因子γ=1，即直接计算累积回报，则有

根据first MC methods，对出现过状态s的episode的累积回报取均值，有Vπ(s)≈ (2 + 1 – 5 + 4)/4 = 0.5
容易知道，当我们经过无穷多的episode后，Vπ(s)的估计值将收敛于其真实值。
参考：Reinforcement Learning笔记(2)--动态规划与蒙特卡洛方法

动作值
在每个阶段中，先查看状态动作对的经历，然后计算每个状态动作对之后的回报，再取平均值。如果在一个阶段中，某一状态动作对出现多次，则处理方法与上面一样，分为只考虑首次经历和考虑所有经历。

蒙特卡罗法→控制问题（策略改进）

前面我们讲到，我们通过一些样本来估计动作值函数Q和状态值函数V，并且在未来执行估值最大的动作。
这里就存在问题，假设在某个确定状态s0下，能执行a0, a1, a2这三个动作，如果智能体已估计了两个Q函数值，如Q(s0,a0), Q(s0,a1)，Q(s0,a0)>Q(s0,a1)，那么它在未来将只会执行一个确定的动作a0。
这样我们就无法更新Q(s0,a1)的估值和获得Q(s0,a2)的估值了，无法保证Q(s0,a0)就是s0下最大的Q函数。
为了解决这个问题，我们需要对策略进行改进。和动态规划对比，动态规划中的更新策略是通过最大化动作值函数获得的，这种方法称为贪婪策略。在蒙特卡洛方法中仍然使用贪婪策略的话，会使智能体很容易掉入眼前的陷阱中，而忽略其他最大化奖励的可能。所以要修改算法，使得智能体能够探究每种策略背后最大化奖励的可能。
这时候的方法是采用随机性策略，随机策略中以高概率选择贪婪策略，低概率选择某个非贪婪策略，即不再始终采用贪婪策略。
该算法称为ϵ 贪婪策略。ϵ 的范围为 [0,1]
ε-greedy policy（ϵ- 贪婪策略），即在所有的状态下，用1-ε的概率来执行当前的最优动作a0，ε的概率来执行其他动作a1, a2。这样我们就可以获得所有动作的估计值，然后通过慢慢减少ε值，最终使算法收敛，并得到最优策略。

具体的流程

以下版本用的是every-visit,即个状态序列中每次出现的相同状态，都会计算对应的收获值。

友情参考：强化学习（四）用蒙特卡罗法（MC）求解

总结
蒙特卡罗法可以避免动态规划求解过于复杂，同时还可以不事先知道环境转化模型，因此可以用于海量数据和复杂模型。
但是它也有自己的缺点，这就是它每次采样都需要一个完整的状态序列。如果我们没有完整的状态序列，或者很难拿到较多的完整的状态序列。

Ending 吃饭啦！周末愉快！
友情链接： 增强学习（四） ----- 蒙特卡罗方法(Monte Carlo Methods)