強化学習による「Montezuma's Revenge」への挑戦

20170704
1
強化学習による
「Montezuma's Revenge」への挑戦
飯塚孝好
( スタッフサービスエンジニアリング、日立製作所OB)

20170704 2
Monezuma's Revengeとは
 DeepMindが強化学習の評価に
利用するAtari2600ゲームの1つ
 平均得点が人間に対し0%と、
強化学習における最難関ゲーム
の1つだった（2016年6月まで)
関連サイト：https://deepmind.com/blog/deep-reinforcement-learning/

20170704 3
得点が取れない原因
①キャラ(*1)が直ぐに死んでしまい、先に進めない
②得点頻度が少ない → 学習機会が少なくい
下記はランダムなアクションでの得点比率(1M steps中)
ゲームゲーム回数得点非0のゲーム回数得点比率
Breakout 5440 4202 77.3%
Montezuma's Revenge 2323 1 0.043%
(*1) キャラの通称はPanama Joe。Montezumaは地名。

20170704 4
単純対策とその結果
①キャラが直ぐに死んでしまい、先に進めない
【対策】危険回避に向け、マイナスの得点を与えては？
【結果】危険な場所に近づかず、前に進まない
②得点頻度が少ない → 学習機会が少ない
【対策】学習機会を増やすため、常に得点を与えては？
【結果】何もしなくても報酬があるので、何もしない
③上記に加え、危険な場所の先に進む動機が無い
【対策】上記①と②の対策を組み合わせては？
【結果】結局、一箇所に留まって、前に進まない
＝＞危険な場所を超えて未開拓領域に行く動機付けが必要
＝＞同じ場所に留まると得点が減るようにすれば良さそう

20170704 5
DeepMindの論文との出会い
 Monezuma's Revenge実験経過をブログとtwitterで発信し
ていたところ、評価に使っているコードの作成者である三好
氏からtwitterでDeepMindの論文「Unifying Count-Based
Exploration and Intrinsic Motivation」を紹介頂いた
 論文概要を見たところ、ゲーム状態の頻度に基づいて得点
を与えることで「動機付けする」方法が書かれており、
Montezuma's Revengeにも適用済だった
 Montezuma's Revengeへの適用結果は良好で、
平均得点が、Double DQNでは3439まで上昇(100M step)、
A3Cでは273まで上昇(200M step)

20170704 6
[論文] キーアイデア
 状態をバイナリー比較して回数を数える方法もあるが、全く
同じ状態の頻度はほぼ0で、未経験状態には有効性が低い
【例】下記で新データ(SUN, LATE, BUSY)の予測確率は?
 キーアイデア：
・1/10*1/10*9/10 (=0.009)が予測確率として適切そう (ρ )
・新データ観測後の確率は2/11*2/11*10/11(=0.03) (ρ')
(論文ではρ'をrecording probabilityと命名)
day# 天気時間帯混雑度
1 SUN LATE QUIET
2 RAIN EARY BUSY
3 RAIN EARY BUSY
4 RAIN EARY BUSY
5 RAIN EARY BUSY
6 RAIN EARY BUSY
7 RAIN EARY BUSY
8 RAIN EARY BUSY
9 RAIN EARY BUSY
10 RAIN EARY BUSY

20170704 7
[論文] アイデアの定式化
 データが複数空間(前頁例では天気、時間帯、混雑度)の直積の要素の場
合、空間毎の確率が互いに独立と仮定/単純化し、各空間毎の出現確
率ρ(又はρ')の積をデータの出現確率ρ(又はρ')と考えてみる
 各空間では、該当空間での新データ値(例えばSUN)の、既存データn個
中での出現回数がN回のとき、ρとρ'は、次の式になる
 ρ = N/n
 ρ' = (N + 1)/(n + 1)
 逆に、 ρとρ'からNを求めると次のようになる
 N = ρ(1 – ρ')/(ρ' – ρ) ≒ ρ/(ρ' – ρ) (ρ' << 1と仮定)
 そこで、直積空間に対するρとρ'に対しても、Nを計算できる
 論文では、このNをpseudo-count (疑似カウント)と命名
 前頁例は、ρ = 1/10*1/10*9/10 =0.009、ρ' = 2/11*2/11*10/11 = 0.03で、
N = 0.009/(0.03 – 0.009) = 0.42 となる (0以上1以下で、それらしい値)
(注)上記、かなり簡略化し、記号も一部省略しています。詳細は論文を参照ください

20170704 8
[論文] 強化学習での活用
 ゲーム画面xの各画素毎にρ(及びρ')を計算する
 全画素のρ(及びρ')の積を、xのρ(及びρ')とする
 xのρ及びρ'から、pseudo-count「N(x)」を計算する
 N(x)から下記を計算し、pseudo-rewardとして学習させる
 R(x) = β / (N(x) + 0.01)P
 N(x)が大きいほどR(x)は小さくなる => 頻度が高い画面は得点が小さい
 0.01は0割防止が目的で、値に意味はない
 Pは実際に学習させて試し、最適な値を算出
 1と2と1/2を試し、Double DQNでもA3CでもP=2が最適
 βは実際に学習させて試し、最適な値を算出
 Double DQNでは0.05、A3Cでは0.01が最適
 Peudo-reward R(x)は、学習に用いるがゲーム得点には非計上

20170704 9
[論文] Double DQNでの効果
 5ゲームで評価し、下記2ゲームで特に効果大
 Montezuma's Revengeで到達部屋が大幅拡大
この部屋だけで3000
点取得でき、高得点
を取るうえでは一番
重要な部屋
（論文作者に確認済：
https://www.youtub
e.com/watch?v=0yI
2wJ6F8r0 ）

20170704 10
論文概要 (A3Cでの効果)
 全60ゲームで評価。Randomアクションによる得点
の150%以下しか取れないゲームが5個減った(ピンク)
 [報告者意見] Montezuma' Revengeでの効果は限定的
Score<150%Random Stochastic-ALE Deterministic-ALE Stochastic-ALE Deterministic-ALE
A3C A3C+ DQN A3C A3C+ A3C A3C+ Random Human A3C A3C+ DQN A3C A3C+ DQN
1 ASTEROIDS X 2680.7 2257.9 3946.2 2406.6 719.1 47388.7 4% 3% 0% 7% 4% 0%
2 BATTLE-ZONE X 3143.0 7429.0 3393.8 7969.1 2360.0 37187.5 2% 15% 41% 3% 16% 45%
3 BOWLING X 32.9 68.7 35.0 76.0 23.1 160.7 7% 33% 4% 9% 38% 5%
4 DOUBLE-DUNK X X 0.5 -8.9 0.2 -7.8 -18.6 -16.4 870% 442% 320% 854% 489% 210%
5 ENDURO X 0.0 749.1 0.0 694.8 0.0 860.5 0% 87% 40% 0% 81% 51%
6 FREEWAY X 0.0 27.3 0.0 30.5 0.0 29.6 0% 92% 103% 0% 103% 102%
7 GRAVITAR X X X 204.7 246.0 201.3 238.7 173.0 3351.4 1% 2% -4% 1% 2% 1%
8 ICE-HOCKEY X X -5.2 -7.1 -5.1 -6.5 -11.2 0.9 49% 34% 12% 50% 39% 7%
9 KANGAROO X 47.2 5475.7 46.6 4883.5 52.0 3035.0 0% 182% 138% 0% 162% 198%
10 MONTEZUMA'S-REVENGE X 0.1 142.5 0.2 273.7 0.0 4753.3 0% 3% 0% 0% 6% 0%
11 PITFALL X X X -8.8 -156.0 -7.0 -259.1 -229.4 6463.7 3% 1% 2% 3% 0% 2%
12 ROBOTANK X 2.1 6.7 2.2 7.7 2.2 11.9 -1% 46% 501% 0% 56% 395%
13 SKIING X X X -23670.0 -20066.7 -20959.0 -22177.5 -17098.1 -4336.9 -51% -23% -73% -30% -40% -85%
14 SOLARIS X X 2157.0 2175.7 2102.1 2270.2 1236.3 12326.7 8% 8% -4% 8% 9% 5%
15 SURROUND X X X -7.8 -7.0 -7.1 -7.2 -10.0 6.5 13% 18% 7% 18% 17% 11%
16 TENNIS X X X -12.4 -20.5 -16.2 -23.1 -23.8 -8.9 76% 22% 73% 51% 5% 106%
17 TIME-PILOT X X X 7417.1 3816.4 9000.9 4103.0 3568.0 5925.0 163% 11% -32% 231% 23% 21%
18 VENTURE X X 0.0 0.0 0.0 0.0 0.0 1188.0 0% 0% 5% 0% 0% 0%
14X 10X 10X 15X 14X 14X 16X 14X 13X
注：上記表は、論文に書かれたデータを基に、報告者が再集計したもの

20170704 11
[報告者] A3Cで試行（その理由）
 報告者はA3Cで論文の手法を試行
 理由は、論文を読む前に、Montezuma's Revengeを
色々と試行したA3C環境があったため
 また、同A3C環境は、学習速度(steps/秒)が高速な
ため、短時間で論文の効果を確認できると考えた
 論文でDouble DQNの評価結果が少ないのは、おそらく、
評価に時間が掛かり結果を出せなかったか、他のゲーム
では悪い結果になるためと推測

20170704 12
[報告者] 試行初回でDeepMind越え
 既存A3C評価環境に、pseudo-countを組込み、
試したら、初回で論文のA3Cを超える得点が出た

20170704 13
[報告者] 報告者独自コードの効果
 正確に評価するために、報告者独自コードをOFFに
して再評価したところ、点数が伸びないことが判明
 途中からONにすると、点数が上がることが分かった
独自コード： OFF -> ON

20170704 14
[報告者] 報告者独自コード概要
 報告者の独自コードは、得点(pseudo-countでの得点を除く)を得る度に、得点を得
るまでの150ステップの履歴で学習するというもの。On-Highscore-Leaning:OHLと命名
 上記に加え下記も入っていたが、上記の効果が最大
 ライフが減る度にマイナスの得点(-1.0)を与える
 無得点期間が長いとアクションのランダム性を高める
 上記以外にも、下記のような多数のパラメータ／機能を導入し、試行
 TES: 学習履歴長 (150以上・以下で色々試行。残ライフ数に応じた動的履歴長も試行)
 Peudo-count計算で用いるPとβ (β=0.01は点数が上がらず、β=0.02近辺が最適だった)
 学習アルゴリズム (A3C-FFとA3C-LSTMを試行)
 ゲーム環境基盤 (ALEとOpenAI Gymの両方で試行)
 フレームスキップ数 (ALEは4が高得点、7が探索範囲最大。OpenAI Gymは2が最適)
 カラー変換方式 (スキップしたフレーム含め平均/最大計算、又は最後のフレームを利用)
 Thread 0でsavedしたpseudo countを全threadでrestore / thread毎にsave/restore
 Pseudo-count計算時の画素値のビット数 (DeepMindは3、当方で最適は7)
 Pseudo countを全部屋共通で持つ / 各部屋ごとに持つ
 各thread毎に別々のパラメータを指定 (TES、P、βをthread毎に指定可能)
 最適ハイパーパラメーター探索のため、Google Cloudで100回以上試行
 常套手段は、全パラメータを乱数で割り当て、同時多数評価が良いが、1試行に4CPUで
4日程度掛かるため、少ないIT資源の元、ヤマ勘に頼りながらパラメーターを探索
 格安(通常の1/3)のPreemptible VMを利用し、無料試用枠で6 VMを2か月運用 (x 2)

20170704 15
[報告者] ALEでの試行 (1)
 ALE環境で平均得点が2000点に迫った (2016/10/6)
 Laser Barrierを超えられず、3000ポイント取れる部屋に行けず
Laser barriers
Laser barriers

20170704 16
 キャラが成功体験の亡霊に囚われたような行動にハマった
https://youtu.be/UZn4yJkIaN0
 状態遷移がループしているためと推測※
 即ち、2カ所がループ結ばれると、過去の得点(下記①)が未来の得点
として観測され、もう点数が得られないのに、得られると錯覚する
 状態のループが無ければ、R(x)が部屋の左端で急激に0になる事で、
その場所、つまり状態での評価値も次第に減少するが、ループがある
と、ループに沿って、上の部屋やその場所での過去の得点がベルマン
方程式で伝播されるため、何時まで経っても、その場所の評価値が変
化せず、高得点のままなので、その場所に留まると言う事。
1
2
• 左上から入ってきて、②を通って、①で得点取得
• その後、②でさらに得点取得
• その後、①に行って、そのままずっと留まる
（一度①で得点が得られたので、また得られると錯覚）
※ ①の剣が無くなる前と後の区別が十分に出来ず、ループに見えてしまう

20170704 17
[報告者] OpenAI Gymでの試行 (1)
 平均スコアが1600点を超えた
 DeepMindの論文未記載の部屋に到達(下記でピンクの部屋)
 部屋3, 8, 9到達動画 https://youtu.be/qOyFLCK8Umw
 部屋18, 19到達動画 https://youtu.be/jMDhb-Toii8
 部屋19, 20到達動画 https://youtu.be/vwkIg1Un7JA

20170704 18
 OpenAI GymでLaser Barrierを超えた要因は非決定性と推測
 OpenAI Gymでは、フレームスキップ数が非決定的に決まる
(OpenAI Gym側で勝手に(一様乱数で)2～4フレームスキップする)
 以て、遭遇する状態が増え、Laser Barrier超えの試行もできたと推測
 なお、フレームスキップ数が一様乱数で2～4というのは、変動が激しすぎるた
め、報告者は、同じActionでOpenAI Gymを2回呼び出すことにより、平均値が7
の正規分布に近いフレームスキップ数に変換して試行
 スコアが0になり回復しない現象が多発したため、Thread毎にパラメー
タを変えて多様性を高めたところ、0から回復し安定した学習ができた
全Thread同一パラメータ
Thread毎に別パラメータ
Thread 0 1 2 3 4 5 6 7
TES 40 40 40 40 29 29 29 29
β 0.018 0.018 0.018 0.018 0.02 0.02 0.02 0.02
P 2 2 2 2 2.2 2.2 2.2 2.2
Thread 0 1 2 3 4 5 6 7
TES 40 40 40 40 40 40 40 40
β 0.018 0.018 0.018 0.018 0.018 0.018 0.018 0.018
P 2 2 2 2 2 2 2 2
注：上記2例含む実験結果：http://52.199.15.161/OpenAIGym/montezuma-x1/00index.html

20170704 19
 スコアが0になり回復しない現象に関するコメント
 ROOM#7訪問回数増加後に、突然スコアが0になった
 次の現象が起きていると推測
 ROOM#7や他の部屋での学習の副作用として、ROOM#1の
脱出鍵が入手できなくなる(NNの値がそのように変化する)。
 これにより、ROOM#1から脱出でず、ROOM#1でしか学習が起こらない
 しかし、ROOM#1内の各地点(実際は状態)は通過頻度が高く、R(X)がほぼ0に
なっている、R(X)による学習は発生せず、R(X)無しの学習とほぼ同じ状態。
 ただし、キャラが死ぬActionは選ばれない状態になっているので、キャラが死な
ない程度の僅かな動きだけになる (これはプレイ動画で確認済)。
 上記が正しいとすると、R(X)のみでの学習では、実得点を取れる所に
辿り着けるものの、その地点へのルートの学習が一度失われると、回
復しない。そのために、学習が非常に不安定になると思われる。
 これに対し、Double DQNでは、一度学習したパスを後で利用するの
で、一度スコアが0になっても、安定な学習ができると思われる。
 Thread毎別パラメータで学習が安定するのは、R(X)が0にならない
Threadが残り、そのThreadで鍵到達の学習が進むためと思われる。

20170704 20
到達範囲 (2016/12/5)
 OpenAI Gymでの実験結果一覧：http://52.199.15.161/OpenAIGym/
3000点の部屋：
残念ながら、
到達できず

20170704 21
 ALEでもフレームスキップ数を7にすると、フレーム数/秒(60)と互いに
素になり、遭遇する状態が増え、Laser Barrier超えができるか試行
 試行初回で、ALEでもLaser Barrierを超えることができた
 なお、Google Cloud試用期限切れで自宅PCしか使えなかったため、
実験回数は数回程度だが、到達範囲は下記で、比較的広い
 ALEでの実験結果一覧：http://52.199.15.161/ALE/

20170704 22
まとめ
 Pseudo-countは、得点機会が僅少のゲームに有効
 On-Highscore-Leaning (OHL)は、A3Cでのスコアアップに有効
 OpenAI Gymでの非決定性は探索範囲拡大に有効
 Thread毎別パラメーターは、学習の安定化に有効
 DeepMindの論文で未記載の部屋に到達
 補足
 本発表に関連した情報
 ブログ：http://itsukara.hateblo.jp/
 コード：https://github.com/Itsukara/async_deep_reinforce
 謝辞
 高速なA3Cコードを提供頂いた三好氏に感謝します

20170704 23
今後の課題・展望
 他の強化学習含め、状態のループを考慮する必要がある。
 一度学習した結果が他の部屋の学習で失われる点に関しては、
Replay Memory、UNREAL、EWC、DNC、など、各種手法の適用が
考えられる (全てDeepMindが論文を出している)。
 キャラの場所を検出し、キャラの場所毎の状態評価値や、Action方向
等を図示すると、今後の取り組みのヒントになる可能性あり。
 現在のNNでは、前処理でモノクロ化を行っているが、人間もカラー方
が現在場所が分かるので、カラー画像での学習も必要では？
 同じような作りの部屋が多いので、人間でも、マップを見ないとどの部
屋にいて、どの戦略が必要か分かりにくい。AIもマップが必要では？
 直近の行動を決めるNNの上に、階層的に、直下のNNの評価・制御を
行うNNを構築すると、高度な判断(戦略等)が創出できないか？
（スクエアエニックスのゲームAIは、そのような構造とのこと)
 参考『人工知能は意識を持てるのか？』 https://t.co/scva6kmIps https://t.co/scva6kmIps https://t.co/GGgtmsbKFu

20170704 24
付録1：Pseudo-count関連疑似コード
Data structure (with initial value)
Case when having pseudo-count in each room, each thread has following data
 psc_vcount = np.zeros((24, maxval + 1, frsize * frsize), dtype=np.float64)
 24 is the number of rooms in Montezuma’s Revenge
 Currently it is constant.
 In the future, currently playing room and connection structure of rooms
should be detected automatically.
 This will be useful to evaluate the value of exploration.
 The value of exploration can be used as additional reward.
 maxval is the max value of pixel in pseudo-count
 Can be changed in option. Default:128
 Real pixel value is scaled to fit this maxval
 frsize is size of image in pseudo-count
 Can be changed in option. Default:42
 Screen of game is scaled to fit image size (frsize * frsize)
Case when having one pseudo-count, each thread has following data
 psc_vcount = np.zeros((maxval + 1, frsize * frsize), dtype=np.float64)
Two cases in above can be selected by option
The order of dimension is important to have good memory locality
 If dimension for pixel value comes last, the performance of training decreases
roughly 20%. Because the value of pixel is sparse and cause many cache miss.

20170704 25
付録1：Pseudo-count関連疑似コード
Algorithm (algorithm to calcalate pseudo-reward)
vcount = psc_vcount[room_no, psc_image, range_k]
 This is not a scalar, not a fancy index, but is a temporary array
 room_no is index of the room currently playing
 psc_image is screen image scaled to fit size:(frsize * frsize), pixel-value:maxval
 range_k = np.array([i for i in range(frsize * frsize)]) (calculated in initialization)
psc_vcount[room_no, psc_image, range_k] += 1.0
 The count of occurred pixel value is incremented
r_over_rp = np.prod(nr * vcount / (1.0 + vcount))
 ρ / ρ‘ for each pixel is calculated, and ρ / ρ‘ for screen image is calculated
 ρ / ρ‘ = {N/n} / {(N+1)/(n+1)} = nr * N / (1.0 + N) = nr * vcount /(1.0 + count)
 nr = (n + 1.0) / n where n is the number of observation, count starts in initialization
psc_count = r_over_rp / (1.0 – r_over_rp)
 This is a pseudo-count. As easily confirmed, r_over_rp / (1.0 – r_over_rp) = ρ/(ρ' – ρ)
 Not directly calculate ρ/(ρ' – ρ).
Because both ρ' and ρ are very small, caluculation error in ρ' – ρ become big.
psc_reward = psc_beta / math.pow(psc_count + psc_alpha, psc_rev_pow)
 This is a pseudo-reward calculated from pseudo-count
 psc_beta = β and can be changed by option in each thread
 psc_rev_pow = 1/P, P is float value and can be changed by option in each thread
 Psc_alpha = math.pow(0.1, P) ; So,
 math.pow(psc_count + psc_alpha, psc_rev_pow) = 0.1 for any P when psc_count is almost 0

20170704 26
付録２：Pseudo-countの可視化
 3M step
 45M step
頻度No.1画素値頻度No.2画素値頻度No.3画素値
頻度No.1画素値頻度No.2画素値頻度No.3画素値
複数の部屋が混在
し、キャラクターの軌
跡が十分に見えな
い。
部屋ごとに
別々のpseudo-
countを持ったほうが
良さそう。
=>
機能実装・実験済
頻度No.2以降の画
像は、キャラクターの
軌跡が含まれるよう
に見える。つまり、キ
ャラクターの場所ごと
の頻度が得られてい
る。

20170704 27
付録3：学習状況リアルタイム可視化
*.r: 全スコア(実スコア)の分布と、その平均の推移
*.R: 凡例に示した番号の部屋の訪問頻度
*.RO: 凡例に示した番号の部屋でのOHL頻度
*.lives: 凡例に示したスコア取得時の残ライフ数
*.k: 凡例に示した部屋でのkill頻度
*.tes: 凡例に示したスコア取得時のOHL学習履歴長
*.s: 凡例に示したスコア取得までのstep数
*.prR: 部屋毎のR(x)の分布とその平均の推移
*.vR: 部屋毎の評価値の分布とその平均の推移

20170704 28
付録4：thread多様性の効果
 Same parameters in every thread
 Different parameters in each thread (diversity of parameters in threads)
Score went down to 0,
and not recovered from it
Score went down to 0,
but recovered from it
 See: http://52.199.15.161/OpenAIGym/montezuma-x1/00index.html

強化学習による「Montezuma's Revenge」への挑戦

強化学習による「Montezuma's Revenge」への挑戦

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Viewers also liked

Viewers also liked (20)

Similar to 強化学習による「Montezuma's Revenge」への挑戦

Similar to 強化学習による「Montezuma's Revenge」への挑戦 (16)