1. 方法概述

蒙特卡罗方法是一种无模型（Model-Free） 的强化学习方法，所谓无模型，就是不需要依赖环境动态模型（如转移概率函数 $P(s\prime \mid s,a)$和奖励函数$R(s,a)$的显式知识）。简单来说，我们前面来说的策略都是通过公式推导出动作价值函数$Q$，而蒙特卡洛可以直接通过观测数据来近似估计$Q$，这样就省略了模型。

2. 如何估计$Q(s_i,a_j)$

将$(s_i,a_j)$对应的动作价值函数记作$Q(s_i,a_j)$，$s_i$状态下做出$a_j$动作所获得的累计奖励记作$G{s}_i,a_j$。

如果你觉得我的符号命名十分混乱，请听我给你解释一下，我的文章中已经出现过多种 $G$ 了。有$G,G_t,G_S,G_{S,A},G_{s_t},G_{s_t,a_t}$
其中 $G_t,G_S,G_{S,A}$是等价的，都是代表某一个随机状态下获得累计奖励的随机变量。的当我们着重讨论 “时间步” 的时候（如贝尔曼公式那一节），我将其记为$G_t$；当我我们关注 “状态” 时，我将其记为$G_S$；当我们关注 “状态-动作对” 时，我将其记为$G_{S,A}$。
其中 $G_{s_t}$ 是指确定的某个状态 $s_t$ 下获得的累计奖励，有时表示随机变量，有时表示样本。
其中 $G_{s_t,a_t}$ 是指确定的某个状态$s_t$并且做出某个确定动作$a_t$时获得的累计奖励，有时表示随机变量，有时表示样本。
其中 $G$ 是一个笼统的名字，就是单纯的代表 “累计奖励” 这四个字，也可以将其看作是上面的所有的符号的统称。

2.1 什么是episode（回合/轨迹）

一个 episode（回合/轨迹） 是指智能体从状态s出发，采取动作a，然后按照策略$\pi$在环境中进行交互，直到到达终止状态（或达到最大步数）的完整过程。

2.2 使用观测到的$G_{s_i,a_j}$估计$Q(s_i,a_j)$

众所周知：
Qπ(s,a)≐Eπ{GS,A∣S=s,A=a}=Eπ{Gs,a} \begin{align*} Q_{\pi}(s,a) &\doteq E_{\pi} \left\{ G_{S,A} \mid S=s, A=a \right\} \\ &=E_{\pi} \left\{ G_{s,a} \right\} \\ \end{align*} Qπ​(s,a)​≐Eπ​{GS,A​∣S=s,A=a}=Eπ​{Gs,a​}​
通过一个episode就会获得一个或多个 $G$ 值，即 $G_{s_i,a_j}$ 。多次采样（得到多个episode）获得足够多的 $G_{s_i,a_j}$ ，对多个 $G_{s_i,a_j}$ 分别求平均值。随着采样次数的增加，该估计会越来越接近当前轮次下真实的$Q(s_i,a_j)$。
例如有一个episode
$$episode=(s_0,a_0,r_1,s_1,a_1,r_2,\dots ,s_{T-1},a_{T-1},r_T,s_T)$$
自然会得到$G_{s_0,a_0},G_{s_1,a_1},G_{s_2,a_2},...,G_{s_T,a_T}$

如果有多个episode，我就可能得到更多$G_{s_0,a_0},G_{s_1,a_1},G_{s_2,a_2},...$，分别对$G_{s_i,a_j}$求平均值，使用这个平均值估计$Q(s_i,a_j)$。
当我们获得了一个可用的$Q(s_i,a_j)$时，我们就可以使用策略迭代去更新我们的策略了。
以上就是蒙特卡洛方法的大体思想。一下是一些小细节。

3. every-visit方法和first-visit方法

当episode中有多个相同的$(s_i,a_j)$如

$$episode=(s_0,a_0,r_1,s_1,a_1,r_2,s_0,a_0,r_3\dots )$$

其中有两个$(s_0,a_0)$

如果是every-visit方法，只要出现一次就收集一次；但是对于first-visit方法，只收集第一次出现的$(s_0,a_0)$ 的q值。
every-visit比较直观，但first-visit的设计理念是什么？

• 无偏性：First-visit的估计在理论上是无偏的（即期望值等于真实 Q(s,a)）。因为每次 (s,a) 的首次出现都对应一个独立的采样路径（从该状态开始的后续轨迹是独立于之前的历史的）。
• 避免依赖性：如果同一episode中多次使用同一个 (s,a) 的回报，这些回报会共享相同的后续状态和奖励，导致样本间存在相关性，可能引入偏差。

4. ε-greedy策略

为了保证所有的(s,a)都能被遍历到，我们不能使用贪心的策略去选择动作，应当给其他的动作一些“机会”，改用ε-greedy策略，即有较大概率选择当前最好的动作，一较小的概率选择其他动作。
其中，A(s)是s所对应的action的个数，参数ε为一个0~1的数。