目录前言1. Outline2. Motivating example: Monte Carlo estimation结语参考前言学习赵老师讲授的强化学习的数学原理视频本篇文章记录第五讲 Part 1蒙特卡洛方法通过例子介绍蒙特卡洛记录个人学习笔记和大家一起分享交流videohttps://www.bilibili.com/video/BV1sd4y167NS1. OutlineOK这是我们的第五次课这次课我们将会介绍基于蒙特卡洛的强化学习方法下面是我们这个课程的地图。相信大家也比较熟悉了这次我们来到了第五章上次课我们介绍的是value iteration和policy iteration这两节课是什么关系呢上节课介绍的是model-based方法而这次课我们将介绍整个课程中的第一个model-free方法它们一个是依赖模型的一个是不依赖模型的。在开始之前我想说明两点第一点我们上节课介绍的policy iteration方法实际上是这一次课的基础。待会大家就会看到我们把policy iteration中依赖模型的部分替换为不需要模型的方法采样估计就得到了今天的算法。第二点我想说明的是在我们这门课当中我们把value iteration和policy iteration也统称为model-based reinforcement learning但更准确地说它们应该称为dynamic programming动态规划方法。近年来model-based reinforcement learningMBRL又重新兴起它研究的是什么呢例如先用数据估计出一个模型再基于这个模型进行强化学习。不过在本课程中我们仍统一把value iteration和policy iteration也称为model-based reinforcement learning方法。下面是我们这次课的大纲1. Motivating example2. The simplest MC-based RL algorithmAlgorithm: MC Basic3. Use data more efficientlyAlgorithm: MC Exploring Starts4. MC without exploring startsAlgorithm: MCε \varepsilonε-Greedy首先我会通过一个motivating example来介绍Monte Carlo Estimation的基本思想之后会介绍 3 个基于蒙特卡洛的强化学习的算法这三个算法分别称为MC Basic、MC Exploring Starts以及MCε \varepsilonε-Greedy这里的MC是 Monte Carlo蒙特卡洛的缩写。另外想强调的是这三个算法实际上是环环相扣的前面一个是后面一个的基础比如说MC Basic是最简单的基于蒙特卡洛的强化学习算法它简单到在实际当中是没法用的因为效率等各方面都比较差但它在揭示“如何去掉模型、不基于模型来实现强化学习”这一核心 idea 上非常关键。这个算法经过改进得到后续两个算法比如说考虑如何让数据的使用效率更高、如何去除exploring starts这一假设等。2. Motivating example: Monte Carlo estimation下面我们来看第一部分。其实从model-based的 reinforcement learning 过渡到model-free的 reinforcement learning最让人难以理解的应该就是如何在没有模型的情况下去估计一些量。这里有一个重要的方法思想—Monte Carlo Estimation。下面我通过这样一个例子来说明这个方法这个例子是什么呢就是掷硬币。假设我手上有一枚硬币我把它抛到空中然后硬币会落到我的手心这枚硬币要么是正面朝上要么是反面朝上然后我把这个结果表示为一个随机变量X XX如果它是正面朝上我就说X 1 X1X1如果它是反面朝上我就说X − 1 X-1X−1。所以我下面要求解的问题就是X XX的平均数也就是它的expectation即E [ X ] \mathbb{E}[X]E[X]是多少这里有两种方法第一种方法是基于模型的model-based。那就是随机变量X XX的probability distribution是已知的p ( X 1 ) 0.5 , p ( X − 1 ) 0.5 p(X1)0.5, \quad p(X-1)0.5p(X1)0.5,p(X−1)0.5比如说它正面朝上的概率是 0.5反面朝上的概率也是 0.5那expectation就可以直接按定义计算E [ X ] ∑ x x p ( x ) 1 × 0.5 ( − 1 ) × 0.5 0 \mathbb{E}[X] \sum_x xp(x) 1 \times 0.5 (-1) \times 0.5 0E[X]x∑​xp(x)1×0.5(−1)×0.50公式中x xx是取值p ( x ) p(x)p(x)是概率最后算出来是 0。这个方法非常简单。但是问题是这么精确的probability distribution模型我们可能无法知道这也是我们本次课要面对的问题所以我们能不能在没有模型的情况下也去估计呢其实答案也非常简单利用蒙特卡洛估计就行。它基本的思想就是掷硬币很多次做很多次实验、得到很多采样然后求它们的平均数。具体来说我们做N NN次实验假设结果分别为{ x 1 , x 2 , … , x N } \{ x_1,x_2,\ldots, x_N \}{x1​,x2​,…,xN​}然后把这些结果相加再除以N NN得到平均值记作x ˉ \bar{x}xˉ然后用x ˉ \bar{x}xˉ来近似E [ X ] \mathbb{E}[X]E[X]。即认为E [ X ] ≈ x ˉ 1 N ∑ j 1 N x j . \mathbb{E}[X] \approx \bar{x} \frac{1}{N} \sum_{j1}^N x_j.E[X]≈xˉN1​j1∑N​xj​.这个就是Monte Carlo Estimation 的一个基本的思想。那有的同学可能会说了你用一个平均数来近似E [ X ] \mathbb{E}[X]E[X]那是否精确呢当N NN比较小的时候这种近似实际上是不精确的但随着N NN逐渐增大这种近似会变得越来越精确上面这个图清晰地展示了出来。这个掷硬币任务总共做了 200 次真实的expectation是 0如果用最开始的两次结果做平均—前两次都是反面-1—平均值为负与真实值相差较大但随着数据越来越多平均数会越来越收敛到真实的 expectation。这种直观解释有很好的数学支撑那就是Law of Large Numbers大数定律[blog]具体是什么呢大数定律考虑随机变量X XX。假设{ x j } j 1 N \{x_j\}_{j1}^N{xj​}j1N​是X XX的独立同分布iid样本。令x ˉ 1 N ∑ j 1 N x j \bar{x} \frac{1}{N} \sum_{j1}^N x_jxˉN1​∑j1N​xj​为这些样本的均值。那么E [ x ˉ ] E [ X ] , Var [ x ˉ ] 1 N Var [ X ] . \begin{align*} \mathbb{E}[\bar{x}] \mathbb{E}[X], \\ \text{Var}[\bar{x}] \frac{1}{N} \text{Var}[X]. \end{align*}E[xˉ]Var[xˉ]​E[X],N1​Var[X].​因此x ˉ \bar{x}xˉ是E [ X ] \mathbb{E}[X]E[X]的一个无偏估计并且随着样本量N NN趋向于无穷大其方差将减小至零。具体来说假设有N NN个iid的样本iid即independent and identically distributed独立同分布然后用这些样本做平均得到x ˉ \bar{x}xˉ可以证明以下两个结论第一个结论如果把x j x_jxj​看作随机变量那么x ˉ \bar{x}xˉ也是随机变量可以对其求期望。它的期望等于真实的E [ X ] \mathbb{E}[X]E[X]—所以x ˉ \bar{x}xˉ是E [ X ] \mathbb{E}[X]E[X]的无偏估计。第二个结论x ˉ \bar{x}xˉ的variance是1 N Var [ X ] \frac{1}{N}\text{Var}[X]N1​Var[X]即X XX方差的1 N \frac{1}{N}N1​。那么显然当N NN趋向于无穷时方差1 N Var [ X ] \frac{1}{N}\text{Var}[X]N1​Var[X]趋向于 0方差趋向于 0 意味着x ˉ \bar{x}xˉ会收敛到一个常数而这个正是expectationE [ X ] \mathbb{E}[X]E[X]具体证明可以参考教材。所以通过这样一个例子其实我们就非常清晰地了解了蒙特卡洛估计的基本的思想。蒙特卡洛不仅可以用于掷硬币这样简单的任务凡是需要大量采样、再用实验结果进行近似的方法都可以称为蒙特卡洛估计方法。我们在这个课程当中为什么会需要考虑Monte Carlo Estimation就是因为我们是无模型的而Monte Carlo Estimation 恰好也不需要模型。我们为什么要考虑这个mean estimation为什么要用蒙特卡洛来估计 expectation就是因为state value和action value—如果大家还记得的话—它们的定义实际上就是expectation所以后面会用到。结语本讲第一部分正式拉开了 model-free 强化学习的序幕。通过掷硬币这个简单直观的例子我们掌握了 Monte Carlo Estimation 的核心思想当概率模型未知时不依赖模型的解析计算而是通过大量采样、求平均来估计期望值。大数定律为这一方法提供了坚实的数学保障—样本均值x ˉ \bar{x}xˉ是E [ X ] \mathbb{E}[X]E[X]的无偏估计且其方差随样本量N NN增大而趋于零因此采样越多、估计越精确。这一思想之所以对强化学习至关重要正是因为 state value 和 action value 本质上就是期望值而蒙特卡洛方法恰好提供了一条绕开模型的估计路径。接下来我们将看到如何把这一思想融入 policy iteration 的框架—只需将其中的模型依赖部分替换为基于采样的估计就能得到第一个 model-free 强化学习算法 MC Basic。参考https://www.bilibili.com/video/BV1sd4y167NShttps://github.com/MathFoundationRL/Book-Mathmatical-Foundation-of-Reinforcement-Learning