之前我们讲的都是model-based的方法，现在我们要讨论model-free的方法。在去掉模型时，我们要考虑的就是如何不用模型去估计一些量。这里最简单的思想就是蒙特卡洛估计。

假设我们有这么一个例子：投硬币。假设正面朝上X=1；负面朝上X=-1，我们希望计算E(X)。那么这里就有两种方法：

1.model-based。也就是说我们知道这个正反面的概率，即P(X=1)=P(X=-1)=0.5，这样就能轻松算出E(X)。可是这样的精确的概率模型大部分时候是没法知道的，所以我们也可以用第二种方法。

2.model-free。基本思想就是我做很多实验或者采样，得到了一个序列{x1，x2，……，xn}，这样均值就可以近似为：这就是蒙特卡洛估计的思想。当N越来越大，我们估计的E(X)会越来越精准。这里其实就应用了统计学的大数定理。大数定理见下：

这就是最基本的关于蒙特卡洛（Monte Carlo，MC）的思想。由此，我们将讲述三种算法：MC Basic，MC Exploring Starts，MC Epsilon()-Greedy。

MC Basic

要理解这个算法，核心是如何把policy iteration中的model-based模块替换掉，转化成model-free的。我们知道policy iteration分为两部分：一个是PE,一个是PI。在PI中，我们要更新策略，需要知道q值。因此，最重要的一步就是求解。而算q值呢，我们又有两个方法：

·1. 基于模型的表达式： ·2. 不基于模型的原始表达式：显然，我们可以使用后者，基于数据（data，samples or experiences(经验，强化学习专有名词)）去计算q值，从而实现向model-free RL的转变。以下便是q值的蒙特卡洛估计过程：

1.从(s，a)开始，根据策略,生成一个episode（是跟据目前策略的，不是瞎走的）；

2.得到这个episode的return，记作g(s，a)。这个g(s，a)便是的一个采样。

3.我们得到了一组episodes和，于是有：由此，我们的MC Basic algorithm就可以分为两步：

·Step 1：policy evaluation。

在这一步中，我们对每一个action-state pair（s，a）运行许多episodes，根据均值来估计q值。

·Step 2：policy improvement。

在这一步中，我们根据获得的q值更新greedy optimal policy。

这个算法和policy iteration algorithm很像，不同在于后者要求解，而前者直接估计q值。伪代码如下：

实际上MC Basic algorithm效率太低了（这是老师独自提的概念），他只是一个最核心的想法，并不足以应用到实践。在这个算法中，我们并不需要估计state value，否则又要依赖于模型去解action value了。

要估算q值，我们要采样episodes然后对return求平均。对于我们的grid world，episode length只有充分长才能让所有状态达到目标；如果太短，只有接近target的state会有正的value。

MC Exploring Starts

这个算法是对MC Basic的推广，动机是为了更有效地利用数据。考虑以下的一个episode：按照之前的方法我们只估计了q(s1，a2)，也就是只visit了这一个state-action pair。但是实际上，我们也可以visit其他的state-action pairs。我们不妨写的更清楚一些：这样就可以看出我们不仅可以从原始的episode估计出q(s1，a2)，还能把后续的子episode看成新的episode，估计出q(s2，a4)、q(s2，a3)……等。

在更新策略方面，也有两种方法。在MC-Basic里，我们是等待所有episode都出来后再估计平均return，这个等待的过程会有时间的耗费。第二种方法是得到一个episode后就改进策略，从而得到效率提升。下面是一段伪代码：

之前介绍过的这种思想框架都叫做GPI(generalized policy iteration)。在这段伪代码中，我们是从后往前算return。还是考虑下面的过程：如果我们从头往后算，就需要依次算各子episode的return。如果从后往前，我们先算(s5，a1)开始的return，之后乘个衰减系数再加上(s2，a3)的reward就是(s2，a3)开始的return了。

exploring starts中的exploring是指我们要探索每一个action，因为可能会有action是最优的却被忽略了，那么这就使得我们必须explore每一个(s,a)出发的episode。当然了，我们也可以visit其他的(s,a)来获得当前的(s,a)，但是这是依赖于策略和环境的，有可能访问不到当前(s,a)。为了解决这种问题，我们要引入soft policy，以及之后介绍的算法。

MC Epsilon()-Greedy

soft policy简而言之就是对每一个action都有可能去选择。我们说对一个state，采取的action可以是deterministic的也可以是stochastic的。这个算法便是stochastic的。假如我们的episode足够长，那么只要从一个或几个state-action pair出发，就能经过所有的state-action。Epsilon()-Greedy策略选择的公式如下：其中， , 是状态s可以采取的action的数量。采取greedy action的概率一定是最大的，因为有：我们为什么要用这个算法？因为我们要平衡exploitation和exploration，这是RL中两个词汇，前者是指剥削，意为充分利用，就是我知道哪个action的value是最大的我就采取它；后者是指我虽然知道某个action能给我带来很多reward，但是我现在信息可能不完备，我应该探索一下别的action，可能其他action也是非常好的。

对于这个算法，如果，那么它就变的greedy，exploitation的比重更大；反之，就变成一个均匀分布，exploration就会变得更强。那么如何把Epsilon()-Greedy应用到MC-based RL中呢？我们之前的MC算法是这样的：我们要解决如下式子（policy improvement step）：这里的是所有可能的策略集合。最优策略是deterministic的。现在，这一步被变为：其中表示所有的-greedy policies的集合。最优策略就变成了：这就不需要exploring starts了。伪代码如下：

这个和前一个算法是基本一模一样的，一个是最优策略，一个是用的是every-visit，因为对于非常长的episode，很多state-action pair实际被访问了很多次，但只做一次估计的话是很浪费的。