Deep Q-learning (DQN) 原理說明

Mnih, Volodymyr, et al. “Playing atari with deep reinforcement learning.” arXiv preprint arXiv:1312.5602 (2013).

這個演算法就是當今鼎鼎有名的公司DeepMind所發明出來的，而DeepMind就是靠著這套演算法得到Google公司的青睞，因而在2014年就花高價把這間公司買下來，多年後證明Google當初的決定是對的，DeepMind不負眾望的挑戰從前人工智慧難以望其項背的棋類項目-圍棋，並成功打敗目前人類最頂尖棋手-柯潔，從最初版本的AlphaGo，一直到AlphaGO-Master，最後是不靠人類棋譜資料的AlphaGO-Zero，無處不顯示人工智慧的強大，而打造這一切的基礎便是當初的演算法DQN。

DQN 是由兩個龐大體系所組成的，第一個是強化式學習，另一個就是深度學習。強化學習是存在許久的理論，早在幾十年前研究學者就已經對它進行了許多研究，有興趣的朋友可以找找 Sutton 強化學習的聖經 - An introduction to reinforcement learning，又或者是可以到小編所寫日誌上觀看學習，亦或是到網路上也都存在許多珍貴的學習資源。
Reinforcement Learning - Q learning 推導

另一個龐大體系則為深度學習，是近期非常蓬勃發展的研究項目，DeepMind的厲害之處在於它成功的結合這兩大系統，並利用Atari遊戲當做實驗環境來進行學習並得到非常好的成效，在某些遊戲中，學習的機器人得分甚至比人類專家的得分還要高，因而人們才開始體現到這兩大演算法結合所能發揮的效用。

底下是DeepMind用DQN學習打磚塊遊戲的精彩影片 :
https://www.youtube.com/watch?v=V1eYniJ0Rnk

其實若要簡單的講解DQN的話，就是把Q-learning中的Qtable換成卷積神經網路罷了，先讓我們來複習一下強化式學習在做什麼，下圖是一個收斂的走迷宮Qtable，左上角是起點，右下角是終點，共有16個狀態，四種動作(上下左右)，Q-learning的最終目的其實就是要學習圖裡面的這些數字

如果還不懂上面這圖的建議看一下我之前的教學實現最簡單Q-learning迷宮程式

通常我們會把Q-table 這樣表示

因此就可以表示成 f(s,a)=?, 舉例來說  f(s2,ad)=0.4096

DQN 就是把這個函數 f() 換成 卷積神經網路，所以可以圖解成

因此，核新概念還是一樣，我們希望這網路最終會收斂，且收斂後的數值能讓整個系統拿到最大的reward加總，將機器人按照最後收斂的這個網路執行動作，則機器人最終就會超越常人。如同剛剛的打磚塊範例一樣，為什麼那個打磚塊機器人那麼厲害，撇除訓練的步驟不說，實際上就是在運行一個巨大的Qtable罷了，機器人每獲得一個畫面就會把它當成輸入狀態輸進網路中得到不同動作的Q值，而機器人僅僅只是挑選動作最大的Q值動作，如此反覆不斷的執行，最終就會呈現出影片中的學習效果。

下面繼續說明演算法的訓練過程，小編把幾個核新想法獨立出來講解並搭配個實際遊戲例子好說明整個流程

收集一個經驗

這裡舉個實際的例子方便後續的講解，state指的就是系統狀態，套用在遊戲中則是指遊戲的畫面，我以flappy bird遊戲為例子，遊戲的狀態即為連續四張的遊戲畫面，剛開始小鳥會胡亂飛，為的是收集足夠多的數據來進行訓練，等資料收集足夠後即會開始縮小亂飛的機率，在強化學習專業術語中，這個亂飛的機率稱為epsilon，epsilon剛開始設1，之後隨著時間的增長會慢慢變小，直到最後一直固定成0.05。假設此次小鳥在S狀態下採取了向上的動作得到了reward，則此次的經驗所獲得的資訊有

• 1.S: 本次狀態畫面
• 2.A: 採取的動作
• 3.S’:採取動作A後所獲得的下次狀態畫面
• 4.R: 採取動作A後所獲得的reward

訓練更新流程

訓練的更新過程其實就是訓練一個CNN網路，如同傳統監督式學習算法，學習的過程中必須給予輸入樣本以及輸出樣本資訊，這裡的輸入樣本即為狀態S，也就是在S狀態下的連續四張遊戲畫面，而輸出樣本即是Q值，給予Q值的方法正是強化式學習的精髓所在，分為兩種情況:

• 註:本遊戲設置的reward為撞到管子為-1，其它時候皆為0

1.下個狀態S’為終止狀態(小鳥撞到管子至使遊戲結束):
Q_up 更新為

                                              -1(reward)   

2.下個狀態S’不為終止狀態:
Q_up 更新為 reward 加上折扣率乘上下個狀態所有action中的最大Q值。以下面的圖例來說，下個狀態S’總共有兩個動作，一個代表上，Q值為0.2，一個代表下，Q值為0.3，則按照公式的意思來說就是挑選最大的值，也就是0.3，因此完整數字更新如下

                                            0(reward)+0.9(gamma)*0.3

按照演算法公式不斷得更新，最終，網路就會學出最佳Q值出來，達成如上面迷宮範例所示的呈現收斂的狀態。執行的時候，網路只要一直選擇Q值最大的動作，長久一來就會獲得最大的reward加總，因此就會看到小鳥一直不停的躲過管子，成為一隻具有智慧的鳥。

收集一連串經驗

如同往常深度學習一樣，訓練的時候皆需要大量的訓練樣本，這在DRL中是再輕鬆也不過的事了，獲得的經驗只需要不斷的獲得環境的反饋即可，樣本是無窮無盡的，也因為如此，咱們必須限定收集樣本的數量，否則只怕您的電腦記憶體會吃不消吧，這個收集經驗的容器撐作 experience replay buffer，總共會收集N比，若收集到了第N+1筆則會捨棄第一筆所得到的資料，因此會讓經驗集合一直保持在N筆。

成群的訓練

剛剛所講解的只是訓練一筆資料，而實際上訓練網路時基本上都要成群成組的訓練，採取這樣的方式訓練出來的資料才會又快又準，在機器學習中這稱為batch learning。訓練的時候會從剛剛所蒐集的經驗容器中隨機抽取N筆資料來進行訓練，隨著學習次數的增加，所學習到的經驗會越來越純熟，因此小鳥能越學越穩定，最終超乎人類專家。

至此所有核新概念都已經闡述完畢，若您實際跑過這程式的話，您會很驚奇這演算法，因為小鳥就像是嬰兒在學習一樣，剛開始小鳥會胡亂飛，甚至一直去撞管子，可到了後來小鳥就像開啟外掛模式一樣，總能夠在快撞到管子的時候驚險閃過，躲過重重的障礙。而舉例小鳥這遊戲只是小小的一個例子，實際上這演算法可以運用在許多遊戲中，DeepMind就是用這套演算法來打古老的電玩遊戲Atari Game，從此一舉成名，甚至後來還發展出不用人類棋譜學習的AlphaGo Zero機器人，相信經過了解DQN的演算法後您能對AlphaGo有更清楚的體會為什麼DRL有這麼強大的力量，也為什麼各家科技巨頭都在研究發展它了。

有興趣的同學想要更深入研究的話可以細細觀看程式碼並且若資源許可的話也可以跑跑程式碼

https://github.com/yenchenlin/DeepLearningFlappyBird