[RL Note] 蒙特卡洛方法和蒙特卡洛预测

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 的规模无关。蒙特卡洛方法可以独立地估计每一个状态的价值,而动态规划的方法则需要依赖其他状态来更新当前状态。