提出背景

在DP方法中，需要指导转移概率的先验知识，但是一般情况夏是不知道这个概率的，即无法知晓 那么前面的 DP 方法就会失效，那么这里提出一种基于采样的方法来获取相关的信息。
蒙特卡洛方法指的是一系列从重复采样中进行估计的方法。在强化学习中，蒙特卡洛方法通过对大量样本的回报进行平均，来进行价值估计。随着收集到的样本越来越多，平均值就会收敛到期望值。MC算法是在每一幕结束之后进行更新的。

关于 visit 访问的定义

如果状态 出现在策略 中，每一次出现称为一次 访问 , 第一次访问称为 首次访问

两种MC算法

MC算法分为首次访问和每次访问两种，首次访问是只计算每一幕的首次访问的回报，而每次访问则是每一次遇到状态 就进行更新，首次访问的算法流程图如下：

去掉关于 的判断就是每次访问的算法了。

利用蒙特卡洛方法估计动作价值

如果问题是 Model-unaware 的那么就可以考虑利用蒙特卡洛方法去估计动作-状态价值函数 ，只需要把上面的算法中的 换成 二元组就可以了。

消除初始策略带来的影响

为了尽可能多的探索可能的情况，减小策略带来的影响而学习到全局的最优解，通常有 on-policy 和 off-policy 两种方式。

on-policy

on-policy 的方法，本质上还是使用 greedy策略，即让每个动作被选择的概率不小于 ，算法如图所示

不过因为这个策略不要求试探性假设，得到的结果不是最优的

off-policy

off-policy 采用两份不同的策略，一个用于学习，称为 目标策略 ，一个用于生成动作，称为 行动策略 。需要注意的是，行动策略必须包含目标策略，即

重要性采样

重要性采样就是一种通过一种策略的采样来衡量另一种策略的价值函数的技巧，数学推导见下：

首先，我们知道一串序列 在策略 下出现的概率为：

那么这一串事件在行动策略和目标策略下出现的概率之比就是：

那么就可以在这个基础上，得到通过行为策略获取回报并转换成目标策略的价值函数的方法：

注意到前面的 只和具体的策略有关，在行为策略和目标策略都是自己确定的情况下，可以直接算出来。

加权的重要性采样

重要性采样还有一个加权版本，分为 Ordinary 的和 Weighted 的两种，其中的记法是一样的，记 为所有访问过 的集合， 为在 时刻之后到终止时刻之间的回报，那么Ordinary 版本的公式如下：

这个和前面的那个 every-visit 的很像，只不过加上了重要度采样比

而 weighted 版本如下：

如果式 中的分母为0则整个式子的值定义为0，相当于这个状态不会在目标策略中出现，那么其价值是没有衡量意义的。

误差和方差分析

Ordinary 版本的加权重要性采样是无偏的而 Weighted 的版本是有偏的（但是偏差渐进趋近于0），但是 Ordinary 版本的方式往往是无上界的，而 Weighted 的是 bounded 的

通常选择加权版本。

增量实现

假设有一个回报序列 对应的每一个都有一个权重 例如重要性采样里面的 那么需要估计的值是：

稍作变形可以得到：

其中的 的递推定义如下：

初始值

由此得到 off-policy 的增量实现算法：

off-policy 蒙特卡罗控制

前面提到了 on-policy 的蒙特卡罗控制，这里给出 off-policy 的版本：

这个和上面那个增量算法没有本质区别，只是每一步加了一个更新目标策略而已。

我个人的感觉，离线算法的好处是行为策略是不更新的，所以可以选择一个高效的行为策略更偏向于 exploration 这样可能得到的策略是更好的。

书上给出了离线算法的潜在问题，即如果在行为策略中，非贪婪的选择太多的话，会导致乘上那个重要性比例之后，值的占比很小，策略收敛的速度会很慢