收敛性定理证明详解

收敛性定理引理1:迭代(*)Q⑴=(1-^(x))Q(x)+^(x)[PQ](x)。假设t+1 t t t ttTOC\o"1-5"\h\zQ(x)=(1-a(x))Q(x)+a(x)[PQ*](x)产生的｛Q(x)｝序列以概率1收敛到Q*。其t+1 t t t t t中P为映射P:Q—Q。如果下面的条件满足：0<Y<1和序列｛人tI七>0｝以概率1收敛到0。若PPQ一PQ*P<YPQ一Q*P+人对VQeQ成立，且a(x)满足0<a(x)<1,tt t t t切a(x)=8,£a2(x)V8,则迭代(*)产生的序列｛Q(x)｝当ts时，以概率1收敛t t ti=0 i=0到Q*(x)。定理1：贝尔曼方程虽然直接，但状态的数量通常会很巨大(随问题维度指数增加)，所以迭代全空间来精确求解Bellman方程是不可行的。所以一般会采用近似的方法，采用Q-Learning算法去求解。经典的Q-Learning方程：Q(s,a)=(1-a)Q(s,a)+a[r(s,a)+ymaxQ(s',a)]'+ ' a产生的序列｛Q(s,a)｝收敛到Q*(s,a)对VseS，VaeA成立。其中tQ*(s,a)=r(s,a)+y£p(s'Is,a)V(s')s证明：定义PQt(s,a)=r(s,a)+ymaxQt(s',a)]。有aPPQ一PQ*P<max|PQt(s,a)一PQ*(s,a)。其中P是空间Q到Q的映射。seS同理有PQ*(s,a)=r(s,a)+ymaxQ*(s',a)。a|PQt(s,a)一PQ*(s,a)=ymaxQt(s',a)—maxQ*(s',a)a a<y\Qt(s,a)-Q*(s,a)|已经有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))a a因为有V(s')=maxQ*(s',a)a故Q*=E[PQ*]。引理1的两个条件都满足，所以说序列｛Q,(s,a)｝收敛到Q*(s,a)对VseS，VaeA成立。

定理2:很显然，以上的QLearning方程并不适用于本文的零和马尔可夫博弈模型，因此匕，结合minmax算法，将Qlearning算法改进为minmax Q算法，并将单方学习扩展至双方学习，以如下的公式来更新Q值：t)Qt(s,a,o) [r(s,a,o)Qt1展至双方学习，以如下的公式来更新Q值：t)Qt(s,a,o) [r(s,a,o)Qt1(s,a,o)(1maxminQ(s,a,o)]PD(A)aAt产生的序列s,a,o收敛到Q*s,a,otS,a入成立。其中Q*Q*(s,a)r(s,a)p(s'|s,a)V(s')。s证明:定义PQt(s,a,o)r(s,a,o)映射。有PQ*(s,a,o)r(s,a,o)maxPD(A)maxminQt(s,a,o)PD(A)aAminQ*(s,a,o)。aA其中s证明:定义PQt(s,a,o)r(s,a,o)映射。有PQ*(s,a,o)r(s,a,o)maxPD(A)maxminQt(s,a,o)PD(A)aAminQ*(s,a,o)。aA其中「是空间Qt到七的|PQt(s,a,o)PQ*(s,a,o)| |maxminQt(s,a,o)Amaxmin|Qt(s,a,o)PD(A)aAPD(A)aQ*(s,a,o)maxminQ*(s,a,o)|PD(A)aA因为Qt(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))很明显0(maxmin|q0(maxmin|q*(s,a,o)I)PD(A)aAQ*E[PQ*]同定理1可以证明sS,aA,Qt(s,a)于是收敛的两个条件满足。所以