马尔可夫决策过程编辑本段回目录
正文编辑本段回目录
发展概况 50年代R.贝尔曼研究动态规划时和L.S.沙普利研究随机对策时已出现马尔可夫决策过程的基本思想。R.A.霍华德(1960)和D.布莱克韦尔(1962)等人的研究工作奠定了马尔可夫决策过程的理论基础。1965年,布莱克韦尔关于一般状态空间的研究和E.B.丁金关于非时齐(非时间平稳性)的研究,推动了这一理论的发展。1960年以来,马尔可夫决策过程理论得到迅速发展,应用领域不断扩大。凡是以马尔可夫过程作为数学模型的问题,只要能引入决策和效用结构,均可应用这种理论。
数学描述 周期地进行观察的马尔可夫决策过程可用如下五元组来描述:{S,(A(i),i∈S,q,γ,V},其中S 为系统的状态空间(见状态空间法);A(i)为状态i(i∈S)的可用行动(措施,控制)集;q为时齐的马尔可夫转移律族,族的参数是可用的行动; γ是定义在Γ(Г呏{(i,ɑ):a∈A(i),i∈S}上的单值实函数;若观察到的状态为i,选用行动a,则下一步转移到状态 j的概率为q(j│i,ɑ),而且获得报酬γ(j,ɑ),它们均与系统的历史无关;V是衡量策略优劣的指标(准则)。
策略 策略是提供给决策者在各个时刻选取行动的规则,记作 π=(π0,π1,π2,…, πn,πn+1…),其中πn是时刻 n选取行动的规则。从理论上来说,为了在大范围寻求最优策略πn,最好根据时刻 n以前的历史,甚至是随机地选择最优策略。但为了便于应用,常采用既不依赖于历史、又不依赖于时间的策略,甚至可以采用确定性平稳策略。
指标 衡量策略优劣的常用指标有折扣指标和平均指标。折扣指标是指长期折扣〔把 t时刻的单位收益折合成0时刻的单位收益的βt(β<1)倍〕期望总报酬。平均指标是指单位时间的平均期望报酬。采用折扣指标的马尔可夫决策过程称为折扣模型。业已证明:若一个策略是β折扣最优的,则初始时刻的决策规则所构成的平稳策略对同一β也是折扣最优的,而且它还可以分解为若干个确定性平稳策略,它们对同一β都是最优的。现在已有计算这种策略的算法。采用平均指标的马尔可夫决策过程称为平均模型。业已证明:当状态空间S 和行动集A(i)均为有限集时,对于平均指标存在最优的确定性平稳策略;当S和(或)A(i)不是有限的情况,必须增加条件,才有最优的确定性平稳策略。计算这种策略的算法也已研制出来。
参考书目
R.A.Howard,Dynamic Programming and Markov Processes, MIT Press, Cambridge Mass., 1960.
配图编辑本段回目录