Reinforcement Learning and Game Theory

study seminar @ deeplab
https://deeplab-team.github.io/

Transcript

1. 強化学習とゲーム理論 (MARL) Reinforcement Learning x Game Theory 東京工業大学 経営工学系 清原 明加 Haruka Kiyohara 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 1
2. 目次 • 強化学習とは？ • ゲーム理論について • マルチエージェント強化学習 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 2
3. 強化学習とは？ 教師あり学習/教師無し学習/強化学習 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 3 machine learning reinforcement supervised unsupervised Cartpole Atari breakout 碁(Go)
4. 強化学習とは？ 歴史的には，動物の餌付け が起源とされる ボタンを踏むと確率的に餌 が落ちてくる ⇒鶏はせかせかとボタンを 踏み続けるように 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 4 https://www.reddit.com/r/aww/comments/f 1akqn/parrots_playing_basketball/
5. 強化学習とは？ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 5 状態ｓ 報酬ｒ 行動 a エージェント 環境 将来的に得られる報酬を最大化するよう，エージェント が行動価値/行動方策を学習し，最適化する．
6. 強化学習とは？-前提- • エージェントが，環境のなかで得られる報酬を最大化 する最適化問題． • ただし，報酬を得るためにどうしたらよいかというの は非自明な場合が多く，また，報酬のみではスパース で扱いにくいので，途中の過程ででてくる状態や， エージェントの行動に価値を付与し，その価値を最大 化する問題に置き換える． • 状態や行動の価値に関しても一概に決まるものではな いため，まずは価値を推測するところから始め，推測 した価値の最大化までをひとまとめで行うことを目標 とする． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 6
7. 強化学習とは？-方策ベース・価値ベース- • 方策ベース 状態価値Vを推測し，以降の状態価値の現在割引和を 最大化する方策π(s,a)を決定 • 価値ベース エージェントの行動価値Qを推測し，以降の行動価値 の現在割引和を最大化する行動aを決定 • モデルベース 環境が分かっているという仮定のもと，価値最大化を プランニング 現在割引和..同じ報酬が得られるならなるべく早く得られる方が良い，という考え方． 数学的には，割り引くことで和を発散させたくない，という意味も． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 7
8. 強化学習とは？-最適化問題の解き方- • 動的計画法 選択肢をひとつづつ増やしていき，逐次的に最適化 問題を解いていく方法で，厳密的な解法． • モンテカルロ法 方策ベースなどで用いられ，ロールアウトによって 疑似体験的にいくつかの選択肢を比較し，方策を選択． • TD法 価値ベースなどで用いられ，tステップ先の行動価値 まで考えた上での行動選択の最適化を行う． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 8
9. 強化学習とは？-探索と活用- • 探索 現時点で持っている知識では最適とは限らない方策を 選択し，周辺の環境や行動価値を学習する． • 活用 探索で得られた情報を基に，考えられる内で最適な 行動(方策)を選択する． 上記の探索と活用にはトレードオフが存在 ⇒学習初期には探索を重視し，後半では活用を重視． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 9 活用 探索 exploration exploitation
10. 強化学習とは？-観測範囲と報酬- • Fully Observable エージェントがすべての環境や状態を観測できる場合． • Partially Observable エージェントが環境や状態を部分的にしか観測できな い場合．例えば，一人称視点など． • Sparse Reward 報酬が一番最後だけなど，連続的に得られない場合． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 10
11. 強化学習とは？-最近のトレンド- • 2014年頃から再び波が来ている．(ex. AlphaGo) • 強化学習の価値関数の推論に深層学習を組み込んだ， 深層強化学習で適応可能性が広がる． • 分散学習による効率的かつ精度の高い学習． • 一人称視点など，環境を部分的にしか観測できない エージェントの行動(方策)最適化の研究． • 環境に複数のエージェントが存在するマルチエージェ ント環境での挙動の研究． • 近年，実応用がますます注目される． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 11
12. 強化学習とは？-マルチエージェント化と最適- 最適化の3つの視点とトレードオフ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 12 自律分散型最適化 個別最適化 全体最適化 全体での利益が最大に なるよう設計． 格差が存在することも． 全体/個別での利益が両方 ともそこそこ大きい． バランス型と言える． 各個人が自分の利益を 最大化するよう行動． 過剰競争などが発生．
13. ゲーム理論について-概要- • ゲーム理論の定義 (from Wikipedia) 社会や自然界における複数主体が関わる意思決定の 問題や行動の相互依存的状況を数学的なモデルを用 いて研究する学問である． • 起源 1944年「ゲームの理論と経済活動」 著者：数学者 ジョン・フォン・ノイマン 経済学者 オスカー・モルゲンシュテルン 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 13
14. ゲーム理論について-協力/非協力- • 非協力ゲーム理論 戦略的ゲームの参加者が互いにコミュニケーションを 取れない状況で，それぞれが自分の利益を最大化する 行動をとる．戦略形ゲームと展開ゲーム． • 協力ゲーム理論 プレーヤー間の連携が可能で，連携を含めた戦略を各 参加者が検討し，自分の利益を最大化する行動をとる． 一般的に，コミュニケーションや事前協議が可能． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 14
15. ゲーム理論について-対称/非対称- • 対称ゲーム 全てのプレーヤーが同じ状況下で同じ選択肢のもとで 行動選択を行う場合．厳密な意味での対称ゲームは社 会にはあまり存在しないが，問題の簡略化として． • 非対称ゲーム プレーヤー毎に置かれた状況や選考，選択肢が異なる 場合を考えたゲーム．特に，相手の状況が部分的にし か把握できない場合，不完全情報ゲームと呼ばれる． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 15
16. ゲーム理論について-完全/不完全- • 完全情報ゲーム ゲームへの参加者が，他者のことも含めて全ての情報 を知っているという仮定が置かれている． • 不完全情報ゲーム ある人のみが知っている情報など，情報の非対称性が 生じるゲーム．実社会での状況は不完全情報ゲームに 該当するが，この時意思決定者は既に知っている情報 を基に，知らない情報に対する信念を形成する． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 16
17. ゲーム理論について-囚人のジレンマ- 対称ゲームにおいて，最適は実現されない 2人の共犯の強盗がいたとします．2人とも黙秘であれば物証が得られていないので， 2人は1年の懲役，2人とも自供すれば，立証により2人は3年の懲役を受けます．ただ し，警察は自供させたいので，片方が自供し，もう片方が自供しなかった場合，自 供した方は懲役0年，しなかった方は懲役5年とすることにしました．2人は別々に尋 問を受けていますが，あなたが強盗だとしたら自供するでしょうか？・・ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 17 囚人A / 囚人B 自供 黙秘 自供 (-3,-3) (0,-5) 黙秘 (-5,0) (-1,-1)
18. ゲーム理論について-非対称のジレンマ- 非対称ゲームにおける意思決定は悩ましい Aさん(彼)とBさん(彼女)は付き合っています．2人は週末デートに行くことになってい て，カラオケか映画館のどちらかに行く予定で，10時に入口で待ち合わせをしまし た．ところが困ったことに，2人はカラオケか映画館のどちらにするか決め忘れてい たことに家を出てから気づきました．スマホは持っていません．2人は，落ち合えな ければ最悪の気持ちですが，もし落ち合えるならば，彼の方はどちらかというとカ ラオケに，彼女の方はどちらかというと映画館にいきたいと思っており，お互いに そのことは分かっています．さあ，あなたが彼/彼女ならどちらへいきますか？・・ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 18 彼A / 彼女B カラオケ 映画館 カラオケ (3,2) (0,0) 映画館 (0,0) (2,3)
19. ゲーム理論について-共有地の悲劇- 個別最適と全体最適は一致しない 村全体で飼うなら3頭が適切な(利益が最大となる)牛の放牧．しかし，村の農家一人 ひとりが自分自身の利益を最大化しようとすると，3人の農家は一人2頭牛を飼い始 め，村全体では計6頭になってしまいました．・・ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 19 too much 6cow/village appropriate 3cow/village
20. ゲーム理論について-ジレンマの回避- 互いの意思を確認できる場合と，できない場合． あなたの意思決定は変わりますか？ A国では国民10人全員に，ひとりあたり10万円が与えられることになりました．10万 円は国民それぞれのものですので，どんな使い方をするかは国民の自由です．今， 国が投資のための資金を国民から集めることにしました．この投資は成功が保障さ れていて，国民から集まったお金の3倍を税金として10人に均等に再分配することが できます．あなたはいくら国に投資資金として渡すでしょうか？また，その決断は 他の住民と話し合いの上行う場合と，自分一人で行う場合，変わりますか？・・ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 20 協力する 出し抜く 話し合い あり？なし？
21. マルチエージェント強化学習 Multi-Agent Reinforcement Learning (MARL) 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 21
22. 問題提起 • ゲーム的状況において，個別学習させた エージェントは周囲との協調を考えた行動 を選択できるのか？ • つまり，自律分散型最適化をマルチエー ジェント環境において学習させることはで きるのか？ • 人間の行うコミュニケーションの代わりと なるものを，どのように観測環境や情報と して組み込めるか？ また，コミュニケーションなく協調は可能 なのか？ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 22
23. 場面設定 • 協力 エージェント同士が協力して行動しなければ良い報酬 が得られない，全体での報酬を大きくしたい場合． • 敵対 zero-sumゲームなどの，一方が得をすれば他方が損を する状況で敵対的にエージェントを学習させたい場合． • 影響 必ずしもエージェント間で協力して何かを達成したい 訳ではないが，他のエージェントの行動も考慮に入れ た上で最適化をしなければならない場合． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 23
24. 以下での参考文献 • A Review of Cooperative Multi-Agent Deep Reinforcement Learning, Oroojlooyjadid, Afshin, and Davood Hajinezhad , 2019 https://arxiv.org/abs/1908.03963 • Paper Collection of Multi-Agent Reinforcement Learning (MARL), https://github.com/LantaoYu/MARL-Papers と，上記紹介論文のAbstractをいくつか． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 24
25. 主要課題 • MDPが達成されない⇒定常性がない，収束性に問題． (つまり，経験再生が利用しづらい) • 情報共有を規定すると，情報過多になり次元の呪いが 問題に． • どうやって協力することをを学ばせるか． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 25
26. 研究分野 • Framework • Joint Action Learning • Cooperation and Competition • Coordination • Security • Self-Play • Learning to Communicate • Transfer Learning • Imitation and Inverse Reinforcement Learning • Meta Learning • Application 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 26
27. 研究分野の概観-Framework/Joint Action- • Framework あるシチュエーションを仮定して，どのような枠組み の中で収束性を担保できるかなど，アルゴリズムの話． • Joint Action Learning エージェントが同時に意思決定するシチュエーション を考えて，マルコフ性など収束性に関する問題への考 察を行う． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 27
28. 研究分野の概観-3C- • Cooperation and Competition マルチエージェント環境において，エージェント同士 に協力したり，競い合ったりする状況での方策や行動 の最適化を学習させる． • Coordination 上記Cooperationタスクにおいて，同じタイミングで エージェントがそれぞれ適切な行動を起こさないとい けない状況設定において，探索の困難性などについて 議論する． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 28
29. 研究分野の概観-Security/Self-Play- • Security サイバーセキュリティの状況設定において，attacker とdefenderの間のzero-sumゲームを考えている．ここ で，defender側をマルチエージェントにして，パト ロールの最適化をしたいらしい． • Self-Play AlphaGoなど，正解を人間が知らない∧ゲームなどの 閉じた設定∧対戦相手が明確な場合に，エージェント 同士を戦わせて，自己対戦によって最適方策(行動)を 学習していく． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 29
30. 研究分野の概観-Communicate/Transfer- • Learn to Communicate(詳しくは次ページ) マルチエージェントの特にCooperativeな場面において， 情報共有や意思伝達の機能をエージェントに学習させ る．個人的には，Competitiveな状況でCommunication によって駆け引きが学習できると面白そうと思うけど， 収束性に問題があるのかあまり研究されていなさそう． • Transfer Learning 他のエージェントが異なる/同じ状況で学習した記録 を，別のエージェントの学習に転用できないだろう か？という発想．学習効率の向上について議論． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 30
31. 意思疎通・情報共有の設定 • Consensus 予め人間の手によって共有する情報と範囲を決めてお き(その意味で”合意”という)，共有された情報と自分 の見れる範囲の観測を基にエージェントは意思決定す る．また，全体最適の場合エージェント間の重みにつ いても取り決められていたりする． • Communication エージェントに，”いつ” ”誰と” ”どのようにして”情報 を共有したり，シグナルを発信したりするのかまでも 学習・決定させる．ここで送られるメッセージはあく まで環境を変化させないものと仮定されている． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 31
32. 研究分野の概観-Imitation/Inverse/Meta- • Imitation and Inverse Reinforcement Learning 通常は報酬を最大化するようエージェントが最適方策 (行動)を学習するが，対して，最適な方策(行動)を天下 り的に与えて，そこから報酬の推定を行う，という意 味で逆強化学習．状態数が多く探索が困難な場合に， 優秀な人間のデータを最適方策として与えることも． • Meta Learning 学習の仕方を学習する．マルチエージェントの Competitiveな状況において，メタ学習を使って変化し ていく状況に対応し，収束性課題に取り組むなど． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 32
33. 研究分野の概観-Application- • multiple traffic signals 交通量を最大化するように，信号機の切り替えを都市 全体で調整． • bike rebalancing 貸し自転車の店舗間移送を効率化する． • distributed resource allocation 流通システムにおいて在庫を抱えないよう資源を分配． • liquidation of stock 株の流動性の予測やポートフォリオ最適化など． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 33
34. モデル選択の自由度 • 使用するモデル 方策ベース？価値ベース？ • 観測範囲 state, action, rewardについて， 各々local, neighbor, globalのどの範囲で観察できるか？ • ConsensusとCommunication どの範囲での情報共有を設定するか？ • 階層(ヒエラルキー) 中央集権的に行うか？どこまで自主性に任せるか？ • その他 RNN, GNN, Attention, Importance Sampling, Distributed, etc. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 34
35. 補足-観測範囲について- 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 35 Fully Observable (すべてのエージェントが) すべての状態や報酬を観測できる． Partially Observable 各エージェントは，自分の周りの近くの 状態や報酬のみ観測できる． 観測の共有をConsensusで決定． ・観測を全エージェント間で共有 ・観測を近傍のエージェントや，サブグ ループ内でのみ共有 ・エージェント間の共有は行わない Share? or not? globally locally individually
36. 補足-階層について- 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 36 Centralized Decentralized 中央集権型 エージェントを統括して 全体を見る仮想エージェ ントがいるイメージ． サブグループ型のさらに 上のエージェントなども． サブグループ型 近傍のエージェントとな どサブグループを生成し， その中を統括するリーダ ーエージェントが存在し ているイメージ． 自律分散型 各エージェントが個別に 意思決定を行い，全体を 統括するエージェントが 存在しないイメージ．
37. 補足-その他(1)- • RNN.. 価値の推定に，自身の時系列の過去経験から内部状態 を保持・使用する．LSTM, GRUなど． • GNN.. エージェントをノード，エージェント間の関係をエッ ジとみるとグラフとして全体を把握できる． • Attention.. 全体でのpolicy, Qの決定を行う際に，各エージェント の持つ予測モデルの重みづけができる． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 37
38. 補足-その他(2)- • Importance Sampling.. 重みづけをした場合など，重みに応じてSampling Rate を変えることで，優先付けしてサンプリングできる． • Distributed Learning.. あるエージェントで学習した結果を他のエージェント でも活用できるようにすることで，分散的に学習を行 うことができ，学習効率が向上する．ただし，基本的 に他のエージェントの行動を観測できないようにして いる場合などは，経験をどこまで他のエージェントが 活用できるようにするかは議論がある． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 38
39. ホットトピック • Off-policy MARL 他のエージェントも含めた状況で，行動方策から最適 な方策を学習する． • Safe MARL 長期的利益を最大化しつつ，決定的な打撃をさけるた めのリスク回避を行いたい． • Heterogeneous MARL 一様なエージェントではなく，技能などに個性を持っ たエージェントでの最適化． • Optimization in MARL マルチエージェント環境での最適化問題を解く数学． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 39
40. 問題提起(再掲) • ゲーム的状況において，個別学習させた エージェントは周囲との協調を考えた行動 を選択できるのか？⇒できる • つまり，自律分散型最適化をマルチエー ジェント環境において学習させることはで きるのか？⇒できそう • 人間の行うコミュニケーションの代わりと なるものを，どのように観測環境や情報と して組み込めるか？ また，コミュニケーションなく協調は可能 なのか？ ⇒ConsensusとCommunicationを導入できる 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 40
41. まとめ • MARLはゲーム理論的な課題に対し，Communicationの 導入などにより解決できそうだった． • ただし，MARLでは収束性や学習の安定性が課題となる ので，工夫が必要そうだった． • これからのMARLは，適用範囲を増やしていくことや， 一人一人違う個性を持ったエージェントにおける最適 化などがおもしろそうだった． 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 41
42. Appendix. 強化学習ライブラリ • OpenAI Gym Atariゲームなど，強化学習の一般的なタスクについて 実装されているライブラリ． https://gym.openai.com/ • OpenSpiel バックギャモンや囲碁など，幅広く対戦型のゲームの タスクについて実装されているライブラリ． https://deepmind.com/research/open-source/openspiel • Arena 多くのMARLの実行環境を備え，MARLのベースライン タスクを作ろうというモチベでつくられたライブラリ． https://sites.google.com/view/arena-unity/ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 42