《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第16章离散状态的Markov控制与决策过程简介.pdf_大学文库

439 龚光鲁, 钱敏平著应用随机过程教程 – 与在算法和智能计算中的应用清华大学出版社, 2003 第16章离散状态的Markov控制与决策过程简介 (Controlled Markov Process, Markov Decision Process, MDP) 1 例 1. 1 随机决策模型的简单例子定义１６.１随机决策模型的对象是可以控制的随机系统, 人们可以选取控制决策, 以改变发展过程的路径. 在任意固定时刻, 系统随机地处在 S = {1,2,L,N}中的某个状态, 而在策略取定为 a 的情况下系统的发展是按照一个随机矩阵 P (a) 作为转移概率阵而变化. 这就称为一个 Markov 决策过程．从下面的简单例子，可以得到一些直观的认识。例１６．２设某个经营系统总处在"1","2","3"三种状态之一．假定在每个整值时刻可选择两种不同的动作之一：a（1）或a（2），而在采取动作a（1）或a（2）时，状态间的转移矩阵分别为 P( (1) a )= ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ 2 1 0 2 1 2 1 2 1 0 0 2 1 2 1 , P( (2) a )= ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ 2 1 2 1 0 0 2 1 2 1 2 1 0 2 1 . 假定开始时（即时间n = 0时）该系统以相等的可能性处在这三个状态之一 , 即初始分布为 ÷ ø ö ç è æ 3 1 , 3 1 , 3 1 . 又设处在状态i 时, 采取动作 (1) a 能得到报酬为 g(i, a ) 2i (1) = , 而处在状态i 时, 采取动作 (2) a 能得到报酬为 2 1 ( , ) 2 g i a(2) = i + . 我们要在各个时刻, 根据历史状况,有目的地选取动作 (1) a 或 (2) a ,使在时间区段0 £ n £ m 内得到的平均累积报酬最大．这里，动作是历史状况的函数．从时刻 n 的历史状况到采取的动作的对应（即函数），称为时刻 n 采取的策略．各个时刻采取的策略合起来，称为一个策略．我们要选取一个策略，使在时间区段 0 £ n £ m 内得到的平均累积报酬最大．把在时刻 n 采取的动作记为 an , 那么它只能 (1) a 或 (2) a 之一. 于是转移矩阵 P(an ) ij n i j N p a = , £ ( ( )) 有确切的含义. 这样, 由初始分布 m0 =( m 1 , m 2 , m 3 )=( 3 1 , 3 1 , 3 1 ) 及转移矩阵列{ P(an )}决定了一个 3 个状态的非时齐的 Markov 链{ : n ³ 0} n x ． n x 代表系

442 而在n £1时段内的最高平均累积报酬为 12 125 ( , ) * 1 * V f 0 f = . 1. 2 简单模型的启示由例１６．２可以看出, 如果限制在形如 ( ) n n n a = f x 的策略类中, 去找最佳的策略 ( 即 ”从状态到动作的对应" n f ，那么, 只要先选定时刻最后的m 时刻所对应最佳的 * m f ，然后向后归纳地选最佳的 * 0 * 1 f , , f m - L . 由此可以抽象出第 2 节中较为一般的数学模型． 2 动作只依赖当前所处状态的简单决策模型 2. 1 简单模型的一般描述定义１６.３（决策动作不依赖系统的状态的情形）假定在参数a （a ∈某个有限集 A , 称为行动集）固定时, Ｐ(a ) ij i j N p a = , £ ( ( )) 是一个以 S = {1，2，L，N} 为状态空间的转移矩阵. 设在时刻 0,1,...各选一个行动，记为 , , ( ) a0 a1 L ai Î A , 那么由初分布m0 ( , , ) = m1 L m N 及转移矩阵序列{P(an ):n≥0} 可以决定一个非时齐的 Markov 链 n x ，满足： i P(x0 = i) = m , ( | ) ( ) n 1 n ij n P = j = i = p a + x x . 假定时刻 n 系统处在状态 i 时，采取行动 an 得到的报酬由报酬函数 g (i,a) n 表示,那么在时刻m 得到的累计报酬为 å= m n g n n an 0 (x , ) , 其中 g (i,a) n 是在时刻n 采取行动 a 且处在状态 i 时的报酬函数, 那么,平均累计报酬为 [ ( , )] 0 å= m n E g n x n an . 定义１６.４（决策动作仅依赖系统当前的状态的情形时的期望总报酬）这也是一种简单情形，例１６．３是它的特例．这时容许an 的取值依赖于链所处的状态i 的情形, 即 a f (i) n = n 的情形, 其中 n f 是状态集 S 到动作集的 A 的一个映射, 其含义为: 若 Markov 链在时刻n 处于状态i , 则采取决策a f (i) n = n ．令 P n ij n i j N p f i = , £ ( ( ( )) , （１６．１）则它仍是一个随机矩阵．由初始分布m0及{P n ,n≥0}决定了一个非时齐 Markov 链 n x ．类似地由报酬函数 g(i, a) 可以得到时刻m 的平均累计报酬．此 Markov 链 n x 在各个时刻的转移

443 矩阵是不同的，它们依赖初始分布m0及各个时刻的策略映射序列{ f n ³ 0} n，．我们记 f { f ,0 n m} = n £ £ D , （１６．２）并称它为一个策略．于是，使用它得到的平均累计报酬为 m０ E ÷ ø ö ç è æ å= m n n n n g f 0 (x , (x ) . 注意, 对于非时齐的 Markov 链 n x 的轨道 } 0 1 m （x ，x ，L，x 而言，我们采取的行动列为 { ( ), , ( )) 0 0 m m f x L f x . 由于我们的行动列只依赖于 Markov 链当前所处的状态, 这样的特殊策略 f { f f ( ),0 n m} = n = n * £ £ D 也称为 Markov 策略, 这时动作 ( ) n n n a = f x 是随机的. 在 Markov 链的初分布为m0时, 我们将 f 在时刻m 取得的平均累计报酬记为 J ( m0 ,f): J ( m0 ,f) = m０ E ÷ ø ö ç è æ å= m n n n n g f 0 (x , (x )) . （１６．３）在系统的初始状态为 i 时, 平均累计报酬为 J ( i ,f) = ÷ ø ö ç è æ å= m n i n n n E g f 0 (x , (x )) . (有时在总报酬中, 除了累计报酬外, 还要加上一个终止报酬 ( ) h m x , 此时 J ( m0 ,f) = m０ E ÷ ø ö ç è æ å + = m n n n n h n g f 0 (x , (x ) (x ) . 而其数学处理是完全一样的). [注 1] 以上考虑的是纯策略, 更为灵活的是使用混合策略, 也就是随机策略, 它以给定的概率分配取动作集 A 中的不同动作, 抽象地可以看成一个取值于 A 的概率向量(概率分布) m . 这时的动作集 A 就用取值于 A 的全体概率向量组成的集合(记成 P )所代替. 注意, 我们可以认为 A Ì P , 因为纯策略是一个特殊的随机策略. 在随机策略类P 中考虑累计报酬, 其每一步计算都应作相应的改变. 在使用随机策略时的最佳报酬函数相应地为 ( ) 0, × V m , 其中 D Vk,m (i) = p sup ÷ ø ö ç è æ å= m n k Ei gn n n (x ,p ) , （１６．４）而p p p p n ( , , ), = 0 1 L 表示时刻n 使用的随机策略．可以证明，当g (i,a) g(i,a) n = (不依赖n )时, Vk,n 关于k 满足一个 Bellman 型向后递推公式 ( ) 0 ( ) sup [ ( , ) ( ) ( )] , 1, 1 , = = + + = Î å V i V i g i a p a V j m m ij k m N j k m a A

由此可以反向地逐步解出在随机策略下的最佳报酬函数.显见,它不小于在纯策略下的最佳报酬函数在其它的情形,例如下面将介绍的折扣模型的情形,实际上只须沿着这个思路方向,做相应的改变就也就可以得到最佳报酬函数.在历史发展给定条件下,随机策略的条件分布如果只与系统的当前状态有关则这样的随机策略称为 Markov随机策略.如果只与系统的初始状态与当前状态有关,则称为半Mrk。v随机策略 [注2]在实际情形中,更多出现的是复杂的情形,即对不同的状态可采取的动作集也不同,就是说,如果系统处在状态i,则能选取的动作集合为A·于是这时相应地要求f(n)∈A·为了使读者领会实质,在本书中我们只讨论A1们相同的简单情形,其实其方法与理论并无二致注3]以上考虑的是 Markov策略,即当前时刻所采取的动作只依赖于当前所处的状态的简单情形.一般如果采取的动作依赖于 Markov链的历史,那就复杂多了,但是在实际问题中,出现更多的是只依赖当前所处的状态的情形,或者近似是这种情形.作为个别情形,也需要考虑依赖最近两个或多个时间的历史资料的情形,此时原则上可以通过扩大状态空间维数的方法,化为 Markov策略的情形定义16.5(最佳策略) Markov随机决策的基本问题是:寻找最优平均累计报酬 sup( J(μo,f)及最佳马氏策略f",使平均累计报酬 J(μo,f)=sψrJ(μo,f), (16.5) 这里Sωp取遍所有的 Markov策略.这样的f如果存在,则称为最佳 Marko策略在实际问题中,有时即使最佳 Markov策略存在,但却因为计算量过大或计算时间过长而变得实际上不可能.而ε一最佳 Markov策略常比最佳 Markov策略更为实际可行. 定义16.6(E-最佳 Markov策略)f称为一个ε-最佳 Markoⅴ策略,如果 J( Ho, f)>sup j(Ho, f)-E [注]在求最佳 Markov策略的计算复杂度为非多项式时,求E一最佳马氏策略常常能使计算降为多项式复杂度.可见花费这个E的代价,能带来极大的收益定义16.7如果对于任意n,an也不依赖于ξn,但是,是随机的,即它是与 Markov链的发展无关的″常随机″行动:an=ηn(ηn是取值于A的随机变量),这种策略记为a={n,n≤m},称为独立的随机策略 2.2有限时段总报酬准则下的最佳 Markov策略的构造定理16.8在所有的 Markov策略类中存在最佳 Markov策略(但未必唯一) 证明证明的过程实际上就是寻找一个最佳 Markov策略的具体方法.要在 Markov策略类中构造一个最佳的.而构造最佳 Markov策略f’的方法则完全和例16.1一样首先取∫m(1) g(i,fm(i))=maxs4 8 (i,a=gm(D)

444 由此可以反向地逐步解出在随机策略下的最佳报酬函数. 显见，它不小于在纯策略下的最佳报酬函数. 在其它的情形, 例如下面将介绍的折扣模型的情形, 实际上只须沿着这个思路方向, 做相应的改变就也就可以得到最佳报酬函数. 在历史发展给定条件下, 随机策略的条件分布如果只与系统的当前状态有关, 则这样的随机策略称为 Markov 随机策略．如果只与系统的初始状态与当前状态有关, 则称为半 Markov 随机策略． [注 2] 在实际情形中, 更多出现的是复杂的情形, 即对不同的状态可采取的动作集也不同, 就是说, 如果系统处在状态i , 则能选取的动作集合为 Ai ．于是这时相应地要求 n f n n Ax (x )Î ．为了使读者领会实质, 在本书中我们只讨论 Ai 们相同的简单情形, 其实其方法与理论并无二致． [注 3] 以上考虑的是 Markov 策略, 即当前时刻所采取的动作只依赖于当前所处的状态的简单情形．一般如果采取的动作依赖于 Markov 链的历史, 那就复杂多了．但是在实际问题中, 出现更多的是只依赖当前所处的状态的情形, 或者近似是这种情形．作为个别情形，也需要考虑依赖最近两个或多个时间的历史资料的情形, 此时原则上可以通过扩大状态空间维数的方法, 化为 Markov 策略的情形．定义１６.５（最佳策略） Markov 随机决策的基本问题是：寻找最优平均累计报酬sup f J ( m0 ,f)及最佳马氏策略 f *，使平均累计报酬 J ( m0 ,f * )= sup f J ( m0 ,f), （１６．５）这里 Sup 取遍所有的 Markov 策略. 这样的 f *如果存在，则称为最佳 Markov 策略．在实际问题中, 有时即使最佳 Markov 策略存在, 但却因为计算量过大或计算时间过长而变得实际上不可能. 而e -最佳 Markov 策略常比最佳 Markov 策略更为实际可行. 定义１６.６（e -最佳 Markov 策略） f e 称为一个e -最佳 Markov 策略, 如果 J ( m0 ,f e )> sup f J ( m0 ,f)- e . （１６．６） [注] 在求最佳 Markov 策略的计算复杂度为非多项式时, 求e - 最佳马氏策略常常能使计算降为多项式复杂度. 可见花费这个e 的代价, 能带来极大的收益．定义１６.７如果对于任意 n , an 也不依赖于 n x ，但是, 是随机的，即它是与 Markov 链的发展无关的"常随机"行动: an =hn (hn是取值于 A 的随机变量)，这种策略记为 a { ,n m} = hn £ ，称为独立的随机策略． 2. 2 有限时段总报酬准则下的最佳 Markov 策略的构造定理１６．８在所有的 Markov 策略类中存在最佳 Markov 策略(但未必唯一). 证明证明的过程实际上就是寻找一个最佳 Markov 策略的具体方法．要在 Markov 策略类中构造一个最佳的．而构造最佳 Markov 策略 f *的方法则完全和例１６．１一样. 首先取 ( ) * f i m ( , ( )) max ( , )( ( )) * * g i f i g i a g i m m a A m m D = Î =

445 再取 * m-1 f 使时刻m -1的报酬函数达到最大, 即 ( , ( )) ( ( )) ( ) max [ ( , ) ( ) ( )]( ( )) * 1 1 * 1 1 1 * * 1 * 1 1 g i f i p f i g j g i a p a g j g i m N j a A m ij m N j m m ij m m - D = Î - - = - - +å - = +å = 然后，向后递推地取 ( ) * f i k 使时刻k 的报酬函数达到最大, 即 ( , ( )) ( ( )) ( ) max [ ( , ) ( ) ( )]( ( )) * 1 * 1 * 1 * * g i f i p f i g j g i a p a g j g i k N j a A k ij k N j k k ij k k D = Î = +å + = +å = . 这样就得到了 f { , , , } * * 1 * 0 * m m f f f = L - ．现在证明它是最佳的 Markov 策略. 对于任意 Markov 策略 f=( n f ,0≤n≤m), 定义辅助 Markov 策略 f (k ) { , , , , , } * * 0 k k 1 m f L f f L f + D = . 用后向数学归纳法可以直接验证以下不等式 J ( m0 ,f)≤J ( m0 ,f ) (k ) (k≤m). 取 k=0 即得J ( m0 ,f)≤J ( m0 ,f ) * ．请读者自己补上这段验证． [注 1] 以上寻找 f *的方法, 在计算机上实现十分简单．问题在于当行动集 A 较大的时候, 计算量会非常大，甚至难以在允许的时间内完成。于是代之以用 e -最佳 Markov 策略. [注 2] 本定理可以推广到状态集 S 是为可数集，行动集 A 是紧集，而报酬函数 g (i,a) n 是有界连续函数情形. [注 3] 在状态集与动作集较为一般的时候, 为了保证最佳策略的存在, 纯策略类就不够,必须考虑用随机策略类. 2. 3 无穷时段下的总报酬情形 (m = ¥的情形) 定理１６．９如果报酬函数序列满足以下的衰减性质 å < ¥ ¥ =0 , sup | ( , ) | n i a g n i a , （１６．７）那么存在最佳 Markov 策略 f * ．（可以利用有限近似证明）．例１６.１０（折扣模型）在应用中常见例子为折扣报酬模型，即 ( , ) ( , ) 0 g i a r g i a n n = 的情形，其中0 < r <1是折扣因子．此时只要 ( , ) g0 i a 是有界函数, 则条件(16.7)满足. 定义１６.１１（平稳策略）如果 Markov 策略 f=( , n f n≥0)对于任意n 满足 0 f f n = ，则称为平稳 Markov 策略．

统的初始状态.作平均报酬序列Jx(o,f) ∑Vm(i,f),一般J(0,f)的极限未必存在 N+1如=6 所以常取其收敛子序列中极限的最大者,记为J(o,f),或极限中的最小者,记为J(o,f).用它们作为目标函数.前者是以乐观的态度看待报酬,而后者是以悲观的态度看待报酬.在使用随机策略时,相应地记为J(,丌),其中兀=(兀0,丌1…)兀n表示时刻n使用的随机策略而把 J(0)=supx(0,丌)作为最佳函数.这种平均准则常见于发展较为平稳的系统,例如通讯网络,而累计总报酬准则,则常见于较快变化的系统,例如金融系统.轨道平均报酬准则的数学处理,通常比平均累计总报酬准则情形要复杂 [注6]最一般的模型是策略的动作依赖历史情况的策略:设S与A仍都为有限集,又设随机变量列{n}满足 Pm=50=051=4,…,5n=in)=P,(an) 其中an由下式递推地确 ao=fo(io) a,=f,(io,ao, i,a,,.,i-l,a-in) 这时的{n}不再是 Markov链,因为它依赖于所有的过去历史.而且此时an是一个依赖于{50,…,n} 的随机变量.如果我们仍记f=(n,n≥0,并称之为一个策略,那么对此模型也可类似地定义最佳策略及最佳E一策略.事实上,对此模型可以证明:在很宽的条件下,定理16.8中的最佳 Marko策略也是这里的策略类中的最佳策略.也就是最佳 Markov策略在以上定义的非马氏策略类中仍是最佳的.这就可以把搜索最佳策略的策略类的范围大大地缩小了 [注7]在常见的实际模型中,有一类状态空间S是一个区间(端点可以为∞),动作集A=A2 是依赖状态x的一个有限区间.例如 (1) Ricker模型(合理捕鱼问题)设在时刻n湖中鱼的总量为5n·捕鱼的原则是,在有计划地留下数量(随机的)a的鱼用以繁殖的前题下,求最大捕鱼量.假定鱼的数目与留下的数量受群体控制的 Ricker模型所制约 EniI=C a,e" 其中C1,C2为常数,{n}是独立同分布随机变量列.于是捕鱼量为g(5n,an)=5n-an中的 8n(x,a)=x-a与n无关,这时状态空间为S=[0∞),当状态确定为x时的动作集为

447 统的初始状态. 作平均报酬序列 ( , 0 J i N f å= D + = N N 1 m 0 1 ) ( , 0 V i m f ) , 一般 ( , 0 J i N f ) 的极限未必存在，所以常取其收敛子序列中极限的最大者，记为 ( , 0 J i f ) ，或极限中的最小者，记为 ( , 0 J i f ) . 用它们作为目标函数．前者是以乐观的态度看待报酬, 而后者是以悲观的态度看待报酬. 在使用随机策略时，相应地记为 ( , 0 J i p ) , 其中 p p p p n ( , , ), = 0 1 L 表示时刻 n 使用的随机策略．而把 0 J (i ) sup ( , ) p J i 0 p D = 作为最佳函数．这种平均准则常见于发展较为平稳的系统，例如通讯网络, 而累计总报酬准则，则常见于较快变化的系统，例如金融系统．轨道平均报酬准则的数学处理，通常比平均累计总报酬准则情形要复杂． [注６] 最一般的模型是策略的动作依赖历史情况的策略：设 S 与 A 仍都为有限集，又设随机变量列{ }n x 满足 P(x | 1 j n+ = x , , , ) 0 0 1 1 n n = i x = i L x = i ( ) i , j n p a n = , 其中an 由下式递推地确定： ( ) 0 0 0 a = f i , ..., ( , , , , , , , ) n n 0 0 1 1 n 1 n 1 n a f i a i a i a i = L - - ．这时的{ }n x 不再是 Markov 链，因为它依赖于所有的过去历史．而且此时an 是一个依赖于{ , , } 0 n x L x 的随机变量．如果我们仍记 f=( , n f n≥0), 并称之为一个策略, 那么对此模型也可类似地定义最佳策略及最佳e - 策略．事实上，对此模型可以证明：在很宽的条件下，定理１６．８中的最佳 Markov 策略也是这里的策略类中的最佳策略．也就是最佳 Markov 策略在以上定义的非马氏策略类中仍是最佳的．这就可以把搜索最佳策略的策略类的范围大大地缩小了． [注７] 在常见的实际模型中, 有一类状态空间 S 是一个区间(端点可以为¥ ), 动作集 A = Ax 是依赖状态 x 的一个有限区间．例如 (1) Ricker 模型 (合理捕鱼问题) 设在时刻n 湖中鱼的总量为 n x ．捕鱼的原则是，在有计划地留下数量(随机的) an 的鱼用以繁殖的前题下，求最大捕鱼量．假定鱼的数目与留下的数量受群体控制的 Ricker 模型所制约： n c an n n c a e 2 1 1 - + = h x , 其中 1 2 c , c 为常数, { } hn 是独立同分布随机变量列．于是捕鱼量为 g n an = n - an D (x , ) x 中的 gn (x,a) = x - a 与 n 无关．这时状态空间为 S = [0,¥) , 当状态确定为 x 时的动作集为

448 A [0, x] x = ．在这模型中 , 相应于转移矩阵 P ( ) ( ( ), ) ij Ai a = p a a Î 的是转移核 p(x, y; a) （a Î Ax）．如果采用策略 f ( , ( )) n n n n = f a = f x , 则在时刻 m 的平均累计报酬为 ( , 0 J x f ) [ ( ( ))] 0 0 n n m n x = E å x - f x = , 其中 0 0 x = x (也可以是随机的), f x x 0 £ n ( ) £ ． (2) 最佳投资组合假定只有两种证券, 无风险的证券(例如存银行, 其利率为r )及有风险的股票．设财产 n x 中投资于股票的比例为 ,(0 £ £ 1) an an , 且以数量 n c 消费．此时状态空间为 S = [0,¥) ,当状态确定为 x 时的动作集为 A [0,1] [0, x] x = ´ , 即 a = (a,c),(0 £ a £ 1,0 £ c £ x) ．于是状态发展为 [(1 )(1 ) ]( ) n 1 n n n n n = + r - + - c + x a a h x , 其中hn 是股票的价值．典型的报酬函数是 g( x,(a,c)) = u(c) , 它代表由消费带来的 ”乐趣”, 在经济学中称为由消费 c 产生的效用函数．如果假定{ } hn 为独立同分布, 则{ }n x 正是与前面类似的模型. 但是, 用独立同分布的随机变量来描述股票的误差较大．如果用 Black-Scholes 模型的离散采样描述股票, 虽然较为合理, 但是这会使模型变得复杂． (3) 存储问题讨论时刻 n 时商店中某种货品的存储量 n x ．设进货量为 an ，假定市场需求为独立同分布的随机变量序列hn ．又设商店对此货品划定了最大容许库存量 c ．那么,状态空间 S = [-¥, c] (在x n < 0 时表示缺货), 在状态(库存)为 x 时的动作集为 A [0, c x] x = - , 而 n n an hn x +1 = x + - ．此时报酬函数依赖于市场需求．假定单个货品的卖价为 s , 进货价为 d , 存储消耗价为h , 那么时刻n 的报酬为 ( , , ) (min( , ) ( ) n n n n n an n dan h n an g x a h = s x + h - - x + . 由此可以考虑最大化报酬. [注８] 还可以考虑时间连续的情形, 这就是可控 Markov 过程．这类问题较为复杂, 在概率论中涉及最佳停时, 而在求解最佳策略时, 常用偏微分方程中的活动边界理论或变分不等式．

《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第16章 离散状态的Markov控制与决策过程简介

《应用随机过程教程》教学资源（参考资料）与在算法和智能计算中的应用——第16章离散状态的Markov控制与决策过程简介