[RL Note] 蒙特卡洛控制

1. 动作价值的蒙特卡洛估计

  动作价值函数的策略评估问题是估计策略 $\pi$ 下从状态 $s$ 选择动作 $a$ 的期望回报,即

\begin{equation}
q_\pi(s, a) \doteq \mathbb{E}_\pi [G_t | S_t = s, A_t = a] \tag{1}
\end{equation}

通过动作价值函数可以比较同一状态下采取不同行动的差异,这对于学习策略十分重要的。

  使用蒙特卡洛方法对动作价值进行估计的过程和蒙特卡洛预测类似——收集策略 $\pi$ 下“状态-动作”二元组所产生回报的样本,再计算平均。

  类似于蒙特卡洛预测,如果在某一幕中 $s$ 被访问,且在这个状态中选择了动作 $a$,则称“状态-动作”二元组 $(s, a)$ 被访问了一次。如果只计算每一幕中“状态-动作”二元组第一次被访问的回报的平均,则得到首次访问型 MC 算法,只需将首次访问型 MC 预测算法中对状态的访问改成对“动作-价值”二元组的访问即可。如果计算“状态-动作”二元组所有访问的平均,则得到每次访问性 MC 算法。

  使用蒙特卡洛方法对动作价值函数进行估计的一个问题是,需要确保每个“状态-动作”二元组都被访问到。如果某个“状态-动作”二元组从未被访问,就无法收集到对应的回报样本,也就无法对这个“状态-动作”二元组的价值进行估计,从而无法比较该状态下这个动作与其他动作的优劣。

  这就要求要在学习中保持试探。一种方法是确保每个“状态-动作”都会作为一幕的起点,称为试探性出发(exploring starts)。但在真实环境中,并不是总能满足试探性出发的要求,此时可以使用另一种方法,即确保每个状态下所有动作都有非零概率被选择的随机策略。

2. 蒙特卡洛控制

  通过动作价值的估计,就可以进一步实现广义策略迭代(GPI)来解决控制问题,即找到近似最优的策略。

  广义策略迭代包括策略评估和策略改进两个步骤,不断迭代得到一个不断改进的策略和价值函数序列。在蒙特卡洛广义策略迭代中,策略评估阶段使用蒙特卡洛方法估计动作价值,策略改进阶段使用贪心策略,即

\begin{equation}
\pi_{k+1}(s) \doteq \underset{a}{\arg\max} \; q_{\pi_k}(s, a) \tag{2}
\end{equation}

  基于试探性出发的蒙特卡洛(蒙特卡洛 ES)算法如下所示。


蒙特卡洛 ES(试探性出发),用于估计 $\pi \approx \pi_*$
初始化:
  对所有 $s \in \mathcal S$,任意初始化 $\pi(s) \in \mathcal A(s)$
  对所有 $s \in \mathcal S$,$a \in \mathcal A(s)$,任意初始化 $Q(s, a) \in \mathbb R$
  对所有 $s \in \mathcal S$,$a \in \mathcal A(s)$,$Returns(s, a) \leftarrow 空列表$
无限循环(对每幕):
  选择 $S_0 \in \mathcal S$ 和 $A_0 \in \mathcal A(S_0)$ 以使得所有“状态-动作”二元组的概率都 $> 0$
  从 $S_0, A_0$ 开始根据 $\pi$ 生成一幕序列 $S_0, A_0, R_1, \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, A_t$ 在 $S_0, A_0, S_1, A_1, \cdots, S_{t-1}, A_{t-1}$ 中没有出现过:
      将 $G$ 加入 $Returns(S_t, A_t)$
      $Q_t(S_t, A_t) \leftarrow \mathrm{average}(Returns(S_t, A_t))$
      $\pi(S_t) \leftarrow \underset{a}{\arg\max} \; Q(S_t, a)$