精华内容
下载资源
问答
  • 马尔可夫决策过程

    千次阅读 2018-06-22 00:46:50
    马尔可夫决策过程是基于马尔可夫过程理论的随机动态系统的最优决策过程。马尔可夫决策过程是序贯决策的主要研究领域。它是马尔可夫过程与确定性的动态规划相结合的产物,故又称马尔可夫型随机动态规划,属于运筹学中...
    马尔可夫决策过程是基于马尔可夫过程理论的随机动态系统的最优决策过程。马尔可夫决策过程是序贯决策的主要研究领域。它是马尔可夫过程与确定性的动态规划相结合的产物,故又称马尔可夫型随机动态规划,属于运筹学中数学规划的一个分支。
    中文名
    马尔可夫决策过程
    外文名
    Markov Decision Processes
    简    称
    MDP
    属    于
    运筹学中数学规划的一个分支
    领    域
    概率论,统计学
    人    物
    安德雷·马尔可夫

    简介

    编辑
    概率论统计学中,马可夫决策过程(英语:Markov Decision Processes,缩写为 MDPs)提供了一个数学架构模型,用于面对部分随机,部分可由决策者控制的状态下,如何进行决策,以俄罗斯数学家安德雷·马尔可夫的名字命名。在经由动态规划强化学习以解决最佳化问题的研究领域中,马可夫决策过程是一个有用的工具。
    马尔可夫过程在概率论和统计学方面皆有影响。一个通过不相关的自变量定义的随机过程,并(从数学上)体现出马尔可夫性质,以具有此性质为依据可推断出任何马尔可夫过程。实际应用中更为重要的是,使用具有马尔可夫性质这个假设来建立模型。在建模领域,具有马尔可夫性质的假设是向随机过程模型中引入统计相关性的同时,当分支增多时,允许相关性下降的少有几种简单的方式。
    马尔可夫决策过程是指决策者周期地或连续地观察具有马尔可夫性的随机动态系统,序贯地作出决策。即根据每个时刻观察到的状态,从可用的行动集合中选用一个行动作出决策,系统下一步(未来)的状态是随机的,并且其状态转移概率具有马尔可夫性。决策者根据新观察到的状态,再作新的决策,依此反复地进行。马尔可夫性是指一个随机过程未来发展的概率规律与观察之前的历史无关的性质。马尔可夫性又可简单叙述为状态转移概率的无后效性。状态转移概率具有马尔可夫性的随机过程即为马尔可夫过程。马尔可夫决策过程又可看作随机对策的特殊情形,在这种随机对策中对策的一方是无意志的。马尔可夫决策过程还可作为马尔可夫型随机最优控制,其决策变量就是控制变量

    发展概况

    编辑
    50年代R.贝尔曼研究动态规划时和L.S.沙普利研究随机对策时已出现马尔可夫决策过程的基本思想。R.A.霍华德(1960)和D.布莱克韦尔(1962)等人的研究工作奠定了马尔可夫决策过程的理论基础。1965年,布莱克韦尔关于一般状态空间的研究和E.B.丁金关于非时齐(非时间平稳性)的研究,推动了这一理论的发展。1960年以来,马尔可夫决策过程理论得到迅速发展,应用领域不断扩大。凡是以马尔可夫过程作为数学模型的问题,只要能引入决策和效用结构,均可应用这种理论。

    定义

    编辑
    马尔可夫决策过程是一个五元组
      
    ,其中
    1)
      
    是一组有限的状态;
    2)
      
    是一组有限的行为(或者,
      
    是从状态可用的有限的一组行动
      
    );
    3)
      
    是行动的概率
      
    在状态
      
    在时间
      
    会导致状态
      
    在时间
      
    ;
    4)
      
    是从国家转型后得到的直接奖励(或期望的直接奖励);
    5)
      
    是折现系数,代表未来奖励与现在奖励之间的重要差异 [1]  。
    (注:马尔可夫决策过程的理论并没有说明这一点,
      
      
    是有限的,但是下面的基本算法假设它们是有限的)。
    图1.简单MDP的示例图1.简单MDP的示例
    图1表示具有三个状态(绿色圆圈)和两个动作(橙色圆圈)的简单MDP的示例。

    描述

    编辑
    MDP的核心问题是为决策者找到一个策略:一个功能
      
    指:决策者什么时候会选择行动
      
    。一旦马尔可夫决策过程以这种方式与策略相结合,就可以解决每个状态的行为,并且产生的组合行为就像一个马尔可夫链
    目标是选择一项策略
      
    这将最大化随机奖励的一些累积函数,通常是在可能无限的时间范围内的期望折扣总和:
      
    ,其中
      
    )。
      
    是折扣因素和满足 
     
    。(例如,
      
    当折扣率为r时)
      
    通常接近1。
    由于马尔可夫属性,这个特定问题的最优策略确实可以写成一个函数
      
    只有,如上所述。

    分类

    编辑

    1.连续时间马尔可夫决策过程

    对于连续时间的马尔可夫决策过程,可以在决策者选择的任何时候作出决定。与离散时间马尔可夫决策过程相比,连续时间马尔可夫决策过程可以更好地模拟连续动态系统的决策过程,即系统动力学由偏微分方程定义。

    2.离散时间马尔科夫决策过程

    在离散时间马尔科夫决策过程中,决策是在离散的时间间隔进行的。

    策略指标

    编辑
    策略是提供给决策者在各个时刻选取行动的规则,记作
      
    ,其中
      
    是时刻n选取行动的规则。从理论上来说,为了在大范围寻求最优策略
      
    ,最好根据时刻
      
    以前的历史,甚至是随机地选择最优策略。但为了便于应用,常采用既不依赖于历史、又不依赖于时间的策略,甚至可以采用确定性平稳策略。
    衡量策略优劣的常用指标有折扣指标和平均指标。折扣指标是指长期折扣〔把
      
    时刻的单位收益折合成0时刻的单位收益的
      
    (β < 1)倍〕期望总报酬;平均指标是指单位时间的平均期望报酬。
    采用折扣指标的马尔可夫决策过程称为折扣模型。业已证明:若一个策略是
      
    折扣最优的,则初始时刻的决策规则所构成的平稳策略对同一
      
    也是折扣最优的,而且它还可以分解为若干个确定性平稳策略,它们对同一β都是最优的,已有计算这种策略的算法。
    采用平均指标的马尔可夫决策过程称为平均模型。已证明:当状态空间
      
    和行动集
      
    均为有限集时,对于平均指标存在最优的确定性平稳策略;当
      
      
    不是有限的情况,必须增加条件,才有最优的确定性平稳策略。计算这种策略的算法也已研制出来。

    扩展

    编辑

    1.约束马尔可夫决策过程

    约束马尔可夫决策过程(CMDPs)是马尔可夫决策过程(MDPs)的扩展。MDP和CMDP有三个基本的区别。
    1)应用时一个动作而不是一个动作需要多个成本;
    2)CMDP只能通过线性程序来解决,动态编程不起作用;
    3)最终的政策取决于开始的状态。
    CMDP有很多应用。它最近被用在机器人的运动规划场景中。

    2.模糊马尔可夫决策过程(FMDPs)

    在MDP中,最优策略是使未来奖励的概率加权总和最大化的策略。因此,最优策略由几个属于一组有限行为的动作组成。在模糊马尔可夫决策过程(FMDP)中,首先,价值函数被计算为规则的MDP(即具有有限的一组行动);那么,这个策略是通过一个模糊推理系统来提取的。换句话说,价值函数被用作模糊推理系统的输入,策略是模糊推理系统的输出 [2]  。
    参考资料
    • 1.  [1]周从华,邢支虎,刘志锋,王昌达. 马尔可夫决策过程的限界模型检测[J]. 计算机学报,2013,12:2587-2600.
    • 2.  [2]邱祎,董彦彦. 基于马尔可夫过程的线性规划方法探讨[J]. 统计与决策,2017,10:88-90
    展开全文
  • 马尔可夫决策过程
  • 马尔可夫决策过程引论是学习马尔可夫过程的绝佳参考书目,下载必有收获哦
  • 在介绍一般马尔可夫决策过程的基础上, 分析了当前主要马尔可夫过程自适应决策方法的基 本思想、 具体算法实现以及相应结论,总结了现有马尔可夫过程自适应决策算法的特点, 并指出了需要 进一步解决的问题。...
  • 马尔可夫决策过程的偏好计划
  • 加权马尔可夫决策过程的成分推理
  • 马尔可夫决策过程理论与应用,刘克,曹平 马尔可夫决策过程理论与应用_13701577
  • 实用马尔可夫决策过程: 马尔可夫决策详细解释,非常好的资料,大家值得一看,对学习马尔科夫非常有用处.
  • 基于马尔可夫决策过程的语义主题检测
  • 测量有限马尔可夫决策过程之间的距离
  • matlab开发-马尔可夫决策过程摆度控制。建立了摆锤的马尔可夫决策过程模型,然后找到了摆锤的最优上摆策略。
  • 马尔可夫决策过程(MDP) 马尔可夫决策过程的基本概念,作学习笔记用,资料链接在文末 马尔可夫决策过程是序贯决策的数学模型,用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报。 一...

    马尔可夫决策过程(MDP)

    马尔可夫决策过程的基本概念,作学习笔记用,资料链接在文末

    马尔可夫决策过程是序贯决策的数学模型,用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报。

    一、马尔可夫性质

    当一个随机过程在给定现在状态以及所有过去状态情况下,其未来状态的条件概率分布仅依赖于当前状态,换句话说,在给定现在状态时,它与过去状态(即该过程的历史路径)是条件独立的,那么说此随机过程具有马尔可夫性质,具有马尔可夫性质的过程通常称之为马尔科夫过程。公式表示如下:

                                  P[X(t+h)=y|X(s)=x(s),s\leq t]=P[X(t+h)=y|X(t)=x(t)],\forall h> 0

    二、马尔可夫决策过程

     

    MDP是在环境中模拟智能体的随机性策略(policy)与回报的数学模型,且环境的状态具有马尔可夫性质。

    MDP有两个交互对象:

    • 智能体(Agent):MDP中进行机器学习的代理,可以感知外界环境进行决策,对环境做出动作并通过环境的反馈调整决策。
    • 环境(Environment):MDP模型中智能体外部所有事物的集合,其状态会受到智能体动作的影响而改变,且上述改变可以完全或部分地被智能体感知。环境在每次决策后可能会反馈给智能体相应的奖励。

    MDP模型有五个模型要素:

    • 状态S:对环境的描述,在智能体做出动作后,状态S会发生改变,且具有马尔可夫性质。
    • 动作A:对智能体行为的描述,是智能体决策的结果。MDP所有可能动作的集合称为动作空间,动作空间可以离散可以连续。
    • 策略\pi (a|s):MDP的策略时按状态给出的动作的条件概率分布,在强化学习的语境下属于随机性策略。
    • 奖励R:在智能体给出动作后环境对智能体的反馈。是当前状态、当前动作和下个状态的标量函数:R=R(s_t,a_t,s_t_+_1)
    • 回报G:奖励随时间的积累。在引入轨迹的概念后回报定义为轨迹上所有奖励的总和。

    MDP的组织方式:

    智能体对初始环境s_0进行感知,按策略\pi_0实施动作a_0,环境受到智能体动作的影响进入新的状态s_1,并反馈给智能体一个奖励r_0(s_0,a_0,s_1)。随后智能体基于r_0s_1采取新的策略,对环境进行新的感知,重复上述过程与环境进行持续交互。

     

    资料链接:

    https://baike.baidu.com/item/马尔可夫决策过程/5824810?fr=aladdin

    https://baike.baidu.com/item/马尔可夫性质/23149887

     

     

     

    展开全文
  • 理解马尔可夫决策过程

    千次阅读 2019-02-04 11:18:29
    在高层次的直觉中,马尔可夫决策过程(MDP)是一种对机器学习非常有用的数学模型,具体来说就是强化学习。该模型允许机器和agent确定特定环境中的理想行为,从而最大限度地提高模型在环境中实现特定状态甚至多个状态...

    https://www.toutiao.com/a6651196916329611780/

     

    2019-01-28 01:17:00

    在高层次的直觉中,马尔可夫决策过程(MDP)是一种对机器学习非常有用的数学模型,具体来说就是强化学习。该模型允许机器和agent确定特定环境中的理想行为,从而最大限度地提高模型在环境中实现特定状态甚至多个状态的能力。这个目标是由我们称为策略的东西决定的,策略应用于依赖于环境的agent的操作,MDP试图优化为实现这样的解决方案所采取的步骤。这种优化是通过奖励反馈系统完成的,在这个系统中,不同的行为根据这些行为将导致的预测状态进行加权。

    分解

    要了解MDP,我们首先应该看一下流程的独特组成部分。它包含:

    • 存在于我们指定环境中的一组状态:S(state)
    • 在指定环境中存在一组有限的行为:A(agent)
    • 描述每个动作对当前状态的影响:T
    • 给出所需状态和行为的奖励函数:R(s,a)。
    • 寻求解决MDP的政策。您可以将其视为从状态到我们的行为的映射。用更简单的术语表示在状态S时应该采取的最佳行为'a'。

    理解马尔可夫决策过程

    MDP的图像概述

    理解模型:

    从上图中可以看出,我们有T(S,a,S')〜P(S'| S,a)。

    该模型通常被称为转换模型。T代表了我们行为的概念化。我们从一些状态S开始,我们采取行动A,我们的agent发现自己处于一个新状态S'。

    接下来,我们定义P,或者我们通过在前一种状态中采取行动而达到新状态的概率。

    Markov性质:

    P[St+1 | a, S0, ….. , St]= P[St+1 |a, St]

    上面的公式是马尔科夫性质状态的定义。我们再来分解一下。

    St+1可以被解释为未来的状态,[ S 1,...,S t ]表示状态历史中存在的所有相关信息的历史。当然,a仍然代表着正在采取的行为。但是,新状态仅取决于之前的状态。

    给定马尔可夫状态,定义转移概率。

    鉴于我们的agent处于某种状态s,对于每一个存在的状态,都有一种到达第一种状态的概率,另一种到达第二种状态的概率,依此类推。这是转换概率。

    我们可以采用这些概率并将它们输入状态矩阵!让我们定义一个带有3种状态天气问题的例子。规则如下:

    1. 你住在阳光镇,但可悲的是,阳光镇从来没有连续两天好天气。
    2. 如果你有个美好的一天,第二天就有可能下雪或下雨。
    3. 如果我们下雪或下雨,第二天有50%的机会有相同的天气。
    4. 如果天气从下雪或下雨变化,它只会一半的时间变成晴天。

    使用这个假的环境信息,我们可以像这样构造一个状态矩阵:

    理解马尔可夫决策过程

     

    其中,矩阵的第一行表示在给定雨天的情况下,未来几天天气的概率。第二行表示正常日子的概率,第三行表示雪天的概率。这种转换概率矩阵称为转换矩阵。

    现在,让我们从我们的矩阵中尝试一个模型真正的问题从矩阵p²(ij)

    i表示当前状态,j表示未来状态。

    我们想知道今天下雨的可能性是多少,从现在开始两天后下雪的可能性是多少?假设在下雨,我们可能的状态是什么?

    唯一的限制是不能连续两天过得很好。从现在到那时的所有其他状态都是可能的。所以明天可能会下雨,第二天可能会下雪,明天可能会很好,第二天可能会下雪,明天可能会下雪,第二天也可能会下雪。

    以等式形式:

    P²(Rain⁰Snow²) = P(RainRain)*P(RainSnow) + P(RainNormal)*P(NormalSnow) + P(RainSnow)*P(SnowSnow)

    现在我意识到这看起来很痛苦,但是你可能已经意识到这本质上是向量和矩阵的数学。我们取第一行和第三行做点积。

    可视化使生活更轻松

    让我们假设我们希望预测给定6天时间周期的P,或者6个状态转变。我们还没有定义一个初始状态,我们只是希望在给定初始概率的情况下,求出过渡时期状态的概率。这被称为正则马尔可夫链。如你所见,我们继续使用向量数学通过点积来计算每个状态的概率。

    理解马尔可夫决策过程

     

    但我们如何确定初始起始状态?它将如何影响我们的概率计算或如何创建马尔可夫链:

    我们可以将其定义为:u ^(n)= uP ^(n)

    其中u是表示状态初始分布的向量,P是马尔可夫链的转换矩阵。

    我们知道我们有三种状态,我们把它带入.u³=uP³

    我们来解第三天的概率。我们制作一个1x3向量来表示初始分布,并采用点积来求出给定随机初始状态的第三天每种状态的可能性。

    理解马尔可夫决策过程

     

    如何找到这么多状态的最佳解决方案以获得理想的结果?这就是我想用强化学习来做的。

    为了理解如何计算状态和操作的优化,我们需要给它们赋值。为了理解价值,我们需要定义一个策略,为了定义一个策略,我们需要了解奖励和回报。

    奖励和回报价值

    强化agent寻求最大化未来奖励的总和。他们希望预测获得最大奖励的行为。这称为return,我们可以像这样建模,r表示奖励,R表示返回,下标t表示时间步长,在我们的例子中是状态转换。

    理解马尔可夫决策过程

     

    现在,正如你所看到的,这个等式允许趋于无穷大,但处理许多问题是没有意义的。我们希望奖励的总和结束。我们称任务结束剧集。想象一下大富翁棋盘游戏,一开始给所有人分配相同的价值,然后给出一系列可能的状态和行为,这一集最终以赢家结束。一个新内容可以从创建游戏的新实例开始。

    处理回报价值的更常用方法是称为未来累积折扣奖励的方法

    理解马尔可夫决策过程

     

    其中,奖励前的折扣表示0到1之间的值。这种方法的好处是,现在对无限回报有了更好的模型,而且它更重视更直接的回报。这个模型现在关心的是更早的回报,而不是未来的回报。我们可以自己加权。我们选择的折扣越小,越强调早期奖励。正如您可能想象的那样,1的折扣变成了我们原来的奖励方程,0的折扣创建了一个只关心第一个奖励的模型。这在某种意义上是有用的,因为agent将会在特定的时刻学习绝对最好的事情,但它将缺乏对自己未来的洞察力。

    更多关于政策

    π(s,a)是我们的政策函数。它描述了一种行为方式。它采用当前状态和agent操作,并返回在该状态下执行该操作的概率。有点像我们上面演示的那样。

    如果你考虑这意味着什么,那么在给定所有行为的情况下,所有状态的集合必须等于1的概率。

    理解马尔可夫决策过程

     

    我们的政策应描述如何在每个状态采取行动。

    以Josh Greaves创建的这个策略为例

    理解马尔可夫决策过程

     

    正如你所看到的,当我们吃饱时,我们会得到奖励,当我们饥饿就吃饭时,我们会得到奖励,并且我们因为吃饱而不吃东西而获得奖励。如果饥饿而不吃饭是,我们会受到极大的惩罚,并且在吃饱时吃饭会受到惩罚。很容易看出,在这个非常简单的例子中,最优策略是在饥饿时吃东西。

    价值函数:

    强化学习中的两种价值函数是状态价值函数V(s)和行为价值函数Q(s, a)。

    状态值函数解释给定特定策略的状态的值。当我们从初始状态s开始并在我们的策略规则中行动时,它是对回报的计算。

    理解马尔可夫决策过程

     

    操作值函数返回在遵循指定策略时在给定状态下执行操作的值。

    理解马尔可夫决策过程

     

    现在,考虑到在选择操作时,环境是返回下一个状态的,我们必须记住,如果我们的策略发生变化,值函数也会发生变化。我们希望看到这些函数有一个给定的返回值,然而,在到达某个状态时可能会有大量的随机性,并且转换函数也会影响我们的状态。我们不可能有100%的可能性。

    展开全文
  • 基于马尔可夫决策过程的智能多无线电接入
  • 关于马尔可夫决策过程的马尔可夫是什么? 马尔可夫是安德烈·马尔科夫(Andrey Markov),​​他是著名的俄罗斯数学家,以其在随机过程中的工作而闻名。 “马尔可夫”通常意味着在当前状态下,未来和过去是独立的。 ...

    作者|Nathan Lambert 编译|VK 来源|Towards Data Science

    关于马尔可夫决策过程的马尔可夫是什么?

    马尔可夫是安德烈·马尔科夫(Andrey Markov),​​他是著名的俄罗斯数学家,以其在随机过程中的工作而闻名。

    “马尔可夫”通常意味着在当前状态下,未来和过去是独立的。

    建立Markovian系统的关键思想是无记忆。无记忆是系统历史不会影响当前状态的想法。用概率表示法,无记忆性转化为这种情况。考虑一系列动作产生的轨迹,我们正在寻找当前动作将带给我们的位置。长的条件概率可能看起来像:

    现在如果系统是Markovian,则历史将全部包含在当前状态中。因此,我们的第一步分配要简单得多。

    这一步是改变计算效率的规则。马尔可夫性质是所有现代强化学习算法的存在和成功的基础。

    马尔可夫决策过程(MDP)

    MDP由以下定义:

    • 状态集$s\in S。状态是代理程序所有可能的位置。在下面的示例中,它是机器人位置。
    • 一组动作$a\in A$。动作是代理可以采取的所有可能动作的集合。在下面的示例中,这些动作的下方是{北,东,南,西}。
    • 转换函数T(s,a,s')。T(s,a,s')保持MDP的不确定性。给定当前位置和给定动作,T决定下一个状态出现的频率。在下面的示例中,转换函数可能是下一个状态在80%的时间内处于目前动作方向,而在其他20%的情况下偏离了90度。在下面的示例中,机器人选择了北,但每个机器人有10%的机会向东或向西移动。
    • 奖励函数R(s,a,s')。最大化报酬总额是任何代理的目标。此函数说明每个步骤可获得多少奖励。通常,为鼓励快速解决方案,每个步骤都会有少量的负奖励(成本),而在最终状态下会有较大的正面(成功的任务)或负面(失败的任务)奖励。例如下面的宝石和火坑。
    • 开始状态s0,也许是结束状态。

    这给了我们什么?

    这个定义给我们提供了一个有限的世界,我们建立了前进的模型。我们知道每个转换的确切概率,以及每个动作的效果。最终,该模型是一种方案,我们将在知道自己的操作可能会出现错误的情况下计划如何采取行动。

    如果机器人就在火坑旁边,机器人是否应该总是选择北方,但是北方有可能把它送到东边掉入火坑?

    不,最佳策略是西方。因为最终进入墙壁将(有20%的机会)向北移动,并使机器人驶向目标。

    策略规定

    学习如何在未知环境中行动是了解环境的最终目标。在MDP中,这称为策略。

    策略是一项函数,可让你根据状态执行操作。π*:S→A.

    制定策略的方法很多,但是核心思想是值和策略迭代。这两种方法都可以迭代地为状态(可能是动作)的总效用建立估算。

    状态的效用是(折后)奖励的总和。

    一旦每个状态都具有效用,那么高层的规划和策略制定就会遵循最大效用的路线。

    在MDP和其他学习方法中,模型会添加折扣因子γ来优先考虑短期和长期奖励。折扣因素在直觉上是有道理的。通过将奖励的总和转换成几何级数,折扣因子也带来了巨大的计算收敛性。

    原文链接:https://towardsdatascience.com/what-is-a-markov-decision-process-anyways-bdab65fd310c

    欢迎关注磐创AI博客站: http://panchuang.net/

    sklearn机器学习中文官方文档: http://sklearn123.com/

    欢迎关注磐创博客资源汇总站: http://docs.panchuang.net/

    展开全文
  • 在本文中我将介绍强化学习的基本方面,即马尔可夫决策过程。我们将从马尔可夫过程开始,马尔可夫奖励过程,最后是马尔可夫决策过程。 目录 马尔可夫过程 马尔可夫奖励过程 马尔可夫决策过程 马尔可夫过程 马尔可夫...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 732
精华内容 292
关键字:

马尔可夫决策过程