中山大学
硕士学位论文
连续时间MDP折扣模型的单调最优策略
姓名:廖恭图
申请学位级别:硕士
专业:概率论与数理统计
指导教师:郭先平
20100607
中山大学硕士学位论文
连续时间MDP折扣模型的单调最优策略
【中文摘要】
本文在期望折扣总报酬准则和期望折扣总费用准则下首次研究连续时间马尔可夫决
策过程(简记为MDP)单调最优策略的存在性问题,给出使得最优策略关于系统状态单
调(不减或不增)的充分条件.在介绍相关背景及预备知识之后,本文首先给出可加函数
的定义以及一些与取到其极值点的单调性问题相关的主要性质;然后在上述两种不同的
折扣准则下,分别就转移速率q(J㈦n)有界与无界两种情形,探讨单调最优(平稳)策略
的存在性.具体说来,先给出使得从决策模型的原始数据出发递归地定义的一组函数序
列和该序列的极限函数关于系统状态单调的条件,再给出进一步条件保证在文献Guo&
Hem缸dez-Lerma(Springer-Verlag,New York,2009)的基础上构造的最优平稳策略关于
系统状态是单调不减(或单调不增)的.此外,给出了两个例子以进一步阐明本文得到的
单调最优策略存在的结果和条件,还得到一些有趣的新结果.最后,本文介绍了两个与连
续时间MDP单调最优策略有关的两个有待研究的问题.
【关键词】
单调最优策略、最优策略、上可加函数、下可加函数、充分条件
连续时问MDP折扣模型的单调最优策略
Monotone Optimal Policies for Continuous-Time Markov
Decision Processes in Discounted Models
ABSTRACT
T11iS thesis first studies the monotone ohmal policies for continuous—time Markov decision
processes(MOP)under the expected discounted—reward and expected discounted-cost
criteria,and provides sufficient conditions to ensure that the optimal policies are monotone
(nondeereasing or nonincreasing)in the system states.ARer a brief introduction of the background
and preparatory knowledge,the thesis gives the definition of superadditive and subaddi—
tive functions and provides the key properties related to the monotonicity offinding the extremal
points ofthose functions,and then establishes the existence ofoptimal(stationary)policies with
monotone structure in two distinct discounted models above—mentioned with bounded and anbounded
transition rates q(J l i,n),respectively.To be more specific,we first give conditions
to ensure the monotonicity of the function sequence recursively defined from the original data
ofthe decision model and the monotonicity of its limit function.Based on Guo&Hemfi_ndez-
Lerma(Springer-Verlag,New York,2009),we then add further conditions to ensure that the
optimal stationary policies constructed in the thesis are monotonically nondecreasing(or nonincreasing).
In addition,we use two examples to illustrate the main results in this thesis and derive
some new interesting results.Lastly,we introduce two open problems related to the monotone
optimal policies for continuous.time加P
KEYWoRDS
Monotone optimal policy,optimal policy,superadditive function,subadditive function,SU-
伍eient condition.
中山大学硕士学位论文
付符丐号说明
8
0
o(亡)
4
A(i
留(X
玩(S
c(t,a
E。

{
,幸
,Q
S(i)
F


m(i)
p(jli,a)
办(s,i,亡,歹)
JP(X)


·l,.S
q(jli,7r)
q(jli,7rt)
q(jli,a)
q(jli,,)
矿(i)
岱(o)
行动
状态
在时刻t选取的行动
行动空间
系统处于状态i时可用的行动集
Borel空间X上的Borel盯一代数
全体S上存在有限伽一范数的函数组成的空间
系统处于状态i,选取行动a时产生的费用
对应于磁。的期望算子
对应于碍的期望算子
确定性平稳策略
对应于折扣因子Q的最优确定性平稳策略
在策略f下系统处于状态i时选取的行动
全体平稳策略组成的集合
对应于折扣因子Q的最优折扣总费用函数
由(2.27)定义的算子
满足m(i)≥旷({)的正数
由(2.20)或(2.28)定义的转移概率
在策略7r下的转移概率
留(X)上所有概率测度组成的集合
由策略7r和初始状态i确定的概率测度
由策略7r和时刻s上的初始分布∥确定的概率测度
在策略7r下从状态i到状态j的转移速率
在策略仉下从状态i到状态j的转移速率
选取行动a时从状态i到状态j的转移速率
在策略厂F从状态i到状态J的转移速率
对每个i∈S,口+0):=sup{一q(ili,a)la∈A(t))
q(ili,o)的绝对值
连续时间MDP折扣模型的单调最优策略
qM)
Q(7r)
Qh)
Q(f)
r(i,a)
r(·,丌t)
r(·,7r)
s
T
K(i,丌)
uo(i,7r)

矿(t,丌)
y+
z(亡)


丌t

Ⅱ5
”忆
q(ili,,)的绝对值
在策略7r下系统的转移速率矩阵
在策略几下系统的转移速率矩阵
在策略,下系统的转移速率矩阵
系统处于状态i,选取行动a时产生的报酬
在策略丌t下的报酬函数
在策略7r下的报酬函数
状态空间
所有决策时刻组成的点集或由(2.19)定义的算子
初始状态为i,在策略7r下的期望折扣总报酬
初始状态为i,在策略7r下的期望折扣总费用
对应于折扣因子Q的最优折扣总报酬函数
初始状态为i,在策略7r下的长期期望平均报酬
最优平均报酬函数
在时刻t系统所处的状态
S上的初始分布
随机平稳策略
随机马氏策略
全体随机马氏策略组成的集合
全体随机平稳策略组成的集合
以W为权重的范数
中山大学硕士学位论文
缩写说明
M DP
cTMDP
DRDE
DcoE
马尔可夫决策过程
连续时间马尔可夫决策过程
折扣报酬最优方程
折扣费用最优方程
学位论文原创性声明
本人郑重声明:所呈交的学位论文,是本人在导师的指导下,
独立进行研究工作所取得的成果.除文中已经注明引用的内容外,
本论文不包含任何其他个人或集体已经发表或撰写过的作品成果.
对本文的研究作出重要贡献的个人和集体,均已在文中以明确方式
标明.本人完全意识到本声明的法律结果由本人承担.
学位论文作者签名:
日期: 年月日
学位论文使用授权声明
本人完全理解中山大学有关保留、使用学位论文的规定,即:学
校有权保留学位论文并向国家主管部门或其指定机构送交论文的电
子版和纸质版,有权将学位论文用于非赢利目的的少量复制并允许
论文进入学校图书馆、院系资料室被查阅,有权将学位论文的内容
编入有关数据库进行检索,可以采用复制、缩印或其他方法保存学
位论文.保密的学位论文在解密后使用本规定.
学位论文作者签名: 导师签名:
日期: 年月日日期: 年月E1
第一章绪论
§1.1问题提出的背景
§1.1.1马尔可夫决策过程与基本概念
作为20世纪50年代产生的随机运筹学的一门分支,在过去的几十年中,马尔可夫
决策过程的理论和应用得到了长足的发展.具体说来,马尔可夫决策过程已经在生态科
学(如水资源管理、森林管理),经济理论(如动态资产定价、商品与服务定价、广告优
化),通信工程(如计算机/通信网络系统控制)以及众多学科中得到了应用,丽这些新的
应用也为其带来了丰富的理论结果.
马尔可夫决策过程(Markov Decision Processes,简记为MDP,也称为马尔可夫控制
系统或马氏决策规划等)是研究一类随机序贯决策问题的理论.所谓随机序贯决策问题,
是指在一系列相继的或连续的时刻(称之为决策时刻)点上,决策者根据观察到的状态从
可用的行动集中选取—个作为决策;将决策付诸实施后,系统将获得与所处状态和所采取
决策相关的一项报酬(或费用),并影响系统在下一决策时刻点所处的状态.系统在下一
决策时刻点处的状态是随机的.决策者根据新观察到的状态,再作新的决策,如此一步一
步进行下去.决策的目的是使系统的运行在某种意义下(称为准则)达到最优.而马氏决
策过程模型的特点是可采用的行动集,即得报酬(或费用)和转移概率(或转移速率)只依
赖于当前的系统状态和选取的行动,与过去的历史无关.马氏决策过程就是研究这种马尔
可夫随机序贯决策问题的一门学科,是(确定性)动态规划与马尔可夫过程相结合的产物.
本文的主要目的在于探讨可数状态连续时间MDP折扣模型的单调最优策略的存在
性问题,为了使读者能够更好的理解什么是单调最优策略,在此先介绍一些MDP的基本
概念.如前所述,在每个决策时刻,系统可能的每一个状态在决策过程中随机的出现.针
对每个不同的状态,决策者会选取不同的行动,我们把在一个特定的决策时刻在每个可
能状态上选取行动的原则称为决策规则.决策规则不仅依赖于当前状态,而且还有可能
依赖于以前的那些状态和在那些状态上选取的行动.我们把在将来任意可能的状态上选
取行动的规则称之为策略.一个策略实际上就是一个决策规则序列.因此一个策略产生
了一个报酬(或费用)序列.而马氏决策问题就是要在第一个决策时刻之前就预先选好
(最优)策略,使得报酬(或费用)序列的某个函数值一一准则在这个策略下达到最大.准
则的选取要由决策者权衡各方面的利弊而决定.比较常用的准则有期望折扣总报酬准则
和平均报酬准则.
对于某个最优策略,如果它关于系统状态单调不减或单调不增,更确切的说,如果该
策略所包含的所有决策规则都是从有序状态集到有序行动集的单调函数,那么就称其为
单调最优策略.显然,单调最优策略是一种具有特殊结构的最优策略.如果我们能够给出
条件保证最优策略是单调的,那么将会大大简化最优策略的结构,这样不仅能够满足决
策者的要求,而且具有易操作性和更重要的一一易计算性.因为,一旦知道决策问题的最
2 连续时间MDP折扣模型的单调最优策略
优策略具有某种简单(在此可指单调)的结构,我们可以设计并利用某些特殊的算法在具
有相同简单结构的策略集中选取一个作为最优策略,直接免去在不具有该简单结构的策
略集中筛选策略的过程,从而达到减少计算步骤,缩短计算时间的效果.
§1.1.2离散时间MDP单调最优策略的研究现状
很多文献对离散时间MDP的单调最优策略的存在性问题及应用进行过广泛的讨
论.Serfozo(1976)[23】为离散时间MDP的单调最优策略的理论分析研究奠定了基础.该
论文给出了在状态集定义了偏序以及行动集空间是实直线上的紧子集时,离散时间MDP
的单调最优策略存在的充分条件.论文还分析了在证明单调最优策略存在的过程中起到
重要作用的单调转移概率的性质,并利用受控随机游走模型和多机器维修模型作为单调
最优策略理论应用的实例.‘
Topkis(1978)【24】给出了使得一系列目标函数与受约束集都依赖于某个参数的优化
问题具有依赖于该参数的单调最优解的条件,提供了下可加函数在格上最小化的一般化
理论,并成功在运筹学中引入这些理论,有力推动了单调最优策略领域的进一步研究.
随后,有关单调最优策略理论的论文和专著陆续发表和推出,比较著名的有Albright
和Winston(1979)【1】.该论文利用马尔可夫决策分析去研究在动态随机环境中最优(广
告)宣传和定价决策的特征,在无竞争和有竞争情形下分别给出并解释使得最优(广告)
宣传水平和最优定价总是随着公司的市场地位单调增加或减少的具有马氏性的转移概率
和单阶段报酬函数的性质.此外,Heyman和Sobel(1984)【13】的第八章在更一般的(包括
有限阶段和无线阶段)模型中讨论单调最优策略存在的充分条件,并通过资源管理、现金
管理等模型来阐明前面得到的结果,最后还对单调最优策略的收敛性展开了深入讨论.
§1.1.3连续时间MDP折扣模型的研究现状
本文讨论的是连续时间MDP折扣模型的单调最优策略的存在性问题,由于单调最优
策略是一种具有特殊结构的最优策略,所以单调最优策略存在的一个大前提是决策模型
的最优策略存在.关于连续时间MDP折扣模型的最优策略存在性问题,前人也做过很多
讨论.1960年著名数学家Howard首次提出MDP,还给出了折扣准则以及折扣报酬最优
方程.当状态空间和行动集都有限的时候,Howard(1960)【14],Miller(1968)【16],Roykov(
1966)【22],Veinott(1969)【25】分别在不同的条件下对折扣报酬最优方程的解以及
折扣最优平稳策略的存在性进行了研究.galmmanu(1971)【15】把上述各文献的结果推
广到状态空间和行动集可数,转移速率和报酬函数都有界的模型中.他利用有限MDP逼
近可数MDP的方法证明了最优折扣报酬函数是折扣报酬最优方程的唯一有界解,以及
任意使得折扣最优方程成立的确定性平稳策略也是折扣最优的.
对转移速率可能无界以及状态集和行动集可能不可数的更一般的折扣模型,Guo和
Hemfindez-LermaGuo(2009)【7】,Guo和和Hem矗11dez-Lerma(2003a,2003b)【8,9】,Guo
和Zhu(2002)【10],Hemfindez-Lerma和Govindan(2001)【12],Prieto—Rumeau和Hem缸-
中山大学硕士学位论文3
dez—Lerma(2006)【19],侯振挺和郭先平(1998)【311,宋(1987)[35],以及伍(1997)【36】
分别在不同的假设下进行过讨论.本文将借助Guo和Hemfindez-LermaGuo(2009)【7】关
于折扣最优策略存在的几个假设条件,进一步给出保证折扣最优策略还是关于系统状态
单调的条件!
§1.1.4引言
在离散时间MDP理论中,文献【20】详细阐述了无限阶段折扣模型
{T={1,2,⋯),S,A(i),p(歹li,口),r(i,a),i,J∈S,a∈A(i)) (1.1)
的单调最优策略存在的两个充分条件;
假设1.1【20】存在一个常数p<oo,使得
sup Ir(i,口)I≤zw(i).
a_∈A(O
假设1.2【20】(1)存在一个常数K,0≤K<oo,使得对所有的a∈A(茁),i∈S,有
Σp(jli,o)伽(歹)≤K伽({);
J∈S
(2)对每个入,0≤A<1,存在一个Q,0≤Q<1和某个整数t7r,使得对所有的
7r=(dl⋯.,如),有
AJΣPff(jli)w(j)≤Q叫(i),
其中dk(1≤k≤J)是马氏确定性决策规则.
以上两个假设可参见文献【20】第232页.
定理1.1【20】设对任意定义在非负整数集S上的单调函数钍,
搿似。)+霎砌㈠砌)) n2,
上式可达到最大值,且假设1.1,1.2成立,若以下四个条件
(1)对所有的a∈A’,r(i,o)是关于i∈S的单调不减函数;
oo
(2)对所有的a∈A7和七∈S,Σp(jli,a)是关于i∈S的单调不减函数;
歹=七
(3)r(i,a)是S×∥上的上可加(下可加)函数;
00
(4)对所有的南∈S,Σp(jli,a)是S×At上的上可加(下可加)函数;
j=k
也成立,则存在最优策略(扩)oo满足:最优决策规则矿(s)在i∈S上单调不减(单调
不增).其中入,0≤入<1是折扣因子,且对所有i∈S,A(i)=∥.
证明参见文献【20】第258页的定理6.11.6. 口
4 连续时间MDP折扣模型的单调最优策略
推论1.1【20】设对任意定义在非负整数集S上的函数u,(1.2)式可达到最大值,且假
设1.1,1.2成立,若以下四个条件
(1)对所有的a∈A7,r(i,a)是关于i∈S的单调不增函数;
00
(2)对所有的a∈A’和k∈S,Σp(jli,a)是关于i∈S的单调不减函数;
j=k
(3)r(i,a)是S X At上的上可加函数;
00
(4)对所有定义在S上单调不增的函数u,Σp(jli,a)u(j)是S xA'上的上可加函数;
j=o
也成立,则存在最优策略(扩)oo满足:最优决策规则扩(s)在i∈S上单调不减.其中
入,0≤入<1是折扣因子,且对所有i∈S,A(i)=∥.
以上推论参见文献[20】第260页的例6.1 1.1.
在上述离散时间无限阶段折扣MDP模型中,状态空间S是可数的非负整数集,报酬
函数r(i,a)无界.另一方面,文献【7】在状态空间可数,报酬函数无界的模型下给出了连
续时间MDP折扣模型最优策略的存在性条件(见本文第二章的定理2.6).
本文在文献【7】和文献[20】的基础对以上结论进行推广,讨论使得连续时间MDP折
扣模型的单调最优策略存在的充分条件.在该模型中,状态空间S也是可数的非负整数
集,报酬函数r(i,a)(或费用函数c(蟊a))也无界.由于连续时间MDP问题系统状态的转
移概率p(jli,a)只能通过转移速率q(jii,a)来刻画,本文将会在期望折扣总报酬准则和期
望折扣总费用准则下就q(Jli,a)有界与无界两种情形进行分别讨论,并且给出了两个具
有实际背景的例子作为补充说明.
中山大学硕士学位论文5
§1.2本文的主要工作
文献【20】给出了可数状态离散时间无限阶段MDP折扣模型的单调最优策略存在的
充分条件,文献【7】给出了可数状态连续时间无限阶段MDP折扣模型最优策略的存在性
条件,本文是在二者基础上的推广,在两个不同的折扣准则下研究单调最优策略的存在
性问题,给出使得最优策略关于系统状态单调(不减或不增)的充分条件.
本文分四章介绍有关工作.第一章介绍了马尔可夫决策过程的概况,单调最优策略
的相关成果以及问题的由来.第二章提供了阅读本文的预备知识.第三章是全文内容的
核心,首先给出可加函数的定义以及一些与取到其极值点的单调性问题相关的主要性质;
然后分别在期望折扣总报酬准则与期望折扣总费用准则下探讨单调最优(平稳)策略的
存在性条件;此外,还就q(jli,a)有界与无界两种情形分别给出了两个例子,以进一步阐
明前文得到的单调最优策略存在的结果和条件.第四章简单总结了本文的主要结果,并
介绍了两个在撰写本文的过程中有待研究的问题.
第二章连续时间MDP基础
本章给出连续时间MDP基础作为预备知识,绝大部份内容来自文献【7】的第二章和
第六章.
§2.1连续时间马尔可夫决策过程模型
本文所讨论的连续时间马尔可夫决策过程(Continuous.Time Markov Decision Processes,
简记为CⅨDP)模型由如下五元组组成:
{互S,A(i),q(jli,a),r(i,a),i,歹∈S,n∈A(i)) (2.1)
它所描述的是一个动态概率系统,其中各元的含义如下:
(1)T是所有决策时刻(选取行动的时间点)组成的点集.本文假定T=【0,OO)为
非负的半实轴.由于T是连续的,决策者可以连续地做决策,也可以在某些随机点(某些
事件发生时)上做决策或者由决策者选择时机做决策.
(2)S是系统所有可能的状态所组成的非空的状态集,称之为系统的状态空间,它
可以是有限集、可列集或任意非空集.除非特别说明,本文假定S是可数(即有限或可
列)集.我们用小写字母i,J,k等(或加上上、下标)来表示系统状态.
(3)A(i)是系统处于状态i时的可用行动集,它是非空可测的,称之为行动空间.我
们用a表示行动.令A=U A(t),并且假定S和A(i)都独立于时刻t.设
iES
K:={(i,a)li∈最a∈A(z)) (2.2)
为全体可行的状态.行动对组成的集合.
(4)q(jli,a)是平稳的转移速率,满足对所有(i,a)∈K以及J≠i,有q(jli,a)≥0.
本文还假定转移速率q(j li,a)是保守的,即
Σq(jli,口)=0, v(i,。)∈K, (2.3)
J∈S
以及稳定的,这意味着
口+({):=sup依(口)<o。, V/∈S, (2.4)
aeA(i)
其中qi(a):=-q(ili,a)≥0对所有(i,a)∈K都成立.同时,对每对固定的i,歹∈
S,q(jli,a)是A(i)上的可测函数.
(5)r(i,a)是K上的可测实值函数,也称为报酬函数.对每个固定的i∈S,它还在
A(i)上可测.当r(i,a)为正值时,表示收入;当其为负值时,表示费用(故有时还称其为
费用函数).需要注意的是,本文MDP模型中的报酬(费用)函数无界.
上面基本完成了CTMDP模型的描述,接下来简单介绍一下决策者是如何采取行动,
达到控制系统的目的.为此,我们先引入下面几个概念。
7
8 连续时间MDP折扣模型的单调最优策略
定义2.1【7】称实值函数丌t(CIt)为—个随机马氏策略,如果它满足以下条件:
(1)对所有的t∈S和C∈留(A(i)),t H丌t(Cli)是[0,00)上的可测映射;
(2)对所有的i∈S和亡≥0,C H仉(Clz)是留(A)上的概率测度,且7h(A(i)li)=1,
其中丌£(CIi)表示在时刻亡系统处于状态i时在C中选取某个行动的概率.
定义2.2【7】称随机马氏策略7rt(CI{)为随机平稳的,如果7rt(CIi)兰7r(Cli)独立于时
刻亡.
定义2.3阴称函数,:S_A为一个确定性平稳策略,如果对所有i∈S有/(i)∈
A(i).通常确定性平稳策略简称为平稳策略.
以上定义可参见文献[7】第10.1l页.
全体随机马氏策略组成的集合记作Ⅱ,全体随机平稳策略组成的集合记作Ⅱs,全体
平稳策略组成的集合记作F.事实上,我们可以把平稳策略,∈F看作函数仉(CIi)∈II,
满足对所有亡≥0和i∈S,吼(Clt)是/(i)上的一个Dirac测度.
由上述定义可以看出,各类策略集间的关系为F cⅡs cⅡ.
有时,我们会简称随机马氏策略丌t(CI{)为马氏策略,并把它记作丌t.类似的,随机
平稳策略-(Cli)也会被简记作7r.
对每个7rt∈II,定义矩阵Q(仉):=【q(jii,仉)】如下;
q(jii,丌t):--/ q(jli,a)=t(dali), {,J∈S,t≥0 (2.5)
JA(i)
根据(2.3)和(2.4),上述积分(2.5)有定义且以口+(t)为上界,因为
q(j]i,o)≤Σq(jli,口)=吼(口)≤g’(t), Vi,歹∈s,o∈A(i)
J≠i
同时,对任意固定的i,歹∈S,90lt,丌t)在t≥0上是可测的.根据(2.4)和(2.5),可知
q(jii,7rt)也是稳定且保守的,即
吼(仉):=一q(ili,丌t)=Σq(Jlt,仉)<+oo, Vi∈s,t≥0
J≠‘
Q(7rt)是使用策略71"t,系统在时刻t相应的转移速率矩阵.当7r是平稳策略,即
霄∈IIs或,∈F时,Q(丌t):---【q(Jit,7rt)】与t无关,简记为Q(7r):=【q(jii,7r)】或
Q(/):=[a(Jli,,)】.
由文献【7】知,对每个7r∈II,存在一个最小转移函数,在此记它为m(s,i,z,歹),它具
有转移速率q(jli,巩).更确切的说,对所有i,J∈S,t≥0以及a.e.s∈(0,亡),m(s,i,t,歹)
是满足下列柯尔莫哥诺夫向前向后微分方程掣:Σ啪一啪)g(ilk础况急,“㈠一用
~”
坠幽:一F口(啦丌。)办(s,¨歹),Os 忽扒11叫⋯一””
驾掣2Σ椭^啪引咖)
的最小解.此外,
=Σq(kli,7r炳(o,k,t,歹) (当7r∈11s)
七∈S
m(s,i,t,j『)=Σ‰(s,i,t,,k)p霄(口七,t,j『),
七∈S
Vt,∈【s,tl, 躲咝型笋-口(巾川,咖^印)=如,
其中翰表示Kronecker’s delta,“a.e’表示在【o,oo)上几乎处处成立·
为保证转移函数陬(s,t,t,J)满足正规性,即
(2.6)
(2.7)
Σ‰(8,i,t,歹)=1, Vi∈S,t≥s≥0, (2·8)
jes
从而保证对应马氏过程的存在性,我们还需要下面的假设,即所谓的飘移条件.
假设2.1【7】存在一个S上函数叫≥1和常数co≠0,bo≥0和‰>0,使得
(1)对所有(t,n)∈K,有Σ歹∈sw(j)q(jli,o)≤cow(i)+6;o;
(2)对所有i∈S,有矿(t)≤Low(i),其中旷(i)的定义见(2.4).
以上假设可参见文献【7】第13页.
对任意的初始时刻s≥0,令
GB:={(亡o,t1,⋯,k)Is≤to<tl<⋯<tn<o。,Vn≥o).
设E::S×A,∥为任意给定的S上的初始分布.则对每个7-:=(to,tl⋯.,tn)∈G5,
我们定义(扩+1,历(驴+1))上的乘积概率测度擘丌使得:对每个B={如)×瓯×戗,)×
a,×⋯×{五。)×G。,兔∈S,G。∈留(A)(%=0,1⋯.,n),有
尸y(B):=I,0£0)7rt。(ck忱。)p霄(%,‰,tl,j『t。7[t,(G,魄)
⋯如(亡n一1,k圳tn,五。71"t。(G。l五。). (2.9)
设Q::矿是由全体从T到E的映射组成的集合,(Q,留(Q))为乘积可测空间.设啊是
Q上面的投影,即
价(z):=zr,对每个z=(z(亡),t≥0)∈Q, (2.10)
其中磊:=(z(to),z(亡1)⋯.,名(亡n)).然后我们有以下定理:
10 连续时间MDP折扣模型的单调最优策略
定理2.1【7】若假设2.1成立,初始时刻s≥0,则对每个7r=(71"t)∈II和每个给定的S
上的初始分布扩,存在可测空间(Q,留(Q))上的唯一一个概率测度焉(取决于s,z,,7r)
使得对任意t≥S和丁:=(to,tl⋯.,tn)有
彤。(职,t(C))=v(i)Tr。(C[i), (2.1 1)
磁。(呱t,,ij(c))=∥(t)p丌(s,i,t,J)仉(c13), (2.12)
最。(研)=Σ∥(i)p丌(s,i,to,死)‰(瓯I丸协(%,死舳t五。Trt,(G。院。)
iES
⋯孙(k一1,死一。,tn,五。)仉。(G。I五。). (2.13)
其中
巩,f(c):=Z∈Q:z(s)∈{订X C),
彬t.,tf(C):=Z∈Q:(z(s),z(亡))∈{i)×A X{歹,×C),
Bl:=Z∈Q:聃(z)∈1【如)×Ck x⋯X{死)X ck),
在此i,J,九∈S,C,Gk∈留(A)(忌=0⋯.,n),8≤to<⋯<tn<oo.
证明参见文献【7】第14页的定理2.3. 口
定义2.4【7】(状态过程与行动过程)对所有z=(z(亡),t≥0)∈Q和t≥0,设z(t):=
(zo(t),z1(亡))∈E=S X A.定义概率空间(Q,留(Q),磁。)上的随机变量z(亡)(名):=少(亡)
和o(亡)(z):=Z1(t).若在初始时刻8≥0给定初始分布扩,选用策略7r∈II,我们称
{z(亡),t≥o}和{o(t),t≥o)分别为状态过程和行动过程.
我们用舷。表示对应于概率测度磁。的期望算子.如果在时刻8,有∥({i))=l和
∥(D))=0(J≠i),那么可以把%。和磁。分别记为臻和饬,这里的i代表初始状态.
当8=0,我们还会把%和确分别记为霹和露.
对定义在K上的任意实值可测函数u(i,a)和(巩)∈II,设
f
u({,丌t):=/ 让(i,a)7rt(dali), Vi∈A(i),t≥0, (2.19)
.,a(o
只要以上积分有定义.如果用,∈F替换(7rt)∈II,则(2.14)可简写为u(i,,):=
u(i,.厂(i)).
定理2.2【刀若假设2.1成立,则对所有t,歹∈S,7r=(丌t)∈II,C∈留(A)和t≥s,有
(1)圪(z(£)=J)=如(s,i,亡,歹)和ΣkES‰(s,{,t,k)=1;
(2)吃(o(亡)∈CIz,(t)=歹)=丌t(CIJ);
(3)设对某些M≥O,有
sup lr(i,n)I≤Mw(i), Vi∈S, (2.15)
*ca0)
其中r(i,a)和w(i)的定义分别见(2.1)和假设2.1.则期望报酬既r(z(亡),o(亡))有限并在
t≥s上可测.
证明参见文献【7】第15页的定理2.5. 口
中山大学硕士学位论文
虽然本文讨论的MDP折扣模型下报酬(费用)函数无界,但是我们看到在任何一个
状态上选取任一行动时的期望折扣总报酬(费用)还是有界的,因此我们还需要以下定
义:
定义2.5【71对任意在X上满足∞≥1的函数W,定义X上的实值可测函数让的权重
上界范数”忆如下:
Ilull∞:=sup{伽(z)一1I让(z)I),
z∈X
且Banach空间玩(x):={u:llull伽<co}.
以上定义可参见文献【7】第9页.
连续时间MDP折扣模型的单调最优策略
§2.2期望折扣总报酬准则的最优策略
本节主要讨论在期望折扣总报酬准则下最优策略的存在性条件,首先给出期望折扣
总报酬准则的定义.
定义2.6【7】(期望折扣总报酬准则)当系统的初始状态为i∈S,定义策略7r=(7rt)∈II
的期望折扣总报酬如下:
哪,小=霹[Z00e咄Ⅵ∞),7rt)叫, (2.16)
其中
r(i,n't):=/ r(i,a)7r,(dali), (2.17)
.,A(O
相应的最优折扣总报酬函数(或折扣最优问题的最优值函数)是
嵋(i):=sup圪(i,7r), 初始状态i∈S.
'r∈Ⅱ
定义2.7阴如果存在策略7r+∈17,满足
K(i,7r+)=吆(i), Vi∈S,
则称策略7r+是折扣(报酬)最优的.
定义2.8【71(Discounted-Reward Optimality Equation,以下简记为DROE)方程
伽o)-刚sup∽似n)+≤呱力“引t n)j’Vi e S, (2.18)
称为折扣报酬最优方程.
以上定义可参见文献[7】第17页和第87页.
正如绪论中提到的,本文的主要工作是在文献【7】的基础上给出保证最优策略是单
调(关于系统的状态非降或非增)的条件.由于单调最优策略是具有特殊结构的最优策
略,在此我们先给出最优策略的存在性条件以及相关的重要假设、概念、算子与定理.
假设2.2['rl ’
(1)对每对(i,a)∈K和某常数M>0,有lr(i,口)f≤Mw(i),其中W见假设2.1;
(2)正的折扣因子Q满足Q>Co,其中常数印见假设2.1.
以上假设可参见文献【7】第92页.
对每个i∈S,设m(i)为任意满足m(i)≥矿(i)≥0的正数.当IIqlI:=supq+(t)<
‘∈.s
+o。,可选取m(i):=IIqll,Vi∈S.定义算子T:玩(s)_玩(S)如下:
聊):=刚sup∽{端+ire(i)牡∽pm)) ㈣
其中U∈B山(S),i∈S,对每对(i,a)∈K,
中山大学硕士学位论文13
p(jli,a):=掣+妨(2.20)
是S上的一个概率测度.显然算子丁是单调的,即若让≥口,有孔≥Tv.
利用以上算子递归地定义s中的函数序列{Ⅱn)他≥o如下: 咖(i):=一碉boM 一面M伽(i), i∈s,(2.21)
其中叫,co,bo,M见假设2.1,2.2,对n≥0,
钍他+1:=Tun. (2.22)
假设2.3[71
(1)对每个t∈S,行动集A(i)是紧集;
(2)对每对固定的圣,歹∈S,r(i,8),q(jli,a)和&∈s w(k)q(kli,a)都是关于a∈A(i)
的连续函数,其中W见假设2.1;
(3)存在S上的非负函数W’和常数c,>0,6,≥0和M>0,使得
矿(i)"o)≤M’W7(i) , Σ删7(j)q(j Ji,n)≤dw7(主)+6,
J∈S
对所有(主,a)∈K都成立,K与矿(i)的定义见(2.2)和(2.4).
以上假设可参见文献[7】第95页.
假设2.4
(1)对每个i∈S,行动集A(i)是有限集;
(2)存在S上的非负函数W7和常数d>0,6,≥0和M7>0,使得
口+(i)铷(i)≤M7W7(i) , Σ伽7(j)q(j Ji,9)≤dw7@)+6,
j∈S
对所有(i,a)∈K都成立,K与旷(i)的定义见(2.2)和(2.4).
定义2.9[71称策略,∈F是F中的策略序列{厶)n≥o的一个极限点,如果存在{佗)
的一个子列{m),使得对每个i∈S,有
lim,m(i)=S(i).
以上定义可参见文献【7】第97页.
定理2.3忉若假设2.1,2.2成立,则:
(1)对所有i∈S和7r∈II,有№删≤揣+磊M呻)
成立,其中bo,co见假设2.1.特别地,屹(·,7r)在民(S)中;
(2)最优折扣总报酬函数吆在民(S)中.
14 连续时间MDP折扣模型的单调最优策略
证明参见文献【7】第92页的定理6.5. 口
定理2.4【刀若假设2.1,2.2成立,{札n)竹≥o为根据(2.19)、(2.21)和(2.22)定义的函
数序列,则:
(1)函数序列{乱n)竹>o是单调不减的,且该序列的极限让+:=timn.+o。乱n在玩(S)
中;
(2)让‘满足不动点方程t‘‘=2k‘,等价地说,t‘+满足DROE(2.18),即
甜∽2剌sup∽卜。)+荟让㈨航口))'VI E S. (2.23)
证明参见文献【7】第93页的定理6.6. 口
定理2.5阴若假设2.1,2.2,2.3(3)均成立,设7r=(几)∈II,牡∈玩(S),则:。
(1)对所有的i∈S和a.e.t≥0,如果
Qu(i)≥7(蕾,仉)+Σu(j)q(jli,7rt)
j∈S
成立,则对所有的i∈S,有u(i)≥K(t,7r);
(2)对所有的i∈S和a.e.t≥0,如果
a乱(1)≤r(t,死)+Σu(j)q(jli,仉)
jes
成立,则对所有的i∈S,有u(i)≤K(t,7r);
(3)对每个7r∈118,K(·,7r)是方程
Qu(i)=r(善,7r)+Σu(j)q(jli,丌), Vi∈S
jes
在风(s)中的唯一解.
证明参见文献【7】第95页的定理6.9. 口
设_【乱n)n>o为根据(2.19)、(2.21)和(2.22)定义的函数序列.称确定性平稳策略
f∈F达到方程‰+1=2、k的最大值,如果
啪)=端+焉篆姒咖Ⅲ),Ⅵ@
类似地,f∈F达到方程DROE(2.23)的最大值,如果
QⅡ+(t)=r(t,,)+Σ让+(j)q(jli,f), Vi∈S.
定理2.6【刀若假设2.1,2.2,2.3均成立,那么:
(1)存在确定性平稳策略序列{厶)n≥o和策略庀使得方程组‰+1=‰和DROE(2.23)
分别达到最大值;
(2)DROE(2.23)的解为让。=屹,(1)中的策略E是折扣最优的;
(3)序列{厶)n≥o的每个极限点都是折扣最优平稳策略.
中山大学硕士学位论文15
证明参见文献【7】第97页的定理6.10. 口
推论2.1若假设2.1,2.2,2.4均成立,那么:
(1)存在确定性平稳策略序列{厶)n≥o和策略庀使得方程组珏n+1=Tu他DROE(2.23)
分别达到最大值;
(2)DROE(2.23)的解为让‘=昭,(1)中的策略露是折扣最优的;
(3)序列{厶>n≥o的每个极限点都是折扣最优平稳策略.
证明(1)由于对每个i∈S,行动集A(i)是有限集,故存在ai‘,n∈A(t)和ai‘∈A(t),
使得
以及
蔫+确m(O薹咖引和∞
2刚sup∞{端+器嘉蚓pm,),
r(i,n:)+Σ矿◇)口◇fi,西)
2酬sup。如㈡+Σ以m引锄)卜
于是(1)成立.
(2)和(3)的证明同定理2.6. 口
16 连续时间MDP折扣模型的单调最优策略
§2.3期望折扣总费用准则的最优策略
定义2.10 (期望折扣总费用准则)当系统的初始状态为i∈S,定义策略7r=(7ft)∈
Ⅱ的期望折扣总费用如下:
嘶㈡:=霹忻e刊啦∽川叫, (2.24)
其中
c(i,"fit):=/ c(i,a)rrt(dali), (2.25)
JA(i)
相应的最优折扣总费用函数(或折扣最优问题的最优值函数)是
以(i):2:n∈儿f Va(i,7r), 初始状态i∈S·
定义2.11如果存在策略矿∈II,满足
vo(i,矿)=以(i), Vi∈S,
则称策略矿是折扣(费用)最优的.
定义2.12(Discounted-Cost Optimality Equation,以下简记为DCOE)方程
a砸)=剌inf∽似口)+薹蜊非㈡),VI E S, (2.26)
称为折扣费用最优方程.
下面将给出在期望折扣总费用准则下最优策略存在的条件.首先给出最优策略的存
在性条件以及相关的重要假设、概念、算子与定理.
假设2.5
(1)对每对(i,o)∈K和某常数M>0,有Ic(i,n)l≤Mw(i),其中W见假设2.1;
(2)正的折扣因子Q满足Ot>Co,其中常数Co见假设2.1.
对每个i∈S,设m(i)为任意满足m(i)≥矿(i)≥0的正数.当Ilgll:=supq+(i)<
iES
+oo,可选取m(i):=llqll,Vi∈S.定义算子L:‰(S)_÷玩(S)如下:
洲:=刚inf∽{端+高薹捌巾㈠) ㈣
其中可∈风(S),i∈S,对每对(i,o)∈K,
’p(jli,a):=掣+如
是S上的一个概率测度.显然算子三是单调的,即若仳≥移,有Lu≥Lv.
利用以上算子递归地定义S中的函数序列{%)竹≥o如下: ‰({):=而boM+而M叫(吾),i E S,
(2.28)
(2.29)
中山大学硕士学位论文17
其中W,Co,bo,M见假设2.1,2.2,对礼≥0,
‰+1:=厶%. (2.30)
定理2.7若假设2.1,2.5成立,则最优折扣总费用函数圪在民(S)中.
证明同文献【7】第92页的定理6.5类似. 口
定理2.8若假设2.1,2.5成立,_【%)n芝。为根据(2.27)、(2.29)和(2.30)定义的函
数序列,则: (1)函数序列{%)n>o是单调不增的,且该序列的极限矿:=虬oo%在玩(S)
中;
(2)矿满足不动点方程钉幸=Lv’,等价地说,移‘满足DCOE(2.26),即
铡弋孙=剃inf∽b曲+争o)口引柚)卜Vi e S (2.31)
证明同文献【7】第93页的定理6.6类似. 口
假设2.6
(1)对每个i∈S,行动集A(i)是紧集;
(2)对每对固定的主,歹∈S,c(i,n),q(j[i,n)和ΣkES w(k)q(kli,a)都是关于a∈A(i)
的连续函数,其中彬见假设2.1;
(3)存在S上的非负函数∥和常数c,>0,6,≥0和M7>0,使得
口+(i)伽(i)≤M7∥(主) , Σ铷7(j)q(jli,o)≤dw心)+6,
jeS
对所有(i,a)∈K都成立,K与g+(i)的定义见(2.2)和(2.4).
.设{%)n>o为根据(2.27)、(2.29)和(2.30)定义的函数序列.称确定性平稳策略
,∈F达到方程%+1=上%的最小值,如果
晰∽=端+确re(i)Σ嘶湫巾∽,Ⅵ@
类似地,,∈F达到方程DCOE(2.31)的最小值,如果
Qu+(i)=c(i,,)+芝:矿(歹)90It,f), Vi∈s.
歹∈S
定理2.9若假设2.1,2.5,2.6均成立,那么。
(1)存在确定性平稳策略序列{厶)n≥o和策略靠使得方程组%+1=己%和DCOE(2.31)
分别达到最小值;
(2)DCOE(2.31)的解为口’=龙,(1)中的策略庀是在期望折扣总费用准则下折扣
最优的;
(3)序列{厶)n≥o的每个极限点都是在期望折扣总费用准则下的折扣最优平稳策略.
证明同文献【7】第97页的定理6.10类似. 口
18 连续时间MDP折扣模型的单调最优策略
推论2.2若假设2.1,2.4,2.5均成立,那么;
(1)存在确定性平稳策略序列{厶>n邳和策略龙使得方程组Vn+l=L%和DCOE(2.31)
分别达到最小值;
(2)DCOE(2.31)的解为矿=龙,(1)中的策略龙是在期望折扣总费用准则下折扣
最优的;
(3)序列{厶)n>o的每个极限点都是在期望折扣总费用准则下的折扣最优平稳策略.
证明同推论2.1类似. 口
第三章可数状态连续时间MDP折扣模型的单调最优策略
§3.1可加函数及其性质
本节讨论可加函数及其性质,主要是可加函数的判别方法以及取到可加函数极值点
的单调性问题.它们将在下文探讨单调最优策略的存在性条件过程中发挥重要作用.
定义3.1 1201设x,y为两个定义了偏序的集合,夕(z,Y)是X×Y上的实值二元函数,
如果对矿≥z一(矿,z一∈x),Y+≥Y一(Y+,Y一∈y),有
g(x+,Y+)十g(x-,Y一)≥g(x+,可一)+g(x一,Y+), (3.1)
称函数g(x,Y)为上可加的或者上模的.如果-g(x,Y)是上可加的,则称函数g(x,Y)是下
可加或者下模的.
等价地,称函数g(x,Y)是上可加的,如果它满足
g(x+,Y+)一9(z+,Y一)≥g(x一,Y+)--g(x一,Y一), (3.2)
称函数g(x,Y)是下可加的,如果它满足
g(x+,Y+)一9(z+,Y一)≤g(x一,Y+)一g(x一,Y一). (3.3)
以上定义可参见文献【20】第103页.
由上面可加函数的等价定义我们可以得到以下几个可加函数的判别方法:
定理3.1[2q设X=Y=R,若029(x,v)/oxov存在,则
(1)g(x,Y)是上可加的当且仅当铲g(x,v)/oxov≥o;
(2)g(x,Y)是下可加的当且仅当029(x,v)/OxOv≤0.
证明先证(2).充分性.对于矿≥z一(矿,z一∈x),Y+≥Y一(Y+,Y一∈y),根据
积分的单调性,有
ff掣蛐舛
,.掣+A
Z一蔷M矿,沪g(z-,v)]dy≤0,
进一步展开,整理得
g(x+,Y+)一9(z+,Y一)≤g(x一,Y+)一夕(z一,Y一).
因此函数g(x,Y)是下可加的.
必要性.由于g(x,Y)是下可加函数,根据下可加函数的等价定义知里垦兰:』坚:}型≤望垦兰二三鼍享掣,v2+≥z一秒+≥s,Y十一Y 可十一Y
。。’
其中z+,z一∈X,矿,Y∈Y,固定z+,z一,对夕(z,Y)分别求(z+,Y)和(z一,Y)点关于Y的
偏导数,根据极限的保序性有lim丛竺I芝攀塑<lim丞兰章丛兰二塑., Ⅳ+一可暑f十一爹掣+一掣暑f十一可
20 连续时间MDP折扣模型的单调最优策略
以上不等式等价于
国(矿,Y)/Og@一,Y)
曲一曲’ z+≥z一,
所以029(x,夕)/如动≤0.
现证(1).由定义3.1知,夕(z,Y)是上可加的等价于-g(x,Y)是下可加的.而由(2)
知一夕(z,Y)是下可加的等价于伊[-夕(z,秒)】/如观≤0,故一g(x,y)是下可加的等价于
029(x,可)/跳动≥0,从而有g(x,y)是上可加的当且仅当(fg(x,y)/ozov≥0. 口
以上定理可参见文献[21】第6—7页.
引理3.1【20】设9(s,a)是S X A上的实值函数,其中A={o,1),
有的8,如果g(8,a)满足
g(s+1,1)一夕(s+1,0)≥9(s,I)一9(s,0),
那么夕(s,a)是上可加的.
S={o,1⋯.).对所
证明Vs一≤s+,8+一8一=As≥0,s+,8一∈S,若As=0,显然有
夕(s+,1)一夕(s+,0)=夕(s一,1)一9(s一,0);
若As>0,由假设条件可得
把上边△5个不等式的两边各自相加,得
从而夕(s,a)是上可加的.
g(8+,1)一9(s+,0)≥9(s一,1)一g(s-,0),
以上引理可参见文献[20】第l 10页.

引理3.2设9(s,a)是S X A上的实值函数,其中S=A={o,l⋯.).对所有的8,
如果夕(s,a)满足
g(8+l,a-t-1)一9(s+1,a)≥9(s,a+1)一9(s,a),
那么g(8,a)是上可加的.
证明Vs一≤s+,8+一8一=As≥0,s+,8一∈S,Va一≤n+,a-i-一n一=Aa≥
0,口+,a一∈A,若As=0或△口=0,显然有
9(s-!-a+)一g(8-I-a一)≥9(s一,口+)一g(s-,a一);



L

+
叭∽
旷叭
L
9
9一,

一;一p
+D
D
9
矿m
m
q
叫以
“肛
D旷
旷旷
L
9
9
9

>一
.、l,,、l, >一>一
矿埘
埘脚
“l
幺.L,
八I

++
∞∽
旷旷
},9
9
9
p一;一

哆D
D
D
—L
邑L
厂L
幺1

十+
+,+


““
,Il-IJ‘lI【从“
△ 个
中山大学硕士学位论文21
若As>0,Aa>0,由假设条件可得
l 9(s+,n一+1)一9(s+,Q一)≥g(s+~1,o一+1)一9(s+一1,o一),
I 9(s+一1,o一+1)一9(s+一l,口一)≥9(s+一2,n一十1)一夕(5+一2,n~),
△s个{ ; ;
l 9(s一+2,口一十1)~9(s一+2,口一)≥9(s~+1,o一+1)一9(s一+1,口一),
l 9(s一+1,口一+1)一9(s—+1,口一)≥g(s一,o一+1)一9(s一,o一),
把上边As个不等式的两边各自相加,得
9(s+,n一+1)一夕(s+,o一)≥g(s~,o一+1)一9(s一,a一),
反复利用这个方法,我们可以得到下面这组不等式:
l夕(s+,口+)一9(s+,口+一1)≥夕(s一,o+)一夕(s一,n+一1),
l 9(s+,n+一1)一9(s+,口+一2)≥夕(s一,矿一1)一夕(s+,o+一2),
△价.c i ;
l 9(s+,口一+2)一9(s+,o一+1)≥夕(s一,口一+2)一夕(s一,n一+1),
I 9(s+,o一十1)一9(s+,口一)≥夕(s一,n一+1)一夕(s一,a一),
把上边Aa个不等式的两边各自相加,得
9(s+,a+)一9(s+,口一)≥9(s一,n+)一9(s一,a一),
从而夕(s,o)是上可加的. 口
引理33设夕(s,a)是S X A上的实值函数,其中s={o,l⋯.),A=[0,1】.对所
有的8和任意的0≤a—S矿≤1,如果9(s,o)满足
9(s+1,o+)一9(s+1,a一)≥9(s,口+)一9(s,a一),
那么9(s,a)是上可加的.
证明Vs一≤s+,s+一s一=As≥0,s+,s一∈S,Va一≤a+,n+,a一∈A,若As=0,
显然有
夕(s+,a+)一夕(s+,a一)≥g(s-,a+)一g(s-,口一);
若△s>0,由假设条件可得
, AJI。,C
IL
夕(s+,n+)一9(s+,o一)≥g(8+一1,a+)一夕(s+一1,a一),
9(s+一1,口+)一g(S+一1,口一)≥9(s+一2,a+)一9(s+一2,口一),
g(s一+2,n+)~g(s一+2,口一)
夕(s一+1,口+)一9(s一+1,o一)
把上边△s个不等式的两边各自相加,得
≥g(s一十1,a+)一9(s一十1,口一),
≥g(s一,a+)一g(s-,口一),
g(s+,口+)一9(s+,o~)≥g(s-,口+)一9(s-,o一),
从而9(s,n)是上可加的. 口
连续时间MDP折扣模型的单调最优策略
以下几个引理给出了可加函数的一些重要性质:
引理3.4设g,h都是X×Y上的上(下)可加函数,Q,p为非负实数.则
Qg+{3h
也是X X Y上的上(下)可加函数.
证明直接用定义验证即可. 口
引理3·5例设夕是x×r_l:篚j_lz(下)可加函数,对每个z∈X,maXg(x,可)存在·

l(x)=max{矿∈arg maxg(x,秒)) (3.4)
yEY
是关于z的单调不减(不增)函数.
证明不减的情形参见文献[20】第104-105页的引理4.7.1.下证不增的情形.设
矿≥z一,Y≤,(矿).则根据,的定义,有
g(x+,f(x+))一9(x+,Y)≥0,
再由下可加函数的定义,有
9(x+,f(x+))+g(x一,Y)≤9(x+,Y)+g(x一,f(x+)).
对上面的不等式作移项,得
fg(x+,y(x+))一g(x+,Y)】+g(x一,Y)≤g(x一,f(x+)),
对照第一个不等式,可知对所有的Y≤i(x+),有
g(x一,Y)≤g(x一,f(x+)),
故,(矿)≤f(x一). 口
引理3·6设g是x×y上的上(下)可加函数,对每个z∈X,m掣∈arx g(x,可)存在·则
y(x)=rain{∥’∈argmaxg(x,可)) (3.5)
yEY

是关于z的单调不减(不增)函数.
证明只证不减的情形.设矿≥z一,Y≥y(x+).则根据,的定义,有
g(x+,f(x+))一g(x+,Y)≥0,
再由上可加函数的定义,有
g(x+,耖)+g(x一,f(x+))2 g(x一,Y)+g(x+,y(x+)).
对上面的不等式作移项,得
9(z一,f(x+))≥g(x一,Y)-I-【g(x+,f(x+))一g(x+,Y)】,
中山大学硕士学位论文
对照第一个不等式,可知对所有的Y≥,(矿),有
夕(z~,,(z+))≥g(z一,Y),
故,(z+)≥,(z一). 口
需要注意的是,当argmaxg(x,Y)只包含唯一一个元素时,(3.4)和(3.5)可以改写
l,∈y
成,(z)=argmaxg(x,秒).
yEY
引理3·7设9是x×y上的上(下)可加函数,对每个z E X,磐夕(z,y)存在·则
m)=maX{可’∈ar倒gmln9(z,秒))
是关于z钧单调不增(不减)函数.
证明只证不增的情形.设矿之z一,Y≤,(矿).则根据.厂的定义,有
9(z+,Y)一9(z+,,(z+))≥0,
再由上可加函数的定义,有
夕(z+,I(x+))+g(x一,Y)≥夕(z一,,(z+))+g(x+,Y).
对上面的不等式作移项,得’
g(x--Y)≥夕(z一,厂(z+))+【9(z+,Y)一9(z+,,(。+))】,
对照第一个不等式,可知对所有的Y≤,(矿),有
夕(z一,Y)≥g(z一,,(z+)),
故,(z+)≤,(z一).
(3.6)

引理3·8设夕是x×y上的上(下)可加函数,对每个z∈x,m掣∈iyn9(z,秒)存在·则
m)=mln{可7∈ar听gmyin9(z,可))
是关于z的单调不增(不减)函数.
证明只证不增的情形.设矿≥z一,Y≥,(z一).则根据厂的定义,有
g(x一,Y)一g(z一,f(x一))≥0,
再由上可加函数的定义,有
g(x+,Y)+g(x一,f(x一))≥g(x一,Y)+g(x+,,@一)).
对上面的不等式作移项,得
9(z+,Y)≥9(。十,,(z一))+[g(x-,Y)一夕(z一,,(z一))】,
对照第一个不等式,可知对所有的Y≥,(z一),有
9(z+,Y)≥夕(z+,I(x一)),
故,(2+)≤,(z一).
(3.7)

连续时间MDP折扣模型的单调最优策略
需要注意的是,当arg min g(x,Y)只包含唯——个元素时,(3.6)和(3.7)可以改写成
yEY
,(z)=arg rain 9(x,秒).
yEY
中山大学硕士学位论文25
§3.2期望折扣总报酬准则的单调最优策略
本节在期望折扣总报酬准则下讨论单调最优策略的存在性问题.为了使得定理2.6(或
推论2.1)得到的最优(平稳)策略是单调的,我们还要在该定理(或推论)的基础上对连续
时间MDP模型(2.1)中的状态空间,行动空间,报酬函数和转移速率加上更多限制条件.
假设状态空间s是全体非负整数组成的集合,且对所有的i∈S,有A(i)=A,显然
有U A(i)=A.
iES
下面将通过三个步骤证明最优平稳策略的单调性:
(1)首先用归纳法证明根据(2.19)、(2.21)和(2.22)定义的函数序列{铭住(i))n≥o和
IS*(i)在S上单调不减或单调不增;
(2)然后证明
咖):=端与re(⋯i)w伽蚶咖m) (3.8)
以及抓柚):=端+丽m(i)Σoo以跏蚓咖) (3.9)
是上可加或者下可加函数;
(3)最后证明在定理2.5(或推论2.1)基础上构造的最优平稳策略在S上单调不减
或单调不增.
我们先给出与步骤(1)、(2)密切相关的两个重要引理.
引理3.9‘冽设{xj}j>o,{弓b≥o是两个实值非负序列,对所有的非负整数七,满足
其中(3.10)当k=0时等号成立.另设序列{vjb_>o是单调不减的,即%+1≥吩,则有
oo 00
Σvixi≥Σ吻蟛, (3.1 1)
j=o j=o
其中(3.11)两边的极限存在(可等于无穷).
证明参见文献【20】第106页的引理4.7.2. 口
引理3.10设{xjb>o,{弓)j>o是两个实值非负序列,对所有的非负整数k,满足
哆O l∞
∞Σ:!fI 巧>一∞Σ似
弓O 屹
∞Σ滞q >一∞Σ似
连续时间MDP折扣模型的单调最优策略
其中(3.12)当k=0时等号成立.另设序列{vjb>o是单调不增的,即%+l≤%,则有
其中(3.13)两边的极限存在(可等于无穷).
证明设钐一l=0,对级数作变换,有
=Σ(吻一v,-1)Σ翰+VoΣ既
j=l i=,j i=0
00 ∞ ∞
≤Σ(vj—vs-·)Σz:+VoΣz:
j=a扛0 i=0
=Σ%弓,
(3.z3)
其中不等号的成立由(3.12)保证. 口
定理2.6(或推论2.1)给出了最优策略存在的条件,现在我们在它们的基础上进一
步给出保证函数序列Un({))n≥o和钍+(i)在S上单调的条件.假设对任意单调的函数
u∈玩(s),连续时间MDP模型中的以,r,g能够使得
磐{端+丽re(i)萎乱啪阢n)) (3.14)
达到上确界.这只需假设2.1,2.2,2.3(或2.4)成立,此时,上式可改写为
m口∈a¨x I Qr+(im,a【)万+ire⋯(i⋯)k。u(咖㈨,。)>. (3.15)
回顾算子T的定义(见(2.19)(2.20)),由于l|口ll:=sup q+(t)的性质可导致m(i)有
不同的取法,下面分两种情形进行讨论.
§3.2.1 lIgII<00的情形
因I|qlI<oo,选取m(i):=⋯I,Vi∈S.
定理3.2假设对任意单调的函数t‘∈玩,(S),(3.15)式可达到最大值且|J口II<oo,
若以下三个条件
(1)对所有的a∈A,r(i,口)是关于i∈S的单调不减(单调不增)函数;
o。
(2)对所有的口∈A和k∈S,ΣP(j[i,n)是关于i∈S的单调不减函数;
j=k
叼弓∞Σ:豆%巧<一∞Σ舢
魄一耽。歹Σ础巧∞Σ伽
% f| 吩∞Σ伽

∞Σ吲
% 一%_ ∞Σ倒
=
中山大学硕士学位论文
(3)w(i)是关于i∈S的单调不增(单调不减)函数;
成立,则u¨(i)(佗≥0)以及t‘‘(i)郡是关于i∈S的单调不减【早调/卜增)凼致·
证明由Il口lI<∞知m(t)=llgl|.下面用归纳法证明单调不减的情形:
由条件(3)知咖(t)是关于i∈S的单调不减函数,现假设对l=1⋯.,n,uL(i)是关
于i∈S的单调不减函数,下证牡n+1(乏)也是关于i∈S的单调不减函数.由(3.15)式可
达到最大值知对所有的i∈S,存在至少一个a㈨-*,使得
晰∽=搿{端+厕re(i)poo∽pm))
=觜<瑞+厕Ilqll圳铷啪删巾问)
==矧~O十t+鼎一妻’啪T工^I’M,-lJ蕊l 1lZ.‘小上:一-. +l|qIl。Q+㈣乞1¨川¨川”钆刖。
设i’≥i,i,i7∈S.由条件(1),(2)以及引理3.9,有
砌)=矧≮Ilq州ll%y础M巾,畦n)
≤矧+瑞篆00姒咖引以畦n) 二a+⋯。Q+⋯急叫H川H川q~一7
≤搿<瑞+热喜u删删㈡>
=乱n+1(i’),
由归纳法原理知{“n(i)}n≥o是关于i∈S的单调不减函数序列.此外,由上述论证可知,
对任意i’≥i,i,i’∈S,有
Un+l(i)≤un十1(i,)'
对不等式两边取极限.由极限的保序性可得
lira un+10)≤lira'Un+1(,),
n--*00 lrl--_00

u‘(i)≤钍+(t,),
从而u+(i)也是关于i∈S的单调不减函数.
同理可证单调不增的情形. 口
下面的定理将给出当II口II/o。时单调最优策略的存在性条件.必须指出的是,在单
调最优策略存在的同时,其它非单调的最优策略也有可能存在.
定理3.3假设对任意单调的函数u∈占0(S),(3.15)式可达到最大值且IIqlI<o。,
若以下五个条件
211 连续时间MDP折扣模型的单调最优策略
(1)对所有的a∈A,r(i,a)是关于i∈S的单调不减函数;

(2)对所有的a∈A和k∈s,Σp(Jli,a)是关于i∈S的单调不减函数;
j=七
(3)r(主,a)是S×A上的上可加(下可JJN)函数;

(4)对所有的k∈S,Σp(巾,a)是S×A上的上可加(下可加)函数;
j=k
(5)叫(i)是关于i∈S的单调不增函数;
成立,则存在最优平稳策略龙,T(i)(E,I(i))在i∈S上单调不减(单调不增)1.
证明只证存在单调不减的最优平稳策略的情形.首先证明由(3.8),(3.9)定义的
鲰(i,n),9+(i,a)都是上可加的.由条件(4)和上可加函数的定义知对所有的k∈S,以及
任意的i一≤i+(i一,i+∈S),o一≤n+a一,a+∈A)有
00 00
[p(jli-,吐一)+po卜+,口+)】≥Σ【poIt一,口+)+poK+,口一)】.
j=k
由条件(1)、(2)、(5)和定理3.2,知{‰(t)}n>o是关于i∈S的单调不减函数序列,乱+(i)
是关于i∈S的单调不减函数.故根据引理3.9,对所有的佗≥0,有
以及
因此,
是S×
以及

Σu.(j)[p(jli-,口一)+p(巾+,n+)】≥
j=o
Σ钍+(j)[p(jli-,口一)+p(矿,o+)】
j=o
i一,a+)+p(jli+,a一)】
一,a+)+p(jli+,a一)】,
A上的上可加函数,从而根据引理3.4,对所有的n≥0,有
都是上可加函数.
啪'n)=端+再m(丽i)萎oo u础)航。)
Σu.(j)p(j li,n)
j=o
州讪)=端+_re(⋯i)w倒让㈨pm)
1简单的单调平稳策略可以描述为。当i<f,时采用行动口l,当i≥i’时采用行动d2.实际上可以定义一般的单调平
稳策略.
Σ似
U 0 pU 妨都是匕可-#Ⅳ Ⅱ的由条件@ 知“ 回
∞Σ伽
∞ 和>一
U“力p◇ .% ∞ V 亿∞Σ伽
一口幽制
.} 韭叶^|⋯
矿U 珍0 妨
一口怕霸i丽∞Σ伽

盟叶妨一㈨
中山大学硕士学位论文
下面构造单调最优策略.令
£,T(i)=max at∈argm.axg+(i,o))
口∈A

尤,T(t)=rain{at∈argm.axg+(t,n)).
n∈A
由定理2.6知尤,T(i)是最优平稳策略,再由引理3.5,引理3.6知庀,t(i)在i∈S上单调不
减.对所有的钆≥0,又令
厶,T(i)=max at∈argmaxgn(i,o))
d∈A

厶,T(i)=min a’∈argmaxg,,(i,o)).
口∈A
由引理3.5,引理3.6知厶,t(i)在i∈S上单调不减,根据极限的保序性可知策略序列
{厶,t(z))n≥o在F中的每个极限点在i∈S上也单调不减;另一方面,根据定理2.6(或推
论2.1),可知这些极限点还是最优平稳策略,因此它们都是单调不减的最优平稳策略.
同理可证存在单调不增的最优平稳策略的情形. 口
定理3.4假设对任意单调的函数t‘∈上乙(S),(3.15)式可达到最大值且I|口|I<∞,
若以下五个条件
(1)对所有的a∈A,r(i,a)是关于i∈S的单调不增函数;
oo
(2)对所有的a∈A和尼∈S,Σp(jli,a)是关于i∈S的单调不减函数;
j=k
(3)r(i,a)是S×A上的上可加(下可加)函数;
oo
(4)对所有的七∈S,Σp(jli,a)是S×A上的下可加(上可加)函数;
j=k
(5)伽(主)是关于i∈S的单调不减函数;
成立,则存在最优平稳策略庀,t({)(亢,l(i))在i∈S上单调不减(单调不增).
证明只证存在单调不减的最优平稳策略的情形.首先证明由(3.8),(3.9)定义的
gn(i,o),94(t,n)都是上可加的.由条件(4)和下可加函数的定义知对所有的k∈S,以及
任意的i一≤{+(1一,i+∈S),n一≤o+(口一,a+∈A)有
oo oo
Σ[p(jli-,n一)+北n矿)】≤Σ【p(巾一,n+)+p(jli+,。一)】.
由条件(1)、(2),(5)和定理3.2,知{‰(i))n≥o是关于i∈S的单调不增函数序列,缸+(i)
是关于i∈S的单调不增函数.故根据引理3.10,对所有的n≥0,有
∞ ∞
Σun(j)[p(jli-,a-)+p(矿,口+)】≥Σ‰(歹)【p(舻,口+)+p(矿,n一)】
J=O j=o
连续时间MDP折扣模型的单调最优策略
以及
因此,Σun(j)p(jli,口)(V佗≥0)和Σu4(j)p(jli,n)都是上可加的.由条件(3)知r(i,a)
’=U ,=U
是S X A上的上可加函数,从而根据引理3.4,对所有的礼≥0,有
椭)=端+丽m(0薹姒m引柚)
=端!碉Ilqll po,,'-I--t-Iql Iql啪k 8) =一一’ Tt一●’,-T儿7IZ.,王-
Q I 卜Q+I l急岬n川H川q叫
以及
以锄)=端+丽m(0扣咖引锄)
==端=t一鼎驴一oo',-I--Tt-^Iqll伽引咖) 7,IT儿’JIZ.,EI Q+⋯。Q l急u川八川1⋯
都是上可加函数.
下面构造单调最优策略.方法与定理3.3证明中的构造方法完全相同,在此就不赘述
了.
同弹可证存在望调不增的帚优平稳箫略的情形. 口
注在单调最优平稳策略的构造中,当argmaxg+(t,a)或argmaxgn(i,n)∽≥0)只
aEA aEA
包含唯一一个元素时,龙,T(i),厶,T(i)可以分别改写成
龙,T(i)=argmaxg+(i,n)
口∈A

厶,T(i)=argmaxgn(i,a).
aEA
由于存在单调最优策略的那些条件很不容易验证,以下两个推论给出了保证单调最
优策略存在的其他类似条件,虽然没有降低验证的难度,但从另一个角度给出了一种验
证方式,它们的证明可参照定理3.3,3.4.
推论3.1假设对任意单调的函数让∈后0(S),(3.15)式可达到最大值且IIqll<∞,
若以下五个条件
(1)对所有的a∈A,r(i,a)是关于i∈S的单调不减函数;
oo
(2)对所有的o∈A和k∈S,Σp(Jli,a)是关于i∈S的单调不减函数;
j=k
(3)r(i,a)是S×A上的上可加(下可加)函数;


+
+ p ., +


U p .了
∞Σ:豆>一
+
0
+
+p 一


U p
∞Σ舢
中山大学硕士学位论文31

(4)对任意单调不减的函数钍∈B叫(s),Σu(j)P(jli,n)是S X A上的上可加(下可
j=o
加)函数;
C5)w(i)是关于i∈S的单调不增函数;
成立,则存在最优平稳策略定,t(主)(龙,l(乏))在i∈S上单调不减(单调不增)·
推论3.2假设对任意单调的函数仳∈最廿(S),(3.15)式可达到最大值且||g|}<00,
若以下五个条件
(1)对所有的a∈A,r(i,a)是关于i∈S的单调不增函数;
(2)对所有的a∈A和k∈S,Σp(jli,a)是关于i∈S的单调不减函数;
j=k
(3)r(i,a)是S X A上的上可加(下可加)函数;
(4)对任意单调不增的函数u∈五0(S),Σu(j)P(jli,a)是S X A上的上可加(下可
j=o
加)函数;
(5)w(i)是关于i∈S的单调不减函数;
成立,则存在最优平稳策略疙,T(i)(/2,l(z))在i∈S上单调不减(单调不增).
注上述讨论均在取仇(i)=Ilqll的情形下进行·事实上,如果Ilqll<oo,可以选取
m(i)=p为任意大于lIqll的正实数,此时只要在证明过程中把Il口Il换成卢,上述各结论
依然成立.
§3.2.2 Ilqll=OO的情形
因㈦I=00,取m(i)为任意满足m(i)≥矿(t)≥0的与i有关的正数.
定理3.5假设对任意单调的函数t‘∈五乙(S),(3.15)式可达到最大值且|lqIl二∞,
若以下四个条件
数;
(1)对所有的i∈S,a∈A,r(o,a)≤Oi
(2)对所有的。E A,端是关于t∈s的单调不增函数;
(3)对所有的n∈A和七∈s,誉糯和姜p(Jli,口)都是关于t∈s的单调不减函
(4)w(i)是关于i∈S的单调不减函数5
成立,则‰(t)(n≥0)以及牡+(i)都是关于i∈S的单调不增函数.
证明由IIg|I=oo知m(i)≥矿(1)≥0.由条件(4)知uo(i)是关于i∈S的单调不
增函数,另外,根据咖(t)的定义(见(2.21))和W≥1(见假设2.1),有咖(。)=一碉60M 一而M叫(。)≤。.
31 连续时间MDP折扣模型的单调最优策略
现假设对f=1⋯.,n,udO)≤0且uz(i)是关于i∈S的单调不增函数.下证un+1(o)≤0
且‰+1(1)也是关于i∈S的单调不增函数.由(3.15)式可达到最大值知对所有的i∈S,
存在至少—个n王n,使得
晰∽=搿{端
r(t,o纛)
a+m(i)
+羔薹蚴m))
+焉薹唰外删.
特别地,对i=0,存在至少一个ao‘.n使得
乱州(。)=max{r(O,a)而+万re丽(o)Σ钍础)帅’8))
==瑞I丽一m(O)Σoo-4-O一l m(o蚴引。,蝣一. ’ T工一f 1 Iz,I 1ll-,1. ●.
Q+m(o)’ + )怎岬¨州烈川v’Ⅶ一∥
于是,一方面,由条件(1),心n(o)≤0以及Un(i)是关于i∈S的单调不增函数可得
螂)=瑞+丽re(o)薹o。蚴引咖如)<0,
另一方面,由条件(2)、(3),设i7≤i,i,i’∈S,Un(-1)=0,则
缸n+t(i)=丽r(i,ai*n)+丽re(i)
r(茁,o;n)
=—————————-——一
Q+m(i)
r(t,《n) ==~
Q+m(i)
r(i,o妻n) =一Q+m(i) ≤蹦一Q+m(i’)
,.(i’,n:n) =Ot一+m(i7)
。+赢m(mi) Q+ (i)
。+赢m(i)
oo

ΣⅡn(歹)p(m nin)
j=o
∞ J
Σp㈨口in)Σ【‰(七)-‰(k-1)】
j=o k=O
∞ ∞
Σ
j=o
【‰(歹)一‰U一1)】Σp(kli,ai。,n)
+再re丽(i)ΣM沪钆n◇_1)】
。+满m(i’)
. +葫m(i7)
==一瑞++一五Q+m(矿) Q
m(i7)
+m(i’)
妻M)一啪_1)】妻m∥,畦H羔螂) j=l k--j 、7
1)】Σp(kli',ai‘,n)
tc-=j
≤搿{端+器薹蚓州㈠)
=un+l(t,)'

J
0

n
,,



@
)
p
0

k

口~

h卜
u
∞Σ罢Σ伽
中山大学硕士学位论文
由归纳法原理知{牡n(t))竹≥o是关于i∈S的单调不增函数序列.此外,由上述论证可知,
对任意i7≤i,i,i’∈S,有
‰+i(i)≤‰+1(i,)’
对不等式两边取极限,由极限的保序性可得
limⅡ竹+1(i)≤lim‰+l(∥), 竹—+oo rI—’∞

乜‘(i)≤U+(,),
从而让宰(i)也是关于i∈S的单调不增函数. 口
下面的定理将给出当IIqll=o。时单调最优策略的存在性条件.必须指出的是,在单
调最优策略存在的同时,其它非单调的最优策略也有可能存在.
定理3.6假设对任意单调的函数u∈玩,(S),(3.15)式可达到最大值且Ilqll=oo,
若以下六个条件
数;
(1)对所有的i∈S和a∈A,r(0,a)≤O;
(2)对所有的口E A,端是关于t∈Js的单调不增函数;
(3)对所有的a E A和七∈s,蔷‰和黑p(Jli,n)都是关于{∈s的单调不减函
(4)a“+m“(、i)一S×A上的上可加(下可加)函数;
⋯ oo (5)对所有的七∈S,蔷‰Σp(jli,口)是s×A上的下可加(上可加)函数;
,=尤
(6)w(i)是关于i∈S的单调不减函数;
成立,则存在单调的最优平稳策略e,T(i)(庀,J(i))在i∈S上单调不减(单调不增)·
证明只证存在单调不减的最优平稳策略的情形.首先证明由(3.8),(3.9)定义的
鲰(i,n),94(i,a)都是上可加的.由条件(5)和下可加函数的定义知对所有的k∈S,以及
任意的i一≤i+0一,i+∈S),a一≤o+(o一,a+∈A)有薹[端幻旷∥)+器砌旷’口+)】
≤薹【器p眠n+)+端p呲口-)】.
由条件(1)、(2)、(3)、(6)和定理3.5,知{un(t))n≥o是关于i∈S的单调不增函数序
列,缸‘({)是关于i∈S的单调不增函数.故根据引理3.10,对所有的n≥0,有篆00【舞高北旷∥)+端砌旷'0+m础)
连续时间MDP折扣模型的单调最优策略
≥三oo‘而re(i丽-)幻旷’n+)+篙斋黼口.)】姒趴
壹[舞斋幻旷∥)+舞稿北旷'0+mⅦ)j=o ≥萎00[器砌旷,0+)+舞翁砌旷∥m坳).
因此,誉‰曼钍n(J)P(Jli,。)和高‰呈.·(J)P(Jli,n)都是上可加的.由条件(4)知端是因此,誉‰Σ钍n ,o)和署‰.。‘ ,n)都是上可加的·由条件(4)知畜崭裔是.4 ---一u(J)P(Jli ,E=u
u(J)P(Jli
S X A上的上可加函数,从而根据引理3.4,对所有的n≥0,有
蜘)=端+羔≤OO蚓比Ii'。)
以及¨讪,=端+羔薹u铡JIi,a,
都是上可加函数.
下面构造单调最优策略.方法与定理3.3证明中的构造方法完全相同,在此就不赘述
了. 口
类似推论3.2,当IIqll=∞时我们也有以下推论.其证明可参见定理3.6.
推论3.3假设对任意单调的函数钍∈Bw(s),(3.15)式可达到最大值且IIqlI=oo,
若以下六个条件
(1)对所有的i∈S和a,6 A.,r(o,a)≤o;
(2)对所有的n∈A,署蒜是关于i∈s的单调不增函数;
(3)对所有的。∈A和七∈S,苦‰和置poIi,n)都是关于{∈s的单调不减函
数;
,.
(4)未禹%是S×A上的上可加(下可加)函数;
(5)对任意单调不增的函数牡∈玩(s),石m丽(O两Σu(j)p(jli,n)是s×A上的上
j=o
可加(下可加)函数;
(6)w(i)是关于i∈S的单调不减函数;
成立,则存在单调的最优平稳策略庀,,(z)(龙,I(i))在i∈S上单调不减(单调不增).
当IIqll=00,m(i)为与i有关的正数时,我们不能忽略m(i)的变化.而m(i)的变化
正好导致了定理3.2与定理3.5之间的以下几点差异:
中山大学硕士学位论文
第一,要使得‰(i)(n≥0)以及让‘(i)都是关于香∈S的单调不增函数,定理3.5在定
理3.2的基础上对r(o,a)加上非正性条件.
第二,在用归纳法证明un+1(i)是关于i∈S的单调不增函数过程当中,由于对
i7≤i,i,i7∈S,
端扣锄∽=器争以n::n,
不一定成立,因此引理3.10不再适用.
第三,定理3.5没有给出使得‰({)∽≥0)以及t‘+(i)都是关于i∈S的单调
不减函数的条件.为什么呢?对照定理31,我们可能会推测:假设对任意单调的函数
让∈点0(S),(3.15)式可达到最大值且lIqlI=o。,只要以下四个条件
数;
(1)对所有的i∈只a∈A,r(o,o)≥o;
(2)对所有的n∈A,者耥是关于i∈S的单调不减函数;
(3)对所有的口∈A和k∈S,蔷糯和曼p(外,口)都是关于i∈s的单调不减函。’ '=拧
(4)w(i)是关于i∈S的单调不增函数5
成立,则Un(i)(礼≥0)以及矿(i)都是关于i∈S的单调不减函数.而事实上,我们会发现
即使以上四个条件成立,利用类似(即单调不增情形)的方法也无法保证‰(i)(n≥0)以
及乱+(i)都是关于i∈S的单调不减函数.这是因为在用归纳法证明‰+1(主)是关于i∈S
的单调不减函数过程当中(见定理3.5),钆n(0)≥0不一定成立.
那么,在什么情况下,由上面四个条件可以得到Un({)(n≥0)以及牡+(虿)都是关于
i∈S的单调不减函数呢?。经过进一步研究,我们可以发现只需对前面定义的期望折扣总
报酬最优准则稍作修改,变为期望折扣总费用最优准则,见下一节定理3.10.
连续时间MDP折扣模型的单调最优策略
§3.3期望折扣总费用准则的单调最优策略
定理2.9和推论2.2分别给出了在期望折扣总费用准则下最优策略的存在条件.下面
我们在新准则下讨论单调最优策略的存在性问题.与之前类似,为了使得定理2.9(或推
论2.2)得到的最优(平稳)策略是单调的,我们还要在该定理(或推论)的基础上对连续
时间MDP模型(2.1)中的状态空间,行动空间,报酬函数和转移速率加上更多限制条件.
假设状态空间S是全体非负整数组成的集合,且对所有的i∈S,有A(i)=A,显然
有U A(i)=A.
{∈S
下面将通过三个步骤证明最优平稳策略的单调性:
(1)首先用归纳法证明根据(2.27)、(2.29)和(2.30)定义的函数序列{%(i))n≥o和
矿(i)在S上单调不减或单调不增;
(2)然后证明
咖):=端+-re(⋯i)w触勘㈨和)
以及z砸,口):=端+厕m(i)驴oo咖引锄)
(3.16)
(3.17)
是上可加或者下可加函数5
(3)最后证明在定理2.9(或推论2.2)基础上构造的最优平稳策略在S上单调不减
或单调不增.
定理2.9和推论2.2给出新准则下最优策略存在的条件,现在我们在它们的基础上进
一步给出保i正fl!i数序列{‰(t)】.n≥o和t,+(t)在S上单调的条件.假设对任意单调的函数
t,∈民(S),连续时间MDP模型中的A,r,q能够使得
剃inf[LQc十m((i,a)万+焉争城巾㈠) (3.18)
达到下确界.这只需假设2.1,2.4(或2.6),2.5成立,此时,上式可改写为
赌{端+焉扣槲㈠). B-∞
回顾算子L的定义(见(2.27)(2.28)),由于II口ll:=supq+(i)的性质可导致m(i)有
不同的取法,下面同样分两种情形进行讨论.
§3.3.1 Il口|l<00的情形
因|IqlI<(30,选取m(i):=⋯I,Vi∈S.
中山大学硕士学位论文37
定理3.7假设对任意单调的函数钞∈三乙(S),(3.19)式可达到最小值且IIqlI<o。,
若以下三个条件
(1)对所有的o∈A,c(i,D)是关于i∈S的单调不减(单调不增)函数;

(2)对所有的a∈A和k∈S,Σp(Jlt,口)是关于i∈S的单调不减函数;
j=k
(3)叫(z)是关于i∈S的单调不减(单调不增)函数;
成立,则‰(i)(佗≥0)以及移4({)郡是关于/∈S的单调不减(单调不增)iiti敦.
证明由Ilqll<CO知m(t)=Ilqll·下面用归纳法证明单调不减的情形:
由条件(3)知v0(i)是关于i∈S的单调不减函数,现假设对l=1⋯.,n,叻(1)是关
于i∈S的单调不减函数,下证‰1(i)也是关于i∈S的单调不减函数.由(3.19)式可
达到最小值知对所有的i∈S,存在至少—个o:n,使得
啪)=赌{端+丽re(i)三o。砌p引和))
=卿<端+瑞三00啪从巾㈠>
:矧I揣Σ0蚓p(Jl碱ai,-'1-I 小ql-t-lql =一一' 口LI 1 lfl Z. 1.
Q+l I’Q l I急Ⅵw∥q刑。
设i7≤i,i,{7∈S.由条件(1),(2)以及引理3.9,有
啪)=矧坷Ilq州ll%一。咖捌㈣
二≥-矧Q++⋯鼎‘OC+I IqIl急薹Ⅵ八蚴川引n川qt飞0:一:t17)
≥卿<端+而Ilqll≤蚓北F㈠)
=%+1(i’),
由归纳法原理知{%(1))n≥o是关于i∈S的单调不减函数序列.此外,由上述论证可知,
对任意i’≤i,Z,t’∈S,有
%十i(i)≥Vn+1(i,)’
对不等式两边取极限,由极限的保序性可得
lim%+1(i)≥lim%+i(i7),
n—+∞ n--+00

t,+(茁)≥t,‘(i,)'
从而口+(i)也是关于i∈S的单调不减函数.
同理可证单调不增的情形. 口
连续时间MDP折扣模型的单调最优策略
下面的定理将给出当IIqlI<OO时期望折扣总费用准则下单调最优策略的存在性条
件.必须指出的是,在新准则下的单调最优策略存在的同时,其它非单调的最优策略也有
可能存在.
定理3.8假设对任意单调的函数移∈玩(S),(3·19)式可达到最小值且llqll<00,
若以下五个条件
(1)对所有的a∈A,c(i,a)是关于i∈S的单调不减函数;

(2)对所有的a∈A和k∈S,Σp(jli,a)是关于i∈S的单调不减函数;
j=k
(3)c(i,a)是S×A上的上可加(下可加)函数;
OO
(4)对所有的k∈S,Σp(Jli,a)是S×A上的上可加(下可加)函数;
j=k
(5)w(i)是关于i∈S的单调不减函数;
成立,则存在最优平稳策略龙,l(i)(丘,T({))在i∈S上单调不增(单调不减).
证明只证存在单调不增的最优平稳策略的情形.首先证明由(3.16),(3.17)定义的
Zn(t,n),z+(i,a)都是上可加的.由条件(4)和上可加函数的定义知对所有的k∈S,以及
任意的i一≤t+(i一,{+∈S),a一≤n+a一,a+∈A)有
00 00
>二[p(jli-,口一)+p0Ii+,n+)】≥芝二[p(jli一,口+)+p0卜+,口一)】.
J=七j=k
由条件(1)、(2)、(5)和定理3.7,知{%(t))n≥o是关于,i∈S的单调不减函数序列,矿(i)
是关于i∈S的单调不减函数.故根据引理3.9,对所有的n≥0,有
以及
因此,妻v.(j)p(jli,o)(V礼≥o)和主v*(j)p(jli,口)都是上可加的.由条件(3)知c(i,n)
’=U ,刮
是S X A上的上可加函数,从而根据引理3.4,对所有的n≥0,有
咖)=端+丽re(i)≤oo蚴m)
=端+鼎Iql薹蚴m, Q+lI口lI。Q+I l急v’H川州r,7
以及
州如,=端+高争咖蚓锄,

D
+
+p +


‰ .了p
∞Σ伽>一


+
+ p ., 一
0

% p .了
∞Σ触


+
+ p
}


移p
∞Σ触>一
+

}
+ p ., 一
0

移., p
∞Σ伽
中山大学硕士学位论文39
=端+揣壹嘞啡柚j=o J =~+————‘~'TJ I 1 l"l lZ.nl
a十¨口lI Q十¨口|I“ ’
都是上可加函数.
下面构造单调最优策略.令
£,J({)=max{∥∈arg rain z+(1,n))
d∈A

£,J(乏)=min Up∈argm.inz+(i,o)),
口∈^
由定理2.9知庀,I(主)是最优平稳策略,再由引理3.7,引理3.8知名,J(i)在i∈S上单调不
增.对所有的n≥0,又令
厶,j(主)=max{∥∈argmin z,。(i,o))
o∈^

厶,j(茁)=min{∥∈argrain z.(i,n)),
口∈A
由引理3.7,引理3.8知厶,J({)在i∈S上单调不增,根据极限的保序性可知策略序列
{厶,I(t))n≥o在F中的每个极限点在t∈S上也单调不增;另一方面,根据定理2.9(或推
论2.2),可知这些极限点还是最优平稳策略,因此它们都是单调不增的最优平稳策略.
同理可证存在单调不减的最优平稳策略的情形. 口
定理3.9假设对任意单调的函数t,∈鼠,(S),(3.19)式可达到最小值且lIqll<OlD,
若以下五个条件
(1)对所有的a∈A,c(i,a)是关于i∈S的单调不增函数;
oo
(2)对所有的o∈A和k∈S,Σp(jli,G)是关于i∈S的单调不减函数;
j=k
(3)c(i,a)是S×A上的上可加(下可加)函数;
oo
(4)对所有的k∈s,Σp(Jli,a)是S×A上的下可加(上可加)函数;
j=詹
(5)w(i)是关于i∈S的单调不增函数;
成立,则存在最优平稳策略庀,l(i)(E,t(主))在i∈S上单调不增(单调不减).
证明只证存在单调不增的最优平稳策略的情形.首先证明由(3.16),(3.17)定义的
磊(i,口),z+(t,a)都是上可加的.由条件(4)和下可加函数的定义知对所有的七∈S,以及
任意的i一5 l+({一,{+∈S),a一≤o+(口一,口+∈A)有
∞ 00
Σ【p(旷,口一)+p(舻,矿)】≤Σ【p(矿,n+)+ponn一)】.
j=k J=七
连续时间MDP折扣模型的单调最优策略
由条件(1)、(2)、(5)和定理3.7,知{%(i)}n>0是关于i∈S的单调不增函数序列,矿(t)
是关于i∈S的单调不增函数.故根据引理3.10,对所有的扎≥0,有
以及
因此,Σvn(j)P(jli,口)(V礼≥0)和Σt,‘(J)P(Jli,n)都是上可加的.由条件(3)知c(i,a)
':=U ,=U
是S×A上的上可加函数,从而根据引理3.4,对所有的佗≥0,有
咖,=端+羔砉蚓pm,
==端~+揣-+I-一Iql薹砌砌k。) , TJ—l 1 17¨’,lZ,正I Q+⋯’Q I I急ⅥH川八川q叫
以及
引柚)=端+丽re(i)poo∽砒∞
==瑞~·瑞po一o-t-Iql∽砌k。) , ’,I,,If¨1lZ,L l
Q+IIgII。Q+I I急u川n川q叫
都是上可加函数.
下面构造单调最优策略.方法与定理3.8证明中的构造方法完全相同,在此就不赘述
了.
同弹可证存在望调不减的晶优平稳管略的情形. 口
注在单调最优平稳策略的构造中,当argminz4(i,a)或argminz,,(i,口)∽≥0)只
aEA aEA
包含唯一一个元素时,龙,l(i),厶,J(i)可以分别改写成
层,l(i)=arg min z+({,D)
a∈A

厶,l(i)=argminzn(i,a).
aEA
下面两个推论给出了保证单调最优策略存在的其他类似条件,它们的证明可参照定
理3.8,3.9.
推论3.4假设对任意单调的函数口∈鼠,(S),(3.19)式可达到最小值且IIqlI<∞,
若以下五个条件

n
+
+p +


% p
∞Σ!豆>一
+
0
+ + pG 一


‰ p .J
∞Σ:豆


+
+矽
+


钞p
∞Σ伽>一
+
n
+
+ p 一


秒p .J
∞Σ触
中山大学硕士学位论文41
(1)对所有的Q∈A,c(i,a)是关于i∈S的单调不减函数;
(2)对所有的a∈A和詹∈s,Σp(jli,口)是关于i∈S的单调不减函数;
j=膏
(3)c(i,口)是S×A上的上可加(下可加)函数;
(4)对任意单调不减的函数t,∈玩(S),Σv(j)p(jli,a)是S X A上的上可加(下可
j=o
加)函数;
(5)协(i)是关于i∈S的单调不减函数;
成立,则存在最优平稳策略龙,l(i)(龙,t(i))在i∈S上单调不增(单调不减).
推论3.5假设对任意单调的函数t,∈鼠,(S),(3.19)式可达到最小值且|fg|I<(30,
若以下五个条件
(1)对所有的a∈A,c@,o)是关于i∈S的单调不增函数;
(2)对所有的a eA和k∈S,Σp(yli,a)是关于i∈S的单调不减函数;
j=k
(3)c(i,a)是S×A上的上可加(下可加)函数;
(4)对任意单调不增的函数秒∈玩(s),Σv(j)p(jli,a)是S×A上的上可加(下可
j=o
加)函数;
(5)w(i)是关于i∈S的单调不增函数;
成立,则存在最优平稳策略龙,l(t)(宽,t(i))在i∈S上单调不增(单调不减).
注上述讨论均在取m(i)=lIqlI的情形下进行.事实上,如果lIqlI/OO,可以选取
m(i)=p为任意大于l|口II的正实数,此时只要在证明过程中把IIglI换成卢,上述各结论
依然成立.
§3.3.2 IIqlI=OO的情形
因lIqlI=OO,取m(i)为任意满足m(i)≥g+(t)≥0的与i有关的正数.
定理3.10假设对任意单调的函数钉∈点乙(s),(3.19)式可达到最小值且lIqll=00,
若以下四个条件
数;
(1)对所有的i∈S,口∈A,c(o,a)≥0; 2)对所有的口∈A,器是关于i∈s的单调不减函数;
(3)对所有的口∈A和后∈s,嚣‰和曩poIt,。)都是关于i∈s的单调不减函,=K
(4)w(i)是关于i∈S的单调不减函数5
成立,则‰({)(n≥0)以及秒‘(t)都是关于i∈S的单调不减函数.
证明由IIqll=oo知m(i)≥q+({)≥0.由条件(4)知%(i)是关于i∈S的单调不
42 连续时间MDP折扣模型的单调最优策略
郴)=害与+而M呻)>0.
现假设对l=1⋯.,n,vz(O)≥0且忱(i)是关于i∈S的单调不减函数.下证Vn+l(o)≥0
且%+1(i)也是关于i∈S的单调不减函数.由(3.19)式可达到最小值知对所有的i∈S,
存在至少一个ai‘,n,使得
帅(1)=rain(c(i,a)万+再re(丽i)篆oo%咖啡,口))
==——篇———-—4—_I二—-一器m一(i薹’砌/',1一的I口¨,nI'kIt,引l:.l
Q+m(t)’Q+ )白ⅥuJ V r’’一∥
特别地,对i=0,存在至少一个a0‘m使得
帅(0)=ma叫in,Q.c+(Om,a()可+再re丽(o)≤。o啪)p∽,n)>
=瑞+丽re(O)善oom(O咖川帅b). Q+m(0)‘Q+ )勺v’‘、川¨川v’wu—r
于是,一方面,由条件(1),%(o)≥0以及%(i)是关于i∈S的单调不减函数可得螂)=篇+焉喜咖引070;_>o'
另一方面,由条件(2)、(3),设i’≤i,i,i’∈S,‰(一1)=0,则
嘶)=蔫+焉Σ00嘞引和釉
=篇+确re(i)Σp州")争㈤叫¨)】
=瑞+确re(i)驴小嘶_1)】争k《n)
=篇+确re(i)驴砌-1)】酗和柚+器岬)
≥端+高洳h㈣峥砷’以H端们,
=瑞+器争∽-咖驯争t训
=瑞+器薹嘞㈦以引
≥rain{c(i',a)万+焉壹蚴㈨口))j=o
中山大学硕士学位论文
=vn+1(i,)'
由归纳法原理知{‰(i))竹≥o是关于i∈S的单调不减函数序列.此外,由上述论证可知,
对任意i7≤i,i,i7∈S,有
%+1(i)≥Vn+l(i7),
对不等式两边取极限,由极限的保序性可得
lira Vn+1(i)≥lim%+1(i,),

矿(吾)≥矿(i,)'
从而口’(t)也是关于i∈S的单调不减函数. 口
下面的定理将给出当lIqlI=o。时期望折扣总费用准则下单调最优策略的存在性条
件.必须指出的是,在单调最优策略存在的同时,其它非单调的最优策略也有可能存在.
定理3.11假设对任意单调的函数V∈上乙(s),(3.19)式可达到最小值且lIqlI=∞f
若以下六个条件
数;
(1)对所有的i∈S和a∈A,c(o,a)≥O; 2)对所有的a∈A,端是关于i∈s的单调不减函数;
(3)对所有的。∈A和尼∈s,啬犏和萎p(歹I主,口)都是关于t∈s的单调不减函’’ ,=詹.
(4)署端是s×A上的上可加(-F,--J2Ⅱ)函数;
⋯ oo (5)对所有的七∈s,器Σp(j[i,o)是s×A上的上可加(-F,-f力n)函数; ,=尤
(6)w(i)是关于i∈S的单调不减函数;
成立,则存在最优平稳策略£,J(t)(尤,T(。))在i∈S上单调不增(单调不减)·
证明只证存在单调不增的最优平稳策略的情形.首先证明由(3.16),(3.17)定义的
zn(i,o),z+(i,a)都是上可加的.由条件(5)和上可加函数的定义知对所有的k∈S,以及
任意的i一≤i+(蕾一,i+∈S),a一≤口+a一,a+∈A)有
ΣOO【舞斋比旷'0.)+舞斋p蚓一∽】
≥妻【舞高舯矿)+舞‰砌旷'n_)】.
由条件(1)、(2)、(3)、(6)和定理3.10,知{%(t)>n≥o是关于1i∈S的单调不减函数序
列,t,+(i)是关于i∈S的单调不减函数.故根据引理3.9,对所有的他≥0,有薹【器如I{.,0_)+高幻旷∽M)
连续时间MDP折扣模型的单调最优策略
以及
≥薹【端pm∽+嵩砌Ii+,n—M
薹f器p眦口-)+蔫粹m∽妒u)
≥薹【器pm口+)+端删’口.mM.
⋯ ∞ oo ,.、
因此,誉‰量%(歹)p(JI{,n)和叶mm(O(∞堇秽‘(J)p(j Ji,口)都是上可加的.由条件(4)知若鬟裔是
S×A上的上可加函数,从而根据引理3.4,对所有的亿≥0,有
咖)=端+确re(i)Σo。咖m)
以及以锄,=端+羔争啪k。,
都是上可加函数.
下面构造单调最优策略.方法与定理3.8证明中的构造方法完全相同,在此就不赘述
了. 口
类似推论3.4,当IIqll=o。时我们也有以下推论.其证明可参照定理3.8.
推论3.6假设对任意单调的函数移∈三乙(S),(3.19)式可达到最小值且⋯I=∞,
若以下六个条件
(1)对所有的i∈S和a,E A、,c(o,o)≥o;
(2)对所有的n∈A,舞耥是关于t∈S的单调不减函数;
(3)对所有的。∈A雨il k∈s,嚣‰和三pGfi,口)都是关于蕾∈s的单调不减函
数;
,, (4)署褊是S×A上的上可加(下可加)函数;
(5)对任意单调不减的函数钞∈玩(s),啬‰Σv(j)P(j Ji,o)是s×A上的上
j=o
可加(下可加)函数;
(6)伽({)是关于i∈S的单调不减函数:
成立,则存在最优平稳策略庀,J(t)(龙,t(i))在i∈S上单调不增(单调不减).
可见,本节在期望折扣总费用准则(见定义2.10)下得到的绝大多数结论都是上一
节在期望折扣总报酬准则(见定义2.6)下得到的结论的平移.表面上,它们之间最大的
中山大学硕士学位论文45
差异主要体现在当lIqll=oo时,在期望折扣总报酬准则下如果要保证单调最优策略的存
在性,那么r(o,a)必须非正且‰(i)m≥0)以及u+(i)都只能是关于i∈S的单调不增函
数;丽在期望折扣总费用准则下c(o,a)必须非负且‰(i)(竹≥0)以及移+(t)都只能是关于
i∈S的单调不减函数.
但是,只要经过仔细的观察和比较,我们不难发现,在本文给出的单调最优策略存在
的条件下(分别见定理3.6与定理3.11),两种最优准则的最优策略的作用都是使得报酬
(或费用)的绝对值的总折扣期望最小,即
期望折扣总报酬准则:对所有的主∈S a∈A,r(o,a)≤0,7r=(死)∈H,有
嵋(∞=s,truepn霹fLZ。0e刊r(雄),丌t)叫=一翳霹[Z∞e吨tlr(邢),仉)l司,
期望折扣总费用准则:对所有的i∈S a∈A,c(o,a)≥0,7r=(71"t)∈Ⅱ,有
龙(i)=瓣霹[//e-Qtc(雄),几)叫=+瓣霹[fo e刊lc(邢),几)l司.
因此,我认为两种折扣最优准则没有本质上的区别.
连续时间MDP折扣模型的单调最优策略
§3.4两个例子
本节利用两个具有实际背景的例子来进一步阐明前文关于单调最优策略存在的结果
和条件.
例3.1 (设备维修系统的最优控制)考虑一个设备维修系统.在制造过程中有一
台设备在运行,在每个决策时刻t≥0,可以观察到它的运行状态(即系统状态)为
i∈S={O,1,2⋯.).运行状态的数值越大表示该设备的运行条件越差.假设该设备
随时都有可能发生状态转移,换句话说,系统状态在时间轴T=[0,oo)中连续地发生变
化.在决策时刻之间设备磨损等级增加歹个的概率是p(J)(不依赖当前的状态).在每个
决策时刻,若系统处于状态i,决策者能够根据需要及时在集合A(i)三A={o,1)中选取
的—个行动,其中行动a=0表示让设备继续运作,而行动a=1表示立即更换一个完全
相同的新设备(假设更换新设备不需要时间).决策者每选取一次行动,都会得到一个恒
定的报酬R>0;但同时还要支付与设备状态相关的运行费用c(i),c(i)关于状态i单调
不减;以及更换新设备的费用G>0(如果决定更换的话).这里的问题是:是否有一个
方法,使得报酬在某种目标下达到最大.
现在我们建立一个连续时间MDP模型以刻画这个系统.上文已经给出模型的决策
时刻集T,状态空间S和行动空间A对任意的t,J∈S,a∈A,定义相应的转移速率
q(jli,a)和报酬函数r(i,a)如下。
1 0, “2,
q(jli,0):={p(o)一1, 歹=i, (3.20)
I p0一i), 歹>i;
柏k聃=馏,_1, 置n2-,
砸,小:fR叫@)' a--O,
(3-22)
Il R—c(o)一G三尉, n=1;
这里运行的费用c(i)关于状态i单调不减表示设备状态越差,需要支付的运行费用越高.
我们的目标是寻找条件以保证在期望折扣总报酬准则下单调最优平稳策略的存在性.
考虑以下几个条件;
cl·用Y记具有概率分布p(歹)的随机变量.Y服从参数为p(o<P≤1)的几何分
布:P(Y=』)=p(J)=p(1一p)J,歹=0,1⋯.
C2.Q—lip>0,其中Ot为某给定的折扣因子.
C3.存在一个常数面>0,使得o<c(i)≤磁i+1),i=o,1⋯.
经过仔细验证,我们能够得到以下结论.
中山大学硕士学位论文47
命题3.1在条件C1,C2,C3成立的情况下,上述设备维修系统连续时间MDP模
型满足假设2.1,2.2和2.4.因此,根据推论2.1,该决策模型存在至少一个折扣最优平稳
策略.而且,在这些(如果多于一个)折扣最优平稳策略中,存在至少—个关于状态i∈S
单调不减.
证明首先验证假设2.1.对所有的i∈S={o,1,2⋯.),令w(i):=i+1,Lo:=1.
由(3.20),(3.21)知
口“Ii,。,。{:舅二:』na:----Ol;’
根据q4(寡)的定义(见(2.4)),可得
口宰(t)=sup[--q(ili,a)】≤1.≤i+1=Low(i), Vi≥0.
此外,由C1以及(3.20),(3.21),对口=0,有
Σw(j)q(jli,o)=伽o)[p(o)一l】+Σw(j)p(j—i)
=伽“)p(o)一硼(i)+Σ叫o+主)po)
. j=l
=Σ叫o+i)p◇)一钮G)
邓“+字)邓“)
1·——P
≤;伽(i),Lo, Vi≥o·
对a=1,有
Σw(j)q(jli,1)=伽(i)∽)一1】+ΣⅢ(歹)p(歹)
j=o j#i
=Σ伽(加(j)-w(i)
j=o
=;1一(t+1)
≤;1叫(i)+‰,V{≥。.
令60:=Lo,co:=1/p,可知假设2.1成立.
然后验证假设2.2.由C3以及(3.22)可得
Ir(t,口)I 5(M+R十a)w(i), Vi≥0,
取M:=M+R+G,再由C2可知假设2.2成立.
45 连续时间MDP折扣模型的单调最优策略
最后验证假设2.4.对所有的i∈S,令W他):=伽(i),M’:=Lo,∥:=cD,6,:=bo,由
以上三个不等式可知

旷(t)叫@)≤M'w7(主) ,芝二伽7(j)q(Jli,口)≤c'w7(i)+6,
i=o
对所有的(i,a)∈K:={(i,a)li∈S,a∈A(i))都成立.再由行动空间A有限可知假设2.4
成立.
因此,根据推论2.1,该决策模型存在至少一个折扣最优平稳策略.
F面利用推论3.2证明在从刚才得到的折扣最优平稳策略中,至少存在一个关于状
态i∈S单调不减.由(3.20),(3.21)易知
IIqll:=sup g+(i)≤1<+oo.
选取m({)=1,对所有的(i,a)∈K,令
p(jli,a):=掣+如=㈣(Jl n)+如,
其中如表示Kronecker’s delta.于是有
p。k。,2{三己一;,, ;主:;
p(jli,1)=p(J), 歹≥0.
由于该决策模型存在至少—个折扣最优平稳策略,这意味着对任意单调的函数U∈玩(S),
搿{端+焉挚蝴问)
可达到最大值.此时我们只需逐一验证该决策模型满足推论3.2的五个条件.
(1)由(3.22)以及c(1)关于状态i单调不减,可知对固定的a=1或a=0,r(i,a)
都是关于状态i单调不增的函数,其中i∈S.
(2)对n=1,有
因此Σ器七p(jli,1)与状态i无关的,这时可认为它关于i单调不减.对a=0,定义
Ap(k,i):=Σp(jli+1,o)一Σp(jli,o), Vk≥o,i≥0,
j=k j=k
于是有
△pc豇,t,=‘j羔=k【p。一;一1,一p。一。,,, k≤i,
k≥i;
0
>一
O
>一
p◇ V后∞Σ:!l
p0 .钆1 |I ∞Σ:lI
中山大学硕士学位论文49
故△p(后,i)≥0,对所有的k≥0,Σ嚣知P(jli,o)也关于状态i单调不减.
(3)由(3.22)以及c(i)关于状态i单调不减,对任意的i∈S可得
rG+1,1)一r“+1,0)=c(i+1)≥c(i)=r(i,1)一r(i,0),
故根据引理3.1,r(i,a)是S×A上的上可加函数.
(4)对任意单调不增的函数t‘∈战(S),t,J∈S有
ΣP(jli+1,1)钍(歹)一ΣP(jli+l,o)让(歹)
i=o i=o
=Σp(歹)u(J)一Σpo—i一1)u(歹)
i=o j=i+l
=Σp(J)让(歹)一Σp(j)u(j+t+1)
j=o i=o
≥Σp(歹)u(J)一Σp(j)u(j+t)
i=o j=o
=Σpo)乱o)一Σpo—i)钍o)
j=o i=i
=ΣP(jli,1)钍(歹)一Σp(Jli,o)牡(歹),
故根据引理3·l,Σ凳op(外,1)u(,)也是s×竺上的上司加凼效。
(5)回顾bo=Lo=1,co=1/p,M=M+R-!-G,w(i)=i+1以及C2,对任意的
i∈S,令u。(i):=一碉boM一而M叫(主) uo∽2一砾i可一ii叫㈣
一瓮等一等学㈦-t-1 1), :==一———-——------—--:---一~●Z l I.
Q(Q一;) Q一;
r。工,’
可知咖(t)是关于状态i∈S的单调不增函数.得证! 口
可见,该决策模型满足推论3.2的所有条件和假设,从而存在至少一个折扣最优平稳
策略在i∈S上单调不减.又因为行动集A(i)=A只包含两个行动,所以,存在一个状
态i+,使得当i≥i’时,决策者的最优选择是立即更换新设备;当i<i’时,决策者的最
优选择是让设备继续运作一段时间.
在设备维修系统的最优控制例子当中,我们在期望折扣总报酬准则下讨论单调最优
平稳策略的存在性,其中模型的转移速率q(jli,a)有界,A(i)三A中的行动离散且个数
有限.
而在下面给出的另一个例子当中,我们将在期望折扣总费用准则下讨论单调最优平
稳策略的存在性,其中模型的转移速率q(jli,a)无界,A(i)兰A中的行动连续且不可数.
连续时间MDP折扣模型的单调最优策略
例3.2 (有迁移生灭系统的最优控制)考虑一个受控的有迁移生灭系统,它可用于
描述生物再生和人口增长过程.这里的状态表示在任意时刻t≥0时系统中的群体总量,
将在T=f 0,(20)中连续地发生变化.群体中每个个体的自然出生率和死亡率分别是非负
常数A和p.同时,群体受外界的影响又以系数h增加或减少,该系数的大小受决策者
控制.当系统处于状态i∈S:一---{o,1⋯.)时,决策者在给定的行动集A(i)三A=[o,1】
中选取行动a以改变迁移系数h(i,a)的大小,他也因此得到一定的报酬r(8),其中行动
a=0表示控制强度最低,而行动a=1表示控制强度最高.此外,决策者还得在系统逗
留在状态i的期间支付一定的维护费用伽+∥,其中Po>0是初始费用,P>0是固定的
费用系数.这里的问题是:是否有一个方法,使得费用在某种目标下达到最小.
现在我们建立一个连续时间MDP模型以刻画这个系统.上文已经给出模型的决策
时刻集T,状态空间S和行动空间A.定义相应的转移速率q(jli,a)和费用函数c(i,a)如
下:对i=0和任意的a∈A(O)=[0,1】,
如Io,小=p
q(Jli,a):=
h(i,a)
J=0,
歹=1, (3.23)
J≥2;
歹=i一1,
,2。’
(3.24)
J=i+1,
其他;
c(t,a):=/90+p/一r(a), V(i,a)∈K:---{(i,a):i∈S a∈A(i)). (3.25)
我们的目标是寻找条件以保证在期望折扣总费用准则下单调最优平稳策略的存在性.
考虑以下几个条件:
C4.Q+肛一入>0,其中Ot为某给定的折扣因子.对i=0和任意的a∈A(o),h(0,a)≥
0;对i≥1和任意的a∈A(i),hi+h(i,a)≥0.
C5.r(a)是关于a∈A(i)(i≥0)的严格单调递增非负连续函数且0<r(1)≤Po.
Cn.h(0,a)是关于a∈A(0)的严格单调递减非负连续函数;h(i,a)兰hl(i)(i≥1)是
与口无关的有界函数,故IIhlI._sup(i,口)∈K Ih(i,n)I<(30.
经过仔细验证,我们能够得到以下结论.
命题3.2在条件C4,C5,C6成立的情况下,上述有迁移的生灭系统连续时间MDP
模型满足假设2.1,2.5和2.6.因此,根据定理2.9,该决策模型存在至少一个折扣最优
平稳策略.而且,在这些(如果多于一个)折扣最优平稳策略中,存在至少一个关于状态
i∈S单调不增.

h
.0
啦锄口
}


p
+
脚一她叽11●●●\
中山大学硕士学位论文51
证明首先验证假设2.1.对所有的i∈S={o,1,2⋯.),令w(i):=i+1,‰:=
p+入+lIhll,由(3.23),(3.24)以及c6知对i=0,o∈A(o),有
oo
Σw(j)q(jlO,o)=-伽(O)q(OlO,o)+w(1)q(1lO,o)
j=o
=-h(O,a)+2h(O,a)
=h(O,a)
≤(入一p)伽(o)+Lo,
口+(o)=sup h(O,a)=h(O,0)≤肛+A+IIhlI=Low(O);
aeA(O)
对i≥1,a∈A(O,有
Σw(j)q(jli,o)=w(i-1)q(i--11i,口)+w(i)q(ili,n)+加@+1)g@+11i,口)
j=o
=埘2一[(p+A)主+h(i,a)】@+1)+【Ai+h(i,a)l(i+2)
=(A—p)i+h(i,o)
≤(入一p)坩@)+Lo,
q‘(i)=sup{(p+A)t+h(i,口))≤(p+入+lI^lI)(i+1)=Low(i),
aea(O
令bo=Lo,Co=A一肛,可知假设2.1成立.
然后验证假设2.5.由c5以及(3.25)可得
Ic(i,n)I≤(po+p)训0), Vi≥0,
取M:=Po+P,再由C4可知假设2.5成立.
最后验证假设2.6.对所有的i∈S,令W你):=(i+1)2,M’:=Lo.由(3.23),(3.24)
以及C4知对i=0,a∈A(O)有

ΣW7(j)q(jlO,a)=--'t07(O)q(OlO,a)+∞7(1)q(1lO,o)
j=o
=-h(O,a)+4h(O,a)
=3h(O,a)
≤伽7(o)+311hil,
矿(o)加(o)=h(O,0)≤肛+入+IIhlI=Low(O)=MIW7(o);
对i≥1,口∈A(i)有
Σ叫’(J)q(jli,a)=tU’o一1)q(i一1lt,a)+叫’(i)q(ili,口)+tU’@+1)q@+11i,口)
j=o
=p矿一【(p+A)i+h(i,n)】(i+1)2+[Ai+h(i,口)1(i+2)2
=2Ai2+3Ai~2pi2一埘+2h(i,a)i+3h(i,a)
52 连续时间MDP折扣模型的单调最优策略
_max{2)t-2#+1,1M)+坠}筹躞+2p+311九l-
矿(i)彬@)≤(p+A+1]hiD(/+1)2=‰伽7G)=M7t£,7(i),
令忙坠尘竽型+印+311hll一=max(2入嘞+1,1),
故由C5,C6和行动集A(t)兰【0,1】(i≥0)是紧集可知假设2.6成立.
因此,根据定理2.9,该决策模型存在至少一个折扣最优平稳策略.
下面利用定理3.1l证明在从刚才得到的折扣最优平稳策略中,至少存在一个关于状
态i∈S单调不增.由(3.23),(3.24)易知
lIqlI:=supq+(t)=00.
对所有的i∈S,选取m(i)=似+入)t+D,其中
D::m觚{p+IIhll+1,熊盟警剑一Q),
显然有m(i)≥旷(i)(主≥0).对所有的(i,a)∈K,令p(jli,a):=掣+吩=丽q(jli,a)+%,
其中文j表示Kronecker’s delta.
由于该决策模型存在至少一个折扣最优平稳策略,这意味着对任意单调的函数移∈
玩(S), 卿{端+焉争M外柚>
可达到最小值.此时我们只需逐一验证该决策模型满足定理3.1 1的六个条件.
(1)由【3.25)以及C5司得对所有的i∈S,口∈A都有c({,a):=Po+p/一r(o)≥0.
(2)对所有固定的a∈A,令
Ca(z):=ipo面+i缈-丽rO)
为在f0,+co)上的连续函数.显然九(z)在(0,oo)上可导,由c5以及D的定义知九(z)
的导数纰,=q高等掣独
故九(z)在【0,00)上单调不减.再由(3.25)以及m(i)的定义可知
群器=郇),Vi e s,
所以对所有固定的o∈A,舞‰是关于t∈s的单调不减函数.
中山大学硕士学位论文
(3)由m(i)的定义以及入>0,p>0知m(i)是关于i的单调不减函数,故
m(i)
+m(i) 南+1’
Vi∈S
也是关于i的单调不减函数.
下证对所有固定的口∈A和k∈S,ΣJ(30;%p(歹li,口)是关于i∈S的单调不减函数.根
据p(jli,a)的定义可知
Σp(j[i,
j=k
oo
骨Σp(j[i,

褂F『Z—一‘
j----k
o)在i∈S单调不减,

口)≤Σp(巾
j=k
q(jli,a)
m(i)
+1,a), Vi∈S,
+nij】, Vi∈S,
k≠i+1,Vi∈S,
+1, k=i+1,Vi∈S,
由此我们的目标可转化为证明不等式组(3.26)成立.
当k≤i一1时,对所有固定的n.∈A,由(3.23),(3.24)有
妻帮j=k 。、。7 一薹等等,蛇l·
当k=i时,对所有固定的a∈A,由(3.23),(3.24)有

:0:F
√二一
j=o
q(j[1,a)
m(1)
i=0,
一蒜缈薹等掣,Vi一>I.
当k=i+1时,对所有固定的a∈A,由(3.23),(3.24)以及m(i)和D的定义有§剑一÷剑生!!型
惫re(i) 急m(汁1)
2—入矿主+十危(—i,—a).—(p+—A)(—z十—1)+—h(i顽+1,再n)一可入—@+1—)一—h(i—+1,~a) mI Zl 仇【0十l J
入t+^G,a). pt+卢
(p+入)t+D。(p 4-A)(i+1)+D
, 入i+lI^I| 。p i+p
_:
(p+A)t+D‘(p+A)i+D
At+Il^I| . 弘i+p
(p+A)i+p+llhIl’(p+A)t+p+II^
(3.26)
∞一, 等∞Σ滞

吲l_ 回一,
砖一, 喜I罱
∞Σ触m <一
吲|藿±'+L—l 曲一, g一
∞Σ触<一㈨丽.钆一@ 曲一, q一
,IlI,、-●I【∞Σ喾Σ:!l
、,_
I-
引I藿㈨l藿业㈣缝∽
q一
口一
∞Σ言Σ触,l●J-1●一,
连续时间MDP折扣模型的单调最优策略
=1,
对以上不等式作移
Vi
项,可得
子剑勺m
j=k
+1, Vi≥0.
当k=i+2时,对所有固定的a∈A,由(3.23),(3.24)以及C4有
邯掣辫拶=薹OO等等,Vi>0.
当k≥i+3时,对所有固定的a∈A,由(3.23),(3.24)有
妻帮j=k 。。。、。7 一薹等等,№。·
因此不等式组.(3.26)成立,从而对所有固定的n∈A和k∈S,Σ,o:o。.、。i。,口)是关
于i∈S的单调不减函数.
(4)由(3.25)以及C5,对任意的i∈S,0≤n一≤o+≤1可得揣一=丽r(a-)-a+)Ot 1 Ot 1
≤。
+m(t+) +m(i+) Q+m(i+1)一。
和篇Q+m(一i) 揣口+仇=“糟) Ot+m() i虬-二。’
然后由m(i)是关于i的单调不减函数有
c(t+1,a+)
ot+m(i+1)
再根据引理3.3可知
c(i+1,a一)
Q+m(i+1) ≥篇Ot 一m i一+ ()
是S×A上的上可加函数.
(5)首先证明对任意的i,k∈S,0≤a一≤口+≤1,有
c(i,a一)
Q+m(i)‘
[q(jli+1,口+)一q(jli+1,a一)】
【q(Jli,a+)一q(jli,a一)】.
对i=0,0≤n一≤矿≤1,当k=0时,由(3.23),(3.24)有
00
Σ
j=o 业铲=。= Q+m(1)
当k=1时,由(3.23),(3.24)以及C6有
等蒿幽啦芈蔫铲= 00
Σ
J=1
(3.27)
q(jlO,a+)一q(jlO,a一)
ot+m(O)
㈨丽型”L—l 口一)
g一
∞Σ:!f. <一.%一0 口一)
引I藿.钆一@ 砖一,
g一
∞Σ础
南∞Σ:if-
南∞Σ触
0一一口一
盟卅型似D一∞ “一.,一仉一
∞Σ伽
中山大学硕士学位论文
当k≥2时,由(3.23),(3.24)以及C6有
oo
Σ
歹=七
q(jll,a+)一q(Jl
Q+m(1) 幽=。=妻业告器幽. ,5詹’‘
对i≥1,0≤口一≤a+≤1,当k≥0时,由(3.23),(3.24)以及C6有一妻业掣. ’2七’。
因此不等式(3.27)成立,再由p(Jli,a)的定义可知对任意的i,k∈S,0≤a一≤a+≤
1,有
同理可得
m(i)
+m(i) 薹砌k n+)一丽re(i)薹砌kn一)
[再m丽(O p(外,口+)一五丽m(O毗(Jl口一)】
羔[p(jli,a+)一p(Jl如_)】
仇(t)
Ot+m(i)
Q+m(i)
[帮+岛一帮一如]
【q(jli,n+)一q(j[i,a一)】,
羔器挚m∽一蔫器驴00 Ii+1,a-,
O/+m(i+1)
【q(j[i+1,a+)一q(j[i+1,a-)】.
故联合(3.27),(3.28),(3.29)可知对任意的i,七∈S,0≤n一≤a+≤1,有
m(i+1)
Ot+m(i+11
≥器Q十m10 J
知川,n+,一蔫器知i+1,a-,
薹p(歹Ii,。+)一丢-re.(,,i,)、。,J:七p(歹Ii,口一).
p(j[i,o)是S×A上的上可加函数.
(3.28)
(3.29)
(6)回顾bo=Lo=p+入+IIhll,Co=A—p,M=Po+P,w(i)=i+1以及C4,对
任意的i∈S,令‰(t):=碉boM+Q—Co
w(i)
旦^l
K—D 群L—Q 矿一+
◇一二!P一+一
∞Σl}
∞Σ喾Σ等Σ芸Σ触
∞Σ触
连续时间MDP折扣模型的单调最优策略
=:譬=岩Q一(口磐+十p产—A+一)若I0Z1%十(IⅢ-)., ’
+p一入r。√’
可知vo(i)是关于状态i∈S的单调不减函数.得证! 口
可见,上述决策模型满足定理3.11的所有条件和假设,从而存在至少一个折扣最优
平稳策略在i∈S上单调不增.
我们在命题3.2的证明中可以发现,为了保证定理3.1l的条件(5)成立,C6发挥了关
键作用.这告诉我们只要q(110,n)=h(O,a)是关于a∈A(O)的严格单调递减非负连续函
数;h(i,a)三hl(i)(i≥1)是与a无关的有界函数,或者说,当i≥1时,q(i-lli,o)、q(ili,a)
与g(i+11i,a)都是与n∈A(i)无关的函数,则对任意的尼∈S,
者‰妻p(Jl锄) Q+m(i)急一q叫
是S×A上的上可加函数.反过来,如果已知某MDP折扣模型的转移速率族{口(·K,n))
满足对i=0和任意的a∈A(0)=A,
q(j10,a):=
对i≥1和任意的a∈A(i)三A,
q(jli,a)
(3.30)
J=i一1.
J 2。’
(3.31)
J=i+1,
其他;
此时Q:=【q(jli,口)】可看作具有一般生灭过程形式的Q矩阵,且对任意的k∈S,
端却和卜焉薹[掣+如] B32,
是S×A上的上可加函数.我们是否可以得到一些有趣的结果呢?
首先,由(3.28)和(3.32)可知对任意的忌∈S,
,:
O
1
2
=
II
>一.了
o
h
q
N㈣o



,I-l-f、●-【O
一入.钆n
@p“ 叭柚叭

从1
N叽11●●●_,
Ⅱ 函数








^月




A

(






S
*


川∞Σ:!fp
—n ∞曾志
∽面

型棚

中山大学硕士学位论文57
于是,当i=0,k=1时,对任意的a一≤n+(o一,a+∈A),由(3.30),(3.31)有
Q+m(1)
1
Q+m(1)
≥厕1m 一Q+ (0)
l
Q+m(0)
而1丽§CO舭口一)
【p(1,a~)一p(1,n+)1

Σq(jlO,n+)一
j=k
Ol+m(o)
【入(o,a+)一A(o,a一)】;
i‰妻g石Q+仇(2)惫叭J
==0
≥丽1薹00m 1
>————I> 一a+()_
Q+m(1)
12,a+)一
Q+m(2)
q(j[1,a+)一

Σq(j10,n一)
j=k
00
Σq(j]2,口一)
j=k
Q+m(1)
[弘(1,a一)一p(1,a+)】.
联合(3.33)、(3.34)可知
入(o,a+)一A(o,o一)/
Ot+m(o) 一
显然,
)qo,a一)≥A(o,a+)

Σq(jll,n一)
j=k
譬掣m1

Q+ () 一
p(1,a一)≤p(1,a+).
当i≥1,k=i+1时,对任意的a一≤n+a一,a+∈A),由(3.30),(3.31)有
(3.33)
(3.34)
确p00 k n+j一志争kn一,
2五_二F弓元巧了【入@,n+)一A(主,n一)】(3.35)
≥纛禹争i-1,a+,一未南麴i-1,a-,
=0;
Ot+m(i+1)
1
Σq(jli+l,矿)一
j=k
Ol+m(i+1)
Ot+m(i)
1
Ot+m(i)
Ot+m(i+1)
[肛0+1,a一)一p(i+1,n+)】
oo
Σq(Jli,矿)一
j=k
Q+m(i)
【入(i,口+)一A(t,a一)】;
Σq(jli+1,a一)
歹=七
oo
Σq(j]i,o一)
j=k
(3.36)
+
口o
∞Σ触
连续时间MDP折扣模型的单调最优策略
知Ⅲ矿,一熹函静i+2,a-,
≥高薹如K“,n+)一南薹“引i+1,a-00 )
37) 1

1 (3.
=再丽1丽[p(i-t-1,a-)一p(i+1,矿)】.
联合(3.35)、(3.36)、(3.37)可知。≤等羔铲≤业等铲舛
故对i≥1,有
A(喜,a一)=入(i,a+) , p(i+1,a一)=z(i+1,a+).
根据a一,a+∈A的任意性知,模型的生率和灭率可写为
i=0,
i≥1;
这意味着当系统状态为“0”时,生率会随着行动的增加而减少,当系统状态为“l”时,生
率与行动的变化无关,灭率会随着行动的增加而增加;当系统状态大于或等于“2”时,生
率与灭率都与行动的改变无关.
对称地,若对任意的k∈S,
丽re(i)驴oo锄净器薹[掣+西]
是S×A上的下可加函数,利用同样的方法可以验证当系统状态为“0。时,生率会随着
行动的增加而增加,当系统状态为“l”时,生率与行动的变化无关,灭率会随着行动的
增加而减少;当系统状态大于或等于。2”时,生率与灭率都与行动的改变无关.
赤划
1
2
=
>一
.●■
.1
、l,、I,




仉力
b力
入~入
、-●.,、p~p
Il
ll
、,、,
0
0
.口p
.0
,,\,●\

p
第四章本文的结束语及有待研究的问题
§4.1本文的结束语
本文主要研究了可数状态连续时间MDP折扣模型的单调最优策略存在的充分条件,
我们可以得到四个主要结果:
第一,在期望折扣总报酬准则下,分别就转移速率q(jli,a)有界与无界两种情形,首
先给出使得由递归算子T(见(2.19))生成的函数序列{钆n(t))n>o和该序列的极限函数
钍4(t)在S上单调不减(单调不增)的条件,见定理3.2,3.5;在此基础上继续给出条件保
证算子T右边的式子鲰({,a)以及折扣报酬最优方程右边的式子9+(i,a)(见(3.8)、(3.9))
是上可加(下可加)函数,并证明在定理2.6(或推论2.1)基础上构造的最优平稳策略关
于系统状态单调不减(单调不增),见定理3.3,3.4,3.6,推论3.1,3.2,3.3.
第二,在期望折扣总费用准则下,分别就转移速率q(jli,a)有界与无界两种情形,首
先给出使得由递归算子L(见(2.27))生成的函数序列{‰(i))n>o和该序列的极限函数
口‘(i)在S上单调不减(单调不增)的条件,见定理3.7,3.10;在此基础上继续给出条件保证
算子己右边的式子磊(i,a)以及折扣费用最优方程右边的式子矿(i,a)(见(3.16)、(3.17))
是上可加(下可加)函数,并证明在定理2.9(或推论2.2)基础上构造的最优平稳策略关
于系统状态单调不增(at调不减),见定理3.8,3.9,3.11,推论3.4,3.5,3.6.
第三,给出了两个例子,以进一步阐明前文得到的单调最优策略存在的结果和条件.
在设备维修系统的最优控制例子当中,我们在期望折扣总报酬准则下讨论单调最优平稳
策略的存在性,验证了该决策模型满足推论2.1,3.2,见命题3.1,其中模型的转移速率
q(jli,a)有界,A(i)兰A中的行动离散且个数有限;而在有迁移生灭系统的最优控制例子
当中,我们在期望折扣总费用准则下讨论单调最优平稳策略的存在性,验证了该决策模
型满足定理2.9,3.11,见命题3.2,其中模型的转移速率q(jli,a)无界,A(i)三A中的行
动连续且不可数.
第四,如果已知由某MDP折扣模型的转移速率族{口(·li,口))得到的Q:=【q(jli,o)】可看作具有一般生灭过程形式的Q矩阵,且盟ct+m(i)Σ【丽q(jl矿i,a)+如】是S×A上的上(下) J=七’‘
可加函数,则可以证明当系统状态为“0”时,生率会随着行动的增加而减少(增加),当
系统状态为“l”时,生率与行动的变化无关,灭率会随着行动的增加而增加(减少);当
系统状态大于或等于。2”时,生率与灭率都与行动的改变无关.
总而言之,本文在期望折扣总报酬与期望折扣总费用准则下,分别就转移速率有界
与无界两种情形,首次研究连续时间MDP折扣模型单调最优策略的存在性问题,不仅给
出使得最优策略关于系统状态单调(不减或不增)的充分条件,还给出了设备维修系统的
最优控制与有迁移生灭系统的最优控制两个例子以进一步阐明前文得到的单调最优策略
存在的结果和条件,并得到了一些有趣的新结果.
59
连续时间MDP折扣模型的单调最优策略
§4.2有待研究的问题
限于时间和水平,作者在撰写本文的过程中留下了一些有待解决的问题,它们包括:
问题1在连续时间MDP的折扣模型中,如果状态空间和行动空间都是Polish空间,
我们能否给出相应的单调最优策略存在的充分条件?特别地,对状态空间S=[0,+∞),行
动空间为某个带偏序的紧的Polish空间的折扣模型,假设对任意单调的函数“∈三乙(S), sup{r(i,a)万+焉f钍咖(帅)) ⋯)
可达到上确界,II口II:=supiES,aEA(i)【一口({母lt,口)】<CO,若以下五个条件
(1)对所有的n∈A,r(i,a)是关于i∈S的单调不减函数;
(2)对所有的a∈A和k∈S,斤t‘U)q(djti,o)是关于i∈S的单调不减函数;
(3)r(i,a)是S×A上的上可加(下可加)函数;
(4)对所有的k∈S,f u(j)q(djli,a)是s X A上的上可加(下可加)函数;
(5)w(i)是关于i∈9的单调不增函数;
成立,或lIg|I.=supi∈只口∈郇)【-q({i}li,a)】=oo,若以下六个条件
(1)对所有的i∈S和a E A.,r(o,a)≤o;
(2)对所有的n∈A,再r(im,a㈤)届_fft八gt:一。。{∈S的单调不增函数;
(3)对所有的n∈A和七∈S,器貉和f u(j)q(dj[i,n)都是关于i∈S的单调不
减函数. ⋯
(4)未%表是s×A上的上可加(下可加)函数;
(5)对所有的七∈S,甭re丽(i两)F u(j)q(djli,o)是s×A上的下可加(上可加)函
数;
(6)w(i)是关于i∈S的单调不减函数;
成立,是否存在单调的最优平稳策略尤,t(i)(丘,J(i))在i∈S上单调不减(单调不增)?
问题2在连续时间MDP的平均模型中,当系统的初始状态为i∈S,定义策略
7r=(?i-t)∈II的长期期望平均报酬如下(该定义参见文献【7】第17页)t
盹7r)--linmi。。nf T*⋯"7r), (4·2)
其中
晰,小=霹[foTr(蛾。㈣)叫, (4.3)
相应的最优平均报酬函数(或平均最优问题的最优值函数)是
矿(t):=sup9(/,7r), 初始状态i∈S.
我们能否给出使得单调最优策略存在的充分条件?
致谢
有一位老师,
他治学严谨,勤奋踏实,几十年如一日,孜孜不倦地从事教学和科研工作.
他思维敏捷,诙谐幽默,能为严肃凝滞的气氛带来活力,更显示了高度的机智与自
‘L
1青.
他因材施教,会从学生的实际需要、个别差异出发,有的放矢地进行有差别的教学,
使每个学生都能扬长避短,获得最佳发展.
他诲人不倦,无论多忙,只要学生有问题,都非常耐心,不厌其烦地抽出时间为他们
授道解惑,不管在下课后,还是在饭桌上.
他严格要求,以身作则,学习上要求我们扎扎实实,掌握每一个概念和定义,弄懂每
一个问题,生活中要求我们上下课主动擦黑板,为人处世不能只考虑自己还得多为他人
着想.
他胸怀宽广,处事公正,能够在前一分钟因你某事做得不当而及时批评或提醒,而在
后一分钟看到你的进步而给予肯定与鼓励.
他热情随和,体贴入微,他请大伙儿唱K,因不忍心打断羽毛球场的节奏而在旁边等
了许久,亲自打电话问候病后在家休养的学生,一次又一次地为他们提供到国外、香港读
博的机会,在他们的求职路上还给予充分的理解和全力的支持.
他是一座高山,在我以为快要靠近山顶的时候,才蓦然惊醒,原来我看到的,仅仅是
萦绕在山腰间的光芒.
无意中,我发现,自己已经变成他的粉丝之一!
他,就是我最最尊敬的导师一一中山大学数学与计算科学学院的郭先平教授!
在此谨向郭老师致以诚挚的谢意和崇高的敬意!
还要感谢聪明帅气的黄永辉师兄,成熟大方的刘秋丽师姐,时尚知性的叶柳儿师姐,
乐于助人的魏清达和美丽温柔的林少英同学,以及善解人意的张文钊师弟;在此特别感
谢可爱细心的龙娟师妹,她为本文的校对工作提出了许多宝贵的建议!没有你们的支持
关怀与陪伴,我是不可能走到今天的!怀念和大家一起学习上课,一起打球娱乐的时光,
这些都是最美好的回忆,认识你们是我十世修来的福分!
还要感谢在—起愉快地度过研究生生活的173.727宿舍各位同学以及宿管叔叔阿姨,
正是由于你们的帮助和支持,我才能克服一个又一个的困难和疑惑,直至本文的顺利完
成.
最后要感谢培养我长大含辛茹苦的父母,谢谢你们!
最最后要感谢答辩委员会的李仲飞主席,任佳刚,黄煜,王学钦和郭先平教授!
我爱你们1
6l
62 连续时间MDP折扣模型的单调最优策略
参考文献
【1】Albright,S.C.&Winston,W.,Markov models of advertising and pricing decisions,
Operations Research,1979,V01.27,668—681.
[2】Ash,R.B.,Probability and Measure Theory(Second Edition),Academic Press,New
York,1999.
【3】3 Chow,Y S.and Teicher,H.,Probability Theory,Springer-Verlag,New Y0rk,1978.
【4】4 Cohn,Donald L.,Measure Theory,Birkhiiuser Boston,Boston,Basel,1980.
[5】Doob,J.L.,Measure Theory,Springer-Verlag,New York,1993.
【6】Guo,X.P,Continuous—Time Markov decision processes with discounted rewards:the
case ofPolish spaces,Mathematics of Operations Research,2007,32,73—87.
【7】Guo,X.P&Hermindez-Lerma, O., Continuous.Time Markov Decision Pro.
cesses,Springer-Verlag,New York,2009.
f8】Guo,X.P&Hemfindez-Lerma,0.,Continuous—Time controlledMarkov chains。Annals
ofApplied Probability,2003a,13,363—388.
【9】Guo,X.P.&Hemfindez—Lerma,O.,Continuous.Time controlled Markov chains埘砌
discountedrewards,Acta Applicandae Mathematicae,2003b,79,195—216.
【1 0】Guo,X.P&Zhu,WP,Denumerable state continuous.time Markov decision processes
with unbounded cost andtransition rates under the discountedcriterion,Joumal ofA矿
plied Probability,2002,39,233—250.
【1 1】Halmos,Paul R.,Measure Theory,Springer-Verlag,New Yod【,1974.
【1 2】Hernhndez-Lerma,O.&Govindan,T.E.,Nonstationary continuous.time Markov control
processes with discounted COSTS on infinite horizon,Acta Applicandae Mathemati.
cae,2001,67,277—293.
【13】Heyman,D.E&Sobel,M。J Stochastic Models in OperationsResearch,V01.2,McGraw-
Hill,New York,1 984.
【14】Howard,R.A.,DynamicprogrammingandMarkovProcesses,Wiley,NewYork,1960.
[15】Kakumanu,P,Continuously discounted Markov decision models with countable state
andaction spaces,Annals ofMathematical Statistics,1971,42,919—926.
【1 6】Miller,B.L.,Finite state continuous time Markov decision processes with an infinite
planning horizon,Journal of Mathematical Analysis and Applications,1968,22,552.
569.
【17】Neveu,J.,MathematicalFundationsoftheCalculusofProbability,Holden—DayInc.。San
Francisco,1965.
中山大学硕士学位论文
【1 8】Porteus,E.L.,Foundations of Stochastic Inventory Theory,Stanford University
Press,California,2002.
【19】Prieto—Rumeau,T.&Hemhndez-Lerma,O.,Bias optimalityfo,.continuous—time controlledMarkov
chains,SIAM Journal On Control and Optimization,2006,45,51—73.
【20】Puterman,M.L.,Markov Decision Processes,John Wiley&Sons,Inc,New York,1994.
【21】Ross,S.M.,Introduction to Stochastic Dynamic Programming,Academic Press,New
York,1983.
【22】Roykov,VV,Markov sequential decision processes with伽娩state and decision
space,Theory of Probability and Its Applications,1 966,1l,302-3 1 1.
【23】Serfozo,tLE,Monotone Optimal Policies For Markov Decision Processes,Springer-
Verlag,Berlin,1976.
【24】Topkis,D.M., Foundations of Stochastic Inventory Theory, Operations Research,
1978,V01.26,No.2,305—321.
【25】Veinott,A.E,Discrete dynamic programming with sentitive discount optimality criteria,
Annals ofMathematical Statistics,1969,40,1635—1660.
【26】程士宏.测度论与概率论基础.北京;北京大学出版社,2004.
【27】邓东皋,常心仪.实变函数简明教程.北京:高等教育出版社,2005.
【28】邓东皋,尹小玲.数学分析简明教程(上册).北京:高等教育出版社,1996.
【29】侯振挺,郭先平.马尔可夫决策过程.长沙:湖南科学技书出版社,1998.
【30】胡奇英,刘建庸.马尔可夫决策过程引论.西安:西安电子科技大学出版社,2000.
。【3l】刘克.实用马尔可夫决策过程.北京:清华大学出版社,2004.
【32】李贤平.概率论基础(第二版).北京:高等教育出版社,1997.
【33】林元烈.应用随机过程.北京:清华大学出版社,2002.
【34】陆风山.排队论及其应用.长沙:湖南科学技书出版社,1984.
【35】宋京生. 转移速率族非一致有界的连续时间马氏决策规划, 中国科学A
辑,1987,12,1258—1267.
【36】伍从斌.报酬函数及转移速率族均非一致有界的连续时间折扣马氏决策规划,应用
数学学报,1997,20,196—208.
【37】汪嘉冈.现代概率论基础(第二版).上海:复旦大学出版社,2005.
【38】夏道行等.实变函数论与泛函分析(上册).北京:高等教育出版社,1984.
【39】严加安.测度论讲义(第二版).北京:科学出版社,2004.
[40】严士健,王隽骧,刘秀芳.概率论基础.北京;科学出版社,1982.