《Reinforcement Learning: An Introduction》 讀書筆記 - 目錄
先來看一個例子
每天上班的路程，都是可以看作是一系列子過程的組合，如：走路去地鐵站=>地鐵1=>地鐵2=>公交，總時長是這些子過程之和。每天我們依賴之前的經驗，估計當天的時長，并更新我們的經驗。
那麼如何做出更好的估計呢？如何更快地積累有效的經驗？
尤其是在一個沒有适合model（回顧MDP中的 p(s′,r|s,a) p ( s ′ , r | s , a ) ）的環境下
兩種思路
回顧第二章中的疊代式更新reward方法：
New=Old+StepSize⋅(Target−Old) N e w = O l d + S t e p S i z e ⋅ ( T a r g e t − O l d )
這裡并沒有對model做任何假設，并且可以以一種線上、增量的方式進行更新
進而我們可以有兩種方式：
-
const-α Monte Carlo
- stepsize設為一個固定的值 α α ，這樣新的經驗會占有更大的權重，能适應環境的變化
- target定義為 Gt G t ，也就是需要每一輪episode結束後才能進行更新
-
TD(0)
(one-step TD)
V(St)←V(St)+α[Rt+1+γV(St+1)−V(St)] V ( S t ) ← V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) − V ( S t ) ]
- stepsize同樣是一個固定的 α α
- target定義為 Rt+1+γV(St+1) R t + 1 + γ V ( S t + 1 ) ，和const-α MC的差別在于用 V(St+1) V ( S t + 1 ) 代替了實際的reward
- 但是這裡要注意的是， V(St+1) V ( S t + 1 ) 仍然是目前的估計值，并不是真實的value，類似第四章中動态規劃的做法，這種利用目前估計值進行更新的方法叫做
bootstrap
MonteCarlo
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning）
我們來比較一下兩種方法
- 相同點
- 兩者都是value function的無偏估計
- 每次更新都是基于樣本(
sample update
expected update
model-free
- 另一種表示方式， V(St)←(1−α)V(St)+α⋅target V ( S t ) ← ( 1 − α ) V ( S t ) + α ⋅ t a r g e t ，即兩者都可以認為是一種對老的估計和新的target之間的權重和(平均)， α α 為調節因子
- 不同
- TD(0) 可以在每一步都對value做更新，而不用等到episode結束
- 同時，在這種動态的環境下，一般TD(0)的收斂速度都會比const-α MC快
- 考慮下面這個問題，每組都是一個state,reward序列，如何評價狀态A,B的value？
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning） - 兩種思路
- 不考慮Markov轉移，直接用MonteCarlo上極大似然，則V(A)=0, V(B)=0.75
- 考慮問題的整體性，将A->B的轉移考慮進來 對這個新的模型假設，做一輪的新的MLE，假設 γ=1 γ = 1 ，可以得到V(A)=V(B)=0.75
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning）
- 對比一下這兩種思路，兩者在各自的模型假設下，都得到了各自的最小誤差（但兩者不一樣），但後者似乎更合理一些，且得到了更小的誤差
- 尤其是 如果後者的模型假設是對的話，則value function一定是對的，這個被稱為
certainty-equivalence estimate
- 兩種思路
對于開頭提到的那個例子，兩者的差別可以看到
Temporal Difference Prediction
- 上面的疊代式中 Target−Old T a r g e t − O l d 可以認為是一種目前估計的誤差，對應到TD(0)中，就是
-
TD-error
- td-error是對不同時間（temporal）的狀态的估計的差異（error, difference）
-
- 收斂性
-
對固定的policy π π ，TD(0) 能保證收斂到 vπ v π , 如果 α α 足夠小，或者滿足以下條件
∑∞n=1αt=∞ , ∑∞n=1α2t<∞ ∑ n = 1 ∞ α t = ∞ , ∑ n = 1 ∞ α t 2 < ∞
-
- 更新方法
- 上面提到的更新周期是每一個sample更新一次，相當于batch size=1，同理，我們也可以将batch size調大一些
TD Control
上面介紹了用TD method估計state value function，同理，action value function也是一樣，并由此進行control
更新的疊代式如下：
Q(St,At)←Q(St,At)+α[Rt+1+γX−Q(St,At)] Q ( S t , A t ) ← Q ( S t , A t ) + α [ R t + 1 + γ X − Q ( S t , A t ) ]
算法基本就像value iteration一樣
這裡的 X X 表示在TD中bootstrap方法使用的替代估計量，有幾種常見的方法：
-
Sarsa
- X=Q(St+1,At+1)X=Q(St+1,At+1)
- 在實際計算時，需要先向前模拟一步，産生一個 {St,At,Rt+1,St+1,At+1} { S t , A t , R t + 1 , S t + 1 , A t + 1 } 序列，故名SARSA
- 這裡，behavior序列（實際抽樣模拟的）和target序列（ X X 所代表的）都是目前的序列，是以是on-policy的
-
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning）
-
Q-Learning
- X=maxaQ(St+1,a)X=maxaQ(St+1,a)
- 這裡，target序列選擇的是根據Q選擇的最優action，但實際的behavior卻不變，是以是off-policy的
-
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning） -
Expected Sarsa
- X=E[Q(St+1,At+1)|St+1]=∑aπ(a|St+1)Q(St+1,a) X = E [ Q ( S t + 1 , A t + 1 ) | S t + 1 ] = ∑ a π ( a | S t + 1 ) Q ( S t + 1 , a )
- 如果 α=1 α = 1 ，那就是動态規劃中的方法
- 相比上面的兩種，是一種更折中，更穩健的方法
- 舉個例子，
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning） 《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning） - Sarsa在這裡效果更好，原因是q-learning過于激進，會很快選擇靠近懸崖邊的路徑，導緻經常掉下去，而sarsa會“乖一點”，expected sarsa通常會更優
-
Double Learning
- 在q-learning和sarsa中， 用到的target policy是 ε ε -greedy或貪婪的，這麼做容易過于樂觀，導緻
maximizaion bias
- 因為這個問題，是以一種簡單的做法就是維護另一個action-value 估計，兩者相關性小
- 每一次選擇behavior政策時，綜合考慮兩個估計
-
而更新的target，則使用另一個value function來估計，即
Q2(A∗)=Q2(argmaxaQ1(a)) Q 2 ( A ∗ ) = Q 2 ( a r g m a x a Q 1 ( a ) ) ，且 E[Q2(A∗)]=q(A∗) E [ Q 2 ( A ∗ ) ] = q ( A ∗ )
- 對于 Q1 Q 1 來說， X=Q2(St+1,argmaxaQ1(St+1,a)) X = Q 2 ( S t + 1 , a r g m a x a Q 1 ( S t + 1 , a ) )
- 以q-learning為例
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning） - 舉例
《Reinforcement Learning》 讀書筆記 6：時序差分學習（TD-Learning）
- 在q-learning和sarsa中， 用到的target policy是 ε ε -greedy或貪婪的，這麼做容易過于樂觀，導緻
- X=Q(St+1,At+1)X=Q(St+1,At+1)