马尔可夫决策基础理论
内容提要
本章介绍与研究背景相关的几类决策模型及算法。模型部分，首先是最基本的马尔可夫决策模型，然后是在此基础上加入观察不确定性的部分可观察马尔可夫决策模型，以及进一步加入多智能体的分布式部分可观察马尔可夫决策模型和部分可观察的随机博弈模型。算法部分，针对上述几类模型，我们均按照后向迭代和前向搜索两大类进行对比分析。最后，我们介绍了半马尔可夫决策模型及Option理论，这一理论为我们后面设计分等级的大规模多智能体系统的决策模型及规划框架提供了重要基础。
2.1 MDP基本模型及概念
马尔可夫决策过程适用的系统有三大特点：一是状态转移的无后效性；二是状态转移可以有不确定性；三是智能体所处的每步状态完全可以观察。下面我们将介绍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，执行动作
P s s a；
a，而转移到状态s’的概率('|,)
♦报酬函数R: S×A→R：我们一般用R(s,a)来表示在状态s执行动作a所能得到的立即报酬。
虽然有针对连续参数情况的MDP模型及算法，然而本文在没有特殊说明的情况都只讨论离散参数的情况，如时间，状态及行动的参数。
图2.1描述的是在MDP模型下，智能体(Agent)与问题对应的环境交互的过程。智能体执行行动，获知环境所处的新的当前状态，同时获得此次行动的立即
收益。
边程
图 0.1 MDP 的基本模型 2.1.2 状态 状态是对于在某一时间点对该世界（系统）的描述。最一般化的便是平铺式表示[]，即对世界所有可能状态予以标号，以s 1,s 2,s 3,…这样的方式表示。这种情况下，标号状态的数目也就代表了状态空间的大小。而一种更加自然的方式是因子化表示，因子化是一种面向对象的思想，这种状态表示方式我们会在结合Robocup 的高层设计章节详细讨论。
不同的应用中，人们对状态的具体定义是不一样的，但一般来说，在MDP 中定义的状态必须包括所有当前世界中Agent 能够掌握利用，会对Agent 决策产生影响的信息，这也可做为建模过程中，某些因素要不要加入问题状态表示的依据。事实上，这些因素，又对应为一些概念，或者说状态变量。要不要将这些变量加入问题的状态表示中，再或者要不要对概念对应的状态量进行某种拆分或合并，这些问题在建模时都是需要考虑的。处理的不好，便可能引入大量冗余信息。目前，也有专门针对这些问
题所作的工作，如识别无关状态(Jong N K, Stone P,2005)，聚类等等(Givan R, et al, 2003; Li L H, et al, 2006)。 大多数情况，智能体对自己所处的当前世界的状态不可能有一个完整的认
识。因此，我们引入概率的方法来处理这类信息的不确定性。我们引入随机变量S t  ，随机变量从状态集合S 中取值。变量S t  并非由未来时刻的状态所决定，而是由过去状态影响，如图2.2 所示。
行动
图 0.2 马尔可夫链
图2.2 所表示的是一离散的、随机的动态系统，图中的每个节点表示在某一时刻的某一状态。对于随机变量S t, 有Pr(S t|S0,S1,...,S t−1) = Pr(S t|S t−1) ，为一条件概率。它也同时体现了马尔科夫性质，即S t只是概率依赖于S t−1。任何两个状态间的关系可以只用两个状态来表示。
同时，我们引入吸收状态这一概念，如果对于某一状态s，执行任何行动，过程都以概率1转移到s本身，则该状态s被称为吸收状态(absorb state)。
2.1.3 行动
Agent 的行动会参与改变当前世界的状态。MDP的一个关键部分是提供给Agent的用于做决策的行动集合。当某一行动被执行，世界状态将会发生改变，根据一个已知的概率分布转换为另一状态，这个概率分布也和所执行的动作有关。不加说明的情况下，我们讨论的是时齐马尔可夫过程，即所有行动的执行时间是相同的，状态转移的时间间隔一致。这种行动有时也可以被称为系统的原子动作。在该系统内，行动已对应最小的时间划分，原子动作不可再分割。比如，在一个棋盘类游戏中，每一步所有的走子方式构成了原子动作的集合。再比如，在一个实时的机器人运动控制中，离散的最小时间片内，机器人可以选择以一定的离散的角度转向，或者以一定的离散的加速度进行速度控制，这些也构成了在该系统下的原子动作集合。
2.1.4 状态转移函数
状态转移函数描述了系统的动态特性，我们可以做以下比较：
0.5
图 0.3 对给定行动的状态间概率转移图
♦确定环境下的行动：T: S×A→S
在某个状态s 执行动作a 可以得到一个确定的状态；
♦ 随机环境下的行动：T: S×A →Prob(S) 在某个状态s i 下执行某一动作a ，我们得到的是一状态的概率分布(|,)j i P s s a ，也记为(,')a T s s 。
图2.3显示了一个对某给定行动，状态间概率转移的情况。在简单的问题中，状态转移函数也可以记为表格的形式。 2.1.5 策略与值函数 以上都是对模型本身的一些概念的解释，下面我们介绍在MDP 问题求解过程引入的若干概念。 决策问题的解称为策略(policy)，是从状态集合到动作集合的一个映射，即
π : S →A 。按照策略解决问题的过程是，首先智能体需要知道当前所处状态s ，然后执行策略对应的行动π(s) ，并进入下一状态，重复此过程直到问题结束。MDP 中假定Agent 通过观察可以完全确定当前所处的状态。而该假设不能保证的问题属于POMDP 模型解决的对象，将在下一章讨论。在MDP 某些材料中对策略有如下区分，若动作的选取只和当前的状态有关，而与时间无关，称作平稳策略；相应的，非平稳策略是经时间索引后的一系列状态到行动的集合，也就是说非平稳策略即使对于同样的状态，在过程的不同时刻，可能会对应不同的行动。 我们希望Agent 能够按照某个准则来选择动作以最大化长期的报酬。比如有现阶段最优准则，要求最大化有限阶段期望总报酬最大，也就是k -1t t=0maxE R ⎡⎤⎢⎥⎣⎦∑，其中R t 是Agent 在第t 步得到的报酬。如果我们处理的是一个无限阶段问题，考虑整个过程中的总报酬，通常会引入一个折扣因子γ，其中0<γ <1。这样Agent 选择动作所得到的报酬是k-1t t t=0maxE R γ⎡⎤⎢⎥⎣⎦∑。折扣因子保证了k-1t t t=0maxE R γ⎡⎤⎢⎥⎣⎦∑的收敛性。 事实上，一个过程本质上是在因果关系下的推进，而并非时间推进本身。当可以把时间也作为一个变量加入状态描述中时，前面提到过的有限阶段与无限阶段，以及这里的平稳策略与非平稳策略，都可以统一起来理解。首先，对于有限阶段和无限阶段的问题，长期期望回报是用来评价策略优劣的，理论上它不能出现无穷大的情况，这样将无法比较。而在所谓的无限阶段中，这一点却很难保证。事实上，对于一个现实中决策的智能体来说，无限阶段是不存在的，其生存周期决定了这一点。于是，折扣因子的另一个含义是人为的认定过程在每步执行都有较小的非零的概率1 − γ终止。这样，该过程能无限进行下去的概率为0，无限
阶段的问题仍是转换成了有限阶段。因此，两者都是依靠问题的终止状态来结束，并无本质区别。同样，当时间可以成为状态变量后，平稳策略与非平稳策略也可以统一起来考虑，所谓的靠时间索引的策略也将变成统一的状态到行动的映射了。在本文后面的部分，无特殊说明的情况下，将不对有限阶段或无限阶段，以及平稳策略或非平稳策略加以区别。 对于任何一个策略，我们都可以用执行该策略所能获得的长期期望回报来评价其优劣。 定义值函数(Value Function):V S π→ 为采用策略π时在状态s 的期望回报：  0()(,())t t t t V s E R s s πγπ∞=⎡⎤=⎢⎥⎣⎦∑ (0.1) 其中t s 为时刻t 所处状态，0t =对应初始状态s 。以递归的形式表示则为：  ()'()(,())(,')(')s s S V s R s s T s s V s ππππγ∈=+∑  (0.2) 对每个策略π，其对应的值函数V π是一系列线性方程(每个状态s 对应一个方程)的唯一公共解。在某些文献中值函数也被称为评价函数(evaluation function)。 上述定义给了我们一种计算策略对应的值函数的方法，同时，我们也需要知道如何从值函数来计算得到相应策略。首先，定义一个求解过程常常用到的中间变量，行动值函数:Q S A π×→ 为在状态s 采用行动a ，其它状态采用策略π的期望回报。  '(,)(,)(,')(')a s S Q s a R s a T s s V s ππγ∈=+∑ (0.3) 当策略没有显式记录，只有值函数V 时，行动值函数记为Q 。策略π可以通过下式计算得到：  ()arg max (,)a A s Q s a π∈= (0.4) 即：
'()arg max (,)(,')(')a a A s S s R s a T s s V s πγ∈∈⎧⎫=+⎨⎬⎩⎭∑ (0.5) 同时有：  '()max (,)(,')(')a a A s S V s R s a T s s V s πγ∈∈⎧⎫=+⎨⎬⎩⎭∑ (0.6) 由于(0.5)式事实上是采用的一步前瞻的贪婪搜索，我们也称这样获得的策略为贪婪策略。