深入理解强化学习——马尔可夫决策过程：马尔可夫奖励过程-[计算马尔可夫奖励过程价值的蒙特卡洛方法]

分类目录：《深入理解强化学习》总目录

---

文章《[深入理解强化学习——马尔可夫决策过程：马尔可夫奖励过程-[贝尔曼方程]]](https://machinelearning.blog.csdn.net/article/details/134407229)》介绍了计算马尔可夫奖励过程价值的解析方法，但解析解的计算复杂度是$O(n^3)$，其中$n$是状态个数，因此这种方法只适用很小的马尔可夫奖励过程。求解较大规模的马尔可夫奖励过程中的价值函数时，可以使用动态规划（Dynamic Programming）算法、蒙特卡洛方法（Monte-Carlo Method）和时序差分（Temporal Difference）算法（动态规划和蒙特卡洛方法的一个结合）。

首先我们用蒙特卡洛方法来计算价值。如下文所示，蒙特卡洛方法就是当得到一个马尔可夫奖励过程后，我们可以从某个状态开始，把小船放到状态转移矩阵里面，让它“随波逐流”，这样就会产生一个轨迹。产生一个轨迹之后，就会得到一个奖励，那么直接把折扣的奖励即回报$g$算出来。算出来之后将它积累起来，得到回报$G_t$。当积累了一定数量的轨迹之后，我们直接用$G_t$除以轨迹数量，就会得到某个状态的价值。

蒙特卡洛方法来计算价值
输入：随机产生轨迹的个数$N$
(1) $i=0;G_t=0$
(2) while$i\ne N$
(3) \quad 从状态$s$和时刻$t$开始生成一个轨迹
(4) \quad 使用生成的轨迹计算回报：$g={\sum }_{i=t}^{H-1}{\gamma }^{i-t}{r}_i$
(5) $G_t=G_t+g$
(6) $i=i+1$
(7) $V_t(s)=\frac{G_t}{N}$

比如我们要计算$s_1$状态的价值，可以从$s_1$状态开始，随机产生很多轨迹。把小船放到状态转移矩阵里面，然后它就会“随波逐流”，产生轨迹。每个轨迹都会得到一个回报，我们得到大量的回报，比如1000个回报，然后直接取平均值，就可以等价于现在$s_1$的价值，因为$s_1$的价值$V_t(s_1)$定义了我们未来可能得到多少的奖励。这就是蒙特卡洛采样的方法。

参考文献：
[1] 张伟楠, 沈键, 俞勇. 动手学强化学习[M]. 人民邮电出版社, 2022.
[2] Richard S. Sutton, Andrew G. Barto. 强化学习（第2版）[M]. 电子工业出版社, 2019
[3] Maxim Lapan. 深度强化学习实践（原书第2版）[M]. 北京华章图文信息有限公司, 2021
[4] 王琦, 杨毅远, 江季. Easy RL：强化学习教程 [M]. 人民邮电出版社, 2022