5.4　價值迭代法

在剛剛的簡單示例中，為了計算狀態和動作的價值，我們利用了環境的結構：在轉移中沒有循環，因此可以從最終狀態開始，計算其價值，然后回到中心的狀態。但是，環境中只要有一個循環就會給這個方法造成障礙。我們來考慮具有兩個狀態的此類環境，如圖5.7所示。

我們從狀態s1開始，唯一可以采取的行動會使我們進入狀態s2。我們得到獎勵r=1，并且從s2的唯一個動作會使我們回到s1。因此，智能體會進入無限的狀態序列[s1, s2, s1, s2, s1, s2, s1, s2, …]。要處理這種無限循環，可以使用折扣因子：γ=0.9。現在的問題是，兩個狀態的價值分別是什么？實際上，答案并不復雜。從s1到s2的每次轉移的獎勵為1，反向轉移的獎勵為2。因此，獎勵序列為[1, 2, 1, 2, 1, 1, 2, 1, 2, …]。由于在每個狀態下只有一個動作，智能體沒有選擇余地，因此可以省略公式中的max運算（只有一種選擇）。

狀態的價值如下：

嚴格來講，我們無法計算狀態的確切價值，但由于γ=0.9，隨著時間的推移，每次轉移的貢獻值在減小。例如，在10步以后，γ10=0.910=0.349，但是在100步以后，該折扣因子變成0.000 026 6。由于以上原因，我們在50次迭代后停止計算，也可以得到比較精確的估計值。

前面的示例有助于理解更通用的價值迭代算法。這使我們能夠以數值計算已知狀態轉移概率和獎勵值的馬爾可夫決策過程（Markov Decision Process，MDP）的狀態價值和動作價值。該過程（對于狀態價值）包括以下步驟：

1）將所有狀態的價值Vi初始化為某個值（通常為零）。

2）對MDP中的每個狀態s，執行Bellman更新：

3）對許多步驟重復步驟2，或者直到更改變得很小為止。

對于動作價值（即Q），只需要對前面的過程進行較小的修改即可：

1）將每個Qs, a初始化為零。

2）對每個狀態s和動作a執行以下更新：

3）重復步驟2。

這只是理論。實際中，此方法有幾個明顯的局限性。首先，狀態空間應該是離散的并且要足夠小，以便對所有狀態執行多次迭代。對于FrozenLake-4x4甚至是FrozenLake-8x8（Gym中更具挑戰性的版本），這都不是問題，但是對于CartPole，并不完全清楚該怎么做。我們對CartPole的觀察結果是4個浮點值，它們代表系統的某些物理特征。這些值之間即使是很小的差異也會對狀態價值產生影響。一個可能的解決方案是離散化觀察值。例如，可以將CartPole的觀察空間劃分為多個箱體，并將每個箱體視為空間中的單個離散狀態。然而，這將產生很多實際問題，例如應該用多大的間隔來劃分箱體，以及需要多少環境數據來估計價值。我將在后續章節中（在Q-learning中使用神經網絡時）解答該問題。

第二個實際局限問題是我們很少能知道動作的轉移概率和獎勵矩陣。記住Gym所提供給智能體的接口：觀察狀態、決定動作，然后才能獲得下一個觀察結果以及轉移獎勵。我們不知道（在不查看Gym的環境代碼時）從狀態s0采取動作a0進入狀態s1的概率是多少。

我們所擁有的僅僅是智能體與環境互動的歷史。然而，在Bellman更新中，既需要每個轉移的獎勵，也需要轉移概率。因此，顯然可以利用智能體的經驗來估計這兩個未知值。可以根據歷史數據來決定獎勵，我們只需要記住從s0采取動作a轉移到s1所獲得的獎勵即可，但是要估計概率，需要為每個元組（s0, s1, a）維護一個計數器并將其標準化。

好了，現在來看價值迭代方法是怎么作用于FrozenLake的。