蒙特卡洛强化学习[Monte-Carlo Reinforcement Learning，MC]是强化学习中的经典方法，应用于model-free的场景中，并且可以得到相对好的结果。

model-free就是$\mathcal{P},\mathcal{R}$未知， model-free和model-based中的model其实就是对环境的建模，比如如果直到一周之内的天气变化概率，这就是model-based，但是如果不知道的话，只有每天观测天气变化，这就是model-free，而天气就是环境。

Motivation

在model-free的场景中，由于不知道$\mathcal{P},\mathcal{R}$，无法直接计算行为价值函数和状态价值函数，也就无法进行强化学习[根据价值函数进行策略估计，然后策略提升]。我们既然不知道环境是怎么样的或者说无法对环境建模，那最直接的想法就是直接和环境交互获得反馈，也就是从试验中学习或从经验中学习。这也是为什么这种强化学习方法叫做蒙特卡洛的原因。

蒙特卡洛方法的核心思想是用多次实验逼近客观分布真实值的统计学应用，这和在model-free的场景中只能通过多次实验获得反馈进行学习的思路不谋而合，因此得名。

Monte-Carlo Reinforcement Learning

蒙特卡洛方法是假设每个状态的$V(S)$取值等于多个episodes的回报$G_t$的算术平均值，而不是其期望值。

Episode：指必须从某一个状态开始，Agent与Environment交互直到终止状态，环境给出终止状态的即时收获为止。注意：Episode不要求起始状态一定是某一个特定的状态，但是要求个体最终进入环境认可的某一个终止状态。

之前介绍过$G_t$的定义，本质上说$G_t$是基于目前状态，在一个episode中所能获得所有reward的总和，所以MC方法需要每个episode是完整的，即一定要执行到终止状态。所以，

\[V(S) = E[G_t \mid S_t = S] \approx \sum_{k=1}^n R_{S_t = S}^{ep. k}\]

故MC算法中，需要记录两个值状态S被访问到的次数$N(S) \leftarrow N(S) + 1$，以及每次访问时获得回报并计算其总和$RS(S) \leftarrow RS(S) + G_t$。遍历完所有的episodes之后，得到状态S下值函数取值为$V(S) = RS(S) / N(S)$。而这里有两种访问次数的记录方式，一种是在一个episode中只记录第一次访问到的s，另一种是一个episode中每次访问到s都记录下来，两种方式最后都是渐进收敛。同时，此平均值函数是实时更新，也就是说计算平均收获时不需要存储所有既往收获，而是每得到一次收获，就计算其平均收获。给定状态$s$, 使用MC方法计算其价值的理论公式及其推导如下，其中，$k$是累积采样次数。

\[\begin{eqnarray} v_{k}(s) &=& \frac{1}{k} \sum_{j=1}^{k}G_{j}(s)\nonumber \\ &=& \frac{1}{k}(G_{k}(s) + \sum_{j=1}^{k-1} G_{j}(s)) \nonumber \\ &=& \frac{1}{k}(G_{k}(s) + (k-1)\frac{1}{k-1}\sum_{j=1}^{k-1} G_{j}(s)) \nonumber \\ &=& \frac{1}{k}(G_{k}(s) + (k-1)v_{k-1}(s)) \nonumber \\ &=& \frac{1}{k}(G_{k}(s) + kv_{k-1}(s) - v_{k-1}(s)) \nonumber \\ &=& v_{k-1}(s) + \frac{1}{k}(G_{k}(s) - v_{k-1}(s)) \nonumber \\ \end{eqnarray}\]

上述推导给出了一个MC的递增计算平均的方法，也就是第$k$次采样和第$k-1$次采样的关系。比如对于一个episode有$S_1, A_1, R_2, \cdots, S_t, A_t, R_{t+1}, \cdots$, 对于每个状态$S_t$, 没碰到一次[或者说采样一次]，就会获得此次的回报$G_t$，然后累积次数$N(S) \rightarrow N(S) + 1$。这样根据上述推导，我们可以更新状态的平均价值:

\[V(S_t) \leftarrow V(S_t) + \frac{1}{N(S)}(G_t - V(S_t))\]

这里\frac{1}{N(S)}是一个参数[也就是原始推导的$\frac{1}{k}$]，其取决于采样次数，有时为了简便，我们会扔掉之前的episode的采样，所以可以使用$\alpha$表示。

\[V(S_t) \leftarrow V(S_t) + \alpha(G_t - V(S_t))\]

Drawback

MC方法，是一个通过不断采样让样本丰富起来，进而比较准确地估算出由策略$\pi$驱使的某个状态的估值$v_{\pi}(s)$的过程。简单地说，通过多次实验进行统计，计算状态估值，一旦状态估值$v(s)$能够估算准确，就能评价一个动作的估值$q(s, a)$。只要这一点能够达成，一个好的策略就会变成”在某状态下,查看$q(s, a)$中的哪个$a$在当前给定的状态$s$下估值最高”的问题了，原因在于，只要$q(s, a)$是准确的，就表示其中包含远期回报(而不是直接回报)，$q(s, a)$是一个可以信任的估值，而这个过程，就是由MC法试出来的。

MC的优势在于，它不是以模型为基础的[model-free]，而是通过多次试探求平均值的方法让估值逐步变得准确的。于是，问题产生了。在统计中，尽管随着实验次数的增加，平均值会逐渐稳定在一个值附近。例如，在扔硬币时一定会从第一次正面朝上或反面朝上的概率为$100%$开始，随后统计结果大幅波动，最终逐步无限逼近正面朝上和反面朝上的概率均为$50%$这个统计平均值。然而，在这个过程中，前几次实验结果的方差一定大得惊人。MC也没办法避免这个问题，在开始的几十个甚至上百个Episode中，这种方差会像梦魇一样伴随着我们。这些最初产生的状态估值都严重偏离真实的估值，是不可信的。

Blackjack Example

下面是一个经典的例子，其中一个episode就是一局blackjack，终止状态就是输赢判定，通过不断的重复玩，最终可以获得策略。

Blackjack Example

Reference:

  1. 理解强化学习知识之解决无模型的MDP, https://zhuanlan.zhihu.com/p/32161274
  2. 从零开始认识强化学习, https://zhuanlan.zhihu.com/p/56045177
  3. Sutton, Richard S., and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
  4. 高扬，叶振斌，白话强化学习与PyTorch