1 背景介绍
在强化学习简介及马尔可夫决策过程的案例中，我们采用马尔可夫决策过程中的五元组进行建模，使用基于动态规划的策略迭代和值迭代方法，利用贝尔曼方程将求解价值函数递归为求解子问题，从而求解最优策略。动态规划方法建立在模型已知的情况下，但是现实中大多数情况下模型是未知的，例如状态转移函数、奖励函数无法提前完全掌握。因此强化学习中的蒙特卡罗方法（Monte Carlo, MC），通过经验学习的方法，从样本轨迹的状态、动作和奖励中估计价值函数，寻找最优策略。
本案例将基于迷宫游戏，对强化学习的蒙特卡罗方法进行介绍。
2 蒙特卡罗算法简介
蒙特卡罗 (Monte Carlo) 是一大类随机算法 (Randomized Algorithms）的总称，它们通过随机样本来估算真实值。
均匀生成[-1,1]区间随机数x和y，(x,y)落在的正方形中圆心为(0,0)、半径为1的圆中的概率为。随机抽样n个点，设圆内的点的数量为随机变量M,。根据大数定律，当n 非常大，那么随机变量 M 的真实观测值 m 就会非常接近期望值,。
算法流程：
初始化m=0，设定抽样样本数n，精度、计算量均随着n的增加而提升 对于轮抽样： 从区间[-1,1]上进行两次均匀随机抽样，分别得到x和y 如果，则 返回的估计值
对于一元函数求解在区间[a,b]上的定积分，蒙特卡罗方法通过在区间[a,b]上随机抽样n个x的样本，返回函数值的平均值与区间长度的乘积估计定积分。
对于多元函数，求解在上的定积分，算法流程如下：
设定抽样样本数n，精度、计算量均随着n的增加而提升 在集合上均匀随机抽样n个样本 计算的体积 返回的估计值：函数值的平均值与体积的乘积
定义是维随机变量， 它的取值范围是集合,是的概率密度函数，的期望。
根据的概率密度函数进行非均匀抽样，能够比均匀抽样更快收敛。随机抽样n个独立同分布样本，，在n足够大时的估计值为，
算法流程：
设定抽样样本数n，精度、计算量均随着n的增加而提升 随机抽样n个独立同分布样本 计算函数值的平均值 返回的估计值
3 蒙特卡罗求解预测问题
3.1 Prediction and Control
在上一节中，我们介绍了马尔可夫决策过程，通过五元组进行建模，下面我们简单回顾五元组的元素定义：
指有效的状态的集合状态空间 指有效的动作的集合动作空间 指状态转移函数：表示在状态下采取动作后状态转移到的概率 指奖励，奖励是智能体在特定状态下采取行动获得的反馈信号 指折扣因子，用于计算累积未来奖励时对未来奖励的折现程度
在马尔可夫决策过程中，分为预测（Prediction）和控制（Control）两类问题。
预测问题：输入和策略后，估计状态价值函数和动作价值函数 控制问题：在强化学习中基于预测来制定决策的阶段，在输入后，输出最优价值函数、以及最优策略
3.2 Model-Based and Model-Free
强化学习方法通常分为两类：基于模型的方法 (Model-Based) 和无模型方法 (Model-Free)。Model-based方法建立在环境模型已知的情况下，包括状态转移概率和奖励函数，通常采用动态规划（如值迭代或策略迭代）来规划最佳策略，而model-free方法建立在环境模型未知的情况下，通过与环境的交互来学习，并根据经验直接更新其策略，常用方法包括蒙特卡罗方法（MC）和时间差分法（TD）。
3.3 蒙特卡罗方法
强化学习中的蒙特卡罗方法，在MDP状态转移概率未知的情况下，直接从完整的轨迹来估计状态的真实价值，认为某状态的价值等于在多个轨迹中该状态所有回报的平均值。其中，完整的轨迹是指从某一个状态开始，智能体与环境交互直到终止状态的轨迹。
基本思想：对于策略，从n条轨迹样本中估计s)和，
以的估计为例：
定义回报：时刻及其之后之后累计奖励，
的估计方式与相似，将替换为状态动作对后，计算多个轨迹中该状态动作对所有回报的平均值。
3.4 蒙特卡罗求解预测问题
轨迹包含起始状态为的子轨迹。在每一条轨迹中每一次状态的出现被称作一次访问(visit)，有可能在一个中重复出现，分别采用该状态第一次出现和多次出现的回报，由此分为first-visit MC method和every-visit MC method：
First-visit：用第一次出现状态后的子轨迹的回报均值估计，对于每个状态或动作，在每条轨迹中只考虑该状态或动作首次出现时的回报，而忽略后续出现的情况。
Every-visit：用所有出现状态后的子轨迹的回报均值估计，对于每个状态或动作，在每条轨迹中考虑该状态或动作每次出现时的回报，利用更多样本，。
其中，every-visit的计算量更大，但在迭代轮次少、完整轨迹数量少时效率更高。
4 蒙特卡罗求解控制问题
4.1 蒙特卡罗求解控制问题
与动态规划（DP）方法的策略迭代、值迭代算法的思想类似，在MC方法的策略迭代中，策略评估阶段通过MC Prediction计算动作价值函数，策略改进阶段采用贪心思想，选择使最大的，循环直到策略收敛。
但这个算法存在探索性开端的问题。探索性开端假设从特定的状态动作对出发，能够覆盖所有可能的状态-动作对。对于确定性的策略，遵循策略导致每个状态仅能观察到一个动作的回报，可能会有许多状态-动作对从未被访问到。但在真实环境中，由于状态动作空间大、无法提前知道所有的状态-动作对，探索性开端假设不具有普遍意义。
4.2 on-policy and off-policy
我们通过使智能体持续选择所有状态-动作对，以避免探索性开端假设，包括on-policy和off-policy两种方法：
on-policy（在策略）：用来评估和改善的策略称为目标策略，用于产生数据的称为行为策略，产生数据的策略与评估改善的策略是同一个策略。 off-policy（离策略）：产生数据的策略与评估改善的策略不是同一个策略
4.3 on-policy with -Greedy Policy
首先，我们介绍采用-贪心策略的on-policy算法。
4.4 Off-Policy
非确定性的on-policy -greedy方法通过非最优选择探索所有行为，而off-policy方法则从另一个探索性策略生成的数据中学习确定性最优策略。
为使用一个分布的采样值，估计另一个分布的估计期望值，也就是从行为策略采样的数据中估计目标策略的动作价值函数，我们需要采用重要性采样（importance sampling）。
从状态开始，根据策略生成子轨迹，该轨迹出现的概率为。
因此，令目标策略和行为策略的轨迹概率分别为和
重要性采样比（importance-sampling ratio）：
由此可见，两条轨迹的概率比仅与策略相关，与环境模型的转移概率是无关的。
定义是行为策略采样的轨迹中采用first-visit或every-visit方法选择的所对应时间的集合，则，将这种简单平均的方式称为原始重要性采样（ordinary importance sampling）。first-visit的原始重要性采样是价值函数的无偏估计，但当目标策略和行动策略的分布函数差异较大时，导致估计的方差大。
另一种重要性采样的方法是加权重要性采样（weighted importance sampling）：。加权重要性采样的期望值为，是的有偏估计，但在实践中具有显著较低的方差，因此更常使用。
初始化策略时，采用任意的soft policy, 使，一般采用 通过的更新：计算重要性采样比，从而估计函数：
5 迷宫游戏实战
下面我们基于上一节所定义的迷宫游戏，分别采用 -Greedy Policy和Off-Policy算法，求解最优的迷宫行进策略。
5.1 -Greedy Policy
-Greedy Policy算法的核心思想是使用蒙特卡罗方法来学习状态-动作值函数，并且在每一轮迭代中根据-贪心策略更新策略。
绘制每一轮策略的累计奖励如图4所示。
在本案例中，较大的能够更快找到最优策略，采用（是迭代轮次）能够使策略在后期轮次中更加稳定。
5.2 Off-Policy
接下来，我们使用Off-Policy算法来寻找最优策略，采用不同的行为策略和目标策略（ -贪心策略），绘制每一轮策略的累计奖励如图5所示。
与-Greedy Policy算法的结果相似，在采用Off-Policy算法和-贪心策略的目标策略时，较大的更快找到最优策略，采用（是迭代轮次）使策略在后期轮次中更加稳定。
6 总结
本案例介绍了蒙特卡罗算法的基本概念，将蒙特卡罗算法应用到强化学习中，在环境模型未知时求解状态价值函数、动作价值函数及最优策略，介绍了解决预测问题和控制问题的蒙特卡罗算法，讲解了蒙特卡罗-Greedy Policy和Off-Policy的算法流程，并使用python在迷宫游戏中分别采用蒙特卡罗-Greedy Policy和Off-Policy算法，求解最优行进策略。
7 参考资料
[1] 魏轲. (2024). Algorithmic and Theoretical Foundations of RL [Handouts]. 复旦大学. https://makwei.github.io/rlIndex.html
[2] 王树森，黎彧君，& 张志华. (2022). 深度强化学习 [M]. 人民邮电出版社.
[3] Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：狗熊会
责任编辑：Road Rash
微信编辑：疑疑
文章转载自『狗熊会』公众号，原文链接： 精品案例 | 强化学习中的蒙特卡罗方法
关注我们
FOLLOW US
