[RL Notes] 蒙特卡洛控制
Contents
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)$