蒙特卡洛方法求解：

由于动态规划法需要在每一次回溯更新某一个状态的价值时，回溯到该状态的所有可能的后续状态。导致对于复杂问题计算量很大。同时很多时候，我们连环境的状态转化模型PP都无法知道，这时动态规划法根本没法使用。这时需要使用蒙特卡洛方法

动态规划法中，强化学习的两个问题里模型状态转化概率矩阵P始终是已知的，即MDP已知，对于这样的强化学习问题，我们一般称为基于模型的强化学习问题。

不基于模型的强化学习问题了。它的两个问题一般的定义是：

预测问题，即给定强化学习的5个要素：状态集S, 动作集A, 即时奖R，衰减因子γ,  给定策略π， 求解该策略的状态价值函数v(π)

控制问题，也就是求解最优的价值函数和策略。给定强化学习的5个要素：状态集S, 动作集A, 即时奖励R，衰减因子γ, 探索率ϵ, 求解最优的动作价值函q∗和最优策略π∗

蒙特卡罗法通过采样若干经历完整的状态序列(episode)来估计状态的真实价值。所谓的经历完整，就是这个序列必须是达到终点的。比如下棋问题分出输赢，驾车问题成功到达终点或者失败。有了很多组这样经历完整的状态序列，我们就可以来近似的估计状态价值，进而求解预测和控制问题了。

从特卡罗法法的特点来说，一是和动态规划比，它不需要依赖于模型状态转化概率。二是它从经历过的完整序列学习，完整的经历越多，学习效果越好。

蒙特卡罗法求解强化学习预测：

一个给定策略π的完整有T个状态的状态序列如下：

每个状态的价值函数等于所有该状态收获的期望，同时这个收获是通过后续的奖励与对应的衰减乘积求和得到。那么对于蒙特卡罗法来说，如果要求某一个状态的状态价值，只需要求出所有的完整序列中该状态出现时候的收获再取平均值即可近似求解，也就是：

这个平均的意义在于，有很多条这样的状态序列，在状态序列的意义下平均

有几个点可以优化考虑。

　　　　第一个点是同样一个状态可能在一个完整的状态序列中重复出现，那么该状态的收获该如何计算？有两种解决方法。第一种是仅把状态序列中第一次出现该状态时的收获值纳入到收获平均值的计算中；另一种是针对一个状态序列中每次出现的该状态，都计算对应的收获值并纳入到收获平均值的计算中。两种方法对应的蒙特卡罗法分别称为：首次访问(first visit) 和每次访问(every visit) 蒙特卡罗法。第二种方法比第一种的计算量要大一些，但是在完整的经历样本序列少的场景下会比第一种方法适用。

第二个点是累进更新平均值（incremental mean)。在上面预测问题的求解公式里，我们有一个average的公式，意味着要保存所有该状态的收获值之和最后取平均。这样浪费了太多的存储空间。一个较好的方法是在迭代计算收获均值，即每次保存上一轮迭代得到的收获均值与次数，当计算得到当前轮的收获时，即可计算当前轮收获均值和次数。通过下面的公式就很容易理解这个过程：

有时候，尤其是海量数据做分布式迭代的时候，我们可能无法准确计算当前的次数N(St),这时我们可以用一个系数α来代替，即

蒙特卡罗法求解强化学习控制问题：

蒙特卡罗法求解控制问题的思路和动态规划价值迭代的的思路类似，和动态规划比，蒙特卡罗法不同之处体现在三点：一是预测问题策略评估的方法不同，这个第三节已经讲了。第二是蒙特卡罗法一般是优化最优动作价值函数q∗，而不是状态价值函数v∗。三是动态规划一般基于贪婪法更新策略。而蒙特卡罗法一般采用ϵ−贪婪法更新。

ϵϵ−贪婪法通过设置一个较小的ϵ值，使用1−ϵ的概率贪婪地选择目前认为是最大行为价值的行为，而用ϵ的概率随机的从所有m 个可选行为中选择行为。用公式可以表示为：

可以避免动态规划求解过于复杂，同时还可以不事先知道环境转化模型，因此可以用于海量数据和复杂模型。但是它也有自己的缺点，这就是它每次采样都需要一个完整的状态序列。如果我们没有完整的状态序列，或者很难拿到较多的完整的状态序列，这时候蒙特卡罗法就不太好用了， 也就是说，我们还需要寻找其他的更灵活的不基于模型的强化问题求解方法

时序差分（TD）方法：

蒙特卡罗法中计算状态收获的方法是：

对于时序差分法来说，我们没有完整的状态序列，只有部分的状态序列，回顾贝尔曼方程：

称为TD误差

这样我们只需要两个连续的状态与对应的奖励，就可以尝试求解强化学习问题了

时序差分TD的预测问题求解：

和蒙特卡罗法类似，但是主要有两个不同点。一是收获Gt的表达式不同

二是迭代的式子系数稍有不同

由于在时序差分我们没有完整的序列，也就没有对应的次数NSt),一般就用一个[0,1]的系数α代替。这样时序差分的价值函数迭代式子是：

一是时序差分法在知道结果之前就可以学习，也可以在没有结果时学习，还可以在持续进行的环境中学习，而蒙特卡罗法则要等到最后结果才能学习，时序差分法可以更快速灵活的更新状态的价值估计，这在某些情况下有着非常重要的实际意义。

二是时序差分法在更新状态价值时使用的是TD 目标值，即基于即时奖励和下一状态的预估价值来替代当前状态在状态序列结束时可能得到的收获，是当前状态价值的有偏估计，而蒙特卡罗法则使用实际的收获来更新状态价值，是某一策略下状态价值的无偏估计，这一点蒙特卡罗法占优。

三是虽然时序差分法得到的价值是有偏估计，但是其方差却比蒙特卡罗法得到的方差要低，且对初始值敏感，通常比蒙特卡罗法更加高效。

从上面的描述可以看出时序差分法的优势比较大，因此现在主流的强化学习求解方法都是基于时序差分的。后面的文章也会主要基于时序差分法来扩展讨论。

n步时序差分：

能不能向前两步呢，这时我们的收获GT的近似表达式为：

n步时序差分收获

n步时序差分就等价于蒙特卡罗法

n到底是多少步好呢？如何衡量n的好坏呢？

n步时序差分选择多少步数作为一个较优的计算参数是需要尝试的超参数调优问题。为了能在不增加计算复杂度的情况下综合考虑所有步数的预测，我们引入了一个新[0,1]的参数λ，定义λ−收获是n从1到∞所有步的收获乘以权重的和。每一步的权重是(1−λ)λn−1，这样λ−收获的计算公式表示为：

进而

当λ=0 时,就是第二节讲到的普通的时序差分法，当λ=1 时,就是蒙特卡罗法。