决策改变未来机会
维修有即时成本,却可以改变下次决策时设备的状态。只比较本期成本会忽略这个后果。有限期 Markov 决策模型记录当前状态、可选行动、成本和下一状态的分布。
定义 8.4.1
(有限期 Markov 决策模型)
设状态集 有限且非空,每个状态 的行动集 有限且非空,决策期数固定为 ,阶段为 。每期观察当前状态 、选择可用行动 、支付有限的确定成本 ,再以概率 抽取下一状态。各概率非负,对所有 的和为一。第 阶段后支付有限的终端成本 。模型已知,本篇不折现。
Markov 假设是:给定当前状态和行动后,下一状态的分布就是 ,不依赖更早的历史。容许策略可以使用过去已观察的所有状态及行动,也可随机化,但不能使用未来观察或未来随机结果。
若零件未来也取决于使用年龄,使用此模型前便须把年龄加入状态。我们最小化期望总成本,而非最坏情况下的实际成本。
反向递推
定义 8.4.2
(最优剩余成本)
是第 阶段状态为 时,在所有容许策略中,直到支付终端成本为止的最小期望成本。到达期限时 。
定理 8.4.3
(Bellman 反向递推)
对 及每个 ,
为每个阶段及状态记录任一达到最小值的行动,便得到一个确定的时变策略,而且它从每个起始状态出发都是最优的。
即时成本现在支付;求和用下一状态概率平均最优后续成本。 有限保证最小值可达。
证明
(对阶段作反向归纳)
在第 阶段,结论就是定义。假设 是第 阶段的最优剩余成本,并且从第 阶段起所记录的行动从每个状态出发都达到它。把递推式中的方括号记作 。
下界。 固定任一容许策略,以及任一在第 阶段停于状态 的历史。策略以某些概率 选取 。给定 ,由 Markov 假设,下一状态的分布是 。观察到 后,策略从第 阶段起的做法是一个从 出发的容许策略,因此其期望成本至少为 。所以期望成本至少为
可达。 选一个达到最小值的行动,并在观察到每个可能的下一状态后采用所记录的策略,其期望成本恰为 。故 等于该最小值,而所记录的策略从第 阶段起是最优的。平局可任选。
证明透视
Markov 假设与有限性在归纳中的作用
关键一步是对下一状态取条件:一旦观察到 s′,余下的问题又是同一形式的问题,只是从第 t+1 阶段开始。这一步需要 Markov 假设。若转移分布依赖更早的历史,从 s′ 出发的后续成本便取决于如何到达 s′,第 t+1 阶段的 V 就不再只是 s′ 的函数。
随机化由一条平均不等式处理:方括号的加权平均永不低于其最小值,所以确定性选择没有损失。行动集有限只用于保证最小值可达;若行动有无限多个,下确界未必由任何行动达到。归纳必须反向进行,因为每一阶段都需要下一阶段的值,而起点由终端成本提供。
两期维修
例题 8.4.4
(随时间改变的维修策略)
令 分别代表良好和不良状态,。在 ,保养成本 并肯定保持 ;等待成本 ,下一状态以各 概率为 或 。在 ,维修成本 并肯定转为 ;等待成本 并肯定保持 。两期规则相同,终端成本为 、。
第 阶段,,故保养;,故维修。第 阶段,,故等待;最后 ,故等待。现在在 等待最优,下一阶段在 却是保养最优:剩余决策期限会影响策略。
反例模式
即时成本最低不一定最好
第 1 阶段状态为 B 时,等待的即时成本为零,但留下终端成本四;维修成本二并使终端成本为零,总成本二较小。只看即时成本会选等待,因而非最优。这是期望成本比较;转移模型改变时策略也可能改变。
例题 8.4.5
(评估短视策略)
“永远等待”这个策略可用同一递推评估,只须把最小值换成它唯一的行动。第 阶段:从 出发的期望终端成本是 ,从 出发是 。第 阶段从 出发:。最优值 只是它的一半,所以在这里忽略未来会使期望成本加倍。从 出发,短视策略的成本是 ,而 。
例题 8.4.6
(增加第三期)
保持相同规则而令 。最后两期的值与前面相同,现在记作 与 ,所以新的第一期使用 及 :
两个状态在第 阶段都等待。在状态 ,维修被推迟到最后一期:在第 阶段维修的成本是 ,因为恢复良好后仍要再照看两期。验算:从 出发“等待、等待、维修”的成本是 。
常见错误
常见错误
(每一期都沿用同一条决策规则)
最优行动取决于阶段,而不只取决于状态。在两期例子中, 的最佳行动在第 阶段是等待,在第 阶段是保养。只由状态对应行动的单一规则无法表示这个最优方案。
常见错误
(漏掉终端成本)
递推从 开始,而不是 。若取 ,第 阶段在 等待看似成本为 ,维修成本为 ,正确决策便被颠倒。
范围及解读
策略为每个可达的状态和阶段指定行动,也包括某条样本路径未实现的状态。最优期望成本不保证每条实际路径都有该成本。以上反向证明依赖有限期及有限行动;无限期极限、未知转移概率、部分观察、风险约束及连续状态需要额外假设,不能由此直接推出。
练习
快速检查
(在两期例子中重算 ,并指出达到它的行动。)
解答 · 答案
保养成本 ;等待成本 。故 ,保养最优。
快速检查
(第 阶段在状态 等待时,加上即时成本之前的期望后续成本是多少?)
解答 · 答案
下一状态以相同概率为 或 ,所以后续成本是 。等待的即时成本为零,所以总成本也是 。
快速检查
(若第 阶段在 等待的成本从 改为 ,其余规则不变, 是多少?)
解答 · 答案
修改后等待成本为 ,维修成本为 。故 ,两个行动平局。
快速检查
(为什么比较最后阶段的行动时需要终端成本?)
解答 · 答案
最后一次决策后到达的状态仍需支付 。省略它会改变目标,并错误地把在 等待的总成本视为零。