逻辑马尔可夫决策过程的正则条件概率理论

南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (4): 440–448.

逻辑马尔可夫决策过程的正则条件概率理论

王蓁蓁;邢汉承;

出版日期:2013-08-30 发布日期:2013-08-30
作者简介:金陵科技学院信息技术学院;江苏省信息分析工程实验室;东南大学计算机科学与工程学院;
基金资助:
基金:金陵科技学院科研基金(jit-b-201207)

T h e o r yf o r r e g u l a r l yc o n d i t i o n a lp r o b a b i l i t yo f l o g i c a lM a r k o v d e c i s i o np r o c e s s

W a n gZ h e n - Z h e n 1 , 2 , X i n gH a n - C h e n g 3

Online:2013-08-30 Published:2013-08-30
About author:( 1. S c h o o l o f I n f o r m a t i o nT e c h n o l o g y , J i n l i n gI n s t i t u t eo fT e c h n o l o g y , N a n j i n g , 2 1 1 1 6 9 , C h i n a ;
2. I n f o r m a t i o nA n a l y s i sE n g i n e e r i n gL a b o r a t o r yo f J i a n g s uP r o v i n c e , N a n j i n g , 2 1 1 1 6 9 , C h i n a ;
3. S c h o o l o fC o m p u t e rS c i e n c ea n dE n g i n e e r i n g , S o u t h e a s tU n i v e r s i t y , N a n j i n g , 2 1 0 0 9 6

摘要/Abstract

摘要： 增强学习已经开始向关系增强学习发展,并且产生了许多新的算法.大部分方法将命题表达提升为关系或计算逻辑的表达.这些方法已经表现出许多好的性质,但是相关的理论分析目前还缺乏,即为什么这些关系的增强学习具有良好的性质,因此提出基础马尔可夫决策过程和逻辑马尔可夫决策过程的测度空间结构,利用现代概率论中条件数学期望和正则条件概率理论建立基础和逻辑两种马尔可夫决策过程之间的深刻联系,从而证实了逻辑马尔可夫决策过程中的最优策略在某种平均意义上是相应的基础马尔可夫决策过程的最优策略.最后由实例分析得出逻辑马尔可夫决策编程方法.建立逻辑马尔可夫决策过程的测度空间结构可以为关系增强学习提供数学理论框架.

Abstract: B e c a u s eo fv e r yl a r g es t a t e si nt h er e a lw o r l d , r e i n f o r c e m e n tl e a r n i n gd e v e l o p st o w a r d sr e l a t i o n a l
r e i n f o r c e m e n t l e a r n i n ga n dm a n ya p p r o a c h e sa r ep r e s e n t e ds u c ha s l o g i c a lM a r k o vd e c i s i o np r o c e s s e s . M a n yo f t h e s e
a p p r o a c h e sa r e t ou p g r a d ep r o p o s i t i o n a l r e p r e s e n t a t i o n st o w a r d st h eu s eo fr e l a t i o n a lo rc o m p u t a t i o n a l l o g i cr e p r e -
s e n t a t i o n s . T h e s ea p p r o a c h e sh a v e a l r e a d ys h o w nm a n yg o o dq u a l i t i e s . H o w e v e r , a r e l a t i v e t h e o r y i sm i s s i n g , t h a t i s ,
w h yd ot h e s er e l a t i o n a lr e i n f o r c e m e n tl e a r n i n ga p p r o a c h e sh a v eg o o dq u a l i t y ? S ow ec o n s t r u c tag r o u n d m e a s u r e
s p a c e f o ru n d e r l y i n gM a r k o vd e c i s i o np r o c e s s e sa n dal o g i c a lm e a s u r es p a c ef o r l o g i c a lM a r k o vd e c i s i o np r o c e s s e s ,
a n dt h e nu s et w op r o f o u n dc o n c e p t so fc o n d i t i o n a le x p e c t a t i o na n dr e g u l a rc o n d i t i o n a lp r o b a b i l i t yi n m o d e r n
p r o b a b i l i t yt h e o r yt oc o m b i n e t h e t w os p a c e s . I nt h i sw a y , w ee s t a b l i s hap r o f o u n dr e l a t i o n s h i pb e t w e e nu n d e r l y i n g
M a r k o vd e c i s i o np r o c e s s ( MD P ) a n dl o g i c a lM a r k o vd e c i s i o np r o c e s s . W i t h i nt h i sk i n do fm a t h e m a t i cf r a m e w o r kw e
p r o v et h a t a no p t i m a l p o l i c y f o u n da t a b s t r a c t i o n l e v e l a l w a y s i so p t i m a l a t t h eg r o u n d l e v e l o f t h eu n d e r l y i n gM a r k o v
d e c i s i o np r o c e s s i ns o m ea v e r a g es e n s e . M a n yr e l a t i o n a l r e i n f o r c e m e n t l e a r n i n gt e c h n i q u e sh a v e t h i sp r o p e r t y , b u t d o
n o t g i v e s u c hap r o o f . M o r e o v e r , w ep u t f o r w a r dd e f i n i t e l y t h e s e m a n t i c s o f t h ep r o b a b i l i t ya n do f t h e r e w a r d f u n c t i o n
i na na b s t r a c t t r a n s i t i o no f l o g i c a lM a r k o vd e c i s i o np r o c e s s e s .
T h eM a r k o vd e c i s i o np r o g r e s sb u i l t o nb o t h t h eh o u n dm e a s u r e s p a c e a n d t h e l o g i c a lm e a s u r e s p a c e a l s o r e f l e c t s
a ni m p o r t a n tc h a r a c t e r i s t i co fh u m a n m i n d , t h a ti s , p e o p l e w h e nf a c i n g v a r i o u sp r o b l e m se s p e c i a l l yc o m p l e x
p r o b l e m s , a l w a y s t a c k l e t h e mf r o ma na b s t r a c to rp r i n c i p l ep e r s p e c t i v e . H a v i n gg o t t e naw h o l ep l a n ,
d e t a i l sa r e t h e n.........

王蓁蓁;邢汉承;. 逻辑马尔可夫决策过程的正则条件概率理论[J]. 南京大学学报(自然科学版), 2013, 49(4): 440–448.

W a n gZ h e n - Z h e n 1 , 2 , X i n gH a n - C h e n g 3. T h e o r yf o r r e g u l a r l yc o n d i t i o n a lp r o b a b i l i t yo f l o g i c a lM a r k o v d e c i s i o np r o c e s s[J]. Journal of Nanjing University(Natural Sciences), 2013, 49(4): 440–448.

参考文献

[ 1 ] B o u t i l i e rC , R e i t e r R , P r i c eB. S y m b o l i cd y n a m i c p r o g r a mm i n g f o rF i r s t - o r d e rMD P s . S e v e n t e e n t h I n -
t e r n a t i o n a l J o i n tC o n f e r e n c eo nA r t i f i c i a l I n t e l l i g e n c e ( I J C A I - 0 1 ) , S e a t t l e , U S A , 6 9 0 ~ 7 0 0 .
[ 2 ] V a n M O. R e i n f o r c e m e n tl e a r n i n gf o rr e l a t i o n a l MD P s .P r o c e e d i n g s o f t h e A n n u a l M a c h i n e L e a r n i n g C o n f e r e n c e o f B e l g i u m n d t h e
N e t h e r l a n d s , B r u s s e l s , B e l g i u m , 2 0 0 4 : 1 3 8~1 4 5.
[3 ] K e r s t i n gK , D eR a e d tL. L o g i c a lM a r k o vd e c i s i o n p r o g r a m s . I nW o r k i n gN o t e so f t h eI J C A I — 2 0 0 3 W o r k s h o po n L e a r n i n gS t a t i s t i c a l M o d e l sf r o m
R e l a t i o n a lD a t a ( S R L — 0 3 ) , A c a p u l c o , M e x i c o . 2 0 0 3 : 6 3~7 0.
[ 4 ] K e r s t i n gK , D eR a e d tL. L o g i c a lM a r k o vd e c i s i o n p r o g r a m sa n dt h ec o n v e r g e n c eo fl o g i cT D ( ) . P r o c e e d i n g so fT h e1 4 t h I n t e r n a t i o n a lC o n f e r e n c e o f I n d u c t i v e L o g i c P r o g r a mm i n g , P o r t o ,
P o r t u g a l , 2 0 0 4 : 1 8 0~1 9 7.
[ 5 ] R a v i n d r a nBG , B a r t oA. S y mm e t r i e sa n d m o d e l m i n i m i z a t i o n i n M a r k o v d e c i s i o n p r o c e s s e s . T e c h n i c a lR e p o r t : UM-C S -2 0 0 1-0 4 3.
[ 6 ] R a v i n d r a nBG , B a r t oA. S M D PH o m o m o r p h i s m s : A n a l g e b r a i ca p p r o a c h t o a b s t r a c t i o ni n s e m i - M a r k o v d e c i s i o np r o c e s s e s . P r o c e e d i n go f t h e 1 8
t h I n t e r n a t i o n a l J o i n tC o n f e r e n c eo nA r t i f i c i a l I n t e l l i g e n c e , 2 0 0 3 : 1 0 1 1 ~ 1 0 1 6 .
[ 7 ] S u t t o nR S , P r e c u pD , S i n g hS. B e t w e e n MD P s a n d s e m i - MD P s : A f r a m e w o r k f o r t e m p o r a l · 6 4 4 · a b s t r a c t i o ni nr e i n f o r c e m e n tl e a r n i n g . A r t i f i c i a l
I n t e l l i g e n c e , 1 9 9 9 , 1 1 2 : 1 8 1~2 1 1.
[ 8 ] Wh i t e h e a dSD , L i nLJ . R e i n f o r c e m e n tl e a r n i n g o fn o n - M a r k o vd e c i s i o np r o c e s s e s . A r t i f i c i a lI n - t e l l i g e n c e , 1 9 9 5 , 7 3 : 2 7 1~3 0 6
[ 9 ] D a sT K , G o s a v iA , M a h a d e v a nS . e ta l . S o l v i n g s e m i - M a r k o v d e c i s i o n p r o b l e m s u s i n g a v e r a g e r e w a r d r e i n f o r c e m e n t l e a r n i n g . M a n a g e m e n t S c i e n c e , 1 9 9 9 , 4 5 ( 4 ) : 5 6 0~5 7 4.
[ 1 0 ] K e r s t i n gK , V a nO t t e r l o M , D eR a e d tL. B e l l m a n g o e s r e l a t i o n a l . P r o c e e d i n g so ft h e2 1 s t I n t e r n a t i o n a l C o n f e r e n c eo n M a c h i n e L e a r n i n g , B a n f f , C a n a d a , 2 0 0 4 : 4 6 5 ~ 4 7 2 .
[1 1 ] T a d e p a l l i P , G i v a n R , D r i e s s e n s K.R e l a t i o n a l r e i n f o r c e m e n t l e a r n i n g : A no v e r v i e w. P r o c e e d i n g so f t h e W o r k s h o p o n R e l a t i o n a l R e i n f o r c e m e n t L e a r n i n g , B a n f f , C a n a d a , 2 0 0 4 : 1 ~1 0 .
[ 1 2 ] S u t t o nR S , P r e c u pD , S i n g hS . B e t w e e n MD P s a n d s e m i - MD P s : A f r a m e w o r k f o r t e m p o r a l a b s t r a c t i o ni nr e i n f o r c e m e n tl e a r n i n g . A r t i f i c i a l n t e l l i g e n c e , 1 9 9 9 , 1 1 2 : 1 8 1~2 1 1.
[ 1 3 ] J o s h iS , K e r s t i n g K , K h a r d o n R. G e n e r a l i z e df i r s t o r d e rd e c i s i o n d i a g r a m sf o rf i r s t o r d e r M a r k o v d e c i s i o n . P r o c e e d i n g so ft h e2 1 s t I n t e r n a t i o n a lJ o i n t
C o n f e r e n c eo nA r t i f i c i a l I n t e l l i g e n c e ( I J C A I ’ 0 9 ) , S a n F r a n c i s c o , C A , U S A , 2 0 0 9 : 1 9 1 6 ~ 1 9 2 1 .
[ 1 4 ] H u a n g Z h Y. E l e m e n t a r y s t o c h a s t i c a n a l y s i s . Wu h a n : W u h a nU n i v e r s i t yP r e s s , 1 9 8 8 , 3 9 1. ( 黄志远 . 随机分析学基础 . 武汉: 武汉大学出版社, 1 9 8 8 , 3 9 1 ) .
[1 5 ] W a n gZ Z , X i n g H C , Z h a n g Z Z , e ta l . A t h e o r e t i c a l m o d e l o f m e a s u r e - v a l u e d M a r k o v p r o c e s s e ss i m u l a t i n gt h ed i v e r g e n tt h i n k i n g o f
m a n . J o u r n a l o f N a n i n g U n i v e r s i t y ( N a t u r a l S c i e n c e s ) , 2 0 0 8 , 2 ( 4 4 ) : 1 4 8~1 5 6. ( 王蓁蓁, 邢汉承, 张志政等 . 一种模拟人类发散思维的测度值马尔可夫理论模型 . 南京大学学报( 自然科学) , 2 0 0 8 , 2 ( 4 4 ) : 1 4 8~1 5 6.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed