439
龚光鲁,钱敏平著 应用随机过程教程 – 与在算法和智能计算中的应用
清华大学出版社,2003
第 16 章 离散状态的 Markov控制与决策过程简介
(Controlled Markov Process,Markov Decision Process,MDP)
1 例
1,1 随机决策模型的简单例子
定义 １６,１ 随机决策 模型的对象是可以控制的随机系统,人们可以选取控制决策,
以改变发展过程的路径,在任意固定时刻,系统随机地处在 },,2,1{ NS L= 中的某个状态,
而在策略取定为 a 的情况下系统的发展是按照一个随机矩阵 P )(a 作为转移概率阵而变化,
这就称为一个 Markov 决策过程,
从下面的简单例子,可以得到一些直观的认识 。
例 １６,２ 设某个经营系统总处在 "1","2","3" 三种状态之一,假定在每个整值时刻可选择两种不同的动作之一,）（ 1a 或 ）（ 2a,而在采取动作 ）（ 1a 或 ）（ 2a 时,状态间的转移矩阵分别为
P ( )1(a )=
2
10
2
1 2
1
2
10
02121
,P ( )2(a )=
2
1
2
10
02121
2
10
2
1
,
假定开始时 （ 即时间 0=n 时 ） 该系统以相等的可能性处在这三个状态之一,即初始分布为
31,31,31,又设处在状态 i 时,采取 动作 )1(a 能得到报酬为 iaig 2),( )1( =,而处在状态 i 时,
采取 动作 )2(a 能得到报酬为 21),( 2)2( += iaig,我们要在各个时刻,根据历史状况,有目的地选取动作 )1(a 或 )2(a,使在时间区段 mn ≤≤0 内得到的平均累积报酬最大,这里,动作是历史状况的函数,从 时刻 n 的历史状况到 采取的动作 的对应 （ 即函数 ）,称为时刻 n 采取的策略,各个时刻 采取 的 策略 合起来,称为 一个 策略,我们要选取一个 策略,使在时间区段
mn ≤≤0 内 得到 的平均累积报酬最大,
把在时刻 n 采取的动作记为 na,那么它只能 )1(a 或 )2(a 之一,于是 转移矩阵
P ( na ) Njinij ap ≤=,))(( 有确切的含义,这样,由初始分布 0m =( m 1,m 2,m 3 )=( 31,31,31 )
及转移矩阵列 { P ( na )} 决定了一个 3 个状态的非时齐的 Markov 链 }0:{ ≥nnx,nx 代表系
440
统在时刻 n 所处的 ( 随机的 ) 状态,于是 系统在时刻 m 前所得的平均累积报酬为
)),((
0
∑
=
m
n
nn agE x,它就是需要 优化 的目标函数,
动作 na 的选取,直接影响了在时刻 n 以 后 此 Markov 链的 样本 的 走向 ),,{ 1 mn xx L+,
一般地,动作 na 依赖于系统的发展历史,即依赖于 },,,,,,,{ 111100 nnn aaa xxxxL,这里我们简单地限制在时刻 n 所采取的动作只依赖于当时所处的状态,也就是 假定 na 只是 nx 的函数,即 )( nnn fa x= ( 其中 nf,},{}3,2,1{ )2()1( aa→,是根据所处的状态选取的动作,即在时刻 n 所采取的策略 ),我们 先 以 1=m 为例,看如何求得最高的平均累积报酬,也就是让 )( 000 xfa =,)( 111 xfa =,要选取函数 ( 映射 ) 10,ff,使
))(,())(,(),( 11100010 xxxx fEgfEgffV +=?
取到最大值,注意
∑
=
=
3
1
0000 ))(,())(,(
i
iifigfEg mxx,
而采取了动作 ))(( 000 xfa = 后,非时齐 的 Markov 链 nx 从时刻 0 到时刻 1 的转移矩阵应该是
P ))(( 00 xf,于是
))(()( 0
3
1
1 ifpjP iji
i
mx ∑
=
==,
从而
∑
=
==
3
1
11111 )())(,())(,(
j
jPjfjgfEg xxx
))(())(,(
3
1
01
3
1
∑∑
= =
=
j
iji
i
ifpjfjgm,
也就是
=),( 10 ffV +∑
=
3
1
0 ))(,(
i
iifig m ∑∑
= =
3
1
01
3
1
))(())(,(
j
iji
i
ifpjfjgm,
由 此式看出,若要选取 策 略 ）（ 10,ff 使 ),( 10 ffV 的值为最大,需先选取 1f 使 ))(,( 1 jfjg 最大,对 此我们 观察到
),1(232),1()1( )2()1( agagj =>==,
441
),2(294),2()2( )2()1( agagj =<==,
),3(2196),3()3( )2()1( agagj =>==,
可见,要使 ))(,( 1 jfjg 最大,1f 应取如下定义的 *1f,
),,()3,2,1(,)()2()1(*1 １aaaf →,
将 在确定了 *11 ff = 后的最大报酬 记 为 *g,那么
=
=
=
==
)3(6
)2(29
)1(2
))(,()( *1*
j
j
j
jfjgjg
于是
))](()())(,([),( 0*
3
1
0
3
1
*
10 ifpjgifigffV ij
j
i
i
∑∑
==
+= m,
剩下的就是选取 0f,使 ),( *10 ffV ) 最大,为此只需使方括号中的各个量都取到最大,与前面不同 之 处,只 是 用方括号中量代替了前面的 ))(,( 1 jfjg 而已,下面我们列出它的值,由
)( )1(apij 与 )( )2(apij 的定义得
)296(21219)2192(2163
)229(2129)21929(2142
)62(2123)292(2121
)()(),()()(),(
3
1
)2(
*
)2(
3
1
)1(
*
)1(
++++=
++++=
++++=
++ ∑∑
==
i
i
i
apjgaigapjgaig
j
ij
j
ij
,
比较其各行的大小,可知 0f 应取 策略 *0f,
),,()3,2,1(,)2))1()2(*0 aaaf →,
其对应的值 ( 最大值 ) 分别为,211,11,459,所 以
12
125)
4
5911
2
11(
3
1),( *
1
*
0 =++=ffV,
于是在我们所限制的策略类之中,最佳 决策 为由如上定义的 ),( *1*0 ff 所确定的
)( 0*00 xfa =,)( 1*11 xfa =,
442
而在 1≤n 时段内的最高平均累积报酬为 12125),( *1*0 =ffV,
1,2 简单模型的启示
由 例 １６,２ 可以看出,如果限制在形如 )( nnn fa x= 的策 略 类中,去找最佳的策略
( 即,从状态到动作的对应 " nf,那么,只要先选定时刻最 后 的 m 时刻 所对应最佳的 *mf,
然后向后归纳地选最佳的 *0* 1,,ff m L?,由 此可以 抽象出 第 2 节 中较为一般的数学模型,
2 动作只依赖当前所处状态的简单决策模型
2,1 简单模型的一般描述
定义 １６,３ （ 决策动作不依赖系统的状态的情形 ）
假定 在 参数 a （ a ∈ 某个有限集 A,称为 行动集 ） 固定时,Ｐ ( a ) Njiij ap ≤=,))(( 是一个以 }21{ NS,，,L= 为状态 空间 的转移矩阵,设在时刻 0,1,..,各选一个行动,记为
)(,,10 Aaaa i ∈L,那么由初分布 0m ),,( 1 Nmm L= 及 转移矩阵序列 { P ( na ):n ≥ 0} 可以决定一个非时齐的 Markov 链 nx,满足,
iiP mx == )( 0,)()|( 1 nijnn apijP ===+ xx,
假定 时刻 n 系统处在状态 i 时,采取行动 na 得到的报酬由报酬函数 ),( aig n 表示,那么 在时刻 m 得到 的累计报酬为 ∑
=
m
n
nnn ag
0
),(x,其中 ),( aig n 是 在时刻 n 采取行动 a 且 处在状态 i
时的报酬函数,那么,平均 累计 报酬为 ]),([
0
∑
=
m
n
nnn agE x,
定义 １６,４ （ 决策动作仅依赖系统当前的状态的情形时的期望总报酬 ）
这 也 是 一种简单情形,例 １６,３ 是 它的特例,这时 容许 na 的取值依赖于链所处的状态 i 的情形,即 )(ifa nn = 的情形,其中 nf 是 状态集 S 到动作集 的 A的 一个映射,其含义为,若 Markov 链在时刻 n 处于状态 i,则采取决策 )(ifa nn =,令
P Njinijn ifp ≤=,))(((,（ １６,１ ）
则它仍是一个随机 矩阵,由初 始 分布 0m 及 { P n,n ≥ 0} 决定了一个非时齐 Markov 链 nx,类似地由报酬函数 ),( aig 可以得到时刻 m 的平均 累计 报酬,此 Markov 链 nx 在各个时刻的转移
443
矩阵是不同的,它们 依赖初 始 分布 0m 及 各个时刻的 策略 映射 序 列 }0{ ≥nf n,,我们记
f }0,{ mnfn ≤≤=D,（ １６,２ ）
并称它为一个 策 略,于是,使用它得到 的平均 累计 报酬为 ０mE?
∑
=
m
n
nnn fg
0
)(,( xx,注意,对于 非时齐的 Markov 链 nx 的轨道 }10 mxxx,，，（ L 而言,我们采 取的行动列为
))(,),({ 00 mmff xx L,由于 我们 的行动列只依赖于 Markov 链当前所处的状态,这样的特殊策略 f }0),({ mnff nn ≤≤?==? 也称为 Markov 策略,这时 动作 )( nnn fa x= 是随机的,在
Markov 链的 初分布 为 0m 时,我们将 f 在时刻 m 取得的平均累计报酬记 为 (J 0m,f ),
(J 0m,f ) = ０mE?
∑
=
m
n
nnn fg
0
))(,( xx,（ １６,３ ）
在系统的初始状态为 i 时,平均累计报酬为 (J i,f ) =?
∑
=
m
n
nnni fgE
0
))(,( xx,( 有时在总报酬中,除了 累计报酬外,还要加上一个终止报酬 )( mh x,此时
(J 0m,f ) = ０mE?
+∑
=
m
n
nnnn hfg
0
)()(,( xxx,
而其数学处理是完全一样的 ),
[ 注 1] 以上考虑的 是 纯策略,更为灵活的是 使用 混合策略,也就是 随机策略,它以给定 的 概率 分配 取动作集 A中的不同动作,抽象地可以看成一 个 取值 于 A的概率向量 ( 概率分布 ) m,这时 的 动作集 A
就用取值 于 A的全体概率向量组成的集合 ( 记成 P ) 所代替,注意,我们可以认为 P?A,因为纯策略是一个特殊的随机策略,在随机策略类 P 中考虑累计报酬,其每 一步计算都应作相应的改变,在使用随机策略时的最佳报酬函数相应地为 )(,0?mV,其中
=)(,iV mk psup?
∑
=
m
kn
nnni gE ),( px,（ １６,４ ）
而 npppp ),,,( 10 L= 表示时刻 n 使用的随机策略,可以证明,当 ),(),( aigaig n = ( 不依赖 n ) 时,
nkV,关于 k 满足一个 Bellman 型向后递推公式
0)(
)]()(),([sup)(
,
,1
1
,
=
+= +
=
∈ ∑
iV
jVapaigiV
mm
mkij
N
j
Aamk,
444
由此可以 反向地逐步 解出在随机策略下的最佳报酬函数,显见,它不小于在纯策略下的最佳报酬函数,
在其它的情形,例如下面将介绍的折扣模型的情形,实际上只 须 沿着这个思路方向,做 相应的改变就也 就 可以得到最佳报酬函数,在历史发展给定条件下,随机策略的条件分布如果只与系统的当前状态有关,
则这样的随机策略 称为 Markov 随机策略,如果只与系统的初始状态与当前状态有关,则称为 半 Markov 随机策略,
[ 注 2] 在实际情形中,更多出现的是复杂的情形,即对不同的状态可 采取 的动作集 也 不同,就是说,如果 系统处在状态 i,则能选取的动作集合为 iA,于是这时相应地要求
n
Af nn xx ∈)(,为了使读者领会实质,在本书中我们只 讨论 iA 们相同的简 单情形,其实其方法与理论并无二致,
[ 注 3] 以上考虑的是 Markov 策略,即当前时刻所采取的动作只依赖于当前所处的状态的简单情形,一般如果采取的动作依赖于 Markov 链的历史,那就复杂多了,但是在实际问题中,出现更多的是只依赖当前 所 处的状态的情形,或者近似是这种情形,作为 个别情形,也 需要考虑依赖最近两个或多个时间的历史资料的情形,此时原则上可以通过扩大状态空间维数的方法,化为 Markov 策略的情形,
定义 １６,５ （ 最佳策 略 ） Markov 随机决策的基本问题是,寻找最优 平均累计 报酬 sup f (J 0m,f ) 及最佳马氏策略 f *,使 平均累计报酬
(J 0m,f * ) sup= f (J 0m,f ),（ １６,５ ）
这里 Sup 取遍所有的 Markov 策略,这样的 f * 如果存在,则称为 最佳 Markov 策略,
在实际问题中,有时即使最佳 Markov 策略存在,但却因为计算量过大或计算时间过长而变得实际上不可能,而?e 最佳 Markov 策略常比最佳 Markov 策略更为实际可行,
定义 １６,６ （?e 最佳 Markov 策略 ） f e 称为一个?e 最佳 Markov 策略,如果
(J 0m,f e ) sup> f (J 0m,f ) e?,（ １６,６ ）
[ 注 ] 在求最佳 Markov 策略的计算复杂度为非多项式时,求?e 最佳马氏策略常常能使计算降为多项式复杂度,可见花费这个 e 的代价,能带来极大的收益,
定义 １６,７ 如果 对于任意 n,na 也 不依赖于 nx,但是,是 随机的,即 它 是 与
Markov 链的发展无关的 " 常 随机 " 行动,nna h= ( nh 是 取值于 A的 随机变量 ),这种策略记为 a },{ mnn ≤= h,称为 独立 的 随机策略,
2,2 有限时段总报酬准则下的最佳 Markov 策 略 的构造
定理 １６,８ 在所有的 Markov 策略类中存在最佳 Markov 策 略 ( 但未必唯一 ),
证明 证明 的 过程实际上就是寻找一个最佳 Markov 策略的具体方法,要在 Markov 策略 类 中构造一个最佳的,而构造最佳 Markov 策略 f * 的方法则完全和例 １６,１ 一样,
首先 取 )(* if m
))()(,(max))(,( ** igaigifig mmAamm?∈ ==,
445
再取 * 1?mf 使时刻 1?m 的报酬函数达到最大,即
))(()]()(),([max)())(())(,( * 1
1
*
11
1
**
1
*
11 igjgapaigjgifpifig m
N
j
mijmAa
N
j
mmijmm?
=
∈
=
=+=+ ∑∑
然后,向后递推地取 )(* if k 使 时刻 k 的报酬函数达到最大,即
))(()]()(),([max)())(())(,( *
1
*
1
*
1
** igjgapaigjgifpifig
k
N
j
kijkAa
N
j
kkijkk
=
∈
=
+ =+=+ ∑∑,
这样就得到了 f },,,{ ** 1*0* mm fff?= L,现在 证明它是最佳的 Markov 策略,对于任意
Markov 策略 f =( nf,0 ≤ n ≤ m),定义辅助 Markov 策略 f )(k },,,,,{ ** 10 mkk ffff LL +?=,用后向数学归纳法可以直接验证以下不等式
(J 0m,f ) ≤ (J 0m,f ))(k (k ≤ m),
取 k=0 即得 (J 0m,f ) ≤ (J 0m,f )*,请读者自己补上这段验证,
[ 注 1] 以上寻找 f * 的方法,在计算机上实现十分简单,问题在于当行动集 A较大的时候,计算量会非常大,甚至难以在允许的时间内完成 。 于是 代之以用?e 最佳 Markov
策略,
[ 注 2] 本定理可以推广到状态集 S 是 为可数集,行动集 A 是 紧集,而报酬函数
),( aig n 是 有界连续函数情形,
[ 注 3] 在状态集与 动作 集较为一般的时候,为了保证最佳策略的存在,纯策略类就不够,必须考虑 用随机策略类,
2,3 无穷时段下的总报酬情形 ( ∞=m 的情形 )
定理 １６,９ 如果 报酬函数序列满足以下的衰减性质
∞<∑
∞
=0
,|),(|sup
n
nai aig,（ １６,７ ）
那么 存在最佳 Markov 策略 f *,（ 可以 利用有限近似证明 ）,
例 １６,１０ （ 折扣模型 ） 在应用中 常见例子 为 折扣报酬模型,即
),(),( 0 aigraig nn =
的情形,其中 10 << r 是 折扣因子,此时 只要 ),(0 aig 是有界函数,则 条件 (16.7) 满足,
定义 １６,１１ （ 平稳策略 ） 如果 Markov 策略 f =(,nf n ≥ 0) 对于任意 n 满足
0ff n =,则称为 平稳 Markov 策略,
446
定理 １６,１２ 对于折扣报酬模型,最佳 Markov 策略 （ 如果存在 ） 是平稳 Markov
策略,
证明 记 平均 累计报酬为
iJ (,f )= ),(0
0
nn
n
n
aEgr x∑
∞
=
,
假定 最佳 Markov 策略 是 f * =(,*nf n ≥ 0),令
f )(k },,,,,{ *2*1*0*0 LL ffff?= ( 共 k 个 *0f ),
那么,用归纳法可以证明
iJ (,f )(n )= iJ (,f )1(?n ) == L iJ (,f )0( )= iJ (,f * ),
令 ∞→n,便得 iJ (,f )(∞ )= iJ (,f * ),这说明平稳 Markov 策略 f )(∞ ),,( *0*0 Lff?= 是一个最优 Markov 策略,】
利用不动点理论还可以证明,对折扣报酬模型,若状态集 S 可 数,行动集 A是 紧集,
且 ),(0 aig 有界,则平稳 Markov 策略 f 是最佳策略的充要条件是,它满足下述 Bellman 方程 ( 动态规划方程 ),
iJ (,f )=max Aa∈ [ ),(0 aig + ∑
j
ij apr )( (J j,f )],)( Si ∈?,（ １６,８ ）
由此可知 J(.,f ) 是下述非线性变换 )(JTJ → 的唯一不动点 ( 即 (J,,f ) 满足方程
JJT =)( ),
)( JT?=)(i m ax Aa∈ [ ),(0 aig + ∑
j
ij apr )( ))(( jJT ],)( Si ∈?,
这个结论的优点在于,定理中的 m 可用 ∞ 代替 （ 即近似 ）,后者显然更为简单,因为它的最佳策略是平稳 Markov 策略,而且只要求出变换 T 的不动点 ( 即 JJT =)( 的解 (J,)),再令
*)( aif?=
即可,其中 *a 是 [ ),(0 aig + ∑
j
ij apr )( ))(( jJT ] 达到最大值的动作,这样的计算将大大地减少机耗时间,有时对于充分大的 m,可以用 )(ITm 来近似 (J,),此处 I 是恒同映射,
而 TTTm oLo?= 为映射 T 的 m 次复合,
[ 注 5 ] 以上是以 平均 累计报酬作为目标函数的,它是按期望准则取最优,还可以按矩准则取最优,
按样本路径平均取最优,后者的报酬 是 一个随机变量,记时刻 m 前的累计报酬为,( 0iVm f ),其中 0i 为系
447
统的初始状态,作平均报酬序列,( 0iJ N f ∑
=
+=
N
mN 01
1),(
0iVm f ),一般,( 0iJ N f ) 的极限未必存在,
所以 常 取其收敛子序列中极限的最大者,记为,( 0iJ f ),或极限中的最小者,记为,( 0iJ f ),用它们作为目标函数,前者是以乐观的态度看待报酬,而后者是以悲观的态度看待报酬,在使用随机策略时,相应地记为,( 0iJ p ),其中 npppp ),,,( 10 L= 表示时刻 n 使用的随机策略,而把
0(iJ ),(sup) 0 pp iJ
=
作为最佳函数,这种 平均准则常见于发展较为平稳的系统,例如通讯网络,而累计总报酬准则,则常见于较快变化的系统,例如金融系统,轨道 平均报酬准则的数学处理,通常比 平均累计总报酬准则情形要复杂,
[ 注 ６ ] 最 一般的模型 是 策略的动作依赖历史情况的策略,设 S 与 A仍都为有限集,又设随机变量列 }{ nx 满足
x(P |1 jn =+ x ),,,1100 nn iii === xx L )(,nji ap
n
=,
其中 na 由下式递推地确定,
)( 000 ifa =,
...,
),,,,,,,( 111100 nnnnn iaiaiaifa= L,
这时的 }{ nx 不再是 Markov 链,因为它依赖于所有的过去 历史,而且此时 na 是一个依赖于 },,{ 0 nxx L
的随机变量,如果我们仍记 f =(,nf n ≥ 0),并称 之 为一个策略,那么对 此 模型也可类似地定义最佳策略 及最佳?e 策略,事实上,对 此 模型可以证明,在很宽的条件下,定理 １６,８ 中的最佳 Markov 策略也是这里的 策略类中的 最佳策略,也就 是最佳 Markov 策略在以上定义的非马氏策略类中仍是 最佳的,这就可以把搜索最佳策略的策略类 的范围 大大地缩小了,
[ 注 ７ ] 在 常见的实际模型中,有一类状态空间 S 是一个区间 ( 端点可以为 ∞ ),动作集 xAA =
是依赖状态 x 的一个有限区间,例如
(1) Ricker 模型 ( 合理捕 鱼问题 ) 设在时刻 n 湖中鱼的总量为 nx,捕鱼的原则是,在 有计划地留下数量 ( 随机的 ) na 的鱼用以繁殖 的前题下,求最大捕鱼量,假定鱼的数目与留下的数量受 群体控制 的
Ricker 模型所 制约,
nn ac
nn eac
2
11
+ =
hx,
其中 21,cc 为常数,}{ nh 是 独立同分布随机变量列,于是捕鱼量为 nnnn aag?=
xx ),( 中的
axaxg n?=),( 与 n 无关,这时状态空间为 ),0[ ∞=S,当状态确定为 x 时的动作集为
448
],0[ xAx =,在这模型中,相应于转移矩阵 P )),(()( iij Aaapa ∈= 的 是 转移核 );,( ayxp
）（ xAa ∈,如果采用策略 f ))(,( nnnn faf x==,则在时刻 m 的 平均累计报酬为
,( 0xJ f ))](([)
0
0 nn
m
n
x fE xx?= ∑
=
,其中 00 x=x ( 也可以是随机的 ),xxf n ≤≤ )(0,
(2) 最佳投资组合 假定只有两种证券,无风险的证券 ( 例如存银行,其利率为 r ) 及有风险的股票,设财产 nx 中投资于 股票的比例为 )10(,≤≤ nn aa,且以数量 nc 消费,此时 状态空间为
),0[ ∞=S,当状态确定为 x 时的动作集为 ],0[]1,0[ xAx ×=,即
)0,10(),,( xcca ≤≤≤≤= aa,
于是状态发展为
)]()1)(1[(1 nnnnnn cr?+?+=+ xhaax,
其中 nh 是股票的价值,典型的报酬函数 是 )()),(,( cucxg =a,它 代表由消费带来的,乐趣,,在经济学中称为由消费 c 产生的 效用函数,如果假定 }{ nh 为独立同分布,则 }{ nx 正是与前面类似的模型,但是,用独立同分布的随机变量来描述股票 的 误 差较 大,如果用 Black - Scholes 模型的离散采样描述股票,虽然较为合理,但是这 会 使模型 变得 复杂,
(3) 存储问题 讨论时刻 n 时商店中某种货品的存储量 nx,设进货量为 na,假定市场需求为独立同分布的 随机变量序列 nh,又设商店对此货品划定了最大容许库存量 c,那么,状态空间
],[ cS?∞= ( 在 0<nx 时表示缺货 ),在状态 ( 库存 ) 为 x 时的动作集为 ],0[ xcAx?=,而
nnnn a hxx?+=+1,
此时报酬函数依赖于 市场需求,假定单个货品的卖价为 s,进货价为 d,存储消耗价为 h,那么
时刻 n 的报酬为
)(),(min(),,( nnnnnnnnnn ahdaasag ++= xhxhx,
由此可以考虑最大化报酬,
[ 注 ８ ] 还可 以考虑时间 连续的情形,这就是可控 Markov 过程,这类问题较为复杂,在概率论中涉及最佳停时,而 在求解最佳策略时,常用偏微分方程中的活动边界理论 或变分不等式,
龚光鲁,钱敏平著 应用随机过程教程 – 与在算法和智能计算中的应用
清华大学出版社,2003
第 16 章 离散状态的 Markov控制与决策过程简介
(Controlled Markov Process,Markov Decision Process,MDP)
1 例
1,1 随机决策模型的简单例子
定义 １６,１ 随机决策 模型的对象是可以控制的随机系统,人们可以选取控制决策,
以改变发展过程的路径,在任意固定时刻,系统随机地处在 },,2,1{ NS L= 中的某个状态,
而在策略取定为 a 的情况下系统的发展是按照一个随机矩阵 P )(a 作为转移概率阵而变化,
这就称为一个 Markov 决策过程,
从下面的简单例子,可以得到一些直观的认识 。
例 １６,２ 设某个经营系统总处在 "1","2","3" 三种状态之一,假定在每个整值时刻可选择两种不同的动作之一,）（ 1a 或 ）（ 2a,而在采取动作 ）（ 1a 或 ）（ 2a 时,状态间的转移矩阵分别为
P ( )1(a )=
2
10
2
1 2
1
2
10
02121
,P ( )2(a )=
2
1
2
10
02121
2
10
2
1
,
假定开始时 （ 即时间 0=n 时 ） 该系统以相等的可能性处在这三个状态之一,即初始分布为
31,31,31,又设处在状态 i 时,采取 动作 )1(a 能得到报酬为 iaig 2),( )1( =,而处在状态 i 时,
采取 动作 )2(a 能得到报酬为 21),( 2)2( += iaig,我们要在各个时刻,根据历史状况,有目的地选取动作 )1(a 或 )2(a,使在时间区段 mn ≤≤0 内得到的平均累积报酬最大,这里,动作是历史状况的函数,从 时刻 n 的历史状况到 采取的动作 的对应 （ 即函数 ）,称为时刻 n 采取的策略,各个时刻 采取 的 策略 合起来,称为 一个 策略,我们要选取一个 策略,使在时间区段
mn ≤≤0 内 得到 的平均累积报酬最大,
把在时刻 n 采取的动作记为 na,那么它只能 )1(a 或 )2(a 之一,于是 转移矩阵
P ( na ) Njinij ap ≤=,))(( 有确切的含义,这样,由初始分布 0m =( m 1,m 2,m 3 )=( 31,31,31 )
及转移矩阵列 { P ( na )} 决定了一个 3 个状态的非时齐的 Markov 链 }0:{ ≥nnx,nx 代表系
440
统在时刻 n 所处的 ( 随机的 ) 状态,于是 系统在时刻 m 前所得的平均累积报酬为
)),((
0
∑
=
m
n
nn agE x,它就是需要 优化 的目标函数,
动作 na 的选取,直接影响了在时刻 n 以 后 此 Markov 链的 样本 的 走向 ),,{ 1 mn xx L+,
一般地,动作 na 依赖于系统的发展历史,即依赖于 },,,,,,,{ 111100 nnn aaa xxxxL,这里我们简单地限制在时刻 n 所采取的动作只依赖于当时所处的状态,也就是 假定 na 只是 nx 的函数,即 )( nnn fa x= ( 其中 nf,},{}3,2,1{ )2()1( aa→,是根据所处的状态选取的动作,即在时刻 n 所采取的策略 ),我们 先 以 1=m 为例,看如何求得最高的平均累积报酬,也就是让 )( 000 xfa =,)( 111 xfa =,要选取函数 ( 映射 ) 10,ff,使
))(,())(,(),( 11100010 xxxx fEgfEgffV +=?
取到最大值,注意
∑
=
=
3
1
0000 ))(,())(,(
i
iifigfEg mxx,
而采取了动作 ))(( 000 xfa = 后,非时齐 的 Markov 链 nx 从时刻 0 到时刻 1 的转移矩阵应该是
P ))(( 00 xf,于是
))(()( 0
3
1
1 ifpjP iji
i
mx ∑
=
==,
从而
∑
=
==
3
1
11111 )())(,())(,(
j
jPjfjgfEg xxx
))(())(,(
3
1
01
3
1
∑∑
= =
=
j
iji
i
ifpjfjgm,
也就是
=),( 10 ffV +∑
=
3
1
0 ))(,(
i
iifig m ∑∑
= =
3
1
01
3
1
))(())(,(
j
iji
i
ifpjfjgm,
由 此式看出,若要选取 策 略 ）（ 10,ff 使 ),( 10 ffV 的值为最大,需先选取 1f 使 ))(,( 1 jfjg 最大,对 此我们 观察到
),1(232),1()1( )2()1( agagj =>==,
441
),2(294),2()2( )2()1( agagj =<==,
),3(2196),3()3( )2()1( agagj =>==,
可见,要使 ))(,( 1 jfjg 最大,1f 应取如下定义的 *1f,
),,()3,2,1(,)()2()1(*1 １aaaf →,
将 在确定了 *11 ff = 后的最大报酬 记 为 *g,那么
=
=
=
==
)3(6
)2(29
)1(2
))(,()( *1*
j
j
j
jfjgjg
于是
))](()())(,([),( 0*
3
1
0
3
1
*
10 ifpjgifigffV ij
j
i
i
∑∑
==
+= m,
剩下的就是选取 0f,使 ),( *10 ffV ) 最大,为此只需使方括号中的各个量都取到最大,与前面不同 之 处,只 是 用方括号中量代替了前面的 ))(,( 1 jfjg 而已,下面我们列出它的值,由
)( )1(apij 与 )( )2(apij 的定义得
)296(21219)2192(2163
)229(2129)21929(2142
)62(2123)292(2121
)()(),()()(),(
3
1
)2(
*
)2(
3
1
)1(
*
)1(
++++=
++++=
++++=
++ ∑∑
==
i
i
i
apjgaigapjgaig
j
ij
j
ij
,
比较其各行的大小,可知 0f 应取 策略 *0f,
),,()3,2,1(,)2))1()2(*0 aaaf →,
其对应的值 ( 最大值 ) 分别为,211,11,459,所 以
12
125)
4
5911
2
11(
3
1),( *
1
*
0 =++=ffV,
于是在我们所限制的策略类之中,最佳 决策 为由如上定义的 ),( *1*0 ff 所确定的
)( 0*00 xfa =,)( 1*11 xfa =,
442
而在 1≤n 时段内的最高平均累积报酬为 12125),( *1*0 =ffV,
1,2 简单模型的启示
由 例 １６,２ 可以看出,如果限制在形如 )( nnn fa x= 的策 略 类中,去找最佳的策略
( 即,从状态到动作的对应 " nf,那么,只要先选定时刻最 后 的 m 时刻 所对应最佳的 *mf,
然后向后归纳地选最佳的 *0* 1,,ff m L?,由 此可以 抽象出 第 2 节 中较为一般的数学模型,
2 动作只依赖当前所处状态的简单决策模型
2,1 简单模型的一般描述
定义 １６,３ （ 决策动作不依赖系统的状态的情形 ）
假定 在 参数 a （ a ∈ 某个有限集 A,称为 行动集 ） 固定时,Ｐ ( a ) Njiij ap ≤=,))(( 是一个以 }21{ NS,，,L= 为状态 空间 的转移矩阵,设在时刻 0,1,..,各选一个行动,记为
)(,,10 Aaaa i ∈L,那么由初分布 0m ),,( 1 Nmm L= 及 转移矩阵序列 { P ( na ):n ≥ 0} 可以决定一个非时齐的 Markov 链 nx,满足,
iiP mx == )( 0,)()|( 1 nijnn apijP ===+ xx,
假定 时刻 n 系统处在状态 i 时,采取行动 na 得到的报酬由报酬函数 ),( aig n 表示,那么 在时刻 m 得到 的累计报酬为 ∑
=
m
n
nnn ag
0
),(x,其中 ),( aig n 是 在时刻 n 采取行动 a 且 处在状态 i
时的报酬函数,那么,平均 累计 报酬为 ]),([
0
∑
=
m
n
nnn agE x,
定义 １６,４ （ 决策动作仅依赖系统当前的状态的情形时的期望总报酬 ）
这 也 是 一种简单情形,例 １６,３ 是 它的特例,这时 容许 na 的取值依赖于链所处的状态 i 的情形,即 )(ifa nn = 的情形,其中 nf 是 状态集 S 到动作集 的 A的 一个映射,其含义为,若 Markov 链在时刻 n 处于状态 i,则采取决策 )(ifa nn =,令
P Njinijn ifp ≤=,))(((,（ １６,１ ）
则它仍是一个随机 矩阵,由初 始 分布 0m 及 { P n,n ≥ 0} 决定了一个非时齐 Markov 链 nx,类似地由报酬函数 ),( aig 可以得到时刻 m 的平均 累计 报酬,此 Markov 链 nx 在各个时刻的转移
443
矩阵是不同的,它们 依赖初 始 分布 0m 及 各个时刻的 策略 映射 序 列 }0{ ≥nf n,,我们记
f }0,{ mnfn ≤≤=D,（ １６,２ ）
并称它为一个 策 略,于是,使用它得到 的平均 累计 报酬为 ０mE?
∑
=
m
n
nnn fg
0
)(,( xx,注意,对于 非时齐的 Markov 链 nx 的轨道 }10 mxxx,，，（ L 而言,我们采 取的行动列为
))(,),({ 00 mmff xx L,由于 我们 的行动列只依赖于 Markov 链当前所处的状态,这样的特殊策略 f }0),({ mnff nn ≤≤?==? 也称为 Markov 策略,这时 动作 )( nnn fa x= 是随机的,在
Markov 链的 初分布 为 0m 时,我们将 f 在时刻 m 取得的平均累计报酬记 为 (J 0m,f ),
(J 0m,f ) = ０mE?
∑
=
m
n
nnn fg
0
))(,( xx,（ １６,３ ）
在系统的初始状态为 i 时,平均累计报酬为 (J i,f ) =?
∑
=
m
n
nnni fgE
0
))(,( xx,( 有时在总报酬中,除了 累计报酬外,还要加上一个终止报酬 )( mh x,此时
(J 0m,f ) = ０mE?
+∑
=
m
n
nnnn hfg
0
)()(,( xxx,
而其数学处理是完全一样的 ),
[ 注 1] 以上考虑的 是 纯策略,更为灵活的是 使用 混合策略,也就是 随机策略,它以给定 的 概率 分配 取动作集 A中的不同动作,抽象地可以看成一 个 取值 于 A的概率向量 ( 概率分布 ) m,这时 的 动作集 A
就用取值 于 A的全体概率向量组成的集合 ( 记成 P ) 所代替,注意,我们可以认为 P?A,因为纯策略是一个特殊的随机策略,在随机策略类 P 中考虑累计报酬,其每 一步计算都应作相应的改变,在使用随机策略时的最佳报酬函数相应地为 )(,0?mV,其中
=)(,iV mk psup?
∑
=
m
kn
nnni gE ),( px,（ １６,４ ）
而 npppp ),,,( 10 L= 表示时刻 n 使用的随机策略,可以证明,当 ),(),( aigaig n = ( 不依赖 n ) 时,
nkV,关于 k 满足一个 Bellman 型向后递推公式
0)(
)]()(),([sup)(
,
,1
1
,
=
+= +
=
∈ ∑
iV
jVapaigiV
mm
mkij
N
j
Aamk,
444
由此可以 反向地逐步 解出在随机策略下的最佳报酬函数,显见,它不小于在纯策略下的最佳报酬函数,
在其它的情形,例如下面将介绍的折扣模型的情形,实际上只 须 沿着这个思路方向,做 相应的改变就也 就 可以得到最佳报酬函数,在历史发展给定条件下,随机策略的条件分布如果只与系统的当前状态有关,
则这样的随机策略 称为 Markov 随机策略,如果只与系统的初始状态与当前状态有关,则称为 半 Markov 随机策略,
[ 注 2] 在实际情形中,更多出现的是复杂的情形,即对不同的状态可 采取 的动作集 也 不同,就是说,如果 系统处在状态 i,则能选取的动作集合为 iA,于是这时相应地要求
n
Af nn xx ∈)(,为了使读者领会实质,在本书中我们只 讨论 iA 们相同的简 单情形,其实其方法与理论并无二致,
[ 注 3] 以上考虑的是 Markov 策略,即当前时刻所采取的动作只依赖于当前所处的状态的简单情形,一般如果采取的动作依赖于 Markov 链的历史,那就复杂多了,但是在实际问题中,出现更多的是只依赖当前 所 处的状态的情形,或者近似是这种情形,作为 个别情形,也 需要考虑依赖最近两个或多个时间的历史资料的情形,此时原则上可以通过扩大状态空间维数的方法,化为 Markov 策略的情形,
定义 １６,５ （ 最佳策 略 ） Markov 随机决策的基本问题是,寻找最优 平均累计 报酬 sup f (J 0m,f ) 及最佳马氏策略 f *,使 平均累计报酬
(J 0m,f * ) sup= f (J 0m,f ),（ １６,５ ）
这里 Sup 取遍所有的 Markov 策略,这样的 f * 如果存在,则称为 最佳 Markov 策略,
在实际问题中,有时即使最佳 Markov 策略存在,但却因为计算量过大或计算时间过长而变得实际上不可能,而?e 最佳 Markov 策略常比最佳 Markov 策略更为实际可行,
定义 １６,６ （?e 最佳 Markov 策略 ） f e 称为一个?e 最佳 Markov 策略,如果
(J 0m,f e ) sup> f (J 0m,f ) e?,（ １６,６ ）
[ 注 ] 在求最佳 Markov 策略的计算复杂度为非多项式时,求?e 最佳马氏策略常常能使计算降为多项式复杂度,可见花费这个 e 的代价,能带来极大的收益,
定义 １６,７ 如果 对于任意 n,na 也 不依赖于 nx,但是,是 随机的,即 它 是 与
Markov 链的发展无关的 " 常 随机 " 行动,nna h= ( nh 是 取值于 A的 随机变量 ),这种策略记为 a },{ mnn ≤= h,称为 独立 的 随机策略,
2,2 有限时段总报酬准则下的最佳 Markov 策 略 的构造
定理 １６,８ 在所有的 Markov 策略类中存在最佳 Markov 策 略 ( 但未必唯一 ),
证明 证明 的 过程实际上就是寻找一个最佳 Markov 策略的具体方法,要在 Markov 策略 类 中构造一个最佳的,而构造最佳 Markov 策略 f * 的方法则完全和例 １６,１ 一样,
首先 取 )(* if m
))()(,(max))(,( ** igaigifig mmAamm?∈ ==,
445
再取 * 1?mf 使时刻 1?m 的报酬函数达到最大,即
))(()]()(),([max)())(())(,( * 1
1
*
11
1
**
1
*
11 igjgapaigjgifpifig m
N
j
mijmAa
N
j
mmijmm?
=
∈
=
=+=+ ∑∑
然后,向后递推地取 )(* if k 使 时刻 k 的报酬函数达到最大,即
))(()]()(),([max)())(())(,( *
1
*
1
*
1
** igjgapaigjgifpifig
k
N
j
kijkAa
N
j
kkijkk
=
∈
=
+ =+=+ ∑∑,
这样就得到了 f },,,{ ** 1*0* mm fff?= L,现在 证明它是最佳的 Markov 策略,对于任意
Markov 策略 f =( nf,0 ≤ n ≤ m),定义辅助 Markov 策略 f )(k },,,,,{ ** 10 mkk ffff LL +?=,用后向数学归纳法可以直接验证以下不等式
(J 0m,f ) ≤ (J 0m,f ))(k (k ≤ m),
取 k=0 即得 (J 0m,f ) ≤ (J 0m,f )*,请读者自己补上这段验证,
[ 注 1] 以上寻找 f * 的方法,在计算机上实现十分简单,问题在于当行动集 A较大的时候,计算量会非常大,甚至难以在允许的时间内完成 。 于是 代之以用?e 最佳 Markov
策略,
[ 注 2] 本定理可以推广到状态集 S 是 为可数集,行动集 A 是 紧集,而报酬函数
),( aig n 是 有界连续函数情形,
[ 注 3] 在状态集与 动作 集较为一般的时候,为了保证最佳策略的存在,纯策略类就不够,必须考虑 用随机策略类,
2,3 无穷时段下的总报酬情形 ( ∞=m 的情形 )
定理 １６,９ 如果 报酬函数序列满足以下的衰减性质
∞<∑
∞
=0
,|),(|sup
n
nai aig,（ １６,７ ）
那么 存在最佳 Markov 策略 f *,（ 可以 利用有限近似证明 ）,
例 １６,１０ （ 折扣模型 ） 在应用中 常见例子 为 折扣报酬模型,即
),(),( 0 aigraig nn =
的情形,其中 10 << r 是 折扣因子,此时 只要 ),(0 aig 是有界函数,则 条件 (16.7) 满足,
定义 １６,１１ （ 平稳策略 ） 如果 Markov 策略 f =(,nf n ≥ 0) 对于任意 n 满足
0ff n =,则称为 平稳 Markov 策略,
446
定理 １６,１２ 对于折扣报酬模型,最佳 Markov 策略 （ 如果存在 ） 是平稳 Markov
策略,
证明 记 平均 累计报酬为
iJ (,f )= ),(0
0
nn
n
n
aEgr x∑
∞
=
,
假定 最佳 Markov 策略 是 f * =(,*nf n ≥ 0),令
f )(k },,,,,{ *2*1*0*0 LL ffff?= ( 共 k 个 *0f ),
那么,用归纳法可以证明
iJ (,f )(n )= iJ (,f )1(?n ) == L iJ (,f )0( )= iJ (,f * ),
令 ∞→n,便得 iJ (,f )(∞ )= iJ (,f * ),这说明平稳 Markov 策略 f )(∞ ),,( *0*0 Lff?= 是一个最优 Markov 策略,】
利用不动点理论还可以证明,对折扣报酬模型,若状态集 S 可 数,行动集 A是 紧集,
且 ),(0 aig 有界,则平稳 Markov 策略 f 是最佳策略的充要条件是,它满足下述 Bellman 方程 ( 动态规划方程 ),
iJ (,f )=max Aa∈ [ ),(0 aig + ∑
j
ij apr )( (J j,f )],)( Si ∈?,（ １６,８ ）
由此可知 J(.,f ) 是下述非线性变换 )(JTJ → 的唯一不动点 ( 即 (J,,f ) 满足方程
JJT =)( ),
)( JT?=)(i m ax Aa∈ [ ),(0 aig + ∑
j
ij apr )( ))(( jJT ],)( Si ∈?,
这个结论的优点在于,定理中的 m 可用 ∞ 代替 （ 即近似 ）,后者显然更为简单,因为它的最佳策略是平稳 Markov 策略,而且只要求出变换 T 的不动点 ( 即 JJT =)( 的解 (J,)),再令
*)( aif?=
即可,其中 *a 是 [ ),(0 aig + ∑
j
ij apr )( ))(( jJT ] 达到最大值的动作,这样的计算将大大地减少机耗时间,有时对于充分大的 m,可以用 )(ITm 来近似 (J,),此处 I 是恒同映射,
而 TTTm oLo?= 为映射 T 的 m 次复合,
[ 注 5 ] 以上是以 平均 累计报酬作为目标函数的,它是按期望准则取最优,还可以按矩准则取最优,
按样本路径平均取最优,后者的报酬 是 一个随机变量,记时刻 m 前的累计报酬为,( 0iVm f ),其中 0i 为系
447
统的初始状态,作平均报酬序列,( 0iJ N f ∑
=
+=
N
mN 01
1),(
0iVm f ),一般,( 0iJ N f ) 的极限未必存在,
所以 常 取其收敛子序列中极限的最大者,记为,( 0iJ f ),或极限中的最小者,记为,( 0iJ f ),用它们作为目标函数,前者是以乐观的态度看待报酬,而后者是以悲观的态度看待报酬,在使用随机策略时,相应地记为,( 0iJ p ),其中 npppp ),,,( 10 L= 表示时刻 n 使用的随机策略,而把
0(iJ ),(sup) 0 pp iJ
=
作为最佳函数,这种 平均准则常见于发展较为平稳的系统,例如通讯网络,而累计总报酬准则,则常见于较快变化的系统,例如金融系统,轨道 平均报酬准则的数学处理,通常比 平均累计总报酬准则情形要复杂,
[ 注 ６ ] 最 一般的模型 是 策略的动作依赖历史情况的策略,设 S 与 A仍都为有限集,又设随机变量列 }{ nx 满足
x(P |1 jn =+ x ),,,1100 nn iii === xx L )(,nji ap
n
=,
其中 na 由下式递推地确定,
)( 000 ifa =,
...,
),,,,,,,( 111100 nnnnn iaiaiaifa= L,
这时的 }{ nx 不再是 Markov 链,因为它依赖于所有的过去 历史,而且此时 na 是一个依赖于 },,{ 0 nxx L
的随机变量,如果我们仍记 f =(,nf n ≥ 0),并称 之 为一个策略,那么对 此 模型也可类似地定义最佳策略 及最佳?e 策略,事实上,对 此 模型可以证明,在很宽的条件下,定理 １６,８ 中的最佳 Markov 策略也是这里的 策略类中的 最佳策略,也就 是最佳 Markov 策略在以上定义的非马氏策略类中仍是 最佳的,这就可以把搜索最佳策略的策略类 的范围 大大地缩小了,
[ 注 ７ ] 在 常见的实际模型中,有一类状态空间 S 是一个区间 ( 端点可以为 ∞ ),动作集 xAA =
是依赖状态 x 的一个有限区间,例如
(1) Ricker 模型 ( 合理捕 鱼问题 ) 设在时刻 n 湖中鱼的总量为 nx,捕鱼的原则是,在 有计划地留下数量 ( 随机的 ) na 的鱼用以繁殖 的前题下,求最大捕鱼量,假定鱼的数目与留下的数量受 群体控制 的
Ricker 模型所 制约,
nn ac
nn eac
2
11
+ =
hx,
其中 21,cc 为常数,}{ nh 是 独立同分布随机变量列,于是捕鱼量为 nnnn aag?=
xx ),( 中的
axaxg n?=),( 与 n 无关,这时状态空间为 ),0[ ∞=S,当状态确定为 x 时的动作集为
448
],0[ xAx =,在这模型中,相应于转移矩阵 P )),(()( iij Aaapa ∈= 的 是 转移核 );,( ayxp
）（ xAa ∈,如果采用策略 f ))(,( nnnn faf x==,则在时刻 m 的 平均累计报酬为
,( 0xJ f ))](([)
0
0 nn
m
n
x fE xx?= ∑
=
,其中 00 x=x ( 也可以是随机的 ),xxf n ≤≤ )(0,
(2) 最佳投资组合 假定只有两种证券,无风险的证券 ( 例如存银行,其利率为 r ) 及有风险的股票,设财产 nx 中投资于 股票的比例为 )10(,≤≤ nn aa,且以数量 nc 消费,此时 状态空间为
),0[ ∞=S,当状态确定为 x 时的动作集为 ],0[]1,0[ xAx ×=,即
)0,10(),,( xcca ≤≤≤≤= aa,
于是状态发展为
)]()1)(1[(1 nnnnnn cr?+?+=+ xhaax,
其中 nh 是股票的价值,典型的报酬函数 是 )()),(,( cucxg =a,它 代表由消费带来的,乐趣,,在经济学中称为由消费 c 产生的 效用函数,如果假定 }{ nh 为独立同分布,则 }{ nx 正是与前面类似的模型,但是,用独立同分布的随机变量来描述股票 的 误 差较 大,如果用 Black - Scholes 模型的离散采样描述股票,虽然较为合理,但是这 会 使模型 变得 复杂,
(3) 存储问题 讨论时刻 n 时商店中某种货品的存储量 nx,设进货量为 na,假定市场需求为独立同分布的 随机变量序列 nh,又设商店对此货品划定了最大容许库存量 c,那么,状态空间
],[ cS?∞= ( 在 0<nx 时表示缺货 ),在状态 ( 库存 ) 为 x 时的动作集为 ],0[ xcAx?=,而
nnnn a hxx?+=+1,
此时报酬函数依赖于 市场需求,假定单个货品的卖价为 s,进货价为 d,存储消耗价为 h,那么
时刻 n 的报酬为
)(),(min(),,( nnnnnnnnnn ahdaasag ++= xhxhx,
由此可以考虑最大化报酬,
[ 注 ８ ] 还可 以考虑时间 连续的情形,这就是可控 Markov 过程,这类问题较为复杂,在概率论中涉及最佳停时,而 在求解最佳策略时,常用偏微分方程中的活动边界理论 或变分不等式,
