强化学习（蒙特卡洛法）
本文介绍了强化学习的 model-free 方法——蒙特卡洛法。
1. 引言
在前面的 model-based 动态规划方法中，我们假设已知模型的动态特性 $p(s^\prime,r \vert s,a)$，此时可以对下一步的状态和回报做出预测。而在很多实际案例中，我们无法得知模型的动态特性，此时动态规划方法就不适用了。
2. 蒙特卡洛法
2.1. 大数定律
大数定律的定义是，当随机事件发生的次数足够多时，随机事件发生的频率趋近于预期的概率。可以简单理解为样本数量越多，其平概率越接近于期望值。大数定律的条件：1、独立重复事件；2、重复次数足够多。
2.2. 蒙特卡洛法
蒙特卡洛方法的主要思想是“当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。是一种基于大数定律的统计方法。
蒙特卡洛方法解决强化问题的本质，是基于通过采样大量数据来进行学习的经验方法实现的，因此，即便是在环境模型 $p(s^\prime,r \vert s,a)$ 未知/未完全可知的情况下，采用时间步骤有限的、完整序列(episode)中进行采样，并通过平均采样回报来解决强化学习问题。
2.3. 蒙特卡洛价值估计
在一次交互过程中，可采样得到一条序列
\[s_0, a_0, r_1, s_1, a_1, r_2, s_2,\cdots\]采集 $N$ 条序列，对于其中每条序列，找寻期望的状态起点 $s$ 并计算对应的 $G_t$
\[G_t = \sum_{k=0} \gamma^k R^{t+k+1}\]由于序列中期望状态起点可能不存在，也可能出现1次，也可能出现多次，因此期望的状态起点 $s$ 的找寻方式分为两种：
- 首次访问型（first visit）：只采集第一个出现 $s$ 时对应的 $G_t$
- 每次访问型（every visit）：采集每次出现 $s$ 时对应的 $G_t$
首次访问型和每次访问型相比之下各有利弊。首次访问型的优势与每次访问型的劣势：
- 由于序列与序列之间相互独立，若从每个相互独立的序列中取出唯一一个状态 $s$ 的回报，那么首次访问型产生的回报样本同样也是经过独立试验产生的相互独立的样本；
- 相比之下，若将相同序列下的状态 $s$ 的回报均作为样本，根据回报的计算过程，回报之间可能存在关联关系；
首次访问型的劣势与每次访问型的优势：
- 由于首次访问型只从一个序列中获取一个样本(在序列中存在状态 $s$ 的条件下)，因此获取样本集需要的序列数量大于样本集数量（因为可能存在某个序列中不含状态 $s$）。
- 相比之下，每次访问型可能仅需要更少的序列数量就可以得到足够多的样本。因此，从收集样本花费代价的角度观察，每次访问型优于首次访问型。
最后，根据大数定律
\[\begin{aligned} v_\pi(s) &\doteq \mathbb{E}_\pi[G_t \vert S_t = s] = \sum_a\pi(a\vert s)\sum_{s^\prime,r}p(s^\prime, r \vert s,a)(r+\gamma v_\pi(s^\prime))\\ &=\frac{1}{N}\sum_{i=1}^N G_t^{(i)} \end{aligned}\]同理可计算 $q_\pi(s,a)$，且实际计算动作价值函数的意义更大，方便策略改进。但注意，状态序列采样时需要同时命中 $S_t=s,A_t = a$ 条件时才能采集对应的 $G_t$，这对样本量需求更大，操作难度更高。
局限性：
-
对 $G_t$ 采样的过程中，样本必须在一幕（从 $t$ 时刻开始，$T$ 时刻结束）全部执行结束的状态下，才能获取 $R_{t+1},R_{t+2},…,R_{t+T}$ 的具体结果，并最终获得1个 $G_t$ 结果。
-
最终需要获取足够量的（$N$ 个） $G_t$ 结果才能够执行均值操作，整个过程绝大部分时间浪费在了采样过程，时间利用率极低。
2.4. 增量更新方法
为了客服上述缺点，计算均值时，可采用增量更新方法，更新时间更短，更容易观察到收敛结果，有效提高了时间的利用率。
以取均值为例，已知一个数列中包含3个数值 $[3,4,5]$，增量更新方法如下：
\[\begin{aligned} u_1 &= \frac{1}{1}\sum_{i=1}^1 x_i = 3\\ u_2 &= \frac{1}{2}\sum_{i=1}^2 x_i = \frac{3+4}{2} = 3.5\\ \Rightarrow u_2 &= u_1+\frac{1}{2}(x_2-u_1) = 3+\frac{1}{2} = 3.5\\ \Rightarrow u_3 &= u_2+\frac{1}{3}(x_3-u_2) = 3.5+\frac{1}{2} = 4 \end{aligned}\]则蒙特卡洛增量更新方法如下
\[\left\{ \begin{aligned} N(S_t) &\leftarrow N(S_t)+1\\ v(S_t) &\leftarrow v(S_t) + \frac{1}{N(S_t)} (G_t - v(S_t)) \end{aligned} \right.\]这样只需要每次得到 1个 新的 $G_t$ 即可更新一次价值函数，即便和真正的均值存在差异，但更新时间更短，更容易观察到收敛结果，且可以随着时间的推移逐步接近均值。
局限性：
然而，仍然要求采样一条完整的序列直到结束时刻 $T$ 才能计算出 1个 $G_t$。因为
\[G_t = \sum_{k=0} \gamma^k R^{t+k+1}\]后面介绍时序差分法克服该局限。
3. 参考文献
[1] shuhuai008. bilibili蒙特卡洛方法-强化学习-合集
[2] 韵尘. 知乎：5.1 —— 蒙特卡洛预测（Monte Carlo Prediction）
[3] 静静的喝酒. 强化学习之SARSA