第1期 闫书亚，等：概率规划的研究与发展 ·11 态变量且∫是数值状态变量上的实值函数， 显然价值迭代算法和策略迭代算法可以用于求 4)r↑f是一效果，如果f是数值状态变量上 解上述问题 的实值函数： 2.1.1价值迭代算法 5)e个…八en是效果，如果e,em是 价值迭代算法(value iteration,VI)）是求解 效果： MDP问题的一种经典的动态规划算法，它从任意 6)c>e是效果，如果c是V上的一个公式且e 的初始评估值开始，通过迭代来求解方程.令f:(s 是一个效果： 为状态s在第i次迭代中的评估值，那么价值迭代 )pme…|pmen是效果，如果a,en是 执行下述更新： 效果，对于所有i∈{1，n},p:≥0且 f(s)=min [c(a.s)+>T(s,a.s)f(s)1. >p.=1. 2 其中2)~4)称为简单效果，x一∫意为当前状 如果无限地应用贝尔曼更新方程，价值迭代最终会 态中的值f在下一状态变为数值状态变量x的值， 收敛在贝尔曼方程组的惟一解上.在这种情况下， 效果r↑∫用来与转移回报相联系 对应的策略是最优的 动作a=(虫，ea〉定义了一个转移概率矩阵P。 和转移回报矩阵R。,p表示在状态i上运用动作 (=arg ile(a.T(s.a.s)f(s)1. a,转移到状态j时的概率：表示在状态i上运用 (3) 动作a,转移到状态j时得到的回报.效果c>e定 对于s∈S,当lf:(-f1(s川≤e,价值迭 义了一组状态转移，其中e是简单效果的合取.计 代算法停止，其中￡>0是给定的误差界限，即当评 算P。和Ra时，可首先将ea转化为p1e|…| 估函数∫足够接近于最优时，价值迭代算法停止： pmem,其中e是确定效果.具体的转化方法见文献 但是，由于V1更新每一个状态的值，它求解的过 187. 程是相当缓慢的.一个优化的措施是当它进行状态 当结果为多个效果pmel…pren时，具有同 更新时，对其进行限制，只更新那些从初始状态可 样的转移，这时要求一个特定转移的回报与结果是 以到达的状态的评估值 一致的 2.1.2策略迭代算法 2概率规划求解方法 价值迭代算法中，在每一时间步，评估函数只 是被用来计算动作，而策略则没有被显式地存储或 2.1动态规划算法 记录.策略迭代，在求解过程中则在存储更新评估 一个概率规划问题通常可以模型化为随机最短 值的同时也存储并更新策略的值， 路径问题(stochastic shortest path problems, 策略迭代算法从某个初始策略乃开始，交替 SSPs)2o).随机最短路径问题是一类特殊的马尔可 执行下面的2个步骤22-21： 夫决策问题(Markov decision problems,MDPs). 1)策略评价：确定当前策略的评估函数∫，即 SSPs为一个六元组：(S,A,T,c,G,S),其中， 给定策略刀，计算”； S是一组有限状态的集合：A是有限动作的集合， 2)策略改进：基于当前评估函数，更新当前策 对任一s∈S,A(表示在状态s上的可用动作的集 略，即当前策略π不是最优策略时，利用更新方 合；T是转移模型，即对在每个可能状态中的每种 程，找到一个新的策略π’，使得对任一状态， 行动的结果概率的详细说明.对于s,s’∈S,T(s, ∫”()≤f”(),并且至少存在一个状态i,使得 a,s')表示在状态s上执行动作a时到达状态s'的 f()<f(). 概率；c是代价函数，对任一s∈S,a∈A(s, 当策略改进步骤没有产生评估值的改变时，算 c(a,s表示在状态s上执行动作a的立即代价；G 法终止.对于有限的状态空间而言，策略数是有限 是目标集，GSS;S∈S是初始状态 的，并且每一次迭代都可以产生更好的策略，所以 这时，求解概率规划问题即转换为求解下述不 动点方程： 在有限次迭代后，算法会收敛于一个最优策略，并 终止 (=mc(a(s.a.s)f(s)1. 因为策略把每个状态中的行动都固定了，在第 1) i次迭代中，策略兀指定了状态s中的行动π：(s), 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net态变量且 f 是数值状态变量上的实值函数; 4) r ↑f 是一效果 , 如果 f 是数值状态变量上 的实值函数; 5) e1 ∧ … ∧en 是效果 , 如果 e1 , …, en 是 效果; 6) c þ e 是效果 , 如果 c 是 V 上的一个公式且 e 是一个效果; 7) p1 e1 | …| pne n 是效果 , 如果 e1 , …, en 是 效果 , 对 于 所 有 i ∈{ 1 , …, n } , pi ≥0 且 ∑ n i = 1 pi = 1 . 其中 2) ～4) 称为简单效果 , x ←f 意为当前状 态中的值 f 在下一状态变为数值状态变量 x 的值 , 效果 r ↑f 用来与转移回报相联系. 动作 a =〈<a , ea〉定义了一个转移概率矩阵 Pa 和转移回报矩阵 Ra , p a ij 表示在状态 i 上运用动作 a , 转移到状态 j 时的概率; r a ij表示在状态 i 上运用 动作 a , 转移到状态 j 时得到的回报. 效果 c þ e 定 义了一组状态转移 , 其中 e 是简单效果的合取. 计 算 Pa 和 Ra 时 , 可首先将 ea 转化为 p1 e1 | … | pne n , 其中 ei 是确定效果. 具体的转化方法见文献 [18 ]. 当结果为多个效果 p1 e1 | …| pne n 时 , 具有同 样的转移 , 这时要求一个特定转移的回报与结果是 一致的. 2 概率规划求解方法 2. 1 动态规划算法 一个概率规划问题通常可以模型化为随机最短 路 径 问 题 ( stochastic shortest path problems , SSPs) [ 20 ] . 随机最短路径问题是一类特殊的马尔可 夫决策问题 (Markov decision problems , MDPs) . SSPs 为一个六元组〈: S , A , T , c , G, S0 〉, 其中 , S 是一组有限状态的集合; A 是有限动作的集合 , 对任一 s ∈S , A (s) 表示在状态 s′上的可用动作的集 合; T 是转移模型 , 即对在每个可能状态中的每种 行动的结果概率的详细说明. 对于 s, s’∈S , T (s, a , s’) 表示在状态 s 上执行动作 a 时到达状态 s’的 概率; c 是代价函数 , 对任一 s ∈S , a ∈A ( s) , c( a , s) 表示在状态 s 上执行动作 a 的立即代价; G 是目标集 , G ΑS ; S0 ∈S 是初始状态. 这时 , 求解概率规划问题即转换为求解下述不 动点方程[21 ] : f (s) = min a∈A (s) [ c( a ,s) + s′∑∈S T (s, a ,s′) f (s′) ]. (1) 显然价值迭代算法和策略迭代算法可以用于求 解上述问题. 2. 1. 1 价值迭代算法 价值迭代算法 ( value iteration , VI) 是求解 MDP 问题的一种经典的动态规划算法 , 它从任意 的初始评估值开始 , 通过迭代来求解方程. 令 f i (s) 为状态 s 在第 i 次迭代中的评估值 , 那么价值迭代 执行下述更新 : f i+1 (s) = min a∈A (s) [ c( a ,s) + s′∑∈S T (s, a ,s′) f (s′) ]. (2) 如果无限地应用贝尔曼更新方程 , 价值迭代最终会 收敛在贝尔曼方程组的惟一解上. 在这种情况下 , 对应的策略是最优的. π(s) = arg min a ∈A (s) [ c( a ,s) + s′∑∈S T (s, a ,s′) f (s′) ]. (3) 对于 Πs ∈S , 当| f i (s) - f i - 1 (s) | ≤ε, 价值迭 代算法停止 , 其中ε> 0 是给定的误差界限 , 即当评 估函数 f 足够接近于最优时 , 价值迭代算法停止. 但是 , 由于 V I 更新每一个状态的值 , 它求解的过 程是相当缓慢的. 一个优化的措施是当它进行状态 更新时 , 对其进行限制 , 只更新那些从初始状态可 以到达的状态的评估值. 2. 1. 2 策略迭代算法 价值迭代算法中 , 在每一时间步 , 评估函数只 是被用来计算动作 , 而策略则没有被显式地存储或 记录. 策略迭代 , 在求解过程中则在存储更新评估 值的同时也存储并更新策略的值. 策略迭代算法从某个初始策略π0 开始 , 交替 执行下面的 2 个步骤[22223 ] : 1) 策略评价 : 确定当前策略的评估函数 f , 即 给定策略π, 计算 f π ; 2) 策略改进 : 基于当前评估函数 , 更新当前策 略 , 即当前策略π不是最优策略时 , 利用更新方 程 , 找到一个新的策略 π’, 使得对任一状态 i , f π’( i) ≤f π ( i) , 并且至少存在一个状态 i , 使得 f π’( i) < f π ( i) . 当策略改进步骤没有产生评估值的改变时 , 算 法终止. 对于有限的状态空间而言 , 策略数是有限 的 , 并且每一次迭代都可以产生更好的策略 , 所以 在有限次迭代后 , 算法会收敛于一个最优策略 , 并 终止. 因为策略把每个状态中的行动都固定了 , 在第 i 次迭代中 , 策略πi 指定了状态 s 中的行动πi (s) , 第 1 期 闫书亚 ,等 :概率规划的研究与发展 · 11 ·