DQN速習会@Wantedly

Brief workshop of Deep Q-Network at Wantedly

1. DQNはDQNでも賢いDQN速習会@Wantedly 妹尾卓磨
2. 自己紹介 妹尾 卓磨 慶應義塾大学理工学部情報工学科 今井研究室 強化学習についての研究 好きなもの: Star Wars 2
3. 速習すること • 強化学習の概要をなんとなく知る ◦ DQNで遊ぶのに必要なミニマルな基礎理論を知る • DQNがどうやって動いているか知る ◦ DQNで遊ぶのに必要なDQNの仕組みを知る • DQNで遊んでみる ◦ 遊んでみる 3
4. 今回の経緯 強化学習の研究をしているのでプロダクトに活かしたいので速習会やろ でもDQNはまだ気軽にプロダクションへ活かせるものではない （そもそもDeepである必要がない場合が多いだろう） だからこそ最初に強化学習の概要を知るのは大事 でも入り口としてDQNは面白いじゃん！！ 4
5. 強化学習を知る 5
6. 強化学習で話題になったこと（１） AlphaGo 囲碁チャンピオンを倒したAI https://www.youtube.com/watch?v=f_r9smp4-0U Silver, David and Huang, Aja and Maddison, Chris J. and Guez, Arthur and Sifre, Laurent and van den Driessche, George and Schrittwieser, Julian and Antonoglou, Ioannis and Panneershelvam, Veda and Lanctot, Marc and Dieleman, Sander and Grewe, Dominik and Nham, John and Kalchbrenner, Nal and Sutskever, Ilya and Lillicrap, Timothy and Leach, Madeleine and Kavukcuoglu, Koray and Graepel, Thore and Hassabis, Demis, Mastering the Game of Go with Deep Neural Networks and Tree Search, 2016 6
7. 強化学習で話題になったこと（２） Deep Q-Network (DQN) Atariで人間と同じかそれ以上の点数を取れるようになった https://www.youtube.com/watch?v=TmPfTpjtdgg 7 Volodymyr Mnih and Koray Kavukcuoglu and David Silver and Alex Graves and Ioannis Antonoglou and Daan Wierstra and Martin Riedmiller,Playing Atari With Deep Reinforcement Learning, 2013 Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis, Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, Demis Hassabis, Human-level control through deep reinforcement learning, 2015
8. 強化学習で話題になったこと（３） Googleがデータセンターの冷却に必要なエネルギーを40%削減したらしい （DQNを使ったとは明示的には書いていないが） https://environment.google/projects/machine-learning/ https://blog.google/topics/environment/deepmind-ai-reduces-energy-used-for/ 8
9. 身近な強化学習の例 遭難して無人島にいるところを想像しましょう 浜辺にずっといると死んでしまうので島を探索しなければならない • 戦略1 綺麗な水や食べ物を探しに歩きまわる • 戦略2 歩いたら疲れるし、悪い水を飲んだら危ないので浜辺でじっとする 牧野貴樹、渋谷長史、白真一、これからの強化学習、 2016より抜粋 9
10. 無人島での戦略 • 戦略1: 綺麗な水や食べ物を探しに歩きまわる リスクはあるが、もし発見できれば今後そこを利用して長く生存できる可能性 • 戦略2: 歩いたら疲れるし、悪い水を飲んだら危ないので浜辺でじっとする リスクはないのでアクシデントで死ぬことはないが、このままだと死ぬ これをうまく解くのが強化学習！ 10
11. 強化学習とは（１） 機械学習には大きく分けて3つのタイプがあります • 教師あり学習 • 教師なし学習 • 強化学習 強化学習は教師あり学習でも教師なし学習でもありません 11
12. 強化学習とは（２） • 教師あり学習 ◦ 教師データを元に学習を行う • 教師なし学習 ◦ 入力データ群に対して隠れたデータ構造を発見する • 強化学習 ◦ 環境とインタラクションしつつ報酬を最大化する行動を獲得する 12
13. 強化学習とは（３） エージェントが環境とインタラクションしつつ 環境から受け取る報酬の和を最大化する行動を獲得する手法 13
14. 強化学習の特徴 知識と探索を駆使して報酬を最大化する行動を獲得する手法 • 知識の利用 過去の経験で得られた知識を利用して報酬を最大化する • 探索 今まで見たことのない、より高い報酬を探し求める このバランスを取るのが大事 14
15. 無人島の例に戻ると エージェント: 人間 環境: 無人島 報酬: 行動が生存につながった度合い 行動: 無人島で人間がする行動 目標: より長く生存すること 報酬の総和を最大化すること 15
16. 無人島の例での戦略 • 戦略1: 綺麗な水や食べ物を探しに歩きまわる リスクはあるが、もし発見できれば今後そこを利用して長く生存できる可能性 探索と知識の利用をうまくすれば収益を最大化できそう その代わり、知識の利用をせずに探索すると収益が低くなるかも • 戦略2: 歩いたら疲れるし、悪い水を飲んだら危ないので浜辺でじっとする リスクはないのでアクシデントで死ぬことはないが、このままだと死ぬ 探索が足りておらず、局所解に陥ってしまった 16
17. Webにおいてどういう場合に使える？ • 教師データがないような場合にパラメータを探索したい 検索のスコアリングの重み付けの最適化 • UIの出し方を最適化しつつ変更したい クリック率などを報酬に設定してUIを最適化 • インフラの最適化などをオンラインで学習しつつやる 料金と応答時間のバランスを最適化 17
18. 少し詳しく見る 18
19. 用語を覚えよう 状態 エージェントのいる環境の様子 s t : tでの環境の様子 19
20. 用語を覚えよう 行動 エージェントが環境に働きかける行動 a t : tでの行動 20 ファイヤー！
21. 用語を覚えよう 報酬 環境からエージェントへ与えられる評価 r t : tでの環境からの評価 21
22. 用語を覚えよう 方策 エージェントの行動パターン π(s, a): 状態sで行動aを取る確率として表すことが多い 22 ここをジャンプだ！
23. 用語を覚えよう 収益 報酬の和。割引率γを導入してどのくらいのスパンでの収益かを調整する R t = r t + γr t+1 + γ2r t+2 + γ3r t+3 + …. 23
24. マルコフ性 次の状態が今の状態と行動にしか依らない Pr {s t+1 = s’, r t+1 = r | s t , a t } 強化学習では環境がマルコフ性をもつとする 24
25. 状態価値関数 状態に対する価値（収益）を返す関数 真の価値関数を求めるのが目標！！ 収益 25
26. 簡単な方策の例 状態価値関数をすでに持ってるなら 常に一番大きな価値を持つ状態に移動するように行動 s s 1 s 2 s 3 V(s 1 ) = 0.1 V(s 2 ) = 0.2 V(s 3 ) = 0.1 囲碁とかチェスはこれで行動選択できる 26
27. 遅れて発生する報酬 インベーダーゲームだと、撃ってからしばらくしてスコアが貰える 打った瞬間の状態にも価値を与える必要がある 27
28. Belleman方程式（１） ある状態の報酬と後続の状態群の報酬の関係を表した式 即時報酬 未来の割引報酬 28
29. Belleman方程式（２） 次の状態の価値との関係を表せる 次の状態の価値 29 即時報酬
30. TD学習（１） 状態価値関数をオンラインで更新する手法 各ステップで上を計算することで 報酬を前の状態に伝搬させる 目標 今の値 30
31. TD学習（２） V(s t+3 )=0, V(s t+2 )=0, V(s t+1 )=0, V(s t )=0, a = 1, γ=0.9 s t+2 s t+1 s t r t+3 =1 r t+2 =0 r t+1 =0 V(s t+2 ) = 0 + {1 + 0 - 0} V(s t+1 ) = 0+ {0 + 0 - 0} V(s t ) = 0 + {0 + 0 - 0} iteration1 例としていつも同じ状態遷移をするとする 31
32. TD学習（３） V(s t+3 )=0, V(s t+2 )=1, V(s t+1 )=0, V(s t )=0, a = 1, γ=0.9 s t+2 s t+1 s t r t+3 =1 r t+2 =0 r t+1 =0 V(s t+2 ) = 1 + {1 + 0 - 1} V(s t+1 ) = 0 + {0 + 0.9 - 0} V(s t ) = 0 + {0 + 0 - 0} iteration2 32
33. TD学習（４） V(s t+3 )=0, V(s t+2 )=1, V(s t+1 )=0.9, V(s t )=0, a = 1, γ=0.9 s t+2 s t+1 s t r t+3 =1 r t+2 =0 r t+1 =0 V(s t+2 ) = 1 + {1 + 0 - 1} V(s t+1 ) = 0.9 + {0 + 0.9 - 0.9} V(s t ) = 0 + {0 + 0.81 - 0} iteration3 33
34. 状態価値関数の不便なところ 状態価値関数は次の状態がわからないと使えなくない？ s s ? s ? s ? 状態価値関数に入れる状態がわからない 34
35. 行動価値関数 状態と行動に対する価値（収益）を返す関数 状態価値関数との関係 35
36. 行動価値関数の簡単な方策の例 行動価値関数をすでに持ってるなら 常に一番大きな行動価値を持つ行動を選択 s Q(s, a 1 ) = 0.1 Q(s, a 2 ) = 0.2 Q(s, a 3 ) = 0.1 これなら次の状態を考えなくて良い（マルコフ性のおかげ） 36
37. 行動価値関数の後続の状態との関係 次の状態の最大のQ値 37
38. Q学習 TD学習と同様にオンラインで行動価値関数を更新する 一番簡単なQ関数の表し方はテーブル 状態/行動 行動1 行動2 状態1 ... ... 状態2 ... ... 目標 今の値 38
39. 探索について 今持っている方策にいつも従うと経験できない状態がある ここを如何にうまくやるかが大事！！ 39
40. 行動の選択方法 • greedy選択 常に現在の学習状態で最高の選択を行う • ε-greedy選択 確率εでランダムに行動を選択する • ボルツマン行動選択 各行動のQ値に対してsoftmax関数を適応した確率分布で選択 40
41. DQNを知る 41
42. DQNとは ヤンキー（不良）もしくは、軽率そうな者や実際にそうである者、粗暴そうな風貌をしてい る者や実際に粗暴な者、また、非常識で知識や知能が乏しい者を指すときに用いられる 1994年から2002年までテレビ朝日で放送されていた番組『目撃!ドキュン』が由来とされ る。目撃ドキュンの内容は、離婚などで生き別れの親子が対面などというものであった。 そのため、ヤンキーのことを、「15歳で結婚して子供が生まれて、20歳になったら離婚し て、40歳になったら目撃ドキュンにでている人たち」という意味でDQNと2ちゃんねるを 中心に呼ぶようになった。 https://ja.wikipedia.org/wiki/DQN 42
43. DQN (Deep Q-Network)とは Deep Mind より発表された深層強化学習の手法 Atariのゲームで高得点が取れるようになった 43 Volodymyr Mnih and Koray Kavukcuoglu and David Silver and Alex Graves and Ioannis Antonoglou and Daan Wierstra and Martin Riedmiller,Playing Atari With Deep Reinforcement Learning, 2013 Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis, Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, Demis Hassabis, Human-level control through deep reinforcement learning, 2015
44. DQNの成果 from NIPS 44
45. DQNの成果 from Nature Atari 2600[1] のゲームで人間よりも高いスコアが取れるようになった [1] The Arcade Learning Environment: An Evaluation Platform for General Agents, 2013, Bellemare, Naddaf, Veness, Bowling 45
46. Atari 2600 での設定 環境: ゲーム エージェント: 自機 状態: ゲーム画像 行動: ゲームの操作 報酬: ゲームのスコア 46
47. 今まで何が難しかった？ 状態は84x84の白黒画像 テーブルでQ関数を表すのは無理 線形関数近似でも画像を扱うのは難しい 25684x84通りの状態 47
48. CNNによる画像の扱い CNNを用いたImageNetがILSVRC2012（画像認識コンテスト）で優勝 Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton, ImageNet Classification with Deep Convolutional Neural Networks, 2012 48
49. CNNによる畳み込み計算 画像に対して畳み込み計算を行うことで空間的な情報も含めて特 徴抽出することができる https://deepage.net/deep_learning/2016/11/07/convolutional_neural_network.html 49
50. DQNでどこがディープになったのか Q関数をCNNを使ったDNNで近似 ゲーム画像をそのまま学習に使えるようになった sにゲーム画像をそのまま使える！ DEEP!! 50
51. ニューラルネットワークの構成 CNN FC FC 各 行 動 の Q 値 84x84の白黒ゲーム画像 CNN CNN 51
52. 探索 行動選択はε-greedy法 100万ステップかけてεが線形に 100% →10% まで下がり、このまま一定 52
53. DQNの工夫 実はDQNはQ関数をディープにしただけではない • Experience Replay • Freezing the target network • Clipping rewards • Skipping frames 色々工夫してようやくスコアが上がった！ 53
54. Experience Replay オンラインでそのまま学習すると DNNは現在の経験に対して過学習してしまう 昔経験したことをランダムに選んで学習に使う 繰り返し学習することで昔のことを忘れない！ Reinforcement Learning for Robots Using Neural Network, 1993, Lin 経験1 経験2 経験3 経験4 Replay Memory 学習 54
55. Experience Replay の他の効果 • TD誤差を伝搬させるのに時間がかかる バッチ処理で過去の経験を学習させることで加速！ • いい経験を一回しか使わないのは勿体無い 過去の経験を使いまわそう！ ここを改良するとかなりの性能向上につながる！ 55
56. Freezing the target network 誤差計算を行うときの目標のネットワークに古いものを使用 目標値が安定しないと収束できない 一定周期で現在のネットワークと同期する ここだけ 56
57. Clipping rewards ゲームによってスコアの大きさが違う 例 • Pongだったら一回点を取ると1点もらえる • Space Invadorsだったら倒したインベーダの場所に応じて10~30点 いろんなゲームに対応するために、 • 負のスコアは-1 • 正のスコアは+1 で統一する 57
58. Skipping frames 4フレームごとに前の4フレームを使って行動選択を行う 4フレーム後まで同じ行動を繰り返し選択する 計算コストが減るのでより多くの経験を積むことができる Atari 2600 の制限で描けるオブジェクトの数が決まっていて ビームが消えたりするので Space Invaders では3フレーム 58
59. DQNで遊んでみる お待たせしました！！ 59
60. 実行環境 Python3系 以下をpipでインストール • chainer==2.0.0 • chainerrl==0.2.0 • gym[atari] • opencv-python（OpenCV3は別の方法でもOK） 60
61. DQNで遊んでみよう 申し訳ありません 今学習しても全く成長しません... あらかじめ学習済のモデルを複数用意しました 61
62. まずは動かしてみよう 以下をcloneして https://github.com/takuseno/dqn-sokushukai 以下から任意のステップまで学習したモデルを落とす https://goo.gl/MN8676 breakout/30000000を上からダウンロードして実行する例 python play.py --gpu -1 --load 30000000 --env Breakout-v0 --render 62
63. 学習させたゲーム 63 Breakout-v0 Pong-v0 SpaceInvaders-v0 MontezumaRevenge-v0
64. コード dqn.pyのベースになっているコードはPFNのchainerrl https://github.com/chainer/chainerrl ライブラリというよりは実装集な感じ（個人の感想） 64
65. chainerrl いろんな手法が実装されているのでとても参考になります （結構論文にハイパーパラメータがないことが多い） 今回のdqn.pyはここから説明していない箇所を削りました 65
66. 見るべき実装 _compute_loss関数が の誤差計算を行なっている箇所 66
67. MontezumaRevenge やってみた人は気づいたと思いますが 全く学習ができません 67
68. 報酬がスパースな環境への対策の例 個人的に感動した UC Berkeley から出てた新しい論文 報酬なしでマリオをプレイできるようにした https://www.youtube.com/watch?v=J3FHOyhUn3A Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, Trevor Darrell, Curiosity-driven Exploration by Self-supervised Prediction, 2017 68
69. 報酬がスパースな環境への対策の例 見たことない状態へ移動すると追加で報酬を与える 好奇心 69 Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, Trevor Darrell, Curiosity-driven Exploration by Self-supervised Prediction, 2017
70. 家で別のゲームを学習する 頑張って以下を実行してください CPUだとめちゃくちゃ時間かかります... python train.py --gpu -1 --env {environment} GPUある場合はgpuオプションなしで実行 以下でゲーム一覧を確認できます https://gym.openai.com/envs#atari 70
71. もっと強化学習やってみたい人へ 今日やった内容はDQNのためにかいつまんで説明しました 本格的に勉強してみたい人には以下の本がおすすめです Richard S. Sutton Andrew G.Barto 強化学習 71