2.1.3 最優策略的迭代算法

與式（2.1）和式（2.2）類似，可以觀察到式（2.6）和式（2.7）也有一個遞歸的結構，也就是當前步的函數和下一步的函數有依賴關系。這就給我們使用動態規劃的算法提供了基礎。有關具體的算法步驟，這里用估計最優狀態價值函數V?（s）作為例子闡述如下。

（1）要有一個初始化的狀態價值函數作為最初的估計，記為V₀（s），在最簡單的情況下可以將這個函數初始化為零。

（2）在給定環境條件下做出模擬，基于上一步中給出的狀態價值V_t（s）函數估算最優的動作，以及該動作能夠獲得的獎勵，并且根據式（2.6）更新狀態價值函數，得到新的狀態價值函數V_t+1（s）。

（3）重復以上步驟，直到相鄰兩次迭代的狀態價值函數的差值小于給定的標準。在狀態價值函數收斂之后，可以直接采用得到的函數進行決策。可以從數學上證明（對應的每次迭代更新稱之為將貝爾曼算子（即Bellman Operator）作用于狀態價值函數，根據壓縮映射定理可以證明這個算子存在一個不動點，即收斂的最優狀態函數），這樣迭代的算法被稱為價值迭代，將會在后續的內容中進一步闡述。

下面用一個實際的例子來闡述計算最優價值函數的算法。我們從一個簡單的4×4的網格強化學習環境開始。圖2.3給出了該強化學習環境的一個實例。在這個強化學習環境中，智能體可以從任意一點出發，移動到相鄰的格點（前、后、左、右）。在圖中可以注意到，有兩個特殊的點，其中如果智能體到達B點，會被傳送到A點，并且獲得+5的獎勵。除此之外，在其他網格點移動的時候智能體不獲得任何獎勵。具體模擬的代碼如代碼2.1所示。在筆者的計算機上，取γ=0.9，控制兩次最大的價值函數差值小于0.001為收斂標準，在第81步迭代的時候算法收斂，最后收斂的結果如圖2.3右圖所示。在圖中可以觀察到，任取一點C，狀態價值函數增大的方向總是向下和向右，也就意味著最優策略的方向總是傾向于往B點的方向，從而能夠在B點獲得獎勵。這也與我們的直覺相符，即一個合理的智能體總是傾向于獲取最大的獎勵。有興趣的讀者可以試著修改代碼2.1，使用不同的參數和不同的獎勵來觀察最后收斂到的狀態價值函數的值的變化。

圖2.3 網格強化學習環境（左），迭代收斂后的結果（右）

代碼2.1 簡單的最優策略迭代算法代碼示例。