5.5　價值迭代實踐

完整的示例在Chapter05/01_frozenlake_v_iteration.py中。此示例中的主要數據結構如下：

• 獎勵表：帶有復合鍵“源狀態”+“動作”+“目標狀態”的字典。該值是從立即獎勵中獲得的。
• 轉移表：記錄了各轉移的次數的字典。鍵是復合的“狀態”+“動作”，而值則是另一個字典，是所觀察到的目標狀態和次數的映射。例如，如果在狀態0中，執行動作1十次，其中有三次導致進入狀態4，七次導致進入狀態5。該表中帶有鍵（0, 1）的條目將是一個字典，內容為{4：3,5：7}。我們可以使用此表來估計轉移概率。
• 價值表：將狀態映射到計算出的該狀態的價值的字典。

代碼的總體邏輯很簡單：在循環中，我們從環境中隨機進行100步，填充獎勵表和轉移表。在這100步之后，對所有狀態執行價值迭代循環，從而更新價值表。然后，運行幾個完整片段，使用更新后的價值表檢查改進情況。如果這些測試片段的平均獎勵高于0.8，則停止訓練。在測試片段中，我們還會更新獎勵表和轉移表以使用環境中的所有數據。

我們來看代碼。首先，導入使用的包并定義常量：

然后定義Agent類，該類包括上述表以及在訓練循環中用到的函數：

在類構造函數中，創建將用于數據樣本的環境，獲得第一個觀察結果，并定義獎勵表、轉移表和價值表。

此函數用于從環境中收集隨機經驗，并更新獎勵表和轉移表。請注意，我們無須等片段結束就可以開始學習。只需要執行N步，并記住它們的結果。這是價值迭代法和交叉熵方法的區別之一，后者只能在完整的片段中學習。

下一個函數將根據轉移表、獎勵表和價值表計算從狀態采取某動作的價值。我們將其用于兩個目的：針對某狀態選擇最佳動作，并在價值迭代時計算狀態的新價值。圖5.8說明了其邏輯。

執行以下操作：

1）從轉移表中獲取給定狀態和動作的轉移計數器。該表中的計數器為dict形式，鍵為目標狀態，值為歷史轉移次數。對所有計數器求和，以獲得在某狀態執行某動作的總次數。稍后將使用該值將個體計數器數值變為概率。

2）然后，對動作所到達的每個目標狀態進行迭代，并使用Bellman方程計算其對總動作價值的貢獻。此貢獻等于立即獎勵加上目標狀態的折扣價值。將此總和乘以轉移概率，并將結果匯總到最終動作價值。

圖5.8舉例說明了狀態s下采取動作a時的價值的計算。想象一下，根據經歷，我們已經執行了此動作很多次（c1+c2），并以s1或s2這兩種狀態之一結束。我們在轉移表中記錄了這些狀態轉移的次數，格式為dict {s1：c1,s2：c2}。

然后，狀態和動作的近似價值Q(s, a)將等于每個狀態的概率乘以狀態價值。根據Bellman方程，它也等于立即獎勵和折扣長期狀態價值之和。

下一個函數將使用剛剛描述的函數來決定某狀態可采取的最佳動作。對環境中所有可能的動作進行迭代并計算每個動作的價值。動作價值最大的獲勝，并返回該動作。這個動作選擇過程是確定性的，因為play_n_random_steps()函數引入了足夠的探索。因此，智能體將在近似值上表現出貪婪的行為。

play_episode()函數使用select_action()來查找要采取的最佳動作，并在環境中運行一整個片段。此函數用于運行測試片段，在這里我們不想打亂用于收集隨機數據的主要環境的當前狀態。因此，將第二個環境用作參數。邏輯很簡單，你應該很熟悉：一個片段中只需遍歷一遍狀態來累積獎勵。

Agent類的最后一個方法是價值迭代實現，得益于前面的函數，它非常簡單。所需要做的只是循環遍歷環境中的所有狀態，然后為每個該狀態可到達的狀態計算價值，從而獲得狀態價值的候選項。然后，用狀態可執行動作的最大價值來更新當前狀態的價值。

上面就是智能體全部的方法，最后一部分代碼是訓練循環和監控。

我們創建了用于測試的環境、Agent類實例，以及用于TensorBoard的SummaryWriter。

前面代碼片段中的兩行是訓練循環中的關鍵部分。首先，執行100個隨機步驟，使用新數據填充獎勵表和轉移表，然后對所有狀態運行價值迭代。其余代碼使用價值表作為策略運行測試片段，然后將數據寫入TensorBoard，跟蹤最佳平均獎勵，并檢查訓練循環停止條件。

好了，我們來運行程序：

我們的解決方案是隨機的，并且實驗通常需要12～100次迭代才能找到解決方案，但是，在80%的情況下，它可以在1秒內找到一個好的策略來解決該環境的問題。如果你還記得使用交叉熵方法需要多少小時才能達到60%的成功率，那么你就可以理解這是一個重要的進步。這有幾個原因：

首先，動作的隨機結果，加上片段的持續時間（平均6～10步），使交叉熵方法很難理解片段中什么是正確的動作以及哪一步是錯誤的。價值迭代作用于狀態（或動作）的價值個體，通過估計概率并計算期望值自然地給出了動作的概率性結果。因此，價值迭代更加容易進行，并且所需的環境數據要少得多（在RL中稱為樣本效率）。

第二個原因是價值迭代不需要完整的片段即可開始學習。在極端情況下，僅從一個例子就可以開始更新價值。然而，對于FrozenLake，由于獎勵的結構（僅在成功到達目標狀態后才得到獎勵1），仍然需要至少成功完成一個片段才能從有用的價值表中進行學習，這在更復雜的環境中可能會有一定挑戰性。例如，你可以嘗試將現有代碼轉換為較大版本的FrozenLake（其名稱為FrozenLake8x8-v0）。較大版本的FrozenLake可能需要150～1 000次迭代才能解決，根據TensorBoard圖，大多數情況下，需要等待第一個片段成功，然后就會很快收斂。圖5.9顯示了在FrozenLake-4x4上訓練的獎勵動態，圖5.10則是針對8x8版本的。

現在，是時候將剛剛討論過的學習狀態價值的代碼與學習動作價值的代碼進行比較了。