[徵文] DQN與其後續的改進

看板DataScience作者thefattiger (LT)時間6年前 (2018/08/24 22:29)推噓7(7推 0噓 4→)

留言11則, 9人參與討論串1/1

小弟剛換新工作兩個禮拜，需要應用一些RL(Reinforcement Learning)的知識以前對這領域沒什麼接觸，背景知識就只有最近看的幾堂David Silver 所以有些概念講得不清楚或不對還請各位前輩指正這篇文章算是小弟研究DQN(Deep Q Learning)的一個小筆記 DQN被提出來也已經五年了，除了原始論文外，後續改進的paper也很多不太可能在一篇文章內全部概括完這篇文章是根據這個網站 https://goo.gl/nXArSB 所提到的幾個概念，小弟去閱讀原始論文後做個簡單地介紹希望能幫助到跟我一樣剛入門的新手那麼就開始了 I.Playing Atari with Deep Reinforcement Learning 網址：https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf 這篇是提出DQN的paper，作者們就是大名鼎鼎的DeepMind 這篇paper的出版年份是2013年，也就是DL(Deep Learning)正開始火熱的時候當時DL已經在電腦視覺已經語音辨識方面非常成功主要就是歸功於CNN(Convolutional Neural Network)及RNN(Recurent Neural Network) 等概念以及硬體的進步(當然還有ReLu) 然後DL目前在SL(Supervised Learning)方面的成功也倚賴於大量經過人工標註的資料，這個在RL中是沒有的並且RL所要預測的reward，常常是非常的稀疏、充滿雜訊且延遲的筆者註：這邊可以用走迷宮想像，若走到出口才會得到reward其餘都是0，則剛開始訓練時會有大量沒有reawrd=0的state-action pair 另外在DL中訓練的資料常常都被假設為是獨立取樣的，並且符合某個固定的distribution （也就是常說的i.i.d.) 然而在RL時訓練資料(state, action, reward)往往都是有因果關係並且訓練的過程中會因為決策(policy)的改變而使得資料的distribution也跟著改變，既不i也不d！這些都會對訓練造成影響還有一點與SL不同的是DQN跟傳統的Q-Learning一樣，是用TD(0)的方法來更新Q值 (target Q=R+gamma*max_over_a(Q(s_next,a|w_i-1)) ) 也就是說target本身也跟網路的係數有關，這會大幅地增加收斂難度訓練時的損失函數則是採用mean squared error paper中的DQN是被訓練來玩Atari 2600(一款遊戲主機）的各種遊戲，輸入為遊戲的原始影像影像只經過灰階化及resize，沒有任何手動提取的特徵值得一提的是大部分的電動遊戲是沒辦法只靠單張影像就得知所有資訊的例如有時候我們需要知道角色或物體的速度才能判斷接下來怎麼操作所以paper中的輸入是將最近的四個frame預處理過後疊在一起（paper中似乎有將action也加入state，但我沒看到他怎麼使用action的） DQN的訓練中應用了一個方法叫experience replay，跟傳統的Q-Learning不同在DQN中每做一個action、經過一個state及得到的reward，都會儲存到replay memory裡在更新係數時並不是用最新的state及action來更新，而是從replay memory內隨機取樣一小群樣本當作mini-batch replay memory的大小N，是hyper parameter 使用experience replay有兩個優點 1.隨機取樣可以打破資料間的關聯性 2.每筆資料有可能被多次使用，提升資料的利用率 paper最後有把DQN跟人類以及其他演算法做比較 DQN的不管是平均或是最佳分數都是贏過其他演算法很多且這些演算法都是有用到遊戲相關的知識，DQN是直接使用raw pixel 簡言之就是很好很強大至於跟人類玩家比較則是有輸有贏，幾款輸給人類很多的遊戲是需要long-term strategy II.Human-Level Control Through Deep Reinforcement Learning 網址：https://storage.googleapis.com/deepmind-media/dqn/DQNNaturePaper.pdf 以往在使用non-linear function approximator(例如神經網路)代表Q值時往往會預到訓練過程不穩定甚至發散的情況原本計算TD error時的target Q是直接用現有的網路，所以會每一次更新也都會跟著改變可以想像成你往目標方向跨了一步，目標卻也又走了一步這篇的解決方法是把計算target Q值的網路(稱為target network)固定C個iteration後，再換成最新的係數 C是hyper parameter 這個方法在實作上相當簡單，但大大地提昇了訓練的穩定性跟收斂速度 III.Deep Reinforcement Learning with Double Q-LearningQ Learning 網址：https://arxiv.org/pdf/1509.06461.pdf 在估計target Q值時，常因為在action space做maximize而造成Q值的高估而1993年有篇paper有論述這個現象確實會對最後policy有負面的影響 2010年時有另一篇paper提出dounle Q learing，使用兩個Q table輪流更新彼此解耦action selection及target value estimation來改善最後的結果（筆者註：為何解耦能改善Q的高估？我也不知道） Double DQN的精神即與此相似，而且做起來更方便，因為我們本來就有第二個 network:target network 實作上就是在用target network估計Q值的action使用基於current network的greedy policy 如此又進一步加強了DQN IV.Prioritized Experience Replay 使用experience replay時原本都是用uniform sampling，意即每個樣本被採樣到的機率都一樣但事實上並非每個樣本的重要性都一樣尤其是在sparse reward的task replay memory裡可能有大量的樣本reward都為0好不容易有非0的樣本卻又不一定被採樣到我們知道那些TD-error較大的樣本代表網路的預測與估計值相差甚遠可以給係數有較大的改進因此第一直覺就是：若將樣本依照TD error決定prioritization，由大排到小每次只固定取前幾大的那些樣本來更新這樣是否更好呢？答案是否定的主要原因是每個樣本的TD-error是以上次被採樣到時的網路去計算的隨著網路的更新原先TD-error值也已經不準了若一直沒有機會被採樣到的話，也無法更新它的TD-error 這個樣本就永遠沒機會被使用了因此我們還是要採用機率的方式，讓TD-error高的樣本只是具有較高的機率被取樣作者提出了兩個決定prioritization(p_i)的方式第一種是proportional prioritization，讓p_i直接等於TD-error 第二種是rank-based prioritization，p_i=1/rank(i) rank(i)是第i個樣本的error在所有樣本中的排名這邊引入了一個hyper parmeter:alpha來控制這個機率分佈但因為用這個機率去採樣樣本的話會使樣本偏離真正的data distribution 所以需要使用IS(Importance Sampling)來消除這個bias 這邊引入了第二個hyper parameter:beta，來控制IS（beta跟learning rate一樣訓練中會變化的） beta=1時就是常規的IS，等於是回到uniform sampling 在訓練前期由於policy的變化迅速，資料的distribution也會劇烈變化此時unbiased sampling並沒那麼重要，可以讓beta較低在訓練快結束時再慢慢增加beta到1，以確保採樣的樣本有符合真正的distribution 使用IS也有另一個好處是TD-error與IS的權重成反比剛好可以平衡各個樣本的step size 原本error大的樣本step size也會較大，使gradient desecent的更新不準確 paper另外有解釋實作上怎麼採樣才能節省時間跟空間，細節就要請各位去看paper了網路上也有很多的程式碼可以參考(其實我也還沒完全搞懂XD) V.Dueling Network Architectures for Deep Reinforcement Learning 網址：https://arxiv.org/pdf/1511.06581.pdf 這篇的概念是我個人覺得最有趣的，也是本文章中唯一不是由DeepMind發表的paper 作者們在原先DQN的CNN後用兩個獨立的FCN把輸出分成兩個部分一個部分是預測目前state本身的value：V(s) 另一個部分預測在當前state上採取不同action所造成的影響：A(s,a) （筆者註：可以想像這個做法是把共同的部分V(s)提取出來後讓你有機會把各個action的差異分得更明顯）最後再通過一個aggregate layer把他們整合起來在整合時若直接讓Q(s,a)=V(s)+A(s,a)，會發現當給定一個Q值時，V與A有無限種可能的組合，無法將他們識別出來的實際上採用這個equation的時候也會發現效果很差，需要重新思考一下回到Q與V的定義，可以推出如果採用greedy-policy，當我們在state s選擇到action a* 時，A(s,a*)=0 因此我們可以強迫A(s,a*)=0，實際上的作法就是讓新的 A'(s,a)=A(s,a)-max_over_a[A(s,a)] 這樣V(s)就符合一般RL領域state-value function的意義了但最後他們選擇讓A'是減去所有A的平均，應該實驗過這樣收斂比較好下一個部分他們用走迷宮做了一個小實驗，這個迷宮只有一條路，action則有上、下、左、右、不動在這個環境顯然有很多action是沒有差別的（會撞牆的跟不動），這時能獨立學習共同的 value：V(s)就很有用作者們把透過增加，不動來比較有duel network跟沒有的差別，可以發現行為類似的 action越多，優勢越大最後就是一樣訓練DQN去玩Atari 2600來跟之前的結果做比較，這邊就不再詳述了 VI.結論其實這幾篇paper用到的概念都不是新東西了，只是以前沒有人能夠將它們很好地整合進 DRL(Deep Reinforcement Learning) 第一篇DQN的起始paper是用experience replay，解決了資料關聯性太強的問題第二篇及第三篇都是在改善target Q value的估計，讓訓練更stable及更快第四篇提升了replay memory的利用效率，對於sparse reward的task幫助相當大第五篇算是比較有創意，對於action space很大的task尤其有幫助後面幾篇改進paper的共通點就是他們對於DQN架構的改動都非常少第二第三篇甚只是數行程式碼的程度但提供的效果卻是很顯著，從簡單的cart-pole平衡問題就可以看到很明顯的差別 DQN可說是DRL的開山始祖，在DL內RL相對於SL來說還算是很稚嫩對於這種快速火熱起來的領域當然也免不了一些吐槽文章，其中一篇比較知名的： https://www.alexirpan.com/2018/02/14/rl-hard.html 不過他也不是在唱衰，只是想提醒人們：我們還有很多問題沒有解決並且大部分你想用DRL解決的問題都已經有很好的解決方法，還不用training！（當然就是需要很多domain knowledge) 我目前的心得是DQN雖然主打不需要prior knowledge 就像DL可用CNN feature取代hand-crafted feature 但要能發揮得好，還是得定義一個良好的reward function 這還是需要prior knowledge呀QQ 另外我最近在試時總有一個感覺，DQN對hyper parameter好像超級敏感？有時候只是微調結果卻天差地遠，可以從不會收斂變成快速收斂，不知道是不是我的錯覺最後如果有前輩或跟我一樣正在學習的板友想討論RL領域(不一定要是DQN) 也歡迎來信給我在公司目前還沒有人可以討論更別說請教了QQ，有點閉門造車的感覺 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 58.114.212.150 ※ 文章網址: https://www.ptt.cc/bbs/DataScience/M.1535120997.A.106.html ※ 編輯: thefattiger (58.114.212.150), 08/24/2018 22:31:56 ※ 編輯: thefattiger (58.114.212.150), 08/24/2018 22:35:14 ※ 編輯: thefattiger (58.114.212.150), 08/24/2018 22:38:39 ※ 編輯: thefattiger (58.114.212.150), 08/24/2018 22:39:54