[RL Notes] 蒙特卡洛方法和蒙特卡洛预测
1. 蒙特卡洛方法
使用动态规划来估计价值函数并寻找最优策略的效率虽然很高，但要事先知道 MDP 的动态特性 $p(s’,r|s,a)$，而在很多实际问题中，我们并不具有关于环境状态变化的先验知识，此时就需要能够仅从经验中学习，即从真实或模拟的环境交互中采样得到状态、动作、收益序列，并对价值进行估计。
蒙特卡洛（Monte Carlo）方法指的是一系列从重复采样中进行估计的方法。在强化学习中，蒙特卡洛方法通过对大量样本的回报进行平均，来进行价值估计。随着收集到的样本越来越多，平均值就会收敛到期望值。需要注意的是，状态的回报需要在一幕结束后才能观察到，这里只讨论分幕任务的蒙特卡洛方法。
2. 蒙特卡洛预测
如果某个状态 $s$ 在出现在给定策略 $\pi$ 的某一幕中，则称之为对 $s$ 的一次访问。如果某个状态 $s$ 在一幕中被多次访问，则称对 $s$ 第一次访问为首次访问。如果算法只使用 $s$ 所有首次访问的回报的平均值来对 $v_\pi(s)$ 进行估计，称这种算法为首次访问型 MC 算法。相对地，每次访问型 MC 算法使用 $s$ 的所有访问的回报的平均值来对 $v_\pi(s)$ 进行估计。
首次访问型 MC 算法如下所示。
首次访问型 MC 预测算法，用于估计 $V_\pi \approx v_\pi$
输入：待评估的策略 $\pi$
初始化：
对所有 $s \in \mathcal S$，任意初始化 $V(s) \in \mathbb R$
对所有 $s \in \mathcal S$，$Returns(s) \leftarrow 空列表$
无限循环（对每幕）：
根据 $\pi$ 生成一幕序列：$S_0, A_0, R_1, S_1, A_1, R_2, \cdots, S_{T-1}, A_{T-1}, R_T$
$G \leftarrow 0$
对本幕中的每一步进行循环, $t = T-1, T-2, \cdots, 0$：
$G \leftarrow \gamma G + R_{t+1}$
如果 $S_t$ 在 $S_0, S_1, \cdots S_{t-1}$ 中没有出现过
将 $G$ 加入 $Returns(S_t)$
$V(S_t) \leftarrow \mathrm{average}(Returns(S_t))$
删除上面算法倒数第三行检查 $S_t$ 是否已经出现过的判断，就得到每次访问型 MC 算法。
由上述算法可见，蒙特卡洛方法不需要知道环境，也不需要记录环境的模型，其更新状态价值所需的计算量与每一幕的长度有关，而与 MDP 的规模无关。蒙特卡洛方法可以独立地估计每一个状态的价值，而动态规划的方法则需要依赖其他状态来更新当前状态。