coursera by University of Alberta
Sample-based Learning Methods
Week 1
1怖亭、Monte Carlo 蒙特卡洛方法
使用 Dynamic Programming 的局限性在于，很多時(shí)候并不知道轉(zhuǎn)移概率 trainsition probability 棍矛，比如 Policy Evaluation 中，不知道 p(s',r|s,a) 隐圾，因此提出 Monte Carlo 方法端礼。此方法通過對大量隨機(jī)樣本的均值來進(jìn)行估值括饶。
通過對同一個(gè) state 大量收集樣本，取其均值作為 V(s) 的估計(jì)值恕洲。
2塔橡、Using Monte Carlo for Action Values
對于每個(gè) state-action paire 也可以使用 Monte Carlo 方法來進(jìn)行估計(jì)
為了防止某個(gè) action 永遠(yuǎn)不會(huì)被選擇到以至于沒有對其 state-action paire 進(jìn)行探索，提出了 exploring starts
這個(gè)指的是在初始 state-action paire 進(jìn)行隨機(jī)選擇霜第，之后根據(jù) policy Π 進(jìn)行選擇 action
3葛家、Using Monte Carlo methods for generalized policy iteration
4、Epsilon-soft policies
ε-Greedy policy ∈ε-Soft policy
ε-Soft policy 在每個(gè) state 當(dāng)中泌类，對每個(gè) action 都有非 0 概率值進(jìn)行執(zhí)行
exploring starts 方法可以找到最優(yōu)策略癞谒，但是在很多問題上沒有辦法使用
ε-Soft policy 不一定能找到最優(yōu)策略
5、on-policy & off_policy
off-policy 指的是 target policy 和 behavior policy 不一致的情況
on-policy 實(shí)際上是 off-policy 的特殊情況刃榨，即 target policy=behavior policy
6弹砚、Importance Sampling
Importance Sampling 指的是通過對另一個(gè)分布的采樣來估計(jì)本分布的期望值
x：從分布 b 中取的樣本
Π：需要估計(jì)期望的分布
7、Off-Policy Monte Carlo Prediction
主要方法是通過 b 分布的采樣來估計(jì) Π 分布的值
其中喇澡， Returns 從 b 分布中獲得的采樣
P(trajectory under Π/b ) ：指的是在 Π/b 分布的情況下迅栅，路徑軌跡的概率
其中，W 就是 ρ
week 2
主要講了 TD learning 時(shí)差學(xué)習(xí)
1晴玖、Temporal Difference (TD) learning
TD 和 DP dynamic programming 區(qū)別是读存，DP 需要知道關(guān)于環(huán)境的轉(zhuǎn)移函數(shù)，即需要知道從當(dāng)前 state action 的情況下呕屎，轉(zhuǎn)移到下一個(gè) state reward 的概率让簿；而 TD 不需要知道， TD 可以直接根據(jù)與環(huán)境的交互來估計(jì)
2秀睛、 TD learning & prediction learning & supervised learning
prediction learning 是對每一步做預(yù)測的學(xué)習(xí)方法尔当， TD learning 是其中的一個(gè)特例；但它不是 supervised learning ， prediction learning 相當(dāng)于 unsupervised supervised learning
3椭迎、The advantages of temporal difference learning
TD DP MC 區(qū)別
① MC 只能在 episode 結(jié)束的時(shí)候?qū)?estimate of state 進(jìn)行更新锐帜，即只有在 episode 結(jié)束的時(shí)候才能學(xué)習(xí)； TD 可以在 episode 每一步進(jìn)行更新畜号，即 online learning 在線學(xué)習(xí)
② DP 需要環(huán)境模型缴阎，以便根據(jù)當(dāng)前 state action 來推出下一個(gè) state reward ； 而 TD 模型不需要简软，只需要和環(huán)境進(jìn)行交互
③ TD 比 MC 收斂更快 蛮拔， TD 可以在線學(xué)習(xí)
4、 α 對 TD 影響
α 越接近 0 收斂越快痹升，誤差越大
α 越接近 1 收斂越慢建炫，誤差越小
week 3
1、Sarsa: GPI with TD
GPI 由兩部分組成： policy evaluation & policy improvement
在 Sarsa 中疼蛾，由 TD 方法估計(jì) V(s) state 值轉(zhuǎn)為估計(jì) Q(s,a) state-action paire 值 肛跌； 因此，必須要執(zhí)行到下一個(gè) state-action paire 才能更新參數(shù)据过，即 St At Rt+1 St+1 At+1 才能估計(jì)值
與 TD 對比
TD
2惋砂、Q learning
Q learning 可以直接學(xué)習(xí)到 Q* ，而不用在 policy evaluation & policy improvement 之間轉(zhuǎn)換
Saras 實(shí)際上是 Bellman equation 基于采樣方法的實(shí)現(xiàn) 绳锅；Sarsa 和 Q learning 主要區(qū)別在于使用的方程不同
Q learning 是 off policy ： Target policy 是 optimal policy 西饵， behavior policy 是 ε-greedy policy
不理解
3、Expected Sarsa
可以認(rèn)為 Sarsa 通過大量樣本的學(xué)習(xí)鳞芙，使其值趨近于期望值眷柔，而 Expected Sarsa 直接根據(jù)期望公式得到其期望值
一般來說， Expected Sarsa 比 Sarsa 更穩(wěn)定原朝，方差更小驯嘱，但缺點(diǎn)是計(jì)算量更大，尤其在 action 很多的時(shí)候
Expected Sarsa 中喳坠， 當(dāng) Π 不必為 behavior policy 鞠评，這時(shí) Expected Sarsa 為 off policy learning
Expected Sarsa 中， 當(dāng) target policy Π 為 greedy 壕鹉，這時(shí) Expected Sarsa 為 Q learning剃幌，即 Q learning 為 Expected Sarsa 的一種特殊情況
4、 Sarsa & Q learning & Expected Sarsa
week 4
1晾浴、 Model
Model 指的是 agent 對環(huán)境的認(rèn)識
Planning 指的是 agent 根據(jù) Model 來改進(jìn)自己的 policy 负乡，一般 agent 可以通過使用 Model 來模擬經(jīng)驗(yàn)，然后根據(jù)經(jīng)驗(yàn)來更新 policy 脊凰，這種方法可以減少 agent 與環(huán)境的直接交互抖棘，提高與環(huán)境交互經(jīng)驗(yàn)的利用率
2、 Sample model & Distribution model
Sample model 直接通過采樣來獲得估計(jì)，比 Distribution model 更加壓縮
Distribution model 可以對所有可能出現(xiàn)的情況進(jìn)行枚舉切省，并且通過計(jì)算每種情況的概率都是準(zhǔn)確的最岗，不是采樣估計(jì)的，缺點(diǎn)是需要存儲的信息多
3数尿、 Planning
planning 通過對 model 的采樣仑性，模擬出 agent 和環(huán)境的交互，進(jìn)而更新 policy
Planning 的好處是在 agent 與環(huán)境的兩次交互之間可以進(jìn)行多次的更新右蹦，即在兩個(gè) step 之間進(jìn)行多次的 planning ，可以減少 agent 與環(huán)境交互的次數(shù)
4歼捐、 The Dyna Architecture
The Dyna Architecture 包含兩部分一是 agent 直接和環(huán)境進(jìn)行交互何陆，更新 policy ，二是在和環(huán)境的交互過程中學(xué)習(xí) model 豹储，使用 model experience 來更新 policy
在 Q learning 中贷盲，每個(gè) episode 只能更新一個(gè) state ，但是在 The Dyna Architecture 中剥扣，一個(gè) episode 可以更新 agent 在 episode 中走過的 state
5巩剖、The Dyna Algorithm
Dyna & Q-learning 比較， Dyna 比 Q-learning 對樣本的利用率要高得多钠怯，一般每個(gè) step 的 planning 越多對樣本的利用率越高
在 Tabular Dyna-Q 當(dāng)中佳魔， S ← random previously observed state 很多時(shí)候都是無效的，無法對 Q 進(jìn)行有效的更新晦炊，因此提出
P ： 優(yōu)先級排序的值
PQueue ： 優(yōu)先級隊(duì)列
基本思想 ： 當(dāng)前 S , A 由 Model(S,A) 得到 R , S' 更新 Q 值 鞠鲜；計(jì)算每個(gè)能夠到達(dá) S , A 的前一個(gè) ,
, 若其 P 值夠大，則將其加入隊(duì)列 PQueue
6断国、What if the model is inaccurate?
model 不準(zhǔn)確有兩種情況贤姆，一是 agent 沒有對所有的 state 進(jìn)行探索， model 不完整稳衬，二是 environment 發(fā)生變化而 agent 沒有探索到
為了解決隨著時(shí)間變化環(huán)境也隨之變化的情況霞捡，將原來的 reward 變?yōu)?New reward → Bonus ，當(dāng)某一 state 長時(shí)間沒有被訪問的時(shí)候 Bonus 就會(huì)增加薄疚，以防止某一 state 長時(shí)間沒有訪問的情況
