这次我们要分享的是蒙特卡洛方法，一种基于随机采样的优化策略。与前一章不同，不需要对环境有完整的了解。蒙特卡罗方法只需要根据经验，即与环境交互的状态、动作和奖励的样本序列。
“蒙特卡洛”这个术语通常用于任何涉及随机分量的估计方法，蒙特卡洛方法是基于平均样本回报解决强化学习问题的方法，注意这里使用的是 return，而不是 reward。为了确保有明确定义的 return 可用，我们只为可以划分为episode的任务定义蒙特卡罗方法。也就是说，假设经验（experience）被划分为片段，并且无论选择什么动作，所有 episode 最终都会终止，只有在一个 episode 完成时，值函数和策略才会发生变化。因此，蒙特卡洛方法可以在 episode 意义上是增量的，而不是在 step 意义上。
蒙特卡洛方法对每个状态-动作对进行采样并计算平均回报（return），这与我们在前面分享的多臂老虎机方法对每个动作的采样和计算平均回报非常相似。主要区别在于现在有多个状态，每个状态都像一个不同的老虎机问题，并且不同的老虎机问题是相互关联的。也就是说，在一个状态下采取行动后的回报取决于同一episode中在后面的状态下采取的行动。
与前面的动态规划求解强化学习问题的方法一样，我们先分享在蒙特卡洛方法下的值函数估计，再分享蒙特卡洛方法下的策略优化，最后分享基于重要性采样的优化方法。
值函数估计
状态值函数
根据估计时所使用的样本的不同，蒙特卡洛方法可以分为“first-visit\ MC\ method”和“every-visit\ MC\ method”。其中，first-visit\ MC\ method 使用的样本是每个 episode 中第一次遇到状态 s 之后的回报，而 every-visit\ MC\ method 使用的是每个 episode 中每次遇到状态 s 之后的回报。但相同点是，我们对所有的 episode 中采样到的回报进行一个平均，就得到状态的值函数了。
我们直接看伪代码：
动作值函数
事实上，我们在借助值函数进行决策时，常常会更多地用到动作值函数，比如贪心策略的 \arg\max_a\{q(s,a)\}。因此，我们也总结下蒙特卡洛方法下的动作值函数的估计方法。
和状态值函数一样，动作值函数的估计也分为 “first-visit\ MC\ method”和“every-visit\ MC\ method”。值得一提的是，动作值函数是针对每个“状态-动作”对而言的。因此，在 first-visit\ MC\ method 下，使用的采样就是每个episode中第一次遇到状态 s 并采取了动作 a 之后的回报进行平均，every-visit\ MC\ method 同理。
exploring\ starts
对于一个特定的强化学习问题，“状态-动作”对的数量是非常庞大的，这就导致在一个确定性的策略下有大量的“状态-动作”对将无法被选到，而我们又需要保证每个“状态-动作”对被选到的次数都是无限多的。因此，我们经常会有一个假设就是每个“动作-状态”对都有非零的概率被选到。这个假设就被称作 ”exploring\ starts“。
蒙特卡洛策略优化
我们使用和之前一样的方法进行策略优化--greedy方法，即在每个状态下尝试值函数最大的策略，如果现有的动作值函数下更优，则将该状态下的决策调整为该动作。再结合上面的假设--”exploring\ starts“，这个方法被称作 Monte\ Carlo\ ES。算法伪代码如下：
without exploring\ starts
为了去掉 exploring\ starts 这个假设，我们根据动作值函数定义一个新的动作选择概率分布如下
a^* = \arg\max_aQ(s,a)\\
\pi(s,a) \gets
\left\{\begin{matrix}
1-\epsilon + \epsilon/|\mathcal{A}(s)| &if\ a=a^* \\
\epsilon/|\mathcal{A}(s)| & if\ a\neq a^*
\end{matrix}\right.伪代码如下：
基于重要性采样的优化策略
基于重要性采样的优化策略往往被称作 off-policy，在重要性采样方法下，我们通常定义一个目标策略 \pi 和一个控制策略 \mu。也就是说在与环境交互的过程中遵循的是策略 \mu，而我们要基于交互中的采样计算出目标策略 \pi 的值函数。相比以往的方法，我们的控制策略和目标策略都是 \pi，故而这里被称作 off-policy。
这种策略的一个好处就是，我们往往可以在当前策略下计算最优策略的值函数，也就是说将控制策略和目标策略分离开，目标策略是一个确定的策略，而控制策略可以是一个概率模型，从而保证了每个”状态-动作“对都可以被选择到，下面，我们就来看看这种方法的实现原理。
其实在两种策略下，每个状态动作序列都是有可能出现的，只是出现的频率或者概率不一样，这就需要我们对控制策略 \mu 下得到的回报进行一定的加权再平均。在策略 \pi 下，一个状态动作序列 A_t, S_{t+1},\cdots,S_T 的概率为
\Pi_{k=t}^{T-1}\pi(A_k|S_k)p(S_{k+1}|S_k,A_k).（注意，这里我们将所有的 episode 在时间上连接在一起，这样每个 episode 的每个 step 都可以用不同的时间戳区分开来了。）根据，这个概率公式，我们计算每个回报的权重因子为
\rho_t^T = \frac{\Pi_{k=t}^{T-1}\pi(A_k|S_k)p(S_{k+1}|S_k,A_k)}{\Pi_{k=t}^{T-1}\mu(A_k|S_k)p(S_{k+1}|S_k,A_k)} = \Pi_{k=t}^{T-1}\frac{\pi(A_k|S_k)}{\mu(A_k|S_k)}.按照计算平均的方法，重要性采样的优化策略分为”ordinary“和”weighted“两种：
ordinary\ importance\ sampling 的计算公式为
V(s) = \frac{\sum_{t\in \mathcal{T}(s)}\rho_t^{T(t)}G_t}{|\mathcal{T}(s)|},以 first\ visit 策略为例，其中，\mathcal{T}(s) 表示所有的 episode 中第一次遇到状态 s 的时刻，T(t) 表示时刻 t 之后的首次termination。
weighted\ importance\ sampling 的计算公式为
V(s) = \frac{\sum_{t\in \mathcal{T}(s)}\rho_t^{T(t)}G_t}{\sum_{t\in \mathcal{T}(s)}\rho_t^{T(t)}}.增量实现
重要性采样下值函数迭代的一种增量实现，和之前多臂老虎机里面计算均值的思想是一样的
V_n = \frac{\sum_{k=1}^{n-1}W_kG_k}{\sum_{k=1}^{n-1}W_k}\\
V_{n+1} = V_n + \frac{W_n}{C_n}[G_n - V_n]\\
C_{n+1} = C_n + W_{n+1}总结
以上就是蒙特卡洛方法，下次我们分享强化学习的时间差分学习方法。