[Dl輪読会]introduction of reinforcement learning

Introduction of Reinforcement Learning KEISUKE FUKUTA HARADA USHIKU LAB.

Outline 1. What is RL 2. Classical Algorithm in RL ◦ ◦ TD-learning Policy gradient method 3. Recent DRL application

What is Reinforcement Learning 試⾏錯誤を通じて未知の環境に適応する学習制御の枠組 状態⼊⼒に対する正しい⾏動出⼒を⽰す教師は存在しないかわりに 報酬というスカラーを受け取る 最適な戦略を報酬から間接的に学習

Demo • https://www.youtube.com/watch?v=jXHnBouhAdU

• https://www.youtube.com/watch?v=jXHnBouhAdU

What is RL • 各Time Step 𝑡 = 0, 1, … で Environment 1. Agentは状態 𝑠( ∈ 𝑆 を観測 s 状態 𝑠 Agent

What is RL • 各Time Step 𝑡 = 0, 1, … で 1. Agentは状態 𝑠( ∈ 𝑆 を観測 2. 状態 𝑠( に応じて⾏動 𝑎( ∈ 𝐴 を選択 Environment s ⽅策 𝜋 𝑠 Agentの⾏動規則 状態から⾏動への写像 𝜋 ∶ 𝑆 → 𝐴 ⾏動 𝑎 𝜋(s) Agent

What is RL • 各Time Step 𝑡 = 0, 1, … で 1. Agentは状態 𝑠( ∈ 𝑆 を観測 2. 𝜋(𝑠( ) を利⽤して⾏動 𝑎( ∈ 𝐴 を選択 Environment s s’ 3. 環境は 𝑠( → 𝑠(34 に遷移する 𝜋(s) Agent

What is RL • 各Time Step 𝑡 = 0, 1, … で 1. Agentは状態 𝑠( ∈ 𝑆 を観測 2. 𝜋(𝑠( ) を利⽤して⾏動 𝑎( ∈ 𝐴 を選択 Environment s s’ 3. 環境は 𝑠( → 𝑠(34 に遷移する 4. Agentは環境から 報酬𝑟( ∈ 𝑅 と 𝑠(34 を観測 状態 𝑠′, 報酬 𝑟 𝜋(s) Agent

What is RL • 各Time Step 𝑡 = 0, 1, … で Environment 1. Agentは状態 𝑠( ∈ 𝑆 を観測 2. 𝜋(𝑠( ) を利⽤して⾏動 𝑎( ∈ 𝐴 を選択 s’ s 3. 環境は 𝑠( → 𝑠(34 に遷移する 4. Agentは環境から 報酬𝑟( ∈ 𝑅 と 𝑠(34 を観測 𝑠 𝑎 𝑠′, 𝑟 • ⽬標 : 累積報酬 ∑( 𝑟( を 最⼤化する⽅策 𝜋(𝑠) の獲得 （普通は、減衰係数 𝛾 を導⼊し、∑( 𝛾 (:4𝑟(とする） 𝜋(s) Agent

Characteristic of RL • 教師は存在せず、報酬のみで学習 • Agentは環境についての事前知識はない ◦ プランニングとの違い（両⽅組み合わせることもある, Ex. Guided Policy Search） • 報酬のフィードバックは遅れてやってくる ◦ ある瞬間の⾏動が正しかったかの判断が難しい • 時間という概念 (sequential, non i.i.d data) • Agentのある時刻での⾏動が後に影響を与える • Markov decision Process ◦ マルコフ性 : 𝑃 𝑠(34 , 𝑟( 𝑠( , 𝑎 ( , 𝑠(:4 , 𝑎 (:4 … 𝑠< , 𝑎 < ) =𝑃 𝑠(34 , 𝑟( 𝑠( , 𝑎 ( ) ◦ マルコフ性を満たす環境下でのAgentの意思決定をMDP (Markov decision Processes)と呼ぶ

Applications of RL • ゲームプレイ (ex. Atari, Backgammon, Go) ◦ ゲームに勝つ、スコアを獲得することが⽬標 • ヘリコプター制御 ◦ 墜落せずに⾶⾏することが⽬標 • ロボットの歩⾏制御 ◦ 倒れずに進むことが⽬標 • ⾦融取引 ◦ リスクを⼩さく資⾦を増やすことが⽬標 • 電⼒最適化 ◦ 閾値を超えない範囲で効率化 • 対話システム ◦ 会話が破綻させないことが⽬標

Example Atari • ⽬標 : ゲームのスコアの最⼤化 • 状態 𝑠( : ゲーム画⾯ (markov性を持たせるために4timestep分の画⾯) • ⾏動 𝑎( : ボタン⼊⼒ • 報酬 𝑟( : スコア

Components of RL • ⽅策 : ◦ Agentのふるまいを決める関数 • 価値関数: ◦ 各状態や⾏動がどれくらい良いのかを評価する関数

Value Function • この状態はどれくらい良いのか (囲碁、将棋でいうと盤⾯の評価) • この状態でこの⾏動を取ると将来どうなりそうか 状態価値関数 V > 𝑠 状態 𝑠 において、そこから⽅策𝜋に従って⾏動した とき、最終的に獲得できる累積報酬を予測する関数 時刻tで状態stにいる価値 G𝑟 V > 𝑠 = 𝔼@~B,C~D,E~> [ ∑I 𝛾 (3G | 𝑠( = 𝑠 ] GJ< ⾏動価値関数 𝑄 > (𝑠, 𝑎) 状態 𝑠 において、 ⾏動𝑎を取り、そこから⽅策𝜋に従って⾏動したと き、最終的に獲得できる累積報酬を予測する関数 G Q> 𝑠, 𝑎 = 𝔼@~B,C~D,E~> [ ∑I GJ< 𝛾 𝑟(3G | 𝑠( = 𝑠, 𝑎( = 𝑎 ] 状態 st 時刻tで状態stにいるとき ⾏動atをとる価値 状態 st ⾏動 at

Classification of RL • Model free or Model based ◦ 環境の情報(ダイナミクス 𝑃(𝑠(34 |𝑠( , 𝑎()等)を使⽤するかどうか • On-policy or Off-policy ◦ 意思決定に使⽤される⽅策を直接改善するかどうか • Value based or Policy based ◦ 価値関数を学習するか、明⽰的に⽅策を学習するか

Value based or Policy based • Value-based ◦ 価値関数を学習, Implicitな⽅策を利⽤ ◦ Ex. TD-learning (Sarsa, Q-learning, TD(𝜆)) • Policy-based ◦ 価値関数を学習せず, ⽅策を直接学習する ◦ Ex. REINFORCE, Guided policy search • Actor-Critic ◦ 価値関数を学習し、それをもとに⽅策も学習 ◦ Ex. DDPG,

TD Learning (Temporal-Difference Learning) Bellman Equation 累積報酬 = 即時報酬 + その先の未来でもらえる期待報酬 V > 𝑠 = 𝔼>,@ [ 𝑟( + 𝛾 𝑉 > (𝑠 U )] Q> 𝑠, 𝑎 = 𝔼>,@ [ 𝑟( + 𝛾 𝑄 > (𝑠 U , 𝜋(𝑠′)] • Bellman Equationを利⽤して価値関数を更新 V> 𝑠 ← 𝛼 V> 𝑠 + (1 − 𝛼) { 𝑟( +𝛾 𝑉 > (𝑠 U )} Q> 𝑠, 𝑎 ← 𝛼Q> 𝑠, 𝑎 + 1 − 𝛼 {𝑟( +𝛾 𝑄 > (𝑠 U , 𝜋 𝑠 U } • エピソードの終了を待たずに即時更新できるのが強い • 脳はこんなようなことをやっているらしい

Q-learning 最も基本的な強化学習アルゴリズムの⼀つ (model-free, off-policy, value-base) • ⾏動価値関数を最適化 • Greedyな⽅策𝜋 𝑠 = arg max 𝑄(𝑠, 𝑎) を利⽤ E • 更新式 Q> 𝑠, 𝑎 ← 𝛼Q> 𝑠, 𝑎 + 1 − 𝛼 {𝑟( +𝛾 max 𝑄(𝑠 U, 𝑎U)} EU • 常にQ値の⾼い⾏動を選択するというpolicyを採⽤することで学習が効率化 → 常に⾼いのしか選ばなかったらまだ選んだこと無いけど良い⾏動が学習されないのでは？

Exploitation-Exploration Trade-off Multi-armed bandit ◦ 腕が数本あるスロットマシン ◦ それぞれの腕毎に出てくる賞⾦額とその確率は違う ◦ 限られた回数で多くの賞⾦がほしい バカ：1回⽬で腕Aで1000円当たった → 腕Aしか回さない 賢者：腕Aは確かに悪くない。けど他にもいいのがあるかもしれないから試してみたい → Exploitation-Exploration Trade off 探索 Exploration 活⽤ Exploitation

Q-learning • Greedy 法 ◦ 𝜋 𝑠 = arg max 𝑄(𝑠, 𝑎) E • 𝜖 - Greedy法 ◦ 確率 𝜖 で ランダムな 𝑎 : Exploration ◦ 確率 1 - 𝜖 で arg max 𝑄(𝑠, 𝑎) : Exploitation E ◦ 多くの場合、学習と共に𝜖 を⼩さくしていく（バランスを気をつけないと、局所解に） • Softmax⾏動基準 ` ab/d ◦ 𝑋^ = 𝑄 𝑠, 𝑎^ とすると、𝑝 𝑎^ = ∑ b` a b/d ◦ 探索においても、価値の⽐によって選ばれ⽅が変わる

Representation of Value Function 状態価値V Q(s,a)だったらテーブル 状態価値V 状態s 0.1 0.5 1.0 1.5 0.0 0.3 0.1 … 0.2 0.1 迷路とかの単純な状態空間なら良いが、状態空間が爆発するとき困る

Function Approximation of Value Function 状態価値V 𝑉 𝑠 =𝑓 𝑠 , 𝑠 = (𝑥<, 𝑥4, … ) 状態s 関数 𝑓 には、線形モデルだったり、⼀般化線形モデルだったりが選ばれる

DQN • Q - learning における⾏動価値関数の関数近似においてCNNを使⽤ • 価値関数のNNによる近似⾃体は昔からある ◦ TD – Gammon [Tesauro, 1994] じゃあ何が新しいのか • Q-learningは、関数近似に線形なモデルを利⽤し、適切な学習率を設定し ⼗分な探索が⾏われた場合収束することが理論的に保証されている → CNNのような複雑な⾮線形モデルの場合収束が保証されない → 頑張って収束させた!! (そのためのいろんな⼯夫）

Experience Replay 強化学習 × DNN の難しさ • DNNを学習させる際、データサンプルはi.i.d.である必要 → But! 強化学習では、 ◦ 似たような状態⼊⼒が続く (⼊⼒に相関） ◦ ゲームの進⾏状況によるサンプルのdistributionの変化 ◦ ⼀度覚えたことを忘れてしまう • そもそも学習に⼤量サンプル必要 ◦ 環境とのインタラクションを何度もしなければならない 学習が不安定 サンプルを集めるのに ⾮常に時間がかかる どこか(Replay buffer)に経験をサンプル保存しておいて、 更新するときはそこから確率的に取り出して更新しよう！！ Off-policyにのみ適⽤可能

Value based or Policy based • Value-based ◦ 価値関数を学習, Implicitな⽅策を利⽤ ◦ Ex. TD-learning (Sarsa, Q-learning, TD(𝜆)) • Policy-based ◦ 価値関数を学習せず, ⽅策を直接学習する ◦ Ex. REINFORCE, Guided policy search • Actor-Critic ◦ 価値関数を学習し、それをもとに⽅策も学習 ◦ Ex. DDPG,

Explicit Policy • Value-based ◦ Implicitな⽅策 ex. Q-learning 𝜋 𝑠 = arg max 𝑄 𝑠, 𝑎 E → ⾏動𝑎 の取りうる選択肢が⾮常に多かったら？ → 確率的な⽅策を表現したかったら？ → ロボットの制御みたいに連続値を扱いたかったら？ 𝜋 𝑠 を明⽰的に導⼊ Policy gradient method Guided policy search .. Etc.

Explicit Policy • Advantages: ◦ 収束しやすい ◦ 連続空間、⾼次元空間に適⽤可能 ◦ デモンストレーションから学習することも可能 ◦ 探索を直接的にコントロールできる ◦ 確率的な⽅策も学習可能 • Disadvantages: ◦ 局所解に陥りやすい ◦ ⽅策の評価の効率が悪いことが多い • Policyの学習⽅法は⼤量にある (policy search)

Policy Search

Example Cart pole balancing (Mujoco simulator) • ⽬標 : 棒を垂直に維持する • 状態 : ゲーム画⾯、もしくは速度、回転⾓等の物理量 • ⾏動 : ⼊⼒トルク • 報酬 :cos 𝜃 (𝜃 : 棒の⾓度 )

Policy Gradient Method これまた古典的なアルゴリズムだがよく使⽤される • ⽬的関数 𝐽 𝜋l = m𝜌> m 𝜋 𝑠, 𝑎 𝑟 𝑠, 𝑎 𝑑𝑎 𝑑𝑠 = 𝔼@~r,E~>s 𝑟 𝑠, 𝑎 o q • 𝐽 𝜋l を最⼤にするような⽅策𝜋lを求めたい → そのために、𝛻l 𝐽 𝜋l を求めて𝜋l を更新したい Policy gradient • 𝛻l 𝐽 𝜋l を求める⽅法として ◦ Likelihood ratio method ◦ Value gradient

Likelihood Ratio Method ⽬的関数 求めたい policy gradient 𝐽 𝜋l = m𝜌> m𝜋 𝑎|𝑠 𝑟 𝑠, 𝑎 𝑑𝑎 𝑑𝑠 o 𝜋 𝑎|𝑠 は確率的な⽅策 q 𝛻l 𝐽 𝜋l = m𝜌> m𝛻l 𝜋 𝑎|𝑠 𝑟 𝑠, 𝑎 𝑑𝑎 𝑑𝑠 o q = 𝔼@~r,E~>s 𝛻l log 𝜋l (𝑎|𝑠) 𝑟 𝑠, 𝑎 ≅ 1 𝛻l log 𝜋l (𝑎|𝑠) 𝑟 𝑠, 𝑎 𝑀 𝛻l 𝜋 𝑎|𝑠 = 𝜋 𝑎|𝑠 Score function と呼ぶらしい パラメータ化された確率分布を微分したいがReparametrization trickが使えないとき最近よく⾒る ◦ Hard Attentionとか > E|@ = 𝜋 𝑎|𝑠 𝛻l log 𝜋l (𝑎|𝑠) • サンプリングによって勾配を推定できる！ • us > E|@

Likelihood Ratio Method • 結局 : 𝛻l 𝐽 𝜋l ≅ 4 y 𝛻l log 𝜋l (𝑎|𝑠) 𝑟 𝑠, 𝑎 • 𝑟 𝑠, 𝑎 ◦ 実際に得られた報酬を利⽤ ◦ REINFORCEと呼ばれる ◦ 真の報酬であるのでUnbiasだが、サンプリングなので勾配推定の分散が⼤きい ◦ ⾏動価値関数 𝑄 > 𝑠, 𝑎 による近似を利⽤ ◦ Varianceは下がるが近似なので当然biasが⼤きい。うまいことやる必要 ◦ 両⽅使う ◦ Control Variate ◦ 期待値を求めたいものから解析的に計算できるbaselineを引いて分散を⼩さくする ◦ Baselineに状態価値関数を利⽤し、Advantage functionを ◦ Advantage function 𝐴> 𝑠, 𝑎 = 𝑄> 𝑠, 𝑎 − 𝑉 > 𝑠 ≅ r + γ 𝑉> 𝑠 U − V > (s)

Value Gradient • ⾏動価値関数 𝑄 > 𝑠, 𝑎 の勾配を直接使って更新したい ◦ 𝑄 > 𝑠, 𝑎 が⼤きくなる⽅向に 𝑎 を動かそう ◦ Experience Replayが使える！ • Deterministic policy gradient [Silver et al., ICML, 2015] ◦ 決定的な⽅策 𝜇l (𝑠) を導⼊し、𝑄 | 𝑠, 𝜇l (𝑠) を直接 𝜃 で偏微分することで勾配を推定する ◦ 𝛻l 𝑄 | 𝑠, 𝜇l (𝑠) = 𝛻E 𝑄 | 𝑠, 𝑎 ⋅ 𝛻l 𝜇l ◦ DDPG (Deep deterministic policy gradient) [Lillicrap et al., ICLR, 2016]は 𝑄, 𝜇をCNNでモデル化したもの • Learning Continuous Control Policies by Stochastic Value Gradients ◦ Reparametrization TrickによりStochastic policy にも適⽤可能に

Policy Gradient Method ~summary~ • Likelihood ratio ◦ Bias ⼩・Variance⼤ ◦ On-policy ◦ 学習はある程度安定するが、⼤量のデータサンプルが必要 • Value gradient ◦ Bias ⼤・Variance ⼩ ◦ Off-policy ◦ Experience Replay が使えるためサンプル efficient だが、ハイパラ調整が闇

Design of Reward • ゴールまで⾏きなさいという問題 ◦ 例 1）ゴールに近づいたら (+1), ゴールで⾼い報酬 (+100) → たどり着くまでかなり時間がかかる ◦ 例 2) ポテンシャルに応じた報酬設定 ◦ → ⾼速に学習は進むが、ハイパラ増える、設計⼤変 報酬の設計に関する研究 ◦ ⾼速に探索が進むような報酬の⽣成⽅法の研究 ◦ Reward shaping ◦ 徒弟学習 ◦ 逆強化学習

Inverse Reinforcement Learning • 強化学習では、与えられる報酬＝良さを元に最適な戦略を推定する • 逆強化学習では、最適な戦略から報酬＝良さを推定する 強化学習 報酬 最適な戦略 逆強化学習

Recent DRL ① Learning Hand-Eye Coordination for Robotic Grasping with Deep Learning and Large-Scale Data Collection [Sergey Levine et al., 2016] • Googleがロボットアーム14台並列に動かして 物体のグラスピングを学習させてたやつ • 概要 1. 様々な状況でモーターを動かしてみて、成功したか失敗したかのサンプルを保存 2. 保存したサンプルを利⽤して、Prediction Network 𝑔 𝐼( , 𝑣( { 𝐼( : 視覚情報, 𝑣( : サーボへの命令 }を supervised-learning 3. サーボへの命令は、サンプリングベースで𝑔 𝐼( , 𝑣( が⾼くなるのを選ぶ • 強化学習とよく⾔われるが、 self-supervised learningと呼ばれる ⾃分でデータサンプルを集めて学習する枠組み

Recent DRL ② End-to-End Training of Deep Visuomotor Policies [Sergey Levine, 2015] • UCバークレーのロボットが最初はランダムだが、 だんだん鍵⽳に鍵させるようになるやつ • Guided Policy Search, iLQG ◦ Policy based ◦ TD学習とかとは全く異なるアプローチ ◦ 近傍のダイナミクスを線形近似し、ローカルに最適解を解析的に解く、制御理論という感じ ◦ 強化学習⾃体広い意味を持つのでこれも含まれる

Recent DRL ③ Asynchronous Methods for Deep Reinforcement Learning [Mnih et al., 2016] • ⾮同期に多数のエージェントを⾛らせてパラメータを 同時に更新することでサンプル数を確保すると同時に ⼊⼒の相関をなくすことができる → Experience Replayを使う必要がない → on-policyなRLアルゴリズムが使⽤可能!! • Advantage functionを⽤いたActor-Criticを⾮同期で⾛らせた 結果、CPUで１⽇たった時点で他⼿法を⼤きく上回る (A3C : Asynchronous Advantage Actor Critic)

Recent DRL ④ Continuous Deep Q-Learning with Model-based Acceleration (NAF) • Q-learningを連続空間に適⽤可能に ◦ Advantage部分とState-Valueに分け、Aの⽅を⼆次形式の形で推定することでarg max 𝑄 𝑠, 𝑢 を計算 Normalized Advantage Function • iLQGのように近傍のダイナミクスを推定することで Model-basedの⼿法を取り⼊れたい ◦ Imagination rollout ‚

Recent DRL ⑤ Trust Region Policy Optimization (TRPO) • Policy based • 𝐷…† 𝜃‡ˆ‰ , 𝜃 ≤ 𝛿 (Trust Region )という範囲において、サンプリングによって計算された期待コストを 最⼩化する𝜃を制約付き最適化問題を解くことで求め逐次的に更新 • サンプリング法 ◦ Single Path : 𝑠< から𝜋lに従い軌跡を⽣成する⽅法 ◦ Vine: ランダムシミュレーションにより⽣成する⽅法 • 学習の流れ ◦ Single pathかVineでサンプル（軌跡と報酬）を集める ◦ サンプルから制約条件と⽬的関数を構築 ◦ 制約付き最適化問題を解く ◦ 中⾝はよくわからなかったです

Recent DRL ⑥ Q-prop • Actor-Critic • Off-policyに学習するcriticをbaselineとして利⽤して、 On-policyなpolicy gradientをsample efficient かつunbiasに利⽤する⽅法

おまけ Connecting Generative Adversarial Networks and Actor-Critic Methods [DeepMind, 2016] • GANとActor-Criticの関係 ◦ GANは、Actorが報酬に影響を与えない状況下でのActor-Criticと同じなのでは？ • それぞれで使⽤される学習テクニックを⽐較、お互いに利⽤できないか ◦ GAN ◦ Freezing learning, Label smoothing, Historical averaging, Minibatch discrimination, BN ◦ Actor-Critic ◦ Experience Replay, Target networks, Entropy regularization, Compatibility?

Reference • David silverの講義資料 ◦ http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/intro_RL.pdf • Policy search資料 ◦ http://icml.cc/2015/tutorials//PolicySearch.pdf

• http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/intro_RL.pdf
• http://icml.cc/2015/tutorials//PolicySearch.pdf

Recent Technique • Prioritized Experience Replay ◦ 重要な経験サンプル(TD-errorが⼤きかったもの)を優先的にサンプルするExperience Replay • Deep Reinforcement Learning with Double Q-Learning ◦ DQNのDouble Q-learning版

Applications of RL • • • ヘリコプター制御 http://heli.stanford.edu/ ◦ ⼈間のエキスパートの技を学習させるために、逆強化学習 (Inverse Reinforcement Learning）を利⽤ Windows ヘルプ⽂書理解 http://groups.csail.mit.edu/rbg/code/rl/ ◦ Windows のヘルプに出てくる操作⼿順の⾃然⾔語に対応する操作を学習します。従来であれば教師付き学習の枠組で研究されて いた問題ですが「指⽰通りの操作が不可能」な場合に対して負の報酬を割り当て、どこまで指⽰に従った操作ができるかを強化 学習によって学習することで、 教師データがない、あるいは少量しかない場合でも、精度の⾼い学習ができることを⽰しました。 ⾳声対話システム http://mi.eng.cam.ac.uk/research/dialogue/ ◦ Cambridge ⼤の Young らが開発した⾳声対話システムでは、ユーザーがシステムにしてほしい要求を隠れた状態と考え、ユーザー の発話内容を観測することで要求を明らかして対応する POMDP 問題と考えることで、最も適切な応答を学習すします。ノイズに よって発話内容が正しく観測できない場合でも、従来のシステムに⽐べはるかに良い応答が実現できることが⽰されており、今 後の実⽤化が期待されます。 • 構⽂解析 http://www.umiacs.umd.edu/~hal/SPIRL/10-07-acl-spirl.pdf ◦ 構⽂解析を⾼速化するためには、すべての可能性を探索するのではなく、より⽂らしくなるような候補を先に探索することが有 効です。 解析途中にどの選択肢を選ぶかを⾏動と考え、逆強化学習の枠組で解くことで、この⾼速化が達成できることを⽰しました。 同様のテクニックは、⾃然⾔語処理に限らず、探索問題全般に適⽤可能であり、⾯⽩いアプローチとして注⽬を集めています。 • 滞納債務の取り⽴て(論⽂ http://www.prem-melville.com/publications/constrained-reinforcement-learning-kdd2010.pdf、 講演動画 http://videolectures.net/kdd2010_abe_odcucrl/)

• http://heli.stanford.edu/
• http://groups.csail.mit.edu/rbg/code/rl/
• http://mi.eng.cam.ac.uk/research/dialogue/
• http://www.umiacs.umd.edu/~hal/SPIRL/10-07-acl-spirl.pdf
• http://www.prem-melville.com/publications/constrained-reinforcement-learning-kdd2010.pdf
• http://videolectures.net/kdd2010_abe_odcucrl/