2022年马尔可夫决策基础理论 .pdf

《2022年马尔可夫决策基础理论 .pdf》由会员分享，可在线阅读，更多相关《2022年马尔可夫决策基础理论 .pdf（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、马尔可夫决策基础理论内容提要本章介绍与研究背景相关的几类决策模型及算法。模型部分，首先是最基本的马尔可夫决策模型， 然后是在此基础上加入观察不确定性的部分可观察马尔可夫决策模型，以及进一步加入多智能体的分布式部分可观察马尔可夫决策模型和部分可观察的随机博弈模型。 算法部分， 针对上述几类模型， 我们均按照后向迭代和前向搜索两大类进行对比分析。最后，我们介绍了半马尔可夫决策模型及Option 理论， 这一理论为我们后面设计分等级的大规模多智能体系统的决策模型及规划框架提供了重要基础。2.1 MDP 基本模型及概念马尔可夫决策过程适用的系统有三大特点：一是状态转移的无后效性； 二是状态转移可以有不

2、确定性； 三是智能体所处的每步状态完全可以观察。下面我们将介绍 MDP 基本数学模型，并对模型本身的一些概念，及在MDP 模型下进行问题求解所引入的相关概念做进一步解释。2.1.1 基本模型马尔科夫决策过程最基本的模型是一个四元组S,A,T,R(Puterman M, 1994)： ?状态集合 S：问题所有可能世界状态的集合；?行动集合 A：问题所有可能行动的集合； ?状态转移函数 T: S A S 0,1 : 用 T(s, a, s)来表示在状态 s，执行动作 a，而转移到状态 s 的概率( | , )P s s a ； ?报酬函数 R: S A R: 我们一般用 R(s, a)来表示在状态

3、 s执行动作 a 所能得到的立即报酬。 虽然有针对连续参数情况的MDP 模型及算法，然而本文在没有特殊说明的情况都只讨论离散参数的情况，如时间，状态及行动的参数。图 2.1 描述的是在 MDP 模型下，智能体 (Agent)与问题对应的环境交互的过程。智能体执行行动， 获知环境所处的新的当前状态，同时获得此次行动的立即名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 36 页 - - - - - - - - - 收益。图 0.1 MDP的基本模型 2.1.2 状态状态是对于

4、在某一时间点对该世界（系统）的描述。最一般化的便是平铺式表示，即对世界所有可能状态予以标号，以s1,s2,s3,这样的方式表示。这种情况下，标号状态的数目也就代表了状态空间的大小。而一种更加自然的方式是因子化表示，因子化是一种面向对象的思想，这种状态表示方式我们会在结合Robocup的高层设计章节详细讨论。不同的应用中，人们对状态的具体定义是不一样的，但一般来说，在MDP中定义的状态必须包括所有当前世界中Agent 能够掌握利用，会对 Agent 决策产生影响的信息， 这也可做为建模过程中， 某些因素要不要加入问题状态表示的依据。事实上，这些因素，又对应为一些概念，或者说状态变量。要不要将这些

5、变量加入问题的状态表示中， 再或者要不要对概念对应的状态量进行某种拆分或合并，这些问题在建模时都是需要考虑的。处理的不好，便可能引入大量冗余信息。目前，也有专门针对这些问题所作的工作，如识别无关状态(Jong N K, Stone P,2005)，聚类等等 (Givan R, et al, 2003; Li L H, et al, 2006)。大多数情况，智能体对自己所处的当前世界的状态不可能有一个完整的认识。因此，我们引入概率的方法来处理这类信息的不确定性。我们引入随机变量St，随机变量从状态集合S 中取值。变量 St并非由未来时刻的状态所决定，而是由过去状态影响，如图2.2 所示。当前状态

6、环境智能体立即收益行动S0S1S2Sk-2Sk-1Sk名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 36 页 - - - - - - - - - 图 0.2 马尔可夫链 图 2.2 所表示的是一离散的、 随机的动态系统， 图中的每个节点表示在某一时刻的某一状态。对于随机变量St, 有 Pr(St|S0,S1,.,St-1) = Pr(St|St-1) ，为一条件概率。它也同时体现了马尔科夫性质，即St只是概率依赖于St-1。任何两个状态间的关系可以只用两个状态来表示。同

7、时，我们引入 吸收状态 这一概念，如果对于某一状态s，执行任何行动，过程都以概率 1 转移到 s 本身，则该状态 s 被称为吸收状态 (absorb state) 。2.1.3 行动Agent 的行动会参与改变当前世界的状态。MDP 的一个关键部分是提供给Agent 的用于做决策的行动集合。当某一行动被执行，世界状态将会发生改变，根据一个已知的概率分布转换为另一状态，这个概率分布也和所执行的动作有关。不加说明的情况下， 我们讨论的是时齐马尔可夫过程，即所有行动的执行时间是相同的， 状态转移的时间间隔一致。 这种行动有时也可以被称为系统的原子动作。在该系统内，行动已对应最小的时间划分，原子动作不

8、可再分割。比如，在一个棋盘类游戏中，每一步所有的走子方式构成了原子动作的集合。再比如，在一个实时的机器人运动控制中，离散的最小时间片内， 机器人可以选择以一定的离散的角度转向， 或者以一定的离散的加速度进行速度控制，这些也构成了在该系统下的原子动作集合。2.1.4 状态转移函数状态转移函数描述了系统的动态特性，我们可以做以下比较：图 0.3 对给定行动的状态间概率转移图 ?确定环境下的行动： T: SA S 0.2 0.31.00.50.51.00.80.60.4s1s2s3s6s5s40.50.2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -

9、 - - - - 名师精心整理 - - - - - - - 第 3 页，共 36 页 - - - - - - - - - 在某个状态 s 执行动作 a 可以得到一个确定的状态；?随机环境下的行动： T: SA Prob(S) 在某个状态 si下执行某一动作a，我们得到的是一状态的概率分布(|, )jiP ss a ，也记为( , )aTs s 。图 2.3 显示了一个对某给定行动， 状态间概率转移的情况。 在简单的问题中，状态转移函数也可以记为表格的形式。2.1.5 策略与值函数以上都是对模型本身的一些概念的解释，下面我们介绍在MDP 问题求解过程引入的若干概念。决策问题的解称为策略 (pol

10、icy)， 是从状态集合到动作集合的一个映射， 即 : SA。按照策略解决问题的过程是，首先智能体需要知道当前所处状态s，然后执行策略对应的行动 (s) ,并进入下一状态，重复此过程直到问题结束。MDP 中假定 Agent 通过观察可以完全确定当前所处的状态。而该假设不能保证的问题属于 POMDP 模型解决的对象，将在下一章讨论。在MDP 某些材料中对策略有如下区分，若动作的选取只和当前的状态有关，而与时间无关，称作平稳策略；相应的，非平稳策略是经时间索引后的一系列状态到行动的集合，也就是说非平稳策略即使对于同样的状态，在过程的不同时刻，可能会对应不同的行动。我们希望Agent 能够按照某个准

11、则来选择动作以最大化长期的报酬。比如有现阶段最优准则， 要求最大化有限阶段期望总报酬最大，也就是k-1tt=0maxER?，其中 Rt是 Agent 在第 t 步得到的报酬。 如果我们处理的是一个无限阶段问题，考虑整个过程中的总报酬，通常会引入一个折扣因子 ，其中 0 +，我们便无法经由 (0.8)确定满足( )( )VsV s的 (s)。通常，对于一个满足一致性条件的值函数，只按Bellman 公式进行更新迭代的话，一致性条件始终保持成立。最优策略记为*,对应值函数为 V *,称为最优值函数。通常 ,当一个策略满足对状态 s,有*( )( )VsVs- 时,我们称为状态 s 处的最优策略，当

12、对问题所有状态均满足上述条件时，称其为问题的最优策略。2.2 MDP 典型算法马尔可夫决策过程将客观世界的动态特性用状态转移来描述,相关算法可以按是否求解全部状态空间进行划分.早期求解算法有值迭代和策略迭代,这些方法采用动态规划 ,以一种后向的方式同时求解出所有状态的最优策略.随后,一些利用状态可达性的前向搜索算法,如 AO*, LAO* (Hansen E A, Zilberstein, 2001) 被相继提出 ,他们的特点是只求解从给定初始状态开始的最优策略,通常可以避免大量不必要的计算 ,获得更高的效率 .与 AO* 算法比较 , LAO* 能够处理状态转移存在环的系统 .同样利用状态可

13、达性并结合动态规划的算法有: Heuristic Search/DP (HDP)(Bonet, B., Geffner, H, 2003), Envelope Propagation (EP) (Dean, T et al , 1995)以及 Focused Dynamic Programming (FP) (Ferguson D, Stentz A T, 2004). 从另一个角度 ,相关算法还可以按离线或在线划分.对于很多现实世界应用中的大规模问题 ,无论是否利用状态可达性， 解都不可能以离线的方式一次性求出，这种情况更适合使用在线算法,也称为实时算法 .实时算法的决策计算与执行交替进行,

14、且解的质量通常随给定计算时间的增加而提升.最早的基于动态规划的实时算法是 RTDP(Barto A G, et al., 1995) 。 RTDP 通过不断循环 Trail 来改进策略，每次 Trail 确定一个从初始状态到目标状态的路径然后进行反向的值迭代,然而RTDP 不处理停止问题 (Stopping Problem)( Pemberton J C, 1994) 。 停止问题指如何判断当前解的质量是否已满足要求进而停止计算并提交策略供执行.在值迭代类算法中 ,停止问题对应收敛判据 .Labeled RTDP(Bonet B, Geffner H 2003)通过标记各经历状态是否已被求解,

15、给出了一种处理停止问题的方式,同时避免已经求解过的状态处的计算进而加快收敛.最新的实时动态规划算法 ,如 BRTDP (McMahan H 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 36 页 - - - - - - - - - B, 2005)及 FRTDP (SmithT, Simmons R, 2006)使用了另外一种技术 ,求解过程记录并不断更新相关状态期望值函数的上界下界,这些信息用来指导分支选择,显著的提高了算法性能 .另一方面 ,上下界提供了最优值函数的

16、一个区间估计,当给定初始状态的值函数上下界间隔足够小时,便可认为已经获得满足精度的最优策略. 下面将分别介绍几类典型的MDP 求解算法。为了方便对比，我们针对同一类特殊 MDP 问题，随机最短路径问题 (Bertsekas D, 1995) ，它是对传统人工智能中最短路径问题的泛化。 问题存在有限个状态， 在非目标状态执行任何行动将获得一个负的立即收益，达到目标状态后过程终止，过程本身不再引入时间变量。有如下值函数：( )0( )( ,( )( , )( )ssSif sis goal stateVsR ssTs s Vsotherwise?= ?+?(0.9) 2.2.1 反向迭代类算法策略

17、迭代与值迭代是求解MDP 问题的两个最基本的方法， 均基于动态规划。2.2.1.1 策略迭代在策略迭代中 ,策略显式表示 ,可以计算得到对应 V,然后使用下列公式改进策略 : ( , )( , )( , )( )asSQs aR s aTs s Vs=+(0.10) ( )argmax( , )aAsQs a=(0.11) 其中 为折扣因子 (Discount Factor), 1。由于可能的策略数目是有限的， 而策略迭代的过程总是在改进当前的策略，算法在经过有限步的迭代后总会收敛于最优策略。Alg.1: Policy Iteration1. Start with an initial pol

18、icy 2. Evaluation policy: Compute the value function Vfor policy by solving the following set of |S| equations in | S| unknowns, ( )( )( ,( )( , )( )ssSVsR ssTs s Vs=+3. Improve policy : Use equation (0.10)(0.11), Resolve ties arbitrarily, but give preference to the currently selected action. 4. Con

19、vergence test : If is the same as , go to step 5. Otherwise, set = and go to step 2 5. Return an optimal policy . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 36 页 - - - - - - - - - 2.2.1.2 值迭代在值迭代中 ,策略没有显式表示 ,整个过程按动态规划的Bellman 公式不断进行迭代更新来改进值函数。( )max( , )( ,

20、 ) ( )asSV sR s aTs s V s?=+?(0.12) 当值函数经由有界误差衡量接近最优时，策略可以通过(0.13)式获得。对于随机最短路径问题，误差界限可以通过Bellman误差 及平均初过时间(first passage time) 计算得到。每次迭代所有状态值函数更新前后的最大差值称为Bellman 误差 r:max( )( )s SrV sVs=-；平均初过时间指从状态s 开始，按策略 执行，到达一个目标状态的期望时间步数，记为( ) s。平均初过时间可以通过对所有 s求解线性方程组 : ( )1( , ( ), )( )sSsT ss ss= +(0.14) 给定 B

21、ellman 误差与平均初过时间 ,一个最优值函数V*的下界 VL及上界 VU可以按下式计算得到：( )( )( )( )( )( )LUVsVss rVsVss r?=-?=+? ?(0.15) 对于策略迭代， 当前的值函数是最优值函数的一个下界。上界与下界的最大差值定义为： max( )( )ULs SVsVs?-?，当该差值小于 时，策略为 最优。对给定的任意实数 0， 策略迭代与值迭代在经过有限步的迭代后都将收敛于 最优。Alg.2: Value Itertaion 1. Start with an initial evaluation function V and parameter

22、 for detecting convergence to an -optimal evaluation function. 2. Improve evaluation function by Equation(0.12)3. Convergence test: If the error bound of the evaluation function is less than or equal to , go to step 4. Otherwise, set V = V and go to step 2.4. Extract an -optimal policy from the eval

23、uation function by Equation(0.11).2.2.2 前向搜索类算法现实中有些问题并不需要求解从所有状态到达目标状态的策略，而是给定从固定的初始状态开始。 这类问题属于特例，使用策略迭代或者值迭代都可以求解。然而，这两种求解方法都没有利用初始状态的相关知识，没去尝试把计算集中在由初始状态可能达到的那些状态上。相反，无论是策略迭代还是值迭代在每次更新时都会计算所有状态。 从效果上说， 这两种算法计算的是问题所有可能初始状名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

24、- 第 8 页，共 36 页 - - - - - - - - - 态下的策略。下面结合与或图介绍一些基于前向搜索的MDP 求解算法。2.2.2.1 结合与或图的搜索从更一般的情况来讲，一个状态空间上的搜索问题与MDP 类似，可以被定义为一系列状态 (包含了初始状态及目标状态的集合)， 一系列的行动 (智能体干预状态转移 )，以及一个花费函数或者收益函数。问题的目标为找到一个从起点状态到终点状态的最小花费或者最大收益的路径。经典AI 中搜索问题为确定性搜索，如启发式 A* 算法，迭代加深的 IDA* 算法(Bonet B, Geffner H, 2006)等。而从搜索所基于的树或图的数据结构模型

25、的角度来看，不确定性搜索又有其新的特点。同时，它也是一种更一般的模型，与或图(AND/OR graph)。根据 Martelli ，Montanari(1978)及 Nilsson(1980)，可以定义与或图为一个超图(hypergraph) 。区别与普通图中弧连接了一对状态，超图拥有超弧(hyperarcs)或者 k 连接(k-connectors)将一个状态与 k 个后继状态相连。图2.4 将与节点，或节点及超弧， k 连接的概念联系在一起。图2.4.(a)显示了一个或节点及两条从它出发的弧，分别对应行动a1与行动 a2。每条弧导向一个拥有两个后继或节点的与节点，后继或节点即对应了一个可能

26、的后继状态(按约定 ,其中方形代表或节点，圆形代表与节点。在决策分析的术语中， 方形表示选择节点，圆形表示或然节点 )。(b)显示了一个状态，由一个圆形表示，并有两个2 连接从它出发，分别对应行动 a1 及 a2。每个 2 连接导向了两个可能的后继状态。右边的表示法，使用状态与 k 连接，与左边使用与节点及或节点的表示法等价。图 0.4 与或图基本结构 k 连接可以以不同的方式来解释：在问题规约的搜索中，它被解释为将问题转化为 k 个子问题。 当考虑非确定规划问题时， 它被解释为行动不确定性的结果。行动将一个状态转移到k 个可能的后继状态，每个都关联了一个概率。在一个与或图搜索中，以非循环子图

27、形式表示的解被称为解图，有如下定义：a1 a2 a1a2(a) (b)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 36 页 - - - - - - - - - ?起始状态属于解图?对于解图中的每个非目标状态，恰好有一个输出的k 连接（对应一个行动）与其后继状态，这些也都属于解图?解图中每个定向的路径都终结于目标状态。AO* ，LAO* 是较早的两类基于与或图的搜索类算法。它们和经典人工智能中 A* 算法的设计思路类似，还有在迭代加深的IDA* 算法基础上扩展出来的LD

28、FS 算法(Bonet B, Geffner H, 2006)。2.2.2.2 实时动态规划算法与或图给了我们一种理解MDP 求解过程组织方式的一种基本数据结构。事实上，所有利用状态可达性结合前向搜索的方法都显式或隐式的利用这一结构。Barto et al(1995)提出了一种实时动态规划算法(Real-time dynamic programming，RTDP)，也是基于前向搜索的技术，避免穷举所有状态。Alg.3 是对 RTDP 算法的一个总结。RTDP 将计算组织成一系列的试验执行(triials)。每次试验由多步组成，在每一步，行动基于一步前瞻搜索选择， 然后基于所选择行动的所有可能结

29、果对当前状态进行更新。试验在达到目标状态时终止，或者是经过一个指定步数的更新。这种基于试验 (trial-based)的 RTDP 算法一个最主要的特性就是， 它只更新那些基于当前值函数采用贪婪策略选择行动，从初始状态可以到达的状态。 因此，RTDP可以省掉大量无关状态空间处的计算。Barto 证明在一些合理的条件下，RTDP能够渐近收敛于最优解， 而无需评估整个状态空间， 并将这一结果与启发搜索关联，认为它是基于学习的实时启发式搜索算法(LRTA*) 的一个推广 (Hern C, Meseguer P, 2005a, 2005b) 。Alg.3: Trial-based RTDP 1. St

30、art with an admissible evaluation function. 2. Repeat the following trial n times. Trails: Set the current state s to the start state and repeat the following steps mtimes or until a goal state is reached. (a) Improve the evaluation function by performing the following backup for the current state s

31、, by Equation(0.12). (b) Take the action determined to be best for state s by the backup and change the current state s to the state that results from a stochastic transition following the action. 3. Extract a partial policy from evaluation function V by Equation(0.11). 以上我们介绍了 MDP 的后向迭代及前向搜索两大类最基本的

32、算法，后向迭名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 36 页 - - - - - - - - - 代类算法通常具有状态空间， 行动空间，及求解精度的多项式时间的计算复杂度,而前向搜索类算法在求解具体问题时由于利用了状态可达性的信息常常具有更高的效率 (Littman M L, et al., 1995)。2.3 POMDP 基本模型及概念POMDP 适合用来描述在状态非完全可观察的情况下，智能体与环境交互，并进行决策的问题。它与MDP 的区别在于它建模了观察的不

33、确定性，并在模型中引入了信念状态这一个概念， 是一个更一般化的模型， 因而具有更广泛的应用，如对话管理、机器视觉、机器人导航、医疗诊断、网络维护等等。由于问题复杂性的增加，从效率与求解质量平衡的角度出发，POMDP 问题发展出大量近似求解算法。下面首先介绍POMDP 的基本数学模型及决策过程引入的新的概念。2.3.1 基本模型相对于 MDP 模型， POMDP 模型中加入了对观察的处理。图 0.5 POMDP 模型 一般情况下，模型为一个六元组,S A T RO。其中 S,A,T,R与 MDP 模型相同，而增加的部分为：? : 为智能体可观察信息的集合；?O(s ,a,o): :O SAOO

34、为观察函数，给出在执行行动a 并进入下一个状态 s 时可能观察的概率分布，使用Pr(o|s ,a)表示。?B: 智能体的信念状态空间， 使用 b(s)来描述在智能体信念中， 当前处在状态状态评估 (SE) 策略 世界状态O(s,a,o) a b(s)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 36 页 - - - - - - - - - s的概率。2.3.2 观察我们假设一个有限的观察集合12,HOo oo=，智能体观察的选择和对当前状态的感知来自于这个集合。在 P

35、OMDP 模型上，可以通过一系列的假设得到其他的模型。例如全观察(full observable)的 MDP(FOMDP) ，如前所述， Agent 对各个时刻的环境的了解是全面的。那么有以下的定义：1Pr(|,)0hjhikjifosos asotherwise=?=?另一个比较极端的模型是non-observable 系统(NOMDP) 。在这个系统里，Agent 在执行时，不会从系统获得任何的有关当前状态的信息。这样，该系统的观察集合为 O =o ，即，在每个状态获得的观察都是一样，这样观察集合就变得没有意义了。这两种极端情况是POMDP 的特例。2.3.3 信念状态在 POMDP 问题

36、中，智能体的决策过程如图2.6 所示。图 0.6 POMDP 决策过程 由于智能体在 POMDP 中不能保证每步都获得全部的当前状态信息，为了仍保持过程的马尔可夫性， 这里引入了信念状态这一概念。信念状态是智能体根据观察及历史信息计算得到的一个当前状态对所有世界状态的一个概率分布，记为b(s)，有对s?，有0( )1b s ，且( )1s Sb s=。由于它是智能体主观信念上所认为的一个状态，故称为信念状态。作为一个概率分布，信念状态空间是连续的，无限的。a b os abos 行动信念观察状态b(s)T(s,a,s)R(s,a)O(s,a,o )名师资料总结 - - -精品资料欢迎下载 -

37、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 36 页 - - - - - - - - - 图 0.7示例信念状态的简单模型 图 2.7 是一个小的 POMDP 的例子，两个状态，两个观察，一个行动。如果智能体处在状态 s1，时刻 t 并且做出行动后得到观察o2，那么可以确定，智能体仍处在状态 s1。然而，如果它获得观察o1，那么智能体便既可能处在状态s1，也可能处在状态 s2。表 2.1 总结了 4 种可能的结果，各种结果之间互斥，且概率总和为 1。比如，我们还可以看到，执行行动后获得观察o1的情况下，智能体处

38、在状态 s2的概率为 0.8/(0.02+0.8) 0.976。表 0.1 信念状态计算示例 resulting state observation probability of event s1 o1 0.2 0.1=0.02 s1o2 0.2 0.9=0.18 s2 o10.8 1.0=0.80 s2 o20.8 0.0=0.00 2.3.4 主观贝叶斯更新在 POMDP 中，每一步的信念状态都是智能体的一个主观概率，而获得新的观察后，计算新的信念状态便可以使用贝叶斯公式进行更新。具体过程如下：( )Pr( | , , )Pr( | , , )Pr( | , )Pr( | , )Pr( |

39、 , , )Pr( | , , )Pr( | , )Pr( | , )Pr( | , )Pr( | , )Pr( | )Pr( | , )( , , )( , , ) ( )Pr( | , )s Ss Ss Sb ss o a bo s a bsa bo a bo s a bsa b ss a bo a bo s asa ss bo a bO s a oT s a s b so a b= = =(0.16) 其中：s1s20.2 0.81.0o1:0.1o2:0.9o1:1.0o2:0.0名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

40、- - 名师精心整理 - - - - - - - 第 13 页，共 36 页 - - - - - - - - - Pr( | , )Pr( , | , )Pr( | , )Pr(|, , )Pr( | , ) ( )Pr(| , )( , , )( , , ) ( )sSsSsS s SsSs So a bo sa bsa bo s a bsa s b so s aO s a oT s a s b s=(0.17) 通过反复的使用贝叶斯公式， 便可以得到上述信念状态的更新公式。通过它我们可以从当前的信念状态，根据转移函数T 及观察矩阵 O 得到新的信念状态对应的概率分布。对于同一个观察，分母P

41、r(o|a,b)为一个常数，事实上，它起到的就是归一化因子的作用，使得概率分布总和为1。图 2.8 展示了信念空间的表示方法。在此我们举了一个很简单的2-状态的 POMDP 作为实例。对于一个2-状态 POMDP，给定一个状态的概率是p，则另一个状态的概率是1-p。在这个例子里，信念空间可以用一条线段来表示。信念空间的左边标记为0，右边标记为1，用来表示当前状态为s1的概率。在高维空间中，该线段将变成超平面。图 0.8 状态 POMDP 的一维信念空间 图 2.9 中展示了一个 2 状态的 POMDP 中信念状态的变化情况。假设智能体有两个动作（ a1，a2）和三个观察（ z1, z2, z3

42、 ） 。图中较大的点为初始信念状态，结果的信念状态用较小的点表示。弧表示了信念状态的变换过程。 由于观察是概率的，每个结果也和概率有关。 信念状态的转移过程满足马尔科夫性，即下一个信念状态只依赖于当前信念状态（还有当前的动作和得到的观察），而跟历史信念状态无关。图 0.9 状态 POMDP 的一维信念空间 0 10 1a1a2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 36 页 - - - - - - - - - 2.3.5 策略表示形式在 POMDP 问题中，智能

43、体通常不知道环境明确的状态，而只知道一个在所有状态上的概率分布。 MDP 问题中策略可以用状态到行动的映射来表示，但面对连续的信念状态空间， 这一方法不再可行。 事实上，存在一种有限状态机 (finite states controller，FSC)的表示法 (Hansen E A, 1997)，它会涉及 POMDP 问题值函数的一种性质，我们留在稍后介绍。一般情况下，在 POMDP 问题中，智能体的t 步非平稳策略可以用策略树来表示。根节点决定要采取的第一个动作，然后根据得到的观察， 通过一条弧指向下一节点，这个节点在决定下一步的动作，如图2.10 所示即是一个 t 步策略树。在根节点处，我

44、们有( )( , ()pVsR s a p=。图 0.10 一棵 t-step策略树 这里( )a p 是策略树p 的根节点指定的动作。上式所示即为在初始状态按照策略树 p 选择要执行的动作所能获得的报酬。那么，有：()()( )( , ()()( ,( )Pr( | , ()Pr(| , ()( )( ,( )( , (), )( , (),)( )tttptopsSsStopsSoVsR s a pR s a pss a pos a p VsR s a pT s a psO s a po Vs=+=+=+将来的期望值(0.18) 其中，ot(p)是 t 步策略树根节点的其中一棵t-1 步子

45、策略树，与观察 ot相关。通过信念状态的引入， POMDP 问题可以看成 Belief MDP 问题(Strehl A L, 2004)。a(p)a(p)a(p)a(p)o1o2oka(p)a(p)a(p)a(p)o1o2okt step t-1 step t-2 step t-k step 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 36 页 - - - - - - - - - 定 义 类 似MDP中 状 态 转 移 函 数 的 信 念 状 态 转 移 函数: (

46、 , ,):0,1b a bBAB ，有：( , , )Pr( | , )Pr( | , , )Pr( | , )o Ob a bba bba b oo a b=定义信念报酬函数：( , )( )( , )s Sb ab s R s a=可以得到一个类似MDP 中策略与值函数的计算公式：*( )argmax( ) ( , )Pr( | , )( )ttas So Obb s R s ao a b Vb?=+?(0.19) *( )max( )( , )Pr( | , )( )ttas So OVbb s R s ao a b Vb?=+?(0.20) 当然，有这样的公式并不代表就能按照MDP

47、中类似的求解方法进行下去，最根本原因还是连续的信念状态空间造成的。2.3.6 值函数表示形式在 MDP 中，值函数 V(s)对应了有限个状态的评价值，而对于具有无限个信念状态的 POMDP 问题，也需要寻找一种值函数的有效表示方法。事实上，信念状态下值函数有其本身的特性，即PWLC(piecewise linear and convex) 性质，图2.11 显示了一个 2-状态 POMDP 的例子，其中 pk表示某策略树。图 0.11 简单的 PWLC 函数和它在信念空间上的划分 其对应的值函数是一个分段线性凹函数。由于初始 0-step的值函数总是由立即收益确定的直线或者超平面(多个状态的情

48、况 )，而每次迭代对上一步的值函数做的都是一个线性变化。因而，在有限步的POMDP 问题中，其值函数永远都可0 1 b1 23 (p1) (p2) (p3)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 36 页 - - - - - - - - - 以用一个分段线性凹函数表示(在无限步情况下，其极限的情况可能是曲线)。这意味着对每次值迭代， 只需要找到有限个线段或者超平面来表示值函数即可。进而，由于组成值函数的每一个超平面都可记为信念状态空间的一个向量(维度即原问题的状

49、态数 )，它们分别与给定信念状态对应的向量做内积，取最大便可完全确定该信念状态处对应值函数的值。做形式化的表示，每个构成值函数的超平面对应的向量可记为：12( )( ),(),()pppnpVsVsVs= ，其中 p 表示该向量对应的子策略。进而有：( )( )( )( )( )ppps SVbb s VsVbbp=?=?。 那么，根据上述讨论可以知道，值函数可以定义为：( )max( )tpPV bbp=?。进 而 ， 也 可以 看到 ， 对 于一 个 t-step 的 策 略树 ，其最 大的 节 点 数为(|1)/ (| 1)t - -，其中 | 表示每一层可能的观察数，每个节点所采取的行

50、动有|A 种可能，因此，计算该策略的时间复杂度为：| |1| | 1(|)tTimeOA -=。策略树的时间复杂度为一个指数函数，因此，普通的解决POMDP 的算法将会是一个NP-hard问题。2.4 POMDP 典型算法POMDP 的求解算法一样可以按前向后向分类。在后向迭代类算法中，POMDP 的策略迭代算法并不会直接去对策略树进行，而是会用到有限状态机的概念。所谓的有限状态机事实上可以理解为构成满足PWLC 性质的的值函数的有限个向量。也因此，对于无限步的情况，当PWLC 不能保证时，用有限状态机来表示策略同样不一定可行，当然，求近似解的情况除外。Hansen(1997) 描述过一种改进