由此可以反向地逐步解出在随机策略下的最佳报酬函数.显见,它不小于在纯策略下的最佳报酬函数 在其它的情形,例如下面将介绍的折扣模型的情形,实际上只须沿着这个思路方向,做相应的改变就 也就可以得到最佳报酬函数.在历史发展给定条件下,随机策略的条件分布如果只与系统的当前状态有关 则这样的随机策略称为 Markov随机策略.如果只与系统的初始状态与当前状态有关,则称为半Mrk。v随 机策略 [注2]在实际情形中,更多出现的是复杂的情形,即对不同的状态可采取的动作集也不同,就 是说,如果系统处在状态i,则能选取的动作集合为A·于是这时相应地要求f(n)∈A·为了使 读者领会实质,在本书中我们只讨论A1们相同的简单情形,其实其方法与理论并无二致 注3]以上考虑的是 Markov策略,即当前时刻所采取的动作只依赖于当前所处的状态的简单情 形.一般如果采取的动作依赖于 Markov链的历史,那就复杂多了,但是在实际问题中,出现更多的是只 依赖当前所处的状态的情形,或者近似是这种情形.作为个别情形,也需要考虑依赖最近两个或多个时间 的历史资料的情形,此时原则上可以通过扩大状态空间维数的方法,化为 Markov策略的情形 定义16.5(最佳策略) Markov随机决策的基本问题是:寻找最优平均累计报 酬 sup( J(μo,f)及最佳马氏策略f",使平均累计报酬 J(μo,f)=sψrJ(μo,f), (16.5) 这里Sωp取遍所有的 Markov策略.这样的f如果存在,则称为最佳 Marko策略 在实际问题中,有时即使最佳 Markov策略存在,但却因为计算量过大或计算时间过 长而变得实际上不可能.而ε一最佳 Markov策略常比最佳 Markov策略更为实际可行. 定义16.6(E-最佳 Markov策略)f称为一个ε-最佳 Markoⅴ策略,如果 J( Ho, f)>sup j(Ho, f)-E [注]在求最佳 Markov策略的计算复杂度为非多项式时,求E一最佳马氏策略常常能使计算降为 多项式复杂度.可见花费这个E的代价,能带来极大的收益 定义16.7如果对于任意n,an也不依赖于ξn,但是,是随机的,即它是与 Markov链的发展无关的″常随机″行动:an=ηn(ηn是取值于A的随机变量),这种策略记 为a={n,n≤m},称为独立的随机策略 2.2有限时段总报酬准则下的最佳 Markov策略的构造 定理16.8在所有的 Markov策略类中存在最佳 Markov策略(但未必唯一) 证明证明的过程实际上就是寻找一个最佳 Markov策略的具体方法.要在 Markov策 略类中构造一个最佳的.而构造最佳 Markov策略f’的方法则完全和例16.1一样 首先取∫m(1) g(i,fm(i))=maxs4 8 (i,a=gm(D)444 由此可以反向地逐步解出在随机策略下的最佳报酬函数. 显见，它不小于在纯策略下的最佳报酬函数. 在其它的情形, 例如下面将介绍的折扣模型的情形, 实际上只须沿着这个思路方向, 做相应的改变就 也就可以得到最佳报酬函数. 在历史发展给定条件下, 随机策略的条件分布如果只与系统的当前状态有关, 则这样的随机策略称为 Markov 随机策略． 如果只与系统的初始状态与当前状态有关, 则称为半 Markov 随 机策略． [注 2] 在实际情形中, 更多出现的是复杂的情形, 即对不同的状态可采取的动作集也不同, 就 是说, 如果系统处在状态i , 则能选取的动作集合为 Ai ． 于是这时相应地要求 n f n n Ax (x )Î ． 为了使 读者领会实质, 在本书中我们只讨论 Ai 们相同的简单情形, 其实其方法与理论并无二致． [注 3] 以上考虑的是 Markov 策略, 即当前时刻所采取的动作只依赖于当前所处的状态的简单情 形． 一般如果采取的动作依赖于 Markov 链的历史, 那就复杂多了． 但是在实际问题中, 出现更多的是只 依赖当前所处的状态的情形, 或者近似是这种情形． 作为个别情形，也需要考虑依赖最近两个或多个时间 的历史资料的情形, 此时原则上可以通过扩大状态空间维数的方法, 化为 Markov 策略的情形． 定义１６.５ （最佳策略） Markov 随机决策的基本问题是：寻找最优平均累计报 酬sup f J ( m0 ,f)及最佳马氏策略 f *，使平均累计报酬 J ( m0 ,f * )= sup f J ( m0 ,f), （１６．５） 这里 Sup 取遍所有的 Markov 策略. 这样的 f *如果存在，则称为最佳 Markov 策略． 在实际问题中, 有时即使最佳 Markov 策略存在, 但却因为计算量过大或计算时间过 长而变得实际上不可能. 而e -最佳 Markov 策略常比最佳 Markov 策略更为实际可行. 定义１６.６ （e -最佳 Markov 策略） f e 称为一个e -最佳 Markov 策略, 如果 J ( m0 ,f e )> sup f J ( m0 ,f)- e . （１６．６） [注] 在求最佳 Markov 策略的计算复杂度为非多项式时, 求e - 最佳马氏策略常常能使计算降为 多项式复杂度. 可见花费这个e 的代价, 能带来极大的收益． 定义１６.７ 如果对于任意 n , an 也不依赖于 n x ，但是, 是随机的，即它是与 Markov 链的发展无关的"常随机"行动: an =hn (hn是取值于 A 的随机变量)，这种策略记 为 a { ,n m} = hn £ ，称为独立的随机策略． 2. 2 有限时段总报酬准则下的最佳 Markov 策略的构造 定理１６．８ 在所有的 Markov 策略类中存在最佳 Markov 策略(但未必唯一). 证明 证明的过程实际上就是寻找一个最佳 Markov 策略的具体方法．要在 Markov 策 略类中构造一个最佳的．而构造最佳 Markov 策略 f *的方法则完全和例１６．１一样. 首先取 ( ) * f i m ( , ( )) max ( , )( ( )) * * g i f i g i a g i m m a A m m D = Î =