第5 章每阶段平均费用问题
前面几章的结论主要适用于最优总期望费用有限的情况，或者因为折扣或者因为系统最终进入没有费用的吸收态。然而，在许多情形下，折扣是不合适的，也没有无费用的自然的吸收态。在这样的情形下，优化稍后定义的每阶段的平均费用经常是有意义的。本章讨论这类优化，并将重点放在有限状态马尔可夫链上。
本章问题的介绍在第I卷7.4节中给出了。那里的分析基于每阶段平均费用和随机最短路问题之间的联系。而这一联系可以进一步被增强（见习题5.12），这里研究一种替代方法，这一方法基于与折扣费用问题的联系，具有更强的分析能力。这一联系允许我们为了启发并证明平均费用问题的结论使用在第1章和第2章中折扣费用的结论。
本章还将遇到平均费用问题的特殊性质，这一性质在第I卷和第II卷之前章节均没有遇到：在动态规划的相关分析中系统的概率结构有本质影响。特别地，重返类和相关的马尔可夫链的周期性在分析和算法中均扮演了重要角色。作为结果，本章的内容与随机过程理论的联系比我们到目前为止看到的都要强。第I卷附录D中复习的马尔可夫链理论对我们的分析中的大部分是足够的。一些额外的知识，比如与周期性马尔可夫链相关的内容，将在需要时复习；也可参考教材[BeT08]。
5.1 有限空间平均费用模型
为本章的优先状态和有限控制空间的问题建模。采用2.1节中n-状态折扣问题的马尔可夫链符号。特别地，将状态记作1,,n。对每个状态i和控制u，有对应的一组转移概率pij(u),j=1,,n。
······
每次系统在状态i并使用控制u时，产生费用g(i,u)，系统以概率pij(u)移动到状态j。目标是在满足对所有的i和k，有μk(i)∈ U(i)的所有策略π={μ0,μ1,···} 中最小化从给定的初始状态x0出发的每阶段平均费用，定义如下
.N.1. 
Jπ(x0)=limsup1 E.g(xk,μk(xk))(5.1)k=0
N→∞ N 在这一定义中，使用limsup而不是lim的原因是limsup保证对所有的π和x0均存在，而极限不一定存在。稍后将证明我们将使用极限来定义每个平稳策略的平均费用（见后续的命题5.1.2）。不过，尽管我们的分析将主要涉及平稳策略，为了保持数学上的严格性，用limsup来定义非平稳策略的平均费用是很关键的（见习题5.3中的例子）。建模平均费用问题的另一种方法是引入一个策略的“上”和“下”费用，
1 .N.1	. 
Jπ +(x0)=limsupE.g(xk,μk(xk))k=0
N→∞	N 1 .N.1. 
Jπ.(x0)=liminfE.g(xk,μk(xk))N→∞ N k=0

通过分析，证明对特定的感兴趣的策略π，有Jπ +(x0)=Jπ.(x0)，此时Jπ +(x0)和Jπ.(x0)的相同值可被视作从x0开始的π的费用。
如同在之前的章节中一样，对平稳策略μ，用Jμ(x0)表示策略μ从x0开始的平均费用，使用如下的符号简写：
gμ 
= 
. .
. 
g(1,μ(1))
... 
g(n,μ(n))
. .
.
,Pμ 
. .
. 
p11(μ(1))(μ(1))···p1n
... 
pn1(μ(n))(μ(n))···pnn
. .
. 
= 
. .
. 
Jμ(1)
... 
Jμ(n)
. .
.
Jμ = 
SSP虑所生成的状态序列，并按照到达特殊状态将其分为环。然后断言每个环都可被视作对应的n ..
结论概览. 
尽管本章的内容不依赖第I卷7.4节的平均费用的分析，仍值得小结部分分析的主要特点。我们在那里假设有一个特殊的状态，记为n，是与每个平稳策略对应的马尔可夫链的常返态。其思想是考
问题的状态轨迹，其终了状态是n。更精确地，这个SSP问题的状态是1,,n，加上一个人造的终了状态t，从状态i以概率pin(u)
··· 
移动到状态t。从一个状态i到另一个状态j=.n的转移概率与原问题相同，不过从i到n的转移概率是0。每个状态–控制对(i,u)的期望阶段费用是g(i,u). λ，其中λ是从特殊状态n开始的每个阶段的最优平均费用。
我们证明这个SSP问题本质上等价于原先的每阶段平均费用问题，对应的贝尔曼方程和最优平稳策略本质上是相同的。基于此，证明若干结论，小结如下：
(a) 最优平均费用与初始状态独立。

(b) 贝尔曼方程形式如下


n
g(i,u)+
..
λ+h(i)=min
u∈U(i)
pij(u)h(j)
,i =1, ,n (5.2)
··· 
j=1
其中h(n)=0，λ是最优平均费用，h(i)可解读为每个状态i的相对或者微分费用（这是在所有策略中，从i第一次到达n的期望费用。如果每阶段平均费用等于在所有状态的平均值λ之间差别的最小值）。
(c)有值迭代（简记为VI）、策略迭代（简记为PI）的版本和线性规划方法，可被用于在合理的条件下计算求解。

现在将提出基于平均费用和折扣问题之间的联系，这是本章更强大的分析基础。这里是这一联系的概要：

(1)α-折扣最优费用可被表示为α的一系列展开，展开式中的第一和第二项是最优平均费用（现在是可能具有不等元素的向量）和一个微分费用向量。

(2)存在平稳策略同时对所有的接近1的α是α-折扣最优的，同时对平均费用问题是最优的。这被称为Blackwell最优策略。



(3)α-数列展开和Blackwell最优策略被用于开发一对耦合的最优性条件，最为贝尔曼方程的替
代。当最优平均费用对所有的初始状态相等时，这一方程组退化为贝尔曼方程[见式(5.2)]。折扣和平均费用问题的联系也在超出有限空间问题的领域有用，正如将在5.6.3节中看到的那样。
关于有限状态马尔可夫链
有限状态马尔可夫链的理论在本章中扮演重要角色。为了方便引用，这里小结将使用的一些定义和性质（参见第I卷附录D）。
给定有限状态马尔可夫链，转移概率矩阵为P，我们知道，常返类是一个状态集合互相连通，从
该集合中任意状态，以概率1最终到达该集合中的所有其他状态，以概率0到达该集合以外的状态。
有两类状态：常返的，即属于某个常返类的状态（这些状态一旦被访问，就将以概率1被无穷次访问）
和过渡态，这些状态是非常返的（这些状态以概率1将仅被访问有限次，无论初始状态是什么）。马
尔可夫链和P被称为是周期性的，如果存在一个常返类，其中的状态可以被分为d>1个不相交的
子集合X1,,Xd，满足所有从一个子集合的转移将进入另一个子集合。更精确地说，
··· 
.j ∈ Xk+1,k=1,,d. 1 
如果i ∈ Xk且pij>0,那么j ∈ X1, ··· k = d 
否则这些状态被称为非周期的（例如，见教材[BeT08]）。P的特征值位于复平面的单位圆内（模小于等于1），其中1是一个特征值，对应的特征向量是e=(1,,1).。注意P是非周期的当且仅当其所
··· 
有特征值，除了特征值1，严格位于单位圆内。可以证明P是非周期的，当且仅当Pk(k →∞) 收敛到矩阵

1 N.1
P . = lim . P k
N→∞ N k=0
上述定义的极限总是存在，这将在如下命题5.1.1中证明。如果马尔可夫链仅由一个常返态组成，那么可以证明当且仅当对某个k时它是非周期的，矩阵Pk 的所有元素是正的。
注意矩阵P . 的结构。其第ij个元素[P.]ij是当初始状态为i时长期平均访问状态j的频率。所以，如果i是一个常返态，那么[P.]ij>0当且仅当j是常返的并属于和i相同的常返类。进一步地，对所有的i，有[P.]ij=0，当且仅当j是过渡态。
5.1.1 与折扣费用问题的关系
考虑如下对应的α-折扣问题的平稳策略μ的费用。给定
∞. ∞. 
Jα,μ=.αkP k gμ = . αkP k gμ =(I . αPμ).1 gμ,α∈ (0, 1) (5.3)
μμk=0k=0
为了理解与μ的平均费用Jμ的关系，注意可以写为

1 .N.1.Jμ(i)=limsupE.g(xk,μ(xk))
k=0
N→∞ N .N.1E . αk g(xk,μ(xk)). 
= lim sup lim k=0
α1 N.1→
N→∞ . αk 
k=0
假设上式右侧两个极限运算的顺序可以交换，有
.N.1. 
E . αk g(xk,μ(xk))
Jμ(i)=limlimsupk=0
α1
→N→∞ N.1αk 
k=0
.N.1. 
lim E . αk g(xk,μ(xk))
= lim N→∞ k=0
α1 N.1
→	lim . αk N→∞k=0
= lim (1 . α)Jα,μ(i)
α1
→
上述关系式的正式证明将作为下一个命题的推论给出，同时也提供了Jμ和(1. α)Jα,μ之间差别的一
个估计，形式如下
(1 . α)Jα,μ=Jμ+(1. α)hμ+O(|1 . α| 2) 
其中hμ是某个向量，O(1. α2)是一个α-相关的向量满足limO(1. α2)/1. α=0（见如下命
||	→||||
题5.1.2）。下面的命题提供了对转移概率矩阵的一些一般性的结α论1，也是本章的基础背景。证明并没
有提供对动态规划的深入启示，对其细致的阅读对于理解本章的主要内容并不重要。
命题5.1.1对任意转移概率矩阵P和α∈ (0,1)，有
(I . αP).1 = (1 . α).1P.+H+O(|1 . α|)	(5.4) 
其中O(|1 . α|)是α-相关的矩阵满足
limO(|1 . α|)=0 
α1
→
矩阵P . 和H给定如下N.1P . = lim 1 . P k (5.5) N→∞ N k=0
H =(I . P+P.).1 . P .	(5.6) 
[在证明中将有一部分证明式(5.5)中的极限和式(5.6)的逆存在。]进一步地，P. 和H 满足如下方程：
P . = PP . = P .P = P .P .	(5.7) 

P .H = HP . = 0 (5.8) 
P . + H = I + PH (5.9) 
证明根据矩阵求逆公式将逆的每一项表示为两个行列式的比例（Cramer规则），可以看到矩阵M(α)给定如下M(α)=(1. α)(I. αP ).1 
可以被表示为一个矩阵，元素或者为0，或者为一个分式，分子分母为α的多项式且没有公因子。M(α)的非零元素的分母多项式不可能以1为根，否则的话，M(α)的某些元素将在当α→ 1时趋向无穷；这是不可能的，因为由式(5.3)，对任意的μ，有(1. α).1M(α)gμ=(I. αP ).1gμ=Jα,μ和|Jα,μ(j)| . (1 . α).1 max |gμ(i)|，这意味着M(α)gμ的元素的绝对值对所有的α<1以max|gμ(i)| 为
ii 
界。所以M(α)的第(i,j)个元素具有如下形式
mij(α)=γ(α. ζ1)··· (α . ζp)
(α . ξ1)(α. ξq)···
其中γ、ζi(i=1,,p)和ξi(i=1,,q)是标量，满足ξi=1对i=1,,q。
定义······P . =limM(α).··· (5.10)
α1
→
令H为矩阵，第(i,j)个元素为在α=1的.mij(α)的一阶微分。根据M(α)的元素mij(α)的一阶泰勒展开，对在α=1邻域中的所有的α有
M(α)=P.+(1. α)H+O((1. α)2) (5.11) 
其中O((1. α)2)是α-依赖的矩阵满足
O((1. α)2)
lim =0 
α1 (1 . α)
→
将式(5.11)乘上(1.α).1 ，得到所希望的关系式(5.4)[尽管我们已经证明了P. 和H也分别由式(5.5)
和式(5.6)给定]。现在按照顺序证明式(5.10)定义的P. 满足式(5.7)、式(5.6)、式(5.8)、式(5.9)和式(5.5)。现在有
(I . α)(I. αP )(I . αP).1 = (1 . α)I(5.12)
通过整理，有
αP (1 . α)(I. αP).1 = (1 . α)(I. αP).1 +(α . 1)I 
通过当α → 1时取极限并使用式(5.10)，于是有
PP . = P . 
此外，通过在式(5.12)中交换(I. αP)和(I. αP ).1 的顺序，类似地有P .P = P .。由PP. = P .，还有(I. αP )P . = (1 . α)P. 或者
P . = (1 . α)(I. αP).1P . 

通过当α → 1时取极限并使用式(5.10)，有P. = P .P .。于是式(5.7)得到证明。使用式(5.7)，有(P. P .)2 = P 2 . P .，且类似地有
(P . P.)k = P k . P.,k>0
所以
∞
(I . αP).1 . (1 . α).1P . = . αk(P k . P .) 
k=0
∞
= I . P . + . αk(P . P.)k 
k=1
=(I . α(P. P.)).1 . P . 
另一方面，由式(5.11)，有
H=lim.(1. α).1M(α). (1 . α).1P .. 
α1
→
=lim.(I. αP).1 . (1 . α).1P .. 
α1
→
通过综合之前两个方程，有
H + P . = lim Ak (5.13) 
k→∞ 
其中
Ak =(I . αk(P. P.)).1 
且{αk} 是一个数列满足αk1。式(5.13)的左侧乘上I.P + P . 并在右侧乘上等价的矩阵limA.k 1 ， 
有↑ k→∞ 
(I . P+P.)(H+P.)=limA.1 limAk=lim.A.1Ak.=I
kkk→∞ k→∞ k→∞ 
其中第二个等号是因为左侧的两个极限已知存在。所以
H + P . =(I . P+P.).1 
这将获得H所期望的式(5.6)。由式(5.6)，有(I. P+P.)H=I. (I . P+P.)P.或者，使用式(5.7)，(I . P + P .)H = I . P . (5.14) 
在关系式两侧前端乘上P . 并使用式(5.7)，有P.H=0，这是式(5.8)的一部分。式(5.9)于是来自式(5.14)。类似地，在(5.14)后侧乘上P. 并使用式(5.7)，有(I. P+P.)HP.=0注意I. P + P . 的可逆性，意味着HP. =0，为式(5.8)的剩余部分。

将式(5.9)乘上Pk 并使用式(5.7)，有
P . + P kH = P k + P k+1H,k=0,1
··· 
对这一关系式在k =0, ,N . 1 相加，有
··· 
N.1NP.+H=.Pk + P N Hk=0
除以N，对N→∞ 取极限，并使用P N /N0这一事实（因为P以及PN 是转移概率矩阵）可获得式(5.5)。→ 注意式(5.5)的矩阵P. 可被用于精确表示转移概率矩阵为P的任意马尔可夫链的平均费用向量J和费用向量g作为极限：
1 N.1. 1 N.1. 
J = lim sup . P k g = lim . P k g 
N→∞ N N→∞ N 
k=0k=0
并最终有
J = P .g 
为了解释这一关系式，注意可以将P . 的第i行视作从状态i开始的稳态概率向量；即，P. 的第ij个元素p.表示从状态i出发的马尔可夫链长期来看停留在状态j的时间比例。所以上面的方程给出
ij n
了从状态i出发的平均费用J(i)，作为所有单阶段费用gj通过对应的稳态概率加权后的和.p.。
ij gj 
i=j
下面的命题将α-折扣和平均费用对应到一个平稳策略。
命题5.1.2（Laurent数列展开）对任意平稳策略μ和α∈ (0,1)，有
Jα,μ=(1. α).1Jμ+hμ+O(|1 . α|) (5.15) 
其中Jμ和hμ给定如下Jμ=Pμ.gμ,hμ=Hμgμ(5.16)
满足
. 1 N.1. Pμ.= lim . Pμk ,Hμ=(I. Pμ + Pμ.).1 . Pμ.
N→∞ N k=0
[参见式(5.5)和式(5.6)]。进一步地，有Jμ=PμJμ(5.17)
Jμ+hμ=gμ+Pμhμ(5.18)
证明式(5.15)来自式(5.3)和式(5.4)，并注意到如下替换P=Pμ,P. = Pμ.,H=Hμ和hμ=Hμgμ。将式(5.9)乘上gμ并使用相同的替换得到式(5.18)。式(5.17)源自Jμ=Pμ.gμ，通过乘上Pμ并使用Pμ.=PμPμ.这一事实[参见式(5.7)]。

式(5.15)将被称为平稳策略μ的折扣费用的Laurent数列展开。① Laurent数列展开中的向量Jμ和hμ是唯一定义的，并将分别被称为μ的增益和偏差。我们注意到关于偏差的两个有用的方程。第一个是
Pμ.hμ=0(5.19)
这来自hμ=Hμgμ的定义和Pμ.Hμ=0这一事实[参见式(5.8)]。第二个是
N
. N→∞ k=0 
lim 
P k 
μ 
(gμ. Jμ)(5.20)
hμ = 
该式在如下假设下成立
Pμ.= lim PμN (5.21)N→∞ 
（这一假设反过来当Pμ对应于非周期常返类的马尔可夫链；比如[BeT08]。）为了证明式(5.20)，使用方程gμ. Jμ = hμ . Pμhμ[参见式(5.18)]来写出
NN
P k 
μ 
(gμ. Jμ)=
Pμk(hμ. Pμhμ)=hμ. PμN+1
hμ 
k=0k=0
于是对N →∞ 时取极限，并使用式(5.21)和式(5.19)。式(5.20)的一个有趣的解释是这一偏差可被视作相对费用：这是μ的总费用和如果每阶段的费用是平均值Jμ时将产生的总费用之间的差别。
不幸的是，μ的增益-偏差对(Jμ,hμ)不能通过求解式(5.17)和式(5.18)的系统方程组来确定，因为这个系统有无穷多个解；例如，对(Jμ,hμ+γe)，[其中γ是标量，e是单位向量（所有元素等于1）]是一个解。我们将解决这一问题，并在命题5.1.9中刻画所有解构成的集合，并在5.4节中讨论策略迭代时讨论这个问题。
5.1.2 Blackwell最优策略
Laurent数列展开（命题5.1.2）证明了Jμ，平稳策略μ的平均费用向量，包括3个α-依赖的项：
Jμ = (1 . α)Jα,μ. (1 . α)hμ+O(|1 . α| 2) (5.22) 
①式(5.15)有时被称为截断Laurent数列展开以区别于另一个更细致版本的展开，其中O()这一项显式定义为涉及α、gμ和Pμ的幂级数。这一幂级数展开给定如下. ∞. |1 . α|
Jα,μ=(1+ρ)ρ.1Jμ + hμ + . ρk ykk=1
其中
ρ =1 . α,yk=(.1)kHk+1gμ,k=1,2,αμ ··· 
并有
Hμ =(I . Pμ+P.).1 . P .
μμ 
[参见式(5.6)]。注意上述展开与命题5.1.2中给出的截断版本一致（ρhμ这一项可以并入求和的第一项）。这一展开对0<ρ<|ν|有效，其中ν 是I . Pμ 的最小非零特征值。我们并不需要使用这一更为细致的展开；这一展开在平均费用问题的分析中的几个有趣的问题中有用，不过那些问题超出了我们的讨论范围。

(1)11其中的项对时趋向起支配作用，因为的元素通常在时变得渐近无穷。αJαJα.≈α,μα,μ → 1所以对所有最小化的策略也将最小化平均费用。这启发了一类特殊的策略，将提供平αJJ≈ α,μμ 均费用和折扣问题之间的关键的概念上的联系。Blackwell 5.1.1定义平稳策略被称为是最优的：如果该策略对所有的折扣问题同时是最α-μ (ˉ1)ˉ1优的，其中在一个区间中，。αα, α< Blackwell 5.1.7稍后将证明最优策略在所有策略中是最优的，不论是否为平稳策略（命题）。可1策略有一些优势：它不仅最小化每个截断的平均费用，正如上面提到的，由定义，它对最小化α ≈ 5.7折扣费用。所以它不仅优化了稳态平均性能，而且在某种程度上优化了系统的过渡性能；参见α-[(5.3)]Cramer()参见式和用行列式表示矩阵求逆的规则，我们知道，对每个和状态是iJiαμ ，α,μ()()的有理函数，即，两个的多项式的比例。所以，对任意两个平稳策略和以及.αJiJiμμ.α,μα,μ(01)的图或者相同或者仅在区间上相交有限次。因为只有有限多个平稳策略，所以结论是对每个状, iiˉ(01)(ˉ1)态有一个策略和标量，满足对的折扣问题当初始状态是时是最优iααααi-∈∈μμi , i, i()的。于是，对每个，有如下的折扣问题达到贝尔曼方程的最小值iiα-μ，. 
α是某个标量，满足0<ˉ注意，由式(5.22)，对任意平稳策略μ，有
Jμ = lim (1 . α)Jα,μ
α1
→
因为Blackwell最优策略对所有的充分接近1的α在所有μ上最小化Jα,μ，所以Blackwell最优策略在平稳策略中是最优的。
能存在平稳最优策略非Blackwell最优（见习题5.4）。不过，Blackwell最优策略比其他平均费用最优
节中对m-折扣最优性的讨论。下面的命题建立了Blackwell最优策略的存在性。命题5.1.3存在Blackwell最优策略。
证明由关系式
Jα,μ=(I. αPμ).1 gμ 
n
....
Jα(i)=min
g(i,u)+αpij(u)Jα(j)
u∈U(i)
j=1
对所有的在区间(maxαˉi,1)中的所有的α成立（参见命题1.2.3）。考虑对每个i通过μ.(i)=μi(i)定义的平稳策略。于是i对所有的i，μ.(i)达到贝尔曼方程的最小值，所以μ. 对所有的α ∈ (maxαˉi,1)
i 
的α-折扣问题是最优的（参见命题1.2.3）。所以μ. 是Blackwell最优的。
现在将使用Blackwell最优策略作为一个分析工具来对平均费用问题推导类似于贝尔曼方程的关系式。在这一过程中，还将证明Blackwell最优策略在所有策略中是最优的。下面的命题提供了这一推导中的第一步。
命题5.1.4(a)所有的Blackwell最优策略有相同的增益和偏差向量，即，对任意两个Blackwell最优的μ和μ.，Jμ=Jμ. ,hμ=hμ. 
其中(Jμ,hμ)和(Jμ. ,hμ. )在Laurent级数展开中分别对应于μ和μ.（参见命题5.1.2）。

(b)由(a)部分，令(J.,h.)为所有Blackwell最优策略的共同的增益–偏差对。有
J.(i)=min
n
. U(i)∈uj=1 
pij(u)J.(j),i=1,,n(5.23)
··· 
和
J.(i)+h.(i)=min
U(i)
u∈ ˉ
..
g(i,u)+
n
. j=1 
pij(u)h.(j)
..
,i =1, ,n (5.24)
··· 
其中对每个i，Uˉ(i)是在式(5.23)中达到最小值的控制集合。进一步地，如果μ. 是Blackwell最优策略，那么μ.(i)对所有i达到这两个方程右侧的最小值。证明(a)由命题5.1.2，有
Jα,μ=(1. α).1Jμ+hμ+O(|1 . α|)Jα,μ. =(1 . α).1Jμ. +hμ. +O(|1 . α|)

因为对所有充分接近1的α，有Jα,μ=Jα,μ.，通过在上面的方程中当α → 1时取极限，有Jμ=Jμ. 和hμ=hμ. 。
(b)令μ. 为Blackwell最优策略。因为μ. 对所有在区间(ˉα,1)中的α-折扣问题是最优的，所以一定有，对每个平稳策略μ和α∈ (ˉα,1)，gμ. +αPμ. Jα,μ. .gμ+αPμJα,μ. (5.25)由命题5.1.2，对所有α∈ (ˉα,1)，有Jα,μ. = (1 . α).1J.+h.+O(|1 . α|)在式(5.25)中代入这一关系式，有0.gμ. gμ. +α(Pμ. Pμ. ).(1. α).1J.+h.+O(|1 . α|). (5.26) 或者与之等价的，乘以1 . α， 0 . (1 . α)(gμ. gμ. )+α(Pμ. Pμ. )(J.+(1. α)h.+O((1. α)2)) 当α → 1时取极限，有Pμ. J. .PμJ.，这等于式(5.23)。如果μ满足Pμ. J. =PμJ.，那么由式(5.26)，有
0 . gμ . gμ. +α(Pμ. Pμ. )(h.+O(|1 . α|)) 当α → 1时取极限，可见μ. 在所有μ上最小化gμ+Pμh.，再使用如下方程
J.+h.=gμ. +Pμ. h.（参见命题5.1.2），可获得所期望的关系式(5.24)。