第四章 系统方法的改进

4.1 马尔可夫决策过程

4.1.1 相关理论

 定义4.1 如果状态空间上的函数 满足：对每个 有 ，即 ，则称 为马尔可夫决策函数。全体决策函数所组成的集合记作F。

    如果状态空间上的概率分布函数族 满足：对每个 时刻的 ， 是 上的一个概率分布，即满足 和 。那么称 位一个马尔可夫决策规则，这里 是决策时可。决策函数是马尔可夫决策规则的退化情形。

定义4.2 一个决策函数序列 ， ， 称为马尔可夫策略。其中， 是决策时刻 的决策函数，不依赖于时刻 以前系统的历史， 。全体马尔可夫策略所组成的集合记作 ，成为马氏策略类。

一个马氏决策规则序列 称为随机马氏策略，其中 是决策时刻 的决策规则且不依赖于时刻 以前系统的历史， 。全体随机马氏策略所组成的集合记作 ，称为随机马氏策略类。

定义4.3 一个马氏决策规则序列 ，如果时刻 的决策规则 不仅是随机的，而且还依赖于时刻 以前系统的历史，这是一般的策略。全体一般策略所组成的集合记作 ，称为策略空间。

定义4.4 一个马氏策略 ，如果对每个 都有 ，则称它为平稳策略，记作 。全体平稳策论所组成的集合记作 ，并称为平稳策略类。

从上面的定义可以看到策略类之间的关系为

，

。

定理4.1 对于任意一个一般的策略 和一个状态 ，存在一个与状态 有关的随机马氏策略 ，使

对所有的时间 都成立。

证明思路 参见文献[9]定理1.2

4.1.2 最优准则

为方便起见，我们把状态按表1分别记为1，2 ，18

对策略 和固定的折扣因子 ，折扣模型的报酬效用函数定义为

表示使用策略 ，在0时刻从状态 出发的条件下，系统折扣期望总报酬。用 表示第 个分量为 的列向量，当状态空间 可列时， 为可列维向量。由 的有界性知道是 有界的，从而可以做出下面的定义。

   定义 4.5 令

为最优值函数，用向量表示为 。如果策略 使得 对所有状态 成立，则 成为折扣模型的最优策略。

4.1.3 最优方程

由定理4.1知道，对每个初始状态 和策略 ,存在随机的马氏策略其诱导的随机过程 与策略 是一致的。如果初始阶段的状态是根据其分布决定的，该随机马氏策略 不依赖于初始阶段的状态但可能依赖于那个初始的概率分布。如此类推，得到 的期望总折扣与策略 的相同，所以有

故寻找最优策略的范围就缩小到随机马氏策略类中。

下面的定理说明，任一个随机马氏策略的总期望折扣报酬可以分为一周期的期望报酬与用第一个决策规则后以 为终止报酬的和，这里 的定义可以参见下面的定理。

  定理 4.2  任取策略 ，每个状态 ，

其中 。也可以用向量和矩阵表示为

其中 ， ，这里 的 分量为 以及 为单位矩阵。

证明思路  证明参见文献[9]的定理3.1

在定理4.2中，如果使用的策略是平稳策略，即 ，则公式（4.6）可以写成

也就是说 是方程

的一个解。当 ，解是唯一的。

当 属于S上有界的实值函数的集合 时，对决策规则 和随机决策规则 ，分别定义线性算子 和随机线性算子 为

还定义算子 为

   定理 4.3 （1）存在 满足

其中 为（4.11）式所定义。这个 在 中唯一，而且有 。等式（4.12）也称为折扣模型的最优方程。

（2）对每个 ，存在唯一的 满足 ，而且有 。

证明思路 参见文献[9]定理3.3

定理4.3是十分有意义的，它保证了最优方程解的存在性，从而可以利用线性方程组实现最优值与最优策略的求解过程。

4.1.4 策略迭代算法

策略迭代算法也称为策略空间逼近法，它是求解折扣MDP的一个有效方法。特别是对于状态空间和行为空间有限的MDP问题，方程（4.7）中确定的值 可以通过下面的线性方程组得到

这样，可以建立策略迭代算法。

算法4.1 （策略迭代算法）

步骤1 令 且任取 。

步骤2 （策略求值过程）解方程（4.13）（状态空间和行为空间有限的MDP问题）或者解

得到 。

     步骤3 （策略改进过程） 选取 为一个 -改进规则，即满足