马尔可夫决策过程引论

所需积分/C币:46 2019-01-29 17:12:36 2.02MB PDF
42
收藏 收藏
举报

马尔可夫决策过程引论是学习马尔可夫过程的绝佳参考书目,下载必有收获哦
参考文献……………… 第8章一般化马尔可夫决策过程……………………………(160) 81状态部分可观察的马尔可夫决策过程 ………(160) 8.1.1模型………, …………………………(160) 8.1.2折扣准则………………………………………………………………(161) 8.1.3有限阶段 ………………(166) 8.2约束马尔可夫决策过程… ……(169) 8.2.1单约東 非·和和·,和。中···非和 ………(169) 8.2.2多约束…………………………………………………………………………(173) 8.2.3哈密尔顿圈……………………………………………………………………………(177) 8.3多目标马尔可夫决策过程…………………………………………………………………(180) 831折扣准则………18) 8.3.2折扣与平均的加权准则 186) 8.4摄动马尔可夫决策过程… 8.4.1摄动的非平稳平均准则马尔可夫决策过程………………………………………………(191) 8,4.2摄动的连续时间折扣准则马尔可大决策过程…………………………………………(197) 文献注释 …199 参考文款…200 第9章随机环境马尔可夫决策过程……………………………………………………(206) 9.1半马氏环境连续时间马尔可夫决策过程…………………………………………………………(206) 9.1.1模型………………………………………………………………………………(206) 9.1.2最优方程………4210) 9.1.3弱收敛逼近…………………………………………………………………………………(216) 9.1,1马尔可夫环境和位相型环境……………… 218) 9.2半马尔可夫环境半马尔可夫决策过程 9.2.1模型 9.2.2最优方程……1(22 9.2.3马尔可大坏境………………………………………………………………………………(229) 9,3半马尔可夫环境混合马尔可夫决策过程……·…,……**……"…*“………(230) 9.3.1模型…… ……………………………(230) 9.3.2最优方程……… …………………………………………………………………(232) 933马尔可夫环境…………(37) 文献注释……(238) 参考文献 曾普量看坐量音,量量量非量1量坐重世重香世 (239) 第10章在推队/通信系统中的应用 ,着着着B非福福日着着着着喝 …………………………………(240) 10.1排队系统的到达控制………………"…………,…,…*………(240) 10.1.1静态到达控制 …(241) 10.1.2M/M/c系统的动态到达控制……042) 10.1.3一般动态到达控制………6243) 10.2排队系统服务控制 +(246) 10.3排队网络控制………………………………1(250) 10.3.1到达控制… ……(250) 10.3.2服务控制……250) 10.3.3路径控制……………………………………………………………………………(252) 10.4通信网络控制 文献注释…14255 参考文献 曾·平,·普量鲁,,··t …(255 第11章在其他方面的应用 (257) 11.1生产/存贮系统最优控制……………………………………………1257) 11.2系统最优更换/维修…………………………259) 11.2.1模型……………………………………………………………………(259) 11.2.2折扣准则…262) 1.2.3平均目标 (264) 11.2,4无冲击 …………………………………………………(265) 11.3质量控制……………… 自t自t 11.4日标的最优搜素… …………………………………………………………(268) 11.4.1固定目标的最优搜索……………………11268 11.4.2活动目标的最优拽索……………………………………………………………(269) 11.5柔性制遺系统最优路径控制…… …………………………(270) 11.5.1一类流水线的最优动态负荷分配…………………………… …………(270) 11.5,2动态路径调度………… 昨·目由非,B着看看 …………………………………………(271) 文献注释 272) 参考文献………………………………………………………………………………(272) 第1章 引论 1.1离散时间马尔可夫决策过程模型 本节介绍最为基本的离散时间马尔可夫决策过程( Discrete Time markov decision process- es,简记为υTMDP)的模型。为方便起见,我们假定在时刻点n=0,1,2,…处观察系统,这 里n可取有限多个值,如n=0,1,2,…,N,也可取所有的非负整数。一个 DTMDP模型由 如下的五重组组成: {S,A(i),p(a),r(i,a),V,,j∈S,a∈A(1)} (1.1.1) 其中各元的含义如下: (1)S是系统所有可能的状态所组成的非空的状态集,有时也称之为系统的状态空间, 它可以是有限的、可列的集或任意非空集。本书中假定S是可数集(即有限或可列)。我们用 小写的字母t,j,k等(或加上上、下标)来表示状态。 (2)对状态i∈S,A(t)是在状态i处可用的决策集,它是非空的;当不特别指出时,本书 中亦假定它是可数集。实际上,当A()为非空集并赋以一定的拓扑结构后,本书中的绝大部 分结论仍成立。书中常用a来表示决策。 (3)当系统在决策时刻点n处于状态i,采取决策a∈A(i)时,则系统在下一决策时刻点 n+1时处于状态j的概率为力(a),它与决策时刻n无关。称p={p,(a),t,j∈S,a∈A(i)} 为系统的状态转移概率族,于是,对i∈S,a∈A(),有∑,(a)=1,即{(a),j∈S}为 随机向量。范围稍广一点的是{pa),j∈S为次随机向量的情形,即∑p(a)≤1,在大多 数情形下,这两种情形可统一考虑。 4)当系统在决策时刻点n处于状态讠,采取决策a∈A()时,系统于本阶段获得的报酬 为r(i,a)。如果记r={(,a)i∈S,a∈A(i)},则r是定义在P上的一个广义函数r:r -∞,十∞],于是我们常称r为报酬函数。r可以只取有限实值,也可取广义实值。当 r(i,a)≤0时,它表示的实际上是费用。r(,a)的含义随具体应用问题的不同而有所不同。 5)V为准则( Criterion)函数(也称为目标 Objective)函数),可分为期望总报酬的(包括 折扣的,正的和负的等)和平均的等多种。详细的定义将在后面给出 注1.1(1)模型的时间可以是离散变化的,也可以是连续变化的;可以在有限时间段 上取值,也可以在无限时间段上取值;S,A(i)(∈S)均可以是有限集或至少有一个是可列 集,甚至任意非空集;状态转移概率族力可以是时齐的(即与阶段数n无关),也可以是非时 齐的,或更广的半马氏或漂移的;p也可未知的、状态信息延迟的、部分可观察的;报酬函 数r可以是有界的、各种各样无界的,甚至与系统的历史有关的;准则函数也可是各种各样 的。这几种成分各取一种即得到一个相应的马氏决策过程模型。 (2)我们在本书中之所以假定S和A()均是可数集,一方面是尽可能照顾到应用的广泛 性,另一方面也是为了避免一般状态空间和决策空间所带来的测度论方面的纷扰。因为当S 或A()为非可数无穷集时,许多叙述的合理性应予以证明。 (3)在实际应用时,状态i处可用的决策a与状态j(≠i)处可用的决策a,所代表的实际 意义可以完全不同,a仅代表在可用的决策集中编号为a的决策。 为方便起见,本章中将 DTMDP简记为MDP。从以上的定义可以看出,MDP的历史由 相继的状态和决策组成,其形式为 0 in),n≥0 其中i∈S和a∈A(i4)分别表示在第k个观察时刻点系统所处的状态和采取的决策(k=0,1, 2,…,n-1),in∈S为系统当前所处的状态。称hn为系统到n(即第n个决策时刻)时的一个 历史,其全体记为Hn。若使用记号T,则有H=×S。 系统的一个策略是指一个序列r=(m0,t1,…),当系统到n时的历史为hn时,该策略 则按A(in)上的概率分布π(·hn)采取决策。策略全体记为Ⅱ,并称之为MDP的策略空间 如果π满足条件: 丌(·hn)=兀n( ),hn∈Hn,n≥0 则称x是半马氏( Semi-Markov)策略,其全体记为Im。进而,如果 丌n(|hn)=xn(·|in),h∈Hn 与历史完全无关,则称π为随机马氏策略,其全体记为Ⅱ。在随机马氏策略下,系统在n 时所采取的决策仅仅依赖于所处的决策时刻n和状态l。进一步地,对x∈Ⅱm,如果还有 πr(·|i)=π(·|ln)与n无关,则称之为随机平稳策略,简记为x,其全体记为 定义决策函数集F=×A(i)。f∈F可看作为从S到∪A(i)的一个映射,它满足条件 i∈S f()∈A(i),i∈S。因此称∫为决策函数。对r∈m,如果丌n均是退化的,即有f∈F使 πn(J(i)|)=1(i∈S),则称此π为(确定性)马氏策略,并记为(f。,f1,…),其全体记为I。 进而,称π=(∫,∫,…)(简记为∫)为(确定性)平稳策路,其全体记为I。自然,m与F之 间有一一对应关系。为记号简单起见,我们将随机平稳策略π。简记为π,将平稳策略尸简 记为f。这样,我们将决策函数∫与平稳略∫等同看待。为方便起见,也常将∫称为平稳 策略 从上述定义可以看出,各类策略集间有如下的关系: mcm,,Ⅱ C CI Cl 在上面所定义的策略中,平稳策略是形式最简单的策略。但在实际应用问题中,还要考虑更 简单的策略,这将在有关内容中讨论。 1.2报酬过程与准则函数 对n≥0,我们用Xn,△分别表示在时刻n系统所处的状态和采取的决策,显然,它们都 是依赖于策略π的随机变量,从而(X。,Δ,Ⅺ1,Δ,…)为一随机序列。对给定的策賂x,我 们用乏(π)来表示策略π下的这一随机序列。容易看出,其概率规律完全由初始状态概率分 布(即X。的概率分布)、转移概率族及策略π所确定,其状态空间为(SX∪A(i)),其中 Xn∈S,Δ∈∪A()。还可看出,它与MDP棋型(1.1.1)式中的报酬函数和准则函数无关。 为了表示随机序列≌(丌)中的概率转移规律与所采用策珞π的关系,我们用Pn(E)表示 (x)中事件E的概率。 根据策略π的定义以及马尔可夫性(即无后效性)的含义,容易猜想,对于一般的策略x x(m)不是一个马氏过程,仅当x是马氏策路时,E(m)才是一个马氏过程。对此,我们有下 述定理。 定理21对策略π=(丌,丌1,…) (1)若r∈Ⅱm为随机马氏策略,则x(r)是一非时齐马氏链,其n时的转移概率为 PriX -1=6X a}=p(a)丌n+1(b1j),(t,a),(,b)∈ (1.2.1) 进而,(m)的状态子序列≌8(丌)=X,K1,…}亦是一个非时齐马氏链,其n时的状态转移 概率为 PRXm+1=jX.=il 丌n(a|i)p( ∈S (1.2.2) (2〕若π-π。∈为随机平稳策略,则(π)是一时齐马氏链,其状态转移概率为 Pr iX A11=bXn=i,△=a}=p(a)兀。(b|j),(i,a),(,b)∈ 进而,≌s(丌)={X,X1,…}亦是一个时齐马氏链,其状态转移概率为 P2{Xn=j1X=}=∑x(alt)(a),i,j∈S (1.2.4) gEa(F) 证明(1)对任一n≥0及历史h=(04,i1,a1,…,i-1,an-1,i)∈Hn,a∈A(i), (,b)∈F,由x∈的马氏性及概率乘法公式可知 PriXn-1=j,An+1=6hm, 4=al P(Xn 1=jIhn, 4,=a PR(+ =blh,, 4=a, Xn-1=j7 户,(a)丌n+1(b|(h 力,(a)xn1(bj) =P{xn+1=jXn=i,A,=aP+1=bX,+1=)} Pr(X1=j,A+=bX,=i,4,=a 即x(x)为非时齐的马氏链且(1.2.1)式成立。 对于≌s(x),设n≥0,i0,i1,…,i-1,i,jS,由全概率公式及r∈mm的定义知 PrX I Xo=io,X X =∑P,4=a|X=t,X:=t,…,又n=i ·P{Xn+1=j=1,X1=i1,…,X,=i,=a 丌n(a|i)力,(a) 因此≌s(m)为一非时齐马氏链且(1.2.2)式成立。 (2)由(1)求得的转移概率表达式即可知道。 对于策略r=(f0,f1,…)∈I,(x)中的△是x的一个函数: Δ=fn(Xn),n≥0 因此当X,确定时,△n也就确定了,即△的随机性完全由Xn引起。 在MDP中,对任一策略π,与随机序列x(x)相关的还有另一个随机序列 究()={R。,R1,R2,…} 其中Rn=r(Xn,A)是系统在时刻n时获得的报酬,故我们称之为报酬过程,但(x)并不是 一个独立的随机序列,它是依赖于≌(π)的。因此,也称≌(r)为带报酬的随机序列,有时也 称{X,山,R0,Ⅺ1,△1,R1,X2,△2,R2,…}为报酬过程。 对于一般的随杋序列,要确定它的转移概率,硏究其稳态分布等性质,但对于带报酬的 随机序列x(),我们要研究的主要是与s(r)相关的某些数字特征(如数学期墾,方差等), 并用其来比较策略的优劣。 我们在下面假定所述的数学期望都是存在的,例如当报酬函数一致有界时。 在策略丌下的数学期望用E-{·}表示,简记 Pn,{·}=P{·|X=计},E,{·}=En{·|X。=i 于是在r下,n=0时从初始状态i出发,在n时刻获得的期望报酬为 E,{r(X,△)}=∑Pn;{X,=j,4=ar(j,a) i,a)∈ 下面介绍马氏决策过程中常用的准则。 1.有限阶段总报酬准则 对N≥0,策略x下的N阶段期望总报酬定义为 V(丌,i) E,{r(Xn,n},t∈S (1.2.5) 它表示使用策略π,在0时从状态i出发的条件下,系统直到N-1时所获得的期望总报酬。 用Vy(π)表示第i个分量为Vx(x,)的列向量,当S可列时,Vx(x)为可列维向量 2.折扣准则 有些问题,难于确定所考察系统的有效期有多长。有的问题,即使知道系统的有效期, 只要单位时间长度取得足够短,总的阶段数仍很大,这促使我们要考虑无限阶段问题。由于 长期期望总报酬 ∑Er(x,Δ 往往不收敛或为无穷大,如r(i,a)≡1时为无穷大,因此,用长期期望总报酬作为准则就不 定有意义,需要附加一定的条件,如报酬函数丰负或非正。为了克服这一点,我们引进 个称之为折扣因子的常数β∈(0,1),其含义是:阶段n时获得的单位报酬仅值n-1时的, 从而仅值0时的P。于是系统在周期n所获得的报酬r(X,△)折算到时刻0的值为 Pr(X,△);在策略丌下,从初始状态i出发的折算到时刻0的第n阶段的期望报酬为 En{Pr(X,△)}。当β=1时即为无折扣时的情形 策略π下的无限阶段期望折扣总报酬定义为 ∑ En,{Pr(xn,▲)},i∈S (1.2.7) 第1章 引论 1.1离散时间马尔可夫决策过程模型 本节介绍最为基本的离散时间马尔可夫决策过程( Discrete Time markov decision process- es,简记为υTMDP)的模型。为方便起见,我们假定在时刻点n=0,1,2,…处观察系统,这 里n可取有限多个值,如n=0,1,2,…,N,也可取所有的非负整数。一个 DTMDP模型由 如下的五重组组成: {S,A(i),p(a),r(i,a),V,,j∈S,a∈A(1)} (1.1.1) 其中各元的含义如下: (1)S是系统所有可能的状态所组成的非空的状态集,有时也称之为系统的状态空间, 它可以是有限的、可列的集或任意非空集。本书中假定S是可数集(即有限或可列)。我们用 小写的字母t,j,k等(或加上上、下标)来表示状态。 (2)对状态i∈S,A(t)是在状态i处可用的决策集,它是非空的;当不特别指出时,本书 中亦假定它是可数集。实际上,当A()为非空集并赋以一定的拓扑结构后,本书中的绝大部 分结论仍成立。书中常用a来表示决策。 (3)当系统在决策时刻点n处于状态i,采取决策a∈A(i)时,则系统在下一决策时刻点 n+1时处于状态j的概率为力(a),它与决策时刻n无关。称p={p,(a),t,j∈S,a∈A(i)} 为系统的状态转移概率族,于是,对i∈S,a∈A(),有∑,(a)=1,即{(a),j∈S}为 随机向量。范围稍广一点的是{pa),j∈S为次随机向量的情形,即∑p(a)≤1,在大多 数情形下,这两种情形可统一考虑。 4)当系统在决策时刻点n处于状态讠,采取决策a∈A()时,系统于本阶段获得的报酬 为r(i,a)。如果记r={(,a)i∈S,a∈A(i)},则r是定义在P上的一个广义函数r:r -∞,十∞],于是我们常称r为报酬函数。r可以只取有限实值,也可取广义实值。当 r(i,a)≤0时,它表示的实际上是费用。r(,a)的含义随具体应用问题的不同而有所不同。 5)V为准则( Criterion)函数(也称为目标 Objective)函数),可分为期望总报酬的(包括 折扣的,正的和负的等)和平均的等多种。详细的定义将在后面给出 注1.1(1)模型的时间可以是离散变化的,也可以是连续变化的;可以在有限时间段 上取值,也可以在无限时间段上取值;S,A(i)(∈S)均可以是有限集或至少有一个是可列 集,甚至任意非空集;状态转移概率族力可以是时齐的(即与阶段数n无关),也可以是非时 齐的,或更广的半马氏或漂移的;p也可未知的、状态信息延迟的、部分可观察的;报酬函 数r可以是有界的、各种各样无界的,甚至与系统的历史有关的;准则函数也可是各种各样 的。这几种成分各取一种即得到一个相应的马氏决策过程模型。 (2)我们在本书中之所以假定S和A()均是可数集,一方面是尽可能照顾到应用的广泛 性,另一方面也是为了避免一般状态空间和决策空间所带来的测度论方面的纷扰。因为当S 或A()为非可数无穷集时,许多叙述的合理性应予以证明。 (3)在实际应用时,状态i处可用的决策a与状态j(≠i)处可用的决策a,所代表的实际 意义可以完全不同,a仅代表在可用的决策集中编号为a的决策。 为方便起见,本章中将 DTMDP简记为MDP。从以上的定义可以看出,MDP的历史由 相继的状态和决策组成,其形式为 0 in),n≥0 其中i∈S和a∈A(i4)分别表示在第k个观察时刻点系统所处的状态和采取的决策(k=0,1, 2,…,n-1),in∈S为系统当前所处的状态。称hn为系统到n(即第n个决策时刻)时的一个 历史,其全体记为Hn。若使用记号T,则有H=×S。 系统的一个策略是指一个序列r=(m0,t1,…),当系统到n时的历史为hn时,该策略 则按A(in)上的概率分布π(·hn)采取决策。策略全体记为Ⅱ,并称之为MDP的策略空间 如果π满足条件: 丌(·hn)=兀n( ),hn∈Hn,n≥0 则称x是半马氏( Semi-Markov)策略,其全体记为Im。进而,如果 丌n(|hn)=xn(·|in),h∈Hn 与历史完全无关,则称π为随机马氏策略,其全体记为Ⅱ。在随机马氏策略下,系统在n 时所采取的决策仅仅依赖于所处的决策时刻n和状态l。进一步地,对x∈Ⅱm,如果还有 πr(·|i)=π(·|ln)与n无关,则称之为随机平稳策略,简记为x,其全体记为 定义决策函数集F=×A(i)。f∈F可看作为从S到∪A(i)的一个映射,它满足条件 i∈S f()∈A(i),i∈S。因此称∫为决策函数。对r∈m,如果丌n均是退化的,即有f∈F使 πn(J(i)|)=1(i∈S),则称此π为(确定性)马氏策略,并记为(f。,f1,…),其全体记为I。 进而,称π=(∫,∫,…)(简记为∫)为(确定性)平稳策路,其全体记为I。自然,m与F之 间有一一对应关系。为记号简单起见,我们将随机平稳策略π。简记为π,将平稳策略尸简 记为f。这样,我们将决策函数∫与平稳略∫等同看待。为方便起见,也常将∫称为平稳 策略 从上述定义可以看出,各类策略集间有如下的关系: mcm,,Ⅱ C CI Cl 在上面所定义的策略中,平稳策略是形式最简单的策略。但在实际应用问题中,还要考虑更 简单的策略,这将在有关内容中讨论。 1.2报酬过程与准则函数 对n≥0,我们用Xn,△分别表示在时刻n系统所处的状态和采取的决策,显然,它们都

...展开详情
试读 127P 马尔可夫决策过程引论
立即下载 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
马尔可夫决策过程引论 46积分/C币 立即下载
1/127
马尔可夫决策过程引论第1页
马尔可夫决策过程引论第2页
马尔可夫决策过程引论第3页
马尔可夫决策过程引论第4页
马尔可夫决策过程引论第5页
马尔可夫决策过程引论第6页
马尔可夫决策过程引论第7页
马尔可夫决策过程引论第8页
马尔可夫决策过程引论第9页
马尔可夫决策过程引论第10页
马尔可夫决策过程引论第11页
马尔可夫决策过程引论第12页
马尔可夫决策过程引论第13页
马尔可夫决策过程引论第14页
马尔可夫决策过程引论第15页
马尔可夫决策过程引论第16页
马尔可夫决策过程引论第17页
马尔可夫决策过程引论第18页
马尔可夫决策过程引论第19页
马尔可夫决策过程引论第20页

试读结束, 可继续阅读

46积分/C币 立即下载