馬爾可夫決策規(guī)劃5

馬爾可夫決策規(guī)劃

第五講有限階段模型及其他有限階段模型的目標(biāo)只有有限項，即V(n)(k)=r+PPr+。2PPr+…+?！≒P…PPrpfffffffffff00101201n—1nn+11)當(dāng)n充分大時，近似令n=82)用動態(tài)規(guī)劃法求解注意：用Bellmon最優(yōu)化原理可推出平穩(wěn)策略優(yōu)勢?！?.1向后歸納法在確定性動態(tài)規(guī)劃問題求解中，向后歸納法是尋求最優(yōu)策略的一種有效解法，同樣也是求解有限階段Markov決策規(guī)劃問題中最優(yōu)策略與最優(yōu)值函數(shù)的有效解法。定理5.1在狀態(tài)集與所有行動集均為有限的有限階段模型中，定義函數(shù)匕〃(D，使其滿足如下等式:Vn(i)Vn(i)=max*a品)rG,a)+zp(ji,aVn+1(j)Ji,f*(i)Vn+1(j)=r(,f*(i))+epj蕓(igS,n=N,N—1,N—2,...,0)..(5.1)其中vn+1(j)=0。則由上述算式求出的匕0=(匕0(1),匕0(2),...,匕0(1))即為有限階段模型的最優(yōu)值函數(shù)，即對每個ieS,均有V0(i)=sup匕(兀，，?)；與此同時求得的決策序()*—\F*f*f*夕1尸-、J0，/］，???，JN7即為最優(yōu)策略，其中。一{1,2,...,1}。由于所有的(a(i),iE)及S-{1,2,...,1}均為有限集，故由(5.1)式求得的J(i)一定存在，且達到最優(yōu)的行動可能多于一個(此時可任取一個作為f*(i))。定理5.1不僅解決了有限階段模型求解最優(yōu)策略的方法問題，而且還表明對任何n,匕〃(i)表示在階段n,從狀態(tài)i出發(fā)，在余下N+1-n的階段的最優(yōu)期望總報酬，(f*，f、，…，f)也構(gòu)成從n到階段N的最優(yōu)策略，這體現(xiàn)了Bellman的最優(yōu)化原理。例5.1求解例3.1中當(dāng)N=3時的最優(yōu)策略與最優(yōu)值函數(shù)。［解］:由題意知，機器只有兩個狀態(tài)，即S={1,2},對應(yīng)的行動集分別為A(1)-hMG)-?,aj。故最優(yōu)值函數(shù)的形式為V0-(Vo(1),V0(2)),其中V。(1)與V0(2)可通過(5.1)式分別求*****解得到。注意題設(shè)N-3，因而根據(jù)向后歸納法的求解順序應(yīng)為V*4OrV*3Or匕2(i)rV*1(i)rV*00,其中ieS-{1,2}。下面分別列出n=3,2,1,0時按照(5.1)式計算的有關(guān)結(jié)果。rG,a)+￡p(j1,aV4(j)1)n=3,有：匕4G)-匕4(2)-0V3G)-max*aeA(1)vrG,a)+￡p(j1,aV4(j)JeS-m*(1,a)}-r(1,a「-10

到達V3(1)右邊最大的行動為a1，故令f3*(1)=ai；V3(2)=max**a.A(2)r(2,aV3(2)=max**a.A(2)*JjcS=max^r(2,a^r(2,%)}=maxL5頊=-2到達右端最大的行動為a3，故令f*(2)=%。2)n=2,由(5.1)式及上一步計算得到的匕3(1),V'(2)有=maxaeA(1)=rG,a)+0.7*JjcSx10+0.3xG2)=16.41V2(1)=max]r(1,a)+Sp(j1,aV3(j)>故令f*(1)=a；2=maxaeA(1)=rG,a)+0.7*JjcSx10+0.3xG2)=16.41*aeA(2)[]r(2,a)+0.6x10+0.4x(-2)]=四%(2,a2)+0.4x10+0.6x(-"=maxb.2,0.8}=0.8達到匕2(2)右端最大的行動為a3，故令f*(2)=a3。3)n=1，由(5.1)式及上一步計算得到的V2(1),V2(2)有V1V1G)=max*aeA(1)r(1,a)+￡p(j1,aV2(j)=10+0.7x16.4+0.3x0.8=21.72故令f「(1)=a1；V1(2)=max**aeA(2)r(2,a)+￡p(j2,V1(2)=max**aeA(2)r(2,a)+0.6x16.4+0.4x0.8,=max<2、Ir\2,a)+0.4x16.4+0.6x0.8i3

=maxk16,5.04}=5.16達到匕1(2)右端最大的行動為a2，故令匕*(2)=%。4)n=0,由(5.1)式及上一步計算得到的匕1(1),匕1(2)有匕0G)=maxjrG,a)+￡pj1,a^(j)>a^A(1)iJwS=10+0.7x21.72+0.3x=maxk16,5.04}=5.16達到匕1(2)右端最大的行動為a2，故令匕*(2)=%。4)n=0,由(5.1)式及上一步計算得到的匕1(1),匕1(2)有匕0G)=maxjrG,a)+￡pj1,a^(j)>a^A(1)iJwS=10+0.7x21.72+0.3x5.16=26.752故令f*(1)=a];V0(2)=max**aeA(2)由定理5.1可知最優(yōu)函數(shù)為V*。=V*0G）V*0（2））=（26.752,10.096）=V3Q,1）V3Q,2?，相應(yīng)的最優(yōu)策略為兀*=（f*，/*，/*，/*）=（/，/，g，g），其中fG）=gG）=a，f（2）=a，012312g（2）=a3o注：本例中的最優(yōu)策略不是平穩(wěn)的，決策函數(shù)f,f,f不同。乙JL\j由此可見，有限階段問題的最優(yōu)策略一般不是平穩(wěn)策略。例5.2假設(shè)一設(shè)備制造廠承接了某工程中一臺關(guān)鍵設(shè)備的制造任務(wù)，工程對此設(shè)備的質(zhì)量標(biāo)準(zhǔn)有非常嚴(yán)格的要求。以該廠現(xiàn)有的技術(shù)水準(zhǔn)而言，每臺制成的設(shè)備能通過質(zhì)量檢驗而被接受的概率僅為0.25。再因該工程對此設(shè)備又有一定的時限要求，所以廠

方?jīng)Q定，至多安排三個生產(chǎn)周期完成此項任務(wù)，每一生產(chǎn)周期可制造j(0<j<3)臺設(shè)備。在每一生產(chǎn)周期結(jié)束時，均對已制成的設(shè)備進行檢驗，只要其中有一臺是合格的，便不再安排新的生產(chǎn)周期。在每一生產(chǎn)周期，只要開工制造這種設(shè)備便須一固定的開工費用c1。此外，生產(chǎn)每臺設(shè)備的費用為C2。若在第三個生產(chǎn)周期結(jié)束時，廠方仍未能生產(chǎn)出一臺合格的設(shè)備，從而無法向工程供貨，則需履行事先簽訂的合同，向工程方面支付一筆違約費用C3。試問廠方應(yīng)制訂怎樣的生產(chǎn)策略，以使期望總費用最小？［解］:此例中生產(chǎn)周期至多為3，故取N+1=3，即N=2。在每一生產(chǎn)周期結(jié)束時廠方只關(guān)心是否制造出合格設(shè)備，取狀態(tài)空間S={。，1}0表示廠方已制造出合格設(shè)備，1則表示還未制造出合格設(shè)備。以j(0<j<3)行動表示在一生產(chǎn)周期內(nèi)生產(chǎn)j臺設(shè)備，則有如下行動集為A(0)={0},A(1)={0,1,2,3}。再以r(i,j)表示狀態(tài)為i時采取行動j所導(dǎo)致的費用，則有「(如)="j，i=1,j>0其他最終費用函數(shù)用R(i)表示，有R(i)=最后根據(jù)題意，若在一生產(chǎn)周期內(nèi)制造了j臺設(shè)備，則此j臺設(shè)備均被拒收的概率為f3J?！?如)="j，i=1,j>0其他pG)=11/4P(2)=107/169/16P(3)=1037/6427/64假定C=10,C=5,C=64,于是有1rG,j)=<210+5j,0,R(i)=?,I64,3i=1,j〉0其他下面將遞推地計算最優(yōu)值函數(shù)并確定相應(yīng)的最優(yōu)策略。首先，考慮狀態(tài)0。由于A(0)={0},且匕3(0)=R(0)=0，故*(0)=r(0,0)+zp(j0,0>3(j)=r(0,0)+p(00,0>3(0)=>3(0)類似可求得>1(0)=>0(0)，**f;(0)=0。其次，考慮狀態(tài)1。作為初始值有>3(0)=0>3(1)=64。下**而依次遞推以求出>2(1),>1(1),匕。(1)。由于A(1)={0,1,2,3}，有>2G)=mix^G,a)+pGp,a>3G)}aeA(1)**于是顯然有f°*(0)=f；(0)==mix*3、r(1,0)+1x64,rG,1)+64x_,r(1,2)+64xg,rG,3)+64x271664J=mixi)+64,15+48,20+36,25+27}=52可得故令f*G)=3。再由匕2(0)=0,匕2(1)=52可得ViG)=mix^G,a)+pC|1,aV2G)}aeAG)「一一一3一9一一27〕=mix^0+52x1,15+52x_,20+52x二,25+52x_]〔41664J=46.9375故可令彳(1)=3。最后，類似可求得匕0G)=44.801758,fG)=3。于是，本題中三階段模型的最優(yōu)值函數(shù)為匕0=(V(0),6=(0,44，.最優(yōu)策略7為兀8=(f0,f,f2)，其中f(0)=0,f(1)=3(V0<i<2)。這表明廠方采取這樣的策略：在每一生產(chǎn)周期結(jié)束時，只要還未制造出合格的設(shè)備，便在下一周期生產(chǎn)三臺設(shè)備：若至少已制造出一臺合格設(shè)備，便終止生產(chǎn)。此外，在第三個生產(chǎn)周期結(jié)束時，生產(chǎn)也自動停止。顯然，如廠方最初有合格設(shè)備的庫存，則立即交貨，從而費用為0;否則，在采取上述生產(chǎn)策略后，可使期望總費用達最小，即44.801758o直觀上不難看出，因最終懲罰費用相對地要比固定的與可變的生產(chǎn)費用水平大很多，廠方采取上述策略是很自然的，此處可以想象，一旦費用結(jié)構(gòu)改變，最優(yōu)策略也相應(yīng)地有所改變。用有限階段模型的向后歸納法來求解Markov決策規(guī)劃問題雖然方法較簡單，但前提是要確定該序貫決策問題將在某有限時段內(nèi)結(jié)束。然而，很多實際情況是人們往往無法確定該系統(tǒng)什么時候結(jié)束，即使知道它在有限時間結(jié)束，但階段數(shù)N+1很大，導(dǎo)致了較大的計算量，因而還需要考慮其他算法?！?.2其他模型簡介1、S有限和A無限此時F是無限集（與F有限折扣模型相同）。對max（r（，,k）+房p（k）y），能否找到keA、即可否找到keA.lJJJ最優(yōu)/*是上述算法的關(guān)鍵，而與A的有限或無限無關(guān)。1）在上式中如能找到最優(yōu)k*，則可找到最優(yōu)f*;2）在上式中如能找到8最優(yōu)k*，則可找到8最優(yōu)f*。2、S和A都是無限集方法：用有限集s’近似表示s，即pheS}=1，而pgeS，uSL0.95，從而轉(zhuǎn)化為S有限折扣模型。3、連續(xù)時間馬爾科夫決策規(guī)劃定義5.1：一個連續(xù)時間的MDP可表為由如下六個元素組成的系統(tǒng)：（S,A,{q（a）,aeA},r（l,a）,V,T}ifiii其中：S——狀態(tài)空間，這里仍假定S有限，即S={0,1,2,,1}；A——所有行動方案的集合；q.f(。)表示瞬時轉(zhuǎn)移率，{q(。),aeA}——所有轉(zhuǎn)移率ifiifii的集合；p{X=jIX=i,a}=qf(a)-At+o(At),i豐jr(i,a)(ieS)為系統(tǒng)于時刻t處于狀態(tài)i、而選用行動方案aj時的瞬時收益率，即系統(tǒng)在時段[t/+△t]內(nèi)的收益為r(i,a)?At+o(At)V一目標(biāo)函數(shù)T——時間集，T=[0,8]決策函數(shù)：f:S-A(同前)記Q=(q(f(i))，由馬氏鏈的構(gòu)造性質(zhì)，如果fifQf是一保守的Q