离散事件动态系统--马尔科夫链

1、离散事件动态系统的分析方法随机动态规划与强化学习报告人：报告人： 唐唐 昊昊电气与自动化工程学院电气与自动化工程学院计算机与信息学院计算机与信息学院2016年度2022-5-142/ 51课程基本情况n课程性质：非学位课n学时数/学分：32/2 n周学时：4 （后面有调整）n授课形式：(a) 主讲面授； (c) 文献报告和自由讨论n应用领域：网络系统分析、移动机器人、智能交通、生产自动化和供应链管理、Agent系统、网络控制优化、机器学习、排队网络、系统可靠性分析，以及其它有关决策优化、控制和智能学习等。n前期课程内容：高等数学、概率论、线性代数n考核方式：考查（含课程总结、文献汇报）2022

2、-5-143/ 51课程内容 1.离散事件动态系统基本概念、分类、研究方法2.随机离散事件动态系统的基本仿真技术3.Markov决策过程（含Markov链，半Markov决策过程）基本知识4.动态规划（dynamic programming）和仿真优化：主要介绍Bellman最优方程，策略迭代和数值迭代。5.强化学习（reinforcement learning）技术：主要介绍Monte-Carlo方法、TD学习、Q学习和SARSA学习等。6.神经元/逼近动态规划（neuro-dynamic programming） 7.多Agent学习探讨8.实例分析 2022-5-144/ 51第一章离散

3、事件动态系统基本概念、分类和研究方法2022-5-145/ 51基本概念n随着高新技术的迅猛发展，现实世界中涌现了大量的复杂人造系统（如计算机网络、通信网络、柔性制造系统、CIMS、交通管理系统、军事指挥系统等）。这些系统的共同特征是：系统的演化过程不能由通常的物理定律来描述，而是服从一些由人为规定的复杂规则，并由一系列相互作用的离散事件所决定。n 这样的一类人造系统常被描述为离散事件动态系统（Discrete event dynamic system，DEDS）。n事件：使DEDS状态发生变动的一个行动或事情。2022-5-146/ 51nDEDSDEDS与一般动态系统的差别：与一般动态系统

4、的差别：通常的连续变量动态系统(CVDS)，其动态特性满足一定的物理定律，可用微分方程或差分方程来描述。 例如经典力学下的质点运动方程等可以描述为nDEDSDEDS基本概念基本概念: : 由一些相互作用的离散事件构成，并且由它们触发而引起状态转移（演化）的一类动态系统,它所含的事件的发生在时间和空间上都是离散的。( )( ( ), ( ), ) ( )( )(1)( ( ), ( ) ( )( )x tf x tu ttAx tBu tx kf x ku kAx kBu k&微分方程差分方程：线性系统2022-5-147/ 51例1 柔性制造系统 待加工工件缓冲器工作台1已加工工件缓冲器待加工

5、工件缓冲器工作台M已加工工件缓冲器Sn2Sn1智能仓库自行小车2022-5-148/ 51例2 机器人自动装配线（robotic assembly line）2022-5-149/ 51例3 开排队网络01服务站1缓冲器服务站2缓冲器服务站3缓冲器02010310q11q12q13q20q21q22q23q30q31q32q33q2022-5-1410/ 51通信系统中的接入控制2022-5-1411/ 51基本分类和研究方法DEDS的三个层次模型：n 逻辑层次模型（确定性）主要有形式语言，有限自动机，Markov链，Petri网等(不可时序化）：模型不可赋时，只考虑表征系统行为的符号的顺序关

6、系n 代数层次模型（确定性）主要有极大极小代数，有限递归过程等（可时序化可时序化）n 统计层次模型（随机性）主要有Markov过程，半Markov过程或广义半Markov过程，各种类型的排队网络等（可时序化可时序化、采用仿真方法）2022-5-1412/ 51DEDS统计性能层次的研究情况从九十年代开始，统计性能层次的研究已成为DEDS研究领域的一个重要方面，主要包括以下两个研究方向：u系统的性能分析：主要是灵敏度分析u优化理论和应用研究：Markov控制（决策）过程方法及优化问题已成为当前DEDS领域的一个令人注目的热点，也是本课程的主要介绍对象。拓展：SMDP、POMDP、HMM、HDS建

7、模2022-5-1413/ 51第二章随机离散事件动态系统的基本仿真技术2022-5-1414/ 51随机变量n随机变量：粗略的说就是能取不同数值的量n非随机的（确定性的数值，永不改变） ：太阳系中的太阳个数n随机的：一个人一天接到的电话个数，每天都不一样2022-5-1415/ 51概率n实验（experiment）：考试，掷骰子，打球比赛，扔硬币n一次实验对应一个输出X，考虑实验的输出是随机变量，可取多个值。n（pass，fail），（1，2，3，4，5，6），（win，lose），（heads，tails）n事件：掷骰子，点数为2，或者为偶数n事件的概率：事件发生的机会（chance）或

8、可能性（likelihood），m次实验中，事件A发生n次，则概率为 P(A)=lim m(n/m) 0,12022-5-1416/ 51加数法则（addition law）n互斥事件（mutually exclusive）n复合事件（compound）：由互斥事件构成，如多次掷骰子中，出现偶数的事件由分别出现2，4或6的互斥事件构成。若复合事件E由A1，,An构成，则P(E)=P( A1)+ P(An)n复杂事件（complex）：未必由互斥事件构成，如掷骰子，出现质数（2，3，5）或偶数（2，4，6）的事件P(AB)=P( A)+ P(B)-P(AB)AB2022-5-1417/ 51乘积

9、法则（multiplication law）n独立事件（independent）：两个事件中，一个事件的出现不依赖于另外一个。反之为相关事件（dependent）。扔硬币，第一次为heads的事件A与第二次为tails的事件B相互独立。定义事件E表示第一次为heads且第二次为tails的事件，则P(E)P(A B)=P( A) .P(B)n互斥的就无所谓相关不相关；非互斥的，则有可能独立，则P(A B)=P( A) .P(B)。n既不互斥又不独立，则P(A B)=P( A) .P(B|A)= P( B) .P(A|B)， 其中，P(B|A)和P(A|B)为条件概率。（若A、B独立，则？）20

10、22-5-1418/ 51概率分布离散变量随机变量取值可能是离散的，如1,4.5,18,1969，也可能是连续的，如区间0 10。先考虑离散变量n离散随机变量：掷骰子游戏中，输出X 1,2,3,4,5,6，其中X为1的概率记P(X=1)=1/6，一般地， P(X=k)=l，对应一个概率质量函数（Prob. Mass function, PMF），即f(x)，表示概率P(X=x)。nP(Xk)=l表示随机变量X不超过k的概率为l，该函数表示累积分布函数 （Cumulative distribution function, CDF，有时简称分布函数），记为F(X=k)或F(x)，满足nF(X=k)

11、kx=af(x)（从X的最低可能值a到k的所有pmf值的和）nPMF CDF2022-5-1419/ 51概率分布连续变量连续随机变量：例如连续两次所接电话之间的时间差n概率密度函数（Prob. density function, PDF对应离散情况的PMF），仍记为f(x). 分布函数满足()( )kaF Xkdxf x()1, ( )0 if or ( )baF Xbdxf xxaxbf x( )( )dF xf xdx2022-5-1420/ 51随机变量的期望值和标准偏差n离散随机变量的期望值（expected/mean/average value）( )( )xE Xxf x( )(

12、 )xE Xdxxf xn连续随机变量的期望值n均值不能说明一个随机变量任何特性，只有同标准偏差一起才能说明。随机性完全体现在PDF、PMF或CDF。n标准偏差：随机变量对其均值的平均偏离的估计，定义21*21()()()(1),(),niikiiXXxanannxmkXmk若 是 次实验的平均值(则 个偏差不是独立的)若随机变量 的均值 已知(则 个偏差是独立的)n标准偏差的平方称为方差2()X2022-5-1421/ 51极限定理（Limit Theorems）n中心极限定理：1212,()lim ()nnnXXXXE XXXnLLL令为独立随机变量序列，具有均值的共同分布，则以概率1样本

13、均值收敛于期望12212122,nnnnnXXXXXXXYnnXXY LLLLL令为同分布的独立随机变量序列，具有均值 和方差，定义则时，则不管原来的分布为什么， 的分布逐渐变为均值为 和方差为的正态分布。n强大数定律：2022-5-1422/ 51仿真中的基本概念n离散事件仿真仿真主要涉及随机数产生和随机系统仿真模型n动态系统动态系统：系统（行为）随时间变化n状态状态：描述系统（行为）随时间变化的物理量。如排队系统的队长，库存量，带宽占用率等。n支配（控制）变量支配（控制）变量（governing variable）：动态系统的行为受这些变量支配、控制（操纵），如排队系统中的服务时间和相邻顾

14、客到达时间间隔。n随机系统随机系统：控制变量是随机变量的系统，其行为受随机变量支配。2022-5-1423/ 51模型n实体（模型）实体（模型）：小型飞机模型，模拟仿真系统n抽象（数学）模型抽象（数学）模型：方程，函数，不等式，计算机程序等。帮助理解，分析，预测系统行为.n建模建模一般基于一些假设，如系统结构，支配变量的分布。排队系统中的指数服务和到达间隔。n为研究大规模复杂随机系统，可用计算机程序模拟系统行为（为支配随机变量产生随机数），这样的程序可称为仿真模型。n仿真模型亦可用于优化，特别是无法或难以建立数学模型时。产生仿真优化。2022-5-1424/ 51为什么研究随机系统n很多实际系

15、统是随机系统，如通讯网络n通过研究，可以改变这些系统，使其更有效运行（或降低其运行代价）2022-5-1425/ 51随机系统的仿真模型n随机系统的建模第一步是要寻找支配随机变量的分布。n分布的作用：数学模型中用于建立表达式；仿真模型中用于产生随机数，以便计算机来模拟系统的行为，即重构实际系统发生的事件（产生支配随机变量的值）。n随机变量分布的获取：从实际系统收集数据，然后进行分布函数拟合2022-5-1426/ 51随机数产生-均匀分布随机数的产生（人工产生！）线性同余随机数产生线性同余随机数产生（linear congruential generator）nIj+1(aIj mod m):

16、 aIj 被m除的余数， a和m为正整数，I0小于等于m，Ij0,m是随机序列。如a=2, m=20, I0 =12,则有12,4,8,16,12,4,8,16,12,.n适当选择a和m，则得到0和m之间的所有整数序列（m-1个），第i个整数xi代表（决定了）第i个随机数yi=xi/m，每个yi的可能性相同（ xi 在原来的序列集里出现一次）。m越大，yi越接近于服从0,1之间均匀分布的自然随机数。nI0是种子，能产生的最大随机数个数是m-1。若m2321，对应个数21474836462022-5-1427/ 51随机数产生n实际中，若周期短（m小），则随机数会重复，导致结果变坏（随机数不独立

17、，不再服从均匀分布）。nIj+1(aIj mod m)中的aIj可能会超出计算机表达能力。nSchrage逼近因数分解：Q= a(Ij mod q)-rIj /q，q和r是正整数n随机数产生机制无需计算aIj n对(a, b)间的任何均匀分布，其随机数x都可由(0, 1)之间的随机数y产生: x=a+(b-a)y. （映射！）1 0otherwisejIQif QQm2022-5-1428/ 51随机数产生-其它分布逆函数方法n指数分布的累积分布函数为( ) 1,0 xF xe 1.产生一个随机数y，服从（0，1）之间的均匀分布，令其为指数分布的CDF的值，即F(x)=y2.反解x，即ln(1

18、)1lnor xyyexyx 2022-5-1429/ 51使用随机数的事件重构n以单个服务台排队为例，两个支配变量：n相继到达时间间隔ta。n服务者为一个顾客的服务时间ts。n根据各自分布产生两个随机序列ta,ts，例如ta=10.1, 2.3, 1, 0.9, 3.5; ts=0.1, 3.2, 1.19, 4.9, 1.1.n可构造两种事件发生n到达 tan离开n空闲：10.1+2.2 tsn使用率（utilization）：1-12.3/22.79n长时段仿真（long run）10.12.3-0.12022-5-1430/ 5110 lim,( ) lim, ( ) t niinTT

19、iwWnQ t dtQQ tT队列中顾客的平均等待时间（ 是顾客号）队列中的平均顾客数为 时刻的队长足够大的仿真：指定的精度牵水平内，再涉到随机数增加样本，待估计的值 不再改变。独立样本（）可终止的系统和非终产生！止的系统2022-5-1431/ 51第三章Markov决策过程基本知识2022-5-1432/ 51Examples The deterministic shortest path problem nTransition from one city to the next one is deterministic:Each control (or action) at a give

20、n city leads to a unique and certain successor citynThe objective is to find a path among all possible paths, which has the minimum costnThis problem can be solved effectively by dynamic programmingTermination cityInitial cityFig.1Path programming for a traveling sales man 2022-5-1433/ 51Fig.2 : The

21、 shortest path problem *min,: The optimal cost from city to the termination,: The cost for the transition from to jig i jjiig i jij 327941381314Bellman equation(反向递推，从K节点出发)：2022-5-1434/ 51Examples Stochastic shortest path (SSP) problem nTransition from one state to the next one is stochastic, that

22、isEach action at a given state may lead to several possible successor states, and each transition, e.g. from state C to state F, will generate a cost, which may be dependent on the actionTermination city(Termination state)Initial city (initial state)Fig.3 Path programming for a signal in communicati

23、on systems 2022-5-1435/ 51Examples Transition for signals in the SSP problemsTransition probability: P(E| C, d); Generated cost: f (C, d, E)P(E| C, d)+P(F| C, d)+P(G| C, d )=1;P(G| C, d); f (C, d, G)ddBCDEFGP(F| C, d); f (C, d, F)P(G| C, d ); f (C, d, G)nThe essence of the problem is how to reach th

24、e termination state with minimum expected costP(E| C, d); f (C, d, E)2022-5-1436/ 51Mathematic models for Markov chains System EvolutionDecision epoch: t Decision epoch: t +1 Action: dtdt+1Cost: ft(Xt,dt)ft+1(Xt+1,dt+1)XtXt+1P(Xt+1| Xt, dt)nMarkov property: state transition is independent of the his

25、tory, i.e., transition from Xt to Xt+1 is only determined by current state Xt and selected action dt状态序列行动序列代价序列2022-5-1437/ 51Mathematic models for Markov chainsBasic model parametersControlled Markov chain: : 0, 1, 2, , or 0,1,2, : (generic state ); : (generiDecisio n epochsSc action ) : ( , ) or

26、( , , ) , tate spaceAction setRe r wa ds iDdDf i df i d jiNst, : ( | , ) or ( )A model is called if rewards aTransition proband transition prationobabibilitieslities are independent of timy reaijdDp j i dp d2022-5-1438/ 51Mathematic models for Markov chains Classification of policies 000111,101 of a

27、 controlled Markov chain when evolving from state to : , is a sequence as , where each is a distribution over Stochastic policacHistor y y nnnnnnnXXXdX dXdXHV LLFtion set if history is given: ( |)0 1, ( |)=1 ( is selected deterministic policywith prob. ( |)A is a mapping : (Given a history, a specia

28、l action is nnnnnnnd DnnddddHDFFFF01 selected w.p.1, ( |)1 for a fixed action d): ( |)( |) (Deterministic) Markov polic(Dey: : : , : terministic) poliStochastic Markov policyStatci na yyrDonnnnnnnddd XDD LFFenote a stationary policy as , the set as , and ( (1), (), ( )for a finite state apace. state

29、-action map (look-up table)svvvv Mv iL2022-5-1439/ 51Mathematic models for Markov chains Performance criteria 100100 Finite horizon problem (cost accumulates over a finite number of stages)Discounted( )()1Average( )()criteriacriteri()aNvNnnnnNnNnnnNviEfXv XXifXiEfXv XXiNv X ： ：00, if Infinite horizo

30、n problem (cost accumulates infinitely)Discounted criteria()0total discounInfinite horizon expected cost: , 01( )() 01 Fted vNnnnNnfiEfXv XXXiXv 100Infiniteor stochast horizon exic shotest path problepected (every stage) aExpected totalveram, 1 is possible: Average criterige cost costua: 1( )lim(),

31、nichor faNvnnNniEfXv XXiN ( )i,nvvii011?（）, 2022-5-1440/ 51Mathematic models for Markov chainsOptimization problem ,(,) A controlled Markov chain can be denoted bytransition matrix: ( | , ( ) performance function: ( (1, (1) , (2, (2), (, ()Optimization objectiv vvnvi jvXXD PfPfp j i v ifvfvf M v M*a

32、rgminargmin or e is to select a policy minimizing the chosen performance criteria, that isNote that the received cost is by now assumed when an action is t immeaken diat evvvvssvv What happens if the cost is accumulated with time before the process jumps to the next st!ate? 2022-5-1441/ 511If an act

33、ion is taken at state , the generated cost is accrued with time at period , , then we have to consider the sojourn time . So (, () represents the received cost v ennnnnnXT TTf X v X011 Under , if the underlying chain , is , and distribution of only relies on , and (), leads to a seery unit timemi-MD

34、P (SMDP)Especially if the diMarkovsanti rnnnnnvX XXTXXv X ibution is , leads to continuouexponentias-timle MDPSemi-Markov decision processes (SMDPs) From Markov chain to SMDP 0000 Decisi () (, () on epoch: Action:Cost (rate : )Tv Xf Xv X()(, ()nnnnTv Xf Xv X0121 nnXXXXX1111()(, ()nnnnTv Xf Xv X1nnnT

35、TT一次仿真：2022-5-1442/ 51basic concepts for MDP01, embedded Markov chaiDeterministic stationar y policy :, write ( (1), ()Transition matrix of the , nInfinitesimal ge( , ( ), nerator (nvi jvijvDvvv MXXXPp i v ijAa v ,00( )(, ()|,( ) satisfies ( (1), (2), ()Average-cost performance crite ria (infinite h

36、orizon) under polic y 1limNi jvvsTvttNNviEf Xv Xdt Xi iiAdiagMPIT00,If underlying Markov chain for policy is unichain, then ( ) ( )(, ()|,Discounted-cost performance criterialimNsvvTvttsNtvviiEf Xv Xdt Xi ivei 保守矩阵与策略v有关2022-5-1443/ 51Problem formulation (3) optimization objective*argminargminIf con

37、sider continuous-time MDP or SMDP, the objective is to find Stationary distributio or of states ( (1),(n2),()vvvvvvvvssvvM Balance equations: Markov Chain: ,1 Continuous MDP: 0,0,1 1,1,1vvvvvvvvvPP eeeAA eee2022-5-1444/ 51Potential-based optimization via numerical computation (1) performance potenti

38、al00Definition of performance potential via Poisson equation (Cao 1997) MDP: () MC: () ( ) ()Performance vvvvvvvvvnvnnnIAefIPefgiEf Xv XXgig *potential-based Bellman optimality equation MDP: 0min MC: min()0 or min0Optimization sssvvvvvvvvvvvvvvvvfA gfPI gfP gge based on potentials have two advantage

39、s: Optimization of , and can be unified through potentials; Optimization algorithmSMDP MDPMCaverage- and discounted criterias for both can be unified whether they are realized by numerical computation or simulation2022-5-1445/ 51Reinforcement learning of potentials00A continuous-time MDP (or SMDP) c

40、an be treated as a uniformized MC (UMC)Definition of the performance potential for UMC via sample path ( ) () TDvnvnnngiEf X v XXi111 ( ) learning of the performance potential (, ()()() : (1)()( )if ( ) ( ) 1 otherwis( ):( )(r( )e)o vvvnnnnnvvnvnnnnnnnvnnndfX v XgXgXf X vgigiXziXiz izzzdiii 1( )if (

41、 )1otherwisennnziXii(unified temporary difference)(eligibility trace)2022-5-1446/ 51Semi-Markov decision processes (SMDPs) Relations of different models MDPContinuous-time MDPDiscrete-time MDP(Markov chain)SMDPnIn many cases, the study of a SMDP is realized by transforming to a controlled Markov cha

42、in, if the model is knownE.g., such as a preventive problem provided in the book Simulation-based optimizationFig. 5 Relations of different models 2022-5-1447/ 51Optimization methods & difficult problems Overview of different optimization methodsnNumerical computation Value iteration Policy iteratio

43、n (Non) Linear programmingnSimulation methods Monte-Carlo methods Reinforcement learning Neuro-dynamic programmingIs model known?Yes: TD learning (model-based)NO: Q-learning (model-free)Disadvantages: Model need to be known Computation of matrix inverse is difficult for large scale problems! For fin

44、ite horizon models backward induction (dynamic programming)2022-5-1448/ 51Optimization methods & difficult problems Some variants on the basic modelnBasic and simplest models: Markov chains State space and action set are both finite Stochastic process is ergodicnThere are many problems appearing now

45、! Decisions may be made in continuous time SMDP There may be a continuum of states or actions e.g. compact Model parameters may not be known or uncertain Robust decision/simulation methods System state may be not observable POMDP or HMM2022-5-1449/ 51第三章动态规划（dynamic programming）2022-5-1450/ 51 动态规划是

46、运筹学的一个分支，是求解多阶段决策过程的最优化数学方法。20世纪50年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类问题的新方法动态规划。 2022-5-1451/ 51n多阶段决策过程多阶段决策过程( multi-step decision process ) 指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。n最优化原理最优化原理 作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相

47、对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。也就是说，一个最优策略的子策略也是最优的。2022-5-1452/ 51模型分类以以“时间时间”角度可分成角度可分成： 离散型和连续型。从信息确定与否可分成从信息确定与否可分成： 确定型和随机型。从目标函数的个数可分成从目标函数的个数可分成： 单目标型和多目标型。2022-5-1453/ 51确定性问题Fig. : The shortest path problem *min,jig i jj327941381314Bellman equation(反向递推)：2022-5-1454/ 51随机问题Bellman equatio

48、n(反向递推)： *min, ,minuvvviE f i u jj i ufP2022-5-1455/ 51My previous work Potential-based policy iteration11By solving an easy subproblem argminor argminksksvvvkvvvvkvvfA gvfP gBy solving Poisson equationor by estimate/learning via simulationPolicy evaluationkvgkvgPolicy improvement1kvFig. 6 Illustrat

49、ion of policy iteration 2022-5-1456/ 51My previous work Potential-based learning optimizationReal/simulation environmentPolicy updatingPolicy evaluation(potential learning)Feedback of stateand costActionLearning value ofpotentialsEnvironmentAgentFig.7 PI based on learning2022-5-1457/ 51样本轨道学习00XX 1n

50、X11XX nX1nnnTTT2022-5-1458/ 51Neuro-dynamic programming (NDP) 函数值逼近 Neural network/Approximation mapParameter vector rApproximate cost-to-goof state j State jrjJ,2022-5-1459/ 51Neuro-dynamic programming (NDP) 分类和逼近结构In order to overcome the curse of dimensionality, approximation architecturescan be used to represent potentials or policy, leading to NDP methodology If only potentials are approximated critic-NDP If only policy is approximatedactor-NDP If both two are approximatedactor-critic NDP 1x2x3x4x5