封建的階層型の強化学習の論文を読んでみる

上位レベルはoption（サブゴールへの方策)を使った戦略、下位レベルはサブゴールまでを最適に行動する。この様に上位下達の封建的な分業関係を使った強化学習の論文(以下FuNs)を読んでみる。　

[1703.01161] FeUdal Networks for Hierarchical Reinforcement Learning

(1) モデル

この論文は封建的強化学習(1992)[1]の構想をoption(局面的方針)に適用したとものと言える。

　上位レベル(以下Master)と下位レベル(以下Worker)別に学習方法を記述する。

　(1.1) Master(上位レベル)の学習

　　この論文ではoptionの終端は $c$ ステップで固定になっている。

　　Masterのoptionを使った方策は移転方策(TP:Transfer Policy)と云い、次式の様にoption $\mu(s,\theta)$ を条件とする $c$ ステップ先の分布になっている。

　 $\pi^{TP}(s_{t+c} | s_t) = p(s_{t+c} | s_t,\mu(s,\theta))$ (1)

　　但し

　　 $\mu(s,\theta)$ ：option関数 $\theta$ のパラメータを持つ

　方策勾配法[2]よりoptionの最適な $\theta$ は方策 $\pi^{TP}$ の勾配で更新できる。

　　即ちFuNsでのoptionの関数 $\mu(s,\theta)$ はパラメータ $\theta$ に対して微分可能を前提にしている。

　　　 $\nabla_\theta \pi_t^{TP} = \mathbb{E} [(R_t - V(s_t)) \nabla_\theta \log p(s_{t+c} | s_t,\mu(s_t,\theta)) ]$ (2)

　 $\theta = \theta + \alpha \nabla_\theta \pi_t^{TP}$

　ここで $V(s_t,\theta)$ は価値関数である。

　　この移転方策 $\pi_t^{TP}$ でのWorkerに対する擬似報酬 $g_t$ を以下で改善する。

　　　 $\nabla g_t = A_t^M \nabla_\phi d_{cos}(s_{t+c} - s_t,g_t(\phi))$ (3)

　ここで

　　　　 $A_t^M = R_t - V_t(s_t,\theta)$ は利益関数

　 $d_{cos}$ はコサイン類似度で以下で定義される。

　 $d_{cos}(\alpha,\beta) = \frac{\alpha^T \beta}{|\alpha||\beta|}$

　　ここで擬似報酬 $g_t$ は状態の移転差 $s_{t+c} - s_t$ と擬似報酬 $g_t$ とのコサイン類似度によって増減し、同じ方向なら増幅されることになる。

　(1.2) Worker(下位レベル)の学習

　　Workerの内部報酬 $r_t^I$ はMasterで設定した以下の擬似報酬の平均である。

　　　 $r_t^I = \frac{1}{c} \sum_{i=1}^c d_{cos} (s_t - s_{t-i},g_{t-i})$ (4)

　　 Workerの方策は以下の方策勾配法で改善される。

　　 $\nabla_\vartheta \pi_t = A_t^D \nabla_\vartheta \log \pi(a_t | x_t;\vartheta)$ (5)

ここで $A_t^D$ はWorkerの利益関数で内部報酬 $r_t^I$ で計算される。

$A_t^D = (R_t + \alpha r_t^I - V_t ^D(x_t,\theta))$

　　実装では上記の精緻化は下記の(a)-(c)の深層学習を使っている。

　　(a) 状況 $s_t$ はWorkerでの観測値 $x_t$ を深層学習で特徴ベクトル化したものとしている。

　　　 $z_t = CNN(x_t)$

$s_t = Neuro(z_t)$ 完全結合のニューロ

　　 (b) 式(3)の擬似報酬 $g_t$ は実装上では過去の隠れ変数を使用したLSTMで改善している。

　　　但しLSTMは拡張(dilated)されており、隠れ変数は剰余演算 $t \% r$ を使って更新単位 $r$ の残りのベクトルを入れている。論文ではこの拡張による学習効果を実証している。

　　　 $g_t = LSTM(s_t,h_{t-1}^{t\%r},\phi^{LSTM})$

　　　 $\pi_t = SoftMax(U_t,r_t^I)$

$U_t = LSTM(z_t,h_{t-1})$

　モデルの全体図は以下となる。但し赤字は自分の解釈である

f:id:mabonki0725:20190117103022p:plain — FuN構成図(赤字は解釈)

(3) 実験

FuNsの実験ではA3C(Actor-Criticの並列計算)システムを使ったと記述があるので、(2)モデルで示した $\nabla \pi_t^{TD}$ $\nabla \pi_t$ $V_t^M$ $V_t^M$ は全てActor-Criticで最適計算したと思われる。

　ここではATTARIゲームの以下を使ってFuNsの有効性を示している。

　　①Montezuma's revenge

　　②記憶の再現　(non-match T-maze Water maze)

　　③option-Criticモデルとの比較

　　④10種類のATTARIゲームの学習効率

　　⑤optionの視覚化

　比較対象としてRNN-LSTM BPTT(Backpropagation Though Time)を使っている。

　実験①Montezuma's revenge

　下図の様にこのゲームは2013年にDeepMindがDQNを発表した際、一番解けなかったゲームで、敵を回避して数々の仕掛けをクリアーし鍵を入手して次の場面に進むので様々なアイテムを認識する必要がある。

f:id:mabonki0725:20190118085207p:plain

下図の様にこのゲームを攻略するため様々なモデルが編み出され多大な発展に寄与してきた[4]。(図中のRND[5]は現在では最強でない )

f:id:mabonki0725:20190118201251p:plain — モデルの変遷とスコア

　　下図の様に実験結果を示している。
　　　左図は学習効率の比較（数字は割引率)

　　　右図は学習過程でのサブゴールに達した回数(ピークは適切なサブゴールを示す)

　　　ピークの所はゲーム中では梯子を渡る場面や鍵を取る所に対応していて明示的な設定せずともoptionが認識されている事がわかる。

f:id:mabonki0725:20190117171534p:plain

　　実験②記憶の再現

　　　記憶をOptionと認識する課題である。

　　　non-match(左図)はロボットが下段の部屋にある物体の形状を覚え、ボタンを押下すると上段の部屋に移動する。そこで下段の部屋の物体と異なるものを選択すれば正解である。　　

　　　T_maze(中央図)はT字路先の得られる報酬と物体の形状を覚え、リセットした後記憶を辿り報酬を得られるかの課題である。

　　　何れも形状の記憶をoptionとして認識させており、早期に学習に繋がっている。

f:id:mabonki0725:20190117184222p:plain

　　　Water maze(下図)は円型プール中で複数の見えないゴールを探る課題である。左図と中央図では緑の経路が見えないゴールを探索して迷走している状態だが、これに続く黄・青・赤の経路はゴール探索をOptionとして認識してるので経路が短くなっている。右端はゴールの位置(プールの壁から位置)までもOptionとして認識しているので、同心円を描く様に探索している状態を示している。

f:id:mabonki0725:20190117185157p:plain

　　実験③Option-Cliticモデルとの比較

　　　Actor-Criticをoptionに適用したモデルOption-Criticはサブゴールの終端までを認識する優れたものである[3]。一方FuNsはサブゴールは $c$ ステップ先として固定である。やはりoptionの認識と終端の両方を認識するのは難し様で下記の２種類のゲームではFuNsが優れていることが報告されている。

f:id:mabonki0725:20190117190155p:plain

　　実験④10種類のATARIゲームでの学習効率の比較

　　　上段の枠内はFuNsが優れているゲームで、下段の枠内は劣っているゲームである。論文では下段の様に単純なゲームではFuNsは役に立たないと述べている。

f:id:mabonki0725:20190117191348p:plain

　　実験⑤optionの視覚化

　　　FuNsでは潜水艦ゲームでoptionの視覚化を下図の様に示しているが、解釈が容易でない。論文では下図の分布図はサブゴールを固定してWorkerの動作を記録したとある。右端の分布は左端のゲーム場面で潜水艦が酸素補給のため浮上している所とある。

f:id:mabonki0725:20190117215115p:plain

(3) 感想

　昔から上下関係で強化学習を戦略と実行を分業化するのは、複雑なミッションを行うには合理的と考えられてきたが[1]、確かに上図にあるシステム図は下からは環境データ上位からは擬似報酬とシンプルで説得力がある。しかしこの分業が可能かは残念ながらFuNsの実験が示す様に課題やその難易度に拠っている段階である。FuNsではoptionが $\theta$ の連続関数であるので最適解が微分で得られているが、この連続値のoptionが明瞭でなく解釈が難しい。またサブゴールが $c$ ステップ先として固定である事と下位の擬似報酬がコサイン類似度を使っている２点は合理的な理由が論文では示されていない。サブゴールの終端の認識はOption-Critic[3]で示されているが学習が難しいと云われている。またコサイン類似度を使う擬似報酬でMontezmaゲームの様な渡橋や鍵が入手できるのが不思議である。戦略と実行とで分業するのは複雑なゲームより様々なモーターを使い誤差の制御が難しいロボッテックスの方が切実と考えられる。その点DeepMindの論文は全てゲームを対象としており実世界からは離れている。最近ではロボッテクスに適合した階層型分業モデル[6]の研究も報告されている。

[1] P.Dayan G.Hinton (1992) Feudal Reinforcement Learning

[2] ①方策勾配法反証的な複数エージェントの強化学習を読む - mabonki0725の日記

[3] 報酬に依らず暗示型optionを使った強化学習の論文を読んでみる - mabonki0725の日記

[4] Reinforcement Learning with Prediction-Based Rewards

[5][1810.12894] Exploration by Random Network Distillation

[6][1805.08296] Data-Efficient Hierarchical Reinforcement Learning