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.
狗熊会特别感谢为本案例提供宝贵素材和为案例重新整理加工提供帮助的小伙伴：来自复旦大学的邵路婷。
本案例为狗熊会精品案例库收录。狗熊会精品案例库为狗熊会核心商业产品，目前收录了超过100个案例，包括探索性数据分析、回归分析、机器学习、文本分析、时间序列分析等模块，涉及电商、金融、餐饮等行业。狠戳阅读原文，查看狗熊会精品案例库。狗熊会精品案例库面向机构收费授权开放，有意洽谈者，请加熊二微信clubear2详细沟通。
