2018-10-15

他のエージェントとの協調特徴より複数エージェントの強化学習の論文を読む

この論文は他のエージェント間での協調特徴ベクトルで $x_{1 \dots N}$ を深層学習のAttentionで摘出して、最適な協業をする複数エージェントの強化学習モデルである。

[1810.02912] Actor-Attention-Critic for Multi-Agent Reinforcement Learning

次の画期的な性能を示す中央監視(centralized)による複数エージェントの協業モデル(MADDPG)が出現しており、この論文は非現実的な中央監視を解消するため各エージェントが他のエージェントとの関係を深層学習のAttentionで代替するモデルとなっている。

mabonki0725.hatenablog.comこの他のエージェントの協調特徴(Attention)は次の図で説明されている。

f:id:mabonki0725:20181015081102p:plain

左端図:

　①各エージェントの観察 $o_i$ と行動 $a_i$ を深層モデル(MLP)で埋込みベクトル化 $e_i$ する。

　②中央図で求めたAttentionより協調特徴 $x_i$ を得て再度MLPで行動価値 $Q_i(o,a)$ で算出する

　式で記述すると

　 $Q_i^\phi(o,a) = f_i(g_i(o_i,a_i),x_i)$

　 $o = o_1 \dots o_N$ 全エージェントの観察

　 $a = a_i \dots a_N$ 全エージェントの行動

　これにより行動価値関数 $Q_i$ は全エージェントの観察と行動と協調特徴でMLPで求めていることが分かる。

左端図

　①エージェント $i$ とエージェント $j$ との相互間の関係 $\alpha_j$ の重み $W_i W_j$ をSoftMaxで求める

　　 $\alpha_j \propto \exp(e_j^T W_j^T W_i e_i)$

　②特徴行動 $x_i$ を次の2つのMLP $V h$ で算出する

　 $x_i = \sum_{j \notin i} \alpha_j h(V g_j(o_j,a_j))$

中央図

　①左端図を全エージェント分実行して協調特徴 $x_1 \dots x_N$ ベクトルを得る

　但しこの機構は全エージェントで共有する

行動価値関数 $Q_i$ の勾配は報酬に近似させる一般的な方法を採用

　 f:id:mabonki0725:20181015104534p:plain

方策関数の勾配は $\pi_{\theta_i}$ はエントロフィ最大化の一般的な方法で計算　　

　　 f:id:mabonki0725:20181015104817p:plain

　　但し $b(o,a_{j \notin i})$ はベースラインで、これは全エージェントに対して計算する必要があるので計算負荷が大きいとしている。

実験

　実験は２つの協調学習で行っている。

　①多数の灰色の小丸が協調して色がついた点を獲得し、この色と合う大丸に貯蓄する。

　　　 f:id:mabonki0725:20181015105908p:plain

　② 大きい灰色の丸と色付き丸は互いにランダムにペアを組み協調して点を獲得する。一方は回りが観察できないが獲得行動する。もう一方は回りが見えるだけである。双方は連絡し合って点を獲得する。

　　　 f:id:mabonki0725:20181015110242p:plain

結果

　左は①の実験　右は②の実験で本論分の手法はMAAC（水色)と(橙色)　橙色は $\alpha_j=\frac{1}{N}$ として単純化したモデル。中央監視型(MADDPG)は緑色

SACとはSoft Actor Criticによる最適化

　本論文の手法は①に対しては良いが、②に関しては中央監視型に負けているが最終的には追いついている。また実験①で単純化した橙色と水色が同じ性能というのは単純な実験であることを示し。②ではかなり差があるので複雑な実験である事を示している。

f:id:mabonki0725:20181015113504p:plain

　またエージェントが増える場合の報酬の超過度を中央監視型MADDPGと比較して、本手法が優れているとしている。

　　 f:id:mabonki0725:20181015114951p:plain

他のモデルとの比較

　本論文のMAACは他と比べて非中央監視型だということを強調している。ここでMAAC(Uniform)とは上図の橙色のモデル

f:id:mabonki0725:20181015122537p:plain

感想

　エイジェント間の関係を深層学習(MLP)を使ったAttentionで構成しているが、中央監視型の理論と比べてブラックボックスになっていることは否めない。実験②の様により複雑な協調や敵対モデルでは良い結果出せるか判断できない。

2018-10-07

視覚的な転移学習による強化学習の論文を読む

国際大会での発表の準備で疲弊しているが、「もくどく会」があったので途中まで読んでいたATARIゲームの転移学習による強化学習を読む

[1809.00397v1] Visual Transfer between Atari Games using Competitive Reinforcement Learning

この論文はATARIゲームの同じ様な画面の操作で別のゲームで転移学習できないかという話。具体的にはピンポンをブロック崩しに転移学習をした結果の報告

f:id:mabonki0725:20181007191235p:plain

(1) 方法

ここでは両ゲームの抽象化と方向を合わせる前処理を行って特徴量を掴みやすくしている。

この論文では伝統的な転移学習(stage1)と転移のマッピング(stage2)による２方法で結果を比べている。

伝統的な転移学習stage1はCNN層の上位から２層目をピンポンから取り出しブロック崩しのCNN層に入れる方法である。この方法と同様の転移学習には前の記事を思いだした。

mabonki0725.hatenablog.com

(2)実験

Stage2のマッピングによる方法はマッピング関数 $G$ をGANで訓練する方法を採っている。即ちピンポンの画面からブロック崩しの画面を擬似生成して本物らしくなる様に訓練している。この場合画面の抽象化にVAEを用いているとある。

この論文のタイトル競合的(conpetitive)とは、Stage2で本物のブロック崩しの訓練(Naive)とピンポンのマッピングによる訓練（Visual Mapper)を様々な比率で混ぜた訓練を並列型強化学習A3Cで行っている。

f:id:mabonki0725:20181007193120p:plain

(3) 結果

・伝統的な転移学習stage1ではピンポンでの訓練した上位から２番目層を入れた方が最初から訓練するより良い当然の結果になっている。

f:id:mabonki0725:20181007193513p:plain

・Stage2のマッピングを用いた競合的転移学習の結果

左上のN:MはNaiveとVisual Mappingの比率

Naiveを多めにした方が良い結果で転移学習が多いと標準より劣化する。これはデータ分析全般に言えることだが、多少のバリアンスは精度を向上させる事は経験的に確かである。飛躍し過ぎかもしれないが、多民族国家でない日本は皆同じ事を考えるので、アイデアが洗練されず凋落している理由と同じかもしれない。

f:id:mabonki0725:20181007193913p:plain

2018-09-25

敵対的擬似逆強化学習の論文を読む

AI論文ロボテックス

非線形な逆強化学習の最適解を効率的に図るため、擬似的な関数を定義してこれを使って最大最小値問題として、さらに非線形解を解くためGANを導入したモデルである。単なる逆強化学習をここまで複雑にしている論文は見たことがないが、実験結果では驚異的な性能を示している。

[1606.03476] Generative Adversarial Imitation Learning

逆強化学習は熟練者のコスト関数の期待値を一致させる方法が一般的だが

$min_{\pi \in \Pi} \mathbb{E}_\pi [c(s,a)] - \mathbb{E}_{\pi_E} [c(s,a) ]$

ここでは逆強化学習を次式で定式化している。

$IRL(c) = max_{c \in C}[min_{\pi \in \Pi} - \mathcal{H}(\pi) + \mathbb{E}_\pi [c(s,a) ] ] - \mathbb{E}_{\pi_{E}} [c(s,a)]$

ここで

　 $c(s,a)$ は行動 $a$ と状況 $s$ でのコスト関数

　 $\mathcal{H}(\pi)=\mathbb{E}_\pi [-\log \pi(a|s) ]$ で方策関数のエントロフィ(正則化項)

　 $\pi_E$ は熟練者の方策　

この逆強化学習の式を次の様に分解すると、式の意味は熟練者の方策のコストを最小にして、熟練者でない最良方策のコストは最大にすることを示している。

　最後の項 $\mathbb{E}_{\pi_{E}} [c(s,a)]$ は熟練者の方策のコストは最小化

　エントロフィ項 $\mathcal{H}(\pi)$ は熟練者でない方策の最適化

　最初の項 $\mathbb{E}_\pi [c(s,a) ]$ は熟練者でない最良方策のコストは最大化

ここで擬似的な方策関数である占有尺度 $\rho_\pi$ (occupancy measure)を定義している。

$\rho_\pi(a|s) = \pi(a|s) \sum_{t=0}^{\infty} \gamma^t P(s_t = s | \pi)$

占有尺度は方策 $\pi$ を採った場合、行動履歴上どれ位状況 $s$ が選択され、その場合行動 $a$ が選択される確率である。

論文では以下が証明されているが、難しいため省略する。

$\pi(a|s) \approx \rho_\pi(a|s)$

$\mathcal{H}(\pi) \approx \mathcal{H}(\rho_\pi)$

結局この最適化には次式を解けばよいことになる。

　 $min_{\rho \in \mathcal{D}} \mathcal{H}(\rho)$ subject to $\rho(s,a) = \rho_E(s,a)$

ここでの最小問題を解くために非線形の $\phi_{GA}*$ 関数を導入する。

　 $\phi_{GA}*(\rho - \rho_E)$

これは熟練者の擬似方策関数 $\rho_E$ と最適化したい方策関数 $\rho$ を一致させればよいのでそこでGAN(Generative Adversarial Network)を使う。

　 $\phi_{GA}* (\rho - \rho_E) = max \mathbb{E}_\pi[\log D(s,a)] + \mathbb{E}_{\pi_E}[\log(1-D) ]$

本論分のアルゴリズムでは２段階でモデルを改善している。

　①Discriminater $\mathcal{D}$ の改善 → GAN アルゴリズム

　②コスト関数c(s,a)の改善　→ TRPO アルゴリズム

実験結果

　水色が本論の手法だが全てのゲームで学習するデータ量に比例せず驚異的な性能を示している。

f:id:mabonki0725:20180925085440p:plain

このモデルの詳しい解説は千葉大の中田さんの資料がある。

Generative Adversarial Imitation Learningの紹介（RLアーキテクチャ勉強会） from Yusuke Nakata

www.slideshare.net

2018-09-24

因果情報量最大化による逆強化学習の論文を読む

AI論文ロボテックス

CMUの因果を取りいれた逆強化学習の発表でかなり古い論文である（2010ICML)。強化学習は時間経過に従って学習するモデルなのでタイムステップ間は完全に因果関係が成立する。熟練者の経路データから因果関係を情報量の最大化で求め次の行動を予測しようとするモデルである。

www.semanticscholar.org

一般にデータからコスト関数を推定するモデルをIOC（Inverse Optimal Control)と云い、統計的な解釈で推定するモデルをIOSC(Inverse Optimal Stochastic Control)と云うらしい。

このモデルが逆強化学習と云わないのはMDF(マルコフ決定過程）だけでなくLQR（linear-quadratic regulators)も解けるからである。LQRは一般にモータで駆動するロボットの最適制御に使われる。

このモデルは下記のグラフィカルモデルで記述されるが、理論としては逐次的に過去の成果 $U_t$ を引継いて状況 $S$ から次の最適行動 $A_t$ を予測するものである。

理論式としては、 $P(A||S)$ の情報量を最大化して算出する

　 $H(A|S) \approx \mathbb{E}_{A,S} [-\log P(A||S)] = \sum_{t=1}^T H(A_t|S_{1:t},A_{1:t})$

　 $P(A|S) \approx \Pi_{t=1}^{T} P(A_t|S_{1:t},A_{1:t_1})$

ここで確率 $P(A|S)$ は次式の様に特徴量 $\mathcal{F}(S,A)$ とパラメータ $\theta$ の内積と熟練者の経路 $\mathbb{E}_{ex}$ の差について、これが指数に比例すると云う伝統な考えを導入する。

　 $P_\theta(A|S) \approx \exp\{ \theta^T \mathbb{E}_{S,A} [ \mathcal{F}(S,A) ] - 　\sum_{\tau \gt t} \mathbb{E}_{S,A} [\log P_\theta(A_\tau | B_\tau) ] \}$

　 $\mathbb{E}_{ex} [ \mathcal{F}(S,A) ] \approx \sum_{\tau \gt t} \mathbb{E}_{S,A} [\log P_\theta(A_\tau | B_\tau) ]$

この特徴量とパラメータの線形な関係により $P(A|S)$ の対数勾配を採る $\theta$ は以下となる。

　 $\frac{\partial \log P_\theta(A|S)}{\partial \theta}= \mathbb{E}_{S,A} [ \mathcal{F}(S,A) ] - \mathbb{E}_{ex} [ \mathcal{F}(S,A) ]$

また $P(A|S)$ の対数期待値（情報量）を最大化するためMDF（マルコフ決定過程）と同じ様に報酬を内積（第１項）と事前の遷移確率（第２項）の和で、これが最大になる様に行動選択の確率 $P(A_t|S_t)$ を算出する

　 $\log Z_{A_t|S_t,\theta} = \theta ^ T F(S_t,A_t) + \sum_{S_{t+1}} P(S_{t+1} | S_t,A_t) \log Z_{S_{t+1},\theta}$

$\log Z_{S_t,\theta} = \log \sum_{A_t} Z_{A_t|S_t,\theta}$

$P(A_t|S_t) = \frac{Z_{A_t|S_t,\theta}} {Z_{S_t,\theta}}$

実験結果

(1) 前述した様にに本論文のモデル(MaxCausal)はLQRにも適用できるのでヘリコプター静止操作の軌跡もモデル化できる。その結果は熟練者のDemoと同じ推定が可能になっている。ここでInvOptとは単に特徴量一致で解く方式である。

f:id:mabonki0725:20180924191435p:plain

(2) 追いかけっこ(Pursuit-Evasion)の結果

　一般にネットワーク形式の推論では教師あり推論はCRF(Conditional Random Field)で非教師あり推論ではMRF(Markov Random Field)が使われる。CRFは機械翻訳でLSTMが導入される前は、言葉の羅列から次の言葉を推定するモデルに最も使われていた。

この実験ではMaxCausalとCRFの結果が２次元プロット図で比較してあり何れも45度線より低い所にありMaxCausalの精度が高い事が示されている。

f:id:mabonki0725:20180924192604p:plain

　(3) ベイジアンネットワークでの結果

　MaxCausalはネットワークの因果関係でも推定できるので、ここでは部分観察での自動車の故障について原因追求テストでも比較している。ここでは様々なテストで原因を追究しているベイジアンネット上のデータを使って原因を特定しているが本モデルが普通の推論より早く収束している。

f:id:mabonki0725:20180924192922p:plain

2018-08-28

有名な階層型強化学習の論文を読む

強化学習で階層型がよく話題になっているが、東大修士１年が勉強会で発表していたので興味を持ち読んでみた。

[1804.02808] Latent Space Policies for Hierarchical Reinforcement Learning

バークレイの連中の論文で強化学習での階層間を深層学習と同様に逆微分を使っている所が期待を持たせる。

即ち、下層では機械的な報酬で動作し上層では戦略的な方策で動作をするが、その動作の整合性を隠れ変数として調整するものである。

モデルとしては次の様な構造をしている。

f:id:mabonki0725:20180828175623p:plain

各層での強化学習の最適化は最適な経路確率 $p(・)$ と近似方策 $\pi(・|s_t)$ と乖離を最小にする最大エントロフィ法を使って改善している。

　　　 f:id:mabonki0725:20180828194037p:plain

層間に隠れ変数を追加して方策 $\pi(a_t|s_t)$ を次の合成関数の微分と同じ様な方法で繋いでいる

　　 f:id:mabonki0725:20180828175930p:plain

実際には隠れ変数の密度関数の補正式(NPV:real-valued non-volume preserving)を使っている。

[1605.08803] Density estimation using Real NVP

この考え方は深層学習の逆伝播と同様な考え方で方策 $\pi(a_t|s_t)$ を最適化している。

アルゴリズムとしては各層に報酬設定が必要としており、この手動設定がこの手法の問題点と考えられる。

f:id:mabonki0725:20180828190937p:plain

上図の階層図やアルゴリズムを見ると上段から最下段へ伝播し結果が最適化 $\mathcal{O}'$ されているか最大エントロフィ法で評価して逆順に隠れ変数や行動を決めているので深層学習に近い様に見える。

実験結果

(1) 2層(青)モデル 4層(緑)モデル及び訓練途中から1層→2層(橙)の比較

1層での訓練を経てから2層にした方が高い報酬を得られていることが判明する

これは1層での訓練成果を2層目で改善することを示す。また(b)では4層が劣化している

　　　　 f:id:mabonki0725:20180828191523p:plain

　(2) 他の手法との比較　

　　(a)図は蟻が緑の３隅に早く移動する強化学習の環境

　　下層は早く蟻が動くことを報酬とし、上層は蟻の方向を報酬としている

(b)図は訓練回数にたいするゴールまでの距離

　　　本手法(青) : 学習効率が優れている

SQL(最大エントロフィー法によるQ-learning)(橙)

fine tune task+motion(調整済みで目的と動きを報酬とする) (桃)

　　　scratch task+motion(調整なし目的と動きを報酬とする)(紫)　

　　　 f:id:mabonki0725:20180828192250p:plain

2018-08-08

敵対的理論より学習環境に依存しない逆強化学習の論文を読む

AI論文

このバークレイ学派の論文の寄与は次の２点である

[1710.11248] Learning Robust Rewards with Adversarial Inverse Reinforcement Learning

① 逆強化学習(IRL)はGANと同じ理論とする論文により

　　IRLをGANの識別(Discriminator)関数の最適化で解く

②このモデルを状況 $s$ 依存に変形して、

　学習した軌跡と異なった環境でも適用できるIRLモデルにした。

　具体的にはこの手法のIRLが多少環境を変えても適用できる事が示されている。

f:id:mabonki0725:20180809071828p:plain

　左図は障害壁の向きが逆になった場合、右図は蟻の前足が短くなった場合でも元の行動軌跡からのIRLで解いた報酬関数を使っても適用できる事が示されている。

　①につては次の難しい論文があるが、本文中の付録に解説がある。　　

[1611.03852] A Connection between Generative Adversarial Networks, Inverse Reinforcement Learning, and Energy-Based Models

　　要はエネルギーベースのIRLはGDL(Guided Cost Learning)で解くが、GANと同じ定式化ができるので、次式の識別関数 $D_\theta$ を $\mathcal{L}(\theta)$ のネットワークで解けばよいとのことである。

　 $\mathcal{D}_{\theta}(s,a) = \frac{\exp \{ r_{\theta}(s,a) \}} {\exp \{r_{\theta}(s,a) \} + \pi(a|s)}$

$\mathcal{L}(\theta) = -\mathbb{E}_{\tau \sim D} [ \sum_{t=0}^{T} \log D_\theta (s_t,s_a) ] - \mathbb{E}_{\tau \sim \pi} [ \sum_{t=0}^{T} \log (1 - D_\theta(s_t,a_t)) ]$

　最適な識別関数 $D$ を使うと報酬関数は次式で求まる。

$\hat{r}(s,a) = \log(D_\theta(s,a)) - \log(1 - D_\theta(s,a))$

　上記の証明は

　　　本論文のAppendex A にエネルギーベースのIRLの解法GDL(Guided Cost Learning)

　　　本論文のAppendex B にGDLがGANと同じ事が示されている。

　②を達成するには、変化した環境 $s'$ に依存するモデルではなく、現状の状態 $s$ のみに依存する様に変形する必要がある。

　一般的には次のとおりであるが

　 $\mathcal{D}_{\theta}(s,a,s') = \frac{\exp \{ f_{\theta}(s,a,s') \}} {\exp \{f_{\theta}(s,a,s') \} + \pi(a|s)}$

$f_{\theta}(s,a,s') = r_\theta(s,a) + \gamma V(s') - V(s)$

　状況 $s$ に依存する様にパラメータ $\theta$ と $\phi$ を導入して識別関数 $\mathcal{D}_{\theta,\phi}$ を最適化することで算出する式に変形している。

　 $\mathcal{D}_{\theta,\phi}(s,a,s') = \frac{\exp \{ f_{\theta,\phi}(s,a,s') \}} {\exp \{f_{\theta,\phi}(s,a,s') \} + \pi(a|s)}$

$f_{\theta,\phi}(s,a,s') = g_\theta(s,a) + \gamma h_\phi (s') - h_\phi(s)$

$g_\theta(s) = r(s) + constant$

$f_\phi(s) = V(s) + constant$

$f_\phi(s') = constant \cdot f_\phi(s)$

注記）

　逆強化学習とGANが同様に定式化される事についての詳説したものに下記の資料がある。

Irs gan doc from Masato Nakai

www.slideshare.net

2018-08-05

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

AI論文

この論文はデモが凄いので結構よく論文が読まれている。これはバークレイ学派 Abbeel達の発表である。

[1706.02275v3] Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments

この４つのデモでは、複数のエージェントが協調や敵対を報酬設定によって実現されているのが示されている。 f:id:mabonki0725:20180805091433p:plain

①協調対話：複数の発話者（３点）と聞き役（１点）がある。聞き役は指定された発話者の所に移動する場合、発話者は聞き役に移動方向を指示し、聞き役は呼応して移動する。

②協調狩：大きな障害物がある所で遅い動きの猟者達が早い動きの目標を協調して狩る

③協調指導：複数のエージェントが同数の目標を協調して占める

④偽装協調：複数の協調エージェントと敵対エージェントがある。協調エージェントは敵対エージェントを偽装して引き付ける役と目標を補足する役とで協調する

動画はこちら

Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments

これらのデモを達成するために論文では以下の工夫をしている。

①各エージェントは独自に報酬が設定でき、協調や敵対行動が可能になる

　自分と他のエージェント間の関係

　自分と目標との関係

②各エージェントには次のActor-criticモデルを適用

　・協調や敵対するため各エージェントは他のエージェントの行動 $a_j$ を見ることができる

　・行動選択は決定的方策勾配法を採用：独自の方策関数 $\mu_\theta(s)$ を使う

　・各エージェントの行動選択 $a_i=\mu_\theta(o_i)$ は自分の観察 $o_i$ から選択する

　上記の方法より、全てのエージェントの行動を把握できる事を前提にしており、行動選択はエージェント独自の状況から決定するので「中央監視・独自行動モデル」(centralized training with decentralized execution)として図１が示してある。

　　 f:id:mabonki0725:20180805110952p:plain

この図を式で示すと

　一般のactorでは

$\nabla_{\theta_i} J(\theta_i) = \mathbb{E}_{s \sim p^\pi,a_i \sim \pi_i} [\log_{\theta_i }\pi_i(a_i|o_i) Q_i^\pi(o_i,a_i) \$ ]

　協調や敵対で他のエージェントの行動を考慮して拡張する

$\nabla_{\theta_i} J(\theta_i) = \mathbb{E}_{s \sim p^\pi,a_i \sim \pi_i} [\log_{\theta_i }\pi_i(a_i|o_i) Q_i^\pi(x,a_1 \dots a_N) \$ ]

$x = (o_1\dots o_N)$ $o_j$ はエージェントｊの観察

これに決定勾配関数を $\mu$ を適用すると

$\nabla_{\theta_i} J(\theta_i) = \mathbb{E}_{s \sim p^\mu,a_i \sim \mu_i} [\nabla_{\theta_i }\mu_i(a_i|o_i) \nabla_{a_i} Q_i^\mu(x,a_1 \dots a_N) \ | a_i = \mu_i(a_i) ]$