Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Reinforcement Learning and Game Theory
Search
Haruka Kiyohara
May 17, 2020
Research
2
830
Reinforcement Learning and Game Theory
study seminar @ deeplab
https://deeplab-team.github.io/
Haruka Kiyohara
May 17, 2020
Tweet
Share
More Decks by Haruka Kiyohara
See All by Haruka Kiyohara
Off-Policy Evaluation of Slate Bandit Policies via Optimizing Abstraction(日本語版)
aiueola
0
200
Towards Assessing and Benchmarking Risk-Return Tradeoff of OPE (日本語版)
aiueola
0
250
SCOPE-RL: オフライン強化学習とオフ方策評価のライブラリ
aiueola
0
270
Off-Policy Evaluation of Ranking Policies under Diverse User Behavior (日本語版)
aiueola
0
510
Off-Policy Evaluation of Ranking Policies under Diverse User Behavior
aiueola
1
270
海外大学院留学説明会@東工大 2023夏 事前共有資料
aiueola
1
3.1k
Policy-Adaptive Estimator Selection for Off-Policy Evaluation
aiueola
0
920
OFRL: Designing an Offline Reinforcement Learning and Policy Evaluation Platform from Practical Perspectives
aiueola
0
620
Doubly Robust Off-Policy Evaluation for Ranking Policies under the Cascade Behavior Model
aiueola
2
480
Other Decks in Research
See All in Research
データサイエンティストをめぐる環境の違い 2024年版〈一般ビジネスパーソン調査の国際比較〉
datascientistsociety
PRO
0
180
marukotenant01/tenant-20240826
marketing2024
0
500
CVPR2024論文紹介:Segmentation
hinako0123
0
130
「人間にAIはどのように辿り着けばよいのか?ー 系統的汎化からの第一歩 ー」@第22回 Language and Robotics研究会
maguro27
0
540
Language is primarily a tool for communication rather than thought
ryou0634
4
670
Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve
eumesy
PRO
6
1.1k
SSII2024 [OS1] 画像認識におけるモデル・データの共進化
ssii
PRO
0
490
LINEチャットボット「全力肯定彼氏くん(LuC4)」の 1年を振り返る
o_ob
0
1.8k
SSII2024 [OS1] 研究紹介100連発(オープンニング)
ssii
PRO
0
480
LLM時代の半導体・集積回路
kentaroy47
1
420
文献紹介:A Multidimensional Framework for Evaluating Lexical Semantic Change with Social Science Applications
a1da4
1
190
SSII2024 [OS2] 大規模言語モデルとVision & Languageのこれから
ssii
PRO
5
1.4k
Featured
See All Featured
Imperfection Machines: The Place of Print at Facebook
scottboms
264
13k
BBQ
matthewcrist
85
9.2k
Code Review Best Practice
trishagee
62
16k
The Brand Is Dead. Long Live the Brand.
mthomps
53
38k
Designing on Purpose - Digital PM Summit 2013
jponch
114
6.9k
Designing with Data
zakiwarfel
98
5.1k
Building an army of robots
kneath
302
42k
Product Roadmaps are Hard
iamctodd
PRO
48
10k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
37
1.7k
The World Runs on Bad Software
bkeepers
PRO
65
11k
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
327
21k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
167
48k
Transcript
強化学習とゲーム理論 (MARL) Reinforcement Learning x Game Theory 東京工業大学 経営工学系 清原
明加 Haruka Kiyohara 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 1
目次 • 強化学習とは? • ゲーム理論について • マルチエージェント強化学習 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原
明加 2
強化学習とは? 教師あり学習/教師無し学習/強化学習 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 3 machine learning reinforcement
supervised unsupervised Cartpole Atari breakout 碁(Go)
強化学習とは? 歴史的には,動物の餌付け が起源とされる ボタンを踏むと確率的に餌 が落ちてくる ⇒鶏はせかせかとボタンを 踏み続けるように 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原
明加 4 https://www.reddit.com/r/aww/comments/f 1akqn/parrots_playing_basketball/
強化学習とは? 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 5 状態s 報酬r 行動 a
エージェント 環境 将来的に得られる報酬を最大化するよう,エージェント が行動価値/行動方策を学習し,最適化する.
強化学習とは?-前提- • エージェントが,環境のなかで得られる報酬を最大化 する最適化問題. • ただし,報酬を得るためにどうしたらよいかというの は非自明な場合が多く,また,報酬のみではスパース で扱いにくいので,途中の過程ででてくる状態や, エージェントの行動に価値を付与し,その価値を最大 化する問題に置き換える.
• 状態や行動の価値に関しても一概に決まるものではな いため,まずは価値を推測するところから始め,推測 した価値の最大化までをひとまとめで行うことを目標 とする. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 6
強化学習とは?-方策ベース・価値ベース- • 方策ベース 状態価値Vを推測し,以降の状態価値の現在割引和を 最大化する方策π(s,a)を決定 • 価値ベース エージェントの行動価値Qを推測し,以降の行動価値 の現在割引和を最大化する行動aを決定 •
モデルベース 環境が分かっているという仮定のもと,価値最大化を プランニング 現在割引和..同じ報酬が得られるならなるべく早く得られる方が良い,という考え方. 数学的には,割り引くことで和を発散させたくない,という意味も. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 7
強化学習とは?-最適化問題の解き方- • 動的計画法 選択肢をひとつづつ増やしていき,逐次的に最適化 問題を解いていく方法で,厳密的な解法. • モンテカルロ法 方策ベースなどで用いられ,ロールアウトによって 疑似体験的にいくつかの選択肢を比較し,方策を選択. •
TD法 価値ベースなどで用いられ,tステップ先の行動価値 まで考えた上での行動選択の最適化を行う. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 8
強化学習とは?-探索と活用- • 探索 現時点で持っている知識では最適とは限らない方策を 選択し,周辺の環境や行動価値を学習する. • 活用 探索で得られた情報を基に,考えられる内で最適な 行動(方策)を選択する. 上記の探索と活用にはトレードオフが存在
⇒学習初期には探索を重視し,後半では活用を重視. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 9 活用 探索 exploration exploitation
強化学習とは?-観測範囲と報酬- • Fully Observable エージェントがすべての環境や状態を観測できる場合. • Partially Observable エージェントが環境や状態を部分的にしか観測できな い場合.例えば,一人称視点など.
• Sparse Reward 報酬が一番最後だけなど,連続的に得られない場合. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 10
強化学習とは?-最近のトレンド- • 2014年頃から再び波が来ている.(ex. AlphaGo) • 強化学習の価値関数の推論に深層学習を組み込んだ, 深層強化学習で適応可能性が広がる. • 分散学習による効率的かつ精度の高い学習. •
一人称視点など,環境を部分的にしか観測できない エージェントの行動(方策)最適化の研究. • 環境に複数のエージェントが存在するマルチエージェ ント環境での挙動の研究. • 近年,実応用がますます注目される. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 11
強化学習とは?-マルチエージェント化と最適- 最適化の3つの視点とトレードオフ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 12 自律分散型最適化 個別最適化 全体最適化
全体での利益が最大に なるよう設計. 格差が存在することも. 全体/個別での利益が両方 ともそこそこ大きい. バランス型と言える. 各個人が自分の利益を 最大化するよう行動. 過剰競争などが発生.
ゲーム理論について-概要- • ゲーム理論の定義 (from Wikipedia) 社会や自然界における複数主体が関わる意思決定の 問題や行動の相互依存的状況を数学的なモデルを用 いて研究する学問である. • 起源
1944年「ゲームの理論と経済活動」 著者:数学者 ジョン・フォン・ノイマン 経済学者 オスカー・モルゲンシュテルン 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 13
ゲーム理論について-協力/非協力- • 非協力ゲーム理論 戦略的ゲームの参加者が互いにコミュニケーションを 取れない状況で,それぞれが自分の利益を最大化する 行動をとる.戦略形ゲームと展開ゲーム. • 協力ゲーム理論 プレーヤー間の連携が可能で,連携を含めた戦略を各 参加者が検討し,自分の利益を最大化する行動をとる.
一般的に,コミュニケーションや事前協議が可能. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 14
ゲーム理論について-対称/非対称- • 対称ゲーム 全てのプレーヤーが同じ状況下で同じ選択肢のもとで 行動選択を行う場合.厳密な意味での対称ゲームは社 会にはあまり存在しないが,問題の簡略化として. • 非対称ゲーム プレーヤー毎に置かれた状況や選考,選択肢が異なる 場合を考えたゲーム.特に,相手の状況が部分的にし
か把握できない場合,不完全情報ゲームと呼ばれる. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 15
ゲーム理論について-完全/不完全- • 完全情報ゲーム ゲームへの参加者が,他者のことも含めて全ての情報 を知っているという仮定が置かれている. • 不完全情報ゲーム ある人のみが知っている情報など,情報の非対称性が 生じるゲーム.実社会での状況は不完全情報ゲームに 該当するが,この時意思決定者は既に知っている情報
を基に,知らない情報に対する信念を形成する. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 16
ゲーム理論について-囚人のジレンマ- 対称ゲームにおいて,最適は実現されない 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)
ゲーム理論について-非対称のジレンマ- 非対称ゲームにおける意思決定は悩ましい Aさん(彼)とBさん(彼女)は付き合っています.2人は週末デートに行くことになってい て,カラオケか映画館のどちらかに行く予定で,10時に入口で待ち合わせをしまし た.ところが困ったことに,2人はカラオケか映画館のどちらにするか決め忘れてい たことに家を出てから気づきました.スマホは持っていません.2人は,落ち合えな ければ最悪の気持ちですが,もし落ち合えるならば,彼の方はどちらかというとカ ラオケに,彼女の方はどちらかというと映画館にいきたいと思っており,お互いに そのことは分かっています.さあ,あなたが彼/彼女ならどちらへいきますか?・・ 2020/5/17
強化学習とゲーム理論(MARL)@deeplab 清原 明加 18 彼A / 彼女B カラオケ 映画館 カラオケ (3,2) (0,0) 映画館 (0,0) (2,3)
ゲーム理論について-共有地の悲劇- 個別最適と全体最適は一致しない 村全体で飼うなら3頭が適切な(利益が最大となる)牛の放牧.しかし,村の農家一人 ひとりが自分自身の利益を最大化しようとすると,3人の農家は一人2頭牛を飼い始 め,村全体では計6頭になってしまいました.・・ 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 19
too much 6cow/village appropriate 3cow/village
ゲーム理論について-ジレンマの回避- 互いの意思を確認できる場合と,できない場合. あなたの意思決定は変わりますか? A国では国民10人全員に,ひとりあたり10万円が与えられることになりました.10万 円は国民それぞれのものですので,どんな使い方をするかは国民の自由です.今, 国が投資のための資金を国民から集めることにしました.この投資は成功が保障さ れていて,国民から集まったお金の3倍を税金として10人に均等に再分配することが できます.あなたはいくら国に投資資金として渡すでしょうか?また,その決断は 他の住民と話し合いの上行う場合と,自分一人で行う場合,変わりますか?・・ 2020/5/17
強化学習とゲーム理論(MARL)@deeplab 清原 明加 20 協力する 出し抜く 話し合い あり?なし?
マルチエージェント強化学習 Multi-Agent Reinforcement Learning (MARL) 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 21
問題提起 • ゲーム的状況において,個別学習させた エージェントは周囲との協調を考えた行動 を選択できるのか? • つまり,自律分散型最適化をマルチエー ジェント環境において学習させることはで きるのか? •
人間の行うコミュニケーションの代わりと なるものを,どのように観測環境や情報と して組み込めるか? また,コミュニケーションなく協調は可能 なのか? 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 22
場面設定 • 協力 エージェント同士が協力して行動しなければ良い報酬 が得られない,全体での報酬を大きくしたい場合. • 敵対 zero-sumゲームなどの,一方が得をすれば他方が損を する状況で敵対的にエージェントを学習させたい場合. •
影響 必ずしもエージェント間で協力して何かを達成したい 訳ではないが,他のエージェントの行動も考慮に入れ た上で最適化をしなければならない場合. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 23
以下での参考文献 • 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
主要課題 • MDPが達成されない⇒定常性がない,収束性に問題. (つまり,経験再生が利用しづらい) • 情報共有を規定すると,情報過多になり次元の呪いが 問題に. • どうやって協力することをを学ばせるか. 2020/5/17
強化学習とゲーム理論(MARL)@deeplab 清原 明加 25
研究分野 • 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
研究分野の概観-Framework/Joint Action- • Framework あるシチュエーションを仮定して,どのような枠組み の中で収束性を担保できるかなど,アルゴリズムの話. • Joint Action Learning
エージェントが同時に意思決定するシチュエーション を考えて,マルコフ性など収束性に関する問題への考 察を行う. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 27
研究分野の概観-3C- • Cooperation and Competition マルチエージェント環境において,エージェント同士 に協力したり,競い合ったりする状況での方策や行動 の最適化を学習させる. • Coordination
上記Cooperationタスクにおいて,同じタイミングで エージェントがそれぞれ適切な行動を起こさないとい けない状況設定において,探索の困難性などについて 議論する. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 28
研究分野の概観-Security/Self-Play- • Security サイバーセキュリティの状況設定において,attacker とdefenderの間のzero-sumゲームを考えている.ここ で,defender側をマルチエージェントにして,パト ロールの最適化をしたいらしい. • Self-Play AlphaGoなど,正解を人間が知らない∧ゲームなどの
閉じた設定∧対戦相手が明確な場合に,エージェント 同士を戦わせて,自己対戦によって最適方策(行動)を 学習していく. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 29
研究分野の概観-Communicate/Transfer- • Learn to Communicate(詳しくは次ページ) マルチエージェントの特にCooperativeな場面において, 情報共有や意思伝達の機能をエージェントに学習させ る.個人的には,Competitiveな状況でCommunication によって駆け引きが学習できると面白そうと思うけど, 収束性に問題があるのかあまり研究されていなさそう.
• Transfer Learning 他のエージェントが異なる/同じ状況で学習した記録 を,別のエージェントの学習に転用できないだろう か?という発想.学習効率の向上について議論. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 30
意思疎通・情報共有の設定 • Consensus 予め人間の手によって共有する情報と範囲を決めてお き(その意味で”合意”という),共有された情報と自分 の見れる範囲の観測を基にエージェントは意思決定す る.また,全体最適の場合エージェント間の重みにつ いても取り決められていたりする. • Communication
エージェントに,”いつ” ”誰と” ”どのようにして”情報 を共有したり,シグナルを発信したりするのかまでも 学習・決定させる.ここで送られるメッセージはあく まで環境を変化させないものと仮定されている. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 31
研究分野の概観-Imitation/Inverse/Meta- • Imitation and Inverse Reinforcement Learning 通常は報酬を最大化するようエージェントが最適方策 (行動)を学習するが,対して,最適な方策(行動)を天下 り的に与えて,そこから報酬の推定を行う,という意
味で逆強化学習.状態数が多く探索が困難な場合に, 優秀な人間のデータを最適方策として与えることも. • Meta Learning 学習の仕方を学習する.マルチエージェントの Competitiveな状況において,メタ学習を使って変化し ていく状況に対応し,収束性課題に取り組むなど. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 32
研究分野の概観-Application- • multiple traffic signals 交通量を最大化するように,信号機の切り替えを都市 全体で調整. • bike rebalancing
貸し自転車の店舗間移送を効率化する. • distributed resource allocation 流通システムにおいて在庫を抱えないよう資源を分配. • liquidation of stock 株の流動性の予測やポートフォリオ最適化など. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 33
モデル選択の自由度 • 使用するモデル 方策ベース?価値ベース? • 観測範囲 state, action, rewardについて, 各々local,
neighbor, globalのどの範囲で観察できるか? • ConsensusとCommunication どの範囲での情報共有を設定するか? • 階層(ヒエラルキー) 中央集権的に行うか?どこまで自主性に任せるか? • その他 RNN, GNN, Attention, Importance Sampling, Distributed, etc. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 34
補足-観測範囲について- 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 35 Fully Observable (すべてのエージェントが) すべての状態や報酬を観測できる.
Partially Observable 各エージェントは,自分の周りの近くの 状態や報酬のみ観測できる. 観測の共有をConsensusで決定. ・観測を全エージェント間で共有 ・観測を近傍のエージェントや,サブグ ループ内でのみ共有 ・エージェント間の共有は行わない Share? or not? globally locally individually
補足-階層について- 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 36 Centralized Decentralized 中央集権型 エージェントを統括して
全体を見る仮想エージェ ントがいるイメージ. サブグループ型のさらに 上のエージェントなども. サブグループ型 近傍のエージェントとな どサブグループを生成し, その中を統括するリーダ ーエージェントが存在し ているイメージ. 自律分散型 各エージェントが個別に 意思決定を行い,全体を 統括するエージェントが 存在しないイメージ.
補足-その他(1)- • RNN.. 価値の推定に,自身の時系列の過去経験から内部状態 を保持・使用する.LSTM, GRUなど. • GNN.. エージェントをノード,エージェント間の関係をエッ ジとみるとグラフとして全体を把握できる.
• Attention.. 全体でのpolicy, Qの決定を行う際に,各エージェント の持つ予測モデルの重みづけができる. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 37
補足-その他(2)- • Importance Sampling.. 重みづけをした場合など,重みに応じてSampling Rate を変えることで,優先付けしてサンプリングできる. • Distributed Learning..
あるエージェントで学習した結果を他のエージェント でも活用できるようにすることで,分散的に学習を行 うことができ,学習効率が向上する.ただし,基本的 に他のエージェントの行動を観測できないようにして いる場合などは,経験をどこまで他のエージェントが 活用できるようにするかは議論がある. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 38
ホットトピック • Off-policy MARL 他のエージェントも含めた状況で,行動方策から最適 な方策を学習する. • Safe MARL 長期的利益を最大化しつつ,決定的な打撃をさけるた
めのリスク回避を行いたい. • Heterogeneous MARL 一様なエージェントではなく,技能などに個性を持っ たエージェントでの最適化. • Optimization in MARL マルチエージェント環境での最適化問題を解く数学. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 39
問題提起(再掲) • ゲーム的状況において,個別学習させた エージェントは周囲との協調を考えた行動 を選択できるのか?⇒できる • つまり,自律分散型最適化をマルチエー ジェント環境において学習させることはで きるのか?⇒できそう •
人間の行うコミュニケーションの代わりと なるものを,どのように観測環境や情報と して組み込めるか? また,コミュニケーションなく協調は可能 なのか? ⇒ConsensusとCommunicationを導入できる 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 40
まとめ • MARLはゲーム理論的な課題に対し,Communicationの 導入などにより解決できそうだった. • ただし,MARLでは収束性や学習の安定性が課題となる ので,工夫が必要そうだった. • これからのMARLは,適用範囲を増やしていくことや, 一人一人違う個性を持ったエージェントにおける最適
化などがおもしろそうだった. 2020/5/17 強化学習とゲーム理論(MARL)@deeplab 清原 明加 41
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