收斂性定理證明詳解

于是于是收斂的兩個(gè)條件滿足。所以有收斂性定理引理1:迭代(*)Q(x)二(1—a(x))Q(x)+a(x)[PQ](x)。假設(shè)t+1tttttTOC\o"1-5"\h\zQ(x)二(1—a(x))Q(x)+a(x)[PQ*](x)產(chǎn)生的｛Q(x)｝序列以概率1收斂到Q*。其t+1ttttt中P為映射P:QtQ。如果下面的條件滿足：o<y<i和序列｛九I九'0｝以概率1收tttt斂到0。若PPQ一PQ*巴丫PQ一Q*P+九對(duì)VQeQ成立，且a(x)滿足0<a(x)<1，ttttt藝a(x)=g，區(qū)a2(x)<g，則迭代(*)產(chǎn)生的序列｛Q(x)｝當(dāng)tTg時(shí)，以概率1收斂ttti=0i=0到Q*(x)。定理1：貝爾曼方程雖然直接，但狀態(tài)的數(shù)量通常會(huì)很巨大(隨問(wèn)題維度指數(shù)增加)，所以迭代全空間來(lái)精確求解Bellman方程是不可行的。所以一般會(huì)采用近似的方法，采用Q-Learning算法去求解。經(jīng)典的Q一Learning方程：Q(s,a)=(1—a)Q(s,a)+a[r(s,a)+YmaxQ(s',a)]t+1tttta產(chǎn)生的序列｛Q(s,a)｝收斂到Q*(s,a)對(duì)VseS，VaeA成立。其中tQ*(s,a)=r(s,a)+Y工p(s'Is,a)V(s')s'證明：定義PQt(s,a)=r(s,a)+ymaxQt(sa)]。有aPPQ一PQ*P<max|PQt(s,a)一PQ*(s,a)。其中P是空間Q到Q的映射。seS同理有PQ*(s,a)=r(s,a)+ymaxQ*(sa)。a|PQt(s,a)—PQ*(s,a)=YmaxQt(sa)—maxQ*(sa)aa<YQt(s,a)—Q*(s,a)|已經(jīng)有Q*(s,a)=r(s,a)+Y工p(s'Is,a)V(s')=r(s,a)+YE(V(s'))s'E[PQ*](s,a)=E(r(s,a)+YmaxQ*(s',a))=r(s,a)+YE(maxQ*(s',a))aa因?yàn)橛蠽(s')=maxQ*(s',a)a故Q*=E[PQ*]。引理1的兩個(gè)條件都滿足，所以說(shuō)序列｛Q(s,a)｝收斂到Q*(s,a)t對(duì)VseS，VaeA成立。定理2:很顯然，以上的QLearning方程并不適用于本文的零和馬爾可夫博弈模型,因此，結(jié)合minmax算法，將Q-.earning算法改進(jìn)為minmaxQ算法，并將單方學(xué)習(xí)擴(kuò)展至雙方學(xué)習(xí)，以如下的公式來(lái)更新Q值:Q(s,a,o)(1)Q(s,a,o)[r(s,a,o)maxminQ(s,a,o)]t1ttttPD(A)aAt產(chǎn)生的序列Qs,a,ot收斂到Q*s,a,ot對(duì)sS,aA成立。其中Q*(s,a)r(s,a)p(s'|s,a)V(s')。s'證明:定義PQt(s,a,o)r(s,a,o)maxminQt(s,a,o)其中P是空間Q到Q的ttPD(A)aA映射。有PQ*(s,a,o)r(s,a,o)maxminQ*(s,a,o)。PD(A)aAmaxminQ*(s,a,o)|PD(A)aAPD(A)aQ*(s,a,o)|PQtmaxminQ*(s,a,o)|PD(A)aAPD(A)aQ*(s,a,o)maxmin|Qt(s,a,o)PD(A)aA因?yàn)镼t(s,a,o)|Qt(s,a,o)

Qt(s,a,o)|(QQt(s,a,o)|Qt(s,a,o)

Qt(s,a,o)|(Qt(s,a,o)Q*(s,a,o)Q*(s,a,o)Q*(s,a,o)Q*(s,a,o))Q*(s,a,o)Q*(s,a,o)(Q*(s,a,o)Q*(s,a,o)Q*(s,a,o)Q*(s,a,o))于是|PQt(s,a,o)maxminPD(A)aA|Q|PQt(s,a,o)maxminPD(A)aA|Qt(s,a,o)PQ*(s,a,o)|in(Qt(s,a,o)Q*(s,a,o))Q*(s',a,o)|maxminPD(A)aA(Q*(s,a,o)Q*(s,a,o))很明顯t,0(maxmin很明顯t,0(maxmin|q*(s,a,o)PD(A)aAQ*E[PQ*]同定理1可以證明I)sS,aA,Qt(s,