) 1 | , t t t p s s a + ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 , ,..., , | | , | , T T T t t t t t t p p s a s a p s p a s p s s a + = = = ( ) , t t r s a 和の期待値=期待値の和 ( ) ( ) ( ) ( ) ( ) * ~ , ~ , 1 argmax , argmax , t t t t t t p t T t t s a p s a t t E r s a E r s a = = = i i i i E n E n = ( ) | t t a s なお,取られる軌道τの確率分布は次式で定義 (グラフィカルモデルの通り)
) 1| , exp , t t t t t p s a r s a = ※Oの表記が論文と異なりますが Mathtypeにないのでご了承ください。 • の時、最適であるという意味 • の時、最適でないという意味 • この定義は恣意的だけど… (これで上手くいくので気にしない) (授業中にSergeyもそういってたはず) 1 t = 0 t =
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: 1 1 1 1 1 1 1 1 1 1 | 1 , 1 1| , | , exp , | , | , exp , T T T t t t t t t t T t t t t t t T T t t t t t t t p p p s p s a p s s a p s r s a p s s a p s p s s a r s a + = + = + = = = = = = = = <Optimalityの導入した下での軌道τの確率分布> 結局、ダイナミクスの遷移的に可能性が高くて、かつ、 expの収益が大きい軌道τがOptimality=1のもとで取得される (直感的) optimalityの 定義そのまま ベイズの定理 (よくやるやつ) optimalityの定義そ のまま PGMみて展開
Message ‐ すべての時刻においてOptimalityが1、かつtでの状態を 与えられたもとでの行動の確率分布 ➔ Policy Computation ‐ ある時刻t-1までのOptimalityが1とした時の状態の確率分布 ➔ Forward Message 2020/5/23 -11- ( ) 1: | , 1 t t T p a s = ( ) ( ) : , | , t t t t T t t s a p s a = ( ) ( ) 1: 1 | t t t t s p s − = 様々なもの (方策や状態の 確率分布など) を計算するのに 必要な3つ : 1 t T = : t T 厳密推論
| , t t t t T t t s a p s a = ( ) ( ) ( ) ( ) ( ) ( ) : : 1 1 1: 1 1 1 , | , , | , | | , | , t t t t T t t t T t t t t t T t t t t t t t t s a p s a p s s a ds p s p s s a p s a ds + + + + + + = = = <Backward messageを漸化式スタイル(次の時刻のβt+1でβtを表現)へ> ( ) ( ) ( ) 1: 1 1: 1 1 1 1 1 | | , | t T t t T t t t t t p s p s a p a s da + + + + + + + + = ( ) 1 1 1 , t t t s a + + + ダイナミクス Optimality の定義 これはなに? Optimalityが与えられない もとでの方策(Action Prior)※ (ここはランダムで良いので定数) ➔ なんか漸化式っぽくできそうな。。。? ※これについては省略して良い (興味ある方は第15回のスライドの The action Priorをみてください) 変数追加+周辺化 なので意味なし PGM(左上)を見ると Ot+1以降はat,stからst+1が 与えられもとで条件付き独立 (親ノードの話@須山緑本) Y X Z given 厳密推論
( ) ( ) ( ) 1: 1 1 1 , | | , | , t t t t T t t t t t t t t s a p s p s s a p s a ds + + + + = ( ) ( ) ( ) 1: 1 1: 1 1 1 1 1 | | , | t T t t T t t t t t p s p s a p a s da + + + + + + + + = ( ) ( ) ( ) ( ) 1 1 1 1 ~ | , , | , t t t t t t t t t t t t s p s s a s a p s a E s + + + + = ( ) ( ) ( ) ~ | , t t t t t t t t a p a s s E s a = ( ) | , t t t p s a 1 t s + 期待値に書き直しただけ。 新しくβt(st)を導入 ➔ ➔ ( ) ( ) ( ) ( ) 1 1 1 1 ~ | , , | , t t t t t t t t t t t t s p s s a s a p s a E s + + + + = ( ) ( ) ( ) ~ | , t t t t t t t t a p a s s E s a = for t = T-1 to 1: (後ろから計算できる!) 厳密推論
) ( ) ( ) 1 1 1 1 ~ | , , | , t t t t t t t t t t t t s p s s a s a p s a E s + + + + = ( ) ( ) ( ) ~ | , t t t t t t t t a p a s s E s a = for t = T-1 to 1: (後ろから計算できる!) <Backward messageを漸化式スタイル(次の時刻のβt+1でβtを表現)へ> ここで次のように置いてみる (発音が似てるし!by sergey) ( ) ( ) log t t t t V s s = ( ) ( ) , log , t t t t t t Q s a s a = ( ) ( ) ( ) log exp , t t t t t V s Q s a da = と書くことができる! ( ) ( ) exp , , t t t t t t Q s a s a = なので 厳密推論
あれこれは。。。? Q関数? ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 ~ | , 1 1 ~ | , , | , log , log | , log t t t t t t t t t t t t t t t t s p s s a t t t t t t t t s p s s a s a p s a E s s a p s a E s + + + + + + + + = = + ( ) ( ) ( ) ( ) 1 1 1 ~ | , , , log exp t t t t t t t t t t t s p s s a Q s a r s a E V s + + + = + logをとっただけ 1p前の式と見比べる 後は定義 厳密推論
) ( ) 1 1 1 , , log exp t t t t t t s t t Q a s r s a E V s + + + + “Soft Max” 右図のように ある値だけ 飛び出すと その値に ≈ Maxへ 通常の価値反復 ( ) ( ) ( ) log exp , t t t t V s Q s a da ( ) ( ) ( ) 1 1 , , t t t t t t s t t Q a s r s a E V s + + + ( ) ( ) max , t t t t t a V s Q s a 今回算出したもの t a t a ここに問題あり(後で解説) 厳密推論
t T p a s すべての時刻において Optimalityが1、かつtでの状態を 与えられたもとでの行動の確率分布➔方策 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: : : : : : : : : : | , | | , , | | | , , / | / | , , , | | t t T t t t t t T t t t T t t T t T t t t t t T t T t t t T t T t t t t t t t t t t T t t t t p a s a s p a s p a s p s p a s p a s p p s p s p p a s p a s s a p a s p s p s s = = = = = = 条件付き確率 ベイズの定理 (同時分布にし てからだと分か りやすい) 何かでてきた!! ( ) ( ) ( ) , | t t t t t t t s a a s s = ※これについては省略して良い (興味ある方は第15回のスライドの The action Priorをみてください) ※ とりあえず計算 O1:t-1はstが与えられたもと で条件付き独立に(右上) (つまり与えても意味がない) Y X Z given 厳密推論
) ( ) , | t t t t t t t s a a s s = ( ) ( ) log t t t t V s s = ( ) ( ) , log , t t t t t t Q s a s a = ( ) ( ) ( ) ( ) | exp , t t t t t t a s Q s a V s = − ( ) ( ) ( ) , | explog t t t t t t t s a a s s = ( ) ( ) ( ) 1 1 , , log exp t t t t t t s t t Q a s r s a E V s + + + ( ) ( ) ( ) log exp , t t t t V s Q s a da に代入 計算を進めていくと… 方策を算出することができた! 方策はsoftな価値関数と softな行動価値関数の差 (アドバンテージ)をexpとったもの! 厳密推論
( ) ( ) ( ) | exp , t t t t t t a s Q s a V s = − ( ) ( ) ( ) 1 1 | exp , t t t t t t a s Q s a V s = − 温度パラメータを入れると… ボルツマン探索に!! (αを小で、greedy!) 厳密推論
t t t t s p s − = ある時刻t-1までのOptimalityが 1とした時の状態の確率分布 ( ) ( ) ( ) ( ) ( ) 1: 1 1 1 1 1 1 1 1: 2 1 1 | | , | , | t t t t t t t t t t t t t t s p s p s s a p a s p s ds da − − − − − − − − − − = = とりあえず計算 st-1とat-1を追加して同時分布にして周辺化して 展開する。さっきから何回も使っている過去の Optimalityと状態stと行動atが条件付き独立なことを使う ( ) 1 1 t t s − − ( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 1 1 1 | , | | , | t t t t t t t t t t p s a p a s p a s p s − − − − − − − − − − = ダイナミクス すべて計算可能! (報酬関数, action prior 報酬関数を行動で積分したもの) 初期は なので、t=1から 順々に計算可能! Y X Z given ( ) ( ) 1 1 1 s p s = 厳密推論
すべてのものを計算できた!!でもこれが分かっても。。。 ( ) ( ) 1: 1 | t t t t s p s − = ( ) 1: | t T p s すべての時刻でのOptimalityが1とした時の状態stの 確率分布(最適軌道がどんな状態分布になるのか?) ( ) ( ) ( ) ( ) ( ) ( ) 1: : 1: 1 1: 1: 1: , | , | t T t T t t t t T T T p s p s p s p s p p − = = ( ) ( ) ( ) ( ) ( ) 1: 1 1: 1 | t t t t t t t t t s p s p s s − − 上を使うとこんなものが計算できる! 同じく、stが与えられたもとでの 条件付き独立を使用 なんかでてきた!!!! これは? 厳密推論
( ) ( ) ( ) 1 1 , , log exp t t t t t t s t t Q a s r s a E V s + + + ( ) ( ) ( ) log exp , t t t t V s Q s a da ここに問題あり(後で解説) ( ) ( ) ( ) ( ) | exp , t t t t t t a s Q s a V s = −
1 1 , , log exp t t t t t t s t t Q a s r s a E V s + + + + 楽観的になってしまっていること もし仮にこの状態遷移が良い状態st+1(高い価値)にいけない可能性が高くても その価値が特大だとこの式は楽観的に価値を捉えてしまう。。。 課題とは。。。 1 t s + ( ) 1 1 t t V s + + この状態への状態遷移確率が低くても この値が大きめに反映されてしまう。 (expがかかるので)
( ) 1: 1 1 1 1 | 1 | , exp , T T T t t t t t t t p p s p s s a r s a + = = = = ( ) ( ) ( ) ( ) 1: 1 1: 1 1: 1: 1 ˆ | 1 | | , , | , T T T t t t T t t T t p p s p s s a p a s + = = = 問題は分かったけど。。。 どうすれば良いの?というかつまりその問題は何を指している? ➔問題を一度整理する。 ( ) ( ) ( ) t t t t t p s s s さっきまでこれを一生懸命backwardとforwardで計算してた。 は、 に省略! : 1 t T = : t T
) ( ) 1: 1 1 1 1 | | , exp , T T T t t t t t t t p p s p s s a r s a + = = = ( ) ( ) ( ) ( ) 1: 1 1: 1 1: 1: 1 ˆ | | | , , | , T T T t t t T t t T t p p s p s s a p a s + = = が近くなるような方策 を算出していた。ことと等しい。 よって、 ( ) ( ) ( ) ( ) 1: 1: 1: | , ˆ arg max | 1 || | 1 t t T KL T T p a s D p p − = = ( ) 1: | , t t T p a s
) 1: 1 1 1 1 | 1 | , exp , T T T t t t t t t t p p s p s s a r s a + = = = = ( ) ( ) ( ) ( ) 1: 1 1: 1 1: 1: 1 ˆ | 1 | | , , | , T T T t t t T t t T t p p s p s s a p a s + = = = ( ) ( ) ( ) ( ) 1: 1: 1: | , ˆ arg max | 1 || | 1 t t T KL T T p a s D p p − = = ( ) ( ) ( ) 1: 1: 1 ˆ | 1 1 0 | , T T t t T t p p p a s = = ( ) ( ) ( ) ( ) 1: 1: 1: | , ˆ arg max | 1 || | 1 t t T KL T T p a s D p p − = = ( ) ( ) ( ) 1: 1 | 1 1 0 exp , T T t t t p p r s a = = ある軌道τが取れるか 取れないかだけ (取れない場合は0、 取れる場合は1)
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: ˆ ~ 1 1 1 ˆ ~ 1 1 1 ˆ ~ 1 ˆ , ~ , ˆ ˆ | 1 || | 1 log log log log | , , log log | , log | , log | , log | t t t t KL T T p T t t t t t t p T t t t t t t T t t t t p t t t t s a p s a D p p E p p p s p s s a r s a E p s p s s a a s E r s a a s E r s a a + = + = = − = = = − + + − = + + = − = − ( ) ( ) ( ) ( ) ( ) ( ) 1 ˆ ˆ , ~ , ~ 1 , | t t t t t t T t t T t t t t s a p s a s p s t s E r s a E H a s = = = + 1p前の式を代入 (ダイナミクスが入って いるのは疑問ですがど うせ消えるので) エントロピーの定義と計算 和の期待値=期待値の和 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ˆ ~ , log | | log | | t t t t t t t t t t t t t t t t t s p s p a s a s da ds p s p a s a s da ds E H a s − = − = 報酬最大化+エントロピー最大化!!! (-KLなので!)
) 1: 1 1: 1 1: 1: 1 ˆ | 1 | | , , | , T T T t t t T t t T t p p s p s s a p a s + = = = PGM的に出てきてしまう項 (ダイナミクスに影響を及ぼす)(本当は及ぼせないのに) ここがさっき言っていた 楽観的になってしまう。。。部分!!! 決定論的な場合、この推論が最大エントロピーであることを示せたが。。。 確率的なダイナミクスの場合。。。 Optimalなもとでの状態遷移 なので若干楽観的になりそうな イメージにはなる (Sergeyも例を使って説明してた) けど、これはPGM的に出てきてしまう項 ( ) 1 1: | , , t t t T p s s a + ( ) 1 | , t t t p s s a + ダイナミクスと恣意的なダイナミクスを打ち消すことができないため KLダイバージェンスの計算ができない(論文の式10) (PGM的に出てきてしまう項)
( ) ( ) 1 1 | , | , , t t t t t t t p s s a p s s a + + ( ) ( ) ( ) 1 1 1 , , log exp t t t t t t s t t Q a s r s a E V s + + + + さてどうするか!?
変分推論!!!! ‐ 限られた確率分布でELBOの最大化をする を近似する という確率分布の中で ダイナミクスの部分を固定するような確率分布から良い確率分布を選ぶ ‐ つまり,Optimalityが1として、状態遷移確率を変化させないという条件で、 行動確率(方策)はなんですか?という問いに答える。 2020/5/23 32 ( ) 1 | , , t t t t p s s a + ( ) 1 | , t t t p s s a + ( ) ˆ p ( ) p 変分推論
( ) 1: 1: 1 1 , | , | T T t t t t t t q q s a p s p s s a q a s + = = としましょう もともとのダイナミクスで固定! ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: 1: 1: 1: 1: 1: 1: 1 1 1 1: , ~ 1 1 1 , ~ 1 , ~ , ~ log log | , log | , log log log | , log | , log | , | T T T T T T T T t t T t t t t t t t T s a q T t t t t t t T t t t t s a q t t t t t s a q s a s q s p s p s s a p s a p E p s p s s a q a s E r s a q a s E r s a E H q a s + = + = = + + − − + = − = + 1 T t= ( ) ( ) ( ) ( ) 1 1 1 | , | , T t t t t t t t p p s p s a p s s a + = = ( ) ( ) ( ) ( ) ~ log log , log Z p Z p X E p X Z q Z − 代入しただけです。 変分推論 一部定義を使って変更
) ( ) ( ) ( ) 1: 1: 1: 1: , ~ , ~ | 1 arg max , | T T T T t t t t T t t t t s a q s a s q s q a s t E r s a E H q a s = + 変分推論 よって下記を最大化 = 報酬最大化+エントロピー最大化!!! するような、 を計算すればよい!! その が理想的な軌道p(τ)を実現する(最も近似する)方策になる。 (確率的なシステムにおいても、最大エントロピー原理を算出できた) 補足:次のように書かれることが多いですが、同じものを最大化していることになると思 います(たぶん)、エントロピーの項にはatは含まれないので。 (期待値とっても値変わらない) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: 1: 1: , ~ , | 1 arg max , | T T T T t t T t t t t s a q s a q a s t E r s a H q a s = + ( ) | t t q a s ( ) | t t q a s
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: 1: 1: 1: 1: 1: 1: , ~ , ~ 1 , ~ , 1 , | , log | T T T T t t T T T T T t t t t s a q s a s q s t T t t t t s a q s a t J E r s a E H q a s E r s a q a s = = = + = − では、先ほどのELBOを最大化する = 報酬最大化+エントロピー最大化!!! する をどのように求めるか? ➔ policy gradientが使えそう ( ) | t t q a s <評価値> <勾配> 応用 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: 1: 1: 1: 1: 1: 1: , ~ , 1 ' ' ' ' , ~ , 1 ' ' ' ' ' , log | log | , log | 1 1 | log | , log | 1 T T T T T T T T T t t t t s a q s a t T T t t t t t t s a q s a t t t t t t t t t t t t J E r s a q a s E q a s r s a q a s q a s q a s r s a q a s N = = = = − = − − − − ' T i t t = ベースラインと同じで 期待値に関係ない 変分推論
➔ Dynamic Programmingが使えそう ( ) | t t q a s Dynamic Programmingをやるときは一番最後の時刻から! つまり、最後の時刻で がどうなるべきかを考える ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ~ ~ | ~ ~ | | argmax , | argmax , log | T T T T T T T T T T T T T T T T s q s a q a s T T T T s q s a q a s q a s E E r s a H q a s E E r s a q a s = + = − ( ) | T T q a s ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: 1: 1: , ~ , ~ | 1 arg max , | T T T T t t t t T t t t t s a q s a s q s q a s t E r s a E H q a s = + Sergeyも言っているが たいていこの形の時は expの形の確率分布になる (微分取って計算!割愛!) maximized when ( ) ( ) ( ) ~ argmax log x q x E r x q x − ( ) ( ) ( ) | exp , T T T T q a s r a s 行動すべてで積分すれば良いので。。。 ( ) ( ) ( ) ( ) ( ) exp , | exp , T T T T T r a s q a s r a s da = 変分推論
) ( ) ( ) ( ) ( ) ( ) exp , | exp , exp , T T T T T T T T r a s q a s r a s da Q s a V s = = − 次の状態はないのでQはただの報酬関数に VはQを行動で積分すれば算出できるので! ( ) ( ) ( ) log exp , T T T T V s Q s a da = よって最終的には、 残りの時刻についても行っていきます。 ( ) ( ) ( ) ( ) | exp , T T T T T q a s Q s a V s = − ( ) ( ) ( ) ( ) ( ) ( ) ( ) ~ ~ | ~ ~ | , log | T T T T T T T T T T T T T T T s q s a q a s s q s a q a s E E r s a q a s E E V s − = ( ) ( ) , , T T T T Q s a r s a = 変分推論 応用 ( ) ( ) ( ) , log | T T T T T V s r s a q a s = −
) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 ~ ~ | ~ | , ~ ~ | ~ ~ | | argmax , | argmax , | argmax , log | t t t t t t t t t t t t t t t t t t t t t t t t t t s q s a q a s s p s s a t t t t s q s a q a s t t t t s q s a q a s q a s E E r s a E V s H q a s E E Q s a H q a s E E Q s a q a s + + + = + + = + = − ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1: 1: 1: 1: , ~ , ~ | 1 arg max , | T T T T t t t t T t t t t s a q s a s q s q a s t E r s a E H q a s = + 1時刻前の評価値が分かったのでそれをもともとの式を 展開したと想像して代入する ( ) ( ) ( ) ( ) ( ) ( ) ( ) ~ ~ | ~ ~ | , log | T T T T T T T T T T T T T T s q s a q a s T s q s a q a s E E r s a q a s E E V s − = ( ) ( ) ( ) ( ) 1 1 1 ~ | , , , t t t t t t t t t s p s s a Q s a r s a E V s + + + = + と書けいつものベルマンバックアップに!! maximized when ( ) ( ) ( ) | exp , t t t t q a s Q a s ( ) ( ) ( ) ( ) | exp , t t t t t q a s Q s a V s = − ( ) ( ) ( ) log exp , t t t t V s Q s a da = 変分推論 応用 ( ) ( ) ( ) ( ) ~ | , log | t t t t t t t t a q a s V s E Q s a q a s = − 代入
1: ( ) ( ) ( ) ( ) 1 1 1 1 ~ | , , , t t t t t t t t t t t s p s s a Q s a r s a E V s + + + + = + ( ) ( ) ( ) log exp , t t t t V s Q s a da = 変分推論 応用 価値反復(通常) 厳密推論での価値反復 (楽観的) ( ) ( ) ( ) 1 1 1 , , log exp t t t t t t s t t Q a s r s a E V s + + + + ( ) ( ) ( ) log exp , t t t t V s Q s a da ( ) ( ) ( ) 1 1 , , t t t t t t s t t Q a s r s a E V s + + + ( ) ( ) max , t t t t t a V s Q s a 変分推論での価値反復 (今回) ( ) ( ) ( ) 1 1 1 , , t t t t t t s t t Q a s r s a E V s + + + + ( ) ( ) ( ) log exp , t t t t V s Q s a da
応用 ( ) ( ) ( ) ( ) ( ) ~ ~ | | argmax , log | t t t t t t t t t t t s q s a q a s q a s E E Q s a q a s = − なので、これの勾配を計算(policy gradientの計算参考) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ~ ~ | | argmax log | , log | t t t t t t t t t t t t t t s q s a q a s q a s E E q a s Q s a q a s b s = − − Qが分かれば方策勾配よりもローバリアンスに学習できるので、 後はQを近似(Vも近似するが,しない場合もある) 詳しくは、Soft Actor Criticの論文を参考に!! Dynamic Programming での式そのまま