·22· 智能系统学报 第2卷 g:S XA Xp→S 广.它首先学习系统模型，然后利用该模型计算当前 根据MDP模型为M,构造确定性模型M的过 策略的值，并且可以计算策略值相对于策略参数的 程如下： 梯度.在自行车问题中，EDA算法比PEGASUS收 行为空间不变，状态由原来的S变成S':SX 敛要快，并且利用的策略也比较简单.但是，EDA 0,11°，也就是说，在M中，一个状态为向量(s,p1, 算法需要学习系统模型，并且认为系统模型的模型 p2,),s为M的状态.例如，假设在1时刻状态为 是线性的，或者至少是局部线性的，这就限制了该算 (s,p1,p2,y,行为为a,则1+1时刻的状态为 法的应用范围 (s+1,p2,p,,式中：s+1=g(s,a,p).对于某 4.3和SVM结合的策略搜索方法 个策略π∈Π，其在策略空间Π的对应策略为π' 策略梯度方法由于方差过大，导致收敛速度很 (s,p1,p2,…=I(.最后，令R'(s,p1,p2,…=R 慢，即使很简单的问题，也要学习很长的时间.并且， ( 往往初始策略是随机给定的，因此学习的过程中，尤 根据上述的构造方法，对于2个对应的策略π 其是学习的早期，学习体会选择一些不正确的行为， ∈和π'∈Π'有下式成立： 在实际的试验中，这些不正确的行为可能会引起各 Vwπ)=Vr(I 38 种事故.基于上述2点，王学宁等把SVM引入到策 这也就隐含了关系式opt(M,=op1(M', 略梯度学习方法中来，提出了一种混合式策略梯度 T),也就是说，根据模型M',在策略空间中寻找到 增强学习方法1.在该方法中，初始策略不是随机 的最优策略，其对应策略也是在原问题中的最优策 给定的，而是根据先验知识，或者人为控制，产生一 略.在确定性模型中，因为状态转移是确定性的，所 些样本点，然后根据这些样本点，利用SVM方法产 以如果给定策略π∈Π'，状态s∈S',那么此时刻以 生一个初始策略.这个初始策略往往是可行的，但不 后的所有状态也就完全确定了.因此计算该状态值 是最优的，因此，再利用策略梯度方法对这个初始策 V(s)也就相应的简单了.假设问题有m个初始状 略进行优化.再利用优化之后的策略产生一些样本 态，第1个初始状态记为s,则策略r的值可用下 点，根据这些样本点，利用SVM方法产生一个初始 式计算： 策略，再利用策略梯度方法进行优化，如此循环往 (39 复，使得策略达到一个局部最优解」 m 4.4层次化策略梯度方法 使得优化指标n最大的策略，也就是使得V)最大 对于大规模的问题，比如说状态和行为都是连 的策略，因此，现在问题转化为寻找最优策略 续的，直接求解比较困难，甚至是无法求解.但是如 '=arg maxv() 40 果把问题分解成若干个小问题，往往就能迎刃而解， 为此需要知道求解该梯度有2种方法。一 这就是层次化增强学习方法的基本思想.在cha 种是数值方法，一种是解析方法).数值方法就是 vamzadeh等提出层次化策略梯度(Hierarchical Policy Gradient)算法之前36]，已经有很多关于层次 给每个参数一个小小的扰动，根据这个扰动来计算 梯度，梯度的第1个分量为 化值函数方法的文献B7. ay@-L0±el:'0.l Chavamzadeh等提出的HPG算法中，把问题 80 2a 分为2层，下层是分解后的小问题，上层是在某一时 式中：e=0,0,…1,0,…,0,即第i个分量为1， 刻选择需要解决哪个小问题.利用策略梯度算法进 其他分量为0的向量，其维数和8相同.解析方法比 行下层问题的求解，而利用值函数方法进行上层的 较繁琐，这里不在赘述，详情请参看文献[31]： 学习.该方法可以有效地解决大规模问题 相比较而言，PEGAUSU算法收敛速度比其他 5结论 算法都快，但是，该算法只能应用到仿真试验中，目 前，己经有利用PEGASUS算法成功控制直升机的 尽管策略梯度增强学习方法从1992年已经被 例子z],Strens等利用成对比较法(paired compari- 提出，但是，到了2000年前后，才逐渐引起人们的注 sions)提高了PEGASUS算法的性能，并且解决了 意.虽然刚刚经过几年的发展时间，己经有众多的策 “过拟合”的问题3 略梯度算法被提出.但是，由于策略梯度方法的收敛 4.2本质动力学算法 速度太慢，导致策略梯度还不能应用到大规模的问 本质动力学算法实质上是线性二次调节器的推 题之中因此，策略梯度算法中需要研究的就是如何 @1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.netg ∶S ×A ×p →S 根据 MDP 模型为 M ,构造确定性模型 M′的过 程如下 : 行为空间不变 , 状态由原来的 S 变成 S′: S × [0 ,1 ] ∞ ,也就是说 ,在 M′中 ,一个状态为向量(s, p1 , p2 , …) ,s 为 M 的状态. 例如 ,假设在 t 时刻状态为 (st , p1 , p2 , …) ,行为为 at , 则 t + 1 时刻的状态为 (st + 1 , p2 , p3 , …) ,式中 :st + 1 = g (st , at , p1 ) . 对于某 个策略π∈∏,其在策略空间 ∏′的对应策略为π′ (s, p1 , p2 , …) =π(s) . 最后 ,令 R′(s, p1 , p2 , …) = R (s) . 根据上述的构造方法 ,对于 2 个对应的策略π ∈∏和π′∈∏′,有下式成立 : V M (π) = V M′(π′) . (38) 这也就隐含了关系式 opt ( M , ∏) = opt ( M′, ∏′) ,也就是说 ,根据模型 M′,在策略空间中寻找到 的最优策略 ,其对应策略也是在原问题中的最优策 略. 在确定性模型中 ,因为状态转移是确定性的 ,所 以如果给定策略π∈∏′,状态 s ∈S′,那么此时刻以 后的所有状态也就完全确定了. 因此计算该状态值 V π M′(s) 也就相应的简单了. 假设问题有 m 个初始状 态 ,第 i 个初始状态记为 s ( i) 0 ,则策略π的值可用下 式计算 : V M′(π) ≈ 1 m ∑ m i = 1 V π M′(s ( i) 0 ) . (39) 使得优化指标η最大的策略 ,也就是使得 V (π) 最大 的策略 ,因此 ,现在问题转化为寻找最优策略 π3 = arg max π V (π) . (40) 为此需要知道 5V 5θ,求解该梯度有 2 种方法 ,一 种是数值方法 ,一种是解析方法[31 ] . 数值方法就是 给每个参数一个小小的扰动 ,根据这个扰动来计算 梯度 ,梯度的第 i 个分量为 5V (θ) 5θi = V (θ+αei) - V (θ- αei) 2α . 式中 :ei = (0 ,0 , …, 1 , 0 , …, 0) ,即第 i 个分量为 1 , 其他分量为 0 的向量 ,其维数和θ相同. 解析方法比 较繁琐 ,这里不在赘述 ,详情请参看文献[31 ]. 相比较而言 ,PEGAUSU 算法收敛速度比其他 算法都快 ,但是 ,该算法只能应用到仿真试验中. 目 前 ,已经有利用 PEGASUS 算法成功控制直升机的 例子[ 32 ] . Strens 等利用成对比较法(paired compari2 sions) 提高了 PEGASUS 算法的性能 ,并且解决了 “过拟合”的问题[ 33 ] . 4. 2 本质动力学算法 本质动力学算法实质上是线性二次调节器的推 广. 它首先学习系统模型 ,然后利用该模型计算当前 策略的值 ,并且可以计算策略值相对于策略参数的 梯度. 在自行车问题中 , EDA 算法比 PEGASUS 收 敛要快 ,并且利用的策略也比较简单[34 ] . 但是 ,EDA 算法需要学习系统模型 ,并且认为系统模型的模型 是线性的 ,或者至少是局部线性的 ,这就限制了该算 法的应用范围. 4. 3 和 SVM 结合的策略搜索方法 策略梯度方法由于方差过大 ,导致收敛速度很 慢 ,即使很简单的问题 ,也要学习很长的时间. 并且 , 往往初始策略是随机给定的 ,因此学习的过程中 ,尤 其是学习的早期 ,学习体会选择一些不正确的行为 , 在实际的试验中 ,这些不正确的行为可能会引起各 种事故. 基于上述 2 点 ,王学宁等把 SVM 引入到策 略梯度学习方法中来 ,提出了一种混合式策略梯度 增强学习方法[35 ] . 在该方法中 ,初始策略不是随机 给定的 ,而是根据先验知识 ,或者人为控制 ,产生一 些样本点 ,然后根据这些样本点 ,利用 SVM 方法产 生一个初始策略. 这个初始策略往往是可行的 ,但不 是最优的 ,因此 ,再利用策略梯度方法对这个初始策 略进行优化. 再利用优化之后的策略产生一些样本 点 ,根据这些样本点 ,利用 SVM 方法产生一个初始 策略 ,再利用策略梯度方法进行优化 ,如此循环往 复 ,使得策略达到一个局部最优解. 4. 4 层次化策略梯度方法 对于大规模的问题 ,比如说状态和行为都是连 续的 ,直接求解比较困难 ,甚至是无法求解. 但是如 果把问题分解成若干个小问题 ,往往就能迎刃而解. 这就是层次化增强学习方法的基本思想. 在 Cha2 vamzadeh 等提出层次化策略梯度 ( Hierarchical Policy Gradient) 算法之前[36 ] ,已经有很多关于层次 化值函数方法的文献[37 - 39 ] . Chavamzadeh 等提出的 HPG 算法中 ,把问题 分为 2 层 ,下层是分解后的小问题 ,上层是在某一时 刻选择需要解决哪个小问题. 利用策略梯度算法进 行下层问题的求解 ,而利用值函数方法进行上层的 学习. 该方法可以有效地解决大规模问题. 5 结 论 尽管策略梯度增强学习方法从 1992 年已经被 提出 ,但是 ,到了 2000 年前后 ,才逐渐引起人们的注 意. 虽然刚刚经过几年的发展时间 ,已经有众多的策 略梯度算法被提出. 但是 ,由于策略梯度方法的收敛 速度太慢 ,导致策略梯度还不能应用到大规模的问 题之中. 因此 ,策略梯度算法中需要研究的就是如何 ·22 · 智 能 系 统 学 报 第 2 卷