咱们第三节介绍了基于模型的强化学习方法，动态规划计算值函数的公式。
$$
V_{π}(s)=\sum_{a \in A} π(a|s)(R_{s}^{a}+\gamma \sum_{s' \in S}P_{ss'}^{a}V_{π}(s')) \tag{4.1}
$$
这个公式看起来是不是十分熟悉，但是你有没有想到一个问题，在实际的环境中状态转移概率以及回报实际上是很难获得的。这种情况下使用动态规划就不太适合啦。这个时候就是本章要介绍的蒙特卡洛模拟的内容啦。
蒙特卡洛是统计模拟的方法。是一种基于概率与统计数值的计算方法。
蒙特卡洛
蒙特卡洛评估是通过学习智能体与环境交互的完整轨迹来轨迹值函数的。所谓的完整轨迹就是从一个起始的状态开始，使用某种策略一步步执行动作，直到结束的经验信息，包含所有的时间步骤、行为和回报。
使用蒙特卡洛方法的时候，对评估做了以下三点改变，因为是无模型方法，无法通过贝尔曼方程迭代值函数，因此通过统计很多轨迹中累积回报的平均数对值函数进行估计；求累积回报平均时采用增量更新的方式更新，避免批量更新方法对历史数据的存储，提高计算效率。为了方便直接从估计对象求解最优策略，蒙特卡洛将估计值函数V改成了值函数Q，这样通过贪心就能获取最优行为。
利用平均累积回报估计值函数
我们来看看值函数和行为值函数原始的定义公式是怎么样的，
$$
V_{π}(s)=E_{π}[G_t|S_{t}=s]=E_{π}[R_{t+1}+\gamma R_{t+1}+...+|S_t=s] \tag{4.2}
$$
$$
Q_{π}(s,a)=E_{π}[G_t | S_t=s, A_t=a]=E_{π}[\sum_{k=0} \gamma^{k} R_{t+k+1}|S_t=s,A_t=a] \tag{4.3}
$$
从上面这个计算过程，我们能够看出值函数和行为值函数的计算实际上就是计算累积回报的期望。在没有模型的时候我们就采用蒙特卡洛方法产生经验信息。这个经验信息能够帮我们推导出每个状态s的平均回报。
当要评估智能体当前策略π产生的多个轨迹时候，我们经常使用策略π产生多个轨迹，每个轨迹从任意的初始状态开始直到终止状态，多个完成的轨迹，计算每个轨迹在状态s处的返回值。
$$
G_{t}=r_{t+1}+\gamma r_{t+2}+... \tag{4.4}
$$
所以我们的轨迹可以表示成如下的状态。
$$
<s_{0},a_{0},G_{11},s_{1},a_{1},G_{12}...>
<s_{0},a_{0},G_{11},s_{1},a_{1},G_{12}...>
$$
初访法
初访法指的是只利用每个轨迹第一个访问到状态s时的累积回报。
$$
V_{s_1}=\frac{G_{12}+G_{2k}}{N(s_1)} \tag{4.5}
$$
每访法
每访法指的是每次经过s，都会计算入累积回报中。
$$
V_{s_1}=\frac{G_{12}+G_{1k}+G_{2k}}{N(s_1)} \tag{4.6}
$$
其中 $N(s_1)$是访问状态s的总次数。
增量式更新
蒙特卡洛在求平均值的时候采用的批量处理进行的，就是不是等到所有的值都出现以后才计算平均值，而是一批一批的计算平均值。也就是增量的。
$$
V_{k}=\frac{1}{k} \sum_{j=1}^{k} G_j=\frac{1}{k}(G_k+(k-1)V_{k-1})=V_{k-1}+\frac{1}{k}(G_k-V_{k-1}) \tag{4.7}
$$
当我们得到第k+1个采样数据$G_t$的时候就有如下的公式
$$
V_{k+1}(s_t)=V_{k}(s_t)+\frac{1}{k+1}(G_t-V_{k}(s_t)) \tag{4.8}
$$
可以简单写成
$$
V(s_t)=V(s_t)+\frac{1}{k+1}(G_t-V(s_t))
$$
这里的$\frac{1}{k+1}$是一个权重，我们可以把它替换成$\alpha$，如果$\alpha$越大表示更新步长越大，代表越靠后的累积回报越靠谱。
$$
V(s_t)=V(s_t) + \alpha (G_t-V(s_t))
$$
估计行为值函数Q代替轨迹值函数V
回忆一下我们在讲动态规划的时候，策略迭代算法估计的是值函数V，而最终的策略是通过行为值函数Q获得的，或者下个状态的V。当模型已知的时候，从值函数V到行为值函数Q有一个简单的换算公式。
$$
π'(s)=arg\ max\ Q(s,a) \tag{4.9}
$$
如果知道$P_{ss'}^{a}$和$R_{s}^{a}$，可以这样求解。
$$
π'(s)=arg\ max\ R_{s}^{a} + \gamma \sum_{s' \in S} P_{ss'}^{a} V(s')
$$
上述的过程也很容易通过蒙特卡洛的方式进行计算，假设使用初访法，那么就统计第一个访问到状态s并采取a动作的累积回报即可。
蒙特卡洛控制
这里我们需要说明的是我们根据模型能够产生行为值函数$Q(s_t, a_t)$,然后我们根据贪心的策略采取最大的行为走就可以，但是如果我们每次都采用贪心的策略就会存在一个问题，如果我们采样的经验不全，因为没有尝试挖掘更多的信息，那么我们可能陷入到一个现有样本空间的最优解，所以这个时候我们采取的是$\sigma$贪心，当到状态s的时候，我们以$1-\sigma$的概率执行最优动作，以$\sigma$的概率随机采取一个动作，假设有m个行为数，那么最优的行为被选中的概率是$1-\sigma+\frac{\sigma}{m}$,而非最优的动作的概率是$\frac{\sigma}{m}$。
离线策略和在线策略
在线蒙特卡洛策略就是指产生数据的策略和要评估改进的策略是同一个策略。其本质思想是遵循一个已有的策略进行采样，根据样本数据中回报更新值函数。最后根据更新的值函数优化已有的策略，以得到更优的策略。
而离线策略就是产生数据的策略和评估改进的策略不是同一个策略。其根本思想是虽然有了一个原始的策略，但是不针对这个原始策略进行采样，而是基于另一个策略进行采样。这另一个策略可以学到的，也可以是人工总结的。观察这类策略的行为和回报，并根据这些回报评估和赶紧原始的策略。
离线策略的重要性采样
在在线的蒙特卡洛里，产生的数据策略和评估改进都是引入了$\sigma$贪心策略，而引入$\sigma$贪心策略目的是产生更多的数据，但是具有一定的随机性，不适合作为最终的策略使用。可考虑策略评估的时候引进了随机性，而在策略改进时，改进的是原始非$\sigma$贪心策略。基于这个思想就有了离线的蒙特卡洛方法。
而在离线的蒙特卡洛中，使用重要性采样的方法。通过随机策略才生数据，对原始的贪心策略进行评估和改进。其中采样数据的策略叫做行为策略，用π’表示，评估的是原始策略用π表示。
一般的，假设有p，q两个不同的分布，函数f(x)在概率p下的期望表示为
$$
E(f)=\int_{x} p(x) f(x)dx \tag{4.10}
$$
可以使用概率分布p上采样$[x_1, x_2,..,x_m]$来轨迹f的期望。
$$
E(f)=\frac{1}{m} \sum_{i=1}^{m} f(x_i) \tag{4.11}
$$
我们也能看成是函数$\frac{p(x)}{q(x)}f(x)$在q分布下的期望
$$
E(f)=\int p(x)f(x)dx=\int q(x) \frac{p(x)}{q(x)}f(x) \tag{4.12}
$$
使用$[x_1’, x_2’,..,x_m’]$来估计。当随机变量f(x)的分布无法产生样本，就可以考虑使用一个已知的比较简单的分布来逼近随机变量f(x)的期望。
回到我们的问题上，分别用π和π'产生两条采样轨迹。两条轨迹的区别是每个状态行为对被采样的概率不同。
使用策略π的采样轨迹评估策略π，实际上是求助状态行为对(s,a)的累积回报期望，行为值函数为
$$
Q(s,a)=\frac{1}{m} \sum_{i=1}^{m} G_{i} \tag{4.13}
$$
$G_{i}$表示第i条轨迹上，自状态行为对(s,a)到结束的累积回报，若使用策略π’的采样轨迹来评估，就对累积回报加权得到
$$
Q(s,a)=\frac{1}{m} \sum_{i=1}^{m} \frac{P_{i}^{π}}{P_{i}^{π'}} G_{i} \tag{4.14}
$$
其中$P_{i}^{π}$和$P_{i}^{π'}$表示两个策略产生第i条轨迹的概率。
对于一条给定的轨迹，策略π产生轨迹的概率为
$$
P_{i}^{π}=\prod_{j=0}^{T-1} π(a_j|s_j)P_{s_j,s_{j+1}}^{a_j} \tag{4.15}
$$
同理π‘的也好求的。
$$
P_{i}^{π'}=\prod_{j=0}^{T-1} π'(a_j|s_j)P_{s_j,s_{j+1}}^{a_j} \tag{4.16}
$$
$$
\rho_{i}^{T}=\frac{P_{i}^{π}}{P_{i}^{π'}} \prod_{j=0}^{T-1} \frac{π(a_j|s_j)}{π'(a_j|s_j)} \tag{4.17}
$$
$\rho_{i}^{T}$称为重要采样比率，i表示第i轨迹，T为轨迹终止时刻。可见，原始策略和行为策略产生轨迹的比值转为两个策略的概率比值。
使用策略π'的采样轨迹评估策略π，增量式更新公式如下
$$
Q(s_t, a_t) <- Q(s_t, a_t)+\alpha(\prod_{j=0}^{T-1} \frac{π(a_j|s_j)}{π'(a_j|s_j)} G_t -Q(s_t, a_t)) \tag{4.18}
$$
你可能有个疑问，对于上面这个公式我在计算中是如何计算的呢？
首先我们来看 $\frac{π(a_j|s_j)}{π'(a_j|s_j)}$这个变量计算的过程中是什么含义呢？其实就是如下的解释
$$
\begin{equation}
p_{i}=\left\{
\begin{array}{lr}
1-\sigma+\frac{\sigma}{m}
, & \\
\frac{\sigma}{m}
\end{array}
\right.
\end{equation}
$$
$$
G_t=\sum_{i=t}^{T} \gamma^{i-t} r_i
$$
加权重要性采样离线蒙特卡洛
基于重要性的采样的积分是无偏估计，因此使用重要性采样进行策略评估时，得到的行为值函数的估计是无偏估计。然而由于进行计算的时候，对被积函数乘以一个重要性比率，使得被积函数方差发生了较大的变化。如果轨迹存在循环不终止的情况，对应的方差会变成无穷。为了解决采样方法的问题，就有了本节要说的加权重要性采样方法。
$$
E(f)=\frac{\sum_{i=1}^{m}\frac{p(x_i')}{q(x_i')}f(x_{i}')}{\sum_{i=1}^{m} \frac{p(x_{i}')}{q(x_{i}')}}
$$
与普通的重要性采样相比，分布由m变成了重要性采样比率之和 $\sum_{i=1}^{m} \frac{p(x_{i}')}{q(x_{i}')}$
用加权的重要性采样解决离线蒙特卡洛问题时，对应的行为值函数就如下。
$$
Q(s,a)=\frac{\sum_{i=1}^{m} \rho_{i}^{T} G_i}{\sum_{i=1}^{m} \rho_{i}^{T}}
$$
整个迭代公式就变成了
$$
Q_{m}(s,a)=Q_{m-1}(s,a)+\frac{\rho_{m}^{T}}{\sum_{i=1}^{m}\rho_{i}^{T}}(G_m-Q_{m-1}(s,a))
$$
而 $\frac{\rho_{m}^{T}}{\sum_{i=1}^{m}\rho_{i}^{T}}$就称为加权的重要性采样。