機械学習勉強会～強化学習～ 11/18 江原遥

強化学習 Agentが環境の状態sを観測できる場合 Agentが環境の状態sを観測出来ない場合 報酬 r 環境 Agent 状態 s Markov Decision Process (MDP)モデル．6件． 理論解：Bellman方程式の解 実用的解法：fixed point iteration TD(0)学習，TD(λ)学習などなど． Agentが環境の状態sを観測出来ない場合 sの代わりにAgentが環境を観測した値oは分かる Partially Observable MDP (POMDP)モデル 2件 (#593, #588) online学習

reinforcement 1 187 Convergence of Least Squares Temporal Difference Methods Under General Conditions, H. Yu 336 Least-Squares λ Policy Iteration: Bias-Variance Trade-off in Control Problems, Christophe Thiery, Bruno Scherrer 598 Finite-Sample Analysis of LSTD, Alessandro Lazaric, Mohammad Ghavamzadeh,Remi Munos 654 Should one compute the Temporal Diference fixed point or minimize the Bellman Residual ? The unified oblique projection view, Bruno Scherrer

reinforcement 2 Partially Observableな条件設定の論文 この論文の記法でMDP, TD学習などを説明 269 Bayesian Multi-Task Reinforcement Learning, Alessandro Lazaric, Mohammad Ghavamzadeh 295 Temporal Difference Bayesian Model Averaging:A Bayesian Perspective on Adapting Lambda, Carlton Downey, Scott Sanner 588 Approximate Predictive Representations of Partially Observable Systems, Monica Dinculescu, Doina Precup 593 Constructing States for Reinforcement Learning, M. M. Hassan Mahmud Partially Observableな条件設定の論文

モデル・ベース，モデル・フリー 今日の話は全部こっち Agent 環境s r a 環境がどういう状態の時にどういう行動を起こすと，どういう報酬が帰ってくるか，網羅的に分からなくても動作する

Markov Decision Process MDPは<S, A, T, R>で 定義される S={s1,...,sn}:状態の集合 A={a1,...,an}:行動 状態遷移確率．T:SxAxS→[0,1]. T(s,a,s’)=P(s’|s,a) 報酬関数:R(s,a,r)=P(r|s,a) Agent 環境s a

MDPの目的：最適方策を求めたい S={s1,...,sn},A={a1,...,an} T(s,a,s’)=P(s’|s,a),R(s,a,r)=P(r|s,a)で定義される 方策(Policy) π：π(s,a)=P(a|s) 状態価値観数:Vπ(s)．この方策に従って状態sから行動を決定していったときの割引率γでの累積報酬． MDPの目的は最適方策π*を求めること ∀π, s;Vπ*(s)≧Vπ (s) π*の存在証明(Puterman, 94) Agent r 環境s a

1) Bellman方程式 例えば，状態が４つの時は次の連立方程式を解くことに． 最適方策π*を求める問題が，定点V*を求める問題に帰着． π*:S→Aは，各sに対して とすればよい・ 例えば，状態が４つの時は次の連立方程式を解くことに．

2) 定点法 V*を定点法(fixed point iteration)で求めたい． TD(0)学習 行動価値関数Q： 状態だけでなく，行動に関しても累積報酬を拡張． TD(0)学習

TD(0)学習

TD(λ)学習 α：学習率 Rt(1) の代わりに これを使う→ λ=0.5の場合

TD(λ)学習のλを，ベイズを使って上手く設定する手法（TD-BMA)を提案．実験的に，手動でλを設定するよりよいことを示した. 295 Temporal Difference Bayesian Model Averaging:A Bayesian Perspective on Adapting Lambda, Carlton Downey, Scott Sanner TD(λ)学習のλを，ベイズを使って上手く設定する手法（TD-BMA)を提案．実験的に，手動でλを設定するよりよいことを示した.

SARSA（λ）．TD（λ）学習の一種

Gaussian Model

提案手法

結果 全てのタスクにおいて，青（提案）が，それ以外（既存手法）に対して勝っている．

結果２ どの学習率αにおいても，提案手法でλを決めた方が勝っている．

269 Bayesian Multi-Task Reinforcement Learning, Alessandro Lazaric, Mohammad Ghavamzadeh

概要 問題設定がMulti-Taskで新しい． 複数の似たタスクがあるが，個々のタスクから取得できるsample（state,action,rewardの列）は限られているので強化学習をjointで解きたい． タスクが似ている，ということを，価値関数に共通のpriorがあるということで表現する． さらにpriorのクラスを用意して，タスクに自動的にクラスを振る．クラス数もDPで決定． InferenceはEM.

Graphical Model xは状態 提案手法： Figure 1. Graphical representations for (a) the single-task model ｡ｪ an extension of GPTD by defining a hyper-prior over the parameters, (b) the single-class multi-task model of Section 3, and (c) the multi-class multi-task model of Section 4.

結果 Single ClassとMulti Classの場合を比較すると，MCMulti Task Learningの方がよい．

336 Least-Squares λ Policy Iteration: Bias-Variance Trade-off in Control Problems, Christophe Thiery, Bruno Scherrer

概要 既存にあったLSPIという更新手法に対して，LSλPIという新しい更新の方法を提案して，"Performance Bound"を求めた． LSλPIの位置づけ

598 Finite-Sample Analysis of LSTD, Alessandro Lazaric, Mohammad Ghavamzadeh,Remi Munos

概要 pathwise-LSTD(λ）学習に対して，有限個のサンプルが与えられた場合に，真の価値関数にどれぐらい近づけるかのboundを求めた． まず，状態系列が与えられた場合のバウンドを示した．次に，状態系列がstationary β-mixing processで生成される場合の一般的なboundを示した．

ヤブヘビ

187  Convergence of Least Squares Temporal Difference Methods Under General Conditions, H. Yu

概要 off-policy LSTD（λ）に使われているiterationについて，収束とバウンドを求め，さらに実用的な実装のための改善方法を提示．

654 Should one compute the Temporal Diference fixed point or minimize the Bellman Residual ? The unified oblique projection view, Bruno Scherrer

概要 TD(0)も，Bellman方程式を解くのも，それぞれ，異なる目的関数をminizeしているとみなせる． その目的関数同士の美しい関係を導いた． 具体的には，Bellman方程式のoblique projectionとみなせる． 結果としては，それぞれ一長一短ですよ．

ヤブヘビ Bellman方程式： r（状態）：報酬関数

Markov Decision Process （再掲） MDPは<S, A, T, R>で 定義される S={s1,...,sn}:状態の集合 A={a1,...,an}:行動 状態遷移確率．T:SxAxS→[0,1]. T(s,a,s’)=P(s’|s,a) 報酬関数:R(s,a,r)=P(r|s,a) Agent 環境s a

Partialy Observableなモデル POMDP Agent 環境s o MDPは< S,A,O,T,Ω,R >で 定義される http://en.wikipedia.org/wiki/Partially_observable_Markov_decision_process a

belief state 環境の真の状態は分からないので，観測oから推測した，環境が状態sにいる確率b(s)を用いる．bをbelief stateという．

POMDPのBellman方程式 MDPのBellman方程式 方策πとbelief state bが与えられたときの累積報酬を最大化 τ(b,a,o)：今のbelief stateがbで 行動aを行ってoが観測されたときの 次のbelief state. 価値関数Vをstateの代わりにbelief stateの関数として，その定点を求める問題に帰着． MDPのBellman方程式

588 Approximate Predictive Representations of Partially Observable Systems, Monica Dinculescu, Doina Precup

概要 POMDPは，直前のobservationとactionとbelief stateによって，今のbelief stateが決まるモデル． 一方，過去の全てのobservation-action系列から，未来のobservation-action系列を予測する手法として，例えばlinearPSRがある． このobservation-action系列を予測する問題に対して，新しい問題の定式化を行い，L1正則化を用いて疎な解を求める方法を提案している．

593. Constructing States for Reinforcement Learning, M. M 593 Constructing States for Reinforcement Learning, M. M. Hassan Mahmud

概要 環境が直接観測できない場合に標準的に使用されるモデルであるPOMDPには，学習時のパラメータを設定するのが難しいという問題点があった． そこで，POMDPの表現力を落として決定的にした代わりに，より学習が容易なdeterministic Markov Model (DMMs)を提案する．さらに，このモデルに対するベイズ法を用いた学習法を示す．

まとめ 環境の状態が見えるobservableな状況設定（MDPなど)と，Partially Observableな状況設定（POMDPなど)がある 価値関数には２種類．V：状態価値関数，Q：行動価値関数．最適な方策(policy)を求めることは，価値関数の定点を求めことに帰着． 価値関数に対するfixed point iterationの研究が盛ん．TD学習などもその一例．新奇なアルゴリズムの提案や，アルゴリズムのbound,収束証明など．online学習とも関連？