強化學習第3期：動態規劃

在介紹了MDP與強化學習的總體情況之後，我們便開始來考慮如何求解具體MDP的最佳策略方法。我們首先介紹最優控制

的內容。在最優控制中，MDP的環境是已知的，這也就是說，在給定的$s$下採取給定的$a$，進入下一個$s$的概率分佈我們是有已知的。

由於我們已經有了環境，所以我們求解MDP就不需要一個「學習」的過程。在最優控制中，主要由兩類求解最佳策略的方法。第一類是動態規劃

與HJB方程的方法，第二類則是變分法與龐特里亞金原理。這兩類方法主要應用動態規劃與微分方程來求解最佳策略，並不具有「學習」的性質。不過，動態規劃與HJB方程的思想很大程度上被移植到了強化學習中，所以我們會花兩篇的時間著重介紹一下動態規劃與HJB方程。

首先，我們先考慮最簡單的MDP。最簡單的MDP是什麼樣的呢？顯而易見，最簡單的MDP時間t是離散的，並且狀態$s$與動作$a$都是有限的，另外還是time-invariant的。例如，一個遊戲中一共有10種狀態$s$，3種動作$a$，我們求解最佳策略，就相當於是找出一個$s$與$a$之間的映射。即對於每一個當前狀態$s$，應該採取哪一種相對應的動作$a$。這可以表示成一個10×1的表格（用one-hot變數表示就是10×3的表格）。

###井字過三關

讓我們來考慮一種比較簡單的棋類遊戲，比如「井字過三關」，相信大家小時候都玩過這個遊戲。棋盤只有3×3的大小。兩個玩家一個畫「○」，一個畫「×」，只要在同一行或者同一列或者對角線上連上三個，即可獲得勝利。

我們定義一個這樣的MDP：將目前棋盤中的局勢定義為$s$，將我們下一步的走法定義為$a$。假設我們是先走的那一方，畫「○」。我們走之後輪到對方AI走。我們對手的AI設計得比較平庸——當AI看到我們已經在某一直線上連了兩個「○」，且直線剩下的一個位置是空的（我們將這種情況稱為「叫殺」），AI會選擇在該直線的第三個位置畫上「×」，以阻止我們取得勝利；如果AI發現我們暫時沒有馬上要取得勝利的局面，就會均勻地等概率隨機挑選一個空的位置走。設我們取得勝利可以獲得r=1，打成平局則r=0，如果不幸輸給對手則r=-1。這是一個我們已知環境的MDP（即我們知道每一個$s$下採取每一個$a$，進入下一個$s$的概率分佈），現在考慮求解最佳的策略，即最大概率擊敗AI的方法。

遊戲的開局顯然是同一個基礎的$s$，即棋盤上一個棋子也沒有的情況。我們要選擇第一步的$a$。一般最自然的想法是「走中間」，因為其他位置只是處在兩條或者是三條直線上，而中間的位置則是處在四條直線上，所以看起來中間的位置是一個「兵家必爭之地」。

現在考慮第一步「走中間」。這時由於AI沒有感覺到威脅，所以它會在剩下八個位置中隨機挑選一個位置走，每一個$s$的概率是八分之一。如果我們認為旋轉、對稱可以得到的棋盤都是同一種，我們事實上可以認為只有兩種不同的情況——即AI走到邊上或是走到角上。每一種走法各有$frac{1}{2}$的概率，示意圖如下所示：

<center>![png](http://cookdata.cn/media/topic_images/94_圖片_1.png)</center>

我們發現，如果是落入了下面那種情況（即AI走了「邊上」），事實上我們已經贏了。因為我們下一步選擇走到角上「叫殺」，AI就只能招架我們的進攻。而再下一步的時候，我們就形成了絕殺。也就是說，我們必然可以獲得r=1，如下圖所示：

<center>![png](http://cookdata.cn/media/topic_images/94_2.png)</center>

但是如果落入了上面的那一種情況，我們該怎麼走呢？我們有7種不同的$a$可以選擇。考慮旋轉對稱的等價性，則只有4種。這四種$a$中，有三種$a$走完對對AI構成「叫殺」。但是AI可以通過落子來化解我們的「叫殺」，並且可能會反過來對我們構成「叫殺」。這時候我們又只能應對它的叫殺，最後往往只能走出平局。如下所示：

<center>![png](http://cookdata.cn/media/topic_images/94_3.png)</center>

對於剩下一種走法（即將「○」下在「×」的斜對角），對AI不構成「叫殺」。這種情況下AI會隨機地走入剩下的六個格子中。依照旋轉對稱等價的原則，我們依舊可以認為只有三種情況，各$frac{1}{3}$的概率發生。這三種情況中，第一種情況對我們構成了「叫殺」。我們忙於應付，最後會打成一場平局；第二種情況中，AI沒有對我們構成威脅，我們再走一步便成功絕殺；第三種情況下，AI則給我們氣勢洶洶地來了個「叫殺」，我們必須應付。可是沒想到我們一應付，就反過來將AI給絕殺了，這AI真可謂「扛起石頭砸自己的腳」。如下圖所示：

<center>![png](http://cookdata.cn/media/topic_images/94_4.png)</center>

上面這番分析意味著，如果AI走了角的話，我們選擇下一步「叫殺」其實是沒有好處的，因為這樣無法獲得勝利，肯定只有r=0；我們最佳的走法應該是走到它的對角，讓它隨機走一步。這樣，我們仍舊有$frac{2}{3}$的概率可以獲得勝利，拿到r=1。

總結地說，如果我們第一步走了中間，則我們面臨兩種情況：AI走「邊上」以及AI走「角落」，兩種情況各一半的概率。如果AI選擇了「走邊上」，則我們必然可以取得勝利，獲得r=1；而如果AI選擇走「角落」，則我們最佳的走法應該是走到它的對角，這樣也有$frac{2}{3}$的概率取勝。在面對初始$s$，採取「先走中間」的$a$的情況下，我們取得的r的期望是$frac{1}{2} + frac{1}{2} frac{2}{3} = frac{5}{6}$。

既然面對初始$s$「先走中間」獲得的r期望有$frac{5}{6}$之高。那麼它是不是最佳的策略呢？答案可能令人意外——這並不是最佳的策略。

考慮我們第一步走「角落」。由於沒有對AI產生威脅，故而它會隨機從剩下八個位置中選擇一個落子。根據旋轉對稱等價的原則，事實上有5種情況（其中前兩種情況沒有與之對稱的，故而只有12.5%，後面三種情況都有對稱的情況，所以各算25%）：

<center>![png](http://cookdata.cn/media/topic_images/94_5.png)</center>

我們想說的是，第一種情況，即AI選擇了「走中間」的策略後，我們不能保證取勝。而在其他四種情況下，只要我們走法正確，我們一定能夠取得勝利。我們這裡只給出第二種情況下必勝走法的解答，其他三種情況留給讀者自行思考：

<center>![png](http://cookdata.cn/media/topic_images/94_6.png)</center>

如果我們「走角落」之後，AI選擇了「走中間」，我們是不是一定沒辦法獲勝呢？也不是的，我們可以選擇走到「對角」。這時候，類似於上面的分析，AI有$frac{1}{3}$的概率會選擇走角落，這時候我們就能獲勝。如下所示：

<center>![png](http://cookdata.cn/media/topic_images/94_7.png)</center>

這也就是說，在面對初始$s$，採取「走角落」的$a$之後，有$frac{7}{8}$的概率AI沒有選擇「走中間」。而這些情況下，只要我們後面走法正確，我們是必勝的。如果AI選擇了「走中間」，則我們如果走法正確，仍然有$frac{1}{3}$概率取勝。這意味著，第一步採取「走角落」的$a$，我們獲得的r的期望是$frac{7}{8} + frac{1}{8} frac{1}{3} = frac{11}{12}$。

經過對比，我們發現$frac{11}{12}$比$frac{5}{6}$要大，所以我們最佳的策略下，面對初始的$s$選擇的$a$應該是「走角落」！

###上面涉及到的思想

在上面，我們解決了一個簡單的MDP。現在，我們來看看它主要用到了哪些思想。

首先，我們會發現有一個概念在我們的求解過程中十分關鍵，那就是存在某些狀態$s$，這個狀態本身沒有分出勝負。但是隻要AI走到了這個狀態，如果我們下一步走的正確的話就一定能夠取得勝利。我們可以直接將這樣的局面$s$與r=1劃上等號，並且以這個為前提，再去分析怎樣才能最大可能地進入這些「必勝局面」——比如第一步「走角落」的話會有$frac{7}{8}$的概率進入「必勝局面」，所以我們有理由相信第一步「走角落」是好的。

要注意的是，這種「必勝局面」的前提是「如果我的走法正確」。如果AI走到了我們想要的「必勝局面」，而我們卻不知道應該怎麼走，那麼我們是不能保證自己能獲得勝利的。同樣道理，在我們上一節中講到了一些「一定會打平」的局面，如果我們在這種局面下的走法不正確，甚至是有可能會輸給AI的。所以，我們上面說的所有「必勝」或者「一定打平」都是建立在「我們的走法是正確」的基礎上的。

對於「必勝局面」，我們知道「如果走法正確」，就一定能夠獲得r=1。而對於「必平局面」，我們知道「如果走法正確」，一定會以r=0收場（我們作為先走的一方，如果「走法正確」是絕對不可能輸掉的）。我們可以想像，「必勝局面」對於我們的「價值」就是1，而「必平局面」對我們的「價值」就是0。對於二者之外的「中間局面」，例如最開始的局面，我們卻不能馬上看出會發生什麼。這時候，我們可以看看我們的走法將以多大概率將其導向「必勝局面」與「必平局面」，來分析出這些「中間局面」的價值。

例如「先走角落」的策略，會以$frac{7}{8}$概率進入「必勝局面」，$frac{1}{8}$的局面進入另外一個「中間局面」；而對於「先走中間」的策略，則會以$frac{1}{2}$進入「必勝局面」，以$frac{1}{2}$進入另外一個「中間局面」。這些「中間局面」的「價值」是多少，需要我們用上面同樣的手法作進一步的分析。

<center>![png](http://cookdata.cn/media/topic_images/94_8.png)</center>

分析得出，在後續採用「最佳走法」的情況下，「走中間」的期望收益是0.833，而「走角落」的期望收益是0.916，所以「走角落」的收益更大。這時，我們可以判斷出「第一步走角落」是最佳的策略。按照上面對於「價值」的定義，最初的局面（即場上一個棋子也沒有的初始狀態）的「價值」就是其採用「最佳策略」所帶來價值，也就是「走角落」對應的0.916，而不是「走中間」對應的0.833。我們可以得出如下的「最佳策略」與「價值」的表格（每一種局勢都有對應的「最佳策略」與「價值」，我們只列出一小部分）：

<center>![png](http://cookdata.cn/media/topic_images/94_9.png)</center>

上面說的這些正是動態規劃的基本思想——將大的問題拆分稱為比較小的問題，分別求解這些小問題，再用這些小問題的結果來解決大問題。能將小的問題與大的問題相連接在一起的，正是我們說的「價值」——我們這裡對這個「價值」做出定義：它是關於$s_t$的價值函數$V(s_t)$，代表「在最佳策略下」從t時刻的$s$出發之後，可以獲得的總期望價值$E(Sigma_{i = t} gamma^i r_i)$。當MDP為時齊的時候，一般不需要t作為角標，就好像在下棋時候，你光看棋局判斷哪方佔優，而不必知道現在是第幾回合。另外，要理解的是這裡說的「價值」和MDP本身定義的獎勵r是有區別的。你在$s$下能獲得$V(s)$的前提是你走出了「最佳策略」，否則就不能得到這麼多「價值」。

上面「井字過三關」只是一個特殊的例子，它比較簡單。有一些局勢$s$，我們一眼就能看出它是「必勝局面」，便可以直接把$V(s)$標記為1，並得到它的「最佳策略」。然後，我們又可以用這些標記了0或1的$V(s)$求別的$V(s)$。但是對於更複雜的MDP，例如中國象棋，我們就難以做到這一點。比如在某一個剛開局的$s$處，我們可以選擇立即喫掉對方一個子，獲得立即的r，也可以選擇放棄喫子而去搶佔一個位置，幫助我們在以後獲得更多r。這個$s$才剛剛開局，遠沒有能分出勝負，我們壓根看不出這一步的「最佳策略」到底是什麼，也自然求不出$V(s)$是什麼。這種情況又該怎麼辦呢？

說到底，矛盾的地方在於我們對價值函數$V(s)$的定義——它表示「在最佳策略下」獲得的價值。但我們一開始並沒有「最佳策略」（如果有了最佳策略，我們問題都解完了，何必要求V(s)呢？）。$s$是一個靜態的局面，它本身是沒有價值的。如果是一個不會下棋的人，再好的棋局$s$也能給下輸。$s$的價值$V(s)$大小是一種「策略」賦予的，而「策略」如何制定，又需要參考$V(s)$的大小。我們一開始既沒有$V(s)$，也沒有「最佳策略」，我們怎麼能夠「無中生有」地同時求出$V(s)$與「最佳策略」呢？

動態規劃演算法就是為瞭解決這樣的矛盾設計的，我們下面來介紹其框架：

###動態規劃演算法框架

我們考慮的仍然是$a$與$s$都有限的MDP。不妨設$s$有10種，$a$有3種。

首先我們定義「策略」，即policy，它一般用希臘字母$pi$表示，其含義是$s$與$a$的對應關係，什麼$s$應該採取什麼$a$。由於$s$與$a$都是有限的，所以我們可以用一個10×1的表格記錄policy，每一格記錄一種$s$對應的$a$。

然後我們再定義一個「策略價值函數」$V_{pi}(s)$。這裡的「價值函數」和上面說的有些不同，它指的不是$s$在「最佳策略」下的價值，而是在當前策略$pi$下能獲得的期望。這也就是說，我們從$s$出發，按照$pi$來選擇$a$，進入下一個$s$，然後又在下一個$s$用$pi$來選擇$a$，一直這樣玩下去，最終總的期望獎勵$Sigma_{i} gamma^i r_i$就是我們的$V_{pi}(s)$。顯然，任何一個策略$pi$都可以對應一個「策略價值函數」$V_{pi}(s)$，而不同的$pi$對應的$V_{pi}(s)$自然也是不一樣的。

當我們建立了這個10×1的「策略表」與10×1的「策略價值表」之後，就可以開始進行的迭代以求解「最佳策略」了。下面的演算法被稱為「策略迭代」，是動態規劃求解MDP中最經典的一種演算法，其步驟如下：

1、首先，初始化「策略表」$pi$。我們希望初始策略不要太差，不要和「最佳策略」偏離得太遠，這樣才便於迭代步驟之後能收斂到「最佳策略」，所以我們要爭取生成一個不算太差的初始策略。例如，在「井字過三關」的遊戲中，很多$s$下我們都夠一眼看出有必勝策略$a$，所以可以將這些$a$填在$s$對應的位置。這個步驟幫助我們大大減少了動態規劃的複雜度。但是對於複雜的MDP，我們可能只能隨機產生初始策略。

2、初始化「策略價值函數」$V_{pi}(s)$。同理，我們應該努力讓初始化的「策略價值函數」與真正「價值函數」（「最佳策略」下的「策略價值函數」）更加接近。例如在「井字過三關」中，我們把很多「必勝局面」的$V_{pi}(s)$直接就初始化為1了。但是如果沒有特定的專業知識，我們只能將其全部初始化為0。

3、在策略$pi$下求出「策略價值函數」$V_{pi}(s)$的值。按照定義，按照策略表$pi$上給的規則，以及已知的環境，模擬出從$s$出發按照$pi$操作會發生什麼，以算出$s$的價值。由於這個步驟是在給定策略下求「價值」，故將其稱作「策略評估」，即policy evaluation。

4、進行了「策略評估」後我們得到了$V_{pi}(s)$。但是，我們追求的是「最佳策略」，所以我們還要修改當前的策略。這個步驟被稱為「策略提升」，即policy improvement。如果說上面「策略評估」是用策略表$pi$來求出當前策略下的價值$V_{pi}(s)$，那麼「策略提升」則恰恰相反，是用當前的價值$V_{pi}(s)$來求最佳的策略$pi$。其過程是很樸素的：對於每一個狀態$s$，我們查看3個$a$（記為$a_1,a_2,a_3$）帶來的後果$Sigma_{s』} P_{s,s』}^{a_i} V_{pi}(s』) + r_s^{a_i}, i = 1,2,3 $選擇其中最好的$a_i$作為$s$對應的策略就行了。

動態規劃的主要過程就是先進行1、2，即對「策略表」$pi$與「價值函數」$V$進行初始化，然後迭代地重複3與4，即迭代地「策略分析」與「策略提升」，直到收斂，即「策略提升」步驟不對$pi$產生任何改動，即停止演算法。其偽代碼如下所示：

<center>![png](http://cookdata.cn/media/topic_images/94_10.png)</center>

###策略迭代與值迭代

在上面的演算法中，「策略評估」這個步驟是複雜的。在「井字過三關」的遊戲中，由於整一局遊戲的步數十分有限，所以我們事實上是先枚舉從$s$出發的所有情況，然後將其加和，繼而求出$s$的價值是多少。但是對於複雜一些的遊戲（哪怕$s$與$a$都很少，可是遊戲的回合數很長），想通過先枚舉後求和的方法以計算$V(s)$是極其複雜的。我們得另謀良方。

按照「策略價值函數」的定義，我們有得到如下公式：

<center>$$V_{pi}(s) = Sigma_{s』} P_{s,s』}^a V_{pi}(s』) + r_s^a$$ </center>

公式中，$a$是$s$處根據$pi$選擇出來的。上面我們曾提到過「中間狀態的價值可以用別的中間狀態計算出來」，這個公式所表達的正是這個意思。有了這個公式之後，我們就不必通過枚舉、加和的方式來「策略評估」。由於$P_{s,s』}^a$與$r_s^a$都是已知的，這就是一個10元的線性方程組。我們可以直接通過求解方程的方式來解決它。

對於10元的方程組，我們自然可以直接解出這個方程。直接求解一個線性方程組需要的計算量是$O(n^3)$（例如採用高斯消去法）。對於複雜一些的MDP，$s$的數量n可能會有很大，這會導致計算量很大。如果有學習過數值線性代數這門課程，就會瞭解解線性方程組有兩大類的方法，一類是直接解法，另一類是迭代解法（包括雅克比迭代與高斯賽德迭代）。我們考慮採用雅克比迭代法來解這個方程：

設方程為$x = Ax + b$，首先要隨機生成一個$x_0$，然後對於$i = 1,2,dots,n$，令$x_{i+1} = A x_i + b$，直到$x_i$與$x_{i+1}$之間的距離很小。其框圖如下：

<center>![png](http://cookdata.cn/media/topic_images/94_11.png)</center>

雅克比迭代法的收斂性與矩陣$I - A$的「嚴格對角優勢」有關。而我們這裡的A比較特殊，它的行之和為1（這是因為概率$P_{s,s』}^a$對$s』$求和顯然為1），滿足「嚴格對角優勢」的定義，所以採取雅克比迭代解方程是能夠收斂到方程的真解的，或者說，在迭代過程中$x_i$一定是距離方程的解越來越近的。

不難看出，雅克比迭代法的每一個迭代步要耗費$O(n^2)$的計算量。由於迭代具有距離真解越來越近的性質，所以我們可以選擇只用雅克比迭代法迭代$ k le n$步，求解出一個距離真解不太遠的解。這個過程只需要花費$O(n^2 k)$的計算量。這也就是說，我們在「策略評估」這一步花費了更少的計算量，求出了精確度更低的「策略價值函數」。

這種減少計算量的方法是否會給我們帶來幫助？答案是肯定的。因為我們歸根結底的目的不是求「價值」，而是「最佳策略」。在整個動態規劃演算法的框架中，「策略評估」求解出$V_{pi_i}(s)$其實只是為了「策略提升」來求解$pi_{i+1}$。當我們用$V_{pi_i}(s)$求出了$pi_{i+1}$之後，我們又要重新對$pi_{i+1}$進行「策略評估」，求出新的$V_{pi_{i+1}}(s)$。在「策略提升」中，我們要令$pi_{i+1}(s) = argmax_a Sigma_{s』} P_{s,s』}^a V_{pi_i}(s』) + r_s^a $。這個表達式中，如果$V_{pi_i}(s)$只有較小的誤差，很大程度上是不會影響求$argmax_a$的。所以說，「策略評估」中，「價值」不必要算得太精確，它只要能夠體現出大致哪個$s$比較好，讓我們能夠在「策略提升」中選對$a$就行了。

此外，雅克比迭代法每次要隨機生成一個初始解$x_0$，然後再通過慢慢地迭代讓它接近真解。隨機生成的初始解可能是距離真解很遠，所以要迭代很多步才能靠近真解。但是在這裡，我們可以不必每次都隨機猜出初始解，我們可以利用上一步「策略評估」的$V(s)$作為這一次「策略評估」的初始解。由於在迭代進行到後面，「策略提升」中發生改動可能不大，所以以$pi_i$「策略評估」得到的$V(s)$可能距離以$pi_{i+1}(s)$「策略評估」的$V(s)$的距離本身就不遠，迭代較少的步數也能取得不錯的精度。

以下是的方法就是建立在這個思想上，這個方法被稱作「策略迭代」（policy iteration）。它在上面講的一般的「動態規劃」框架上採用了雅克比迭代法來進行「策略評估」。由於上述的兩點原因，它比一般的「動態演算法」更加高效：

<center>![png](http://cookdata.cn/media/topic_images/94_12.png)</center>

我們可以想像一種比較極端的「策略迭代」，那就是每一次「策略評估」的時候僅僅迭代一步。這樣可能每一步求出的值函數都有一定誤差，但是由於每一步計算量更小，所以可以迭代更多步。並且，由於每一步都在復用前一步的$V(s)$，所以隨著迭代它的誤差會越來越小。總的來說，這也是一種性能不錯的演算法，我們將其稱為「值迭代」（value iteration）。

要注意的是，在「值迭代」演算法中，事實上是不用單獨列出「策略表」的。因為迭代進行到每一步，$s$對應的$a$都是能夠極大化$Sigma_{s』} P_{s,s』}^a V(s』) + r_s^a$的$a$，所以「策略表」其實已經隱藏在「價值表」中了，沒必要再單列出來。「值迭代」的演算法如下所示：我們可以想像在每一時刻，$V(s)$都有一個與之對應的「隱藏」的$pi$。當$V(s)$計算完成，我們也可以自動輸出這個$pi$

<center>![png](http://cookdata.cn/media/topic_images/94_13.png)</center>

在「策略迭代」與「值迭代」兩種演算法之間，還有一些折中的方案。我們可以想像，在演算法剛開始（循環計數$i$還比較小）的時候，「策略評估」需要迭代比較多的步數才能獲得誤差較小的「價值函數」，而在演算法進行了很多步之後，「策略評估」則只需要迭代較少的步數就能求出較精確的「價值函數」。所以我們也可以先將k設的比較大，然後再慢慢減小，直到減為1。這就相當於先進行「策略迭代」然後進行「值迭代」，綜合了兩種演算法的特點。

###演算法的收斂性

前面我們介紹了好幾種演算法，包括最一般的「動態規劃」的框架，以及「值迭代」與「策略迭代」兩種演算法。下面，我們考慮當演算法收斂的時候究竟意味著什麼。

在「動態規劃」的演算法中，各個量的定義是很清晰的。我們用當前的「策略」$pi$求出當前的「策略價值函數」$V_{pi}(s)$，而又用$V_{pi}(s)$提升當前的「策略」。「策略評估」與「策略提升」交替進行，並且它們的定義都很清晰；而在「策略迭代」或「值迭代」中，有些量的定義則不太清晰。因為我們不是用精確解法去「策略評估」的，所以任何一個時刻的$V(s)$都不是真的「價值」，而只是對當前「策略價值函數」的一個近似。另一方面，當前的策略又是在被不斷修改的，所以$V(s)$的確給人一種「不清晰」、「不可靠」的感覺。

我們希望演算法收斂時候達到什麼效果呢？我們自然希望此時策略$pi$正是「最佳策略」，而此時的「策略價值函數」$V_{pi}(s)$也正是「最佳策略」對應的價值，也就是這個狀態「真正的價值」。我們很容易想到，無論是採用「動態規劃」、「策略迭代」還是「值迭代」，如果當演算法運行到某一個時刻，$pi$恰好是「最佳策略」，而$V(s)$也恰好是「真正的價值」時，演算法一定會收斂。因為此時無論是「策略迭代」還是「策略提升」，都不再能改變$pi$與$V(s)$的取值。這也就是說，達到最優解是演算法收斂的充分條件。

但是反之，如果演算法收斂了，就一定是$pi$收斂到「最佳策略」而$V_{pi}(s)$收斂到「最佳策略」下的「價值」嗎？答案是否定的。我們可以想像一種情況，存在一些$pi$，是「不錯的策略」，但不是「最佳策略」，我們將其稱作「次優策略」。當某個時刻$pi$是一個「次優策略」，而$V_{pi}(s)$則是在這個「次優策略」下的各個$s$的價值。這時候，很可能在「策略提升」的步驟中我們沒有辦法改進:

例如在上面「井字過三關」的遊戲中，我們說過第一步「走角落」之後有五種情況，其中四種情況都是「必勝局面」。我們給出了其中一種的「必勝走法」，讓讀者思考其餘三種。如果有粗心的讀者A沒有發現這三種情況是「必勝局面」，認為它們都是「必平局面」，那麼就會判斷第一步「走角落」的價值只有$frac{1}{8} frac{1}{3} + frac{1}{8} = frac{1}{6}$，比起「走中間要低不少。所以，A就會認為第一步的最佳策略是「走中間」，並且認為初始局面的價值是0.833。這樣，A就會得出一個「次優策略」——第一步走中間，並且得出這個「次優策略」下所有$s$的「狀態價值函數」。這個「次優策略」與「狀態價值函數」之間自然是能夠「自圓其說」的，也就是說「策略評估」與「策略提升」都無法改變$pi$與$V(s)$，演算法已經收斂了。

<center>![png](http://cookdata.cn/media/topic_images/94_14.png)</center>

這種情況下，A就沉迷於這個「次優策略」中，每一局第一步都「走中間」，獲得83.3%的勝率。他深信最佳的策略就是「第一步走中間」，並且對83.3%的勝率沾沾自喜，從來就沒有想到過還有更好的方法。這種情況，我們就稱作「局部收斂」，即在沒有求出「最佳策略」的情況下演算法已經無法更新。

事實上，這裡涉及到「價值」的方法，無論是現在講的動態規劃，還是後面要講到的DQN，都難免會遇到「局部收斂」的情況。我們後面講到DQN的時候，會講一系列「off-policy」或是探索-利用（explore-exploit）取捨的trick。它們被設計出來的重要目的之一就是為了防止「局部收斂」的。在我們現在所講的動態規劃問題中，由於環境是已知的（即我們知道$r_s^a$），所以我們可以將估計出現偏差的$V(s)$用$r_s^a$給「扭轉」過來（根據棋局規則的定義很容易判斷出有些局面是「必勝局面」），所以是不容易「局部收斂」的；但是在沒有模型的問題中，尤其是那些r特別稀疏的MDP中，「局部收斂」的風險是很大的。因為當我們對於$V(s)$的估計出現了整體的偏差時，相對很難遇到r去「扭轉」我們判斷的偏差。所以在DQN中，採用「探索」的trick是很重要的。這一點我們後面會慢慢講。

總的來說，我們今天介紹了最簡單的MDP——$s$與$a$均有限，且環境已知的MDP的解法，並且引出了「價值」、「策略」等的定義與含義。在下一節中，我們將考慮$s$與$a$是連續變數的情況，並進一步加深大家對於「價值」與「策略」的理解，並引出最優控制與強化學習中很重要的Bellman方程。