说明：本系列文章是我在学习了西湖大学赵世钰老师的《Mathematical Foundations of Reinforcement Learning》一书后的学习笔记，在B站上有赵老师的完整课程视频。

课程视频链接

PDF教材链接

本文代码链接

一、动因:

前文学习的算法都是在给定环境模型的情况下，才能计算最优策略，即需要知道。当我们不知道环境模型，或者环境模型过于复杂的情况下，我们只能依靠数据。环境模型和数据，二者必须有其一，否则我们无法获取最优策略。

二、MC Basic：

伪代码：

本算法基于policy iteration改造成model-free算法

• 初始化：

                给定任意策略。

• policy evalueation:

                从每一个出发，采样多个episode，计算discounted return，获得一个集合

                则，

• policy improvement:

                使用greedy方法更新策略

这里为什么是估计action value而不是估计state value呢？

        因为如果是估计state value，根据action value的定义，我们在策略更新的时候，仍然需要依赖使用环境模型来计算每一个action value。而MC是一个model free的算法。

• 用来估计均值的sample必须是独立同分布的。
• 在采样的时候，所有的episode采样需要足够长，才能准确的找到最优策略。不同环境下，这个长度需要测试确定。

三、MC Exploring Starts

1、更高效的利用sample

• 在MC Basic方法中，每个episode只利用了一次，用来计算出发点的return，我们称之为initial visit。
• 另外一种对sample利用率更高的方法是，采样一个足够长的episode，对其中每一步经过的(s,a)都计算对应的return，我们称之为every visit。

如果采样的episode足够长，那么环境中的每一个(s,a)都将被访问多次。

every visit方式采样得到的样本之间是相关的(不符合独立同分布)，因为每个(s,a)下，第二次访问开始的轨迹是第一次访问的一个子集。

如果同一个(s,a)的两次访问之间间隔较远，则相关性就不会很强。

2、更高效的更新策略

• 在MC Basic中，我们是等待同一个(s,a)下，所有的return计算完成后，再取均值来估算q值。
• 另一种方法是我们用一个return来近似q(s,a)。虽然这样并不精确，但可以每个episode更新一次策略。

这实际上和n-step policy iteration一样，每一个policy evaluation都计算一次q(s,a)，虽然这个结果并不准确，但任然有效。

3、epsilon-greedy

• 在利用every visit的时候，如果要充分的探索到每一个(s,a)很多次，在更新策略的时候就不可以用之前的greedy方法了。

• 这种方法的缺点是，当一个策略被更新后，那么agent将永远无法探索到的地方，和均值估计的方法相悖，最终估计偏差会很大，无法探索到更优的策略。
• 为了消除这个弊端，我们采用epislon-greedy方法，确保采样过程有足够的探索性，从公式可知，epsilon越大，策略探索性越强，反之相反。：

技巧：epislon-greedy方法虽然确保了足够的探索性，能够做到无偏估计，但是估计的方差会较大，导致即便找到了最优策略，每次迭代也会在最优策略附近反复震荡。可以每次迭代将epsilon乘以一个(0,1)之间的系数，逐渐减小epsilon，当策略越接近optimal的时候，探索性越小。

另外，episode越长，方差也会越大。

伪代码：