2018-12-26

大脳基底核の躊躇機能を模擬した強化学習の論文を読む

強化学習

アルファGoを作ったDeepMindのハザビスは脳科学者として有名であったが、OISTの銅谷先生等は既に2000年に大脳基底核で観察される信号の状態が強化学習のベルマン方程式で表現できるとを示して、生理的な意味でも脳と強化学習は関連が注目されて来た。

globe.asahi.com

今回読んだ論文は、参加できなかったが或るセミナーで紹介されていたもので、大脳基底核で観察される躊躇機能を強化学習に取り込んで成果を上げた報告である。表題には躊躇機能として「Better Safe than Sorry」とある。

[1809.09147] Better Safe than Sorry: Evidence Accumulation Allows for Safe Reinforcement Learning

一般に強化学習では報酬が得られる様に常に行動するが、確信が深まるまで行動を抑制する機能がない。しかし大脳基底核ではこの様な抑制機能が観察されている。これを使うとノイズ多い環境では情報の信頼度を評価できるので既存のA2C-RNN（Advantage Actor clitic)モデルより効率的になるとのアイデアである。

(1) 大脳基底核での躊躇モデル

論文では大脳基底核は下図の情報網としており、躊躇機能はSTR(Striatum)で行われている。

f:id:mabonki0725:20181226170239p:plain — 皮質大脳基底核視床の情報網

STRではDirectの励起信号(D)とIndirectの抑制信号(I)とのバランス(I-D)で下図のB図様に行動の速緩を起こす。(D)が多いと早く行動し、(I)が多くなると遅く行動する様になり、最終的には行動が抑制される。Hyperdirectは図Cの様に行動励起信号の強さに対して行動を抑制する閾値の役目をする。

f:id:mabonki0725:20181226171154p:plain — 信号と行動の関連

上記の仕組みは簡単に表現されているが、複雑な認識を成し遂げる様に数百万個の細胞によって動作しており、高次元の処理をしている事は忘れてはならない。このモデルを模擬するには少なくとも大規模な隠れ変数を使う深層学習を使うべきと考える。やはり後述する様にＢもＣも最終的には深層学習で構築されている。

(2) モデル

論文では行動 $a_i$ の確信度 $\rho^i$ を以下にモデル化している。

　　 $\kappa_t = f(o_t)$ t時点の観察 $o_t$ を根拠ベクトルに変換したもの

$\kappa_t$ は蓄積器に蓄えられ、その総計を根拠情報量とする

$\nu^i = \sum_{t=0} \kappa_t^i$ ：行動 $a_i$ の根拠情報量

$\rho^i = \frac{\exp(\nu^i)}{\sum_{i=1}^A \exp(\nu^i)}$ ：softmaxによる行動 $a_i$ の確信度

　　上式ではノイズが多く根拠情報量 $\nu$ が全て同じ様であれば、確信度 $\rho$ は低くなることを示している。

ここで $f(o_t)$ は観察の根拠変換関数で、後述するが深層学習で求められる。

躊躇のモデル化では制限時間 $T_{max}$ 内に環境から順次根拠 $\kappa_t$ が蓄積器に蓄えられる。蓄積器に貯まった根拠から行動確信度 $\rho$ が計算され閾値 $\tau$ を超える場合に行動する。しかし制限時間内に閾値 $\tau$ を超えないと行動されない。

ここで閾値 $\tau$ も報酬より深層学習で推定される。

この躊躇行動と結果によって以下の報酬を設定している。

f:id:mabonki0725:20181226200745p:plain

ここで $R_1$ は正しい結果では決断が早いほど報酬が高く $R_2$ は罰則である。行動が無い場合でも $R_3$ の報酬がある。

(3) 実験

・モードを推定する課題

　10個の観察データ（例えば顔の写真）の内、ランダムに $n_0$ 番目を選ぶが、乱数 $\epsilon$ で間違いの観察データが得られる場合がある。間違いを含んでいる観察データを貯めて、躊躇機能によって信頼度が高まれば判断を下す方法で、正しく $n_0$ 番目であることを見抜けば次の報酬が得られる。但し $T_{max}$ は30である。

$R_1 = 30$ $R_2 = -30$ $R_3 = -30$

下図はこの課題の状態遷移図で、行動はどの観察データ(モード)かを当てる行為となる。

f:id:mabonki0725:20181226200435p:plain — 課題設定（モードの検出）

この躊躇モデルの真の性能を知るため、次の(a)で示す様に単純に躊躇モデルを10000回繰返したモンテカルロ法を行い、次の(b)～(d)の3モデルで真の値にどの程度学習できるか比較している。

　(a) モンテカルロ法

　　曖昧性 $\epsilon$ を $[0,0.1,0.2,\dots,0.8]$ と変動させ、閾値 $\tau$ も $[0,0.1,0.2,\dots,0.9]$ と変動させ10000回試行させてその躊躇モデルでの報酬の結果を観察する。真の性能は下表の１番目であった。

　(b) A2C-RNN法

　　躊躇機能の代わりに行動に何もしないNoopを追加して、観察データよりA2C-RNNで強化学習を行う。

　　このモデルのパラメータ $\theta$ の推定ではエントロフィの正則化の項を追加した勾配法で計算する。　 $\eta$ $\beta$ はハイパーパラメータ　

f:id:mabonki0725:20181226224248p:plain

　　閾値 $\tau$ を観察データと報酬より深層学習で推定したした方法

　(d) 根拠関数 $f(o_t)$ と閾値 $\tau$ の深層学習モデル

　　閾値 $\tau$ に加え観察データ $o_t$ から根拠関数 $f(o_t)$ も深層学習で学習する

　上記のモデルの学習した結果の報酬は以下であった。A2C-RNNはノイズが多いと各段に劣化していることが分る。

f:id:mabonki0725:20181226204309p:plain — 躊躇モデルの実験比較結果

(4) 評価

　下図の上段は観察データの曖昧性 $\epsilon=0.2$ での性能の改善カーブで、下段は曖昧性 $\epsilon=0.8$ の結果である。（左図：正確度　中央：決断時間　右図：報酬）

　観察データが正確な場合はA2Cや閾値 $\tau$ や根拠関数 $f$ を加えた学習の性能は繰返しを重ねると学習することができる。しかし観察データの曖昧性が多い場合は、学習が難しい事をを示している。

　また下段に示す様に観察データにノイズが多く曖昧性が高い場合、信頼度が高まるまで待つ様な躊躇機能を持つモデルの方が単純なA2C-RNNに比べ優れていることが分る。

f:id:mabonki0725:20181226231524p:plain — 曖昧性と各モデルの性能比較

2018-12-22

ベイズによる複数エージェントの強化学習の論文を読んでみる

強化学習

最近は複数エージェントによる協調学習の理論や実験が著しい進展を遂げており、この方向で様々な研究成果が出現してくると思われる。しかし今回読んでみたベイズによる複数エージェントの強化学習の論文(BADモデル)はこの方向ではなく、カードゲームの様に参加者が秘匿する情報をベイズで推定しようする不完全情報下の最適化モデルと考えられる。論文はベイズモデルなので難解で自分が理解した範囲での記述となってしまった。

[1811.01458] Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learning

ポーカゲームやビジネスの様に秘匿による不完全情報下ではナッシュ均衡状態が最適な状態と考えられ、このナッシュ均衡からの僅かなズレを相手の癖として見破り勝率を上げるモデルが主流である。現在のポーカゲームでは計算機が人間を相手にして凌駕する様になっているが、相当数のゲームを経て計算機がやっと最終的に勝っている状態である（相当数ゲームを行うことで人間が疲れてしまうから勝つとの説がある）。

triblive.com

この論文では、下図の様にゲームで開示されている情報 $s$ の特徴量 $f^{pub}$ と自分だけが知っている(相手には秘匿されている）情報の特徴量 $f^{pri}$ とに区別しており、エージェントが知っている情報の特徴量を $f^a$ としている。行動 $u$ は方策 $\pi$ およびエージェントの特徴量 $f^a$ で $u^a \sim \pi(f^a)$ としてサンプリングされる。

f:id:mabonki0725:20181222112904p:plain

公開情報をモデルに組み込むため、上図を修正して全員で見れる情報での公的信念 $\mathcal{B}$ と、これによる公正な方策 $\pi_{BAD}$ を導入したPubB-MDPモデルを提案している。下図の様に公正な方策からサンプリングされた方策 $\pi^\Delta$ を使ってベイズ推定されたエージェントの特徴量 $f^a$ での行動は $u^a \sim \pi^\Delta(f^a)$ でサンプリングされる。この行動の結果で状態が次に進み $\mathcal{B}'$ と $f'^{pub}$ に更新される。

f:id:mabonki0725:20181222113638p:plain — BAD(Bayesian Action Decoder)モデル

この論文の趣旨は行動 $u^a$ は観察できるので、これから行為者の意図 $f^a$ をベイズの事後分布として推定しようとするものである。即ち不完全情報を推定するモデルとなっている。

$P(\color{red}{f_t^a | u_t^a},\mathcal{B}_t,f_t^{pub},\pi^\Delta) = \frac{P(\color{red}{u_t^a | f_t^a},\pi^\Delta) P(f_t^a | \mathcal{B}_t,f_t^{pub})} {P(u_t^a|B_t,f_t^{pub},\pi^\Delta)}$ (1)

式(1)の赤字部分は $f_t^a$ を $x$ に $u_t^a$ を $y$ にした次のベイズの公式を使っていることがわかる。

　 $P(x | y) = \frac{P(y | x) P(x)}{P(y)}$

ここで

　　 $P(x|y)$ は事後分布

　　 $P(x)$ は事前分布

　　 $P(y|x)$ は尤度

公的方策 $\pi_{BAD}$ は次式で近似される。

　 $\pi_{BAD}(\pi^\Delta \mathcal{B}_t,f^{pub}) \approx \Pi_{f^a} \pi_{BAD} (\pi^\Delta(f^a) | \mathcal{B}_t, f^{pub} ,f^a)$

　右辺の $\pi^\theta_{BAD} (\pi^\Delta(f^a)=u^a | \mathcal{B}_t, f^{pub} ,f^a)$ は $u^a$ を教師データとして深層強化学習で学習される。

　式(1)の事前分布 $P(f_t^a | \mathcal{B}_t,f_t^{pub})$ と尤度関数 $P(u_t^a | f_t^a,\pi^\Delta)$ の推定は自分には理解不能のため省略する。

・実験

BADモデルは公開情報が多い場合が有利なので、ポーカーゲームと間逆のHanabiゲームを使って本論文のBADモデルの有意性を示している。Hanabiゲームはカードの裏が花火の模様で日本語の名称を使っている。このゲームでは各自５枚の札（色と数字が異なる）を持ち、札を出す度に1枚札を引く。およそ次の様なゲームである。

(1)ポーカと反対に、相手の５枚の手札は見えるが、自分の手札は見えない(下図)

(2)ポーカと反対に、全員で協調して手札を７並べの様に色別に数字を順番に場に並べる

(3)自分の札を推定し、場にある同じ色で場の最大数字より大きい札を出さないといけない。できそうとないと判断した場合は札を捨てる事ができる。

　失敗すると罰コインを与えられる。罰コインが３個貯まるとゲーム終了となる。

　成功すると報酬コインを貰える。

(4)相手にヒントを与えて、ヒントコインを出し自分の手札を推定させることができる

(5)全ての色と数字が順番に揃えば終了である。

f:id:mabonki0725:20181222185033p:plain — Each player observes hands of other player,but not their own.

・実験結果

モデルの比較対象としてLSTMを使っている。これはカードゲームの手順での時系列的な特性を反映するためである。

V0-LSTM：ヒントと見えているカードのみで自分のカード推定したLSTMモデル

V1-LSTM：V0-LSTMを繰返し適用して収束させたLSTMモデル

BAD：本論文のモデル

f:id:mabonki0725:20181222220415p:plain — performance in Hanabi game

　上図はBADの優位性を示しているが、LSTMを使った簡便な推定モデルV0-LSTMと相違が少ない。実験に選んだHANABIゲームが複雑なため、ベイズ手法によるモデル化が難しくBADモデルの特性を生かせなかったと推察される。

2018-12-18

高速道路での複数車の協調学習の論文を読む

強化学習

高速道路での協調学習として転移学習を使っている表題に引かれて論文を読んでみた。

著者はドイツ南部のFreiburg大学の人々の様だ。

[1810.08515v1] Transfer Learning versus Multi-agent Learning regarding Distributed Decision-Making in Highway Traffic

これは高速道路で複数車が協調して走行する学習として、転移学習と複数エージェントの強化学習の比較に見えるが、以下の事をしている。何れも報酬は協調して安全範囲を保持して車のスピードが高ければ報酬が高い。

ここで注意すべきは本論文で云う転移学習は単一エージェントの学習結果であるパラメータを他のエージェントに複写していることで、一般的な転移学習では無い。

一般に転移学習は、データの特徴は似ているが分布状態が異なる領域への学習を言う。

(1)転移学習と云っているモデル(ANNcore)

　複数車の存在を環境の一部として単独エージェントの強化学習を行う。このパラメータを結果を全ての車に反映させる。

(2) 複数エージェントの強化学習モデル(ANNshare)

　中央制御型で協調学習させ、このパラメータを全車に配分する。

両学習モデルもDQNを使っており、一般的な転移学習でも無いし、非中央制御型の複数エージェントの強化学習でも無く新規性が乏しい。

実験ではMITの高速道路での強化学習用のプラットフォームを用意している。

selfdrivingcars.mit.edu

(1) 転移学習と称している学習

　下図の左の様に他車を環境の一部として白い範囲を保ちながら速度を上げる様に単独で学習する。このモデルをANNcoreと云い学習結果のパラメータを右図の様に複写して、見かけ上互いに牽制し合うモデルとなっている。

f:id:mabonki0725:20181217141712p:plain — 転移学習と称しているモデル

(2) 複数エージェントの強化学習

　協調する車どうしが連携を採って白いセルの範囲を保ちながら速度を上げる様に中央制御型で強化学習をするモデル(ANNshareと云う)である。各車の状態と報酬とで各車の状態が最適になる様に協調行動させているが、この学習結果のパラメータも下図の様に複写して各車が独自で動作させ、折角学習した中央制御型の協調行動を成り立たなくしている。

f:id:mabonki0725:20181217141826p:plain — 複数エージェントモデルと称しているモデル

・MITの模擬環境での実験結果

　この強化学習には状態 $x$ や行動 $a$ 以外に18個のハイパーパラメータを使っており下図の様にハイパーパラメータはすぐ収束状況になっている。

f:id:mabonki0725:20181217144637p:plain — パラメータの最適化の学習回数と運行スピード

　下図は協調する車の数と速度の関係である。２台では速度が落ちているが両モデルとも不思議なことに車が増えると速度が漸増している。

　論文にも記述されているが、単独で学習した結果を各車に複写した転移学習モデルと複数エージェントで協調学習した結果を各車に複写した結果は殆ど変わらない。

　これによって分ることは、単独で学習した結果を複写してもある程度協調行動が可能で、複数エージェントで協調学習した結果を複写すると、協調学習の効果を維持できなくなるという事と思われる。

f:id:mabonki0725:20181217144815p:plain — 転移学習（濃灰色）と強化学習(薄灰色)での協調台数と運行スピード

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)$ 　