深入了解马尔科夫决策过程(Markov Decision Process)

#深入了解马尔科夫决策过程(Markov Decision Process)| 来源: 网络整理| 查看: 265

马尔科夫决策过程(Markov Decision Process)

马尔科夫决策过程(Markov Decision Process, MDP)是时序决策(Sequential Decision Making, SDM)事实上的标准方法。时序决策里的许多工作，都可以看成是马尔科夫决策过程的实例。

人工智能里的规划(planning)的概念(指从起始状态到目标状态的一系列动作)已经扩展到了策略的概念：基于决策理论对于待优化目标函数最优值的计算，策略将所有的时序状态映射到一个我们期望的最优动作。

策略的一些限定条件

策略通过以下方式将状态映射到动作上：

操作者的动作对规划产生确定性的预期结果。动作的预期结果取决于有关概率性的结果和对目标的贡献(credit)的理论期望。马尔科夫决策过程的优点允许在线的解决方案：通过模拟实验(simulated trials)逐步地学习最优策略。允许依据计算资源实现近似解决方案。（在计算资源充足的条件下，给出最优解的方案；反之，则也能给出能让人接受的最优解的近似解）允许对决策理论的策略质量和学习效果进行数值化度量。形式化描述马尔科夫决策过程

(下面的概念涉及到形式化，博主的导师是研究形式化方法的。)

强化学习问题的元素可以通过马尔科夫决策过程来形式化地描述。马尔科夫决策过程可以看做是有限自动机(finite automata)的随机化扩展，或者看作引入了动作(action)和奖励(rewards)的马尔科夫过程(Markov Process)。

马尔科夫决策过程定义

马尔科夫决策过程是一个由4个元素构成的四元组;S,A,T,R;;S,A,T,R;。其中，SSS是一个包含所有动作的有限集合，TTT是一个定义为S×A×S→[0,1]S\times A \times S \rightarrow[0,1]S×A×S→[0,1]的转换函数，RRR是一个定义为R:S×A×S→RR:S\times A \times S \rightarrow\mathbb{R}R:S×A×S→R的奖励函数。

马尔科夫决策过程包括状态(State)、动作(Action)、转换函数(Transition)、奖励函数(reward function)等，在下面所有形式化描述，×\times×表示笛卡尔积。

状态S，有限集合{s1,s2,...,sN}\{s^1,s^2,...,s^N\}{s1,s2,...,sN}，即∣S∣=N|S|=N∣S∣=N。对于建模的问题来说，状态是所有信息中唯一的特征。动作A，有限集合{a1,a2,...,aN}\{a^1,a^2,...,a^N\}{a1,a2,...,aN}，即∣A∣=N|A|=N∣A∣=N。能够用于某个状态s∈Ss \in Ss∈S的集合表示为A(s)A(s)A(s)，其中A(s)⊆AA(s) \subseteq AA(s)⊆A。先决条件函数(precondition funcion):S×A→{true,false}: S\times A\rightarrow\{true, false\}:S×A→{true,false}可以表达动作a∈Aa\in Aa∈A能否运用在状态s∈Ss\in Ss∈S。转换函数T，可以通过如下方式定义：S×A×S→[0,1]S\times A \times S \rightarrow[0,1]S×A×S→[0,1]，即它是从(S,A,S)(S,A,S)(S,A,S)三元组映射到一个概率的函数，其概率表示为T(s,a,s′)T(s, a, s^{'})T(s,a,s′)，表示，从状态sss转换到状态s′s{'}s′的概率，其值需要满足0≤T(s,a,s′)≤10\leq T(s, a, s^{'})\leq 10≤T(s,a,s′)≤1且∑s∈s′T(s,a,s′)=1\sum_{s\in s^{'}}T(s, a, s^{'})=1∑s∈s′T(s,a,s′)=1，即概率必须满足实际，否则无意义。我们可以定义离散的全局时钟t=1,2,3...t=1,2,3...t=1,2,3...，然后使用sts_tst表示在时间t的状态。如果一个系统的动作不依赖于之前的动作和历史状态，而仅仅取决于当前状态，那么该系统具有马尔科夫特性，即P(st+1∣st,at,st−1,at−1,...)=P(st+1∣st,at)=T(st,at,st+1)P(s_{t+1}|s_t,a_t,s_{t-1},a_{t-1},...)=P(s_{t+1}|s_t,a_t)=T(s_t,a_t,s_{t+1})P(st+1∣st,at,st−1,at−1,...)=P(st+1∣st,at)=T(st,at,st+1) 马尔科夫决策过程的核心思想是当前状态s提供了足够的信息来做最优决策，而之前的状态和动作是不重要的。换一种表述方法是，下一个状态的概率分布和同一个状态下当前动作的概率分布是相同的。奖励函数R，可以定义为R:S→RR:S\rightarrow\mathbb{R}R:S→R，从状态中直接获取奖励；或者R:S×A→RR:S\times A\rightarrow\mathbb{R}R:S×A→R，在某状态执行某动作获得奖励；或者R:S×A×S→RR:S\times A \times S \rightarrow\mathbb{R}R:S×A×S→R，执行某个状态转换获得奖励。最后一种定义方式可以非常方便的应用于无模型算法(model free algorithm)，因此是广泛使用的定义方式。奖励函数是马尔科夫决策过程最重要的部分，因为奖励隐式地定义了学习的目标(goal)。奖励函数给予了系统(即MDP)的前进方向。通常情况下，奖励函是也将非零的奖励分配给非目标的状态，这可以理解为为学习定义的子目标。

转换函数TTT和奖励函数RRR一起定义了马尔科夫决策过程的模型。马尔科夫决策过程经常被描绘成一个状态转换图，图的结点对应状态，有向边对应状态的转换。

马尔科夫决策过程可以建模几种不同类型的系统：

周期性任务有周期长度(episode of length)的概念，在这个概念中，学习的目标是将代理(agent)从开始状态转换到目标状态。对于每一个状态来说，初始状态分布I:S→[0,1]I: S\rightarrow[0,1]I:S→[0,1]，给出了当前系统在此状态下开始的概率。根据所执行的动作，从一个状态s开始，系统通过一系列的状态前进。在周期性任务中，有一个特定的子集G⊆SG\subseteq SG⊆S，这个子集表示过程结束时的目标状态区域，该区域通常包含一些特定的奖励。

此外，任务还可以进一步分为以下类型：

有限的固定范围的任务：任务的每个阶段包含固定数目的步骤。未定义范围的任务：任务的每一个阶段都可以终止，但是阶段的长度可以是任意的。无限范围的任务：无限任务包含无限的步骤，学习系统永不停止，通常被称为一个持续任务。

周期任务可以通过吸收状态(absorbing states)或者终止状态(terminal states)来建模。这是指每一个动作所处的状态都可以变换到一个概率为1，奖励为0的相同状态，即吸收状态。它可以被形式化的表示为：T(s,a,s′)=1T(s, a, s^{'})=1T(s,a,s′)=1和R(s,a,s′)R(s, a, s^{'})R(s,a,s′)=0。进入一个吸收状态时，进程将在一个新的启动状态下重新设置或者重新启动。周期性任务加上吸收状态，可以以这种方式用连续任务相同的框架优雅地进行模拟。

策略

给定一个MDP;S,A,T,R;MDP;S,A,T,R;MDP，策略是一个可计算的函数，它为每一个状态s∈Ss\in Ss∈S和每一个动作a∈Aa\in Aa∈A提供输出。形式化地，一个确定性策略π\piπ是一个被定义为π:S→A\pi: S\rightarrow Aπ:S→A的函数，也可以定义一个随机性策略π:S×A→[0,1]\pi: S\times A \rightarrow [0,1]π:S×A→[0,1]，使得π(s,a)≥0\pi(s,a)\geq0π(s,a)≥0并且∑a∈Aπ(s,a)≥0\sum_{a\in A}\pi(s,a)\geq0∑a∈Aπ(s,a)≥0。

马尔科夫决策过程的应用方法如下：首先，从初始状态分布III产生一个起始状态s0s_0s0。然后，策略建议的动作a0=π(s0)a_0=\pi (s_0)a0=π(s0)，而这个动作将被执行。基于状态转换函数TTT和奖励函数RRR，转换到状态s1s_1s1，那么概率为T(s0,a0,s1)T(s_0,a_0,s_1)T(s0,a0,s1)且奖励r0=R(s0,a0,s1)r_0=R(s_0,a_0,s_1)r0=R(s0,a0,s1)将被接收。重复这个过程，产生以下状态和动作: s0,a0,r0,s1,a1,r1,s2,a2,r2...s_0,a_0,r_0,s_1,a_1,r_1,s_2,a_2,r_2...s0,a0,r0,s1,a1,r1,s2,a2,r2...如果任务是周期性的，这个过程将结束在状态sgoals_{goal}sgoal，并从初始状态分布III中产生一个新的状态后重新启动。如果继续执行，该序列的状态可以无限期执行。策略是代理(agent)的一部分，而代理(agent)的目的是控制环境，而环境是用马尔科夫决策过程建模的。一个固定的策略是在马尔科夫决策过程中推导出一个静态转换，而这个静态转换能够转换成马尔科夫系统;S′,T′;;S^{'},T^{'};，它满足如下条件：当π(s)=a\pi (s)=aπ(s)=a时，S′=SS^{'}=SS′=S和T′(s,s′)=T(s,a,s′)T^{'}(s,s^{'})=T(s,a,s^{'})T′(s,s′)=T(s,a,s′)。

最优准则和折扣

前面的两个小节我们定义了环境(MDP)，代理(agent)(控制元件，或策略)。在讨论最优算法之前，首先要界定什么是最优模型。有两种方式看到最优性：

代理(agent)实际在优化什么方面，它的目标是什么？如何通过最优的方式优化目标。第一个方面与奖励收集(gathering reward)有关；第二个方面与算法的效率和最优性有关。

马尔科夫决策过程中学习的目标是收集奖励。如果agent只关心即时奖励，一个简单的最优准则是优化E[rt]E[r_t]E[rt]。

有限时域(finite horizon)模型选取一个有限的长度为h的有限时域，并声明agent将优化该有限时域内的预期奖励。 E[∑t=0hrt](有限时域)E[\sum_{t=0}^{h}r_t] (有限时域)E[t=0∑hrt](有限时域) 这可以通过两种方法来实现：

agent在第一步采取h步优化行为，在这之后采取(h-1)步优化行为，以此类推。agent始终采取h步最优行为，这称为滚动时域控制(receding-horizon control)。有限时域模型的问题在于(最优)选择的时域长度h不总是已知的。

无限时域模型中，将考虑长期奖励，但是根据接收时间的远近将在时间较远时对接收到的奖励打折扣。为了实现这个，引入一个折扣因子γ\gammaγ，其中0≤γ;10 \leq \gamma ; 10≤γ

【本文地址】

公司简介

联系我们