Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >强化学习读书笔记(3)| 有限马尔科夫决策过程(Finite Markov Decision Processes)

强化学习读书笔记(3)| 有限马尔科夫决策过程(Finite Markov Decision Processes)

作者头像
用户1621951
发布于 2019-08-13 07:21:05
发布于 2019-08-13 07:21:05
1.5K0
举报
文章被收录于专栏:数据魔术师数据魔术师

,

本章我们介绍有限马尔科夫决策过程(Finite MDPs),这个问题和赌博机一样涉及到评估的反馈,但这里还多了一个方面——在不同的情况做出不同的选择。MDPs是经典的序列判定决策模型,也就是说,不是做出一个选择就会马上获得reward。这与赌博机不同,赌博机只要摇一次臂即可立刻获得reward,而MDPs就像下象棋,只有结束了对局才会获得reward,但下象棋从开始到结束涉及到很多个行动,也就是要做出很多次选择才最终到对局结束。因此说MDPs的奖励是延迟的,同时MDPs还有一个即时的权值用来帮助当前决策。在赌博机情景中,我们对每一个行为a做出评估值q(a),而在MDPs情境中,我们则需要对行为a和状态s做出评估q(s,a),也可以估计每个给定最佳动作选择的状态的v(s)值。

MDPs有严格的数学模型,我们将介绍它的关键概念比如返回值,值函数以及贝尔曼等式,我们想通过应用来传递有限马尔科夫的结构,像所有人工智能一样,都有其应用的范围。

一、Agent–Environment交互

我们把能够学习且做决策的对象称为agent,比如在无人驾驶中,车就是agent。提供给agent学习和交互的地方就叫Environment。agent不断在环境中交互学习,而环境则给agent反馈并提供一些状态。环境中包含有一些奖励,agent就要在环境中实现奖励最大化。

大部分我们的agent都是离散行动的,比如一次做出一个选择,就像下象棋,一次进行一步,令t为步数,t=1,2,3,...;每一步agent都会获取环境状态(state)的信息,St ∈ S,一系列行为之后,agent会获得这些行为的reward之和Rt+1,然后继续寻找新的state,MDPs的决策过程如下:

几个要素:

二、目标与奖励

Goal:获取最大化的奖励总和。这意味着不能单单只看眼前的奖励,而要看长远过程下的奖励之和。

Reward:用于告诉agent最终想要得到什么,而不是怎么去得到的。奖励是由环境决定的而不是由agent决定的。

三、回报

那么agent的最大化奖励总和的目标要如何用数学的方式进行定义呢?

假设在某个时间点t之后的一系列的reward序列为:Rt+1 , Rt+2 , Rt+3 , . . .期望返回值(expected return)用Gt表示,即从该时间点往后所有获取的reward序列的某种函数。

当agent-environment交互自然地分解成子片段时,我们称之为Episodes。例如在象棋游戏中,一局比赛就是一个Episode,一旦一方被将军,那么这局Episode结束,然后环境重置,到下一个Episode重新摆好棋子继续比赛,上一局游戏和这一局游戏是相互独立的。因此,这些片段都可以被认为是以相同的终止状态结束,对不同的结果有不同的回报,带有片段式过程的任务叫做片段任务(episodic tasks)。

但有时候,我们会遇到没有终止状态的任务,比如无人驾驶,车一直开就一直学习,没有一个任务重置的节点,这类任务叫做连续任务(continuing tasks)。

在连续式任务中,很难把交互过程看成离散的时间点,所以用discounting sum进行定义:

discounting rate γ∈[0,1],决定了未来奖励的当前价值,其含义是:在当前时间点k步之后的奖励,在当前的价值是未来的倍。当该系数小于1,最终和会收敛,只要奖励序列是有限的。当系数为0,则执行机构是短视的,只顾眼前利益;如果系数大于1,执行机构是远视的,也就是重视长远奖励。

四、 策略和值函数

几乎所有的强化学习算法都涉及到估计value function,这个function自变量是状态,用来判断在某个给定状态下做出某个动作的好坏程度。好坏程度用什么来定义呢?这里我们使用“未来的期望奖励”来定义,也可以说期望返回值。显然agent在未来期望得到的奖励取决于它做出什么决策。因此,value function在定义的时候和policy有关。

强化学习中的value function的一个重要性质是它满足一种特别的递归关系。对于任何policy 和任何状态s,当前状态的value和其后的可能状态的value之间的关系如下式:

其中r(s,a,s’)表示期望奖励,当奖励是确定性的情况下,也就等于即时奖励(immediate reward)。

该式叫做policy 的贝尔曼方程。贝尔曼方程对从当前状态起之后的所有可能性进行了平均化,并按照发生的概率给予不同的权重。

五、最优策略和最优值函数

解决一个强化学习问题,也就是意味着找到一个policy,在这个policy下可以获得最好的长期期望奖励。

最优状态值函数 (Optimal State-Value Function) :最优策略π∗下的状态值函数,最优策略即能使值函数取到最大值的策略

最优行为值函数 (Optimal Action-Value Function) :最优策略下的行为值函数

对于状态-动作对(s,a),此函数给出了在状态s中执行操作的预期回报,然后遵循最优策略,因此,可改写为

最优状态值函数和最优行为值函数也满足贝尔曼等式。贝尔曼最优性方程显示了最优策略下的状态价值必须等于该状态最佳行动的预期收益:

六、有限马尔科夫决策过程实例:GridWorld

接下来我们看一个简单的有限状态的马尔科夫决策过程实例。

这是一个GridWorld问题,如上图所示是一个包含5*5个元胞的网格,在每一个元胞内,agent都有四种行动可以执行,它们分别是“上”、“下”、“左”、“右”。假设agent在每个格子处采取四种行动的概率是相同的,同时未来回报的折扣因子设为0.9,而agent的状态转移以及回报值分为以下四种情况:

  • 如果agent在边缘处,那么如果它此时执行的动作使它溢出网格的话,我们限制它的位置仍然固定不变,但是同时它会得到-1的回报值;
  • 如果agent处在A点,那么它的任意行动都将得到10的回报值,同时下一步的状态移至A'处;
  • 如果agent处在B点,那么它的任意行动都将得到5的回报值,同时下一步的状态移至B'处;
  • 其他情况则会得到0的回报值,状态转移遵从格子的位置变化;

根据以上提示,我们如何计算每个元胞的状态-价值函数以及最优状态-价值函数呢?

计算状态-价值函数

根据状态-价值函数的定义,在这里我们不妨理解为agent处在每个格子的时候未来得到的回报值。可以得出以下三条判断:

  • agent处在A和B处的时候状态-价值应该较大,因为当agent处在A或B时,下一步无论它采取什么行动,都会得到较大的10或5回报值;
  • A或B附近处的元胞的状态-价值也要比远离A或B处元胞的状态-价值要大;
  • 由于边缘处很容易得到-1的回报值,那么显然边缘处的元胞要比内部的元胞的状态-价值要小。

除此之外,我们还应该明白,在计算状态-价值函数的时候,我们是不用区分具体行动的,换句话说我们只用按照题意中的均匀概率进行决策即可。那么,每个元胞的状态-价值函数当然是包含了处在该元胞处的所有行动,因此,我们需要在遵从均匀随机决策下对所有行动进行迭代,直到所有元胞的状态-价值收敛为止,这种做法叫做迭代策略评估。

求解状态-价值函数直接按照贝尔曼方程,进行如下迭代即可:

计算最优状态-价值函数

找出agent在每个元胞处它下一步该采取什么行动可以保证状态-价值最大,按照贝尔曼最优方程,我们只用对行动a进行迭代即可,并且找出最大的价值,重复迭代,直到收敛为止。

代码编写

(1)定义好所有状态转移以及对应回报值

(2)按照贝尔曼方程计算状态-价值函数并可视化

(3)按照贝尔曼优化方程计算最优状态-价值函数并可视化:

实验结果

计算出的状态-价值函数值如下:

每个元胞的最优行动如下:

七、小结

有很多不同的决策方法可以看成是贝尔曼最优方程的近似。比如启发式搜索,可以看成是把贝尔曼最优方程等号右边部分扩展到一定深度,得到一个概率树,然后用启发式评估方法在叶子节点上进行的近似(通常启发式搜索算法大多都是基于片段式任务)。另外一个方法就是动态规划,它和贝尔曼方程的相似程度更加接近。很多强化学习的方法,都可以看成是对贝尔曼最优方程的近似求解,使用实际经历的转移情形来弥补难以完全得知环境动态性质的缺陷。我们会在后续章节陆续介绍几类方法。

然而,尽管显式地求解贝尔曼最优方程可以帮助我们求得最优policies,然而,这个方法直接用处并不太大。因为它涉及到穷尽所有的可能性。这个解法依赖于三个在实际中很难满足的假设:(1)我们精确的知道环境的动态性质;(2)我们有足够的计算资源去完成所有运算;(3)环境满足马尔科夫性质。这三个假设在我们感兴趣的问题中通常很难全部满足。比如对于西洋双陆棋来说,第一个和第三个假设可以满足,然而第二个假设很难满足,因为它有10^20个状态。因此,实际应用中,我们必须采取近似的方式。

参考资料:

[1]R.Sutton et al.Reinforcement learning:An introduction,1998

[2]https://zhuanlan.zhihu.com/p/27414242

[3]https://blog.csdn.net/ILYPL/article/details/78940821

[4]https://www.quantinfo.com/Article/View/725/

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-08-11,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 数据魔术师 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【机器学习】马尔科夫决策过程
本文介绍了马尔可夫决策过程,首先给出了马尔可夫决策过程的定义形式,其核心是在时序上的各种状态下如何选择最优决策得到最大回报的决策序列,通过贝尔曼方程得到累积回报函数;然后介绍两种基本的求解最优决策的方法,值迭代和策略迭代,同时分析了两种方法的适用场景;最后回过头来介绍了马尔科夫决策过程中的参数估计问题:求解-即在该状态下采取该决策到底下一状态的概率。
yuquanle
2020/02/13
1.2K0
强化学习通俗理解系列二:马尔科夫决策过程MDP
第二篇文章是整个强化学习基础知识中最重要的,请大家保持警惕。前面系列一我把马尔科夫奖赏过程的全部内容讲完了,下面开始分析马尔科夫决策过程,写作思路依然是参考Divad Silver强化学习课程ppt,由于本人水平有限,如有问题,欢迎指正,我即时修改,谢谢! 本文思路:
机器学习算法工程师
2018/07/27
1.5K0
强化学习通俗理解系列二:马尔科夫决策过程MDP
强化学习读书笔记 - 03 - 有限马尔科夫决策过程
强化学习读书笔记 - 03 - 有限马尔科夫决策过程 学习笔记: Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto c 2014, 2015, 2016 代理-环境接口(The agent-environment interface) 代理(agent) - 学习者或者决策者 环境(environment) - 代理外部的一切,代理与之交互。 情节性任务(Episodic Tasks)和连续任务(
绿巨人
2018/05/17
6910
深入了解马尔科夫决策过程(Markov Decision Process)
马尔科夫决策过程(Markov Decision Process, MDP)是时序决策(Sequential Decision Making, SDM)事实上的标准方法。时序决策里的许多工作,都可以看成是马尔科夫决策过程的实例。
Steve Wang
2019/08/01
4.2K0
强化学习核心之马尔科夫决策过程理论与实战(二)
均不再重要,比如在围棋中下一步怎么下只跟目前的棋子的位置有关,跟他们前面怎么下成这样无关.
CristianoC
2020/12/15
9320
强化学习核心之马尔科夫决策过程理论与实战(二)
强化学习系列之一:马尔科夫决策过程
文章目录 [隐藏] 1. 马尔科夫决策过程 2. 策略和价值 3. 最优策略存在性和贝尔曼等式 强化学习系列系列文章 机器学习一共有三个分支,有监督学习、无监督学习和强化学习。强化学习是系
AlgorithmDog
2018/01/08
1.4K0
强化学习系列之一:马尔科夫决策过程
强化学习通俗理解系列一:马尔科夫奖赏过程MRP
本文写作目的:尽量通俗讲解强化学习知识,使读者不会被各种概念吓倒!本文是第一篇,但是最关键的一篇是第二篇马尔科夫决策过程(Markov Decision Process,MDP),只有充分理解了马尔科夫决策过程,才能游刃有余的学习后续知识,所以希望读者能够将MDP深入理解后再去学习后续内容。
机器学习算法工程师
2018/07/27
9080
强化学习通俗理解系列一:马尔科夫奖赏过程MRP
强化学习-2:Markov decision process(MDP)
我们说一个state若满足 ,则其具有马尔可夫性,即该state完全包含了历史中的所有信息。马尔科夫过程是无记忆的随机过程,即随机状态序列 具有马尔可夫属性。
列夫托尔斯昊
2020/08/25
7830
强化学习-2:Markov decision process(MDP)
一文读懂AlphaGo背后的强化学习
作者 | Joshua Greaves 编译 | 刘畅,林椿眄 本文是强化学习名作——“Reinforcement Learning: an Introduction”一书中最为重要的内容,旨在介绍学习强化学习最基础的概念及其原理,让读者能够尽快的实现最新模型。毕竟,对任何机器学习实践者来说,RL(强化学习,即Reinforcement Learning)都是一种十分有用的工具,特别是在AlphaGo的盛名之下。 第一部分,我们将具体了解了MDPs (马尔可夫决策过程)以及强化学习框架的主要组成部分;第二部
用户1737318
2018/06/05
8410
【AlphaGo核心技术-教程学习笔记02】深度强化学习第二讲 马尔科夫决策过程
【导读】Google DeepMind在Nature上发表最新论文,介绍了迄今最强最新的版本AlphaGo Zero,不使用人类先验知识,使用纯强化学习,将价值网络和策略网络整合为一个架构,3天训练后就以100比0击败了上一版本的AlphaGo。Alpha Zero的背后核心技术是深度强化学习,为此,专知有幸邀请到叶强博士根据DeepMind AlphaGo的研究人员David Silver《深度强化学习》视频公开课进行创作的中文学习笔记,在专知发布推荐给大家!(关注专知公众号,获取强化学习pdf资料,详情
WZEARW
2018/04/09
1.1K0
【AlphaGo核心技术-教程学习笔记02】深度强化学习第二讲 马尔科夫决策过程
强化学习(二)马尔科夫决策过程(MDP)
    在强化学习(一)模型基础中,我们讲到了强化学习模型的8个基本要素。但是仅凭这些要素还是无法使用强化学习来帮助我们解决问题的, 在讲到模型训练前,模型的简化也很重要,这一篇主要就是讲如何利用马尔科夫决策过程(Markov Decision Process,以下简称MDP)来简化强化学习的建模。
刘建平Pinard
2018/08/14
1.5K0
强化学习(二)马尔科夫决策过程(MDP)
强化学习从基础到进阶-常见问题和面试必知必答[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
(2)另外,我们想把不确定性也表示出来,希望尽可能快地得到奖励,而不是在未来的某个时刻得到奖励。
汀丶人工智能
2023/06/20
3670
强化学习从基础到进阶-案例与实践[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
图 2.1 介绍了强化学习里面智能体与环境之间的交互,智能体得到环境的状态后,它会采取动作,并把这个采取的动作返还给环境。环境得到智能体的动作后,它会进入下一个状态,把下一个状态传给智能体。在强化学习中,智能体与环境就是这样进行交互的,这个交互过程可以通过马尔可夫决策过程来表示,所以马尔可夫决策过程是强化学习的基本框架。
汀丶人工智能
2023/10/11
1.2K0
强化学习从基础到进阶-案例与实践[2]:马尔科夫决策、贝尔曼方程、动态规划、策略价值迭代
强化学习笔记2:Markov decision process(MDP)
我们说一个state若满足 ,则其具有马尔可夫性,即该state完全包含了历史中的所有信息。马尔科夫过程是无记忆的随机过程,即随机状态序列 具有马尔可夫属性。
列夫托尔斯昊
2020/08/31
9720
强化学习笔记2:Markov decision process(MDP)
强化学习第1天:马尔可夫过程
我们知道强化学习是一个状态转移的过程,状态发生变化的原因可能取决于当前状态,也可能取决于先前的许多状态,我们把当前状态设为
Nowl
2024/01/18
4330
强化学习第1天:马尔可夫过程
构建强化学习系统,你需要先了解这些背景知识
选自joshgreaves 机器之心编译 强化学习(RL)是关于序列决策的一种工具,它可以用来解决科学研究、工程文理等学科的一系列问题,它也是围棋程序 AlphaGo 的重要组成部分。本文旨在分享 85 页强化学习课本中最重要的内容,我们从最基础的马尔科夫决策过程开始一步步构建形式化的强化学习框架,然后再详细探讨贝尔曼方程以打好强化学习的基础。当然,如果你想更全面地了解这一主题,建议阅读 Richard Sutton 和 Andrew Barto 的著作《Reinforcement Learning: An
机器之心
2018/05/10
7980
一文学习什么是马尔科夫决策过程(Markov Decision Process, MDP)、以及它的变体POMDP、Dec_POMDP等
什么是马尔科夫决策过程(Markov Decision Process, MDP)
不去幼儿园
2024/12/18
1.9K0
一文学习什么是马尔科夫决策过程(Markov Decision Process, MDP)、以及它的变体POMDP、Dec_POMDP等
AlphaGo等智能体是如何炼成的?你需要懂得马尔科夫链
近年来,世界各地的研究员和媒体对深度学习极其关注。而深度学习方面成就最为突出的就是深度强化学习——从谷歌Alpha Go击败世界顶级棋手,到DeepMind的AI智能体自学走路、跑步以及躲避障碍物,如下图所示:
新智元
2018/11/08
6720
深度强化学习(DRL)专栏(一)
【磐创AI导读】:本篇文章是深度强化学习专栏的第一篇,讲了引言和强化学习基础知识,希望对大家有所帮助。查看上篇关于本专栏的介绍:深度强化学习(DRL)专栏开篇。想要获取更多的机器学习、深度学习资源,欢迎大家点击上方蓝字关注我们的公众号:磐创AI。
磐创AI
2019/09/03
1.5K0
深度强化学习(DRL)专栏(一)
强化学习的最基本概念马尔可夫决策过程简介
在本文中我将介绍强化学习的基本方面,即马尔可夫决策过程。我们将从马尔可夫过程开始,马尔可夫奖励过程,最后是马尔可夫决策过程。
deephub
2020/11/09
1.4K0
强化学习的最基本概念马尔可夫决策过程简介
推荐阅读
相关推荐
【机器学习】马尔科夫决策过程
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档