【RL系列】蒙特卡罗方法笔记

蒙特卡罗方法给我的感觉是和Reinforcement Learning: An Introduction的第二章中Bandit问题的解法比较相似，两者皆是通过大量的实验然后估计每个状态动作的平均收益。不过两者的区别也是显而易见，Bandit问题比较简单，状态1->动作1->状态1，这个状态转移过程始终是自我更新的过程，而且是一一对应的关系。蒙特卡罗方法所解决的问题就要复杂一些，通常来说，其状态转移过程可能为，状态1->动作1->状态2->动作1->状态3。Sutten书中是这样描述两者的区别：

The main di?erence is that now there are multiple states, each acting like a di?erent bandit problem (like an associative-search or contextual bandit) and that the di?erent bandit problems are interrelated. 

这里说的很好，应用蒙特卡罗方法的问题中的每一个状态下的其中一个动作之后的状态转移过程都像是许多个不同的Bandit问题。还有一个很明显的区别是，蒙特卡罗问题大都有一个或几个明确的目标状态，达到目标状态后，才能计算当前收益，中间过程通常来说并没有自己的状态或动作收益，但对于Bandit问题来说是没有这个中间过程的。

什么是中间过程？简单来说就是从起始状态到达目标状态中间所经历的状态动作集合。在蒙特卡罗方法中，中间过程不获得任何奖励，但是中间过程的状态动作价值可以由目标状态奖励进行估计。这个估计的原则也很简单，可以描述为：某状态动作价值可以估计为经过该状态到达目标所获得的奖励之和除以经过该状态的次数。对于某个中间过程的状态动作价值估计实际上就是许多个不同的Bandit问题中的一个。在上一篇文章中提到了在解决Soap Bubble问题中，蒙特卡罗方法的优势，即可以快速收敛某一个状态或某几个状态的价值估计。上一篇文章中的算法只关注起始状态的价值收敛而完全忽略中间过程，但当使用蒙特卡罗方法估计所有状态价值时，对中间过程不进行任何处理的方法就太低效了。所以下面我们尝试将中间状态价值估计应用到之前的算法中，看一看完整的蒙特卡罗方法进行价值估计的算法流程，还是以Soap Bubble为例：

1. 投影闭合曲线到x-y平面
2. 开始迭代，随机选择起始点(x, y)
3. 随机选择动作开始游走
4. 判断是否碰到边界，如碰到边界，记录边界高度值$ H_b $，并记录中间经过的每一个状态，写成状态集合$S$。未碰到则继续游走。
5. 设状态state属于状态集合$ S $，用公式更新状态state的价值总和$ V(\mathrm{state}) $与经过状态state的次数$ C(\mathrm{state}) $：$$ V(\mathrm{state}) =  V(\mathrm{state}) + H_b \\ C(\mathrm{state}) =  C(\mathrm{state}) + 1$$
6. 判断是否收敛，未收敛则回到第三步重新开始。
7. 任何一点（任何一个状态）的高度值的估计可以计算估计为((x, y) = state)：$$ H(state) = \frac{V(state)}{C(state)} $$

【RL系列】蒙特卡罗方法笔记

原文：https://www.cnblogs.com/Jinyublog/p/9357425.html