马尔可夫决策基础理论

马尔可夫决策基础理论内容提要本章介绍与研究背景相关的几类决策模型及算法。模型部分，首先是昀基本的马尔可夫决策模型，然后是在此基础上加入观察不确定性的部分可观察马尔可夫决策模型，以及进一步加入多智能体的分布式部分可观察马尔可夫决策模型和部分可观察的随机博弈模型。算法部分，针对上述几类模型，我们均按照后向迭代和前向搜索两大类进行对比分析。昀后，我们介绍了半马尔可夫决策模型及Option理论，这一理论为我们后面设计分等级的大规模多智能体系统的决策模型及规划框架提供了重要基础。2.1MDP基本模型及概念马尔可夫决策过程适用的系统有三大特点：一是状态转移的无后效性；二是状态转移可以有不确定性；三是智能体所处的每步状态完全可以观察。下面我们将介绍MDP基本数学模型，并对模型本身的一些概念，及在MDP模型下进行问题求解所引入的相关概念做进一步解释。2.1.1基本模型马尔科夫决策过程昀基本的模型是一个四元组S,A,T,R(PutermanM,1994)：♦状态集合S：问题所有可能世界状态的集合；♦行动集合A：问题所有可能行动的集合；♦状态转移函数T:S×A×S’→[0,1]:用T(s,a,s’)来表示在状态s，执行动作a，而转移到状态s’的概率('|,)Pssa；♦报酬函数R:S×A→R:我们一般用R(s,a)来表示在状态s执行动作a所能得到的立即报酬。虽然有针对连续参数情况的MDP模型及算法，然而本文在没有特殊说明的情况都只讨论离散参数的情况，如时间，状态及行动的参数。图2.1描述的是在MDP模型下，智能体(Agent)与问题对应的环境交互的过程。智能体执行行动，获知环境所处的新的当前状态，同时获得此次行动的立即收益。图0.1MDP的基本模型2.1.2状态状态是对于在某一时间点对该世界（系统）的描述。昀一般化的便是平铺式表示[]，即对世界所有可能状态予以标号，以s1,s2,s3,…这样的方式表示。这种情况下，标号状态的数目也就代表了状态空间的大小。而一种更加自然的方式是因子化表示，因子化是一种面向对象的思想，这种状态表示方式我们会在结合Robocup的高层设计章节详细讨论。不同的应用中，人们对状态的具体定义是不一样的，但一般来说，在MDP中定义的状态必须包括所有当前世界中Agent能够掌握利用，会对Agent决策产生影响的信息，这也可做为建模过程中，某些因素要不要加入问题状态表示的依据。事实上，这些因素，又对应为一些概念，或者说状态变量。要不要将这些变量加入问题的状态表示中，再或者要不要对概念对应的状态量进行某种拆分或合并，这些问题在建模时都是需要考虑的。处理的不好，便可能引入大量冗余信息。目前，也有专门针对这些问题所作的工作，如识别无关状态(JongNK,StoneP,2005)，聚类等等(GivanR,etal,2003;LiLH,etal,2006)。大多数情况，智能体对自己所处的当前世界的状态不可能有一个完整的认识。因此，我们引入概率的方法来处理这类信息的不确定性。我们引入随机变量St，随机变量从状态集合S中取值。变量St并非由未来时刻的状态所决定，而是由过去状态影响，如图2.2所示。当前状态环境智能体立即收益行动S0S1S2Sk-2Sk-1Sk图0.2马尔可夫链图2.2所表示的是一离散的、随机的动态系统，图中的每个节点表示在某一时刻的某一状态。对于随机变量St,有Pr(St|S0,S1,...,St−1)=Pr(St|St−1)，为一条件概率。它也同时体现了马尔科夫性质，即St只是概率依赖于St−1。任何两个状态间的关系可以只用两个状态来表示。同时，我们引入吸收状态这一概念，如果对于某一状态s，执行任何行动，过程都以概率1转移到s本身，则该状态s被称为吸收状态(absorbstate)。2.1.3行动Agent的行动会参与改变当前世界的状态。MDP的一个关键部分是提供给Agent的用于做决策的行动集合。当某一行动被执行，世界状态将会发生改变，根据一个已知的概率分布转换为另一状态，这个概率分布也和所执行的动作有关。不加说明的情况下，我们讨论的是时齐马尔可夫过程，即所有行动的执行时间是相同的，状态转移的时间间隔一致。这种行动有时也可以被称为系统的原子动作。在该系统内，行动已对应昀小的时间划分，原子动作不可再分割。比如，在一个棋盘类游戏中，每一步所有的走子方式构成了原子动作的集合。再比如，在一个实时的机器人运动控制中，离散的昀小时间片内，机器人可以选择以一定的离散的角度转向，或者以一定的离散的加速度进行速度控制，这些也构成了在该系统下的原子动作集合。2.1.4状态转移函数状态转移函数描述了系统的动态特性，我们可以做以下比较：图0.3对给定行动的状态间概率转移图♦确定环境下的行动：T:S×A→S0.20.31.00.50.51.00.80.60.4s1s2s3s6s5s40.50.2在某个状态s执行动作a可以得到一个确定的状态；♦随机环境下的行动：T:S×A→Prob(S)在某个状态si下执行某一动作a，我们得到的是一状态的概率分布(|,)jiPssa，也记为(,')aTss。图2.3显示了一个对某给定行动，状态间概率转移的情况。在简单的问题中，状态转移函数也可以记为表格的形式。2.1.5策略与值函数以上都是对模型本身的一些概念的解释，下面我们介绍在MDP问题求解过程引入的若干概念。决策问题的解称为策略(policy)，是从状态集合到动作集合的一个映射，即π:S→A。按照策略解决问题的过程是，首先智能体需要知道当前所处状态s，然后执行策略对应的行动π(s),并进入下一状态，重复此过程直到问题结束。MDP中假定Agent通过观察可以完全确定当前所处的状态。而该假设不能保证的问题属于POMDP模型解决的对象，将在下一章讨论。在MDP某些材料中对策略有如下区分，若动作的选取只和当前的状态有关，而与时间无关，称作平稳策略；相应的，非平稳策略是经时间索引后的一系列状态到行动的集合，也就是说非平稳策略即使对于同样的状态，在过程的不同时刻，可能会对应不同的行动。我们希望Agent能够按照某个准则来选择动作以昀大化长期的报酬。比如有现阶段昀优准则，要求昀大化有限阶段期望总报酬昀大，也就是k-1tt=0maxER⎡⎤⎢⎥⎣⎦∑，其中Rt是Agent在第t步得到的报酬。如果我们处理的是一个无限阶段问题，考虑整个过程中的总报酬，通常会引入一个折扣因子γ，其中0γ1。这样Agent选择动作所得到的报酬是k-1ttt=0maxERγ⎡⎤⎢⎥⎣⎦∑。折扣因子保证了k-1ttt=0maxERγ⎡⎤⎢⎥⎣⎦∑的收敛性。事实上，一个过程本质上是在因果关系下的推进，而并非时间推进本身。当可以把时间也作为一个变量加入状态描述中时，前面提到过的有限阶段与无限阶段，以及这里的平稳策略与非平稳策略，都可以统一起来理解。首先，对于有限阶段和无限阶段的问题，长期期望回报是用来评价策略优劣的，理论上它不能出现无穷大的情况，这样将无法比较。而在所谓的无限阶段中，这一点却很难保证。事实上，对于一个现实中决策的智能体来说，无限阶段是不存在的，其生存周期决定了这一点。于是，折扣因子的另一个含义是人为的认定过程在每步执行都有较小的非零的概率1−γ终止。这样，该过程能无限进行下去的概率为0，无限阶段的问题仍是转换成了有限阶段。因此，两者都是依靠问题的终止状态来结束，并无本质区别。同样，当时间可以成为状态变量后，平稳策略与非平稳策略也可以统一起来考虑，所谓的靠时间索引的策略也将变成统一的状态到行动的映射了。在本文后面的部分，无特殊说明的情况下，将不对有限阶段或无限阶段，以及平稳策略或非平稳策略加以区别。对于任何一个策略，我们都可以用执行该策略所能获得的长期期望回报来评价其优劣。定义值函数(ValueFunction):VSπ→为采用策略π时在状态s的期望回报：0()(,())ttttVsERssπγπ∞=⎡⎤=⎢⎥⎣⎦∑(0.1)其中ts为时刻t所处状态，0t=对应初始状态s。以递归的形式表示则为：()'()(,())(,')(')ssSVsRssTssVsππππγ∈=+∑(0.2)对每个策略π，其对应的值函数Vπ是一系列线性方程(每个状态s对应一个方程)的唯一公共解。在某些文献中值函数也被称为评价函数(evaluationfunction)。上述定义给了我们一种计算策略对应的值函数的方法，同时，我们也需要知道如何从值函数来计算得到相应策略。首先，定义一个求解过程常常用到的中间变量，行动值函数:QSAπ×→为在状态s采用行动a，其它状态采用策略π的期望回报。'(,)(,)(,')(')asSQsaRsaTssVsππγ∈=+∑(0.3)当策略没有显式记录，只有值函数V时，行动值函数记为Q。策略π可以通过下式计算得到：()argmax(,)aAsQsaπ∈=(0.4)即：'()argmax(,)(,')(')aaAsSsRsaTssVsπγ∈∈⎧⎫=+⎨⎬⎩⎭∑(0.5)同时有：'()max(,)(,')(')aaAsSVsRsaTssVsπγ∈∈⎧⎫=+⎨⎬⎩⎭∑(0.6)由于(0.5)式事实上是采用的一步前瞻的贪婪搜索，我们也称这样获得的策略为贪婪策略。定义一致性条件(MonotonicCondition)为，对所有s，有：'()max[(,)(,')(')]aasSVsRsaTssVs∈≤+∑(0.7)如果值函数满足一致性,π即是对当前值函数对应的隐式策略的改进,有:()()VsVsπ≥。相反，如果值函数不满足一致性，在某状态s处，'()max[(,)(,')(')]aasSVsRsaTssVs∈+∑，我们便无法经由(0.8)确定满足()()VsVsπ≥的π(s)。通常，对于一个满足一致性条件的值函数，只按Bellman公式进行更新迭代的话，一致性条件始终保持成立。昀优策略记为π*,对应值函数为V*,称为昀优值函数。通常,当一个策略π满足对状态s,有*()()VsVsπε−≤时,我们称π为状态s处的ε昀优策略，当π对问题所有状态均满足上述条件时，称其为问题的ε昀优策略。2.2MDP典型算法马尔可夫决策过程将客观世界的动态特性用状态转移来描述,相关算法可以按是否求解全部状态空间进行划分.早期求解算法有值迭代和策略迭代,这些方法采用动态规划,以一种后向的方式同时求解出所有状态的昀优策略.随后,一些利用状态可达性的前向搜索算法,如AO*,LAO*(HansenEA,Zilberstein,2001)被相继提出,他们的特点是只求解从给定初始状态开始的昀优策略,通常可以避免大量不必要的计算,获得更高的效率.与AO*算法比较,LAO*能够处理状态转移存在环的系统.同样利用状态可达性并结合动态规划的算法有:HeuristicSearch/DP(HDP)(Bonet,B.,Geffner,H,2003),EnvelopePropagation(EP)(Dean,Tetal,1995)以及FocusedDynamicProgramming(FP)(FergusonD,StentzAT,2004).从另一个角度,相关算法还可以按离线或在线划分.对于很多现实世界应用中的大规模问题,无论是否利用状态可达性，解都不可能以离线的方式一次性求出，这种情况更适合使用在线算法,也称为实时算法.实时算法的决策计算与执行交替进行,且解的质量通常随给定计算时间的增加而提升.昀早的基于动态规划的实时算法是RTDP(BartoAG,etal.,1995)。RTDP通过不断循环Trail来改进策略，每次Trail确定一个从初始状态到目标状态的路径然后进行反向的值迭代,然而RTDP不处理停止问题(StoppingProblem)(PembertonJC,1994)。停止问题指如何判断当前解的质量是否已满足要求进而停止计算并提交策略供执行.在值迭代类算法中,停止问题对应收敛判据.LabeledRTDP(BonetB,GeffnerH2003)通过标记各经历状态是否已被求解,给出了一种处理停止问题的方式,同时避免已经求解过