帶你讀《強化學習：原理與Python實作》之三：有模型數值疊代

點選檢視第一章 點選檢視第二章

第3章

有模型數值疊代

在實際問題中，直接求解Bellman期望方程和Bellman最優方程往往有困難。其中的一大困難在于直接求解Bellman方程需要極多的計算資源。本章在假設動力系統完全已知的情況下，用疊代的數值方法來求解Bellman方程，得到價值函數與最優政策。由于有模型疊代并沒有從資料裡學習，是以一般不認為是一種機器學習或強化學習方法。

3.1　度量空間與壓縮映射

本節介紹有模型政策疊代的理論基礎：度量空間上的Banach不動點定理。度量空間和Banach不動點定理在一般的泛函分析教程中都會介紹。本節對必要的概念加以簡要的複習，然後證明Bellman算子是壓縮映射，可以用Banach不動點定理疊代求解Bellman方程。

3.1.1　度量空間及其完備性

度量（metric，又稱距離），是定義在集合上的二進制函數。對于集合X，其上的度量

，需要滿足：

非負性：對任意的x',x''∈X，有d(x',x'')≥0；

同一性：對任意的x',x''∈X，如果d(x',x'')=0，則x'=x''；

對稱性：對任意的x',x''∈X，有d(x',x'')=d(x'',x')；

三角不等式：對任意的x',x'',x'''∈X，有d(x',x'')≤d(x',x'')+d(x'',x''')。

有序對(X,d)又稱為度量空間（metric space）。

我們來看一個度量空間的例子。考慮有限Markov決策過程狀态函數v（s）（s∈S），其所有可能的取值組成集合

，定義

如下：

可以證明，

是V上的一個度量。（證明：非負性、同一性、對稱性是顯然的。由于對于

有

可得三角不等式。）是以，

是一個度量空間。

對于一個度量空間，如果Cauchy序列都收斂在該空間内，則稱這個度量空間是完備的（complete）。

例如，實數集R就是一個著名的完備空間（事實上實數集就是由完備性定義出來的。有理數集不完備，加上無理數集就完備了），對于度量空間

也是完備的。（證明：考慮其中任意Cauchy列

，即對任意的正實數

，存在正整數K使得任意的k',k'>K，均有

。對于

，是以

是Cauchy列。由實數集的完備性，可以知道

收斂于某個實數，記這個實數為

。是以，對于

，存在正整數

，對于任意

，有

。取

收斂于

，而

，完備性得證）。

3.1.2　壓縮映射與Bellman算子

本節介紹壓縮映射的定義，并證明Bellman期望算子和Bellman最優算子是度量空間

上的壓縮映射。

對于一個度量空間

和其上的一個映射

，如果存在某個實數

，使得對于任意的

，都有

則稱映射t是壓縮映射（contraction mapping，或Lipschitzian mapping）。其中的實數γ被稱為Lipschitz常數。

第2章中介紹了Bellman期望方程和Bellman最優方程。這兩個方程都有用動作價值表示動作價值的形式。根據這個形式，我們可以為度量空間

定義Bellman期望算子和Bellman最優算子。

給定政策

的Bellman期望算子

：

Bellman最優算子

下面我們就來證明，這兩個算子都是壓縮映射。

首先來看Bellman期望算子

。由

的定義可知，對任意的

是以

考慮到

是任取的，是以有

當

時，

就是壓縮映射。

接下來看Bellman最優算子

。要證明

是壓縮映射，需要用到下列不等式：

其中f'和f''是任意的以

為自變量的函數。（證明：設

，則

同理可證

，于是不等式得證。）利用這個不等式，對任意的

進而易知

，是以是壓縮映射。

3.1.3　Banach不動點定理

對于度量空間

上的映射

，如果

使得

，則稱x是映射t的不動點（fix point）。

例如，政策π的狀态價值函數

滿足Bellman期望方程，是Bellman期望算子

的不動點。最優狀态價值

滿足Bellman最優方程，是Bellman最優算子

的不動點。

完備度量空間上的壓縮映射有非常重要的結論：Banach不動點定理。Banach不動點定理（Banach fixed-point theorem，又稱壓縮映射定理，compressed mapping theorem）的内容是：

是非空的完備度量空間，

是一個壓縮映射，則映射t在x内有且僅有一個不動點

。更進一步，這個不動點可以通過下列方法求出：從x内的任意一個元素x0開始，定義疊代序列

，這個序列收斂，且極限為

。（證明：考慮任取x0的及其确定的列

，我們可以證明它是Cauchy序列。對于任意的

且

，用距離的三角不等式和非負性可知，

再反複利用壓縮映射可知，對于任意的正整數k有

，代入得：

由于

，是以上述不等式右端可以任意小，得證。）

Banach不動點定理給出了求完備度量空間中壓縮映射不動點的方法：從任意的起點開始，不斷疊代使用壓縮映射，最終就能收斂到不動點。并且在證明的過程中，還給出了收斂速度，即疊代正比于

的速度收斂（其中是k疊代次數）。在3.1.1節我們已經證明了

是完備的度量空間，而3.1.2節又證明了Bellman期望算子和Bellman最優算子是壓縮映射，那麼就可以用疊代的方法求Bellman期望算子和Bellman最優算子的不動點。由于Bellman期望算子的不動點就是政策價值，Bellman最優算子的不動點就是最優價值，是以這就意味着我們可以用疊代的方法求得政策的價值或最優價值。在後面的小節中，我們就來具體看看求解的算法。

3.2　有模型政策疊代

本節介紹在給定動力系統的情況下的政策評估、政策改進和政策疊代。政策評估、政策改進和政策疊代分别指以下操作。

• 政策評估（policy evaluation）：對于給定的政策π，估計政策的價值，包括動作價值和狀态價值；
• 政策改進（policy improvement）：對于給定的政策π，在已知其價值函數的情況下，找到一個更優的政策；
• 政策疊代（policy iteration）：綜合利用政策評估和政策改進，找到最優政策。

3.2.1　政策評估

本節介紹如何用疊代方法評估給定政策的價值函數。如果能求得狀态價值函數，那麼就能很容易地求出動作價值函數。由于狀态價值函數隻有

個自變量，而動作價值函數有

個自變量，是以存儲狀态價值函數比較節約空間。

用疊代的方法評估給定政策的價值函數的算法如算法3-1所示。算法3-1一開始初始化狀态價值函數v0，并在後續的疊代中用Bellman期望方程的表達式更新一輪所有狀态的狀态價值函數。這樣對所有狀态價值函數的一次更新又稱為一次掃描（sweep）。在第k次掃描時，用

的值來更新

的值，最終得到一系列的

。

在實際疊代過程中，疊代不能無止境地進行下去。是以，需要設定疊代的終止條件。疊代的終止條件可以有多種形式，這裡給出兩種常見的形式。

• 疊代次數不能超過最大疊代次數

  

  ，這裡

  

  是一個比較大的正整數；
• 如果某次疊代的所有狀态價值的變化值都小于誤差容忍度

  

  ，則認為疊代達到了精度，疊代可以停止。

  誤差容忍度和最大疊代次數可以單獨使用，也可以配合使用。

值得一提的是，算法3-1沒必要為每次掃描都重新配置設定一套空間來存儲。一種優化的方法是，設定奇數次疊代的存儲空間和偶數次疊代的存儲空間，一開始初始化偶數次存儲空間，當k是奇數時，用偶數次存儲空間來更新奇數次存儲空間；當k是偶數時，用奇數次存儲空間來更新偶數次存儲空間。這樣，一共隻需要兩套存儲空間就可以完成算法。

如果想進一步減少空間使用，可以考慮算法3-2。算法3-2隻使用一套存儲空間。每次掃描時，它都及時更新狀态價值函數。這樣，在更新後續的狀态時，用來更新的狀态價值函數有些在本次疊代中已經更新了，有些在本次疊代中還沒有更新。是以，算法3-2的計算結果和算法3-1的計算結果不完全相同。不過，算法3-2在疊代次數不限的情況下也能收斂到狀态價值函數。

這裡的疊代政策評估算法具有以下兩大意義：一方面，這個政策評估算法将作為政策疊代算法的一部分，用于最優政策的求解；另一方面，在這個政策評估算法的基礎上進行修改，可以得到疊代求解最優政策的算法。相關内容将分别在3.2.3節和3.3節中介紹。

3.2.2　政策改進

對于給定的政策π，如果得到該政策的價值函數，則可以用政策改進定理得到一個改進的政策。

政策改進定理的内容如下：對于兩個确定性的政策π和π'，如果

則

，即

在此基礎上，如果存在狀态使得（3-1）式的不等号是嚴格小于号，那麼就存在狀态使得（3-2）式中的不等号也是嚴格小于号。（證明：考慮到

嚴格不等号的證明類似。）

對于一個确定性政策π，如果存在着

，使得

，那麼我們可以構造一個新的确定政策π'，它在狀态

做動作

，而在除狀态

以外的狀态的動作都和政策π一樣。可以驗證，政策π和π'滿足政策改進定理的條件。這樣，我們就得到了一個比政策π更好的政策π'。這樣的政策更新算法可以用算法3-3來表示。

值得一提的是，在算法3-3中，舊政策π和新政策π'隻在某些狀态上有不同的動作值，新政策π'可以很友善地在舊政策π的基礎上修改得到。是以，如果在後續不需要使用舊政策的情況下，可以不為新政策配置設定空間。算法3-4就是基于這種思路的政策改進算法。

3.2.3　政策疊代

政策疊代是一種綜合利用政策評估和政策改進求解最優政策的疊代方法。

見圖3-1和算法3-5，政策疊代從一個任意的确定性政策

開始，交替進行政策評估和政策改進。這裡的政策改進是嚴格的政策改進，即改進後的政策和改進前的政策是不同的。對于狀态空間和動作空間均有限的Markov決策過程，其可能的确定性政策數是有限的。由于确定性政策總數是有限的，是以在疊代過程中得到的政策序列

一定能收斂，使得到某個k，有

（即對任意

的均有

）。由于在

的情況下，

，進而

，滿足Bellman最優方程。是以，

就是最優政策。這樣就證明了政策疊代能夠收斂到最優政策。

政策疊代也可以通過重複利用空間來節約空間。在算法3-6中，為了節約空間，在各次疊代中用相同的空間

來存儲狀态價值函數，用空間

來存儲确定性政策。

3.3　有模型價值疊代

價值疊代是一種利用疊代求解最優價值函數進而求解最優政策的方法。在3.2.1節介紹的政策評估中，疊代算法利用Bellman期望方程疊代求解給定政策的價值函數。與之相對，本節将利用Bellman最優方程疊代求解最優政策的價值函數，并進而求得最優政策。

與政策評估的情形類似，價值疊代算法有參數來控制疊代的終止條件，可以是誤差容忍度

或是最大疊代次數

算法3-7給出了一個價值疊代算法。這個價值疊代算法中先初始化狀态價值函數，然後用Bellman最優方程來更新狀态價值函數。根據第3.1節的證明，隻要疊代次數足夠多，最終會收斂到最優價值函數。得到最優價值函數後，就能很輕易地給出确定性的最優政策。

與政策評估的疊代求解類似，價值疊代也可以在存儲狀态價值函數時重複使用空間。算法3-8給出了重複使用空間以節約空間的版本。

3.4　動态規劃

3.2.1節介紹的政策評估疊代算法和3.3節介紹的價值疊代算法都應用了動态規劃這一方法。本節将介紹動态規劃的思想，并且指出動态規劃的缺點和可能的改進方法。

3.4.1　從動态規劃看疊代算法

動态規劃（Dynamic Programming，DP）是一種疊代求解方法，它的核心思想是：

• 将原問題分解成多個子問題，如果知道了子問題的解，就很容易知道原問題的解；
• 分解得到多個子問題中，有許多子問題是相同的，不需要重複計算。

求解Bellman期望方程和Bellman最優方程的疊代算法就實踐了動态規劃的思想。在第k次疊代的過程中

，計算

中的每一個值，都需要用到

中所有的數值。但是，考慮到求解

各個元素時使用了相同的數值

，是以并不需要重複計算

。從這個角度看，這樣的疊代算法就使用了動态規劃的思想。

在求解的過程中，

和

都是的估計值。用一個估計值來估計另外一個估計值的做法又稱為自益（bootstrap）。動态規劃疊代算法就運用了自益的思想。

在實際問題中，直接使用這樣的動态規劃常出現困難。原因在于，許多實際問題有着非常大的狀态空間（例如AlphaGo面對的圍棋問題的狀态數約為

種），僅僅掃描一遍所有狀态都是不可能的事情。在一遍全面掃描中，很可能大多數時候都在做無意義的更新：例如某個狀态

所依賴的狀态（即那些

的狀态

）都還沒被更新過。下一節将給出一些針對這個問題的改進。

3.4.2　異步動态規劃

上一節提到，掃描一遍全部狀态可能會涉及許多無意義的狀态，浪費過多的時間和計算資源。本節介紹的異步動态規劃（asynchronous dynamic programming）可以解決部分問題。

異步動态規劃的思想是，每次掃描不再完整地更新一整套狀态價值函數，而是隻更新部分感興趣的值。例如，有些狀态

不會轉移到另一些狀态（例如對任意

均有

），那麼更新狀态

的價值函數後再更新

的價值函數就沒有意義。通過隻做有意義的更新，可能會大大減小計算量。

在異步動态規劃中，優先更新（prioritized sweeping）是一種根據Bellman誤差來選擇性更新狀态的算法。在疊代過程中，當更新一個狀态後，試圖找到一個Bellman誤差最大的狀态并更新該狀态。具體而言，當更新一個狀态價值函數後，針對這個狀态價值函數會影響到的狀态價值函數，計算Bellman誤差：

并用一個優先隊列來維護各狀态的Bellman誤差。然後從隊頭中取出Bellman誤差最大的狀态，更新其狀态價值函數。

3.5　案例：冰面滑行

冰面滑行問題（FrozenLake-v0）是擴充庫Gym裡内置的一個文本環境任務。該問題的背景是這樣的：在一個大小為的湖面上，有些地方結冰了，有些地方沒有結冰。我們可以用一個的字元矩陣來表示湖面的情況，例如：

SFFF

FHFH

FFFH

HFFG

其中字母“F”（Frozen）表示結冰的區域，字母“H”（Hole）表示未結冰的冰窟窿，字母“S”（Start）和字母“G”（Goal）分别表示移動任務的起點和目标。在這個湖面上要執行以下移動任務：要從“S”處移動到“G”處。每一次移動，可以選擇“左”、“下”、“右”、“上”4個方向之一進行移動，每次移動一格。如果移動到“G”處，則回合結束，獲得1個機關的獎勵；如果移動到“H”處，則回合結束，沒有獲得獎勵；如果移動到其他字母，暫不獲得獎勵，可以繼續。由于冰面滑，是以實際移動的方向和想要移動的方向并不一定完全一緻。例如，如果在某個地方想要左移，但是由于冰面滑，實際也可能下移、右移和上移。任務的目标是盡可能達到“G”處，以獲得獎勵。

本節将基于政策疊代算法和價值疊代算法求解冰面滑行問題。通過這個AI的開發，我們将更好地了解有模型算法的原理及其實作。

3.5.1　實驗環境使用

本節我們來看如何使用擴充庫Gym中的環境。

首先，用下列語句引入環境對象：

import gym

env = gym.make('FrozenLake-v0')

env = env.unwrapped

這個環境的狀态空間有16個不同的狀态

，表示目前處在哪一個位置；動作空間有4個不同的動作

，分别表示“左”“下”“右”“上”四個方向。在擴充庫Gym中，直接用int型數值來表示這些狀态和動作。下列代碼可以檢視環境的狀态空間和動作空間：

print(env.observation_space)

print(env.action_space)

這個環境的動力系統存儲在env.P裡。可以用下列方法檢視在某個狀态（如狀态14）某個動作（例如右移）情況下的動力：

env.unwrapped.P14

它是一個元組清單，每個元組包括機率、下一狀态、獎勵值、回合結束訓示這4個部分。例如，env.P14 傳回元組清單 [(0.3333333333333333, 14, 0.0, False), (0.3333333333333333, 15, 1.0, True), (0.3333333333333333, 10, 0.0, False)]，這表明：

接下來我們來看怎麼使用環境。與之前在第1章介紹的内容一緻，要使用env.reset() 和env.step() 來執行。執行一個回合的代碼如代碼清單3-1所示，其中的play_policy() 函數接收參數policy，這是一個16×4的np.array對象，表示政策π。play_policy() 函數傳回一個浮點數，表示本回合的獎勵。

接下來用剛剛定義的play_policy() 函數來看看随機政策的性能。下面的代碼構造了随機政策random_policy，它對于任意的

。運作下列代碼，可以求得随機政策獲得獎勵的期望值。一般情況下的結果基本為0，這意味着随機政策幾乎不可能成功到達目的地。

3.5.2　有模型政策疊代求解

本節實作政策評估、政策提升和政策疊代。

首先來看政策評估。代碼清單3-3給出了政策評估的代碼。代碼清單3-3首先定義了函數v2q()，這個函數可以根據狀态價值函數計算含有某個狀态的動作價值函數。利用這個函數，evaluate_policy() 函數疊代計算了給定政策policy的狀态價值。這個函數使用theta作為精度控制的參數。代碼清單3-4測試了evaluate_policy() 函數。它首先求得了随機政策的狀态價值函數，然後用函數v2q() 求得動作價值函數。

接下來看看政策改進。代碼清單3-5的improve_policy() 函數實作了政策改進算法。輸入的政策是policy，改進後的政策直接覆寫原有的policy。該函數傳回一個bool類型的值，表示輸入的政策是不是最優政策。代碼清單3-6測試了improve_policy() 函數，它對随機政策進行改進，得到了一個确定性政策。

實作了政策評估和政策改進後，我們就可以實作政策疊代。代碼清單3-7的iterate_policy() 函數實作了政策疊代算法。代碼清單3-8對iterate_policy() 進行測試。針對冰面滑行問題，該代碼求得了最優政策，并進行了測試。

3.5.3　有模型價值疊代求解

現在我們用價值疊代算法求解冰面滑行問題的最優政策。代碼清單3-9的iterate_value()函數實作了價值疊代算法。這個函數使用參數tolerant來控制價值疊代的精度。代碼清單3-10在冰面滑行問題上測試了iterate_value()函數。

政策疊代和價值疊代得到的最優價值函數和最優政策應該是一緻的。最優狀态價值函數為：

最優政策為：

3.6　本章小結

本章對動力已知的Markov決策過程進行疊代的政策評估和最優政策求解。嚴格意義上說，這些疊代算法都是求解Bellman方程的數值算法，而不是從資料中進行學習的機器學習算法。從下一章開始，我們将利用經驗進行學習，進入機器學習的部分。

本章要點

政策評估是求解給定政策的價值。利用Banach不動點定理，可以用疊代的方法求解Bellman期望方程，得到價值估計。

對于給定的價值函數，可以進行政策改進。政策改進的一種方法是為每個狀态

選擇動作

政策疊代交替使用政策評估算法和政策改進算法求解給定環境的最優政策。

利用Banach不動點定理，可以用疊代的方法求解Bellman最優方程，得到最優價值估計。這就是價值疊代算法。可以用疊代得到的最優價值估計計算得到最優政策估計。

基于疊代的政策評估和最優價值估計都用到了動态規劃方法和自益的思想。

傳統動态規劃的一次掃描需要對所有狀态進行全面更新，這樣會有不必要的計算。異步動态規劃算法部分避免了這個缺陷。