资源描述：
《第16章-markov决策》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、龚光鲁,钱敏平著应用随机过程教程–与在算法和智能计算中的应用清华大学出版社,2004第16章离散状态的Markov控制与决策过程简介(ControlledMarkovProcess,MarkovDecisionProcess,MDP)1例1.1随机决策模型的简单例子定义１６.１随机决策模型的对象是可以控制的随机系统,人们可以选取控制决策,以改变发展过程的路径.在任意固定时刻,系统随机地处在S={1,2,L,N}中的某个状态,而在策略取定为a的情况下系统的发展是按照一个随机矩阵P(a)作为转移概率阵而变化.这就称为一个M
2、arkov决策过程．从下面的简单例子，可以得到一些直观的认识。例１６．２设某个经营系统总处在"1","2","3"三种状态之一．假定在每个整值时刻可选择两种不同的动作之一：a或a，而在采取动作a或a时，状态间的转移矩阵（1）（2）（1）（2）分别为æ11öæ11öç0÷ç0÷ç22÷ç22÷ç11÷ç11÷P(a)=0,P(a)=0.(1)(2)ç22÷ç22÷ç11÷ç11÷ç0÷ç0÷è22øè22ø假定开始时（即时间n=0时）该系统以相等的可能性处在这三个状态之一,即初始分布为æ111öç,,÷.又设处在状态i时
3、,采取动作a(1)能得到报酬为g(i,a(1))=2i,而处在状态i时,è333ø21采取动作a能得到报酬为g(i,a)=i+.我们要在各个时刻,根据历史状况,有目的(2)(2)2地选取动作a或a,使在时间区段0£n£m内得到的平均累积报酬最大．这里，动作是(1)(2)历史状况的函数．从时刻n的历史状况到采取的动作的对应（即函数），称为时刻n采取的策略．各个时刻采取的策略合起来，称为一个策略．我们要选取一个策略，使在时间区段0£n£m内得到的平均累积报酬最大．将在时刻n采取的动作记为a,那么它只能a或a之一.于是转移矩
4、阵n(1)(2)111P(a)=(p(a))有确切的含义.这样,由初始分布m=(m,m,m)=(,,)nijni,j£N0123333及转移矩阵列{P(a)}决定了一个3个状态的非时齐的Markov链{x:n³0}．x代表系nnn439统在时刻n所处的(随机的)状态．于是系统在时刻m前所得的平均累积报酬为mE(åg(xn,an)).它就是需要优化的目标函数．n=0动作a的选取，直接影响了在时刻n以后此Markov链的样本的走向{x,L,x).nn+1m一般地,动作a依赖于系统的发展历史,即依赖于{x,a,x,a,L,x
5、,a,x}.这里n0011n-1n-1n我们简单地限制在时刻n所采取的动作只依赖于当时所处的状态，也就是假定a只是x的nn函数,即a=f(x)(其中f:{1,2,3}®{a,a}，是根据所处的状态选取的动作，即nnnn(1)(2)在时刻n所采取的策略)．我们先以m=1为例，看如何求得最高的平均累积报酬．也就是让a=f(x),a=f(x),要选取函数(映射)f,f,使00011101DV(f,f)=Eg(x,f(x))+Eg(x,f(x))01000111取到最大值.注意3Eg(x0,f0(x0))=åg(i,f0(i)
6、)mi.i=1而采取了动作a(=f(x))后，非时齐的Markov链x从时刻0到时刻1的转移矩阵应该是000nP(f(x))，于是003P(x1=j)=åmipij(f0(i)).i=1从而3Eg(x1,f1(x1))=åg(j,f1(j))P(x1=j)j=133=mg(j,f(j))p(f(i)).ååi1ij0j=1i=1也就是333V(f0,f1)=åg(i,f0(i))mi+ååmig(j,f1(j))pij(f0(i)).i=1j=1i=1由此式看出，若要选取策略（f,f）使V(f,f)的值为最大，需先选取
7、f，使对于任意j，01011g(j,f(j))最大.对此我们观察到14403(j=1)g(1,a)=2>=g(1,a),(1)(2)29(j=2)g(2,a)=4<=g(2,a),(1)(2)219(j=3)g(3,a)=6<=g(3,a).(1)(2)2*可见,要使g(j,f(j))最大,f应取如下定义的f：111*f:(1,2,3)®(a,a,a).1(1)(2)(2)**将在确定了f=f后的最大报酬记为g,那么11ìï2(j=1)**ïï9g(j)=g(j,f1(j))=í(j=2)2ï19ï(j=3)ïî2于是
8、33**V(f,f)=m[g(i,f(i))+g(j)p(f(i))].01åi0åij0i=1j=1*剩下的就是选取f，使V(f,f))最大．为此只需使方括号中的各个量都取到最大．与前001面不同之处，只是用方括号中量代替了前面的g(j,f(j))而已.下面我们列出它的值，由1p(a)与p(a)的定义得ij(1)ij(2)33*
