決策會改變未來機會
局部看來吸引的獎勵未必是最佳選擇,因為行動也會改變下一個狀態。無限時域折扣馬爾可夫(Markov)決策過程明確表達這項取捨。本節研究有限且已知的模型並最大化期望獎勵;這是在已知模型下規劃,不聲稱模型已從數據學得。
定義 10.1.1
(折扣馬爾可夫決策過程)
令 為有限非空狀態集。每個狀態 有有限非空行動集 。選擇 時取得有限確定獎勵 ,再以概率 轉移至 ,這些概率非負且總和為一。模型不隨時間改變,且在給定當前狀態與行動後,下一狀態分布與更早歷史獨立。取折扣因子 。狀態—行動對只有有限個,因此獎勵有界;每條軌跡的折扣回報 均絕對收斂;即使 也約定 。策略可依賴已觀察歷史,也可隨機化;平穩確定性策略則在每個狀態選一個固定行動。對起始狀態 ,以 表示策略 的期望折扣回報,並設 。
定義 10.1.2
(Bellman 算子與價值迭代)
對以 為索引的實數向量,定義 Bellman 算子:
最大化在期望之外:行動在抽出下一狀態之前選定。有限行動集保證存在達到最大值的行動。價值迭代可由任意有限向量 開始,反覆令 。
迭代為何收斂
定理 10.1.3
(Bellman 算子的收縮性)
對任何以 為索引的實向量 ,都有 。
證明
(最大值不放大差距,概率則取平均)
對向量 ,寫 。兩個有限數列最大值之差的絕對值,不大於逐項差的最大絕對值。套用此不等式,並利用概率非負且總和為一,得
此式對每個狀態都成立。因此 。
定理 10.1.4
(價值迭代收斂至唯一不動點)
對任意起始向量 ,迭代 在 下收斂至滿足 的向量 。它是 的唯一不動點,且 。
證明
(等比差值給出柯西(Cauchy)序列)
收縮性使相鄰差值按等比速度下降:。由等比級數的尾和, 在有限維上確界範數中是柯西序列,故收斂至某個 。同一不等式給出算子連續性,所以 。若也有 ,則 ,迫使兩向量相等。不動點唯一。
概念視角算法
每個迭代向量都是有限步長的最優值
由 出發,向量 是從 出發的 步計劃中, 的最大期望值:每次 Bellman 更新都在最前面多加一個決策。在兩狀態表中, 是最佳的兩步獎勵,連續停留兩次和先移動再在 收取獎勵都能達到。這也解釋了因子 :第 步之後的部分以 加權。
定理 10.1.5
(不動點就是最優價值)
設 為 的不動點。對每個起始狀態 都有 ,即使容許依賴歷史的隨機化策略亦然。此外,在每個狀態選取使 達到最大值的行動,便定義出一個平穩確定性策略 ,且 。
證明
(以 N 步把每個策略與不動點比較)
由於 不小於任何行動的 Bellman 表達式,先對已觀察歷史及所選行動取條件期望。馬爾可夫性使下一狀態期望等於所指定的概率加權和;對任意隨機行動再取平均仍保持不等式。反覆運用 步,對每個策略 得
因 有界,最後一項趨近零;若 ,獎勵尾和的絕對值最多為 。因此沒有策略可得到更大回報,即 。在每個狀態依精確向量 選取達最大值的行動,並使用該平穩策略:每步不等式均成等式,因此這個平穩確定性策略達到 ,故 。
證明透視
最優性證明中每項假設用在哪裏
不易想到的一步,是不把任意策略與未知的最優回報比較,而是與不動點 比較,並在時刻 截斷,把 當作終端獎勵。每個成分各有作用。不動點方程 提供單步不等式:對每個行動 , 不小於 。馬爾可夫性使這個不等式可在任何已觀察歷史之後套用,所以依賴歷史與隨機化都不會帶來額外好處。 與 有限使 和獎勵有界,而 使 與獎勵尾和在 時消失。論證能夠閉合,是因為對貪婪平穩策略,鏈中每個不等式都成為等式,所以這個策略達到其他策略只能從下方逼近的上界。若沒有 ,終端項不一定消失,與 的比較便無法說明無限和。
可計算的停止證書
命題 10.1.6
(殘差誤差界)
對任何以 為索引的實向量 ,令 ,則
證明
(三角不等式加收縮性)
三角不等式與收縮性給出 ,其中用到 。把最後一項移到左邊,得 ,而 ,故可兩邊除以它。
小殘差證明價值向量在上確界範數下接近;它本身不能在近似行動價值接近時確定最優行動,也不表示模型精確反映真實環境。
常見錯誤
(殘差並不等於誤差)
當 接近 時,若因相鄰兩次迭代只差 便把 當作誤差,是錯誤的。取一個狀態、一個行動、獎勵 及 ,則 。數值 的誤差是 ,但 ,殘差只有 。此處誤差恰好等於 ,所以因子 不能省去。
例題
例題 10.1.7
(帶有並列的兩狀態例子)
有兩個狀態 ,且 。在 ,留守給獎勵 1 並返回 ;移動給獎勵 0 並移至 。在 唯一行動給獎勵 3 並返回 。這些確定性轉移是概率模型的特例。Bellman 方程為
從 開始,次序為 :
| 次數 | 以前一行計算時在 的最大化行動 | ||
|---|---|---|---|
| 0 | 0 | 0 | 無 |
| 1 | 1 | 3 | 留守 |
| 2 | 並列 | ||
| 3 | 移動 |
不動點的 方程給出 。在 ,移動得到 3;若 ,留守得到 ,所以移動嚴格較好。向量 滿足兩式,故是唯一不動點。第 2 次迭代的並列是用 比較行動,並非使用最終價值;它不代表最優策略並列。
例如 的殘差是 ,故誤差上界為 。此例的實際上確界誤差也恰為 。
常見錯誤
(迭代向量中的並列不代表最優值中的並列)
從中間向量讀出貪婪行動,可能選到次優行動。在上面的例題中, 使 處的留守與移動並列(兩者都給 )。但依 ,留守只值 ,移動值 ,所以只有移動是最優的。應由 取出策略,或由證書足以分開各行動的迭代向量取出。
例題 10.1.8
(隨機轉移)
令 。在 ,唯一行動給獎勵 4 並返回 。在 ,穩妥給獎勵 1 並返回 ;冒險給獎勵 0,並各以概率 移至 或 。於是
的方程給出 。檢驗向量 :穩妥的表達式是 ,冒險的表達式是 ,所以 ,而 。此向量是不動點,因此就是唯一的 ,且 處的最優行動是冒險。
再取 ,這是永遠選穩妥的策略的價值。此時 ,,故 ,證書給出誤差至多為 。真正誤差是 ,落在證書範圍內。殘差為正,反映永遠穩妥並非最優:在 冒險嚴格較好。
例題 10.1.9
(完全不重視未來的邊界情況)
沿用同一模型,但取 。算子變成:對任何 都有 ,,所以不論 為何,,且 。因此 , 處的最優行動是穩妥。當 時,同一模型偏好冒險,因為 使到達 的機會計入價值。兩者對比顯示,折扣因子決定如何在眼前獎勵與日後機會之間取捨。
限制與練習
上述收斂論證需要折扣和有界獎勵。若令 ,便失去收縮保證,而無折扣無限和可能發散;平均獎勵或有限時域問題需要各自的條件。轉移不確定性由所指定概率處理,但概率與獎勵的模型誤差需另行分析。
反例模式
取消折扣會破壞唯一性與存在性
聲稱「對每個 ,算子 都有唯一不動點,且價值迭代收斂到它」,在 時並不成立。取一個狀態、一個行動、獎勵 。此時對每個實數 都有 ,所以每個數都是不動點:由 出發的迭代停在 ,由 出發的則停在 ,唯一性失效。現在把獎勵改為 ,則 沒有不動點,而 發散,與無折扣和 發散一致。修補方法就是原有假設 (或改用有限時域、平均獎勵等其他框架)。
快速檢查
(在例題中計算 ,再多做一次 Bellman 更新以計算其殘差。用來計算 的 行動是否並列?)
解答 · 答案
用 : 處留守的表達式是 ,移動的表達式是 ,所以 ,移動嚴格較好,並無並列。又 。再更新一次得 ,所以 的殘差是 。證書把誤差限制在 內,而實際誤差 與之吻合。
快速檢查
(若 ,Bellman 算子返回甚麼?需要多少次更新才到達不動點?)
解答 · 答案
當 ,對任何 都有 ,輸出與輸入無關。從任何 出發,更新一次已得 ,第二次更新不再改變它。最優策略是短視的:選即時獎勵最大的行動。
快速檢查
(考慮另一個單步問題:共同外生隨機結果獨立於行動,每個行動—結果組合的收益均已指定。給一個兩種結果的例子,使先觀察結果再選行動能提高期望收益。解釋此資訊順序為何不同於先選行動。)
解答 · 答案
設結果為 或 ,概率各為 。行動 在 時給 1、在 時給 0;行動 在 時給 0、在 時給 1。先選行動時,每個行動的期望收益都是 。先觀察結果則可在 後選 、在 後選 ,必得 1。前一種次序計算的是 ,後一種是 。Bellman 算子中,行動在抽出下一狀態之前選定,屬於前一種次序。原 MDP 中依行動而變的轉移概率本身並未指定所有行動的共同聯合結果。
練習 10.1.10
(證明:對實數 與 ,有 。這就是收縮性證明中用到的不等式。)
基礎證明
提示(1)
選一個使 達到最大值的指標,再與 的同一項比較。
解答(3)
- 1
先證一個方向
關鍵一步
令 ,並選 使 。由於 ,得 。
依據: 的最大值不小於它的第 項 。
- 2
交換兩個數列的角色
把 與 對調,同一論證給出 。
- 3
合併兩個方向
∎與它的相反數都不大於 ,所以 。