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

龚光鲁,钱敏平著应用随机过程教程一与在算法和智能计算中的应用 清华大学出版社,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 , (3, ) 2 19 ( 3) (3, ) 6 (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