第4期 刘全，等：一种逻辑强化学习的tableau推理方法 ·357 的活动集A(s)∈A:T为迁移，对于每个ss'∈S和 态0是{g(f(x))≈，g()≈f(五， a∈A(,都存在一个迁移T使得状态从s转移到 P(g(f(a),b).如果一个可能状态中存在互补 s,即表示为，严s!这里p表示由活动a引起的 对，那么该状态称为封闭状态.抽象状态{门P(a, 从状态s迁移到s的概率，且对于每个s∈S,a∈A都 c以，gf))≈，g&≈f(,P(g(fa,b, 满足(y:∑esp(3a,s)=L对于每个迁移，Agent P(a,b),P(,c以在替换a/:后，是封闭状态. 都可以获得一个立时回报R(sa,s)=r在这种情 定义3一个抽象迁移To的形式为B。D0 况下，回报函数R只依赖于目前的状态和活动，如 Ho,这里P(To):=p∈0,11，R(To):=r∈0,1， 果R是概率的，那么称它为非确定性的，否则称为 a是一个抽象活动，且body(To):=Bo且head 确定性的.一个策略π：S→A,它基于当前观察到的 (o:=Ho是抽象状态，这里，body/1和head/1为2 状态s选择下一步动作a,即Ⅱ(s)=a,因此A- 个一阶谓词。 ent的任务是找到一个策略π'，使得对于所有的状 假设Io的范围是受限的，即vars(Ho)vars 态s∈S,值函数(s,最大.(s主要有以下3 (Bo)且vars(a)∈vars(Bo),vars/1为一个受限一 种形式 阶谓词.则抽象转换只依赖于目前状态的信息编码 折算累积回报：V(s)=Y+, 抽象转换的主要思想是： 如果Aent处于状态Z,使得B≤Z,那么活动 有限水平回报：产(s)三) a在概率p下，将转移到状态Z':=[ZB01UH0 得到的直接回报为r 平均回报：(s)=m hh 在tableau推理中，引起状态迁移的惟一原因是 这里使用的未解释的记号和概念，请参见文献 扩展规则的使用，即α规则在抽象状态内部，使得 [7和[121 合取元素得到扩展，B规则可以使一个抽象状态分 解为多个状态，Y规则和δ规则分别引入了自变量 2逻辑强化学习 和函数符号 MDP的逻辑组成对应于一个有穷的状态机，由 为了说明问题，考虑下面的抽象迁移，上述含等 于状态和活动是非结构的，因此这个自动机必须是 词公式由一种状态迁移到另一种状态： 以命题表示.通过逻辑马尔可夫决策程序(logical {(x)((g(x)≈f(x))V门(x≈a), Markov decison process,LOMDP])可以通过逻辑符 (x)(g(fx划≈x),b≈cp(g(g(a)),b), 号来替代同类状态和活动，最大程度地减少状态和 7p(ac以}Q9:-1:la脸 f(g(x2)≈f(为)) 活动的数量 V门（≈a),gfx)≈，ecp(g（g(a) 定义1令A为逻辑，「为A中的定理，P为A 中的谓词集合，C为A中的常量集合，A为A中的特 b),7p(a,c} 定的活动谓词集合.逻辑马尔可夫决策程序(LOM- 应用到状态Ep: DP)定义为Mo=(So,Ao,Io,R),其中So= fx)(gx)≈f(x)V门（≈a),(x) fs∈HB"vC IsE『,Ao≡{a∈HBuc|a非「，To (gfx))≈x),b≈cp(g(g(a)),b),p(a S04oSo→0,11 c以 定义2抽象状态是一个逻辑原子的合取式， 当执行抽象迁移rl alfa后，后继状态为 即逻辑查询.这里空合取记为0 {(g()≈f&))V门(&≈a,gfm))≈ 抽象状态表示状态集，状态So是在∑上的一个 ,b≈cp(g(g(al),bl,门p(a.c 基例的有穷合取，即Herbrand子集上的逻辑解释. 转换概率为09，获得直接回报为·1 在一个含等词的逻辑公式{(Hx)((g(x)≈ 下面是基于逻辑强化学习的tableau算法. f(x))V门（≈a)),(x)g(f(x))≈x),≈c 算法1： P(g(g(ad),b,7P(a,c中，一个可能的抽象状 初始化Q。,对所有的(sa)赋初值0 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net的活动集 A ( s) ∈A; T为迁移 ,对于每个 s, s′∈S 和 a∈A (s) ,都存在一个迁移 T,使得状态从 s转移到 s′,即表示为 s p: r: a s′. 这里 p表示由活动 a引起的 从状态 s迁移到 s′的概率 ,且对于每个 s∈S, a∈A都 满足 (s) : ∑s′∈S p ( s, a, s′) = 1. 对于每个迁移 , Agent 都可以获得一个立时回报 R ( s, a, s′) = r. 在这种情 况下 ,回报函数 R 只依赖于目前的状态和活动 ,如 果 R是概率的 ,那么称它为非确定性的 ,否则称为 确定性的. 一个策略 π: S →A,它基于当前观察到的 状态 st 选择下一步动作 at ,即 π ( st ) = at . 因此 A2 gent的任务是找到一个策略 π3 ,使得对于所有的状 态 st ∈S,值函数 V π ( st )最大. V π ( st )主要有以下 3 种形式 : 折算累积回报 :V π (st ) ≡ ∑ ∞ i =0 γi rt+i , 有限水平回报 :V π (st ) ≡ ∑ ∞ i =0 rt+i , 平均回报 : V π (st ) ≡ limh→∞ 1 h ∑ h i =0 γt+i . 这里使用的未解释的记号和概念 ,请参见文献 [7 ]和 [ 12 ]. 2 逻辑强化学习 MDP的逻辑组成对应于一个有穷的状态机 ,由 于状态和活动是非结构的 ,因此这个自动机必须是 以命题表示. 通过逻辑马尔可夫决策程序 ( logical Markov decision p rocess, LOMDP])可以通过逻辑符 号来替代同类状态和活动 ,最大程度地减少状态和 活动的数量. 定义 1 令 Λ为逻辑 ,Γ为 Λ中的定理 , P为 Λ 中的谓词集合 , C为Λ中的常量集合 , &为Λ中的特 定的活动谓词集合. 逻辑马尔可夫决策程序 (LOM2 DP)定义为 MLO = ( SLO , ALO , TLO , R ) , 其中 SLO ≡ { s∈HB P∪C | s5 Γ}, ALO ≡{ a∈HB &∪C | a 5 Γ}, TLO : SLO ×ALO ×SLO →[0, 1 ]. 定义 2 抽象状态是一个逻辑原子的合取式 , 即逻辑查询. 这里空合取记为 ª. 抽象状态表示状态集 ,状态 SLO是在 ∑上的一个 基例的有穷合取 ,即 Herbrand子集上的逻辑解释. 在一 个 含 等 词 的 逻 辑 公 式 { ( Π x ) ( ( g ( x ) ≈ f ( x) ) ∨┐ ( x≈ a) ) , ( Π x) ( g ( f ( x) )≈ x) , b≈ c, P ( g ( g ( a) ) , b) , ┐P ( a, c) }中 ,一个可能的抽象状 态 sLO 是 { g ( f ( x1 ) ) ≈ x1 , g ( x2 ) ≈ f ( x2 ) , P ( g ( f ( a) ) , b) }. 如果一个可能状态中存在互补 对 ,那么该状态称为封闭状态. 抽象状态 { ┐P ( a, c) , g ( f ( x1 ) )≈ x1 , g ( x2 )≈ f ( x2 ) , P ( g ( f ( a) ) , b) , P ( a, b) , P ( x2 , c) }在替换 a / x2 后 ,是封闭状态. 定义 3 一个抽象迁移 TLO的形式为 BLO p∶r∶α HLO ,这里 P (TLO ) ∶ = p∈[0, 1 ], R (TLO ) ∶ = r∈[0, 1 ], a是一个抽象活动, 且 body ( TLO ) ∶ = BLO且 head (TLO ) : =HLO是抽象状态,这里, body/1和 head /1为 2 个一阶谓词. 假设 TLO的范围是受限的 ,即 vars(HLO ) Α vars (BLO )且 vars( a) Α vars(BLO ) , vars/1为一个受限一 阶谓词. 则抽象转换只依赖于目前状态的信息编码. 抽象转换的主要思想是 : 如果 Agent处于状态 Z,使得 B ≤θZ,那么活动 a在概率 p下 ,将转移到状态 Z′∶= [ Z \Bθ] ∪Hθ, 得到的直接回报为 r. 在 tableau推理中 ,引起状态迁移的惟一原因是 扩展规则的使用 ,即 α2规则在抽象状态内部 ,使得 合取元素得到扩展 ,β2规则可以使一个抽象状态分 解为多个状态 ,γ2规则和 δ2规则分别引入了自变量 和函数符号. 为了说明问题 ,考虑下面的抽象迁移 ,上述含等 词公式由一种状态迁移到另一种状态 : { ( Π x ) ( ( g ( x ) ≈ f ( x ) ) ∨┐ ( x≈ a ) ) , ( Π x) ( g ( f ( x) )≈ x ) , b≈ c, p ( g ( g ( a ) ) , b ) , ┐p ( a, c) } 0. 9∶ - 1∶rl_alfa { ( g ( x2 ) ≈ f ( x2 ) ) ∨┐( x2≈ a) , g ( f ( x1 ) )≈ x1 , b≈ c, p ( g ( g ( a ) ) , b) , ┐p ( a, c) }. 应用到状态 Exp: { ( Π x) ( ( g ( x)≈ f ( x) ) ∨┐ ( x≈ a) ) , ( Π x) ( g ( f ( x ) )≈ x ) , b≈ c, p ( g ( g ( a ) ) , b) , ┐p ( a, c) }. 当执行抽象迁移 rl_alfa后 ,后继状态为 { ( g ( x2 ) ≈ f ( x2 ) ) ∨┐ ( x2 ≈ a) , g ( f ( x1 ) ) ≈ x1 , b≈ c, p ( g ( g ( a) ) , b) , ┐p ( a, c) }. 转换概率为 0. 9,获得直接回报为 - 1. 下面是基于逻辑强化学习的 tableau算法. 算法 1: 初始化 Q0 ,对所有的 (s, a)赋初值 0 第 4期 刘 全 ,等 :一种逻辑强化学习的 tableau推理方法 ·357·