【RL从入门到放弃】【六】

1、MC

上面动态规划都是基于modle的，也就是说里面的概率都是固定的，强化学习算法的精髓之一是解决无模型的马尔科夫决策问题

无模型的强化学习算法主要包括蒙特卡罗方法和时间差分方法

无modle的RL和基于modle的RL的思想是一致的，即策略评估和策略改善

学习蒙特卡罗方法之前，我们先梳理强化学习的研究思路。首先，强化学习问题可以纳入马尔科夫决策过程中，这方面的知识已在第2章阐述。在已知模型的情况下，可以利用动态规划的方法解决马尔科夫决策过程。第3章，阐述了两种动态规划的方法：策略迭代和值迭代。这两种方法可以用广义策略迭代法统一：即先进行策略评估，也就是计算当前策略所对应的值函数，再利用值函数改进当前策略。

动态规划中值函数的计算方法：

动态规划方法计算状态 处的值函数时利用了模型 ，但在无模型强化学习中，模型是未知的。无模型的强化学习算法要想利用策略评估和策略改善的框架，必须采用其他的方法评估当前策略（计算值函数）

我们回到值函数最原始的定义公式

动态规划的方法是利用模型计算该期望。在没有模型时，我们可以采用蒙特卡罗的方法计算该期望，即利用随机样本估计期望

在计算值函数时，蒙特卡罗方法是利用经验平均代替随机变量的期望

经验

当要评估智能体的当前策略时，我们可以利⽤策略产⽣很多次试验，每次试验都是从任意的初始状态开始直到终止，比如一次试验（anepisode）为

计算一次试验中状态 S处的折扣回报返回值为

那么“经验”就是指利用该策略做很多次试验，产生很多幕数据，如图4.3

平均

利用蒙特卡罗方法求状态处的值函数时，又可以分为第一次访问蒙特卡罗方法和每次访问蒙特卡罗方法

第一次访问蒙特卡罗方法

是指在计算状态S处的值函数时，只利用每次试验中第一次访问到状态S时的返回值。如图4.3中第一次试验所示，计算状态S处的均值时只利用 ，因此第一次访问蒙特卡罗方法的计算公式为

每次访问蒙特卡罗方法

每次访问蒙特卡罗方法是指在计算状态s处的值函数时，利用所有访问到状态S时的回报返回值，即

根据大数定律【https://baike.baidu.com/item/%E5%A4%A7%E6%95%B0%E5%AE%9A%E5%BE%8B/410082?fr=aladdin】

由于智能体与环境交互的模型是未知的，蒙特卡罗方法是利用经验平均来估计值函数，能否得到正确的值函数，则取决于经验——因此，如何获得充足的经验是无模型强化学习的核心所在

探索性初始化

在动态规划方法中，为了保证值函数的收敛性，算法会逐个扫描状态空间中的状态。无模型的方法充分评估策略值函数的前提是每个状态都能被访问到，因此，在蒙特卡洛方法中必须采用一定的方法保证每个状态都能被访问到，方法之一是探索性初始化

探索性初始化是指每个状态都有一定的几率作为初始状态

第2步中，每次试验的初始状态和动作都是随机的，以保证每个状态行为对都有机会作为初始状态。在评估状态行为值函数时，需要对每次试验中所有的状态行为对进行估计；

如何保证在初始状态不变的同时，精心设计策略可以保证每个状态行为对被访问到？策略需要满足什么条件呢？

答：策略必须是温和的，即对所有的状态s和a

也就是说，温和的探索策略是指在任意状态下，采用动作集中每个动作的概率都大于零。典型的温和策略是

蒙特卡罗策略改善

蒙特卡罗方法利用经验平均估计策略值函数。估计出值函数后，对于每个状态，它通过最大化动作值函数来进行策略的改善。即

递增计算均值

同策略MC强化学习方法

若行动策略和评估及改善的策略是同一个策略，我们称为on-policy

异策略MC强化学习方法

若行动策略和评估及改善的策略是不同的策略，我们称为off-policy

用于异策略的目标策略 和行动策略 并非任意选择的，而是必须满足一定的条件。这个条件是覆盖性条件，即行动策略 产生的行为覆盖或包含目标策略 产生的行为。：满足 的任何（s,a）均满⾜ 。

重要性采样

首先当然是我们本来没办法sample from p，这个是我们看到的，IS将之转化为了从q分布进行采样；同时IS有时候还可以改进原来的sample，比如说:

可以看到如果我们直接从p进行采样，而实际上这些样本对应的f(x)都很小，采样数量有限的情况下很有可能都无法获得f(x)值较大的样本，这样评估出来的期望偏差会较大；

而如果我们找到一个q分布，使得它能在f(x)∗p(x)较大的地方采集到样本，则能更好地逼近[Ef(x)]，因为有Importance Weight控制其比重，所以也不会导致结果出现过大偏差。

所以选择一个好的p也能帮助你sample出来的效率更高，要使得f(x)p(x)较大的地方能被sample出来。

重要性权重

普通的重要性采样求积分如方程（4.7）所示为

在异策略方法中，行动策略u即用来产生样本的策略，所产生的轨迹概率分布相当于重要性采样中的q[z]，用来评估和改进的策略 所对应的轨迹概率分布为p[z] ，因此利用行动策略u所产生的累积函数返回值来评估策略 时，需要在累积函数返回值前面乘以重要性权重。
在目标策略 下，一次试验的概率为

在行动策略u下，相应的试验的概率为

重要性权重

普通重要性采样的值函数估计

加权重要性采样

但是，基于重要性采样的积分估计的方差无穷大。这是因为原来的被积函数乘了一个重要性权重，改变了被积函数的形状及分布。尽管被积函数的均值没有发生变化，但方差明显发生改变。

在重要性采样中，使用的采样概率分布与原概率分布越接近，方差越小。然而，被积函数的概率分布往往很难求得、或很奇怪，因此没有与之相似的简单采样概率分布，如果使用分布差别很大的采样概率对原概率分布进行采样，方差会趋近于无穷大。一种减小重要性采样积分方差的方法是采用加权重要性采样：

 

加权重要性采样值函数估计为

异策略每次访问蒙特卡罗算法的伪代码

 

mc实例

 

2、时间差分

 

无模型RL的基本方法是蒙特卡罗方法，时间差分方法也是无模型的RL的方法，时间差分（Temporal-Difference，简称TD）方法是另一种无模型强化学习方法，也是强化学习理论中最核心的内容。与动态规划的方法和蒙特卡罗的方法相同，时间差分方阿法的主要不同在于值函数的估计

如图5.2所示为动态规划的方法计算值函数。

下面的式（5.1）是值函数估计的计算公式，从中可以看到，用动态规划方法（DP）计算值函数时用到了当前状态s的所有后继状态s’处的值函数。值函数的计算用到了bootstrapping的方法。此处是指当前值函数的计算用到了后继状态的值函数。

要特别注意的是，此处后继的状态是由模型公式

由模型公式和动作集，可以计算状态s所有的后继状态s’。当没有模型时，后继状态无法全部得到，只能通过试验和采样的方法每次试验得到一个后继状态s’。

无模型时，我们可以采用蒙特卡罗的方法利用经验平均来估计当前状态的值函数，用它计算值函数的过程如图5.3所示

蒙特卡罗方法利用经验平均估计状态的值函数。此处的经验是指一次试验，一次试验要等到终止状态出现才结束。公式
（5.2）中的 G（t）是状态St 处的折扣累积回报值。

相比于动态规划的方法，蒙特卡罗的方法需要等到每次试验结束，所以学习速度慢，学习效率不高。通过对两者的比较，我们很自然地会想到：能不能借鉴动态规划bootstrapping的方法，在试验未结束时就估计当前的值函数呢？

答案是肯定的，这是时间差分方法的精髓。时间差分方法结合了蒙特卡罗的采样方法（即做试验）和动态规划方法的bootstrapping（利⽤后继状态的值函数估计当前值函数），它的计算过程如图5.4所

值函数

TD目标:

TD偏差

3、DP\MC\TD区别和联系

值函数

DP：

蒙特卡罗的方法使用的是值函数最原始的定义，该方法利用所有回报的累积和估计值函数

MC:

TD：

动态规划方法和时间差分方法则利用一步预测方法计算当前状态值函数，它俩的共同点是利用了bootstrapping 方法；不同的是，动态规划方法利用模型计算后继状态，时间差分方法利用试验得到后继状态。

期望和方差

MC是无偏估计，但是方差比较大：蒙特卡罗方法中的返回值 ，其期望便是值函数的定义，因此蒙特卡罗方法是无偏估计。但是，蒙特卡罗方法每次得到的G(t)值要等到最终状态出现，在这个过程中会经历很多随机的状态和动作，每次得到的G(t)随机性很大，因此尽管期望等于真值，但方差无穷大

时间差分方法的TD目标为 若采用真实值，则TD估计也是无偏估计，然而在试验中采的也是估计值，因此时间差分估计方法属于有偏估计。与蒙特卡罗方法相比，时间差分方法只用到了一步随机状态和动作，因此TD目标的随机性比蒙特卡罗方法中的G(t)要小，相应的方差也比蒙特卡罗方法中的方差小。

TD实例