龚光鲁,钱敏平著应用随机过程教程一与在算法和智能计算中的应用 清华大学出版社,2003 第16章离散状态的 Markov控制与决策过程简介 Controlled Markov Process, Markov Decision Process, MDP) 1例 1.1随机决策模型的简单例子 定义16.1随机决策模型的对象是可以控制的随机系统,人们可以选取控制决策, 以改变发展过程的路径.在任意固定时刻,系统随机地处在S={1,2,…,N}中的某个状态, 而在策略取定为a的情况下系统的发展是按照一个随机矩阵P(a)作为转移概率阵而变化. 这就称为一个 Markov决策过程. 从下面的简单例子,可以得到一些直观的认识。 例16.2设某个经营系统总处在"1","2″,"3″三种状态之一.假定在每个整值时 刻可选择两种不同的动作之一:ao或aa,而在采取动作ao或aa2时,状态间的转移矩阵 分别为 0 22 P(any) 0 假定开始时(即时间n=0时)该系统以相等的可能性处在这三个状态之一,即初始分布 为 又设处在状态i时,采取动作a1)能得到报酬为g(1a()=2,而处在状态i时, 333 采取动作a(2)能得到报酬为g(,a2)=1+·我们要在各个时刻,根据历史状况,有目的 地选取动作a或a(2),使在时间区段0≤n≤m内得到的平均累积报酬最大.这里,动作是 历史状况的函数.从时刻n的历史状况到采取的动作的对应(即函数),称为时刻n采取的 策略.各个时刻采取的策略合起来,称为一个策略.我们要选取一个策略,使在时间区段 0≤n≤m内得到的平均累积报酬最大 把在时刻n采取的动作记为an,那么它只能a(或a(2之一·于是转移矩阵 P(a)=(n(an)有确切的含义,这样,由初始分布Hn=(,2,3(2,1 及转移矩阵列{P(an)}决定了一个3个状态的非时齐的 Markov链{n:n≥0)}.5n代表系 439
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 代表系
统在时刻n所处的(随机的)状态.于是系统在时刻m前所得的平均累积报酬为 E∑g(nan)·它就是需要优化的目标函数 动作an的选取,直接影响了在时刻n以后此 Markov链的样本的走向{n,…,5m) 般地,动作an依赖于系统的发展历史,即依赖于{0,a0251,a12…,5n-,am125n}.这里 我们简单地限制在时刻n所采取的动作只依赖于当时所处的状态,也就是假定an只是5n的 函数,即an=fn(n)(其中fn:42,3→{a)2a2},是根据所处的状态选取的动作,即 在时刻n所采取的策略).我们先以m=1为例,看如何求得最高的平均累积报酬.也就是 让ao=J(50),a1=f(51),要选取函数(映射)J0,f1,使 (0,f1)=Eg(50,f0(50)+Eg(51,f1(51) 取到最大值.注意 E8(50,f6(50)=∑g(,f6() 而采取了动作a0(=f0(50))后,非时齐的 Markov链5n从时刻0到时刻1的转移矩阵应该是 P(J0(50),于是 P(51=)=∑P2(G() 从而 Eg(5,()=∑g(,f(P(1= 412g(,f()P(f() 也就是 (G,)=∑8(,()1+∑∑Hg(,f(DP2(6(0) 由此式看出,若要选取策略(,∫)使(J,f)的值为最大,需先选取f1使g(j,f()最 大.对此我们观察到 (j=1)g(1a()=2>=g(1a(2)
440 统在时刻 n 所处的(随机的 )状态．于 是系统在时刻 m 前所得的平均累积报酬为 ( ( , )) 0 å= m n E g x n an . 它就是需要优化的目标函数． 动作an 的选取，直接影响了在时刻 n 以后此 Markov 链的样本的走向{ , , ) n 1 m x L x + . 一般地, 动作 an 依赖于系统的发展历史, 即依赖于{ , , , , , , , } 0 a0 1 a1 n 1 an 1 n x x x x L - - . 这里 我们简单地限制在时刻n 所采取的动作只依赖于当时所处的状态，也就是假定an 只是 n x 的 函数, 即 ( ) n n n a = f x (其中 n f :{1,2,3} { , } (1) (2 ) ® a a ，是根据所处的状态选取的动作，即 在时刻n 所采取的策略)．我们先以 m = 1为例，看如何求得最高的平均累积报酬．也就是 让 ( ) 0 0 0 a = f x , ( ) 1 1 x1 a = f , 要选取函数(映射) 0 1 f , f , 使 ( , ) ( , ( )) ( , ( )) 0 1 0 0 0 1 1 1 V f f = Eg x f x + Eg x f x D 取到最大值. 注意 å= = 3 1 0 0 0 0 ( , ( )) ( , ( )) i i Eg x f x g i f i m . 而采取了动作 ( ( )) 0 0 0 a = f x 后，非时齐的 Markov 链 n x 从时刻 0 到时刻 1 的转移矩阵应该是 P ( ( )) 0 0 f x ，于是 ( ) ( ( )) 0 3 1 1 P j p f i i ij i x å m = = = . 从而 å= = = 3 1 1 1 1 1 1 ( , ( )) ( , ( )) ( ) j Eg x f x g j f j P x j ( , ( )) ( ( )) 3 1 1 0 3 1 åå= = = j i ij i m g j f j p f i . 也就是 V( f 0 , f 1 ) = å + = 3 1 0 ( , ( )) i i g i f i m åå= = 3 1 1 0 3 1 ( , ( )) ( ( )) j i ij i m g j f j p f i . 由此式看出， 若要选取策略（f 0 , f 1）使 ( , ) 0 1 V f f 的值为最大，需先选取 1 f 使 ( , ( )) 1 g j f j 最 大. 对此我们观察到 (1, ) 2 3 ( 1) (1, ) 2 (1) (2) j = g a = > = g a
(/=2)g(2,a1)=4、9 19 > g(3,a2) 可见,要使g(,f1()最大,f应取如下定义的f f:(123)→(au2a(2),a() 将在确定了f=后的最大报酬记为g',那么 G=1) g0)=K(()=120=2) =3) 于是 (G,F)=∑Ag(,J0()+∑gOp2(6( 剩下的就是选取f,使V(f0,∫1)最大.为此只需使方括号中的各个量都取到最大,与前 面不同之处,只是用方括号中量代替了前面的g(j,f()而已.下面我们列出它的值,由 P(a1)与P(a(2)的定义得 8(,a)+∑g(p(a)g(a2)+∑g(P(a2) 4+ 9 =3 6+(2+) 比较其各行的大小,可知f应取策略f f6:(123)→(a(2,aa),a 其对应的值(最大值)分别为 (f,f) 59125 于是在我们所限制的策略类之中,最佳决策为由如上定义的(f6,∫)所确定的 ao=f(50),a1=f(1)
441 (2, ) 2 9 ( 2) (2, ) 4 (1) (2) j = g a = = g a . 可见, 要使 ( , ( )) 1 g j f j 最大, 1 f 应取如下定义的 * 1 f ： : (1,2,3) ( , , ) (1) (2) ( ) * f 1 ® a a a１ . 将在确定了 * 1 1 f = f 后的最大报酬记为 * g , 那么 ï î ï í ì = = = = = 6 ( 3) ( 2) 2 9 2 ( 1) ( ) ( , ( )) * 1 * j j j g j g j f j 于是 ( , ) [ ( , ( )) ( ) ( ( ))] 0 * 3 1 0 3 1 * 0 1 V f f g i f i g j p f i ij j i i å å = = = m + . 剩下的就是选取 0 f ，使 ( , ) * 0 1 V f f )最大．为此只需使方括号中的各个量都取到最大．与前 面不同之处，只是用方括号中量代替了前面的 ( , ( )) 1 g j f j 而已. 下面我们列出它的值，由 ( ) (1) p a ij 与 ( ) (2) p a ij 的定义得 ) 2 9 (6 2 1 2 19 ) 2 19 (2 2 1 3 6 2) 2 9 ( 2 1 2 9 ) 2 19 2 9 ( 2 1 2 4 (2 6) 2 1 2 3 ) 2 9 (2 2 1 1 2 ( , ) ( ) ( ) ( , ) ( ) ( ) 3 1 (2) * (2) 3 1 (1) * (1) = + + + + = + + + + = + + + + +å +å = = i i i g i a g j p a g i a g j p a j ij j ij . 比较其各行的大小，可知 0 f 应取策略 * 0 f ： :(1,2,3) ( , , ) (2) (1) )2) * f 0 ® a a a , 其对应的值(最大值)分别为： 2 11，11, 4 59 ．所 以 12 125 ) 4 59 11 2 11 ( 3 1 ( , ) * 1 * V f 0 f = + + = ． 于是在我们所限制的策略类之中, 最佳决策为由如上定义的( , ) * 1 * 0 f f 所确定的 ( ) 0 * 0 0 a = f x , ( ) 1 * 1 1 a = f x
而在n≤1时段内的最高平均累积报酬为T(,f) 125 1.2简单模型的启示 由例16·2可以看出,如果限制在形如an=∫n(ξn)的策略类中,去找最佳的策略 (即“从状态到动作的对应”fn,那么,只要先选定时刻最后的m时刻所对应最佳的fm, 然后向后归纳地选最佳的∫m4,…,f.由此可以抽象出第2节中较为一般的数学模型 2动作只依赖当前所处状态的简单决策模型 2.1简单模型的一般描述 定义16.3(决策动作不依赖系统的状态的情形) 假定在参数a(a∈某个有限集A,称为行动集)固定时,P(a)=(P2(a),s是 一个以S={1,2,…,N}为状态空间的转移矩阵.设在时刻0,1,,各选一个行动,记为 a0,a1,…(a1∈A),那么由初分布o=(p1,…,Hx)及转移矩阵序列伊P(an):n≥0}可以 决定一个非时齐的 Markov链ξn,满足: P(50=1)=H1,P(5m1=f|5n=D)=Pan) 假定时刻n系统处在状态i时,采取行动an得到的报酬由报酬函数gn(i,a)表示,那么在时 刻m得到的累计报酬为∑g(nan),其中gn(a)是在时刻n采取行动a且处在状态i 时的报酬函数,那么,平均累计报酬为E∑gn(n,an) 定义16.4(决策动作仅依赖系统当前的状态的情形时的期望总报酬) 这也是一种简单情形,例16.3是它的特例.这时容许a的取值依赖于链所处 的状态i的情形,即an=∫n(i)的情形,其中∫是状态集S到动作集的A的一个映射,其 含义为:若 Markov链在时刻n处于状态i,则采取决策an=Jn(i).令 Pn=(Pi, (n(jsN (16.1) 则它仍是一个随机矩阵.由初始分布μ及Pn,n≥0}决定了一个非时齐 Markov链n类似 地由报酬函数g(a)可以得到时刻m的平均累计报酬.此 Markov链5n在各个时刻的转移
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 在各个时刻的转移
矩阵是不同的,它们依赖初始分布μ及各个时刻的策略映射序列{f”,n≥0}·我们记 f={n,0≤n≤m} (16.2) 并称它为一个策略,于是,使用它得到的平均累计报酬为En∑g(5n()注意,对 于非时齐的 Markov链n的轨道(50,…,n}而言,我们采取的行动列为 J后(50)…,fn(m).由于我们的行动列只依赖于 Markov链当前所处的状态,这样的特殊 策略f={n=fn(*)0≤n≤m}也称为 Markov策略,这时动作an=fn(n)是随机的.在 Markov链的初分布为μo时,我们将f在时刻m取得的平均累计报酬记为J(μo,f) (,f)=E|∑gn(5n,f5,) 在系统的初始状态为i时,平均累计报酬为J(i,f)=E∑gn(n,f(5n)·(有时在 总报酬中,除了累计报酬外,还要加上一个终止报酬h(m),此时 (Ho,f)=ER 2g,(5n,//(5n )+h(5m) 而其数学处理是完全一样的) [注]以上考虑的是纯策略,更为灵活的是使用混合策略,也就是随机策略,它以给定的概率分 配取动作集A中的不同动作,抽象地可以看成一个取值于A的概率向量(概率分布)μ.这时的动作集A 就用取值于A的全体概率向量组成的集合(记成∏I)所代替.注意,我们可以认为Ac∏,因为纯策略 是一个特殊的随机策略.在随机策略类∏中考虑累计报酬,其每一步计算都应作相应的改变.在使用随机 策略时的最佳报酬函数相应地为。m(),其中 m()=sp,E|∑g5 而丌=(兀0,兀1…)兀n表示时刻n使用的随机策略.可以证明,当gn(i,a)=g(,a)(不依赖n)时 Vn关于k满足一个 Bellman型向后递推公式 Vk.m()=sup s , [g(i, a)+2Pu(a)Vk+m()]
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 = Î =
再取f厂m1使时刻m-1的报酬函数达到最大,即 8m(fm1()+∑P(m(O)gm()= maxell 8m-(,a)+∑ Ay, (a)g(I=8m-O) 然后,向后递推地取fk(1)使时刻k的报酬函数达到最大,即 g(,f()+∑P()g(= manas[gk(,a)+∑p(a)g((=g() 这样就得到了f={∫,…,∫m1,∫m}.现在证明它是最佳的 Markov策略.对于任意 Markov策略f=(fn,0≤n≤m),定义辅助 Markov策略f)={/f0;…,∫,∫1,…,fm}.用 后向数学归纳法可以直接验证以下不等式 J(μ0,f)≤J(μ0,f)(k≤m) 取k=0即得J(μo,f)≤J(μo,f).请读者自己补上这段验证 [注1]以上寻找f的方法,在计算机上实现十分简单.问题在于当行动集A较大 的时候,计算量会非常大,甚至难以在允许的时间内完成。于是代之以用E-最佳 Markov 策略. [注2]本定理可以推广到状态集S是为可数集,行动集A是紧集,而报酬函数 gn(,a)是有界连续函数情形 [注3]在状态集与动作集较为一般的时候,为了保证最佳策略的存在,纯策略类 就不够,必须考虑用随机策略类. 2.3无穷时段下的总报酬情形(m=∞的情形) 定理16.9如果报酬函数序列满足以下的衰减性质 ∑sp|gn(,a)|<∝ (16.7) 那么存在最佳 Markov策略f,(可以利用有限近似证明) 例16.1◎(折扣模型)在应用中常见例子为折扣报酬模型,即 8(i,a)=r"go(, a) 的情形,其中0<r<1是折扣因子,此时只要g0(,a)是有界函数,则条件(16.7)满足 定义16.11(平稳策略)如果 Marko策略f=(fn,n≥0)对于任意n满足 ∫n=f,则称为平稳 Markov策略 45
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 策略．
定理16.12对于折扣报酬模型,最佳 Markov策略(如果存在)是平稳 Markov 策略 证明记平均累计报酬为 J(,f)=∑r"Bg0(5n,an) 假定最佳 Markov策略是f=(f,n≥0).令 ={f6,…,f0,f,f2}(共k个f) 那么,用归纳法可以证明 J(i, f)=J(i J(,f0)=J(i,f') 令n→∞,便得J(i,f()=J(i,f’).这说明平稳 Markov策略f()=(f0,f…)是一个 最优 Markov策略. 利用不动点理论还可以证明:对折扣报酬模型,若状态集S可数,行动集A是紧集, 且go(,a)有界,则平稳 Markov策略f是最佳策略的充要条件是,它满足下述 Be l iman方 程(动态规划方程): J(,f)=- maxed[8(a)+r∑P2a)J(j,f,(vi∈S.(16·8) 由此可知J(,f)是下述非线性变换J→T(J)的唯一不动点(即J(.,f)满足方程 (J)=J): 7(/)(0)= maxed[g(a)+r∑pn(a)7(J)],(i∈S) 这个结论的优点在于:定理中的m可用∞代替(即近似),后者显然更为简单,因为它的最 佳策略是平稳 Markov策略,而且只要求出变换T的不动点(即T(J)=J的解J(.),再令 即可,其中a是[g0(a)+r∑P2(a)7(X)达到最大值的动作,这样的计算将大大 地减少机耗时间.有时对于充分大的m,可以用Tm()来近似J(.),此处是恒同映射, 而Tm=T°…°T为映射T的m次复合 [注5]以上是以平均累计报酬作为目标函数的.它是按期望准则取最优,还可以按矩准则取最优, 按样本路径平均取最优,后者的报酬是一个随机变量:记时刻m前的累计报酬为Vm(0,f),其中l为系 46
446 定理１６.１２ 对于折扣报酬模型, 最佳 Markov 策略（如果存在）是平稳 Markov 策略． 证明 记平均累计报酬为 J (i ,f)= ( , ) 0 0 n n n n å r Eg x a ¥ = . 假定最佳 Markov 策略是 f * =( , * n f n≥0). 令 f (k ) { , , , , , } * 2 * 1 * 0 * f 0 L f f f L D = (共k 个 * 0 f ). 那么, 用归纳法可以证明 J (i ,f (n) )= J (i ,f (n -1) )= L= J (i ,f (0) )= J (i ,f * ). 令n ® ¥，便得 J (i ,f (¥) )= J (i ,f * ). 这说明平稳 Markov 策略 f (¥) ( , , ) * 0 * f 0 f L D = 是一个 最优 Markov 策略． 】 利用不动点理论还可以证明：对折扣报酬模型, 若状态集 S 可数， 行动集 A 是紧集， 且 ( , ) g0 i a 有界，则平稳 Markov 策略 f 是最佳策略的充要条件是，它满足下述 Bellman 方 程(动态规划方程)： J (i ,f)=max aÎA [ ( , ) g0 i a + å j ij r p (a) J ( j ,f)], ("i Î S) . （１６．８） 由此可知 J(.,f)是下述非线性变换 J ® T (J ) 的唯一不动点 (即 J ( .,f)满足方程 T (J ) = J )： T ( J ) D (i) = max aÎA [ ( , ) g0 i a + å j ij r p (a) T ( J )( j) ], ("i Î S) . 这个结论的优点在于: 定理中的m 可用∞代替（即近似），后者显然更为简单, 因为它的最 佳策略是平稳 Markov 策略，而且只要求出变换T 的不动点(即T (J ) = J 的解 J ( .)), 再令 * f (i) a D = 即可, 其中 * a 是 [ ( , ) g0 i a + å j ij r p (a) T ( J )( j) ]达到最大值的动作. 这样的计算将大大 地减少机耗时间．有时对于充分大的m , 可以用T (I ) m 来近似 J ( .), 此处 I 是恒同映射， 而Tm T oLo T D = 为映射T 的m 次复合． [注 5] 以上是以平均累计报酬作为目标函数的．它是按期望准则取最优，还可以按矩准则取最优, 按样本路径平均取最优, 后者的报酬是一个随机变量：记时刻m 前的累计报酬为 ( , 0 V i m f ) , 其中 0 i 为系
统的初始状态.作平均报酬序列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 时的动作集为
A1=0,x在这模型中,相应于转移矩阵P(a)=(Pna)a∈A1)的是转移核p(xya) (a∈A).如果采用策略f=(fn,an=fn(5n),则在时刻m的平均累计报酬为 J(x,f)=E∑(5n-f(5n),其中50=x0(也可以是随机的,0≤f(x)≤x 最佳投资组合假定只有两种证券,无风险的证券(例如存银行,其利率为尸)及有风险的 股票.设财产5n中投资于股票的比例为an,(0≤an≤1),且以数量Cn消费.此时状态空间为 S=[0,∞),当状态确定为x时的动作集为A2=[0.】×[0,x],即 a=(a,c),(0≤a≤10≤c≤x) 于是状态发展为 Enl=[(1+r1-a,)+anI(5, -Cn) 其中ηn是股票的价值.典型的报酬函数是g(x,(a,C)=l(C),它代表由消费带来的"乐趣",在经济 学中称为由消费C产生的效用函数.如果假定切n}为独立同分布,则{2n}正是与前面类似的模型但 是,用独立同分布的随机变量来描述股票的误差较大.如果用 black- Scholes模型的离散采样描述股票,虽 然较为合理,但是这会使模型变得复杂 (3)存储问题讨论时刻n时商店中某种货品的存储量5n设进货量为an,假定市场需求为独 立同分布的随机变量序列Tn·又设商店对此货品划定了最大容许库存量C.那么,状态空间 S=[-∞,C](在n<0时表示缺货),在状态(库存)为x时的动作集为A2=[O,c-x],而 5n+I=5n+a-n 此时报酬函数依赖于市场需求.假定单个货品的卖价为s,进货价为d,存储消耗价为h,那么 时刻n的报酬为 g m,a,, n)=s(min( 5n+a,, n)-da -h(+a,) 由此可以考虑最大化报酬. [注8]还可以考虑时间连续的情形,这就是可控 Markov过程.这类问题较为复杂,在概率论中 涉及最佳停时,而在求解最佳策略时,常用偏微分方程中的活动边界理论或变分不等式 48
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 过程． 这类问题较为复杂, 在概率论中 涉及最佳停时, 而在求解最佳策略时, 常用偏微分方程中的活动边界理论或变分不等式．
