決策改變未來機會
維修有即時成本,卻可以改變下次決策時設備的狀態。只比較本期成本會忽略這個後果。有限期 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
(增加第三期)
保持相同規則而令 。最後兩期的值與前面相同,現在記作 與 ,所以新的第一期使用 及 :
兩個狀態在第 階段都等待。在狀態 ,維修被延到最後一期:在第 階段維修的成本是 ,因為恢復良好後仍要再照顧兩期。驗算:由 出發「等待、等待、維修」的成本是 。
常見錯誤
常見錯誤
(每一期都沿用同一條決策規則)
最優行動取決於階段,而不只取決於狀態。在兩期例子中, 的最佳行動在第 階段是等待,在第 階段是保養。只由狀態對應行動的單一規則無法表示這個最優方案。
常見錯誤
(漏掉終端成本)
遞推由 開始,而不是 。若取 ,第 階段在 等待看似成本為 ,維修成本為 ,正確決策便被倒轉。
範圍及解讀
策略須為每個可到達的狀態及階段指定行動,包括某條樣本路徑上沒有出現的狀態。最優期望成本並不保證每條實際路徑都有該成本。有限期限和有限行動支持上述反向證明;無限期極限、未知轉移概率、部分觀察、風險約束和連續狀態空間需要額外假設,本篇並未推出這些結果。
練習
快速檢查
(在兩期例子中重新計算 ,並指出達到它的行動。)
解答 · 答案
保養成本 ;等待成本 。故 ,保養最優。
快速檢查
(第 階段在狀態 等待時,未加即時成本前的期望後續成本是多少?)
解答 · 答案
下一狀態為 或 的機會相同,所以後續成本是 。等待的即時成本為零,所以總成本亦是 。
快速檢查
(若第 階段在 等待的成本由 改為 ,其他規則不變, 是多少?)
解答 · 答案
修改後等待成本為 ,維修成本為 。故 ,兩個行動平手。
快速檢查
(最後一期的比較為何需要終端成本?)
解答 · 答案
最後一次決策後到達的狀態仍要支付 。忽略它會改變目標,並錯誤地把在 等待當作總成本為零。