强化学习基础 第三讲 蒙特卡罗方法
上一节课我们讲了已知模型时，利用动态规划的方法求解马尔科夫决策问题。从这节课开始，我们讲无模型的强化学习算法。
图3.1 强化学习方法分类
解决无模型的马尔科夫决策问题是强化学习算法的精髓。如图3.1所示，无模型的强化学习算法主要包括蒙特卡罗方法和时间差分方法。这一节我们先讲蒙特卡罗的方法。
在讲解蒙特卡罗方法之前，先梳理一下整个强化学习研究思路。首先强化学习问题可以纳入到马尔科夫决策过程中，这方面的知识已经在第一讲给出。若已知模型时，马尔科夫决策过程可以利用动态规划的方法来解决。之所以讲动态规划的方法是因为动态规划的思想是无模型强化学习研究的根源。在上一讲中，我们讲了动态规划的方法包括策略迭代、值迭代。这两种方法可以用广义策略迭代方法来统一：即先对当前策略进行策略评估，也就是说计算出当前策略所对应的值函数；然后，利用值函数改进当前策略。无模型的强化学习基本思想也是如此，即：策略评估和策略改善。
图3.2 值函数计算图
在动态规划的方法中，值函数的计算方法如图3.2为：
动态规划方法计算状态处的值函数时利用了模型 而在无模型强化学习中，模型是未知的。无模型的强化学习算法要想利用策略评估和策略改善的框架，必须采用其他的方法对当前策略进行评估（计算值函数）。
我们回到值函数最原始的定义公式，在第一讲中，我们已经给出了值函数的定义：
状态值函数和行为值函数的计算实际上是计算返回值的期望。如图3.2，动态规划的方法是利用模型对该期望进行计算。在没有模型时，我们可以采用蒙特卡罗的方法计算该期望，即利用随机样本来估计期望。在计算值函数时，蒙特卡罗方法是利用经验平均代替随机变量的期望。此处，我们要理解两个词，何为经验？何为平均。
首先看何为经验：
当要评估智能体的当前策略时，我们可以利用策略产生很多次试验，每次试验都是从任意的初始状态开始直到终止状态，比如一次试验(an
episode)为： 计算一次试验中状态处的折扣回报返回值为：
所谓经验，是指利用该策略做很多次试验，产生很多幕数据。这里一幕是一次试验的意思。如图3.3所示
图3.3
蒙特卡罗中的经验
再来看什么是平均：
这个概念很简单，平均就是求均值。不过，利用蒙特卡罗方法求状态处的值函数时，又可以分为第一次访问蒙特卡罗方法和每次访问蒙特卡罗方法。
第一次访问蒙特卡罗方法是指，在计算状态s处值函数时，只利用每次试验中第一次访问到状态s时的返回值。如图3.3中第一次试验所示，计算状态处的均值时只利用 。因此第一次访问蒙特卡罗方法的计算公式为：
每次访问蒙特卡罗方法是指，在计算状态处的值函数时，利用所有访问到状态时的回报返回值，即：
根据大数定律：
探索的必要性：
由于不知道智能体与环境交互的模型，蒙特卡罗方法是利用经验平均来估计值函数。能否得到正确的值函数，取决于经验。如何获得充足的经验是无模型强化学习的核心所在。
在动态规划方法中，为了保证值函数的收敛性，算法会对状态空间中的状态进行逐个扫描。无模型的方法充分评估策略值函数的前提是每个状态都能被访问到。因此，在蒙特卡洛方法中必须采用一定的方法保证每个状态都能被访问到。其中一种方法是探索性初始化。
探索性初始化：
所谓探索性初始化是指每个状态都有一定的几率作为初始状态。在给出基于探索性初始化的蒙特卡罗方法前，我们还需要给出策略改进方法，以及便于进行迭代计算的平均方法。
蒙特卡罗策略改进：
蒙特卡罗方法利用经验平均对策略值函数进行估计。当值函数被估计出来后，对于每个状态 ，通过最大化动作值函数，来进行策略的改进。即：
递增计算平均的方法：
(3.4)
图3.4 探索性初始化蒙特卡罗方法
如图3.4为探索性初始化蒙特卡罗方法的伪代码。需要注意的是：
（1）第2步中，每次试验的初始状态和动作都是随机的，以保证每个状态行为对都有机会作为初始化。在进行状态行为对值函数评估时，需要对每次试验中所有的状态行为对进行估计。
（2）第3步完成策略评估，第4步完成策略改进。
我们再讨论一下探索性初始化：
在探索性初始化中，迭代每一幕时，初始状态是随机分配的，这样可以保证迭代过程中每个状态行为对都能被选中。它蕴含着一个假设，即：假设所有的动作都被无限频繁选中。对于这个假设，有时很难成立，或无法完全保证。
我们会问，如何保证初始状态不变的同时，又能保证报个状态行为对可以被访问到？
答案是：精心地设计你的探索策略，以保证每个状态都能被访问到。
可是如何精心地设计探索策略？符合要求的探索策略是什么样的？
答案是：策略必须是温和的，即对所有的状态 和 满足： 。也就是说，温和的探索策略是指在任意状态下，采用动作集中每个动作的概率都大于零。典型的温和策略是 策略，即：
根据探索策略（行动策略）和评估的策略是否是同一个策略，蒙特卡罗方法又分为on-policy和off-policy.
若行动策略和评估及改善的策略是同一个策略，我们称之为on-policy,可翻译为同策略。
若行动策略和评估及改善的策略是不同的策略，我们称之为off-policy,
可翻译为异策略。
接下来我们重点理解这on-policy方法和off-policy方法。
On-policy: 同策略是指产生数据的策略与评估和要改善的策略是同一个策略。比如，要产生数据的策略和评估及要改进的策略都是策略。其伪代码如图3.5所示
图3.5 同策略蒙特卡罗强化学习
如图3.5产生数据的策略以及进行评估和改进的策略都是策略。
Off-policy:
异策略是指产生数据的策略与评估和改善的策略不是同一个策略。我们用表示用来评估和改进的策略，用 表示产生样本数据的策略。
异策略可以保证充分的探索性。例如用来评估和改进的策略是贪婪策略，用于产生数据的探索性策略为探索性策略，如策略。
用于异策略的目标策略和行动策略并非任意选择的，而是必须满足一定的条件。这个条件是覆盖性条件即：行动策略产生的行为覆盖或包含目标策略产生的行为。利用式子表示即为：满足 的任何 均满足 。
利用行为策略产生的数据评估目标策略需要利用重要性采样方法。下面，我们来介绍重要性采样。
图3.6 重要性采样
我们利用图3.6来描述重要性采样的原理。重要性采样来源于求期望：
如图3.6, 当随机变量z的分布非常复杂时，无法利用解析的方法产生用于逼近期望的样本，这时，我们可以选用一个概率分布很简单，产生样本很容易的概率分布 ，比如正态分布。原来的期望可变为：
(3.7)
定义重要性权重： ，普通的重要性采样求积分如方程(3.7)所示为：
(3.8)
由式(3.7)可以知道，基于重要性采样的积分估计为无偏估计，即估计的期望值等于真实的期望。但是，基于重要性采样的积分估计的方差无穷大。这是因为，原来的被积函数乘上了一个重要性权重，这就改变了被积函数的形状及分布。尽管被积函数的均值没有发生变化，但方差明显发生改变。
在重要性采样中，使用的采样概率分布与原概率分布越接近，方差越小。然而，被积函数的概率分布往往很难求得，或很奇怪，没有简单地采样概率分布能与之相似，如果使用分布差别很大的采样概率对原概率分布进行采样，方差会趋近于无穷大。
一种减小重要性采样积分方差的方法是采用加权重要性采样：
(3.9)
在异策略方法中，行动策略即用来产生样本的策略，所产生的轨迹概率分布相当于重要性采样中的，用来评估和改进的策略所对应的轨迹概率分布为，因此利用行动策略所产生的累积函数返回值来评估策略时，需要在累积函数返回值前面乘以重要性权重。
在目标策略下，一次试验的概率为：
在行动策略下，相应的试验的概率为：
因此重要性权重为：
普通重要性采样，值函数估计为如图3.7所示：
图3.7 普通重要性采样计算公式
现在举例说明公式(3.11)中各个符号的具体含义。
图3.8 重要性采样公式举例解释
t是状态访问的时刻，是访问状态s相对应的那个试验的终止状态所对应的时刻。是状态s发生的所有时刻集合。
加权重要性采样值函数估计为：
最后给出异策略每次访问蒙特卡罗算法的伪代码：
需要注意的是：此处的软策略为策略，需要改进的策略为贪婪策略。
最后，总结一下：
本节重点讲解了如何利用MC的方法估计值函数。跟基于动态规划的方法相比，基于MC的方法只是在值函数估计上有所不同。两者在整个框架上是相同的，即对当前策略进行评估，然后利用学到的值函数进行策略改进。
重点理解on-policy 和off-policy的概念，学会利用重要性采样来评估目标策略的值函数