SARSA v.s. Q-learning
爬格子問題，是典型的經典強化學習問題。
動作是上下左右的走，每走一步就會有一個-1的獎賞。從初始狀态走到最終的狀态，要走最短的路才能使獎賞最大。圖中有一個懸崖，一旦走到懸崖獎賞會極小，而且還要再退回這個初始狀态。
如上圖所示，起始點為S, 終點為G ， 沒走一步獎勵為-1， 進入懸崖中獎勵為-100并且跳轉回起始點，本問題的最終目的是求解出最優路徑。
--------------------------------------------------------------------------
這裡采用 Sarsa 和 Q-learning 強化學習中兩種經典的TD值疊代法求解，先說下結論：
Q-learning 和 Sarsa 最終學到的政策都是随機政策（不是确定性的政策），但是我們可以把随機政策轉化為确定性政策，一般我們可以直接将随機政策中狀态S下動作值q(s,a)最大的動作作為确定性政策中的選擇動作，進而得到确定性政策。
最終轉化後的确定性政策中Sarsa算法更偏向選擇安全的路徑進而遠離懸崖，而Q-learning得到的确定性政策所得到的路徑更偏向緊沿着懸崖，是以q-learning算法所走路徑長度短于Sarsa (确定性政策下)，但是在實際的測試效果（此時都是使用未轉化為确定性政策前的随機政策）可以看到Sarsa方法可以取得比Q-Learing更好的效果，這聽起來很沖突，就像上面第二個圖中對兩種算法每回合的回報值的對比圖就可以看出 Sarsa算法強于Q-learning （Sarsa算法每回合的回報值高于Q-learning，也就是說Sarsa算法走的路徑要短于Q-learning）。
------------------------------------------------------------------------------------------
實驗中參數設定：
總實驗次數 1 次
學習率 0.1
每次實驗回合數500
折扣因子 0.95
探索率 epsilon 為 0.1
可以看到隻做一次實驗的話q-learning和Sarsa-learing 的波動很大，不同episode的回報值（這裡不考慮折扣率，但是在學習過程中考慮折扣率），
但是仍然可以看到q-learning每episode的回報值要低于Sarsa 的。由于一次實驗每回合的回報值波動過大，下面的實驗都是進行10000次取平均。
為了更近一步，做100次實驗，結果：
總實驗次數 100 次
學習率 0.1
每次實驗回合數500
折扣因子 0.95
探索率 epsilon 為 0.1
首先要解釋一點，上圖中的每回合回報值是平均值，也就是說那個 reward per episode 是多次實驗的平均值，如進行10000次重複實驗，每次實驗都進行500個episode的訓練。
其次要解釋的是，Q-learning可以學習到比Sarsa更好的确定性政策，但是如果直接使用學習到的随機政策的話 Q-learning實際尋找的路徑要差于Sarsa, 這是因為Q-learning和Sarsa的動作選擇政策或者說最終學習到的随機政策是epsilon-greedy政策而不是确定性的greedy政策，是以最終政策是以機率形式随機選擇一個動作而不是根據确定值選擇固定動作，這樣每次選擇動作的時候也帶着試探，是以Sarsa的最終随機政策因為要更加繞遠卻更加安全不容易掉入到懸崖中，而Q-learning學習到的随機政策是更偏向于緊貼懸崖的，而最終政策由于是随機政策，也就是說會一直保持一定的探索的，是以Q-learning更容易掉入到懸崖中進而有差于Sarsa算法的表現。
------------------------------------------------------------------------------
注：
終止點的q值是不參與訓練的，而且預設為0，也就是說終止點為S' , 前一狀态為S 的話，
q-learning: q(s, a)=q(s, a) + step_size*( r + γ . max{a} q(s' , a' ) - q(s, a) )
sarsa: q(s, a)=q(s, a) + step_size*( r + γ . epsilon-greedy q(s' , a' ) - q(s, a) )
可以看成：
q-learning: q(s, a)=q(s, a) + step_size*( r - q(s, a) )
sarsa: q(s, a)=q(s, a) + step_size*( r - q(s, a) )
因為狀态s選擇動作a後進入終點，是以也可以把 q(s, a) 直接看為 獲得的即時獎勵 r, 即 -1 。
----------------------------------------------------------------
總實驗次數 10000 次
學習率 0.1
每次實驗回合數 500
折扣因子 0.95
探索率 epsilon 為 0.1
q-learning 學習：
10000次實驗q-learning，每次實驗500回合，将最終學習到的epsilon-greedy政策轉為greedy政策，10000次實驗中全部實驗的最終獎勵為-13（這裡不考慮折扣率），也就是說10000次實驗每個實驗500回合訓練後轉換的greedy政策都是緊沿着懸崖走的。
Sarsa 學習：
10000次實驗sara學習，每次實驗500回合，将最終學習到的epsilon-greedy政策轉為greedy政策，10000次實驗中8622次實驗可以找到終點大部分其中大部分的獎勵為-15，還有一部分為-17，并且均值為-15.45， 也就是說10000次實驗每個實驗500回合訓練後轉換的greedy政策都是要繞開懸崖一些走的。
可以看到sara的10000次實驗中獎勵為-15的實驗6679個，獎勵-17的實驗為1925個。
同時還需要注意，有1378個實驗不能找到終點（代碼中設定的，如果進入死循環那麼自動結束尋找終點，這裡設定走10000步沒有找到終點判斷為進入死循環）
還有一個有意思的地方是：
說明沒有找到終點的1378次sara實驗獲得的獎勵均為-10000，也就是這10000步的尋找路徑過程中并沒有進入懸崖，而是在普通的節點之間循環的跳轉。
同樣實驗環境再重新做10000次實驗：
q-learning:
10000次實驗，轉換後的确定性政策全部以最短路徑到終點，獎勵值均為 -13 。
sarsa:
sarsa實驗10000次 8685次找到終點，其中獎勵回報-15的有6809，回報-17的有1855 。
sarsa實驗10000次 1315 次沒有找到終點，其中獎勵回報均為 -10000， 即在普通點上進入死循環的尋路過程，未有一次實驗進入到懸崖中的 。
----------------------------
同樣實驗環境第三次重新做10000次實驗：
可以看到，上面同樣的實驗環境做三組10000次實驗發現，q_learning訓練後的确定性政策10000次實驗全部找到最優路徑（回報值-13），sarsa訓練後的确定性政策大部分可以找到終點，其中基本都是次優解（獎勵都是-15， -17， -19），說明q-learning 學習到的确定性政策是沿着懸崖的，sarsa學習到的确定性政策是偏離懸崖的。
同樣實驗環境做第第四組實驗：
發現這回 sarsa最終獲得的确定性政策回報值除了 -15， -17， -19 以外還有了 -21 。
如下：
分别列印出幾類路徑的具體曆史狀态的通路記錄（每個類别舉出幾個例子）：
-15：
-17：
-19：
-21：
---------------------------------------------------------------
總實驗次數 10000 次
學習率 0.1
每次實驗回合數 1000
折扣因子 0.95
探索率 epsilon 為 0.1
q-learning 學習：
Sarsa 學習到的狀态值：
----------------------------------------------------------------
總實驗次數 10000 次
學習率 0.1
每次實驗回合數 500
折扣因子 1.0
探索率 epsilon 為 0.1
q-learning 學習到的狀态值：
q_learning學習，10000次實驗得到的确定性政策都能走到終點并得到最短路徑，回報均為 -13 。
Sarsa 學習到的狀态值：
sarsa學習 10000次實驗得到的确定性政策有1058次沒有走到終點，進入普通點之間跳轉的死循環，回報均為 -10000。走到最終點的實驗中：
可以看到Sarsa 走到最終點的實驗中回報值有 -15， -17， -19 三種， 其中以 -15 回報獎勵為主。
----------------------------------------------------------------
總實驗次數 10000 次
學習率 0.1
每次實驗回合數 1000
折扣因子 1.0
探索率 epsilon 為 0.1
q-learning 學習到的狀态值：
Sarsa 學習到的狀态值：
---------------------------------------
針對以上内容說下個人觀點：
Q-learning在訓練學習時對評估動作采用greedy政策，在對評估東西進行評估時（對原狀态s動作a後跳轉到的狀态s' 根據greedy政策選擇要評估的 q(s' , a' ) ）, 即使下一狀态S' 有可能因為某動作進入到一個十分糟糕的環境也步過多考慮，隻要S' 狀态有某個動作可以跳轉到更好的狀态即可， 是以Q-learning 更偏向于确定性政策下的最優政策，而忽略該政策可能潛在的風險，比如與極差的政策相近，隻要與較好政策相近即可。
Sarsa在訓練學習時對評估動作采用epsilon-greedy政策（更多的考慮不同動作後跳轉到不同狀态所造成的影響），是以探索性較強，相比于Q-learning更多的考慮懸崖狀态的影響，是以更偏向于遠離懸崖。
是以，以epsilon-greedy政策執行的時候 Q-learning即使更偏向于走最優的路徑但是由于與極差的政策（或路徑）相近仍然會以一定機率進入到極差路徑中，是以平均下來Q-learning的表現不如Sarsa， 而Sarsa更多的考慮下一狀态可能進入的各種環境（造成極好路徑和極壞路徑的狀态），是以更偏向于繞遠但是更安全的路徑，由于進入到極差路徑的可能性也随之降低是以平均起來要比Q-learning表現好。但是，将訓練獲得的epsilon-greedy政策轉換為greedy政策，算法在執行時不進行探索，這時Q-learning選擇走最優路徑，即使這樣也更靠近極壞的路徑中，但是因為不進行探索是以最終不會進入極差的路徑中，是以表現好于Sarsa， 而Sarsa由于更偏向于繞遠但是更安全的路徑，這時由于Q-learning不會進入極差路徑中（進入懸崖狀态），是以表現不如Q-learning 。
以上是個人了解，是否正确不敢保證。
=========================================================
如果這個問題中沒有懸崖的話，那麼運作結果如何呢？
環境為無懸崖的情況：
參數：
總實驗次數 10000 次
學習率 0.1
每次實驗回合數 500
折扣因子 0.95
探索率 epsilon 為 0.1
這時候發現如果沒有懸崖的話 q-learning 和 sarsa 在訓練期間運作的效果大緻相同，基本上是重合的兩個曲線。
不過這時候将500episode訓練好的epsilon-greedy政策轉換為greedy政策後：
q-learning 10000次實驗全部以最短路徑走到終點。
sarsa:
可以看到sarsa算法 10000次實驗後9453次實驗可以找到最終點，其中獎勵值為 -19， -17， -15， -13， -11 五種類型， 其中以最短路徑 回報值 -11 為主。
sarsa算法10000次實驗中547次實驗無法找到終點，而且全部進入各狀态跳轉的死循環。
--------------------------------------------------------------------------------
環境為無懸崖的情況：
參數：
總實驗次數 10000 次
學習率 0.1
每次實驗回合數 1000
折扣因子 0.95
探索率 epsilon 為 0.1
sarsa 算法有9834次實驗greedy政策走到終點，分布：
------------------------------
環境為無懸崖的情況：
參數：
再次做一組相同設定：
總實驗次數 10000 次
學習率 0.1
每次實驗回合數 1000
折扣因子 0.95
探索率 epsilon 為 0.1
可以看到大緻運作的效果是差不多的， 不過這次加入了每episode回合下動作值q的變化，并取10000次實驗的平均值：
可以看到每一個動作q值随之episode的增加逐漸趨于穩定，逼近0 。（這裡的每episode的q的變化是取了10000次實驗的平均值）
----------------------------------------
同樣的設定，這時實驗分别設定為10次，100次， 1000次，并對結果取平均，如下：
10次：
100次：
1000次：
------------------------------
環境為有懸崖的情況：
參數：
學習率 0.1
每次實驗回合數 1000
折扣因子 0.95
探索率 epsilon 為 0.1
實驗1次：
實驗10次：
實驗100次：
實驗1000次：
實驗10000次：
可以看到Q值的大學随着訓練逐漸保持不變，基本上可以當做是收斂的，也就是說政策是收斂的。
（上圖是不同episode時後一episode下所有Q值與前一episode下所有對應的Q值差的絕對值的和）
--------------------------------------------------
============================================================
更正一下，由于代碼編寫錯誤，以上的10000次實驗每個episode之間q值的內插補點變化并不是10000次的平均，而是一次的，下面給出更正的10000次實驗下episode之間q值變化的曲線（所有q值變化的絕對值之和）：
環境為有懸崖的情況：
參數：
學習率 0.1
每次實驗回合數 1000
折扣因子 0.95
探索率 epsilon 為 0.1
總實驗次數為10000
不同episode之間q值的變化（不同episode下所有q的絕對值之和然後求前後episode的內插補點）：
同時給出，所有q的絕對值之和的變化：（episode之間不求差）
可以看到q的絕對值的和還是在緩慢變化的。
是以又做了下面實驗：
環境為有懸崖的情況：
參數：
學習率 0.1
每次實驗回合數 5000
折扣因子 0.95
探索率 epsilon 為 0.1
總實驗次數為1000
所有q的絕對值之和的變化：（episode之間不求差）
每一episode的獎勵平均值：
-------------------------------------
環境為有懸崖的情況：
參數：
學習率 0.1
每次實驗回合數 10000
折扣因子 0.95
探索率 epsilon 為 0.1
總實驗次數為1000
所有q的絕對值之和的變化：（episode之間不求差）
每一episode的獎勵平均值：
-------------------------------------
環境為有懸崖的情況：
參數：
學習率 0.1
每次實驗回合數 50000
折扣因子 0.95
探索率 epsilon 為 0.1
總實驗次數為100
所有q的絕對值之和的變化：（episode之間不求差）
每一episode的獎勵平均值：
可以看到使用表格法的話隻要訓練時間足夠長最終轉化為的确定性政策都是可以走到最終點的。
=============================================================
環境為有懸崖的情況：
參數：
學習率 0.1
每次實驗回合數 1000
折扣因子 0.95
探索率 epsilon 為 前500個episode固定為0.1，從500到1000episode組建降低為0
總實驗次數為10000
所有q的絕對值之和的變化：（episode之間不求差）
每一episode的獎勵平均值：
=========================
-----------------------------------------------------------
可以看到500episode之後随着探索率的下降 每episode所得到的回報逐漸保持不變,并且q-learning獲得的回報迅速超過sarsa，因為此時q-learning降低了探索，減少了進入懸崖的可能并緊沿着懸崖的路徑走，同時也可以看到q-learning和sarsa算法在500episode之後所學習到的q值逐漸保持不變，加快了算法的收斂（如果不降低探索率的話q-learning在50000episode之後仍在有小幅度的變化）
個人感覺： q-learning 對政策的探索力度更大，是以也容易使政策更不穩定，但同時對最優政策探索力度也更大。從本文的實驗結果上看，感覺q-learning 的收斂性不如sarsa，因為在各個episode上q-learning獲得的回報變動更大，而sarsa獲得的回報值變動很小，但是随着訓練的episode的增加逐漸減少探索率epsilon那麼q-learning和sarsa都可以得到很好的收斂，當然評價q-learning和sarsa收斂快慢不能用這一個簡單實驗來下結論，有懸崖的情況下q-learning的學習過程更不穩定收斂可能稍差些但是在無懸崖的時候sarsa和q-learning的效果相當，而且在強化學習中收斂速度不應該太看重而是更應該關注能否收斂的問題。
-------------------------------------------------