前言
這是強化學習基礎的第二篇，在上一篇我們介紹了強化學習的大框架，馬爾科夫決策過程；以及兩組Bellman方程。一組是Bellman期望方程，它對任意的策略適用；另外一組是Bellman最優方程，這組方程只有在最優策略下成立。只要我們解出Bellman最優方程，就可以獲得RL問題的答案，然而我們Bellman最優方程很難解，因而我們有了這一篇的內容。我們嘗試用iteration的方法來解Bellman方程，主要參考資料：David Silver 的強化學習公開課。
#1。 動態規劃（Dynamic Programming）
什麼是動態規劃
Dynamic是處理序列或者帶有時間成分的問題
Programming一般是最佳化一個問題，比如線性規劃
動態規劃一般是用來處理複雜的問題
它透過將問題劃分成子問題，然後把子問題的解組合在一起。比如你想從A走到B，可以將問題劃分成從A到AB之間的中點C，以及C到B兩個子問題。
動態規劃的性質
最優子結構，問題的最優解可以被分解到子問題當中。
子問題重疊，子問題重複出現，子問題的解可以被儲存和重複利用。
馬爾科夫決定過程滿足上面兩個性質
Bellman方程可以被遞迴分解
值函式儲存和重複利用
動態規劃在MDP中應用
動態規劃要求我們知道MDP的全部知識，尤其是環境，也就是說知道轉移機率以及獎勵。
動態規劃是解決MDP中的planning（規劃）問題，因為有MDP的全部知識。
具體而言可以做
prediction
問題：給定MDP全部知識加上策略，求解策略的值函式；也可以做
control
問題：給定MDP全部知識，求解最優策略以及最優值函式。
#2。 Iterative Policy Evaluation
給定一個策略，我們如何獲得對應的值函式
，這裡給出的方法是不斷迭代Bellman期望方程：
第k+1步的值函式是由第k步相關的動作和狀態以及獎勵決定，也就是Bellman期望方程。
理論上，按這種方式計算，一定會收斂到 #FormatImgID_4#
。
舉例說明：
這裡一共由16個格子，灰色的格子是目標位置，遊戲的起始位置是剩餘14個格子中的任意位置，每次可以按照上下左右四個方向中的一個方向移動一格，遊戲的目標是用最短時間達到任意一個灰色的格子，每一步的reward都是-1。現在我們對一個隨機策略進行值函式計算，這個策略就是每次按照相同的機率選擇一個方向。
我們先看左邊一列，先忽略右邊的Greedy Policy。當k=0時，我們將所有的值函式都設成0；k=1時，每個位置的值函式根據Bellman方程更新 ：
以此類推，我們計算k=2，3。。。，直到值函式收斂注意到格子裡的數字省略了小數點後面的數字，比如k=2，-1。7實際上是-1。75。
現在我們看例子中右邊一列，它其實每次都是根據左邊的值函式來選擇動作，哪個方向的值函式最大就選擇哪個方向移動，我們把這種策略叫做Greedy Policy。可以看出來當k=3的時候，我們達到了最優的策略。
#3。 Policy Iteration
現在我們正式介紹最優策略的解法，Policy Iteration，它包含可重複的兩個步驟：
理論上可以證明，不斷重複上面的步驟，策略永遠會收斂到最優策略
。我們用圖示的方式，更好地展示Policy Iteration的過程：
現在我們從理論的角度，來給與Policy Iteration一定會收斂的最優值函式和策略的證明：
考慮一個策略，
，透過選擇讓當前狀態s下所有動作中
最大的那個動作作為新的策略
這裡的argmax的意思找到一個a，讓
最大。現在我們要證明新的策略
下的q值比之前的策略
下的q值更大：
第一個等於比較好理解，新的策略要求動作會挑選出之前策略的中最大的q值，因此也有了接下來的大於等於號。最後的等號，是因為值函式和動作值函式的關係式：
由於動作a是來自於 #FormatImgID_29# ，因此
。
接下來，我們需要證明
：
第一行的等式的意思，在
策略選擇動作的情況下用評估
，
其中 #FormatImgID_36# 是 由按照#FormatImgID_37# 選擇動作演化過去的，而 #FormatImgID_38# 仍然是 #FormatImgID_39# 下的值函式
。
透過不斷在時間步驟t上面迭代，最終完成新策略下的值函式會高於原來策略下的值函式的證明。
建議大家用上面的方格例子把證明過程帶進去推演一遍，增加理解
。
當新的策略不會帶來值函式的提高，這時候我們就滿足了Bellman方程：
此時，
，我們獲得了最優策略。
從上面方格的例子中，我們可以看出來k=3的時候，策略已經達到最優，這預示著我們是否可以在
的估計上在某個k步的時候截斷，而不是迭代到完全收斂。事實上當k=1的時候，Policy Iteration演算法等價於接下來要介紹的Value Iteration。
#4。 Value Iteration
最最佳化原則
：
一個最優的策略可以被分解成兩個部分：
一個當前情況（s）下的最優動作
在後續狀態（s‘）下沿著最優策略繼續進行
最優性定理
：
一個策略
在狀態s上取得最優值函式
，當且僅當：對於從狀態
可以到達的任何狀態
，
從狀態
中能夠獲得最優值函式，
。
Deterministic Value Iteration
假如我們直到一個子問題的解
，根據Bellman最優方程，我們可以計算得到：
不斷按照這個過程迭代，就可以把所有狀態都遍歷到。這個方法的直覺來源於，在終結狀態的前一個狀態的值函式可以優先確定，然後透過Bellman最優方程倒著推，可以把前面的狀態全部確定了。如果你看上一篇文章，你會發現學生MDP的例子用倒推的思路解Bellman最優方程並不可行。但是不用擔心，value iteration方法對於帶有迴圈和隨機的MDP仍然適用。
我們先舉個格子的例子，這個例子只有一個格子是目標位置，標記為灰色。
每移動一步會收穫reward=-1，目標是透過最小的路徑從格子上的任意一點走到灰色目標格子。用value iteration的方法，第一步所有狀態值函式都初始化為0，然後不斷使用Bellman最最佳化方程：
會得到第二步的狀態值函式。以此類推到第七步，我們已經迭代收斂。可以發現此時值函式就是最短路徑所以獎勵的總和。
#5 總結
我們將這節課學到的一種Prediction方法和兩種Control的方法資訊總結一下：
