はじめに MPOとV-MPO Soft Actor Critic と (V-)MPOは兄弟？ MDPと簡単な方策勾配 最適性制御のための推論 方策改善にEMアルゴリズムを使っている V-MPOとMPOの関係は？ 尤度関数が違う 方策評価が違う V-MPOのAdvantage関数の計算 最後に はじめに# 強化学習苦手の会 Advent Calendar 2020 19日目に書いた自分の記事の転載 です。
今回話したいネタが、一年前に読んでもピンと来なかったMaximum a Posteriori Policy Optimization (MPO)とそのOn-Policy版のV-MPOです。私は数学苦手なので、踏み込んだ話よりこれらの論文を読んで「面白いな」と思ったポイントを共有していきたいです。（間違っていれば教えて下さい）
面白いと思った部分が
Soft Actor CriticとMPOが兄弟？ MPOの方策改善にEMアルゴリズムを使っている MPOとV-MPOの関係は？ です。
MPOとV-MPO# Soft Actor Critic と (V-)MPOは兄弟？# Soft Actor CriticとMPOはどちらもControl as Inference から発展したアルゴリズムです。[DL輪読会]Control as Inferenceと発展 がとても参考になるのでぜひ読んでみてください。 Control as Inferenceの前に基礎となるMDPから単純なOn-Policy方策勾配アルゴリズムの変遷について話したいと思います。
MDPと簡単な方策勾配# 一般的なマルコフ決定過程(MDP)は、時刻t t t s t ∈ S \mathbf{s}_{t}\in\mathcal{S} s t ∈ S a t ∈ A \mathbf{a}_{t} \in \mathcal{A} a t ∈ A r t = r ( s t , a t ) {r}_{t} = r(\mathbf{s}_{t} , \mathbf{a}_{t} ) r t = r ( s t , a t ) p ( s t + 1 ∣ s t , a t ) p(\mathbf{s}_{t+1} | \mathbf{s}_{t}, \mathbf{a}_{t}) p ( s t + 1 ∣ s t , a t )
エージェントはパラメトリック方策分布 π θ ( a t ∣ s t ) \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right) π θ ( a t ∣ s t ) τ = ( s 1 , a 1 , … ) \tau=\left(s_{1}, a_{1}, \ldots\right) τ = ( s 1 , a 1 , … )
p ( τ ) = ρ ( s 1 ) ∏ t = 1 T p ( s t + 1 ∣ s t , a t ) π θ ( a t ∣ s t ) (1) p(\tau)=\rho\left(\mathbf{s}_{1}\right) \prod_{t=1}^{T} p\left(\mathbf{s}_{t+1} \mid \mathbf{s}_{t}, \mathbf{a}_{t}\right) \pi_{\theta}\left(\mathbf{a}_{t} \mid \mathbf{s}_{t}\right) \tag{1} p ( τ ) = ρ ( s 1 ) t = 1 ∏ T p ( s t + 1 ∣ s t , a t ) π θ ( a t ∣ s t ) ( 1 ) とします。そして、(語弊がありますが)MDPでの目的はリターン（報酬の総和）を最大化する方策のパラメータベクトルθ \theta θ
θ ⋆ = arg max θ E τ ∼ π θ [ ∑ t = 1 T r ( s t , a t ) ] (1) \theta^{\star}=\arg \max_{\theta} E_{\tau \sim \pi_{\theta}}\left[ \sum_{t=1}^{T}r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)\right] \tag{1} θ ⋆ = arg θ max E τ ∼ π θ [ t = 1 ∑ T r ( s t , a t ) ] ( 1 ) J ( θ ) = E τ ∼ π θ [ ∑ t = 1 T r ( s t , a t ) ] J(\theta) = E_{\tau \sim \pi_{\theta}}\left[ \sum_{t=1}^{T}r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right)\right] J ( θ ) = E τ ∼ π θ [ ∑ t = 1 T r ( s t , a t ) ]
∇ θ J ( θ ) = E τ ∼ π θ [ ∑ t = 1 T r ( s t , a t ) ∇ θ ln π θ ( a t ∣ s t ) ] (3) \nabla_{\theta} J(\theta) = E_{\tau \sim \pi_{\theta}}\left[ \sum_{t=1}^{T}r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right) \nabla_{\theta} \ln \pi_{\theta}(\mathbf{a}_{t} \mid \mathbf{s}_{t}) \right] \tag{3} ∇ θ J ( θ ) = E τ ∼ π θ [ t = 1 ∑ T r ( s t , a t ) ∇ θ ln π θ ( a t ∣ s t ) ] ( 3 ) で、α \alpha α
θ k + 1 = θ k + α ∇ θ J ( π θ k ) (4) \theta_{k+1}=\theta_{k}+\alpha \nabla_{\theta} J\left(\pi_{\theta_{k}}\right) \tag{4} θ k + 1 = θ k + α ∇ θ J ( π θ k ) ( 4 ) と、方策パラメータを更新していきます。 このr ( s t , a t ) r\left(\mathbf{s}_{t}, \mathbf{a}_{t}\right) r ( s t , a t ) General Advantage Estimation )のモチベーションですよね。
最適性制御のための推論# 一般的な強化学習が期待報酬を最大化する軌跡を見つけることに対して、Control as Inferenceでは、軌跡上の事前分布から、タスクが達成や方策が改善したなどの結果を条件付けし、この結果と一致する軌跡の事後分布を推定します。( 1 ) (1) ( 1 ) O t = { 0 , 1 } O_t = \{ 0, 1\} O t = { 0 , 1 } η \eta η
p π ( O = 1 ∣ τ ) ∝ exp ( ∑ t r t η ) (5) p_{\pi}(O=1 \mid \tau) \propto \exp \left(\frac{\sum_{t} r_{t}}{\eta}\right) \tag{5} p π ( O = 1 ∣ τ ) ∝ exp ( η ∑ t r t ) ( 5 ) 一般的な強化学習が( 2 ) (2) ( 2 ) log p ( θ ) \log p(\theta) log p ( θ )
上記の式を語弊を恐れずに以下のように解釈することができます。
面白ポイント ：もともと、一般的な強化学習に最適性変数を加えることによって、ベイズの枠組みで最適制御問題を確率的に推論できるようになりました。SACは、対数周辺尤度の下限に対して、log p ( τ ) \log p(\tau) log p ( τ ) π θ \pi_{\theta} π θ p p p π θ \pi_{\theta} π θ q q q log p θ ( O = 1 ) \log p_\theta(O=1) log p θ ( O = 1 ) q q q π θ ( a ∣ s ) \pi_\theta(a | s) π θ ( a ∣ s )
方策改善にEMアルゴリズムを使っている# 上記した面白ポイントで言及している通り、
そして、変分分布q q q log p θ ( O = 1 ) \log p_\theta(O=1) log p θ ( O = 1 ) q q q π θ ( a ∣ s ) \pi_\theta(a | s) π θ ( a ∣ s )
する手段として
E-step: q q q J ( q , π θ ) \mathcal{J}(q, \pi_\theta) J ( q , π θ ) M-step: π θ \pi_\theta π θ J ( q , π θ ) \mathcal{J}(q, \pi_\theta) J ( q , π θ ) のステップそれぞれを交互に座標上昇してJ \mathcal{J} J
ここで、少し余談（ホントは書きたいがボリューム増えそうで心が折れた話）です。 E-stepでは K L ( q ( a ∣ s t ) ∥ π θ ( a ∣ s t ) ) \mathrm{KL}\left(q(a | s_t) \| \pi_{\theta}(a | s_t) \right) KL ( q ( a ∣ s t ) ∥ π θ ( a ∣ s t ) ) q q q ( 5 ) (5) ( 5 ) η \eta η
max q ∫ μ q ( s ) ∫ q ( a ∣ s ) Q θ i ( s , a ) d a d s s.t. ∫ μ q ( s ) K L ( q ( a ∣ s ) , π ( a ∣ s , θ i ) ) d a < ϵ ∬ μ q ( s ) q ( a ∣ s ) d a d s = 1 (6) \begin{array}{l} \max {q} \int \mu{q}(s) \int q(a \mid s) Q{\theta_{i}}(s, a) d a d s \\\ \text {s.t.} \int \mu_{q}(s) \mathrm{KL}\left(q(a \mid s), \pi\left(a \mid s, \theta_{i}\right)\right) d a<\epsilon \\\ \iint \mu_{q}(s) q(a \mid s) d a d s=1 \end{array} \tag{6} max q ∫ μ q ( s ) ∫ q ( a ∣ s ) Q θ i ( s , a ) d a d s s.t. ∫ μ q ( s ) KL ( q ( a ∣ s ) , π ( a ∣ s , θ i ) ) d a < ϵ ∬ μ q ( s ) q ( a ∣ s ) d a d s = 1 ( 6 ) 上記の制約付き最適化問題から以下のラグランジュ方程式（緩和）を考え、η \eta η
L ( q , η , γ ) = ∫ μ q ( s ) ∫ q ( a ∣ s ) Q θ i ( s , a ) dads+ η ( ϵ − ∫ μ q ( s ) ∫ q ( a ∣ s ) log q ( a ∣ s ) π ( a ∣ s , θ i ) ) + γ ( 1 − ∬ μ q ( s ) q ( a ∣ s ) d a d s ) \begin{aligned} L(q, \eta, \gamma)=& \int \mu_{q}(s) \int q(a \mid s) Q_{\theta_{i}}(s, a) \text { dads+ } \\\ & \eta\left(\epsilon-\int \mu_{q}(s) \int q(a \mid s) \log \frac{q(a \mid s)}{\pi\left(a \mid s, \theta_{i}\right)}\right)+\gamma\left(1-\iint \mu_{q}(s) q(a \mid s) d a d s\right) \end{aligned} L ( q , η , γ ) = ∫ μ q ( s ) ∫ q ( a ∣ s ) Q θ i ( s , a ) dads+ η ( ϵ − ∫ μ q ( s ) ∫ q ( a ∣ s ) log π ( a ∣ s , θ i ) q ( a ∣ s ) ) + γ ( 1 − ∬ μ q ( s ) q ( a ∣ s ) d a d s ) 一年前この論文を読んだとき、ラグランジュ緩和がわからなかった（今もわからん）ので、現在わかってることを話してみます。（ここも怪しいので間違っていたら教えて下さい）
( 6 ) (6) ( 6 ) すべての制約を最大化したい方程式にまとめる。→ラグランジュ緩和 ラグランジュ緩和した方程式の最大値 ≥ \geq ≥ → 良いラグランジュ乗数を見つけたい
ラグランジュ未定乗数法を使う MPOのように双対関数を導いて乗数について最大化を行う このようにして、制約問題を最大化することができます。
私は今までこのような制約問題に対して、TRPOのようなペナルティ法を用いるアルゴリズムは見たことがありますが、双対問題から解くのは見たことがなく、面白ポイントだと思いました。 最適化数学的には、ラグランジュ関数のラグランジュ乗数を双対関数から簡単に見つけづらい→ペナルティ法を使うという論理だと思うので、逆に双対関数を使っているのが面白いんですかね。
V-MPOとMPOの関係は？# 尤度関数が違う# MPOの尤度関数が( 5 ) (5) ( 5 )
p θ old ( I = 1 ∣ τ ) ∝ exp ( ∑ t A π θ old ( s t , a t ) η ) (7) p_{\theta_{\text {old }}}(\mathcal{I}=1 \mid \tau) \propto \exp \left(\frac{\sum_{t} A^{\pi_{\theta \text { old }}(s_t, a_t)}}{\eta}\right) \tag{7} p θ old ( I = 1 ∣ τ ) ∝ exp ( η ∑ t A π θ old ( s t , a t ) ) ( 7 ) としてます。SACやMPOのO t O_t O t I t \mathcal{I}_t I t I = 1 \mathcal{I}=1 I = 1 I = 0 \mathcal{I}=0 I = 0
方策評価が違う# MPOの方策評価に Retraceアルゴリズム(off-policy)
L V ( ϕ ) = min ϕ E μ 0 ( s ) , b ( a ∣ s ) [ ( Q θ i ( s t , a t , ϕ ) − Q t ret ) 2 ] , with Q t ret = Q ϕ ′ ( s t , a t ) + ∑ j = t ∞ γ j − t ( ∏ k = t + 1 j c k ) [ r ( s j , a j ) + E π ( a ∣ s j + 1 ) [ Q ϕ ′ ( s j + 1 , a ) ] − Q ϕ ′ ( s j , a j ) ] c k = min ( 1 , π ( a k ∣ s k ) b ( a k ∣ s k ) ) (8) \begin{align} \mathcal{L}_{V}(\phi)&=\min_{\phi} \mathbb{E}_{\mu_{0}(s), b(a \mid s)}\left[\left(Q_{\theta_{i}}\left(s_{t}, a_{t}, \phi\right)-Q_{t}^{\text {ret }}\right)^{2}\right], \text { with } \\\ Q_{t}^{\text {ret }}&=Q_{\phi^{\prime}}\left(s_{t}, a_{t}\right)+\sum_{j=t}^{\infty} \gamma^{j-t}\left(\prod_{k=t+1}^{j} c_{k}\right)\left[r\left(s_{j}, a_{j}\right)+\mathbb{E}_{\pi\left(a \mid s_{j+1}\right)}\left[Q_{\phi^{\prime}}\left(s_{j+1}, a\right)\right]-Q_{\phi^{\prime}}\left(s_{j}, a_{j}\right)\right] \\\ c_{k}&=\min \left(1, \frac{\pi\left(a_{k} \mid s_{k}\right)}{b\left(a_{k} \mid s_{k}\right)}\right) \end{align} \tag{8} L V ( ϕ ) Q t ret c k = ϕ min E μ 0 ( s ) , b ( a ∣ s ) [ ( Q θ i ( s t , a t , ϕ ) − Q t ret ) 2 ] , with = Q ϕ ′ ( s t , a t ) + j = t ∑ ∞ γ j − t ( k = t + 1 ∏ j c k ) [ r ( s j , a j ) + E π ( a ∣ s j + 1 ) [ Q ϕ ′ ( s j + 1 , a ) ] − Q ϕ ′ ( s j , a j ) ] = min ( 1 , b ( a k ∣ s k ) π ( a k ∣ s k ) ) ( 8 ) を使っているのに対して、V-MPOの方策評価に n n n
L V ( ϕ ) = 1 2 ∣ D ∣ ∑ s t ∼ D ( V ϕ π ( s t ) − G t ( n ) ) 2 (9) \mathcal{L}_{V}(\phi)=\frac{1}{2|\mathcal{D}|} \sum{s_{t} \sim \mathcal{D}}\left(V_{\phi}^{\pi}\left(s_{t}\right)-G_{t}^{(n)}\right)^{2} \tag{9} L V ( ϕ ) = 2∣ D ∣ 1 ∑ s t ∼ D ( V ϕ π ( s t ) − G t ( n ) ) 2 ( 9 ) を使っているのが、MPO(off-policy)とV-MPO(on-policy)の違いです。
V-MPOのAdvantage関数の計算# V-MPOでは軌跡のサンプルのうち、advantage関数の値が高い50%をE-Stepのバッチに用いることによって、大幅に学習が改善されたそうです。この考え方は共分散行列適応進化戦略(CMA-ES)のテクニックに似ているそうです。 数学的にこのようなことをして良いと言えるのかまだよくわかりません…
最後に# MPO、V-MPOは今までのような強化学習の方策改善とは違いEMスタイルを用いている点が面白いですよね。その土壌としてControl as Inferenceという変分ベイズが背景にあるので、ベイズの恩恵が受けられそうで、これからの強化学習の発展が楽しみです。 本当は、実装してみたり、式変形をもっと丁寧に書いたり、理解が歯抜けになっている部分をきちんと埋めてからこの記事を書きたかったですが、時間がなかったり、アカデミックじゃない個人でこのような論文を精読するにはなかなか骨が折れます…。せっかく強化学習苦手の会があるので、積極的に参加して話し合っていきたいです。
前回のアドベントカレンダQ-learningの収束性について 書いたの2年前か… :thinking_face: 時間がすぎるの速いですね
もうすぐ一年が終わりますが、皆さん来年もよろしくお願いします。
