2019-01-11

報酬に依らず暗示型optionを使った強化学習の論文を読んでみる

強化学習

　強化学習を定式化したR.Suttonが2000年にOptionという重要な概念を提供しており[1]これを知らなかったとは相当な勉強不足と認識せざる得ない。

　強化学習では長い迷路を経てゴールに達する場合や非常に稀に得点が入る場合には、相当の試行を重ねる必要がある。そこでサブゴールの様なものを考え、これを環境から推定できれば試行回数を減らせえるというアイデアである。もう一つの利点はゴールが多少移動した場合や環境からの雑音が多くなってもサブゴールを学習していれば到達し易いことである。昼間に要所に目印を付けてゴールすれば、暗くなっても簡単に辿り付けると云う理屈と同じである。

　このOptionには明示的なもと暗示的なものがあり、明示的なOptionは経験的に設定するもので階層型モデルとして使われている様である[2]。しかし暗示的Optionはこの認識が大きなテーマであり変分法を使うものもある[3]。暗示的Optionは、報酬による外的動機付と対立する考えで、内発的動機付(IM:Instrinsic Motivation)に位置づけられ、報酬とは関わりなく動作する自律Agentモデルで使う重要なものの一つである[4]。

　Actor-CriticをOption用に拡張したOption-Critic(2016)は暗示的なoption(以下intra-option)の学習の一つで下記の論文を読んでみる。

[1609.05140] The Option-Critic Architecture

　論文によればintra-optionは $\omega \in \Omega$ で表記され次の組で定義されるものである。

　　 $[ I_\omega,\pi_\omega(\theta),\beta_\omega(\vartheta)]$

　　ここで

　　　 $I_\omega$ はoptionの開始の状態 $s$ を示す

　　　 $\pi_\omega(\theta)$ はoptionの方策

$\beta_\omega(\vartheta)$ は終了関数と云い(サブゴールの確率を示す)

$\theta$ と $\vartheta$ はOptionのパラメータで勾配により最適化の対象

　このoptionを統合したMDPをSemi-MDP(SMDP)とも云う。

　具体な例として、下図の様に４部屋あり通路を通ってゴールに達する課題の場合、学習が進むと終了関数 $\beta_\omega(\vartheta)$ （サブゴール）の確率分布は下図の明るい色で表示され、下図では上下の通路がサブゴールとして認識されていることが分る。

f:id:mabonki0725:20190109165707p:plain — ４部屋と通路

(1) モデル

intra-optionでは、この方策と終了関数(サブゴール)が求まればよいことになる。この論文ではintra-optionの行動価値関数 $Q_\Omega$ を最適化するパラメータを勾配法で求めている。

　　まずintra-optionの行動価値関数は行動 $a$ について価値関数を総和して消去している。

　　 $Q_\Omega(s,\omega) = \sum_a \pi_{\omega,\theta}(a | s) Q_U(s,\omega,a)$ (1)

$Q_U(s,\omega,a) = r(s,a) + \gamma \sum_{s'} P(s' | s,a) U(\omega,s')$ (2)

$U(\omega,s') = (1 - \beta_{\omega,\vartheta}(s'))Q_\Omega(s',\omega) + \beta_{\omega,\vartheta}(s')V_\Omega(s')$ (3)

　 $U(\omega,s')$ は終了関数(サブゴール)の確率 $\beta_{\omega,\vartheta}$ で按分された価値である。前項はサブゴールへの途中intra-option: $\omega$ を採った価値で後項はサブゴールに至っておりoptionを採らない状態価値となる。

ここで

　　 $\gamma$ は割引率

$P(s' | s,a)$ は行動 $a$ で状況 $s$ から状況 $s'$ への遷移確率

　このintra-ptionのパラメータ $\theta$ と $\vartheta$ の最適化は、intra-optionの方策 $\pi_{\omega,\theta}$ と終了関数 $\beta_{\omega,\vartheta}$ を使ったintra-optionの行動価値関数 $Q_\Omega(s,\omega)$ について、それぞれ偏微分して勾配を求めてパラメータを更新して行っている。

　intra-optionの行動価値関数 $Q_\Omega(s,\omega)$ の $\theta$ での偏微分は(1)と(2)式より微分して

　　 $\frac{\partial Q_\Omega(s,\omega)}{\partial \theta} = [ \sum_a \frac{\partial \pi_{\omega,\theta} (a | s) Q_U(s,\omega,a)}{\partial \theta} ] + \sum_a \pi_{\omega,\theta} (a | s) \sum _{s'} \gamma P(s' | s,a) \frac{\partial U(\omega,s')}{\partial \theta}$

これを本論文のAppendixのoption方策勾配定理を使うと以下で表される。

　　 $\frac{\partial Q_\Omega(s,\omega)}{\partial \theta} = \sum_{s,\omega} \mu_\Omega(s,\omega | s_0,\omega_0) \sum_a \frac{\partial \pi_{\omega,\theta}(a | s)}{\partial \theta} Q_U(s,\omega,a)$

$\mu_\Omega(s,\omega | s_0,\omega_0) = \sum_{t=0}^\infty \gamma^t P(s_t = s,\omega_t = \omega | s_0,w_0)$

　次にoptionの行動価値関数 $Q_\Omega(s,\omega)$ の $\vartheta$ での偏微分は(1)と(2)と(3)式より微分すると

$\frac{\partial Q_\Omega(s,\omega)}{\partial \vartheta} = \sum_a \pi_{\omega,\theta} (a | s) \sum _{s'} \gamma P(s' | s,a) \frac{\partial U(\omega,s')}{\partial \vartheta}$

　　 $\frac{\partial U(\omega,s')}{\partial \vartheta} = - \frac{\beta_\omega,\theta(s')}{\partial \vartheta} A_\Omega(s',\omega) + \gamma \sum_{\omega'} \sum_{s''} P(s'',\omega' | s',\omega) \frac{\partial U(\omega',s'')}{\partial \vartheta}$ (5)

　　 $A_\Omega(s',\omega) = Q_\Omega(s',\omega) - V_\Omega(s')$

　また(5)式の $U(\omega,s)$ の $\vartheta$ での偏微分はAppendexの終了関数勾配定理を使うと

　　 $\frac{\partial U(\omega,s')}{\partial \vartheta} = -\sum_{s',\omega} \mu_\Omega(s',\omega | s_0,\omega_0) \frac{\partial \beta_{\omega,\vartheta}(s')}{\partial \vartheta} A_\Omega(s',\omega)$

　以上によりパラメータ $\theta$ と $\vartheta$ を更新するためintra-option行動価値関数 $Q_\Omega(s,\omega)$ の勾配が得られた。

論文ではoptionの選択方策 $\omega \sim \pi_\omega(s)$ の方法は明確に述べられていない。これは課題によって最適な方策を採るべきなのだが、論文では次式の $max_\omega$ で汎用的な価値 $g_t$ を最大化するintra-optionの選択方法を示している。但しintra-optionの選択は $\epsilon$ greedyとして $\epsilon$ だけランダムに選ぶ方法を採っている。

　 $g_t = r_{t+1} + \gamma [ (1-\beta_{\omega,\vartheta}(s_{t+1})) \sum_a \pi_{\omega.\theta}(a | s_{t+1}) Q_U(s_{t+1},\omega_t,a) + \beta_{\omega,\vartheta}(s_{t+1}) max_{\omega} \sum_a \pi_{\omega,\theta}(a | s_{t+1}) Q_U(s_{t+1},\omega,a) ]$

　Option-CriticのCriticの役割として、価値の最大化 $g_t$ を使うとintra-option価値関数 $Q_u(s,\omega)$ は次式で更新することになる。ここで $\alpha$ は学習率

$Q_U(s',\omega,a') = Q(s',\omega,a') + \alpha (g_t - Q(s,\omega,a))$

(2) アルゴリズム

よってOption-Criticのアルゴリズムは以下となる。

　 $s \gets s_0$

$\omega \sim \pi_\Omega(s)$ $g_t$ を最大化する $\epsilon$ greedyでサンプル

repeat :

$a \sim \pi_{\omega,\theta}(a | s)$

$\delta \gets g_t - Q(s,\omega,a)$

行動価値関数の更新 Critic

　 $Q_U(s,\omega,a) \gets Q_U(s,\omega,a) + \alpha \delta$

パラメータの更新

　 $\theta \gets \theta + \alpha_\theta$ × 式 (1)の偏微分

　　　 $\vartheta \gets \vartheta + \alpha_\vartheta$ × 式(5)の偏微分

　　もしサブゴールに達していない $\beta_{\omega,\vartheta} \in s'$ なら

　　　 $\omega' \sim \pi_\Omega(s')$ 　 $g_t$ を最大化する $\epsilon$ greedyでサンプル

$s \gets s'$

もし s がGoalなら終了

　全体のOption-criticのシステム構成は以下で示されている。

f:id:mabonki0725:20190110085529p:plain

(3) 実験　

　ここでは以下の実験を行っている。

　①４部屋に通路があり、ゴールが突然移動になった学習

　 ②任意型の物体の間を抜けるボール

　③汎用的な深層強化学習プラットフォーム(ALE)での結果

実験①４部屋に通路があり、ゴールが突然移動になった学習　

　 Suttonの論文[1]の実験課題であるが、以下の課題としている。

　・Optionは明示されず数のみ設定する。

　・ゴールの移動　前半ではゴールが左２部屋の通路にある。

　　この学習が収束した状態で、ゴールが右下の部屋に移動する。

　・3分1の割合で移動が失敗しランダムに動く

　結果

　　比較対象はSarsa 普通のActor-critic(AC-PG) intra-optionの数４(OC-4) intra-optionの数(OC-8)

(左図)intra-optionでは後半のゴールの移動後の学習は前半の学習効率と殆ど変わらないことが分る。intra-optionでは報酬で直接動作するのではなく有意なoptionに従って動作するので効率がよいと考えられる。

(右図)終了関数 $\beta_{\omega,\vartheta}(s)$ の確率が高い所を明るく表示

　　通路の所が明るく表示され、通路を通ることがintra-optionとして捕らえていることがわかる。　　

f:id:mabonki0725:20190111101833p:plain

　実験②任意型の物体の間を抜けるボール

　下図(左図)の様に任意の形状を持つ障害の間をボールが抜けるintra-optionの学習である。

　次の様な制約がある。

　　・障害には弾力性があり、衝突すると罰則がある　

　　・ボールには速度、上下左右移動、無操作の行動選択がある

　　・無操作が続くとボールは99.5%の確率で停止してしまう

　結果

　　右図の様に約10回の試行回数で学習が収束している。intra-optionが多い方が学習精度が高く、左図の経路はこのモデルで計算された４種類のintra-optionの区分である。各々のintra-optionの経路には特徴があるこが分る。

f:id:mabonki0725:20190111110211p:plain

　　実験③汎用的な深層強化学習プラットフォーム(ALE)での結果

　　　この汎用深層強化学習(ALE:Arcade Learning Enviroment)は文献[5]で開発されたものを使っているが、深層モデルの構成やパラメータの調整を行っている、実験課題はAtariゲームとなっている。ここではActorで正則化項の追加やベースライン項が有意であることが述べている。　　

f:id:mabonki0725:20190111111121p:plain — ALEでのIntra-optionの構成

　結果

　　　以下のAtariゲームでの結果でDQNのレベル(橙色)と比較していて、Pacman以外はintra-optionの方が良い精度が出ている。

f:id:mabonki0725:20190111111712p:plain

　　　潜水艦ゲームでは2種類のintra-optionが設定され、使われているintra-optionの変更状態が下図の上段のBar(白色：option1 黒色：option2)に表示されいる。この場合のゲームの図が下段に表示され、option1は上昇 option2は下降である事が分る。

f:id:mabonki0725:20190111112432p:plain

(4) 感想

暗示的optionはオプション方策とサブゴールを示す終了関数の両方を最適化する必要がありしかも疎な報酬で学習する複雑なモデルである。しかし暗示的optionを一旦習得してしまえばゴールが変更になった場合や雑音や制御が難しくなった場合でも簡単にゴールまで到達できる利点がある。暗示的optionは人間の様に報酬に直接依存せず内発的動機付けによって自律的な動作する様なロボット開発には重要な概念である。例えば料理をさせる様な複雑な動作をするロボットの場合を考えると、最終的な報酬ではなく様々な段階でのサブゴールを習得することが必要である。暗示optionは今後発展が期待できるモデルと思われる。

[1]R.Sutton [A framework for temporal abstraction In reinforcement learning]

[2]増山岳人他 [階層型強化学習におけるスキル価値の汎用化に基づいた探索空間の縮減]

[3]K.Gregor [Variational Intrinsic Control]

J.Achiam [Variational Option Discovery Algorithm]

[4]浅田稔 [内的動機付けによるエージェントの学習と発達]

[5][1207.4708] The Arcade Learning Environment: An Evaluation Platform for General Agents

2019-01-03

Berkeley学派のメタ学習の論文を読む

強化学習でのメタ学習の概念が理解できず、OpenAIサイトのリストにあったAbbeel率いるBerkeley学派の論文(以下 $RL^2$ )を読んでみる。

[1611.02779] RL$^2$: Fast Reinforcement Learning via Slow Reinforcement Learning

(1) $RL^2$ モデル

この論文は下図の様にAgentに系列を保持する隠れ構造 $h_0 \sim h_n$ を想定して、エピソード間での学習スピードの改善を評価した論文である。ここでいうエピソードとはゴールに達するまでの行動で、複数のエピソードの繰返しを試行(trial)とし、trial毎に隠れ構造はリセットされる。Agentには学習した系列が残っているので、下図の様に次のエピソードを繰返すと当然学習が早くなってくる。それ故こ論文のタイトルは「 $RL^2$ :Fast Reinforcemnt Larning via Slow Reinforcemnet Learning」としてある。系列を保持する隠れ構造はGPU(Gated Processing Unit)を使っている。

f:id:mabonki0725:20190103120628p:plain — エージェントに内部構造を仮定したモデル

しかし一般にメタ学習とは、人間の様に同様だが異なるTask(課題)にも素早く適用できる様な学習を意味するが、この論文のメタ学習では同じ課題での漸次的(asymptonic)な改善を意味している。

上図では分らないがデータの流れは以下となっている。

　　 $s_t$ 状態→embeding(特徴ベクトル)→系列の隠れ変数 $h_t$ →TRPO→ $a_t$ 行動→ $s_{t+1}$ 次の状態

強化学習を解くモデルはTRPO(Trast Region Policy Optimizetion)を使っている。ゲームで一般的なActor-Criticを使わず実ロボット用のTRPOを使うのは、TRPOがBerkeley学派のオリジナルだからと考えられる。

(2) $RL^2$ の実験

　実験では多腕Bandit問題で学習の効率を示し、高次元での課題として3D迷路を解いている。

　実験①多腕Bandit問題

　　ここでは多腕Bandit問題を解く有名な次のモデルと比較している。

　　　　Gitten:ベイズによる最適化

　　　　TS：Thomsonサンプリング

　　　　UCB１：Upper-Confident Boundモデル

　　　　Greedy：経験的に一番当たるスロットマシンを引き続ける。

　　　 $\epsilon$ -Greedy：Greedy戦略だが確率 $\epsilon$ でランダムに引く

　　下表で $k$ はスロットマシンの数　 $n$ はエピソードの数　　

f:id:mabonki0725:20190103134633p:plain — 多腕Banditの報酬比較

上表では $RL^2$ モデルがGittensと殆ど同じ高い性能を示していることがわかるが、下図では最もエピソードが多い場合でも、Gittenとの差が明瞭に示され $RL^2$ モデルの限界が示されている。

f:id:mabonki0725:20190103135258p:plain — エピソードが最大時の学習曲線

　　実験②３D迷路探索
　　高次元の３D画像迷路での探索問題を解いている。この３D迷路は有名なFirst-Person-ShootingゲームのViZoomでの強化学習用のプラットホームを使って迷路を生成している。論文では下図の様に２種類（SmallとLarge)の迷路での宝の獲得を課題として、各々ランダムに1000個の迷路を生成して $RL^2$ を訓練したとある。

f:id:mabonki0725:20190103140637p:plain

　　以下は２つの迷路での上位５つでの結果である。左は探索経路長、中央は宝の獲得率、左はエピソードの１番目と２番目の探査経路の短縮率である。

f:id:mabonki0725:20190103141325p:plain

　　上表ではエピソード毎に性能が改善され一見妥当な結果が得られているが、論文では次の２つの問題が報告されている。

　　下図は $RL^2$ の学習曲線であるが、初期値によっては全く学習ができていないことが分る。

　　　　　　 f:id:mabonki0725:20190103141855p:plain

これは強化学習ではよく散見される課題で、下記の記事の様に初期パラメータの設定には辛抱強く取り組む事が必要なことを示している。

Googleロボットチームの強化学習のサーベイ記事を読む - mabonki0725の日記

　　次の問題は $RL^2$ はGPUによる系列の記憶によって連続するエピソードでは改善を示すことであったが、以下の様に左の２つの連続エピソードでは記憶を使って近道をしているが、左の２つは遠回りしている現象が見られるとのことである。論文では $RL^2$ にこの様な現象を回避する特有のロジックが必要としている。

f:id:mabonki0725:20190103142938p:plain

(3) 感想

　1)最近は曖昧になったがBerkeley学派は実世界でのロボットでの開発を目指していて、DeepMindでは碁を含むゲームを通じての仮想世界でのシンギュラリティを目指していている。そのためかBerkeley学派の論文は非常に数理的に明解で実直に述べられている場合が多く信頼感がある。

　2) 現在は強化学習の入力に系列を反映した隠れ変数を適用するのが当然になっていているが、2016年に発表された $RL^2$ は系列記憶の有効性を示した初期の論文と思われる。しかしLSTMやGPUは系列的な教師データに対してのゲート開閉の重みを調整するものなので、メタ知識として人間が類似するが異なる課題に適用し早期に学習するには簡便すぎると思われる。その点DeepMindのUNREALでは系列記憶以外に様々な記憶を有効に組合わせて複雑な３D迷路を解くことには成功しているが、メタ知識としてのモデル化までは意識されていなく残念である。UNREALの様なモデルで $RL^2$ のフレームで同じTASKでなく少しつづ異なったTASKで学習速度の改善が実現できればメタ学習として評価できるかもしれない。

DeepMindのUNREALでの暗黙の特徴量 - mabonki0725の日記

2019-01-02

深層時系列を使った強化学習での汎用化の論文を読む

強化学習

OpenAIのサイトで深層強化学習の主要論文(Keyword Papers)のリストが下記にある。

Key Papers in Deep RL — Spinning Up documentation

この中で転移学習とメタ学習は学習効率に関して人間の高度な学習能力からアイデアを得ることが多いのでどうしても関心が沸く。最近ではメタ学習の論文が注目されている様な気がするので。そこで下記の論文を読んでみた。

arxiv.org

この論文は一昨年のNIPSで有名になったLSTMによる汎用的な漸次的最適化の論文「Learning to Learn using Gradient descent」を強化学習に拡張したものである。この論文については以下の記事がある。

深層時系列を使った汎用的な最適化の論文を読む - mabonki0725の日記

本題のLearing to RL learning（以下Meta-RL）は上記の論文を読んでいないと殆ど理解できないと思われる。何故ならMeta-RLの中核ロジックは殆どLSTMによる最適解の汎用化(以下Learning to Learn)を前提にしているからである。

Meta-RLはMeta学習と標榜しているが、記述を見る限り「全く異なった課題でも同じ考え方で解けるという」意味で使っていて殆ど汎用化の意味に近い。Learning to Learnの論文でも殆どMeta学習とは言っておらずむしろ転移学習に近いと言っている。

(2) Meta-RLのモデル

　まずLearng to Learnからの拡張の対応関係を示す

　　　　　　　Learning to Learn 　　Meta-RL

・目的　関数の最適化のパラメータ探索　　報酬最大化するパラメータ探索

・利点　最適化対象の関数に依存しない　　Model-BaseでなくModel-Free

　・過程　パラメータの勾配の収束過程　　　　　　MDP過程

　・方法　パラメータの勾配改善　　　　　　A3Cでの方策とQ関数のパラメータ改善

　・次元　パラメータ次元　一万次元　　　　画像によるゲームでは高次元

この様に関数の最適化の探索がMeta-RLでは報酬最大化に該当し、パラメータの改善がMeta-RLでは方策と価値関数の両方のパラメータの改善に対応しているだけで殆ど同じ構造をしていることが分る。従って下図の様にMeta-RLは強化学習の改善過程でLearning to Learnを組み込んで使っている。

・Learning to Learnのモデル図　

f:id:mabonki0725:20190101104434p:plain

・Meta-RL

　何れも図中の回転マークは上図のLearning to LearnのOptimizerとOptimizeeの改善過程を表し、最適化対象関数 $f$ はここでは $\pi$ 方策(actor)と $V$ 関数(clitic)の両方に対応しパラメータを改善している。

f:id:mabonki0725:20190102091443p:plain — Meta-RL実験で使用するモデル構造

　　(a) 実験にあるバンディット問題の構造図

　　(b)画像認識による報酬ゲームの構造図ここで $enc$ は画像のエンコードを示す。

　　(c)簡単な迷路探索で課題で構造図ではLearning to Learnを２段にしている。

(2) Meta-RLの実験

　Learning to Learnの汎用最適化の記事にも述べたが、これはパラメータの変更過程をLSTMするだけで高次元の問題でも良い性能が得られる。しかしその根拠が不明なため実験を豊富に示していた。同様の理由でMeta-RLも実験を７種類で行い、何れも良い性能を示しているが根拠を示せてはいない。

実験①独立 Bandit問題　

　各々独立して異なる確率で当たるスロットマシンを引いて、最小の後悔Regretで済む（逆にいうと最大の成果を得る）学習を行う。ここでは学習結果の指標を次のRegretで得る。

　 $R_T(b) = \sum_{t=1}^T \mu^*(b) - \mu_{a_t}(b)$

ここで

　　 $\mu^*(b)$ は環境 $b$ での最も当たるスロットマシンでの報酬

$\mu_{a_t}(b)$ は試行回数 $t$ 回目でスロットマシン $a$ を引いた場合の報酬

　　 $R_T(b)$ は $T$ 回の試行で理想報酬との差で「後悔」を表す量

　この問題は一般には試行毎の結果からベイズよる事後分布を改善するモデルで解かれる場合が多いが、Meta-RLの学習では試行を繰返しても後悔が(Regret)が増えず一定になる傾向（即ちコンスタントな報酬を獲得）を示している。比較モデルとして以下と比較しておりGittinsモデルと同等な性能が得られMeta-RLの性能が高いことが分る。

Gittins：ベイズによるモデル

　 Thompson：非同期最適化モデル

　 UCB：後悔最小化モデル

f:id:mabonki0725:20190101174125p:plain — 独立Bandit問題の結果

実験② 当たる確率が相互に依存し合うBandit問題

　　２台のスロットマシンがあり一方が確率 $p_1$ で当たればもう一方は $p_2=1-p_1$ とする。

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

　②-1実験　一方の確率 $p_1$ が一様乱数の場合の実験

　　ここでは一方の当たる確率が低ければ、一方は高い確率なので異なるスロットマシンを引くことを学習することになる。Meta-RLでは次の結果が得られ、①の独立Bandit問題より少ないRegretを達成していることが分る。

f:id:mabonki0725:20190101175932p:plain — 相互に依存したBandit問題（一方が一様乱数）

　②-2実験訓練時と試行時で当たる確率の一様分布が異なる場合

　　　訓練時の一方の当たる確率 $p_1$ の一様分布が[0.1～0.9]の範囲だが、試行時の $p_1$ の一様分布が[0.4 ～ 0.6]の場合。この場合は試行時の $p_1$ の確率が狭くなっているので学習が難しくなりRegretは大きい（図e)。また反対に訓練時の $p_1$ の一様分布が[0.25 ～ 0.75]で試行時が[0.1 ～ 0.9]の場合は確率が広がるので学習が簡単になりRegretは小さくなっている(図d)。Meta-RLでは適切に相互依存のBandit問題を解いていることが分る。

f:id:mabonki0725:20190101182336p:plain — 訓練時と試行時の条件が異なる場合

実験③ 一台だけが最適スロットマシンの番号を与える問題

　11台のスロットマシンがあり何れかの１台だけが情報提供マシンであり、残り10台の中で最適なスロットマシンの番号を与える場合を考える。Meta-RLは試行を繰返し、どのマシンが情報提供マシンか理解し、次に最適マシンを引き続ける様に学習する。下図はMeta-RLは繰返し学習の結果で、１回目に情報提供マシンを引いて報酬（最適番号に0.1を掛けた値）得て次に報酬の10倍のマシンを引き続け報酬５点を得ている。

f:id:mabonki0725:20190101184139p:plain — 情報学習Bandit問題

　実験④高い報酬が確率的に変動する場合にその変動速度に追随する学習

　　2台のスロットマシンがあり一方の報酬の高い確率が $p_1$ で変動し、もう一方は確率 $p_2=1-p_1$ で変動する。その変動は遅いモードlow-vol と早いhi-volがあり、エージェントは報酬の高い方の選択と変動モードも学習する必要がある。論文の記述はよく理解できないが、変動が早い場合は３種類の学習率のパラメータを大きくする必要があり、これも学習する対象になっている。

　下図はモードがlow-volとhi-volについてMeta-RLと比較用のR-W(Rescorla-Wagner)モデルを示している。low-volモードでは試行を繰返すと報酬が低い側（下側）では殆どバーを引いておらず $p_2$ の高い報酬を見て学習している事が分かる。

しかしhi-volになると殆ど両モデルに差が見られない。

f:id:mabonki0725:20190101200957p:plain — 報酬の変化の速さに対する行動の追従

　また学習率の比較でもR-WのBIC(ベイズ情報基準）（図ｃとｄ）でも大きな差が出ている。学習率alphaについてもMeta-RLはモードによって異なった値（図f)を持っている。

f:id:mabonki0725:20190101201436p:plain — 学習率の相違

　実験⑤２段階課題（The two-step task)

　　下図の(a)様に報酬が得られる２ノード $S_2$ と $S_3$ がありランダムに一方が高い報酬を出す。ノード $S_1$ で行動 $a_1$ か $a_2$ を選択して前に報酬が高い方のノードに行きたいが、その道が確率的に75%(Common)と25％(Rare)で方向が入れ替わる。この課題は報酬を得るために確率が高い道を選ぶかの学習である。即ち下Meta-RLは繰返しの中で下図の様な構造を学習（理解）するかの課題である。

結果（図ｃ）に示す様に、Meta-RLは前に報酬が得られたノードに行くためには確率の高い道に行く様に行動を選択しており、報酬が得られないノードには確率の低い道に行く様に行動を選択しいる。Meta-RLは試行を繰返す事によって図aの構造を学習しているのが分る。

f:id:mabonki0725:20190101205933p:plain — 課題構造図と結果

　実験⑥画像を認識をする課題

　　これは猿の知能レベルの試験に使われたもので、２枚の画像を映す板があり、どちらかは意味があり、これを選ぶと餌が与えられる。２枚の画像の左右はランダムに入れ替わる。実験では猿は餌が出る画像の意味を理解する様になったとの報告であるが、Meta-RLも同様に学習を達成している。

f:id:mabonki0725:20190101212345p:plain — 画像の意味の理解

　実験⑦記憶を使った簡単な迷路問題

　　下図(a)の様な物体のあるゴールの画像を記憶（Ohe-hot Memory)させて、下図(b)の様な簡単な迷路での画像推移からゴールに辿り付く様に学習する課題である。下図(c)の様にMeta-RL(Nev A3c)はOne-hotの画像から迷路を探索の試行を繰返してゴールに辿り付ける様に学習する。しかし下図(c)の試行回数の単位は１億でる事に注意すると、かなりの試行回数を要していることが分る。難しい課題なので２段のLSTMを使ったモデルだが、数百万という試行回数を要することからMeta-RLという汎用的なモデルには限界があると論文には述べている。

f:id:mabonki0725:20190101214549p:plain — 一時記憶による迷路探索問題

(3) 感想

　Meta-RLは高次元の最適化に適しているLearning to Learnを素直に強化学習に拡張したモデルといえるので、一般的に強化学習は高次元のパラメータを扱うので一応筋が通っている。しかし次の課題が見えてくる。

1)LSTMを使うことによって最適化過程で隠れ変数を膨大に使えるのは分るが、高次元の最適化が何故うまく行くのか数理的に解明されていないので、強化学習でも同じ課題が残ってしまっている。

　2)実験⑦の結果で示されている様に高度な問題になると数百万回の試行が必要となっており、汎用的なモデルで解けることは分ったにせよModel-baseに適わないと論文では正直に述べている。Meta-RLの持つ高次元かつ汎用性の能力が本当に有効な課題はどの辺なのかが判然としない。

　

2019-01-01

深層時系列を使った汎用的な最適化の論文を読む

AI論文

時系列を使って強化学習を汎用的に解くモデルが発表されており、この様な画期的な論文を知らなかったとは如何に勉強不足であるか思い知る機会となった。

[1611.05763] Learning to reinforcement learn

もしこの論文があまり読まれていないなら、その理由は「Learning to Learn using
Gradient Descent」にロジックを殆ど踏襲しており、これを読まないと全く記述が理解できないからである。

そこで遅まきながら一昨年のNIPSでかなり有名になったLSTMを使った汎用的最適化の下記の論文を読む。

arxiv.org

この論文は最適化のSDGの収束ロジックを時系列のLSTMに置き換えたものといえる。

深層学習の良くできたモデルでは精度と汎化の両方が傑出している理由は解明中であるが、次の様に既存の数理的なロジックを深層学習に置き換えて、高次元(数万次元)でより性能改善を示す流れが顕著であり、これもその一つと考えられる。

・変分法　 VAE

[1312.6114] Auto-Encoding Variational Bayes

・事後分布　ABC

　https://papers.nips.cc/paper/8228-predictive-approximate-bayesian-computation-via-saddle-points.pdf

一般に多次元のパラメータでの関数の最適解ではSDGを使うが、関数の特徴（勾配や局所解）によって様々な工夫を使うのが一般的である。しかしLearning to learnではこの様な配慮を必要とせず深層学習で最適化できるとしている。

(1) Learning to Learn モデル

最適化パラメータ $\theta^*$ を解くにはLearning to LearnではSDGを以下と置き換えている。

$\theta^* = argmin_{\theta \in \Theta} f(\theta)$ (1)

・SDG　

$\theta_{t+1} = \theta_t - \alpha_t \nabla f(\theta_t)$

・Learning to learn

$\theta_{t+1} = \theta_t + g_t(\nabla f(\theta_t),\phi)$ 　　(2)

ここで

$\theta_t$ は最適化パラメータ(Optimizee)で１万次元を想定

$g_t$ は最適化関数(Optimizer)

$\phi$ はOptimizerのパラメータ

(2)式は時系列過程であり、 $g_t$ をLSTMを使って性能を改善するアイデアは自然である。

これを定式化するとOptimizer $g_t$ は以下の損失関数 $\mathcal{L}(\phi)$ の最小化を深層学習 $m$ で解いて得られることになる。

　　 $\mathcal{L}(\phi) = \mathbb{E}_f [\sum_{t=1}^T w_t f(\theta_t) ]$ (3)

　 (3)式を以下の繰返しで最小化する

$\theta_{t+1} = \theta_t + g_t$

$[g_t,h_{t+1} ] = m(\nabla_t,h_t,\phi)$

ここで

　　 $w_t$ は深層学習の効率化のための緩和係数　実験では $w_t=1$ を使用

　　 $\nabla_t = \nabla_\theta f(\theta_t)$ で $\theta_t$ での勾配である。

$m$ は深層学習を示す実験ではLSTMに限定していない。

　　 $h_t$ は深層学習の隠変数

　 Learning to Learnの論文では(3)式の最適化過程を下図で示している。上段では式(3)の最適化パラメータ $\theta_t$ (Optimizee)の改善　下段では最適化関数 $g_t$ の改善を示している。　

f:id:mabonki0725:20190101104434p:plain

上図の様なモデル化で高次元の最適化を実現しなければならないが、最適化パラメータの各次元 $\theta^i i=1 \cdots n$ の交差を考えると天文学的な組み合わせになる。そこでLearning to learnでは下図の様に並列に次元数nだけLSTMを提供して実現していてパラメータの交差をしていない。この様なモデルの簡便化で性能が出るのが不思議である。

f:id:mabonki0725:20190101105444p:plain

(2) 実験
　(3)式の $m$ でSDGを含み様々な手法の結果を示しているがLearning to Learn(LSTM)が一番性能がよい。また実験2)でも分る様に１万次元の画像でもよく識別できている。

実験1)

Quadraticは $f(\theta) = || W\theta - y ||_2^2$ を示し $\theta$ は10次元

20個の隠れ変数　2層モデルを使用

f:id:mabonki0725:20190101121241p:plain

実験2）画像の識別

　ここで　LSTM-subとはheld-out label(非学習用データでの区分）の結果

f:id:mabonki0725:20190101121835p:plain — 画像CFIRの識別（10個　5個　２個）結果

　実験3) 複数の損失関数でのLearning to Learn

$f(^theta) = \alpha \mathcal{L}_{content}(c,\theta) + \beta \mathcal{L}_{style}(s,\theta) + \gamma \mathcal{L}_{reg}(\theta)$

f:id:mabonki0725:20190101122328p:plain — 画像と絵画の合成　左端：原画像　中央：合成　右端：絵画

(3) 感想

　次元が高いパラメータでの関数の最適化でLSTMを用いたLearing to Learnが実験で汎用的に適合できることを示したが、何故実現できるかは皆目分らず、やはり深層学習の基本的な解明を必要としている。この辺の議論は最近特に成果が出始めていおり、日本では統数研の今泉さんらの成果がある。

深層学習による非滑らかな関数の推定

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 — 転移学習（濃灰色）と強化学習(薄灰色)での協調台数と運行スピード