强化学习数学基础（3）

回顾

回顾上一章节，我们介绍了policy iteration和value iteration两种求解最优贝尔曼最优等式的方法。它们主要的区别在于求解 时不同，policy iteration在policy evaluation步骤中求解的是state value，而value iteration中的value update步骤中只是对 的一次迭代，不保证满足贝尔曼等式，因此，其不能被称为state value。

在我们之前的章节，我们所介绍的系统的都是model-based的，即我们掌握系统的物理模型，掌握系统的概率转移，包括奖赏概率 和状态转移 。但这种情况在真实世界中是较少的，更多是model-free式的系统。那么在model-free的环境中，如何求解贝尔曼最优等式呢？这是我们这章所要介绍的内容。

MC RL algorithm

Monte carlo estimation

如何在不掌握模型的情况下去估计一些事情呢？例如估计抛一个硬币正面朝上的概率，显然，就是通过不断的实验，统计其中正面向上的次数，再除以总次数就得到正面朝上概率的估计。这正是蒙特卡洛估计（Monte carlo estimation）的直观例子，它是model-free情况下进行估计的主要工具。

蒙特卡洛估计的数学基础是什么呢？大数定律！

对于随机变量 ，假设 是iid样本， 为其平均值，那么：

因此，平均值是期望的无偏估计；在抛硬币的例子中，由于满足伯努利分布，事件期望就等于“正面向上的概率”，因此，平均值即统计正面向上次数除以总次数就是概率的无偏估计；

观察方差，当 趋向无穷，其平均值方差趋向于0，就得到了一个确定的值。因此，该定理能够保证蒙特卡洛估计的合理性。

MC basic RL algorithm

本节介绍如何将MC应用于强化学习算法中，回顾求解贝尔满最优等式的policy iteration算法，包括policy iteration和policy improvement两个步骤；其elementwise form如下:

因此，可以看出，我们其实最终是希望得到 ，在policy evaluation 中计算state value也是为了计算该项；

回顾 的原始定义？

即从 这一state-action pair出发所能得到的return的期望；

基于所介绍的MC方法，估计该期望，我们则需要从 出发，遵循 策略，产生episode；计算该episode的return记为 ；重复以上步骤，得到 集合，计算其平均值作为为 的估计。

这也是最简单的MC basis的强化学习算法，但现实中是不work的，这里介绍是为了掌握这类方法的最核心思想，以快速学习基于该方法所衍生的各种变种方法。

MC exploring Starts

上面介绍了MC basic算法，我们说它不work是因为它太低效了；对于每一个state-action对，都需要重复模拟，生成很多episode，以得到较为准确的估计值。这种数据利用方式也被称为initial-visit method。

那如何更高效的利用数据呢？

考虑一个episode：

• 以上例说明，initial-visit指我需要估计 ，则每次从头开始进行模拟；换一个state-action pair则需要重新进行；
• 更高效的数据利用方法指这一条episode，不仅用其估计最开始的 ，它还能被估计 （只需要计算其接下来的return）；这类方法可以被分为first-visit method和every-visit method；
• first-visit method指对一个state-action pair，只取其在该episode第一次出现的位置进行估计；而every-visit method则是出现几次，就会获得对应的return值；

MC exploring starts就是对每一条episode都会进行 的估计，然后进行policy improvement。但是一个episode理论上并不能准确地估计出action value，那么该方法是否合理？这是可以的，因为极端情况，value iteration这种只迭代一次的都可以，或者我们上一章介绍的truncated policy iteration也是不充分迭代，都不妨碍其方法的有效性。

MC -Greedy

即使MC exploring starts能大幅提高数据的利用效率，但仍然很难遍历到每一个state-action pair。遍历不到的，就需要以该state-action pair从头开始（这也是exploring starts的由于）。数学语言描述，即在每一个state 下，选择 中任何一个动作的概率都大于0，这也被称为soft policy。MC -Greedy算法正是一种soft policy。具体如下：

其中 ， 表示动作空间集合数量；

其实， 正是平衡exploitation和exploration的工具，当 则策略退化为greedy策略；当 则是完全的探索。

相比于greedy策略，其优势在于具有很强的探索性，以至于不需要满足exploring starts条件；劣势在于，得到的策略往往不是最优策略，最终得到的optimal也只是在所有 greedy policies中的最优。因此，注意 不能太大。

总结：在本章节中，我们第一次进入model-free的世界；并介绍了model-free设定下的重要估计工具——monte carlo算法。其理论基础在于大数定律，为了提高数据利用效率，我们在MC basic的基础上进一步引入MC exploring starts和MC greedy算法，其中 greedy通过 平衡探索性和利用。