强化学习读书笔记 - 05 - 蒙特卡洛方法(Monte Carlo Methods)

强化学习读书笔记 - 05 - 蒙特卡洛方法(Monte Carlo Methods)

学习笔记: Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto c 2014, 2015, 2016

数学符号看不懂的,先看看这里:

蒙特卡洛方法简话

蒙特卡洛是一个赌城的名字。冯·诺依曼给这方法起了这个名字,增加其神秘性。 蒙特卡洛方法是一个计算方法,被广泛的用于许多领域,用于求值。 相对于确定性的算法,蒙特卡洛方法是基于抽样数据来计算结果。

蒙特卡洛方法的基本思路

蒙特卡洛方法的整体思路是:模拟 -> 抽样 -> 估值

示例: 比如:如何求\(\pi\)的值。一个使用蒙特卡洛方法的经典例子如下: 我们知道一个直径为1的圆的面积为\(\pi\)。 把这个圆放到一个边长为2的正方形(面积为4)中,圆的面积和正方形的面积比是:\(\frac{\pi}{4}\)。 如果可以测量出这个比值\(c\),那么\(\pi=c \times 4\)。 如何测量比值\(c\)呢?用飞镖去扎这个正方形。扎了许多次后,用圆内含的小孔数除以正方形含的小孔数可以近似的计算比值\(c\)。

说明: 模拟 - 用飞镖去扎这个正方形为一次模拟。 抽样 - 数圆内含的小孔数和正方形含的小孔数。 估值 - 比值\(c\) = 圆内含的小孔数 / 正方形含的小孔数

蒙特卡洛方法的使用条件

  • 环境是可模拟的 在实际的应用中,模拟容易实现。相对的,了解环境的完整知识反而比较困难。 由于环境可模拟,我们就可以抽样。
  • 只适合情节性任务(episodic tasks) 因为,需要抽样完成的结果,只适合有限步骤的情节性任务。

蒙特卡洛方法在强化学习中的用例

只要满足蒙特卡洛方法的使用条件,就可以使用蒙特卡洛方法。 比如:游戏类都适合:完全信息博弈游戏,像围棋、国际象棋。非完全信息博弈游戏:21点、麻将等等。

蒙特卡洛方法在强化学习中的基本思路

蒙特卡洛方法的整体思路是:模拟 -> 抽样 -> 估值

如何应用到强化学习中呢? 强化学习的目的是得到最优策略。 得到最优策略的一个方法是求\(v_{pi}(s), \ q_{pi}{s, a}\)。 - 这就是一个求值问题

结合通用策略迭代(GPI)的思想。 下面是蒙特卡洛方法的一个迭代过程:

  1. 策略评估迭代 1. 探索 - 选择一个状态(s, a)。 1. 模拟 - 使用当前策略\(\pi\),进行一次模拟,从当前状态(s, a)到结束,随机产生一段情节(episode)。 1. 抽样 - 获得这段情节上的每个状态(s, a)的回报\(G(s, a)\),记录\(G(s, a)\)到集合\(Returns(s, a)\)。 1. 估值 - q(s, a) = Returns(s, a)的平均值。 (因为状态(s, a)可能会被多次选择,所以状态(s, a)有一组回报值。)
  2. 策略优化 - 使用新的行动价值\(q(s, a)\)优化策略\(\pi(s)\)。

解释

  • 上述的策略评估迭代步骤,一般会针对所有的状态-行动,或者一个起始(\(s_0, a_0\))下的所有状态-行动。 这也说明持续探索(continual exploration)是蒙特卡洛方法的主题
  • 模拟过程 - 会模拟到结束。是前进式的,随机选择下一个行动,一直前进到结束为止。 因此可以看出蒙特卡洛方法需要大量的迭代,才能正确的找到最优策略。
  • 策略评估是计算行动价值(\(q(s, a)\))。 (也可以是状态价值,则\(\pi(s)\)为状态\(s\)到其下一个最大价值状态\(s‘\)的任意行动。) 计算方法: q(s, a) = average(Returns(s, a))

一些概念

  • Exploring Starts 假设 - 指有一个探索起点的环境。 比如:围棋的当前状态就是一个探索起点。自动驾驶的汽车也许是一个没有起点的例子。
  • first-visit - 在一段情节中,一个状态只会出现一次,或者只需计算第一次的价值。
  • every-visit - 在一段情节中,一个状态可能会被访问多次,需要计算每一次的价值。
  • on-policy method - 评估和优化的策略和模拟的策略是同一个。
  • off-policy method - 评估和优化的策略和模拟的策略是不同的两个。 有时候,模拟数据来源于其它处,比如:已有的数据,或者人工模拟等等。
  • target policy - 目标策略。off policy method中,需要优化的策略。
  • behavior policy - 行为策略。off policy method中,模拟数据来源的策略。

根据上面的不同情境,在强化学习中,提供了不同的蒙特卡洛方法。

  • 蒙特卡洛(起始点(Exploring Starts))方法
  • On-policy first visit 蒙特卡洛方法(for \(\epsilon\)-soft policies)
  • Off-policy every-visit 蒙特卡洛方法

蒙特卡洛(起始点(Exploring Starts))方法

On-policy first visit 蒙特卡洛方法(for \(\epsilon\)-soft policies)

Off-policy every-visit 蒙特卡洛方法

总结

蒙特卡洛方法和动态规划的区别

  1. 动态规划是基于模型的,而蒙特卡洛方法是无模型的。 注:基于模型(model-base)还是无模型(model-free)是看(状态或者行动)价值(\(G, v(s), q(s,a)\))是如何得到的? 如果是已知的、根据已知的数据计算出来的,就是基于模型的。 如果是取样得到的、试验得到的,就是无模型的。
  2. 动态规划的计算的,而蒙特卡洛方法的计算是取样性的(sampling)。 注:引导性的(bootstrapping)还是取样性的(sampling)是看(状态或者行动)价值(\(G, v(s), q(s,a)\))是如何计算的? 如果是根据其它的价值计算的,就是引导性的。 如果是通过在实际环境中模拟的、取样的,就是取样性的。 引导性和取样性并不是对立的。可以是取样的,并且是引导的。 如果价值是根据其它的价值计算的,但是有部分值(比如:奖赏)是取样得到的,就是无模型、取样的、引导性的。

解释: 上面两个区别,可以从计算状态价值\(v_{\pi}(s), q_{\pi}(s, a)\)的过程来看: 动态规划是从初始状态开始,一次计算一步可能发生的所有状态价值,然后迭代计算下一步的所有状态价值。这就是引导性。 蒙特卡洛方法是从初始状态开始,通过在实际环境中模拟,得到一段情节(从头到结束)。 比如,如果结束是失败了,这段情节上的状态节点,本次价值都为0,;如果成功了,本次价值都为1。

下面的比喻(虽然不太恰当,但是比较形象) 想象一棵树,动态规划是先算第一层的所有节点价值,然后算第二层的所有节点价值。 蒙特卡洛方法,随便找一个从根到叶子的路径。根据叶子的值,计算路径上每个节点价值。 可以看出蒙特卡洛方法比较方便。

蒙特卡洛方法的优势

  • 蒙特卡洛方法可以从交互中直接学习优化的策略,而不需要一个环境的动态模型。 环境的动态模型 - 似乎表示环境的状态变化是可以完全推导的。表明了解环境的所有知识。 说白了,就是可以计算\(v(s), q(s, a)\)这意味着必须了解所有状态变化的可能性。 蒙特卡洛方法只需要一些(可能是大量的)取样就可以。
  • 蒙特卡洛方法可以用于模拟(样本)模型。
  • 蒙特卡洛方法可以只考虑一个小的状态子集。
  • 蒙特卡洛方法的每个状态价值计算是独立的。不会影响其他的状态价值。

 蒙特卡洛方法的劣势

  • 需要大量的探索(模拟)。
  • 基于概率的,不是确定性的。

参照

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

DeepMind丨深度学习最新生成记忆模型,远超RNN的GTMM

【新智元导读】DeepMind 的最新研究成果,对广泛使用于语音识别、图像识别、语义理解等领域的深度学习人工网络RNN性能带来显著提升(substantiall...

41360
来自专栏iOSDevLog

十个主题,最全的优秀 TensorFlow 相关资源列表

473110
来自专栏AI科技评论

学界 | 谷歌语音识别端到端系统单词错误率降至5.6%,较传统模型提升16%

AI 科技评论按:本文是由来自谷歌语音团队的科学家 Tara N. Sainath 和来自谷歌大脑团队的科学家 Yonghui Wu 共同撰写的,文中简单介绍了...

30560
来自专栏AI2ML人工智能to机器学习

一步一步走向锥规划 - LP

一般来说凸优化(Convex Optimization, CO)中最一般的是锥规划 (Cone Programming, CP) 问题, 前面我们介绍了最简单...

11820
来自专栏机器之心

基于TensorFlow理解三大降维技术:PCA、t-SNE 和自编码器

选自medium 机器之心编译 参与:Panda Pythonista 数据科学家 Elior Cohen 近日在 Medium 上发文解读了最常见的三大降维技...

47370
来自专栏企鹅号快讯

数字电影技术术语普及

1 1K/2K/4K 在数字技术领域,通常采用二进制运算,而且用构成图像的像素数来描述数字图像的大小。由于构成数字图像的像素数量巨大,通常以K来表示210即10...

24850
来自专栏新智元

谷歌发布迄今最准确商用端到端语音识别系统,词错率将至5.6%,性能提升16%

来源:research.googleblog.com 【新智元导读】谷歌大脑和Speech团队发布最新端到端自动语音识别(ASR)模型,词错率将至5.6%,相比...

35550
来自专栏大数据挖掘DT机器学习

机器学习入门和学习系统的设计

作者 RaySaint http://underthehood.blog.51cto.com/2531780/577854 机器学习的定义 《机器学习》By ...

347110
来自专栏AI2ML人工智能to机器学习

GMM的世界,你不懂?(上篇)

其实在统计学习世界里, GMM有高美美和广美美之分,Gaussian mixture model vs Generalized moment method. ...

11720
来自专栏自然语言处理

程序员眼中的统计学2

均值有两种计算方法:第一种计算方式是:将所有的数字加起来,然后除以数字的个数 。可用记为:µ=∑x/n。另一种计算方法是把每个数的频数考虑进去了的,它表示如下:...

9930

扫码关注云+社区

领取腾讯云代金券