马尔可夫决策规划

《马尔可夫决策规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、定理4・7£—最优马氏策略总是存在的。（报酬函数厂有界）［证明］记使得宀％%）},则当厂有界时，v为有界数集。恥）

2、屯0谄匕必=0i=0（01...1、00<工0"••••••••••••M—工0"•••/?=0<11•…1;n=0©+1W丿（厶+1）M1-0于是v为有界数集，所以v必有上确界（最小的上界）。设上确界为V*,则对于任意的F〉0存在Vev,使得V＞V-£・•・存在托*己兀带使得V^（Z）=V。显然匕9（兀）是£—最优的。［证毕］注：这个定理实际上是在r-有界折扣模型上成立的，扩大了F有限折扣模型。定理4.8在厂冇

3、界的范围内，£一最优平稳策略总是存在的。［证明］由定理4.7,存在£一最优马氏策略;f,设/={心/1，心…人…},记兀={/1，心…，九，…}，则有匕，兀）＜耳3*）+FTfy^'）＜Tfoiv^）+£］即vp（龙*）＜Thvp（X）］+j3Pf{•sTfWV“）_£・•・是£+£最优策略。［证毕］作业题：对于F有限折扣模型，总存在最优平稳策略。注意：在上述证明中均没有提到初始状态，这意味着我们得到的决策是相对于所有初始状态而言的一致最优策略。综合结论可得出如下事实：在全体策略类n上寻求最优策略，等价于在平稳策略类上寻求最优策略。

4、因为在平稳策略类上所获得的0■最优策略，在全体策略类口上对同一0來说，它同样是最优的。考虑到在状态集s为冇限以及所冇a®(iuS)均为有限的假设下，平稳策略类仅包含有限个不同的元素、或仅有有限个平稳策略，这就使得寻求最优策略的问题大为简化。§4.3策略迭代法利用定理4.1(2)及定理4.5的结论可得如下策略迭代法的算法步骤：第一•步，策略求值运算任取一个决策规则/eF,i&S={1,2,3....J},求解如下/个线性方程组:/(/))+0工p(j=V(/)或V=r(/)+/?P(/)V其解WrSCTJ)。第二步，策略改进运算将第一

5、步求得的V(z)(/e5)代入(4.2)式，以求得一个新的决策函数g=(g(l),g(2)，……,g(/)),使其各分量分别满足下述关系:飜{畑)+0屮(川,叽)}=r(i,g(i))+0工卩(丿IjwS(4.2)、+lf,/(O)V(j)(ieS)jwS注意：若同时有几个a使(4.2)式左端达最大，则可任取其一作为g(D(/eS)。第三步，终止规则若对所有的IeS,(4.2)式均成立等式，则终止计算，并有结论：为最优策略；若至少存在一个iwS,使(4.2)式成立严格不等式，则以g代替/，并转入第1步，此时冇结论^(g00)>V/y(

6、/x，)o下而来说明上述算法步骤的原理。对于任一个决策规则feF,由算法第二步所定出的g,按矩阵、向量符号书写为：r(g)+/^(g)Vfi(D>r(/)+W)V//w)设计：v/r)=r(n+/?p(/)v/r)珂％厂)=心)+丹(g)%r°)于是可得到：Tsvfi(r)>v^r)(4.3)由定理4.4有：叫(g°°)n吩CT)ooroo即经第二步所得的g至少是与/一样好的策略。现分两种情况讨论：1)若式(4.3)等号成立，则由(4.2)式对任给的heF必有r(/i)+^P(/i)V/r)

7、/D%(n则由定理4.1(2)知有卩0仗")>吩(/"),即是比更好的策略，这种策略得到改进。根据算法步骤，将转入第一步，并重复上述计算，直到程序终止。其小需说明的是，由于F为有限集，而每次迭代都实现严格改进，因此不会岀现循环现£G0彖，即经过冇限次迭代后，将无法再做改进。于是根据前述论证，此时的/必定在全体策略n上是0■折扣最优的。例4.1设冇一工厂为市场生产某种产品。每年年初对产品的销售情况进行一次检查，其可能结果有两种：销路好(记为状态1)

8、和销路丼(记为状态2)。若销路好，一年可获利6千元；若销路差，一年要亏本3T元。在每个状态，工厂管理人员采用的行动有两个：不登记广告(记做b)或登记广告(记做c)。若不登广告，自然无广告费;若登广告，一年要花2千元广告费。对于今年的各种状态所采取的行动，由于随机因索的干扰，转为下年初的状态概率及相应的状态花费的费用见表4.1。工厂希累考虑长期折扣期望收益，取折扣因子〃二().9。用策略迭代法求此MDP的最优决策及其最优值函数(计算取两位小数)。状态i行动转移概率报酬(千元)Q=/⑴p(llW))P(2!/,/(/))厂(d,i)1b0

9、.50.56c0.80.242b0.40.6■3c0.70.3■5表4・1状态转移概率及费用表[解]:由题设知，状态集5={1,2}衍动集A⑴=A(2)={0c}。该Markov决策过程的决策准则共有4个，它们分别是f=