概述
強(qiáng)化學(xué)習(xí)也火了好久，最近才有空來充充電。老實(shí)說，最開始強(qiáng)化學(xué)習(xí)的知識(shí)點(diǎn)還挺多的，看了好久也沒太弄清楚幾個(gè)算法的關(guān)系，所以本著實(shí)踐出真知的想法，找個(gè)案例做下。2048小游戲感覺本身復(fù)雜度還可以，又是個(gè)model-base的模型，檢查起來比較方便，并且可以簡(jiǎn)化到2x2,3x3，所以感覺是個(gè)很不錯(cuò)的demo案例。順便學(xué)習(xí)下傳統(tǒng)的DP那一套東西，所以也做了一些很簡(jiǎn)單的實(shí)驗(yàn)來鞏固下知識(shí)。本文還是會(huì)參雜很多個(gè)人想法，很多想法來自一些實(shí)驗(yàn)測(cè)試結(jié)果。關(guān)于理論的東西網(wǎng)上講的已經(jīng)很多了。因?yàn)椴殚嗁Y料的時(shí)候，看到很多人在嘗試DQN on 2048的時(shí)候遇到了不少問題，所以和大家進(jìn)行下分享。
最終效果
- 大概率能玩出2048
- 最高可以玩3w多分
- 均值1w多分
- 仍有上升空間（可能有啥bug，跑久了容易掛，就沒繼續(xù)跑了）
- 網(wǎng)上能查到的比較厲害的差不多到4096（AI），比例也比較小。
實(shí)驗(yàn)過程
隨機(jī)測(cè)試：
定義：
- max_tile:4x4格子中最大方塊數(shù)
- max_score：n局下來最大總分?jǐn)?shù)（n in 50-100）
- avg_score：n局平均分?jǐn)?shù)（n in 50-100）
4x4的游戲中隨機(jī)算法評(píng)測(cè):
- max_tile:256
- avg_score:700+
- max_score:2k+
這里大概評(píng)估下隨機(jī)水平，方便后面評(píng)估。
DQN初探：
按照自己的想法構(gòu)建了一個(gè)最初版本的DQN
- net:4*4直接reshape(-1,16) - dense_layer(128) - dense_layer_(4)
- memory_sie:100w
- lr:0.001(固定)
- reward:每次運(yùn)行后得分
- gamma(延遲衰減):1
- e-greedy:指數(shù)衰減，最小0.1
結(jié)果：網(wǎng)絡(luò)到max_score:3000之后，好像跑不動(dòng)了。這里一臉蒙，不知道有啥可以改的。于是發(fā)現(xiàn)這個(gè)事情并不簡(jiǎn)單，就想簡(jiǎn)化問題到2x2看看能不能有啥收貨，順便補(bǔ)習(xí)下傳統(tǒng)的一些RL算法，驗(yàn)證下最優(yōu)原理。
值迭代、策略迭代、蒙特卡洛、Q-learning
值迭代：
策略迭代：
- 值迭代、策略迭代、蒙特卡洛、Q-learning：2*2上可以快速收斂。
- Q-learning感覺會(huì)稍微有點(diǎn)波動(dòng)。
DQN 在2x2
當(dāng)用值迭代、策略迭代得到了理論最優(yōu)值之后，又用DQN測(cè)試了一把。發(fā)現(xiàn)DQN結(jié)果比最優(yōu)值總是差點(diǎn)，這就說明網(wǎng)絡(luò)和學(xué)習(xí)策略確實(shí)有點(diǎn)問題，但同時(shí)側(cè)面又反映了，2x2的時(shí)候能很接近最優(yōu)策略，4x4差的比較遠(yuǎn)，那么很大部分問題可能來自參數(shù)化和探索方面。（空間變大會(huì)設(shè)計(jì)到的點(diǎn)）
總結(jié)幾個(gè)提升慢原因：
- 沒有找到足夠高分的點(diǎn)訓(xùn)練
- e-greedy
- 游戲本身隨機(jī)性
- 找到高分點(diǎn)后，沒有訓(xùn)練到
- 被訓(xùn)練數(shù)據(jù)淹沒-memory_size
- lr和高分沒有匹配上,太小了
- reward設(shè)計(jì)不合理
DQN-2013 + 網(wǎng)絡(luò)層迭代、bug修復(fù)
從2x2的地方看出，參數(shù)化有問題，那么第一個(gè)想法就是優(yōu)化下網(wǎng)絡(luò)，dnn還是太粗暴了，還是得cnn，這里就有幾個(gè)方案：
- 原始值 + cnn
- one-hot + cnn
- emb + cnn
- cur + next-step + cnn(github上看到別人的做法，借鑒的alphaGoZero)
新版本改進(jìn):修復(fù)了探索的bug，reward做了log變化，網(wǎng)絡(luò)換成了emb+cnn，新結(jié)果如下：
- max_score:6000
- max_tile:1024
但是問題也暴露的很明顯：
- loss出現(xiàn)了非?？鋸埖陌l(fā)散問題，預(yù)測(cè)值過估計(jì)嚴(yán)重。如下圖，大概意思就是loss變得巨大無比之后，效果就開始變差，loss也下來了。
- loss圖
DDQN/DQN2015
一般講DQN的三個(gè)優(yōu)化：DDQN/Prioritized Experience Replay/dueling-DQN
- DDQN/DQN2015的兩個(gè)方案在2048的案例中都沒有啥效果，過估計(jì)仍然很嚴(yán)重。
- 后面兩個(gè)沒有提到對(duì)過估計(jì)的問題，所以沒有嘗試。
- dueling-dqn在別人的一篇文章中有測(cè)試，dueling-dqn比ddqn的上限要高，早期好像差別也不大。
到這里，其實(shí)有點(diǎn)調(diào)不下去了，后來在網(wǎng)上翻到了一個(gè)代碼。能跑出2048，天吶，發(fā)現(xiàn)寶了，做了很多測(cè)試，發(fā)現(xiàn)我和他的方案上差異還是蠻大的，然后就開始了一點(diǎn)點(diǎn)比較的階段。
復(fù)現(xiàn)Github方案
先提出別人和我方案的差異點(diǎn)：
- lr別人用了離散衰減，start-lr = 0.0005
- reward:用了max_tile增量+合并單元數(shù)
- memory_size:6000?。?！
- 更新方案：dqn2013，沒用target
- gamma:0.9
- egreedy:0.9 ，10000步后快速收斂到0
-
net:一個(gè)比較定制化的one-hot + cnn
image.png
我在他的方案上做了一系列實(shí)驗(yàn)：
實(shí)驗(yàn)1：把e-greedy改成最小0.1
實(shí)驗(yàn)結(jié)果：
- max_score到1w+后開始增長(zhǎng)變得很慢，很久都沒有提升。說明該任務(wù)本身具有比較強(qiáng)的前后相關(guān)性和隨機(jī)性，最終還保持較高的探索難以發(fā)現(xiàn)最佳值。
實(shí)驗(yàn)2：用數(shù)值網(wǎng)絡(luò)代替one-hot+cnn
實(shí)驗(yàn)結(jié)果：
- 提升沒有之前快了，這個(gè)實(shí)驗(yàn)沒跑完就掛了，但是raw的效果不如cnn。說明網(wǎng)絡(luò)結(jié)構(gòu)影響比較大
實(shí)驗(yàn)3：reward改成每步獲取score
- 監(jiān)控幾乎和之前差不多，說明兩個(gè)reward設(shè)計(jì)都可行。
實(shí)驗(yàn)4：在原基礎(chǔ)上只用max_tile來作為回報(bào)，拿掉合并分?jǐn)?shù)。
- 無法達(dá)到2048，在1024前就好像不漲了。說明reward也不能設(shè)計(jì)的太隨意，要保持和訓(xùn)練方案比較高的協(xié)調(diào)性，只用max的話，reward會(huì)比較稀疏。
在做完上述一系列實(shí)驗(yàn)后，我大致有了個(gè)數(shù)，然后對(duì)自己的實(shí)驗(yàn)進(jìn)行了優(yōu)化。
優(yōu)化方案：
- lr設(shè)計(jì)成離散衰減
- gamma:1 （沒變）
- reward:score （沒變）
- 更新方案：dqn-2013（沒變）
- memory_size:6000
- egreedy:0.9指數(shù)衰減，10000步后快速收斂到0
- net:emb+普通2*2的cnn2層 （不變）
結(jié)果： - max_score:3.4w
- max_tile:2048
- avg_score:10000
- 截張圖看下：
- 2048
之后測(cè)試了下ddqn，發(fā)現(xiàn)收斂比較。本身把memory_size設(shè)置小了之后，過估計(jì)就沒有這么嚴(yán)重了。這里簡(jiǎn)單分下，過估計(jì)本身在Q-learning中就存在，回訪池過大之后，訓(xùn)練越多，過估計(jì)越嚴(yán)重，在沒有很好的高分?jǐn)?shù)據(jù)前，就給搞過估計(jì)了，所以后面就不好迭代了。反而用小點(diǎn)的話，過估計(jì)不嚴(yán)重，在高分出現(xiàn)后也不會(huì)淹沒在數(shù)據(jù)中，對(duì)于這個(gè)任務(wù)可能更好一點(diǎn)。很多結(jié)論可能都與這種需要長(zhǎng)期規(guī)劃的性質(zhì)相關(guān)。
蒙特卡洛樹搜索探索
出于對(duì)alphaGo的膜拜，我也想過，dqn很多時(shí)候不好訓(xùn)練，就是很難拿到高分訓(xùn)練數(shù)據(jù)，能不能和alphaGo一樣，用個(gè)mcts,就簡(jiǎn)單做了下。結(jié)果如下：
- 純蒙特卡洛樹搜索的方案:每步模擬100-200，可以輕松到達(dá)2048，均值2w+（這里測(cè)試數(shù)據(jù)不多，跑的很慢，所以想用mcts來訓(xùn)練dqn的方案也被pass了）。
需要監(jiān)控的點(diǎn)
- loss：DQN過估計(jì)嚴(yán)重，需要密切關(guān)注loss情況
- max-label：如果沒有出現(xiàn)過大值，看看探索過程是不是有問題。后期探索不能太大。
- e-greedy：關(guān)注探索程度
- episode：關(guān)注大致進(jìn)度和速度
- lr：這個(gè)和loss配合著看
- 評(píng)估指標(biāo)：avg/max score
RL的任務(wù)感覺需要監(jiān)控的內(nèi)容更多，不光是監(jiān)督學(xué)習(xí)的部分，探索的部分也很重要。
訓(xùn)練情況
- 訓(xùn)練出2048，要2個(gè)小時(shí)左右。大概2w episode這個(gè)樣子。
小結(jié)
到此，2048的探索可能就先告一段落，雖然很多事情并沒有研究太明白。但是對(duì)于整個(gè)算法有了個(gè)基礎(chǔ)的認(rèn)識(shí)。并對(duì)算法中可能存在的優(yōu)化點(diǎn)有了一些了解。后續(xù)可能會(huì)嘗試下策略梯度那一趴的東西。
