2018-12-15

反証的な複数エージェントの強化学習を読む

複数エージェントの強化学習の論文を読むと必ず参照される「反証的複数エージェントモデル」(Counterfactual Multi-Agent：COMA)の論文を読んでみた。

[1705.08926] Counterfactual Multi-Agent Policy Gradients

表題にある反証的(counterfactual)とは、複数エージェントの一員として自分の行動の寄与を計算するため、協調した場合と非協調の場合の比較を行っており、この比較を反証的と称している。

この論文のもう一つ価値としては、Suttonの単独エージェントでの方策勾配法(Policy gradient)の理論を複数エージェントに拡張して数学的に正しいことを証明している点にある。

COMAでは複数エージェントでのActor-Critic方式を以下で構築している。

　Actor：非中央制御型　各エージェントの反証的価値 $A^c$ から方策のパラメータ $\theta^\pi$ を計算

　Critic：中央制御型　各エージェントの状態を統合して、 $TD(\lambda)$ 法でQ価値関数を算出するパラメータ $\theta^c$ の計算と各エージェントの反証的価値 $A^a$ を計算

下図の全体構成ではCriticは環境からは状態と報酬を得て、また各エージェントのActorから次の最適協調行動 $u^a$ と方策関数 $\pi$ を受取り、反証的価値 $A^a$ をActorに戻している。各エージェントのActorは反証的価値 $A^a$ 及び部分観察 $o^a$ を得て最適行動 $u^a$ を求めている。ここで大事なのはActorはGRU(Gated reccurent unit)の時系列モデルを採用しており、時系列の隠れ変数 $h$ を更新していることである。

f:id:mabonki0725:20181215165519p:plain — COMAの全体構成

①方策勾配法（Actorロジック）

　論文ではSuttonの方策勾配法での勾配 $g$ は以下で示されている。

　　 $g=\mathbb{E}_{s_{0:\infty},u_{0:\infty}} [ \sum_{t=0}^T R_t \nabla_{\theta^\pi} \log \pi(u_t|s_t)]$ (1)

　ここで

　　　 $s_t$ は状態

　 $u_t$ は行動（一般的には $a$ を使うが複数エージェントの場合は $u$ で表記する)

　　　 $\pi$ は方策

$t$ 時点の平均報酬 $J_t$ を使うと式(1)は以下の式A～Eの手続きで式(1)を示せる。

　 $J_t = \mathbb{E}_\pi [R_t] = \sum_{s_t}d(s_t) \sum_{u_t} \pi(u_t|s_t) R_t$ 　　式A

　ここで　 $d(s_t)$ は状況 $s_t$ になる確率

これを使うと(1)式は以下に変形できる。

　 $g=\mathbb{E}_{s_{0:\infty},u_{0:\infty}} [ \sum_t^T \nabla_{\theta^\pi} J_t$ ] 　式B

　式Aを $\theta^\pi$ で微分すると

　 $\nabla_{\theta^\pi} J_t = \sum_{s_t}d(s_t) \sum_{u_t} \nabla_{\theta^\pi} \pi(u_t|s_t)$ 　　式 C

　ところで対数の微分公式を使って

　 $\nabla_{\theta^\pi} \log \pi(u_t|s_t) = \frac{1}{\pi(u_t|s_t)} \nabla_{\theta^\pi} \pi(u_t|s_t)$

　両辺を $\pi(u_t|s_t)$ を乗じると以下となる。

　 $\nabla_{\theta^\pi} \pi(u_t|s_t) = \pi(u_t|s_t) \nabla_{\theta^\pi} \log \pi(u_t|s_t)$

　上式を式Cに代入すると

　　 $\nabla J_{\theta^\pi} = \sum_{s_t}d(s_t) \sum_{u_t} \pi(u_t|s_t) \nabla_{\theta^\pi} \log \pi(u_t|s_t)$ 　　式D

　ここで次の確率の総和は１であることを使うと

　　 $\sum_{s_t}d(s_t) \sum_{u_t} \pi(u_t|s_t) = 1$

　以下となる。

　　 $\nabla J_{\theta^\pi} = \nabla_{\theta^\pi} \log \pi(u_t|s_t)$ 式E　

　一方式Bは以下なので

　 $g=\mathbb{E}_{s_{0:\infty},u_{0:\infty}} [\sum_t^T R_t \nabla J_{\theta^\pi}]$

式Eを式Bに代入すると式(1)が示せた。

②反証的ロジックによる価値 $R_t$ の設定

複数のエージェントがあり、特定のエージェントの全体に対して寄与度を計測できれば、特定エージェントが採った行動について全体に及ぼす価値を計算することができる。即ち、特定のエージェントが協調に反する行動を起こした場合の価値関数を反証的として求めて、協調行動との差を寄与度 $A^a(s,\vec{u})$ とする方法である。

　Suttonの方策勾配の $R_t$ は何を使ってもよいことが知られており、本論文でもlemma1でこの証明がある。 $R_t$ は価値関数とベースラインとの差を使う場合が多い。ベースラインを使うのは $R_t$ の大きな変動を抑止するためである。

　　 $R_t = Q(s_t,u_t) - b(s_t)$

本論文では反証的な寄与度 $A^a(st,\vec{u})$ を使う。

　　 $R_t = A^a(s,\vec{u}) =Q(s,\vec{u}) - \sum_{u'^a} \pi^a(u'^a|\tau^a) Q(s,(\vec{u}^{-a},u'^a)$ 　　(4)

上式で分る様にベースラインは反証的な価値関数となっている。

　　 $bs(s_t) = \sum_{u'^a} \pi^a(u'^a|\tau^a) Q(s,(\vec{u}^{-a},u'^a)$

論文には記述していないが式(４)で $\pi(u|s)$ の代わりに $\pi^a(u|\tau^a)$ を使うのは、複数エージェントモデルでは全体的な状況 $s$ よりも個別エージェントが把握している経路 $\tau$ の方が適切と考えられる。

下図の様にCOMAでは各エージェント毎に方策勾配法で求めるパラメータ $\theta^\pi$ を計算するのにGRU(gated Reccurent Unit)を使って時系列の影響を反映できる様にしている。

f:id:mabonki0725:20181215172346p:plain — GRUを使ったActorのモデル

③価値関数のパラメータ最適化（Criticロジック）

Criticは中央制御型なので、COMAではSuttonの教科書通りの単体エージェント型の $TD(\lambda)$ 法によって全エージェントの情報(features)を集めて次の損失関数 $\mathcal{L}_t$ を最小にするパラメータ $\theta^c$ 計算している。

　 $\mathcal{L}_t = (y^{(\lambda)} - Q(features_t,\theta^c))^2$

$y{(\lambda)} = (1-\lambda) \sum_{n=1}^{n-1} \lambda A^{n-1} G_t^{(n)}$

$G_t^{(n)} = \sum_{i=1}^n \gamma^(n-1) r_{t+i} + \gamma^n Q(features_{t+n},\theta^c)$

ここで　

　 $\gamma$ は割引係数　

　 $r_t$ はｔ時点の全エージェントで獲得した報酬

f:id:mabonki0725:20181216093559p:plain — Figure of Sutton's TD(λ)

次にCOMAのCriticでは全体の価値関数 $Q(s,\vec{u})$ から各エージェント毎に式(4)の反証的ロジックより各エージェントの価値を $A^a(s,\vec{u})$ を計算する。

f:id:mabonki0725:20181215172725p:plain — Criticモデル

上図での $o_{t'}^a$ は各エージェントの部分観察を示している。これも本論文で記述していないが価値関数 $Q(s,\vec{u})$ は便宜的な記述で、本来は全エージェントが観察できる特徴量を使った $Q(features;\theta^c)$ が正しいと考えられる。

④チーム対チーム型ゲームStarCraftでのCOMAの実験

StarCraft環境ではチーム対戦（攻撃、回避、待機）をする。自己チームはCOMAモデルで動作するが対戦相手はStarCraftが用意している経験ルールに基づいた動作をする。

COMAの性能実験では下図の様に対戦相手を認識する範囲を故意に設けている。これは部分観察データを使うためと、近接戦に限定することで方策の探査空間を狭めるためである。下図では２匹の竜と３匹のzealosでチームを構成している。

f:id:mabonki0725:20181215200841p:plain — Starcraftでの近接戦範囲の設定

⑤StarCraftでの実験結果

COMAで採用した方法の効果の確認のためモデル比較している。

　(1) Criticで中央制御型の採用　

　　IAC-V：ActorもCriticも非中央制御型(協調行動しない）でQ関数を計算

　　IAC-Q：ActorもCriticも非中央制御型(協調行動しない）でV関数を計算

但しIACの深層学習の最終層は同じパラメータを使用している。

(2) Q関数の採用

　　central-V：Criticは中央制御型でQ関数の代わりにV関数を使用

　(3) Actorで行動価値評価にの反証的方法を採用

　　central-VQ：Criticは中央制御型でActorの行動の価値評価に $Q(s,\vec{u}) -V(s)$ を使用

　下図では縦軸に勝率、横軸に訓練回数をしめしてありチームの編成が異なる。各方法の薄い色は実験結果の変動１σの範囲を示し、実線は平均である。

　3mは3人の海兵隊　5mは５人の海兵隊　5wは5人の生霊(wraith) 2d_3zは２匹の竜に３匹のZealosである。

　なおheuristicは経験的なルールによる行動での勝率を示す。

f:id:mabonki0725:20181215202031p:plain — StarCraftでのCOMAの性能比較

　図(a)の3mでは非協調型のIAC型の性能が悪く中央制御型による協調行動が有意なことが分る。

　図(b)の5mではIAC型も学習が進めば差が出ない。論文に記述はないが５人だと協調行動の必要性が少なくなると考えられる。

　図(d)の2d_3zは異なる種のチーム編成であり、特徴を生かした協調行動が有意なことを示している。

下表のheur(経験的なルールで行動）で判明する様に接近戦が遠隔戦（遠くから攻撃する）より勝つことが難しいことを示している。またGMEZOは中央制御型で記録保持モデルである。

f:id:mabonki0725:20181215211735p:plain — 接近戦と遠隔戦での勝率比較

2018-11-25

複数エージェント間の均衡を図る強化学習の論文を読む

AI論文

年初に発表された複数エージェントでの協調や敵対学習で画期的な性能を示したAbbeel達のモデル(MADDPG)があり、これには動画やGitHubにソースが公開されているので、様々な改良を加えた研究の成果がこれから発表されると思われる。

複数エージェントの協調学習に成功している論文を読む - mabonki0725の日記

この論文は上記のモデルにエージェント間の均衡を加えて、いち早く発表したものである。

[1810.09206] Multi-Agent Actor-Critic with Generative Cooperative Policy Network

この論文の著者は韓国人で、この様にすばやく発表できるのは韓国人の英語力が日本人より勝っている要因も大きいと思われる。

日本でもGMOの勝田さんのMADDPGを改変して集団行動を模擬した秀逸な実験があるが、まだ論文として発表されていないのが残念である。

深層強化学習でマルチエージェント学習（前篇）

深層強化学習でマルチエージェント学習（後篇）

・モデル

この論文の考え方は単純で、非中央制御型のモデルでは、自分のみ最適行動を採るため全体の均衡が崩れるので、同時に自分以外の他のエージェントの最適行動も組込み協調しようとするものである。これを複数エージェント間の均衡と称している。下図の左が従来のMADDPGで右が提案手法で、互いに相手の方策 $\mu^c$ を改善している様子が示されている。

f:id:mabonki0725:20181124200148p:plain

MADDPGは決定論的方策DPG(Deteminisic Policy Gradient)の改善を以下の様にサンプリングしてバッチ $D$ の平均で行うが

$\nabla_{\theta_i} \mathcal{J}(\theta_i) \approx \mathbb{E}_{\vec{o},a \sim D} [\nabla_{\theta_i} \mu_i(o_i) \nabla_{a_i} Q(\vec{o},a_1 \dots a_N;\phi_i) | a_i = \mu_i(o_i;\theta_i) ]$
本論文の均衡側の方策 $\mu^c$ は自分以外 $\{-i\}$ を以下で改善している。上記と比較してMADDPGと殆ど同じなので実装も簡単と思われる。

$\nabla_{\theta_i^c} \mathcal{J}(\theta_i^c) \approx \mathbb{E}_{\vec{o},a^c \sim D^c} [\nabla_{\theta_i^c} \mu_i^c(o_i) \nabla_{a_i^c} \color{red}{Q_{-i}}(\vec{o},a_1^c \dots a_N^c;\phi_i) | a_i^c = \mu_i^c(o_i;\theta_i^c) ]$

ここで

　 $\phi_i$ は自分のCriticで求められた最適パラメータ

　 $\theta_i$ は自分の決定的方策 $\mu_i$ のパラメータ

$\theta_i^c$ は相手の決定的方策 $\mu_i^c$ のパラメータ

$o_i$ は自分の観察状態

　 $\vec{o} = \{o_1 \dots o_n\}$

$D^c$ は相手方策のサンプリングのバッチデータ

・実験結果

　ここでは２つの実験をしている。

１番目はMADDPGの動画で迫力があった、障害物がある環境で素早い動きをする獲物(うさぎ）を２匹の捕食者（猟犬）が協力して追い詰める実験である。

　　　　　　　　　　　 f:id:mabonki0725:20181125084129p:plain

結果は猟犬が報酬を共有する場合(a)と共有しない場合(b)で示されている。報酬を共有する場合はMADDPGと本論文の結果(MADDPG-GCPN1,2)と殆ど変わらない。しかし報酬を共有しない場合は、互いの方策を改良し合うことで有効協調をできることを示している。

ここで

　MADDPG-GCPN１：相手の方策をサンプルからランダムに採用

　MADDPG-GCPN2 ：相手の方策をサンプル全体で均等化

f:id:mabonki0725:20181125084351p:plain

２番目の実験は、エネルギー蓄積システムESSの効率化である。

日本では馴染みがないが、広大な国土では送伝網が伸びると送伝損失があり無視できないらしく、そこで分散された貯蓄設備を作って需要や風力発電の状態に従って効率的に利用しようとするものである。

$B^i$ はESS　 $L^i$ は供給先 $W^i$ は風力発電 $G$ は供給会社　　　　　 f:id:mabonki0725:20181125090146p:plain

本論文のモデルは互いに相手の方策を最適化することなので、他のESSの充足状態を監視して蓄積することができる。左はコストの比較　右は供給量のグラフで効率よくESSに供給していることがわかる。ここではMADDPGとの比較が無く不自然である。QPは２次計画法を示す。

f:id:mabonki0725:20181125090609p:plain

この論文の方法が相手の方策を改良することの効果を入れているが、相手の価値関数 $Q_{-1}$ も知っていることが前提であり、MADDPGの非中央制御型の改善になっているか判断が難しい。

2018-11-22

位置関係を畳込で抽象化した複数エージェントの論文を読む

IBMの恐神先生の複数エージェントの講演で出会った知人から、この講演の様にマルチエージェントの動作を動画と捉えConvolutionして特徴抽出するモデルが注目されていると聞いたが、この論文も複数エージェントの動作を動態グラフと見做してConvolutionで特徴抽出して学習する強化学習となっている。

[1810.09202] Graph Convolutional Reinforcement Learning for Multi-Agent Cooperation

著者の所属は北京大学で、私の理解力不足もあるが、中国本土の論文は未だ成熟途中で漠然とした記述が多いので解釈が難しい場合がある。

最近の複数エージェントは各エージェント毎に内部モデルを保持しているので、エージェントは増やしても数十個が限界である。一方この論文の方式は近傍のエージェント間のみを取出してエージェント間の関係をグラフにしており、各エージェントはこの共通のグラフを用いているのでエージェントの増加に耐えられると(scalable)している。

・モデル

エージェント間の関係は下図の様に２回のConvolutionでエージェント間の関係の特徴抽出を行い、この結果をＱネットワークに投入してＱ関数を精緻化する強化学習を行っている。

f:id:mabonki0725:20181122101640p:plain

ここで最下段の $O_i'$ は各エージェントの観察状態であり、明確な記述はないが

下図の様に近傍行列と各エージェントの特徴量行列の積と思われる。この図ではi番目のエージェントの近傍が３エージェントに限定されており特徴量行列が３行に縮約されている。

このモデルは上図のConvolutionネットワークは共有しているが、各エージェント毎に近傍行列が異なり、異なるＱ関数を保持しているので、この意味では非中央制御型と見えるが、後述のQ関数のパラメータ $\theta$ の算出式を見ると中央制御型のモデルである。偶々高い報酬が得られた場合を有利な協調行動として学習するモデルとなっている。

f:id:mabonki0725:20181122102123p:plain

縮約された各エージェントの特徴量は一層目のネットワークで交差されて、上図の様の式の様に複数エージェントの特徴量が抽象化されてた特徴量 $h'$ として計算される。

　 $h_i' = \sigma ( \frac{1}{M} \sum_{m=1}^M \sum_{j \in \epsilon_i} \alpha_{ij}^m W_v^M h_j )$

$\alpha_{ij} = \frac{\exp(\tau [W_q h_i \dot (W_k h_j)^T])} {\sum_{e \in \epsilon_i }\exp(\tau [W_q h_i \dot (W_k h_e)^T])}$

ここで

　　 $\sigma$ はreluを採用している

$M$ は特徴量の数

　　 $W_v^m$ は特徴量の重み

$h_j w_k w_q$ はネットワークの隠れ変数と重み

$\tau$ はスケールパラメータ

論文には記述が無いがＱ関数は抽象化された特徴量 $h'$ とパラメータ $\theta$ よりＱネットワークで最適化されており、この学習は報酬 $r$ の結果と各々のパラメータ $\theta_i$ を微分して最適解を算出しているはずである。 $W_v^m$ も $w_k$ も微分可能な重みなので、Ｑ関数はＱネットワークとConvolutionネットワークの両方で最適に学習されていることになる。

これも記述が無いが、このモデルは多層構造で、層毎に同じ抽象化をしていて $h' \to h''$ で $h''$ をＱネットワークに投入している様だ。

Ｑ関数のパラメータ $\theta$ は一般のTD式で改善される。実際にはＱネットワークで計算される。

　 $\mathcal{L}(\theta) = \frac{1}{S} \sum_S \frac{1}{N} \sum_{i=1}^N (y_i - Q(O_i,a_i;\theta))^2$

$y_i = r_i + \gamma max_{a'} Q(O_i',a_i';\theta')$

ここで

$S$ はサンプル数

　　 $N$ はエージェントの数

　　ダッシュは1step後の値

　この式を見る限り、Qネットワークは全エージェントの得点とQ関数を使っているので、中央制御型である。

この論文では２つの緩和をしている。一つ目は緩和パラメータ $\beta$ を入れている。

　　 $\theta' = \beta \theta + (1 - \beta) \theta'$

２つめは正則化パラメータの投入している。

$\mathcal{L}(\theta) = \frac{1}{S} \sum_S \frac{1}{N} \sum_{i=1}^N (y_i - Q(O_i,a_i;\theta))^2 + \lambda \mathcal{D}_{KL} (\mathcal{G}^k(O_i;\theta || z_i)$ 　

ここで

　　 $\mathcal{G}^k(O_i,\theta)_j$ は $k$ 層目の $\alpha_{ij}$

　 $z_i=\mathcal{G}^k(O_i',\theta)$

で1step後の状態 $Q_i Q_i'$ とで $\alpha_{ij}$ に差が出ない様にしている。

・実験

　ここでは３つの実験をして性能を比較している。いずれも20エージェント　12特徴量で行っている。近傍の認識はK=3個となっている。

　 (1) jungle :他のエージェントを攻撃すると＋２点　食料を得ると＋１　攻撃されると-1点

(2) battle :敵を倒すと+5点敵に倒されると -2点

(3) packt通信 : 通信に成功すると+10点　接続するだけだと -0.2点

f:id:mabonki0725:20181122122017p:plain

・結果

　本論文の手法がDGN(Deep Graph Network?）と DGN-Mは平均カーネル付きとあるだけで記述なし。DGN-Rは正則化を入れたモデルである比較対象は以下である。

　MFQ:Mean Field Q-learning

commNet:

DQN:

f:id:mabonki0725:20181122122721p:plain

何れもDQNやcommNetに比べDGN-MやDGN-Rが高い性能を示している。中央のBattleでDQNの性能が急激に劣化するのは、安易に倒す先が消化されると、それ以上学習ができないためとある。

2018-11-15

共有知識での複数エージェントの強化学習の論文を読む

国際学会での発表の準備で忙しかったが、ようやく複数エージェントでの共通知識による強化学習(MACKRL)の論文を読んだ。

[1810.11702] Multi-Agent Common Knowledge Reinforcement Learning

これは下図の様に相手が見えるＡとＢは、互いに密接に連絡し合う事を前提に共通の視野を持ち協調行動をする強化学習である。この場合ＣはＡとＢが見えるがＡやＢはＣが見えないので共同行動できない。

また互いに見える範囲では一体として動けるので中央制御型(Centlise)の方策を学習することができる。

f:id:mabonki0725:20181113110236p:plain

本論文の式定義が複雑で解りにくいが、凡そ次の事を述べている。

このモデルには階層型の方策学習を採用しており次の３段階の順に学習し行動する。

(1) 最適な相手を選ぶ方策学習　

(2) グループ内での中央制御型最適方策

(3) 各エージェント毎での最適方策

f:id:mabonki0725:20181115123100p:plain

上図では左端が最適な相手を探す学習、中央が共同行動の学習、右端が個別行動の学習

文献にはこの３段階の学習はActor-Criticで学習しているとある。

本論文の特徴は各エージェントが中央制御型と非中央制御型の方策を両方をActor-Criticで学習することにある。結果で述べている様に各エージェントの特性が異なる場合には有効な方法かもしれない。

・結果

実験ではStarCraftⅡを使っている。

DeepMindのグループ対戦型ゲームの強化学習の論文を読む - mabonki0725の日記

結果では完全中央制御型モデル(Cental-V)とで勝率での比較を示している。

左図は３人の海兵隊が同じ地図を持ち協調している結果で本論のMACKRLと殆ど差が無い。

右図は２人(Stalkers)と３人(Zealos)が異なるタイプで５人で協調している結果で、この共通知識型での協調学習が良い事を示している。

f:id:mabonki0725:20181115123616p:plain

Stalkers や Zealotsはネットで調べると次の様だ。

f:id:mabonki0725:20181115124658p:plain

stalkers

f:id:mabonki0725:20181115124512p:plain

zealots

2018-11-01

相手への影響を報酬の一部とした協調強化学習の論文を読む

AI論文

エージェントの相互の影響を反映した社会的動機による協調強化学習と訳せばいいのか、次のタイトルの論文を読む。

[1810.08647v1] Intrinsic Social Motivation via Causal Influence in Multi-Agent RL

相手の行動と自分の内部状態を因果として次の行動を決定することを因果的影響(causal influence)と云い、これを報酬の一部とすることで協調学習を達成しようとしている。

各エージェントの強化学習は一般のA3Cを採用しており、エージェントの内部状態はLSTMの隠れ変数としており、内部状態はLSTMで遷移する。

要するに複数エージェント間の因果的影響の量を計り、これを報酬とした場合、偶々うまく行けば（得点が多く入る等）この方策を採用する様にA3Cで学習しようとするものである。外から見ればこのエージェント間の因果的影響による行動は協調して働いて(得点を稼いで)いると見える。

・手法

k番目のエージェントの報酬 $R^k$ を以下のパラメータ $\alpha,\beta$ で分離している。

　 $R^k = \alpha E^ + \beta I^k$

　ここで $E^k$ は実際の報酬　 $I^k$ は因果的影響の報酬

下図の様な２つのAとＢエージェントの場合で説明すると

f:id:mabonki0725:20181101180349p:plain

エージェントAの因果的報酬 $I^A$ はエージェントAによる行動 $a^A$ の有無でエージェントBによる行動の $a^B$ が採る確率分布の距離 $\mathcal{D}_{KL}$ を使っている。

　 $I_t^A =\mathcal{D}_{KL} [ p(a_t^B | a_t^A,z_t) || \sum_{a_t^A} p(a_t^B | z_t,a_t^A) p(a_t^A | z_t) ] = \mathcal{D}_{KL} [p(a_t^B | a_t^A,z_t) || p(a_t^B | z_t) ]$

ここで $z_t =\ll u_t^B, s_t^B \gg$ はエージェントＢの内部と外部の状態である。

この式の数理的な正しさはエージェント間の相互情報量からも証明できる。即ちエージェントＡの全行動 $a^A$ と因果的影響 $I^A$ の積和は相互情報量に一致している。

$I(A^B;B^A|z) = \sum_{a^A,a^B} p(a^B,a^A|z) \log \frac{p(a^B,a^A|z}{p(a^B|z) \cdot p(a^A|z)} = \sum_{a^A} p(a^A|z) \mathcal{D}_{KL} [p(a^B|a^A,z) || p(a^B|z) ]$

この論文では因果的影響 $I^A$ は実際のエージェント間の行動履歴のサンプリングから計算するとしている。多分A3Cで得点から学習するにつれて有意な因果的影響の量が増えると思われる。

実際の2エージェントの実験例として２つ(CleanupとHarvest)掲げている。

f:id:mabonki0725:20181102080835p:plain

左図は上部にある川の泥さらいをするとリンゴが生まれ、泥さらいとリンゴの収穫を協調学習をしている。右図はリンゴを植える側と収穫側が協調して学習するものである。何れのゲームも紫の点がエージェントで緑がリンゴである。

両方とも協調しなければ囚人のジレンマの様に両方でリンゴを食いつぶすことになる。

早くて見難いがCleanupの動画としては以下が示されている。

Social influence reward leads to emergent communication in Cleanup game - YouTube

・実験方法

　驚くべきことに実験としては因果的影響を使って以下の３方法の比較をしている。

　1) 協調学習として伝統的な中央制御型(神の視点で全エージェントを協調させる)

2) 因果的影響をメッセージとして他のエージェントに伝える方法

　　Reinfocemented Inter-Agent Learning(RIAL)法による方法との比較

　3) 各エージェントが複数のエージェントの因果的影響を反映した内部状態を持ち、行動を予測する方法

　　Model of Other Agent(MOA)として下図の様にモデル化している

f:id:mabonki0725:20181102103225p:plain

・実験結果

　(a)ではA3Cと中央制御型と因果的影響による比較

　(b)ではA3CとRIALとメッセージに因果的影響を使った比較　

　(c)ではA3CとMOAと因果的影響を反映したMOAとの比較

何れも因果的影響を使った方法が改善されているが、左上のCleanupの中央制御型では学習の立ち上がりが遅い。これは神の視点を入れた手法が優れていることを示しており、やはり協調するには監督の差配が必要だとも言える。

f:id:mabonki0725:20181102104041p:plain

2018-10-28

人間のコントロールで早期に学習する強化学習の論文を読む

AI論文

強化学習は学習に相当時間がかかる事が知られているが、人間が要所々にコントロールして教えれば学習が効果的にきるとの考えを実現した論文である。

[1709.10163] Deep TAMER: Interactive Agent Shaping in High-Dimensional State Spaces

本論文の手法はDeep TAMERと云い概念図は以下である。この論文の特徴は人間のコントロールを深層学習を使って高次元の関数に近似して、これを方策として強化学習に組み込むことである。

f:id:mabonki0725:20181028205726p:plain

この論文を読む動機は下記の記事を見て学習の改善度合いが凄いためであった。

ぼくがかんがえた世界最強のAIをつくるために、アメリカに行ってきた : 情熱のミーム清水亮 - Engadget 日本版

この人間が計算機に教える学習対象はATARIの古典的なボーリングゲームである。

f:id:mabonki0725:20181029085016p:plain

この論文の着想は簡単で、人間のコントロール $h$ を最適な方策 $\pi(s)$ にすることである。しかし最適方策は次の人間の方策理解を示す関数 $\hat{H}(s,a)$ となるものを導入してこれを深層学習で近似する。

$\pi(s) = \hat{H}(s,a)$

この論文での巧妙な現実的な方法は、ゲーム画面と人間のコントロールに遅延があることを許容する遅延関数 $w$ を組込み、方策理解 $\hat{H}$ を次の損失関数で求めていることである。

　 $Loss(\hat{H};x,y) = w(t^s,t^e,t^f) [\hat{H}(s,a) - h ]^2$ 　式(1)

ここで

　 $x$ は画面の状態

　 $y$ はコントロール $h$ を行った後の観察結果

　 $w(t^s,t^e,t^f)$ は遅延関数で $t^s$ と $t^e$ は状態 $s$ の最初と最後の時間

$t^f$ はコントロールしてから結果を見るまでの期間

・遅延関数 $w$

この独特の遅延関数は分布関数 $f_{delay}(t)$ を使って次で定義している。

　 $w(t^s,t^e,t^f) = \int_{t^f-t^e}^{t^f-t^s} f_{delay}(t) dt$

分布関数 $f_{delay}(t)$ はここでは0.25~4の一様関数を採用している。人間の遅延はこの間が多いそうである。

・損失関数 $Loss(\hat{H})$

式(1) の損失関数を解くためにこの論文では次の２種類の最適化を使っている。

　(a) 画面状態 $x,y$ の情報集約

　(b)人間のコントロールのバッチ学習

(a) 情報集約

この $\hat{H}(s,a)$ の損失関数は式(1)から分る様に $x,y$ の教師あり学習になっている。これは深層学習で解いている。しかし画面の状態はかなり数万の高次元なのでAutoEncoder $f(s;\theta_f)$ で次元圧縮して数百次元にして、再度Decode $g(f;\theta_g)$ して画面に戻している。このEncoder Decoderのパラメータは次の関数で最適化している。

$(\theta_f,\theta_g) = arg min_{\theta_f,\theta_g} \frac{1}{M} \sum_{i=1}^M ||s_i - g(f(s_i;\theta_f);\theta_g)||_2^2$

(b)バッファーによるバッチ学習

これも深層学習で以下の人間方策関数 $\hat{H}$ を改善している。

　 $\hat{H}_{k+1} = \hat{H}_k - \eta_k \nabla_{H} Loss(\hat{H}_k; x_{i,k},y_{i,k})$

ここでは画像 $x$ と結果観察 $y$ と人間のコントロール $h$ の1000組程度（ゲームにすると15分程度）をバッファに入れてランダムに取り出して上式を訓練して更新している。

上式の $x_{i,k},y_{i,k}$ は人間のコントロール $h_i$ に対応したランダムに取り出した画面と観察結果である。

但し遅延関数 $w$ が存在しない人間のコントロールは無視している。

・結果

　このゲームに限っては驚異的な学習効率を示している。

勉強不足だったが低次元での人間のコントロールを反映するモデルとしてTAMER(Training an Agent Manually via Evaluation Reinforcement)2009があったそうである。TAMER

しかし本論文での高次元モデルは特徴量を多く取り入れることができ微妙なコントロールも反映でき、低次元での似たコントロールの衝突も回避できる可能性がある。是非ロボットの分野でも使ってもらいたいものである。

f:id:mabonki0725:20181028205502p:plain

2018-10-21

DeepMindのチーム対戦の強化学習の論文を読む

AI論文

DeepMindの複数エージェントのチームでの勝敗による強化学習が人間のレベルを超えており、この理論と実験の詳細な報告になっている。

[1807.01281v1] Human-level performance in first-person multiplayer games with population-based deep reinforcement learning

チームでの勝敗とは自己と敵対チームで互いに相手の陣地の旗を奪い合いするCTF(Capture the flag)ゲームである。ゲーム環境は下図(a)と(b)の様な3D一人視覚(first-person)だが自己チームの一人として学習した行動が見れる様になっている。このゲームには得点が表示されるので、この得点を指針としてチームとしての強化学習を行っている。

f:id:mabonki0725:20181021065229p:plain

この動画は以下で見れる。 (b)の迷路版だと的の陣地に入って旗を奪取して途中で交戦する様子が見れる。

Human-level in first-person multiplayer games with population-based deep RL - YouTube

複数エージェントのモデルとしては、同じチーム内の協調をどの様に理論化することが最大の問題でモデルの特徴になっている。

DeepMindは自己の方策(inner)とチーム全体(outer)との方策とに分けて、次の２式で訓練している。この方式をPBT(Population Based Training)として、各エージェントをFTW(For the Win)と称している。

f:id:mabonki0725:20181021070945p:plain

f:id:mabonki0725:20181021070737p:plain

(1) 式は２チームN人で $\pi_0$ 側が勝つように自己チームの方策を決定することを示している概念的な式である。この式は(2)式の $\mathcal{J}_{outer}$ で使われている。この詳しい理論は論文に添付してあるSupplementary Materialsを読むしかない。

(2)式の $\mathcal{J}_{inner}$ は普通の強化学習の式であるが報酬 $r$ がチームとしての報酬 $W_p(\rho_{p,t})$ となっていいる。このチーム報酬は(2)式の $\mathcal{J}_{outer}$ で算出されるものになっていて複数エージェントの協調化をしている。