為何需要第二種算法
「折扣決策與價值迭代」一課把最優價值向量 算作 Bellman 更新的極限,再讀出貪婪策略。價值迭代要得到精確答案,需要無限多次掃描。策略迭代利用另一個事實:固定的策略可以通過解線性方程組精確評估,而針對該精確價值作貪婪一步只會有益無害。有限的決策問題只有有限個平穩策略,因此評估與改進交替進行,必在有限輪後停在最優策略。本單元證明這些論斷,沿用價值迭代一課的記號:有限狀態集 、有限行動集 、轉移概率 、報酬 、折扣 ,以及 Bellman 算子 。
定義
定義 34.1.1
(平穩策略及其算子)
平穩確定性策略是函數 ,對每個狀態有 。記 ,並令 為元素 的矩陣,其每一行都是概率向量。對價值向量 定義
定義 34.1.2
(策略價值、行動價值與貪婪策略)
的價值 是期望折扣報酬 。對向量 ,行動價值為 。若對每個 , 都使 最大,便稱 對 貪婪,等價於 。向量之間的不等式逐分量理解。
評估、單調性與改進
定理 34.1.3
(策略評估)
矩陣 可逆,,且 是 的唯一解。
證明
(由範數界得到可逆性)
若 ,則 。 的每一行都是概率向量,故 ,從而 。因 ,,所以矩陣可逆, 恰有一個解。對第一步轉移取條件,得 ,所以 就是該解。
概念視角分析
把評估看成期望報酬的折扣和
因為 ,逆矩陣是收斂級數:
分量 是從 出發、在時刻 的期望報酬,所以這正是把 定義為期望折扣報酬、再對時間求和。線性方程組是我們實際計算用的描述;級數描述則解釋了為何該解就是策略的價值,以及為何需要 。
引理 34.1.4
(備份算子的單調性)
若 ,則 且 。
證明
(較大的價值給出較大的備份)
權重 非負,所以每個 ;較小數的最大值也較小。
定理 34.1.5
(策略改進)
設 對 貪婪,則 。此外,若 ,則 ,從而 。
證明
(反覆應用貪婪備份)
因 貪婪,。反覆應用 並用單調性引理,對所有 有 。由價值迭代一課的收縮論證,,即 的唯一不動點。對不等式取極限得 。若 ,則 ,所以 是 的不動點,即 。
定理針對精確的價值 陳述。實際上不精確評估的變體,需要另外論證。
算法及其終止
策略迭代。 由任意策略 開始。對 :
- *評估:*解 得 。
- *改進:*對每個 ,令 。若 ,則取 ;否則任選一個使其最大的行動。
- 若 ,停止並回傳 。
「若現有行動已達最大值就保留」這條規則是必要的。
定理 34.1.6
(策略迭代終止於最優策略)
策略迭代至多評估 次便停止,所回傳的策略是最優的,價值為 。
證明
(嚴格上升的價值不會重複策略)
由策略改進定理,。設 。若 ,定理給出 ,於是 ,即現有行動在每個狀態都達到最大值,按保留規則便得 ,與 矛盾。所以價值向量不遞減,且每次改變策略時都嚴格不同;因此沒有策略會重複出現。策略只有 個,故過程必停止。在停止的策略處,,即 ,所以 , 達到最優價值。
證明透視
每個條件各自提供甚麼
不顯然的一步,是把「策略改變了」轉成「價值嚴格上升了」。精確評估加上貪婪改進,給出 ;保留規則則保證,只有在某個行動嚴格更好時策略才會改變,因而排除 。一個不遞減、而且每步都不同的序列不會回到先前的價值,也就不會回到先前的策略,再由策略集有限便完成論證。去掉保留規則,中間一步就失效,下面的反例會說明;去掉 ,連評估一步也可能無解。
每一輪需要解一個線性方程組(高斯(Gauss)消去法為 ),加上改進步驟的 ;價值迭代每次掃描只需後者,但要達到精度 ,所需掃描次數按 增長。界 遠大於實際常見的輪數,但這是此處所證的界。
反例模式
在平手的最大值之間來回切換永不停止
論斷:任何選取最大化行動的改進步驟都會終止。取一個狀態和兩個行動 ,各自報酬 並回到該狀態,。對任一策略,,故 ,且 。兩個策略都是最優的。若規則總是改選另一個達到最大值的行動,就會 交替下去而永不停止,雖然每個策略早已最優。保留規則則立即停止,因為 。修正後的論斷需要這條規則:只有在存在嚴格更好的行動時才更換行動。
例題
例題 34.1.7
(兩狀態問題的兩輪迭代)
兩個狀態 ,折扣 。狀態 :行動 報酬 ,以各 的概率移到 或 ;行動 報酬 ,留在 。狀態 :行動 報酬 ,留在 ;行動 報酬 ,以各 的概率移到 或 。以 開始。
評估 。 得 ; 得 。故 。
改進。 以 :,;,。所以 。
評估 。 方程為 與 。相減得 。把 代入第一式:,所以 ,。確實 。
改進。 ,;,。現有行動均達最大值,故 ,算法停止。因此 ,最優策略為 ,共評估兩次。
例題 34.1.8
(同一個評估寫成矩陣方程)
對上例的 , 的兩行都是 ,。於是
行列式為 。方程組乘以 得 與 。由第一式 ,代入得 ,所以 ,,與前面的向量相同。兩行都滿足 :,以及 。
例題 34.1.9
(折扣為零的邊界情況)
在第一個例題中取 。此時 ,,評估不費力氣。由 得 ,改進只是比較即時報酬:,。所以 ,;下一次改進時現有行動已達最大值,算法在兩次評估後停止。 時完全不顧未來,貪婪改進恰好就是選即時報酬最大的行動; 時則不然,見下一節。
常見錯誤與細微之處
常見錯誤
(對報酬而不是對價值作改進)
選取即時報酬 最大的行動會忽略未來,未必改進策略。設狀態 有行動 (報酬 ,留在 )與行動 (報酬 ,移到狀態 ),狀態 只有一個行動 (報酬 ,留在 );。對 ,,。若改選即時報酬較大的行動,得到 ,。以價值為準的檢驗比較 與 ,故保留 。
常見錯誤
(折扣為一時仍使用評估步驟)
的可逆性用了 。若 ,且只有一個狀態、一個報酬為 並留在原處的行動,則 , 奇異,方程 無解。上述形式的策略迭代是折扣情形的算法。
習題
快速檢查
(在第一個例題中評估策略 。)
先解狀態 的方程。
解答 · 答案
對 :,故 。於是 ,,。價值為 。
快速檢查
(第一個例題中策略 的價值為 。作改進一步。新策略的價值是否較大?)
算出全部四個行動價值。
解答 · 答案
以 :,,故保留 。,,故改為 。新策略為 ,價值 。
快速檢查
(在第一個例題中,由 開始策略迭代。共作多少次評估?)
使用該例題已求得的價值。
解答 · 答案
一次。評估得 ,在此價值下兩個狀態的現有行動都達到最大值(,),故 ,算法立即停止。
練習 34.1.10
(在第一個例題中評估 ,並作一次改進。)
核心
解答(3)
- 1
評估策略
得 。然後 ,所以 ,。價值為 。
- 2
計算行動價值
關鍵一步
,。又 ,。
- 3
逐個狀態決定保留或改換
狀態 :,改為 。狀態 :,保留 。新策略為 。
練習 34.1.11
(設 ,,。證明 可逆,並求 。)
核心
解答(3)
- 1
用行列式證明可逆
的行列式為 ,故可逆。
- 2
解線性方程組
關鍵一步
方程為 與 。第二式給出 ,所以 ,得 ,。
- 3
驗算 Bellman 方程
,且 。所以 。