[DL輪読会] マルチエージェント強化学習と心の理論

DEEP LEARNING JP [DL Papers] マルチエージェント強化学習と心の理論 9/17 今井翔太 （松尾研究室） えるエル@ImAI_Eruel http://deeplearning.jp/ 1

• http://deeplearning.jp/

書誌情報 2 マルチエージェント強化学習で「心の理論」と関連する（と主張する）研究の一部を、以 下の論文を中心に紹介 1. The Hanabi Challenge: A New Frontier for AI Research - 著者：Nolan Bard, , Jakob N. Foerster et al. - arXiv:1902.00506 2. Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning - 著者：Jakob N. Foerster, H. Francis Song et al. - ICML2019 3. Simplified Action Decoder for Deep Multi-Agent Reinforcement Learning - 著者：Hengyuan Hu, Jakob N Foerster - ICLR2020 Shota Imai | The University of Tokyo

研究概要 3 ◼ 一般人に通じるような表現で大雑把にいうと「AIの心を読むAI」の研究 ◼ 環境内に複数のエージェントが存在するマルチエージェントの設定では、協調・競争時 に自分以外のエージェントの意図を読むことができれば、協調の成功確率、相手に対す る勝率に良い影響を与えられると考えられる ◼ マルチエージェント強化学習においては、認知科学の「心の理論」の考え方をベースに、 自分以外のエージェントの意図を推定する手法について、いくつかの方向で定式化 Shota Imai | The University of Tokyo

マルチエージェント強化学習 （MARL; Multi-Agent Reinforcement Learning） ◼ マルチエージェント分野の研究分野全体はマルチエージェントシステム（MAS）ともよ ばれる ◼ MASの中でもエージェントの「学習（機械学習）」に興味があるものはマルチエージェ ント学習と呼ばれる分野 ◼ マルチエージェント強化学習はマルチエージェント学習の中でもエージェントの学習ア ルゴリズムとして強化学習を使っている手法 ◼ 端的に言うと、環境中に学習するエージェントが複数いる環境における強化学習 - 囲碁や将棋などのボードゲームもMARLの一部 - 最近の例ではStarCraftのAlphaStarが有名で、 多人数の対戦ゲームはMARLのアプローチで解くやり方が主流 - その他、マルチロボット、自動運転への応用 - なお、エージェントして人間を含んでも良い 近年、深層強化学習の処理能力を活かしたマルチエージェント深層強化学習として、研究 が盛ん Shota Imai | The University of Tokyo 4

マルチエージェント深層強化学習 ◼ 深層強化学習によって、あるタスクで高い性能を発揮する（報酬を最大化する）エー ジェントの方策を獲得することが目標 ◼ 環境内の複数エージェントが同時に強化学習を行なっている設定 ◼ 特に、実機を用いた難しい協調タスクへの応用が期待され、現在は計算機上での比較的 難しいタスクをベンチマークとしてアルゴリズムの研究が進む ◼ 有名な手法 - MADDPG (Multi-Agent Deep Deterministic Policy Gradients) COMA (Counterfactual Multi-Agent Policy Gradients) VDN (Value-Decomposition Networks) QMIX AlphaStar マルチエージェント深層強化学習に関する記号の定義 • 環境の状態：𝑠 ∈ 𝑆 • 行動：各エージェント𝑎 ∈ 𝐴 ≡ {1, … , 𝑛}の行動ua ∈ 𝑈 • 共同行動（joint action）：𝒖 ∈ 𝑈 ≡ 𝑈𝑛 • 状態遷移関数：𝑃(𝑠′|𝑠, 𝑢): 𝑆 × 𝑈 × 𝑆 → [0,1] • 部分観測関数：𝑂(𝑠, 𝑎): 𝑆 × 𝐴 → 𝑧 • 報酬関数：𝑟(𝑠, 𝑢): 𝑆 × 𝑈 → 𝑅 5

マルチエージェント強化学習の問題設定の分類 6 ◼ 中央集権型学習-中央集権型実行 (AlphaStar等) - 環境内にエージェントは複数いるが、各エージェントの方策を 出力するモデルは単一で、モデルへの入力も、各エージェント の観測をまとめて受け取る設定 - 方策モデルの処理能力に左右され、個別エージェントの観測の 情報の共有が無制限という仮定が必要 方策モデル： 1, , ) ◼ 分散型学習-分散型実行（IQL, その他古典的手法） - 一番難しい設定で、全てのエージェントが学習/テスト時ともに 個別の観測を受け取って学習・行動する - 深層学習以前のマルチエージェント強化学習や、DQN登場直後 の問題設定はこれ 学習時 - IQL (Independent Q-Learners)としてまとめられることも ⽅策モデル： � � � ) ⽅策モデル： � � � ) ⽅策モデル： � � � ) テスト時 ◼ 中央集権型学習-分散型実行（MADDPG, COMA等） - 現在のMARLの主流設定（後述） - 学習時に追加の中央情報を使うが、 テスト時は分散的 ⽅策モデル： � � � ) ⼊⼒ ⽅策モデル： � � � ) 勾配 中央学習器： Q(� | � )等 損失計算 ⽅策モデル： � � � ) ⽅策モデル： � � � ) ⽅策モデル： � � � ) ⽅策モデル： � � � )

中央集権型学習分散型実行 CTDE; Centralized Learning Distributed Execution ◼ 現在のMARLの最重要概念（だが、今回の発表の本質ではない） ◼ 中央集権型学習：学習時のみ，勾配を計算する時に全体のエージェントの情報を含む環 境の「中央の状態」を使う （e.g, 各エージェントの方策パラメータの勾配計算に部分観測に加え真の状態sを使う） ◼ 分散型実行：テスト時には，各エージェントは自身の部分観測のみを入力として方策を 実行 ◼ COMA[Foerster+ 2017]以降，特に用いられるアプローチで， “in many cases, learning can take place in a simulator or a laboratory in which extra state information is available and agents can communicate freely”[Foerster+ 2016] つまり，「マルチエージェントの学習は，研究的な環境でシミュレータ等を使えるため， 学習を促進するために追加の状態の情報を使ってもよい」という仮定によるアプローチ ◼ 本来エージェントが動作するテスト環境（Execution時）は，基本的に各エージェントが 個別の観測だけを受け取って強調しているため，状態の追加情報は使えない ◼ 今回紹介する手法も学習時にはCTDEの設定で学習している前提で、一部の手法はCTDE の仮定をフル活用している Shota Imai | The University of Tokyo 7

マルチエージェント強化学習の課題 ◼ 学習時の非定常性 - 自分以外のエージェントも方策を学習するので、普通に方策を更新しても最適方策への収束が 見込めない（他のエージェントの学習によって環境の挙動が変化） ◼ 不完全情報性 - 自分以外のエージェントに関して見えない情報が多く、エージェントが利用できる観測だけで は行動決定に必要な情報が不足 ◼ 学習時にセットになっていないエージェントとのテスト時の協調 - 学習の際に一緒に学習した他者エージェントに過学習し、テスト時に別の環境で学習したエー ジェントとの協調がうまくいかない（ゼロショット協調問題） →学習時 or テスト時の推論で、自分以外のエージェントの意図を読むことができれば、こ の辺の問題を軽減できる Shota Imai | The University of Tokyo 8

他のエージェントの意図を「読む」手法の研究 ◼ 他者モデリング（Opponent Modeling） - 学習時の非定常性を解決するために使用されるのが主 - 自分以外のエージェントの方策𝜋𝑜𝑡ℎ𝑒𝑟をモデリングし、方策そのも のや特徴抽出したものを自分の方策モデル𝜋𝑠𝑒𝑙𝑓の入力とすること で、非定常性を緩和 ◼ 心の理論（Theory of Mind） - 不完全情報ゲームなどで、自分以外のエージェントの行動を観測 として使用することで、エージェント𝑎に関する信念𝐵𝑎 非公開情報 𝑓 𝑎 などの追加的な情報を推論する手法 - ベイズ推論を利用することが多い - 「Theory of Mind」を称する研究は大量にあるので、上記はMARL 界隈の代表的なもの Shota Imai | The University of Tokyo 9

心の理論 10 ◼ 1978年霊長類学者David Premackが「チンパンジーは心の理論を持つか」という論文で 提唱した概念で、自分以外の他者の意図を適切に推測する能力 - 高度な知能を持ち、集団生活をするチンパンジーは他の仲間の心の状態を推測できるかもしれ ないと考え、他者の目的、意図などが適切に推測できれば「心の理論を持つ」とした - 「理論」という表現は、心の状態は直接見る（魔法!）ことができず、何らかの基礎的な法則、 経験則から物理法則のように推論に基づいて構成されることから ◼ 1983年のWimmer&Pernerは誤信念課題（後述）を用いて、人間の子供が、4~7歳にかけ て心の理論を持つようになることを示した ◼ 最近、機械学習、特に複数エージェントが存在するマルチエージェント強化学習の分野 でこの概念と絡めた研究が複数発表されている Shota Imai | The University of Tokyo

誤信念課題 11 ◼ 通称「サリーとアン課題」と呼ばれる、 被験者に以下の展開を見せる 1. サリーがカゴにボールを入れる 2. サリーが部屋を去る 3. アンがサリーがいない間にカゴから箱の中にボールを移動させる 4. アンが帰ってくる 被験者に対し「このときアンはボールがどこにあると思っているか」 を問う ◼ アンが「カゴの中にボールがある」という誤った信念を持っている ことを、被験者自身の知識と切り離して、アンの心を推論して 答える必要がある ◼ 4歳〜7歳にかけて正答率が向上 出典：https://en.wikipedia.org/wiki/File:Sally-Anne_test.jpg Shota Imai | The University of Tokyo

機械学習の世界における心の理論 ◼ 定義は完全に混沌としている ◼ 強化学習のみならず、自然言語処理、画像認識など様々な場面で手法を「心の理論」と関連 づけた例が多数 ◼ マルチエージェント強化学習だけで見ても、非常に多様な手法に分類可能 ◼ 自分以外のエージェントに関する、 - 方策 次の行動 以前の行動の意味 RNN、LSTMなどの内部状態 相手の信念 不完全情報で隠されている特徴 を推論し、他のエージェントとの協調・競争に役立てる手法で、 学習時のみに興味がある→Opponent Modeling テスト時にも興味あり→Theory of Mind ◼ かなり適当に人間の知能と結び付けて、論文の貢献のアピールに使われているっぽい例があ るので、知能論と関連づけて考えすぎるのはNG Shota Imai | The University of Tokyo 12

余談 /「心の理論」を安易に使って燃えた例 Shota Imai | The University of Tokyo 13

心の理論を適用する場合の問題点（人間の思考例） ◼ お互いに「相手の意図を読む」機能があることが既知だとした場合、無限に再起的な読 み合いが発生する ◼ 普通の場合（アリスだけが読む能力を持ち、ボブにはできないことを知っている） - ボブ「（Aという行動をしよう）」 - アリス「（ボブはAという行動をするだろうからそれに強いBをしよう）」 ◼ お互いに相手の行動を予測できる場合 - ボブ「（アリスは僕がAをすると思っているだろうからBを選ぶだろう。だからそれに強いCを しよう」 - ボブ「いやだけど、アリスは僕がこんなことを考えているのも読んでいるだろうからCに強い Dをしてくるかもしれない。Dに強いEをしよう」 - ボブ「それすらもアリスは読んでいるかもしれないから、Eを読んでFをしてくるかもしれな い。やっぱりFに強いGで・・・」 - 以後、相手の推論能力の仮定をどこかでストップさせない限り、無限に続く（アリス側の思考 も同じ） Shota Imai | The University of Tokyo 14

心の理論を適用する場合の問題点（MARL） ◼ シングルエージェントでPOMDPを扱う場合、LSTMやRNNをナイーブに適用し、環境に 対する信念を獲得すれば、部分的な観測から大体正しい行動が可能 ◼ MARLの場合、他のエージェントの方策モデルのパラメータ（これは既知という仮定も 多い）、相手のRNNやLSTMの内部状態、さらに「相手が自分に対して推論している何 らかの機構」のモデルも信念として持つ必要がある →再起的な推論が発生し、計算不可能 ※MARLにおいてどの程度の読みが有効か実験的に示している例もある Shota Imai | The University of Tokyo 15

参考/レベルK理論 16 ◼ 相手が何段階読むかを、レベル0（まったく読まない）、レベル1(一手先を読む)などと いうKレベルで表現し、どれくらいの合理性を持った相手なのか予測する ◼ 予測した相手のレベルに応じて行動を実行する - レベル0（相手が何も読まない）なら、一手先を読めば勝てる - レベル1（相手も一手先を読む）なら、２手先を読めば勝てる ◼ ここでの相手に対するKの値はあくまでも推測であり、現実的には相手の合理性を完璧に は評価できないが、ゲームのトッププレイヤーや理系の人間などは一般的に高い （例）数当てゲーム - 複数の被験者に、1~100のどれかの数字を書かせ、全員の書いた数字の平均の2/3に最も近い 数字を書いたものが勝利というゲームをさせる - 簡単に推論すると、全員がランダムに数字を選ぶとして平均50。その2/3の33周辺がよさそう - ここで、推論のレベルを一つあげると「他のみんなも同じことを考えて33と書いてきそうだか ら、平均は33近くなる。その2/3の22がよさそう」となる - 以降、推論のレベルをあげるたびに数値は小さくなり、全員が合理的なプレイヤーという予測 では、0になるまでレベルが上がる - 実験的には、ほとんどのプレイヤーがレベル1で、自分はレベル2の推論で十分なことが多い Shota Imai | The University of Tokyo

Hanabi MARLにおける心の理論系研究の主要ベンチマーク ◼ 2〜5人の協力ゲーム ◼ RLで頻繁にベンチマークとなる主要なボードゲームなどと異なり、ゲーム木探索による 必勝法やナッシュ均衡など、ゲーム情報学的な解を持たない ◼ 相手の意図によって、理想的な行動が異なる＆理想的な行動ではなく、メッセージ的な 行動をも要求されるなど、相手の意図をモデリングして積極的に利用する必要 ◼ 心の理論系（相手の行動を読んで自分の方策のinputとして使う等）の主要ベンチマーク Shota Imai | The University of Tokyo 17

Hanabiのルール 1/2 18 ◼ 各プレイヤーは手札として、４枚（プレイヤー数が2 or 3名の場合は5枚）のカードを持 つ ◼ 各カードは赤緑青白の5色と1~5の数字の組み合わせ（例：赤の5など）で分類され、全 50枚、各色10枚のカードがある（各色について1は3枚、2, 3, 4は2枚、5は1枚） ◼ プレイヤーは自分の手番に、自分の手札を場に出す（プレイ）、手札を捨てる、他のプ レイヤーにヒントを与える、のいずれかの行動を選択 ◼ ゲームの最終目的は、各色について1から順番に場に出して5まで揃えること（各色につ いて５枚揃うことを”花火を打ち上げる”と表現） ◼ 自分の手札は見えないが、他のプレイヤーの手札は全て見える プレイヤー0（P0）視点のHanabi Shota Imai | The University of Tokyo

Hanabiのルール 2/2 19 ◼ 他のプレイヤーに与えるヒントは、ある個人プレイヤーに対し、「そのプレイヤーが持 つ同じ数字のカードを全て教える（色は教えてはいけない）」、「そのプレイヤーが持 つ同じ色のカードを全て教える（数は教えてはいけない） 」のどちらかで、一部だけ教 える等は不可能 - 例：P2に対して「1枚目と3枚目は赤色」 ◼ ヒントを与えるとトークンを１つ消費するが、カードを捨てる行動を選択するとトーク ンが１つ回復する（MAXは8つ） - 捨てられたカードは全プレイヤーが見れるようになる - カードを捨てた後、１枚カードを引いて補充する ◼ 各色について、必ず数字順にプレイしなければならない - 例えば、白1、白2が揃っている時に白4を出したら1ミス ◼ 3回ミスするか、５色全て揃えるとゲーム終了 この場面では、プレイすることを許さ れるカードはG2、B1、W2、Y2、R1 - 終了時点で場に正しくプレイされていたカードの総数が得点になる（MAX25点） Shota Imai | The University of Tokyo

Hanabiの戦略・駆け引き的な部分 ◼ 行動による暗黙のコミュニケーション - ヒントの与え方によって、ヒントで陽に示している以上の情報を与えることが可能 - 例：右下図の状況でP0が、P1に対し、「４枚目は赤」のヒントを与える - P1視点だと４枚目のカードが赤以外の情報はないので、本来はプレイする情報が足りていないが、逆に考 えると「わざわざ不完全なヒントを与えたということは赤は１なのでは」という発想につながる ◼ Finesse（もう少し高度な暗黙コミュニケーション） - P0がP2に対し「３枚目は2」のヒントを与える - P2視点だと、このヒントをもらった場合に考えることは「おそらくこの2は白」（場にG1とW1があるが、 G2はすでに２枚とも捨てられているためW2以外あり得ない） - これは間違いで、実際はR2なので、このままいくとP2はミスする - P0の次の手番のP1視点だと「このままだとP2は失敗する。だが、P0があのようなヒントを出したからに は理由があるはずで、おそらくそれは自分が最近引いたカードがR1でそれをプレイしろということか」 Shota Imai | The University of Tokyo 20

Hanabiの難しさ 21 ◼ 今回発表する手法以前は、機械的な手法では人間の知識を大量に入れたbotが主流で、学 習ベースのアプローチはこれらの手法に勝てなかった - 人間に特有の非言語的なコミュニケーションを読み取れない - テスト環境で学習時と別のエージェントとプレイすると、学習した方策が機能しない ◼ 今回紹介する手法についても、二人以上のプレイではスコアが極端に下がる Shota Imai | The University of Tokyo

BAD; Bayesian Action Decoder ◼ マルチエージェント強化学習（ここではHanabi）において、相手の行動から見えない情 報について何らかの推測ができれば、適切な行動と協調が可能 ◼ 相手の信念の推論はベイズ推論により、割と簡単に定式化可能だが、再起的に信念を推 論する部分で計算が爆発する ◼ BADでは全てのエージェントに公開されている情報（public features）を用いて、全て のエージェントに共通の信念（public belief）を推論し、適切な決定論的方策を実行する 手法を提案 Shota Imai | The University of Tokyo 22

記号定義 23 ◼ 𝑎 ∈ 1. . 𝑁：エージェント ◼ 𝑢𝑡𝑎 ：時刻tにおけるエージェントaの行動 ◼ 𝑜𝑡𝑎 ：時刻tにおけるエージェントaの観測 ◼ 𝑠𝑡 ：時刻tにおける環境の真の状態 ◼ 𝑂(𝑎, 𝑠𝑡 )：観測関数 ◼ 𝜏𝑡𝑎=(𝑜0𝑎 , 𝑢0𝑎 , … , 𝑜𝑡𝑎 )：エージェントaの行動観測の履歴 ◼ 𝜋 𝑎(𝑢𝑡𝑎 |𝜏𝑡𝑎)：エージェントaの方策 ◼ 𝐮𝑡 = (𝑢1𝑡 , . . , 𝑢𝑡𝐴)：共同行動 ◼ 𝑃 𝑠𝑡+1 𝑠𝑡 , 𝐮𝑡 )：遷移関数 ◼ 𝑟𝑡+1(𝑠𝑡 , 𝐮𝑡 )：チーム報酬 ◼ 𝐵𝑡 ：信念（これまでの履歴などからどんな隠れ状態にあるか確率的に表す） Shota Imai | The University of Tokyo

Hanabiでベイズ推論を用い,自分の手札を予測する場合 𝑃 ℎ𝐵 𝑃 𝑢𝐴 ℎ𝐵 )𝑃(ℎ𝐵 ) 𝜋𝐴 𝑢𝐴 ℎ𝐵 𝑃(ℎ𝐵 ) 𝑢𝐴) = = σℎ′ 𝑃 𝑢𝐴 ℎ𝐵 )𝑃(ℎ′𝐵 ) σℎ′ 𝑃 𝑢𝐴 ℎ𝐵 )𝑃(ℎ′𝐵 ) 𝐵 𝐵 ３枚めのカード をプレイします 見えない 見えている Alice Bob ◼ ℎ𝑎 , ℎ𝐵 ：エージェント（アリスとボブ）の手札 ◼ ボブの自分の手札に関する信念 𝐵𝐵 = 𝑃(ℎ𝐵 |𝑢𝐴) ◼ ここでは、アリス（ボブの手札ℎ𝐵 が見えている）が、アリスのターンで、あるカードを 捨てる行動𝑢𝐴を選択した場合、ボブの手札が何かを推論 - アリスの行動𝑢𝐴には、ボブの手札ℎ𝐵 を見たことによるなんらかの意味があるはずという仮定 ◼ 𝑃(𝑢𝐴|ℎ𝐵 )は普通のRLの方策とみなせる Shota Imai | The University of Tokyo 24

お互いが何らかの信念を持っており、環境の公開情報も利用する場合（見 えない情報に対して何らかの「読み」を行っている場合） 方策の入力として、単なる相手の手札の観測ℎだけでなく環境に関する何らかの公開情報𝑃𝑢𝑏 （今までプレイされたカードや、山札の残りなど)や、相手の信念𝐵も使用する場合、前スライ ドの式をさらに変形すると、 変形前：𝑃 ℎ𝐵 𝑢𝐴 ) = 𝑃 𝑢𝐴 ℎ𝐵 )𝑃(ℎ𝐵 ) ′ σ ′ 𝑃 𝑢𝐴 ℎ𝐵)𝑃(ℎ𝐵 ) = ℎ𝐵 変形後：𝑃 ℎ𝐵 𝑢𝐴 ) = 𝑃 𝑢𝐴 ℎ𝐵 )𝑃(ℎ𝐵) ′) σ ′ 𝑃 𝑢𝐴 ℎ𝐵 )𝑃(ℎ𝐵 ℎ𝐵 = 𝜋𝐴 𝑢𝐴 ℎ𝐵 𝑃(ℎ𝐵 ) ′ σ ′ 𝑃 𝑢𝐴 ℎ𝐵 )𝑃(ℎ𝐵 ) ℎ𝐵 𝜋𝐴 𝑢𝐴 ℎ𝐵 , 𝐵𝐴 , 𝑃𝑢𝑏 𝑃(ℎ𝐵) ′) σ ′ 𝑃 𝑢𝐴 ℎ𝐵 ,𝐵𝐴 ,𝑃𝑢𝑏)𝑃(ℎ𝐵 ℎ𝐵 ◼ アリスの方策𝜋𝐴 は、アリスの信念𝐵𝐴 と公開情報𝑃𝑢𝑏に条件づけられているとみなせる ◼ 信念は自分の見えていない手札の予測（BA = 𝑃(ℎ𝐴 )) ◼ 𝐵𝐴 = 𝑃 ℎ𝐴 𝑢𝐵 )はどのように推論する？ →お互いに同じ推論を行っていると考えると、お互いの式に再起的に𝐵が登場し、推論が爆発 Shota Imai | The University of Tokyo 25

BADのアイディア 26 ◼ 全てのエージェントに公開されている情報で条件づけて、全エージェントの信念をまと めて推測した信念をPublic beliefとすれば、全エージェントで共通の信念を共有できそう 𝐵𝐴 = 𝑃 ℎ𝐴 ℎ𝐵 , 𝑓 𝑝𝑢𝑏 𝐵𝐵 = 𝑃(ℎ𝐵 |ℎ𝐴, 𝑓 𝑝𝑢𝑏 ) → 𝐵𝑡 = 𝑃(ℎ𝐴, ℎ𝐵 |𝑓 𝑝𝑢𝑏 ) ◼ Public beliefを利用する方策𝜋𝐵𝐴𝐷（Public agent）を導入し、𝜋𝐵𝐴𝐷によって、ある時刻に おける個別エージェントの決定論的方策を選択、privateな観測から行動を決定する （上記より、各エージェントが共通の方策パラメータを持つことは既知とする） ◼ Hanabiの例を使って具体的に書くと、 𝑩𝒕 = 𝑷(𝒉𝑨 = ボブの手札の確率、𝒉𝑩 = アリスの手札の確率|𝒇𝒑𝒖𝒃 = 山札プレイされたカードなどの公開情報) Shota Imai | The University of Tokyo

BADで登場する概念と記号定義 𝑝𝑢𝑏 ◼ 𝑓𝑡 ：全てのエージェントに公開されている特徴 (public features) →テーブル上に置かれていて全プレイヤーが見れるカード、山札の残りなど 𝑝𝑟𝑖 ◼ 𝑓𝑡 ：一部のエージェントのみが見れる情報 (private features) - 𝑓𝑡𝑎：エージェントaのみが参照できるprivate feature - 自分だけが見れる手札、ℎ𝐴など 𝑝𝑟𝑖 ◼ Public belief 𝐵𝑡 = 𝑃(𝑓𝑡 𝑝𝑢𝑏 - 𝑓<𝑡 =( 𝑓0𝑝𝑢𝑏 , . . , 𝑓𝑡𝑝𝑢𝑏） 𝑝𝑢𝑏 |𝑓<𝑡 ) ◼ 𝜋𝐵𝐴𝐷 ：Public agentの方策 ◼ 𝜋ො ∶ {𝑓 𝑎} → 𝒰：個別エージェントの決定論的方策（Partial Policy） ◼ 𝑠𝐵𝐴𝐷： 𝐵𝑡 と𝑓 𝑝𝑢𝑏 を一まとめにした概念 ◼ 𝜋ො ∼ 𝜋𝐵𝐴𝐷(𝜋ො |𝑠𝐵𝐴𝐷) Shota Imai | The University of Tokyo 27

PuB-MDP（Public belief MDP） Shota Imai | The University of Tokyo 28

Public Belief 29 ◼ 全てのエージェントの可能な𝑓 𝑝𝑟𝑖 の組み合わせに確率を割り振った行列 (例) 𝐵𝑡 = { アリスの手札ℎ𝐴 、ボブの手札ℎ𝐵 、𝑃(ℎ𝐴 , ℎ𝐵 ) 23344, 11122, 0.000 23344, 11123, 0.002 ・ ・ ・ 44444, 55555, 0.001 } Shota Imai | The University of Tokyo

Partial PolicyとPublic Policy 𝑝に対応する行動リスト、Public Policy 𝜋 ◼ Partial Policy 𝜋は特定の𝑓 ො ො 𝐵𝐴𝐷はいくつかある𝜋 を選択するための確率分布 { 𝜋ො = 23344→5のカードをプレイ 23344→青のカードに関するヒント ・ ・ 55555→3のカードを捨てる } Shota Imai | The University of Tokyo 30

Public Policyの更新 31 ◼ プレイヤーが行動する各時間ステップごとに、その時刻のプレイヤーの行動 𝑢𝑡𝑎 、信念 𝐵𝑡 、 選択されたpartial policy 𝜋ො 、その他の公開情報 𝑓 ′𝑝𝑢𝑏 （残りのカード枚数など）を用いて、 次の時刻の信念𝐵𝑡+1を得る 𝐵𝑡+1 = 𝑃(𝑓 𝑝𝑟𝑖 |𝑢𝑡𝑎, 𝜋, 𝑓 ′𝑝𝑢𝑏 , 𝐵𝑡 ) Shota Imai | The University of Tokyo

その他 32 ◼ 実際には、Public belief行列はかなり大きいので、いくつか計算上の工夫を行って小さく している（論文中”Factorised Belief Updates”, Self-Consistent Beliefsの部分） ◼ 実装上は、 𝜋ො ∼ 𝜋𝐵𝐴𝐷(𝜋ො | 𝑠𝐵𝐴𝐷) = 𝜋𝐵𝐴𝐷(𝜋ො |𝐵𝑡 , 𝑓 𝑝𝑢𝑏)の部分については、パラメータθを持 つMLPネットワークを使って近似している（出力の𝑢は全ての行動候補） 計算したいもの：𝑃 𝜋ො | 𝑠𝐵𝐴𝐷 = 𝜋𝐵𝐴𝐷(𝜋ො |𝐵𝑡 , 𝑓 𝑝𝑢𝑏 ) 実際に計算するもの：𝑃 𝑢 𝑓 𝑎, 𝑠𝐵𝐴𝐷) = 𝜋 𝜃 (𝑢|𝑓 𝑎, 𝑠𝐵𝐴𝐷) 𝑓𝑎 𝑢 𝑠𝐵𝐴𝐷 Shota Imai | The University of Tokyo

実験：定量評価 33 ◼ 異なる公開情報をベースにした入力を行うLSTMベースのエージェントと、既存の最強の BotとHanabiにおける平均スコアを比較（マックスは25点） ◼ 方策更新のRL手法としてはActor-Criticの方策オフ手法（IMPALA）を使用 ◼ 注意として、ここでは2人のHanabiしか評価していないため、BADの強さは限定的 Shota Imai | The University of Tokyo

実験：定性的な部分 ◼ テスト時に、エージェント間で、特定の行動が暗黙的なメッセージになっているプレイ が複数見られた - 例えば、赤色or黄色のカードに関するヒントを与えた場合には、「一番新しいカードをプレイ しろ」の意味、青か白の場合は「一番新しいカードを捨てろ」の意味を持っている ◼ 論文Appendixにおいて、過去のHanabiの最強botの作者がテスト時のBADエージェント のプレイを分析したコメントを載せている Shota Imai | The University of Tokyo 34

BADの問題点 35 ◼ テスト環境が2人のHanabiで比較的簡単（人間の普通のゲームなら普通もっと多人数） ◼ Public Agent、方策パラメータが同じという仮定が非現実的 ◼ 公開情報がドメイン依存で、汎用性が低い ◼ 計算コストが大きい（𝑓 𝑝𝑢𝑏 が膨大） Shota Imai | The University of Tokyo

SAD; Simplified Action Decoder ◼ 公開情報をベイズ推論に組み込むBADの手法は、二人プレイHanabiで高パフォーマンス だったが、公開情報の利用が計算コストの増大と汎用性の低さにつながる ◼ SADでは公開情報を必要とする部分（Public Policy、決定論的Partial Policy）を廃し個 別の信念を持つRNNエージェントが個別の方策を表現 - 個別エージェントはε-greedy探索を採用して学習時に探索を行う - BADでは探索の部分を、Public policyが公開情報で条件づけて確率的に選択するpartial policy で代替していた ※ここでの公開情報とは、普通にプレイして観測できる他エージェントの行動𝑢𝑎 などではなく、山札 中の残りのカード数や、ヒントから推論できるカードの詳細情報など、利用にコストがかかるもの ◼ 個別のエージェントの確率的な探索の導入により、不安定になった信念のベイズ推論を 解決するため、学習中に環境に対して実行される行動と単に他のエージェントの入力と なる行動の二つを利用 ◼ 「Simplified」の名の通り、手法は非常にシンプルで簡潔な発想 Shota Imai | The University of Tokyo 36

SADで登場する概念と記号定義 ◼ 𝜏𝑡 ：環境の行動-状態履歴 ◼ 𝜏𝑡𝑎：エージェントaの行動-観測履歴 ※SADのエージェントにはRNNを使用 ◼ 𝐵(𝜏𝑡 )環境の履歴に関する信念 ◼ SADにおける推論 ◼ BADの時と同じく、自分の参照できる情報（自分の履歴）と相手の行動を観測したとき、 自分が見えない環境の情報𝜏を推論する機構（心の理論部分）を表現 Shota Imai | The University of Tokyo 37

公開情報を使わないことによる問題 ◼ 個別のRNNエージェントは学習中に、ε-greedy探索を採用 ◼ 各エージェントの行動は、確率εでランダムに実行された行動かもしれず、信念状態の 更新に利用するのは妥当ではない （ランダムな行動は環境の状態に関する情報を含まない） ◼ ε-greedy探索を行う場合の方策の表現 ′ ◼ 𝑢∗ (𝜏𝑡 )はgreedyな行動、 𝑢∗ 𝜏𝑡 = 𝑎𝑟𝑔𝑚𝑎𝑥 𝑢 𝑄𝑎 (𝑢, 𝑂(𝑎 ′ , 𝜏𝑡 ))、𝑰は指示関数 ◼ 上記を信念の推論に適用すると、計算困難 Shota Imai | The University of Tokyo 38

SADのアイディア 39 ◼ 学習中に、エージェントは２種類の行動を実行する - 𝒖𝒂：実際に環境に対して実行されるアクション（greedyかランダム選択かは問わない） →ベイズ推論・更新にとっては邪魔だが、探索のため必要 - 𝒖∗ ：greedy（行動価値が最も高い）な行動。ε-greedy探索だとεの確率で実行されない →これのみを実行すると探索が進まないが、本来はベイズ推論・更新に必要なアクション 上記のうち𝒖𝒂 はそのまま環境に対して実行。そして、 𝒖∗ については環境に対して実行せず、他 のエージェントの観測の入力のみに使用 ◼ 本来は最適でなかった行動𝒖𝒂 を実行した後「俺は本当は行動𝒖∗ をやりたかった」とメッセー ジを送るイメージ ◼ テスト時はεの値が0で、 𝒖𝒂 と𝒖 ∗ は常に一致するため、行動を送信する必要はない Shota Imai | The University of Tokyo

実験 40 ◼ SADと他のMARLのRNNを使う手法を、二人以上のプレイヤーによるHanabiで評価 ◼ 強化学習はDQNベース ◼ BADより高パフォーマンス&二人以上のゲームでもほぼSOTA Shota Imai | The University of Tokyo

その他の心の理論周りの話題 ◼ ロボット&Visual observation✖️心の理論 Visual behavior modelling for robotic theory of mind - 実機ロボットの軌道の観測から別の時間の観測を予測できるか ◼ 言語✖️心の理論 Few-shot Language Coordination by Modeling Theory of Mind - 指示ゲームで、相手の言語認識レベルに応じた指示を行えるか ◼ 実験的な人間の知能との関連性 Negotiating with other minds: the role of recursive theory of mind in negotiation with incomplete information - 人間のレベルK理論では、レベル2の推論を行うのがちょうどいいとされているが、機械的な エージェントではどの程度のレベルが最適か実験的に明らかに - 機械的なエージェントのシミュレーションでもレベル2程度を採用すると一番効率がよい Shota Imai | The University of Tokyo 41

参考文献 42 ◼ Opponent modeling - - H. He, J. Boyd-Graber, K. Kwok, H.D. III, Opponent modeling in deep reinforcement learning, in: Proceedings of the International Conference on Machine Learning (ICML), 2016. R. Raileanu, E. Denton, A. Szlam, R. Fergus, Modeling Others using Oneself in Multi-Agent Reinforcement Learning., in: International Conference on Machine Learning, 2018. 12, 15, 22, 28 Z.-W. Hong, S.-Y. Su, T.-Y. Shann, Y.-H. Chang, C.-Y. Lee, A Deep Policy Inference Q-Network for MultiAgent Systems, in: International Conference on Autonomous Agents and Multiagent Systems, 2018. 12, 15, 22, 23, 27, 28 [169] M. Lanctot, V. F. Z ◼ 心の理論（心理学・行動科学） - D. Premack, G. Woodruff, Does the chimpanzee have a theory of mind? Behav. Brain Sci. 1 (1978) 515–526 C. Camerer, T. Ho, J. Chong, A cognitive hierarchy model of games, Q. J. Econ. 119 (3) (2004) 861–898. H. de Weerd, R. Verbrugge, B. Verheij, How much does it help to know what she knows you know? An agent-based simulation study, Artif. Intell. 199 (2013) 67–92. 川越敏司（2010）：行動ゲーム理論入門, NTT出版 子安増生、郷式徹（2016）：心の理論 第２世代の研究へ, 新曜社 西野成昭, 花木伸行（2021）：マルチエージェントからの行動科学：実験経済学からのアプローチ, コロナ社 ◼ 心の理論（機械学習） - - - Bard, N., Foerster, J. N., Chandar, S., Burch, N., Lanctot, M., Song, H. F., Parisotto, E., Dumoulin, V., Moitra, S., Hughes, E., et al. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 280:103216, 2020. Foerster, J., Song, F., Hughes, E., Burch, N., Dunning, I., Whiteson, S., Botvinick, M., and Bowling, M. Bayesian action decoder for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 1942–1951. PMLR, 2019. Hu, H. and Foerster, J. N. Simplified action decoder for deep multi-agent reinforcement learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. Hu, H., Peysakhovich, A., Lerer, A., and Foerster, J. “otherplay”for zero-shot coordination. In Proceedings of Machine Learning and Systems 2020, pp. 9396–9407. 2020. N. C. Rabinowitz, F. Perbet, H. F. Song, C. Zhang, S. M. A. Eslami, M. Botvinick, Machine Theory of Mind., in: International Conference on Machine Learning, Stockholm, Sweden, 2018. 12, 15, 24, 28 Shota Imai | The University of Tokyo