[RL Notes] 蒙特卡洛控制

Author: nex3z 2019-10-23

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)$

---