強化學習傳說：第二章 動態規劃和時間差分
Hello，大家好，這裡是糖葫蘆喵喵~！
久しぶりです！
斯坦福強化學習CS234 winter 2018官網已經更新完畢啦，assignment中的大部分code作業並沒有變化，只是把assignment3換成了和CS294 HW2一模一樣的策略梯度（喂！），另外有一些證明推導題有所變化。
在此說明一下
，無論是winter 2018還是 spring 2017作業中的
證明部分喵喵就不再重複說了
，官方給出的solution已經很詳細啦（其實是公式太多，不好輸入><）。另外，就知道你們不想一上來就看到好幾頁的公式23333
本期內容：
動態規劃: 值迭代/策略迭代
；
TD: Q-learning/Sarsa（CS234 Assignment 1）
本期推薦大神文件：強化學習（一） - CSDN部落格
喵喵的程式碼實現：
那麼，繼續我們的強化學習旅程吧~！
Part 1 Value Iteration
(a)
問我們當第k次迭代得到的最優策略和第k+1次迭代得到的最優策略相同時是不是就意味著最優策略收斂了呢？顯然不是的，反例：
圖中狀態為{0， 1， 2}，初始值都是0，出邊代表動作，轉移機率為1，邊上的數字代表立即回報，
，假設折扣
，那麼我們可以手動計算一下Q值：
第一輪：既然值迭代源於貝爾曼最優方程，也就是找使回報最大的動作，顯然
狀態0
選擇到
狀態0
的動作獲得的回報
大於
狀態0
選擇到
狀態1
的動作獲得的回報1。而狀態1、2都只有一個動作可選。第一輪執行完後，狀態0的值是
，狀態1的值是1，狀態2的值是
。
第一輪最優策略：0->0， 1->2， 2->2
第二輪：繼續找使回報最大的動作，
狀態0
選擇到
狀態0
的動作獲得的回報
大於
狀態0
選擇到
狀態1
的動作獲得的回報
。而，狀態1只能選擇到狀態2，狀態1Q值為
，同理狀態2Q值為
。
第二輪最優策略：0->0， 1->2， 2->2。和第一輪一樣，但是策略並沒有收斂，我們再看一輪。
第三輪：
狀態0
選擇到
狀態0
的動作獲得的回報
小於
狀態0
選擇到
狀態1
的動作獲得的回報
，因此狀態0選擇到狀態1。而狀態1、2不變。
第三輪最優策略：0->1， 1->2， 2->2。
策略收斂
。故命題不正確。
Part 2 Grid Policies
Winter 2018 和 Spring 2017的這問區別僅在+5和-5的位置對換了，下面就簡單看一下Spring 2017的問題。
格子世界，綠色格子獲得+5並結束，紅色格子獲得-5並結束，
。粗線代表牆，向牆移動保持在原位置，轉移機率為1。候選立即回報r={-1， 0， 1}。
(a)
為了找到綠格子的最短路徑，立即回報r的值應該是多少？顯然是-1啦，是為了
懲罰
那些走得很多次才到綠色格子的路徑。
(b)
使用（a）中的r，求每個格子的的最優值。就是求
最短路徑
，逆推即可，從綠格子開始，周邊鄰接綠格子的格子選擇綠格子為下一個狀態（
最優策略即最短路徑
），其最優值為-1 + 1 * （5） = 4。 依次類推即可：
(c)
若
，最優策略是否改變？顯然對於這個最短路徑的問題，改變折扣隻影響每個格子的最優值，而不改變最優策略（最短路徑）。
(d)
若綠格子獎勵為20，最優策略改變嗎？同樣的，最優策略（最短路徑）不變，所有格子的最優值改變，每個格子+15就行了。
Part 3 Frozen Lake MDP
好了，前兩個部分熱身完畢！在這個部分裡，我們要利用
動態規劃
求解MDP，有以下兩個演算法：
策略迭代和值迭代演算法
。那麼讓我們愉快地開始碼程式碼吧！
OpenAI Gym
沒有裝好的看上一篇Part 0有介紹哦：強化學習傳說：CS294 Assignment 1。
首先就來回憶一下什麼是策略迭代和值迭代。回到最開始的這幅圖：
回顧我們的強化學習三步走流程：執行策略生成樣本===>利用樣本估計回報函式（對應具體任務）===>根據回報函式更新策略===>執行策略生成樣本。。。。迴圈往復。而動態規劃法透過
不斷迭代貝爾曼方程
可以完美的實現這個流程。
A 策略迭代
首先看
策略迭代，策略迭代
也是符合這樣的流程的：
1。
策略評估
，也就是根據
現有策略
對所有
狀態
進行評估（計算
V值函式
，即
回報期望
）
2。
策略改進
，根據V值函式尋找
最優動作
即使Q值函式最大的動作並更新（貪婪，
確定性策略
）
那麼問題就是，
狀態V值函式值函式
怎麼計算？來看由
累積回報的期望
推匯出來的貝爾曼方程：
![\begin{split}\upsilon_{k+1}(s) &={\bf{E}}_{\pi}\left[R_{t+1}+\gamma \upsilon_{k}(S_{t+1})\mid S_{t}=s \right] \\ &=\sum_{a}\pi(a\mid{s})\sum_{s^{](https://img.heatask.com/upload/website_attach/=kdwCEAgRkiPCPLhEwrzLWfVvZlYwUntEtSwA6EbnN9QNRCRK46q9l8y=GJw1OxslxjwgdGJNe2RCpUYtt3XMJvaKX1ggM1qS1IV2T6r7FjQwc7=C2Cw34-cC4M+gMn6swpdqF3KNe=Sz+MTur1xfGf-LaUygMM7N27eBDpwE-GN0Q1HC2EIGpf6L0SaqTdKSvHdqfVis7-_DfiRK46UmW-y=VlVD6JbMwhdqFf+Sao+lWJyLiMbAtm0C4McgM0dN27eB6SvOBIGz+MxDn1x+pf7MWEggMn6DwjzAEf+6+8tz+nSC25c49f6KGJ72+JZMYwxBKD+6AAZz+MTC25cmVJaR0ZogMn6ltj4gdGnDkGP1wJX611Ufa--===aqT1MN27+gdGnNeFPz+MTC2Edmpf66WEaqGJK6VHdxZm+6A8QpJxjttMbVXG7C41bELJbmnIorc6WMC0QE5dRK4N734mxl9J61USKSvwpgdpKNe=wz+0yC2Ed34mkC41+gMn6tXSbB6-+6+INBBxs=xQWr9fwLkiaqTdKSGYpgdpKNe=wz+0yC2Ed34mkC4nbCQQQ=kcdqffRNe2REoznC2EImaSXtDdaqTdJq.jpeg)
式子裡有個期望，想想看，期望是什麼意思？對於離散變數而言，期望不就是
機率
與
取值
的
乘積
嘛。在這個問題裡在這裡針對狀態s評估，不就是狀態s
根據現有策略選擇的動作a的分佈以及所能轉移到的新狀態的機率分佈
與
轉移到相應新狀態所產生的回報
（即立即回報+折扣*狀態回報）的
乘積
嗎？
式子中
維護的是策略（即狀態s下所能選擇的動作a分佈），對於隨機性策略，
就是各種動作的機率；
對於確定性策略（例如argmax(Q)這樣的貪婪）
就是唯一的確定性動作輸出。
來看程式碼更清晰：
for
prob
，
next_state
，
reward
，
terminal
in
P
［
s
］［
policy
［
s
］］：
val
+=
prob
*
（
reward
+
gamma
*
V
［
next_state
］）
P維護的是
某一狀態s
與
動作
a下的
轉移矩陣
。對於確定性狀態轉移，P［s］［policy［s］］將給出唯一的轉移狀態、回報以及是否結束，且轉移機率prob=1；對於隨機狀態轉移，P［s］［policy［s］］將給出多組資料，其轉移機率prob之和為1。
這兩行程式碼就是一次迭代中對某一狀態的策略評估。剩下的，我們只需計算所有狀態的值函式，並
不斷迭代，最終使得V值函式收斂即可
。
這樣V值函式就得到了。我們要更新策略，也就是要尋找更優的一些動作，顯然
評估哪個動作更優需要用到狀態-動作Q值函式
。下面需根據
收斂的V值函式
計算使
狀態動作Q值函式最大的動作
即可（貪婪策略）。新策略公式：
就是尋找狀態s下
最大的那個狀態-動作Q值函式值
，看程式碼更清晰：
for a in range（nA）：
for prob， next_state， reward， terminal in P［s］［a］：
val［a］ += prob * （reward + gamma * value_from_policy［next_state］）
policy［s］ = np。argmax（val）
透過argmax（V）找到了最優的動作（貪婪），然後更新策略，不斷迭代，使得最優策略收斂。
以上就是我們的策略迭代。
B 值迭代
回想一下，其實我們的
V值函式代表的是Q值函式的期望
，因此在一般策略下我們有
，但對於遵循最優策略的
最優V值函式
，根據貝爾曼
最優
方程有：
透過這個公式，我們事實上消掉了策略這一項，程式碼如下：
for a in range（nA）：
for prob， next_state， reward， terminal in P［s］［a］：
val［a］ += prob * （reward + gamma * V［next_state］）
V［s］ = np。max（val）
而且，因為我們用
來更新
，那麼最後直接
計算最優Q值函式就能得到最優策略
，而無需等待策略收斂，程式碼和策略更新部分一致，只不過這裡的
V是最優值函式
：
for a in range（nA）：
for prob， next_state， reward， terminal in P［s］［a］：
val［a］ += prob * （reward + gamma * V［next_state］）
best = np。argmax（val）
程式碼寫完啦！最後我們先來看看作業中的環境
Stochastic
-4x4-FrozenLake-v0：
“凜冬已至，你在玩飛盤的時候將其飛到了結冰的湖面上。湖上有數個冰洞，你需要避開冰洞找回飛盤。冰面很滑，使你並不能一定移動到你所希望的地方（也就是
隨機狀態轉移
）。”而在另一個模型
Deterministic
-4x4-FrozenLake-v0裡，模型是
確定性轉移
。分別執行兩個環境後，我們發現確定性環境達到目標的迭代次數要小於隨機性環境。
Part 4 Frozen Lake Reinforcement Learning (Spring 2017)
（winter 2018中把這個刪掉了，其實喵喵覺得這個部分挺好。）
上一個部分中我們使用了動態規劃求解了MDP，這個部分中我們首先回顧以下蒙特卡羅
MC方法
求解。
蒙特卡洛法
對比動態規劃
最大的特點是不需要知道完整的環境，它利用大量的經驗episode來估計值函式
。此外，
蒙特卡洛法需要bootstrapping一個完整的episode
（即到終止狀態為止）來估計值函式，而
動態規劃利用貝爾曼方程只bootstrapping了一次
。
那麼有沒有什麼方法能既
不需要知道完整環境
又只需要
bootstrapping一次
麼？
下面就請出我們的大名鼎鼎的時間差分
TD演算法
。
TD(0)
演算法本質是利用一次bootstrapping，使用滑動平均的方式更新V值函式：
![V(S_{t})=V(S_{t})+\alpha\left[R_{t+1}+\gamma V(S_{t+1})-V(S_{t}) \right]](https://img.heatask.com/upload/website_attach/_JS=ItuMMvGofv6vIv=GcsVL+7IBJ5hWRgA=f+4ByoUm+BtX7ZxDx=m0_KXvXw-BwBJAoZQgWlVvyN_+7ZTif_VrV2zQsUPhD=wlUDhNdJQ=6xdEesg5f_VpkMXnXw-PR2wTUVgyO6-mGYqDyb4Maf5G+AGdXwkvC69yg=9=KCn3GwZ4-jORyX5jrBWlz4eF2KK=oZogKC7q7iZ2TEkGblQorB_Pj.jpeg)
顯然如果我們bootstrapping到狀態終止時，TD演算法就等價於MC演算法了。
而介於其中的TD（
λ
）則是給每一步加上一個權重，這裡不再贅述。
回顧了這些知識，下面正式進入到Sarsa和Q-learning。
A Sarsa
Sarsa和動態規劃中對V值函式進行策略評估不同，它直接估計Q值函式：
![Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]](https://img.heatask.com/upload/website_attach/bJ=4Q5dVMv1ocoanILQp+5Tnf0GtbIykegL4_cbqyokmdGHl7R74Xvr+qRnD=Nc1KBStwV1GwBYvN0BR+AVywuDR6AVy1lCzR=F5Dsm8dJT=ICxHktmlhu++qRnCclC4S2FiDTB6Rn6=ahHunHCl2UzEeOV3=xDDmySXwVQGKCqGjgq8yGn0pV+H3QV3lGCzPA+UwV-ow716IC+9TxG0pVf7qRZEUA9lh.jpeg)
為什麼不直接估計V值函式呢？回顧動態規劃方法中策略更新部分，我們需要透過收斂的V值函式來計算Q值函式：
這個式子裡有模型環境P，我們在不知道模型的情況下，透過直接估計Q值函式來避免這個未知的引數。
另外，Sarsa是一種on-policy的方法，也就是說其改進的策略與生成episode的策略是一個策略（作業裡是epsilon-greedy），
一個episode流程
如下：
1.
對當前狀態s使用某策略生成動作a
2. 執行動作
a，轉移到下一狀態s_next
3.
對下一狀態s_next使用
同樣的策略
生成動作a_next
4.
更新Q值函式，令a=a_next，s=s_next，返回第二步（
體現同策略
）
直到episode終止
。
先看epsilon-greedy，就是以一定的機率選擇最優策略，其他情況隨機選擇，
有利於探索
：
if np。random。random（） < e：
a = np。random。randint（env。nA）
else：
a = np。argmax（Q［s］）
然後是Sarsa的流程框架：
for i in range（num_episodes）：
# reset env
# use epsilon-greedy policy create action a
while not done：
next_state， reward， done， _ = env。step（a） # execute action a
# use epsilon-greedy policy create action next_a
Q［s］［a］ += lr * （reward + gamma * Q［next_state］［next_a］ - Q［s］［a］） # update
s = next_state
a = next_a
對照上面的流程就很清晰明瞭啦。
下面我們看看另一個演算法：
B Q-learning
與Sarsa不同，Q-learning是一個off-policy的演算法，也就是其改進的策略與生成episode的策略
不是同一個策略（
作業裡是epsilon-greedy生成episode，貪婪策略更新
）。
Q-learning使用貪婪（直接最大化）的方式更新：
![Q(S_t,A_t)=Q(S_t,A_t)+\alpha[R_{t+1}+\gamma \mathop \max_{a} Q(S_{t+1},a)-Q(S_t,A_t)]](https://img.heatask.com/upload/website_attach/EyJY1YWiwGxg2jgeOb4xOZ=fG_B+kaluB9xYHEkd8e4T3ke3glRI=bVZsouK3lwVy74dvu96uvsZaWmyNmE05aqz3Zo994vrHfnZKbpfCZHcvoBquqXpLajZsoupV4vY0XnLK0tY1dPc0MeGh1Ee5ccH3zeeOq++ooXImF0PgsPVmnDb2mosjv_dqiAJ8YhVy75qO5ta29sZK_rKxvBn=u=MbWYPPqvrHzxy2rt9rvsy6Z7Jm.jpeg)
這裡的策略其實就是
argmax(Q)
，一個episode流程如下：
1.
對當前狀態s使用某策略生成動作a
2. 執行動作
a，轉移到下一狀態s_next
3.
對下一狀態s_next使用
貪婪策略
生成動作a_next（該步驟可以合併到Q值更新過程中）
4.
更新Q值函式，令s=s_next，返回
第一步（體現異策略）
直到episode終止。
與Sarsa相比可以發現，Q-learning在第三步中使用貪婪策略，在生成動作時使用epsilon-greedy。並且，注意Q-learning從第四步回到的是第一步，而Sarsa回到的是第二步。這正體現了Q-learning是異策略。
部分程式碼如下：
for i in range（num_episodes）：
# reset env
while not done：
# use epsilon-greedy policy create action a
next_state， reward， done， _ = env。step（a） # execute action a
Q［s］［a］ += lr * （reward + gamma * np。max（Q［next_state］） - Q［s］［a］） # update
s = next_state
作業的最後還有一個model-based的演算法：
C model-based Learning
其實這個model-based的演算法思路很簡單，一個episode流程如下：
1。 對當前狀態s使用epsilon-greedy生成動作a
2。
執行動作
a，轉移到下一狀態s_next，將本次執行加入history，返回第一步直到終止。
3。
根據history估算模型的轉移矩陣P和立即回報
reward
4。 使用動態規劃-值迭代獲得最優策略
對應程式碼：
for i in range（num_episodes）：
# reset env
while not done：
# use epsilon-greedy policy create action a
next_state， reward， done， _ = env。step（a） # execute action a
history。append（［s， a， reward， next_state， done］）
s = next_state
counts， rewards = update_mdp_model_with_history（counts， rewards， history）
P = counts_and_rewards_to_P（counts， rewards） # esimate P
V， policy = value_iteration（P， env。nS， env。nA）
其中update_mdp_model_with_history函式根據一條history使用平均的方式更新reward，同時更新計數器：
rewards［state］［action］［next_state］ = （rewards［state］［action］［next_state］ * counts［state］［action］［next_state］
+ reward） / （counts［state］［action］［next_state］ + 1）
counts［state］［action］［next_state］ += 1
更新後的計數器可直接用於估算環境轉移機率（其實就是算了s執行a轉移到s_next的次數佔s執行a次數的比例）：
prob = float（counts［state］［action］［next_state］） / float（sum（counts［state］［action］））
好辣，程式碼都寫完了，環境依然是Stochastic-4x4-FrozenLake-v0。這個任務在100次連續trials中達到平均0。78以上即可認為解決。
我們看三個演算法的結果（2000 train episodes）：
但是結果並不穩定哦，可以嘗試增大train episodes效果會好一些。
本期內容裡我們瞭解了
動態規劃
、
蒙特卡洛
以及
時間差分
方法，這三個方法在強化學習中的基礎性地位不言而喻。所涉及到的MDP理論、貝爾曼方程推導如果能夠理解的話是非常有好處的。尤其是
時間差分
的思想，後續的其他演算法中也有所體現。
では、おやすみ～！
下期預告：CS234 Assignment2\CS294 hw3 DQN詳解
