coursera by University of Alberta
Sample-based Learning Methods
Week 1
1、Monte Carlo 蒙特卡洛方法
使用 Dynamic Programming 的局限性在于，很多時候并不知道轉移概率 trainsition probability ，比如 Policy Evaluation 中，不知道 p(s',r|s,a) ，因此提出 Monte Carlo 方法。此方法通過對大量隨機樣本的均值來進行估值。
通過對同一個 state 大量收集樣本，取其均值作為 V(s) 的估計值。
2、Using Monte Carlo for Action Values
對于每個 state-action paire 也可以使用 Monte Carlo 方法來進行估計
為了防止某個 action 永遠不會被選擇到以至于沒有對其 state-action paire 進行探索，提出了 exploring starts
這個指的是在初始 state-action paire 進行隨機選擇，之后根據(jù) policy Π 進行選擇 action
3、Using Monte Carlo methods for generalized policy iteration
4、Epsilon-soft policies
ε-Greedy policy ∈ε-Soft policy
ε-Soft policy 在每個 state 當中，對每個 action 都有非 0 概率值進行執(zhí)行
exploring starts 方法可以找到最優(yōu)策略，但是在很多問題上沒有辦法使用
ε-Soft policy 不一定能找到最優(yōu)策略
5、on-policy & off_policy
off-policy 指的是 target policy 和 behavior policy 不一致的情況
on-policy 實際上是 off-policy 的特殊情況，即 target policy=behavior policy
6、Importance Sampling
Importance Sampling 指的是通過對另一個分布的采樣來估計本分布的期望值
x：從分布 b 中取的樣本
Π：需要估計期望的分布
7、Off-Policy Monte Carlo Prediction
主要方法是通過 b 分布的采樣來估計 Π 分布的值
其中， Returns 從 b 分布中獲得的采樣
P(trajectory under Π/b ) ：指的是在 Π/b 分布的情況下，路徑軌跡的概率
其中，W 就是 ρ
week 2
主要講了 TD learning 時差學習
1、Temporal Difference (TD) learning
TD 和 DP dynamic programming 區(qū)別是，DP 需要知道關于環(huán)境的轉移函數(shù)，即需要知道從當前 state action 的情況下，轉移到下一個 state reward 的概率；而 TD 不需要知道， TD 可以直接根據(jù)與環(huán)境的交互來估計
2、 TD learning & prediction learning & supervised learning
prediction learning 是對每一步做預測的學習方法， TD learning 是其中的一個特例；但它不是 supervised learning ， prediction learning 相當于 unsupervised supervised learning
3、The advantages of temporal difference learning
TD DP MC 區(qū)別
① MC 只能在 episode 結束的時候?qū)?estimate of state 進行更新，即只有在 episode 結束的時候才能學習； TD 可以在 episode 每一步進行更新，即 online learning 在線學習
② DP 需要環(huán)境模型，以便根據(jù)當前 state action 來推出下一個 state reward ； 而 TD 模型不需要，只需要和環(huán)境進行交互
③ TD 比 MC 收斂更快 ， TD 可以在線學習
4、 α 對 TD 影響
α 越接近 0 收斂越快，誤差越大
α 越接近 1 收斂越慢，誤差越小
week 3
1、Sarsa: GPI with TD
GPI 由兩部分組成： policy evaluation & policy improvement
在 Sarsa 中，由 TD 方法估計 V(s) state 值轉為估計 Q(s,a) state-action paire 值 ； 因此，必須要執(zhí)行到下一個 state-action paire 才能更新參數(shù)，即 St At Rt+1 St+1 At+1 才能估計值
與 TD 對比
TD
2、Q learning
Q learning 可以直接學習到 Q* ，而不用在 policy evaluation & policy improvement 之間轉換
Saras 實際上是 Bellman equation 基于采樣方法的實現(xiàn) ；Sarsa 和 Q learning 主要區(qū)別在于使用的方程不同
Q learning 是 off policy ： Target policy 是 optimal policy ， behavior policy 是 ε-greedy policy
不理解
3、Expected Sarsa
可以認為 Sarsa 通過大量樣本的學習，使其值趨近于期望值，而 Expected Sarsa 直接根據(jù)期望公式得到其期望值
一般來說， Expected Sarsa 比 Sarsa 更穩(wěn)定，方差更小，但缺點是計算量更大，尤其在 action 很多的時候
Expected Sarsa 中， 當 Π 不必為 behavior policy ，這時 Expected Sarsa 為 off policy learning
Expected Sarsa 中， 當 target policy Π 為 greedy ，這時 Expected Sarsa 為 Q learning，即 Q learning 為 Expected Sarsa 的一種特殊情況
4、 Sarsa & Q learning & Expected Sarsa
week 4
1、 Model
Model 指的是 agent 對環(huán)境的認識
Planning 指的是 agent 根據(jù) Model 來改進自己的 policy ，一般 agent 可以通過使用 Model 來模擬經(jīng)驗，然后根據(jù)經(jīng)驗來更新 policy ，這種方法可以減少 agent 與環(huán)境的直接交互，提高與環(huán)境交互經(jīng)驗的利用率
2、 Sample model & Distribution model
Sample model 直接通過采樣來獲得估計，比 Distribution model 更加壓縮
Distribution model 可以對所有可能出現(xiàn)的情況進行枚舉，并且通過計算每種情況的概率都是準確的，不是采樣估計的，缺點是需要存儲的信息多
3、 Planning
planning 通過對 model 的采樣，模擬出 agent 和環(huán)境的交互，進而更新 policy
Planning 的好處是在 agent 與環(huán)境的兩次交互之間可以進行多次的更新，即在兩個 step 之間進行多次的 planning ，可以減少 agent 與環(huán)境交互的次數(shù)
4、 The Dyna Architecture
The Dyna Architecture 包含兩部分一是 agent 直接和環(huán)境進行交互，更新 policy ，二是在和環(huán)境的交互過程中學習 model ，使用 model experience 來更新 policy
在 Q learning 中，每個 episode 只能更新一個 state ，但是在 The Dyna Architecture 中，一個 episode 可以更新 agent 在 episode 中走過的 state
5、The Dyna Algorithm
Dyna & Q-learning 比較， Dyna 比 Q-learning 對樣本的利用率要高得多，一般每個 step 的 planning 越多對樣本的利用率越高
在 Tabular Dyna-Q 當中， S ← random previously observed state 很多時候都是無效的，無法對 Q 進行有效的更新，因此提出
P ： 優(yōu)先級排序的值
PQueue ： 優(yōu)先級隊列
基本思想 ： 當前 S , A 由 Model(S,A) 得到 R , S' 更新 Q 值 ；計算每個能夠到達 S , A 的前一個 ,
, 若其 P 值夠大，則將其加入隊列 PQueue
6、What if the model is inaccurate?
model 不準確有兩種情況，一是 agent 沒有對所有的 state 進行探索， model 不完整，二是 environment 發(fā)生變化而 agent 沒有探索到
為了解決隨著時間變化環(huán)境也隨之變化的情況，將原來的 reward 變?yōu)?New reward → Bonus ，當某一 state 長時間沒有被訪問的時候 Bonus 就會增加，以防止某一 state 長時間沒有訪問的情況
