[DL輪読会]Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning

DEEP LEARNING JP [DL Papers] Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning Koichiro Tamura, Matsuo Lab http://deeplearning.jp/

• http://deeplearning.jp/

Agenda 1. 2. 3. 4. 5. 6. 7. Paper Information Problem to Solve Abstract Related Work Action Elimination Method Experiment Results 2

PAPER INFORMATION • Learn What Not to Learn: Action Elimination with Deep Reinforcement Learning – Tom Zahavy, Matan Haroush, Nadav Merlis, Daniel J. Mankowitz, Shie Mannor – https://arxiv.org/abs/1809.02121 – Submitted on 6 Sep 2018 – NIPS2018 accepted – RLにおいて，選択可能な行動が多い場合学習が難しい． contextual multiarmed bandits を導入し，「どの行動を取るべきではないか」というActionElimination機構を深層強化学習に取り入れることで，より高速でロバストな学 習を可能にし，膨大な行動空間を持つゲーム`Zork`などで優れたパフォーマン スを示した． 3

• https://arxiv.org/abs/1809.02121

RLにおける課題 • Deep Reinforce Learning(以下DRL)は，Agentの環境の認識力を高め，ドメイ ンナリッジがなくても学習を行うことを可能にした • しかし，実世界への適用において，選択可能な行動が数多ある場合，そして特に それが冗長で見当外れである場合，学習が非効率で現実的ではないという問題が ある – [人間]: 文脈から可能性の低い行動を認知することができる – [RL Agent]: 人間なら取らない行動も取るため，学習が非効率 • 選択可能な行動空間が多い例 – – – – – – 送電網のような大規模工業用システムの制御 交通制御 旅行の計画 レストラン・ホテル予約 チャットボット テキストベースのゲーム 4

本研究の概要 • Action-Elimination(以下AE，行動空間から現実的な行動空間に制約する) を提案 – [既存]: ドメイン知識を導入(ex: ルールベース)することによって，現実的な行 動空間から選択して学習 – [提案]: ドメイン知識や事前知識なしに学習過程で現実的な行動空間を学習 – 無駄な行動や劣っている行動を予測し，制約された行動空間から学習・制御す る方が簡単であるという仮説 • DQN+AEN – Action Elimination Network – NLPのタスクに適応したCNNによって構成される – linear contextual banditsを導入 • `Zork`で検証 – Text-based game 5

関連研究 • DRL with linear function approximation – DNNの最終層において，線形関数を用いて価値関数を更新する • Shallow Updates for Deep Reinforcement Learning[Levine et al., 2017] – 深層強化学習は学習が不安定なので，DLの認識力の高さを活かしつつ，最終層のみ別途線形関 数を更新して学習するやり方 • Deep Bayesian Bandits Showdown[Requelme, 2018](ICLR2018) – Contextual linear banditsでは，neuro-linear Thompson samplingが優れている 6

関連研究 • RL in Large Action Spaces – 多くの既存研究は行動空間をバイナリ空間に要素分解することに注力 – Fast reinforcement learning with large action sets using error-correcting outputs codes for mdp factorization[Dulac, 2012] • 離散的な行動空間を連続(微分可能)な空間に埋め込む方法を提案 – 行動空間を「eliminate」すること自体は，Learning rates for Qlearning[Even-Dar, 2003]で提案されている • 状態ごとに価値関数の信頼区間を学習することで確率的に可能性が低い行動をeliminateす る • Combating Reinforcement Learning‘s Sisyphean Curse with Intrinsic Fear[Lipton et al., 2016]では， (再起不能な行動に伴う)危険な状態を忘却しないようにする重要性が述べら れている 7

Action Elimination • 本研究では，MDPsにelimination signalを加えたアルゴリズムを提案す る • 通常のRLに対して，agentはelimination signal 𝑒 𝑠, 𝑎 というバイナリシ グナルを観測し，𝑒 𝑠, 𝑎 = 1なら状態sの時の行動aを削除する(つまり 状態sの時に行動aを取ることは二度とない) Agentが行動𝑎𝑡 をとった後，報酬𝑟𝑡 ，次の状態 𝑠𝑡+1，elimination signal 𝑒𝑡 を観測する． 観測した情報をもとに，DQNとAENを学習する 8

Action Elimination • 大規模な行動空間がある場合の強化学習において，Action Elimination には以下の議論点がある 1. Function Approximation • • • Q関数の推定値の誤差によって、学習アルゴリズムがsub-optimalな方策に収束する可能 性があり[Thrun, 1993] ，行動空間が大規模である場合は特に顕著 Action Elimination は最適化を有効な行動空間のみに適用することで，上記の問題を改善 し，潜在的に過大評価する可能性を削減 Q-Estimateを有効な行動空間のみで行えばよく， 1. 2. 関数を近似するにあたって無効な行動をサンプリングする必要がない 関数を近似する際によりsimpleな分布で済むことにより，収束速度が早くて正確 9

Action Elimination • 大規模な行動空間がある場合の強化学習において，Action Elimination には以下の議論点がある 2. Sample Complexity • MDP(マルコフ決定過程)における複雑さ(計算量)において，elimination algorithmによっ て行動空間がA->A‘ になった場合，Aሖ ൗAに計算量が減ることが期待される – 報酬関数に間違った(不適切な)行動をとった場合にペナルティを追加するアイデア » – チューニングが複雑で，収束が遅くまたサンプリングも非効率 方策を，報酬最大化とelimination signal errorの最小化の2つのモデルで決定していくというア イデア » 2つのモデルが高いに相関してしまい，互いの観測に対して相互作用してしまう 本研究では，contextual multi-armed banditsを用いることで，elimination signalをMDPから切り離す 10

Action Elimination with Contextual Bandits • Elimination signalは以下のように定義されていると仮定 – 𝑒𝑡 𝑠𝑡 , 𝑎 = 𝜃𝑎∗ 𝑇 𝑥 𝑠𝑡 + 𝜂𝑡 • • 𝜃𝑎∗ は 𝜃𝑎∗ 2 ≤ 𝑆を満たすパラメタ，𝜂𝑡 は平均0のsub-gaussian分布に従うノイズ • 𝑥 𝑠𝑡 は状態𝑠𝑡 を表す特徴表現 Elimination signal を表す𝜃𝑎∗ を推定していく 𝑇 – 𝜃෠𝑡,𝑎 を学習パラメタとして、以下を解く • 𝑇 𝑋𝑡,𝑎 𝜃𝑡,𝑎 − 𝐸𝑡,𝑎 – −1 ത𝑡,𝑎 𝑉 = 𝜆𝐼 + 2 2 𝑇 + 𝜆 𝜃𝑡,𝑎 2 2 𝑇 𝑇 −1 𝑇 ത𝑡,𝑎 を最小にする𝜃𝑡,𝑎 は， 𝜃መ𝑡,𝑎 =𝑉 𝑋𝑡,𝑎𝐸𝑡,𝑎 𝑇 𝑋𝑡,𝑎 𝑋𝑡,𝑎 • 少なくとも1 − 𝛿の確率で，全てのt > 0において以下を保持される 𝑇 𝑇 – 𝜃መ𝑡,𝑎 𝑥 𝑠𝑡 − 𝜃𝑎∗ 𝑥 𝑠𝑡 ≤ 𝛽𝑡 (𝛿)𝑥 𝑠𝑡 𝑇𝑉 ത −1𝑥 𝑡,𝑎 𝑠𝑡 – 数式はImproved algorithms for linear stochastic bandits [Abbasi, 2011]から導入されている – これ以上詳しい文字定義や証明は上記論文や本論文に記載 11

Action Elimination with Contextual Bandits • Elimination signal を表す𝜃𝑎∗ を推定していく(続き) – 𝑒𝑡 𝑠𝑡 , 𝑎 = 𝜃𝑎∗ 𝑇 𝑥 𝑠𝑡 + 𝜂𝑡 より， • Ε 𝑒𝑡 𝑠𝑡 , 𝑎 = 𝜃𝑎∗𝑇 𝑥 𝑠𝑡 𝑇 𝜃෠𝑡,𝑎 𝑥 𝑠𝑡 − 𝜃𝑎∗ 𝑇 𝑥 𝑠𝑡 ≤𝑙 ≤ −1 ത𝑡,𝑎 𝛽𝑡 (𝛿)𝑥 𝑠𝑡 𝑇 𝑉 𝑥 𝑠𝑡 より以下の場合に状態𝑠𝑡 から行 動aを削除する 𝑇 • 𝜃መ𝑡,𝑎 𝑥 𝑠𝑡 − 𝛽𝑡 𝛿 𝑥 𝑠𝑡 −1 𝑇𝑉 ത𝑡,𝑎 𝑥 𝑠𝑡 > 𝑙 • 以上は， 1 − 𝛿の確率で有効な行動の削除はしないということを保証している • Ε 𝑒𝑡 𝑠𝑡 , 𝑎 = 𝜃𝑎∗𝑇 𝑥 𝑠𝑡 は文脈において線形である(0or1のバイナリではない) – 例えば対話Agentの場合，90%相手の発話が理解できなければ発言すべきでない • 𝑙は既知であることを想定しているが，実践的には大体0.5で十分 12

Method ∗𝑇 𝜃𝑎 𝑥 • 𝑒𝑡 𝑠𝑡 , 𝑎 = 𝑠𝑡 + 𝜂𝑡 における 𝑥 𝑠𝑡 は実際のところわからないので、 NNの関数𝜙 𝑠𝑡 で置き換える – 𝑒𝑡 𝑠𝑡 , 𝑎 = 𝜃𝑎∗ 𝑇 𝜙 𝑠𝑡 + 𝜂𝑡 – 実践的には，最適化の過程でactivationsは変化するのに対してcontextual banditsを用いる場合には特徴量が固定されていなければならないことが問題 • そこでA batch-update framework[Levine, 2017]を導入し，2~3ステップ毎に新しい contextual bandit modelを学習する 13

Method 初期化 NNを定義 Elimination 限定された 行動空間か ら価値関数 を推定 14

Experimental Result • Gold World Domain – 9つの部屋があって，中心から左上を目指すゲーム – 1ステップごとに-1のペナルティで，報酬が0になるまで続ける – 状態はあらかじめK個にカテゴライズし，環境下では4Kの行動がある(1カテゴ リにつき4方向への移動があり，それぞれランダムな方向に移動する可能性が ある) – もし選択した行動が現在の状態と同じカテゴリに属していれば，0.75の確率で 正しく(?)動くが，そう出ない場合は0.25の確率(論文では0.5ってなっているけ ど多分間違い，ランダム)で動いてしまう – もし行動がカテゴリに合わなかったら，elimination signal=1 – 最適は方策は，同カテゴリのaction navigationに従うこと 15

Experimental Result • Gold World Domain – 比較として • Vanilla Q-leaning without action elimination(green) • the action elimination Q-learning(blue, 提案手法) • 一つのカテゴリしかない場合(red) 16

Experimental Result • Zork domain – MITのメンバーによって作られたテキストベースで進んで行くRPG的ゲーム 17

Experimental Result • Zork domain – 膨大な状態と行動空間を持つゲームとして最適 – 20のZorkのお宝を集めるて，トロフィーを獲得することが目的 – 最終ゴールにたどり着く行動に対してポイントがもらえる • Ex: パズルを解いて前に進んだ – ゲーム性としていくつかの難点がある • 長期的な目的を達成するために計画を立てる必要があること • ランダムに発生するトロールの攻撃に対処すること • 手がかりなどを覚えておいて，ゲーム内のオブジェクトと特定のアクションの間の相互作 用を認識する必要があること 18

Experimental Result • Zork domain 19

Experimental Result • Zork domain – Open worldだと大きすぎるので、まずはある特定のドメインで実験 • Egg Quest • Troll Quest • 細かいゲーム設定は省略。。 – 特にTroll QuestではAE-DQNが 大幅な改善を示した 20

Experimental Result • Zork domain – 2つの行動空間を用いてOpen worldで実験 • A3: minimal Zork(131actions) • A4: Open Zork(1227actions) 21