方策勾配法は 強化学習 アルゴリズム の一種です
方策勾配法は方策最適化法のサブクラスである。方策を導出するために価値関数を学習する価値ベース法とは異なり、方策最適化法は価値関数を参照することなく行動を選択する方策関数 を直接学習する。方策勾配を適用するには、方策関数が微分可能なパラメータによってパラメータ化される必要がある。[ 1 ] π {\displaystyle \pi} π θ {\displaystyle \pi _{\theta }} θ {\displaystyle \theta }
概要 方策ベース強化学習では、アクターはパラメータ化された方策関数であり、 はアクターのパラメータです。アクターは環境の状態を引数として受け取り、確率分布 を生成します π θ {\displaystyle \pi _{\theta }} θ {\displaystyle \theta } 秒 {\displaystyle s} π θ （ ⋅ ∣ 秒 ） {\displaystyle \pi _{\theta }(\cdot \mid s)}
行動空間が離散的であれば、。行動空間が連続的であれば、。 ∑ a π θ （ a ∣ 秒 ） ＝ 1 {\displaystyle \sum _{a}\pi _{\theta }(a\mid s)=1} ∫ a π θ （ a ∣ 秒 ） d a ＝ 1 {\displaystyle \int _{a}\pi _{\theta }(a\mid s)\mathrm {d} a=1}
ポリシー最適化の目標は、期待されるエピソード報酬を最大化する を見つけることです。ここで、 は割引率 、はステップ での報酬、は開始状態、 は時間範囲（無限大になる場合があります）です。 θ {\displaystyle \theta } J （ θ ） {\displaystyle J(\theta)} J （ θ ） ＝ E π θ [ ∑ t ∈ 0 ： T γ t R t | S 0 ＝ 秒 0 ] {\displaystyle J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\gamma^{t}R_{t}{\Big |}S_{0}=s_{0}\right]} γ {\displaystyle \gamma} R t {\displaystyle R_{t}} t {\displaystyle t} 秒 0 {\displaystyle s_{0}} T {\displaystyle T}
方策勾配 は と定義される。方策勾配法はそれぞれ異なる方法で確率的に方策勾配を推定する。いずれの方策勾配法も、勾配上昇 によってを反復的に最大化することを目標とする。方策勾配法の核心部分は方策勾配の確率的推定であるため、「モンテカルロ勾配推定」という名称でも研究されている。[ 2 ] ∇ θ J （ θ ） {\displaystyle \nabla _{\theta }J(\theta )} J （ θ ） {\displaystyle J(\theta)}
REINFORCE
方策勾配 1992年にロナルド・J・ウィリアムズ によって導入されたREINFORCEアルゴリズムは 、最初の方策勾配法でした。[ 3 ] [ 1 ] ∇ θ J （ θ ） ＝ E π θ [ ∑ t ∈ 0 ： T ∇ θ ln π θ （ A t ∣ S t ） ∑ t ∈ 0 ： T （ γ t R t ） | S 0 ＝ 秒 0 ] {\displaystyle \nabla_{\theta}J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{t}\midS_{t})\;\sum_{t\in0:T}(\gamma^{t}R_{t}){\Big |}S_{0}=s_{0}\right]} ∇ θ J （ θ ） ＝ E π θ [ ∑ t ∈ 0 ： T ∇ θ ln π θ （ A t ∣ S t ） ∑ τ ∈ t ： T （ γ τ R τ ） | S 0 ＝ 秒 0 ] {\displaystyle \nabla_{\theta}J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{t}\midS_{t})\sum_{\tau\int:T}(\gamma^{\tau}R_{\tau}){\Big |}S_{0}=s_{0}\right]}
証明
補題の証明 再パラメータ化のトリック を 使う
E π θ [ ∇ θ ln π θ （ A j | S j ） | S i ＝ 秒 i ] ＝ ∑ 秒 P r （ S j ＝ 秒 | S i ＝ 秒 i ） ∑ a π θ （ a | 秒 ） ∇ θ ln π θ （ a | 秒 ） ＝ ∑ 秒 P r （ S j ＝ 秒 | S i ＝ 秒 i ） ∑ a π θ （ a | 秒 ） ∇ θ π θ （ a | 秒 ） π θ （ a | 秒 ） ＝ ∑ 秒 P r （ S j ＝ 秒 | S i ＝ 秒 i ） ∑ a ∇ θ π θ （ a | 秒 ） ＝ ∑ 秒 P r （ S j ＝ 秒 | S i ＝ 秒 i ） ∇ θ ∑ a π θ （ a | 秒 ） {\displaystyle {\begin{aligned}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{i}=s_{i}]&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\pi _{\theta }(a|s)\nabla _{\theta }\ln \pi _{\theta }(a|s)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\pi _{\theta }(a|s){\frac {\nabla _{\theta }\pi _{\theta }(a|s)}{\pi _{\theta }(a|s)}}\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\nabla _{\theta }\pi _{\theta }(a|s)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\nabla _{\theta }\sum _{a}\pi _{\theta }(a|s)\end{aligned}}} π θ ( a | s ) {\displaystyle \pi _{\theta }(a|s)} ∑ a π θ ( a | s ) = 1 {\textstyle \sum _{a}\pi _{\theta }(a|s)=1} E π θ [ ∇ θ ln π θ ( A | S ) ] = ∑ s P r ( S j = s | S i = s i ) ∇ θ ( 1 ) = ∑ s P r ( S j = s | S i = s i ) 0 = 0 {\displaystyle {\begin{aligned}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A|S)]&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\nabla _{\theta }(1)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})0\\&=0\end{aligned}}}
タワー法 と前述の補題 により。
E π θ [ Ψ i ∇ θ ln π θ ( A j | S j ) | S i = s i ] = E π θ [ E π θ [ Ψ i ∇ θ ln π θ ( A j | S j ) | S j ] | S i = s i ] = E π θ [ Ψ i E π θ [ ∇ θ ln π θ ( A j | S j ) | S j ] | S i = s i ] = E π θ [ Ψ i 0 | S i = s i ] = 0 {\displaystyle {\begin{aligned}\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{i}=s_{i}\right]&=\mathbb {E} _{\pi _{\theta }}\left[\mathbb {E} _{\pi _{\theta }}[\Psi _{i}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{j}]{\Big |}S_{i}=s_{i}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{j}]{\Big |}S_{i}=s_{i}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}0{\Big |}S_{i}=s_{i}\right]\\&=0\end{aligned}}}
2つの身元の証明 再パラメータ化トリック を適用すると、
∇ θ J ( θ ) = ∇ θ E π θ [ ∑ i ∈ 0 : T γ i R i | S 0 = s 0 ] = E π θ [ ( ∑ i ∈ 0 : T γ i R i ) ∇ θ ln ( π θ ( A 0 , A 1 , … , A T | S 0 , S 1 , … , S T ) ) | S 0 = s 0 ] = E π θ [ ( ∑ i ∈ 0 : T γ i R i ) ∑ j ∈ 0 : T ∇ θ ln ( π θ ( A j | S j ) ) | S 0 = s 0 ] = E π θ [ ∑ i , j ∈ 0 : T ( γ i R i ) ∇ θ ln π θ ( A j | S j ) | S 0 = s 0 ] {\displaystyle {\begin{aligned}\nabla _{\theta }J(\theta )&=\nabla _{\theta }\mathbb {E} _{\pi _{\theta }}\left[\sum _{i\in 0:T}\gamma ^{i}R_{i}{\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\left(\sum _{i\in 0:T}\gamma ^{i}R_{i}\right)\nabla _{\theta }\ln(\pi _{\theta }(A_{0},A_{1},\dots ,A_{T}|S_{0},S_{1},\dots ,S_{T})){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\left(\sum _{i\in 0:T}\gamma ^{i}R_{i}\right)\sum _{j\in 0:T}\nabla _{\theta }\ln(\pi _{\theta }(A_{j}|S_{j})){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\sum _{i,j\in 0:T}(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]\end{aligned}}}
補題により、任意の に対して となります。これを前の式に代入すると、項の三角形全体がゼロになり、 2番目の方程式が得られます。 E π θ [ ( γ i R i ) ∇ θ ln π θ ( A j | S j ) | S 0 = s 0 ] 0 {\displaystyle \mathbb {E} _{\pi _{\theta }}\left[(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]0} 0 ≤ i < j ≤ T {\textstyle 0\leq i<j\leq T} ∇ θ J ( θ ) = E π θ [ ∑ 0 ≤ j ≤ i ≤ T ( γ i R i ) ∇ θ ln π θ ( A j | S j ) | S 0 = s 0 ] = E π θ [ ∑ j ∈ 0 : T ∇ θ ln π θ ( A j | S j ) ∑ i ∈ j : T ( γ i R i ) | S 0 = s 0 ] {\displaystyle {\begin{aligned}\nabla _{\theta }J(\theta )&=\mathbb {E} _{\pi _{\theta }}\left[\sum _{0\leq j\leq i\leq T}(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\sum _{j\in 0:T}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})\sum _{i\in j:T}(\gamma ^{i}R_{i}){\Big |}S_{0}=s_{0}\right]\end{aligned}}}
したがって、ポリシー勾配の不偏推定値 が得られます。ここで、インデックスは、ポリシーを使用したロールアウト軌道の範囲にわたります。 ∇ θ J ( θ ) ≈ 1 N ∑ n = 1 N [ ∑ t ∈ 0 : T ∇ θ ln π θ ( A t , n ∣ S t , n ) ∑ τ ∈ t : T ( γ τ − t R τ , n ) ] {\displaystyle \nabla _{\theta }J(\theta )\approx {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t\in 0:T}\nabla _{\theta }\ln \pi _{\theta }(A_{t,n}\mid S_{t,n})\sum _{\tau \in t:T}(\gamma ^{\tau -t}R_{\tau ,n})\right]} n {\displaystyle n} N {\displaystyle N} π θ {\displaystyle \pi _{\theta }}
スコア関数は、 状態 における行動の確率を高めるパラメータ空間内の方向として解釈できます。つまり、方策勾配は、あらゆる状態におけるあらゆる行動の確率を高めるためのあらゆる可能な方向の加重平均 ですが、報酬シグナルによって重み付けされます。つまり、特定の状態における特定の行動が高い報酬と関連付けられている場合、その方向は強く強化され、逆もまた同様です。 ∇ θ ln π θ ( A t ∣ S t ) {\displaystyle \nabla _{\theta }\ln \pi _{\theta }(A_{t}\mid S_{t})} A t {\displaystyle A_{t}} S t {\displaystyle S_{t}}
アルゴリズム REINFORCEアルゴリズムはループです
をポリシー関数として使用し、環境内で軌道を展開しますN {\displaystyle N} π θ t {\displaystyle \pi _{\theta _{t}}} ポリシー勾配推定を計算します。g i ← 1 N ∑ n = 1 N [ ∑ t ∈ 0 : T ∇ θ t ln π θ ( A t , n ∣ S t , n ) ∑ τ ∈ t : T ( γ τ R τ , n ) ] {\displaystyle g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t\in 0:T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}\mid S_{t,n})\sum _{\tau \in t:T}(\gamma ^{\tau }R_{\tau ,n})\right]} 勾配上昇法でポリシーを更新します。θ i + 1 ← θ i + α i g i {\displaystyle \theta _{i+1}\leftarrow \theta _{i}+\alpha _{i}g_{i}} ここで、は更新ステップにおける学習率です。 α i {\displaystyle \alpha _{i}} i {\displaystyle i}
分散の縮小 REINFORCEは方策オン アルゴリズムです。つまり、更新に使用する軌道は現在の方策からサンプリングする必要があります。軌道間でリターンが大きく異なる可能性があるため、更新の分散が大きくなる可能性があります。REINFORCE には、分散削減 π θ {\displaystyle \pi _{\theta }} R ( τ ) {\displaystyle R(\tau )}
ベースラインによる強化 分散を減らす一般的な方法は、ベースラインによる強化 アルゴリズムです。これは、任意の関数に対して、次の恒等式に基づいています。これは、前の補題を適用することで証明できます ∇ θ J ( θ ) = E π θ [ ∑ t ∈ 0 : T ∇ θ ln π θ ( A t | S t ) ( ∑ τ ∈ t : T ( γ τ R τ ) − b ( S t ) ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t\in 0:T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\left(\sum _{\tau \in t:T}(\gamma ^{\tau }R_{\tau })-b(S_{t})\right){\Big |}S_{0}=s_{0}\right]} b : States → R {\displaystyle b:{\text{States}}\to \mathbb {R} }
このアルゴリズムは修正勾配推定器を使用し、オリジナルの REINFORCE アルゴリズムは の特殊なケースです。 g i ← 1 N ∑ n = 1 N [ ∑ t ∈ 0 : T ∇ θ t ln π θ ( A t , n | S t , n ) ( ∑ τ ∈ t : T ( γ τ R τ , n ) − b i ( S t , n ) ) ] {\displaystyle g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t\in 0:T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}|S_{t,n})\left(\sum _{\tau \in t:T}(\gamma ^{\tau }R_{\tau ,n})-b_{i}(S_{t,n})\right)\right]} b i ≡ 0 {\displaystyle b_{i}\equiv 0}
アクター・クリティック法 が適切に選択され、となる場合、勾配推定の分散を大幅に減少させる可能性があります。つまり、ベースラインは価値関数 に可能な限り近くなり、理想値に近づく必要があります。ポリシーが更新されると価値関数も更新されるため、ベースラインも更新される必要があることに注意してください。一般的なアプローチの1つは、価値関数を推定する別の関数を学習し、それをベースラインとして使用することです。これはアクター・クリティック法 の1つであり、ポリシー関数がアクター、価値関数がクリティックです b i {\textstyle b_{i}} b i ( S t ) ≈ ∑ τ ∈ t : T ( γ τ R τ ) = γ t V π θ i ( S t ) {\textstyle b_{i}(S_{t})\approx \sum _{\tau \in t:T}(\gamma ^{\tau }R_{\tau })=\gamma ^{t}V^{\pi _{\theta _{i}}}(S_{t})} V π θ i ( S t ) {\displaystyle V^{\pi _{\theta _{i}}}(S_{t})} ∇ θ J ( θ ) = E π θ [ ∑ t ∈ 0 : T ∇ θ ln π θ ( A t | S t ) ( ∑ τ ∈ t : T ( γ τ R τ ) − γ t V π θ ( S t ) ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=\mathbb {E} _{\pi _{\theta }}\left[\sum _{t\in 0:T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\left(\sum _{\tau \in t:T}(\gamma ^{\tau }R_{\tau })-\gamma ^{t}V^{\pi _{\theta }}(S_{t})\right){\Big |}S_{0}=s_{0}\right]} π θ t {\displaystyle \pi _{\theta _{t}}} V π θ i ( S t ) {\displaystyle V^{\pi _{\theta _{i}}}(S_{t})}
Q関数は、 タワー法則を使用した同様の議論 により、批評家としても使用できます。Q π {\displaystyle Q^{\pi }} ∇ θ J ( θ ) = E π θ [ ∑ 0 ≤ t ≤ T γ t ∇ θ ln π θ ( A t | S t ) ⋅ Q π θ ( S t , A t ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\gamma ^{t}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot Q^{\pi _{\theta }}(S_{t},A_{t}){\Big |}S_{0}=s_{0}\right]}
価値関数を基準として差し引くと、アドバンテージ関数 も批評家として使用できることがわかります。まとめると、 には多くの不偏推定値があり、すべて の形式をとります。ここでは次の項の任意の線形和です。 A π ( S , A ) = Q π ( S , A ) − V π ( S ) {\displaystyle A^{\pi }(S,A)=Q^{\pi }(S,A)-V^{\pi }(S)} ∇ θ J ( θ ) = E π θ [ ∑ 0 ≤ t ≤ T γ t ∇ θ ln π θ ( A t | S t ) ⋅ A π θ ( S t , A t ) | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\gamma ^{t}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot A^{\pi _{\theta }}(S_{t},A_{t}){\Big |}S_{0}=s_{0}\right]} ∇ θ J θ {\textstyle \nabla _{\theta }J_{\theta }} ∇ θ J ( θ ) = E π θ [ ∑ 0 ≤ t ≤ T ∇ θ ln π θ ( A t | S t ) ⋅ Ψ t | S 0 = s 0 ] {\displaystyle \nabla _{\theta }J(\theta )=E_{\pi _{\theta }}\left[\sum _{0\leq t\leq T}\nabla _{\theta }\ln \pi _{\theta }(A_{t}|S_{t})\cdot \Psi _{t}{\Big |}S_{0}=s_{0}\right]} Ψ t {\textstyle \Psi _{t}}
∑ 0 ≤ τ ≤ T ( γ τ R τ ) {\textstyle \sum _{0\leq \tau \leq T}(\gamma ^{\tau }R_{\tau })} γ t ∑ t ≤ τ ≤ T ( γ τ − t R τ ) {\textstyle \gamma ^{t}\sum _{t\leq \tau \leq T}(\gamma ^{\tau -t}R_{\tau })} γ t ∑ t ≤ τ ≤ T ( γ τ − t R τ ) − b ( S t ) {\textstyle \gamma ^{t}\sum _{t\leq \tau \leq T}(\gamma ^{\tau -t}R_{\tau })-b(S_{t})} γ t ( R t + γ V π θ ( S t + 1 ) − V π θ ( S t ) ) {\textstyle \gamma ^{t}\left(R_{t}+\gamma V^{\pi _{\theta }}(S_{t+1})-V^{\pi _{\theta }}(S_{t})\right)} γ t Q π θ ( S t , A t ) {\textstyle \gamma ^{t}Q^{\pi _{\theta }}(S_{t},A_{t})} γ t A π θ ( S t , A t ) {\textstyle \gamma ^{t}A^{\pi _{\theta }}(S_{t},A_{t})} 他にも以下のような可能性があり、証明も非常に似ています Ψ t {\textstyle \Psi _{t}}
γ t ( R t + γ R t + 1 + γ 2 V π θ ( S t + 2 ) − V π θ ( S t ) ) {\textstyle \gamma ^{t}\left(R_{t}+\gamma R_{t+1}+\gamma ^{2}V^{\pi _{\theta }}(S_{t+2})-V^{\pi _{\theta }}(S_{t})\right)} γ t ( ∑ k = 0 n − 1 γ k R t + k + γ n V π θ ( S t + n ) − V π θ ( S t ) ) {\textstyle \gamma ^{t}\left(\sum _{k=0}^{n-1}\gamma ^{k}R_{t+k}+\gamma ^{n}V^{\pi _{\theta }}(S_{t+n})-V^{\pi _{\theta }}(S_{t})\right)} γ t ∑ n = 1 ∞ λ n − 1 1 − λ ⋅ ( ∑ k = 0 n − 1 γ k R t + k + γ n V π θ ( S t + n ) − V π θ ( S t ) ) {\textstyle \gamma ^{t}\sum _{n=1}^{\infty }{\frac {\lambda ^{n-1}}{1-\lambda }}\cdot \left(\sum _{k=0}^{n-1}\gamma ^{k}R_{t+k}+\gamma ^{n}V^{\pi _{\theta }}(S_{t+n})-V^{\pi _{\theta }}(S_{t})\right)} : TD(λ)学習、 GAE(一般化利点推定) とも呼ばれる。[ 4 ]
自然政策勾配
自然政策勾配法は、 2001年にシャム・カカデ によって提案された政策勾配法の変形です。[ 5 ] 座標フリーの更新を提供することを目的としています θ {\displaystyle \theta }
動機 標準的な方策勾配更新は、制約付き最適化問題を解きます。 目的関数（線形化改善）は幾何学的に意味がありますが、ユークリッド制約は座標依存性を導入します。これに対処するために、自然な方策勾配は、ユークリッド制約をカルバック・ライブラー・ダイバージェンス （KL）制約に置き換えます。ここで、2つの方策間のKLダイバージェンスは、方策 における状態分布にわたって平均化されます 。つまり、これは更新が可逆なアフィンパラメータ変換に対して不変であることを保証します θ i + 1 = θ i + α ∇ θ J ( θ i ) {\displaystyle \theta _{i+1}=\theta _{i}+\alpha \nabla _{\theta }J(\theta _{i})} { max θ i + 1 J ( θ i ) + ( θ i + 1 − θ i ) T ∇ θ J ( θ i ) ‖ θ i + 1 − θ i ‖ ≤ α ⋅ ‖ ∇ θ J ( θ i ) ‖ {\displaystyle {\begin{cases}\max _{\theta _{i+1}}J(\theta _{i})+(\theta _{i+1}-\theta _{i})^{T}\nabla _{\theta }J(\theta _{i})\\\|\theta _{i+1}-\theta _{i}\|\leq \alpha \cdot \|\nabla _{\theta }J(\theta _{i})\|\end{cases}}} ‖ θ i + 1 − θ i ‖ {\displaystyle \|\theta _{i+1}-\theta _{i}\|} { max θ i + 1 J ( θ i ) + ( θ i + 1 − θ i ) T ∇ θ J ( θ i ) D ¯ K L ( π θ i + 1 ‖ π θ i ) ≤ ϵ {\displaystyle {\begin{cases}\max _{\theta _{i+1}}J(\theta _{i})+(\theta _{i+1}-\theta _{i})^{T}\nabla _{\theta }J(\theta _{i})\\{\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}})\leq \epsilon \end{cases}}} π θ i {\displaystyle \pi _{\theta _{i}}} D ¯ K L ( π θ i + 1 ‖ π θ i ) := E s ∼ π θ i [ D K L ( π θ i + 1 ( ⋅ | s ) ‖ π θ i ( ⋅ | s ) ) ] {\displaystyle {\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}}):=\mathbb {E} _{s\sim \pi _{\theta _{i}}}[D_{KL}(\pi _{\theta _{i+1}}(\cdot |s)\|\pi _{\theta _{i}}(\cdot |s))]}
が小さい場合、KLダイバージェンスはフィッシャー情報計量 で近似されます。ここで、は方策のフィッシャー情報行列 で、次のように定義されます。これにより、問題は二次計画 問題に変換され、自然な方策勾配更新が得られます。ステップ サイズは通常、KL制約を維持するように調整され、 となりますϵ {\displaystyle \epsilon } D ¯ K L ( π θ i + 1 ‖ π θ i ) ≈ 1 2 ( θ i + 1 − θ i ) T F ( θ i ) ( θ i + 1 − θ i ) {\displaystyle {\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}})\approx {\frac {1}{2}}(\theta _{i+1}-\theta _{i})^{T}F(\theta _{i})(\theta _{i+1}-\theta _{i})} F ( θ ) {\displaystyle F(\theta )} F ( θ ) = E s , a ∼ π θ [ ∇ θ ln π θ ( a | s ) ( ∇ θ ln π θ ( a | s ) ) T ] {\displaystyle F(\theta )=\mathbb {E} _{s,a\sim \pi _{\theta }}\left[\nabla _{\theta }\ln \pi _{\theta }(a|s)\left(\nabla _{\theta }\ln \pi _{\theta }(a|s)\right)^{T}\right]} θ i + 1 = θ i + α F ( θ i ) − 1 ∇ θ J ( θ i ) {\displaystyle \theta _{i+1}=\theta _{i}+\alpha F(\theta _{i})^{-1}\nabla _{\theta }J(\theta _{i})} α {\displaystyle \alpha } α ≈ 2 ϵ ( ∇ θ J ( θ i ) ) T F ( θ i ) − 1 ∇ θ J ( θ i ) {\textstyle \alpha \approx {\sqrt {\frac {2\epsilon }{(\nabla _{\theta }J(\theta _{i}))^{T}F(\theta _{i})^{-1}\nabla _{\theta }J(\theta _{i})}}}}
逆行列演算は、特に高次元パラメータ（ニューラルネットワークなど）の場合、計算負荷が高くなります。実用的な実装では、近似値が用いられることが多いです。 F ( θ ) {\displaystyle F(\theta )}
信頼領域ポリシー最適化 （TRPO）は、ポリシー更新に信頼領域 制約を適用することで、自然なポリシー勾配アプローチを拡張したポリシー勾配法です。 [ 6 ]
自然勾配降下法は、目的関数が真の二次関数である場合 、理論的には最適ですが、これはあくまで近似値に過ぎません。TRPOの直線探索法とKL制約は、この近似値が崩れない「信頼領域」内に解を限定しようとします。これにより、TRPOは実用上、より堅牢になります。
自然方策勾配と同様に、TRPOは、座標フリーで指定された制約付き最適化問題を解くことで、方策パラメータを反復的に更新します。ここで θ {\displaystyle \theta } { max θ L ( θ , θ i ) D ¯ K L ( π θ ‖ π θ i ) ≤ ϵ {\displaystyle {\begin{cases}\max _{\theta }L(\theta ,\theta _{i})\\{\bar {D}}_{KL}(\pi _{\theta }\|\pi _{\theta _{i}})\leq \epsilon \end{cases}}}
L ( θ , θ i ) = E s , a ∼ π θ i [ π θ ( a | s ) π θ i ( a | s ) A π θ i ( s , a ) ] {\displaystyle L(\theta ,\theta _{i})=\mathbb {E} _{s,a\sim \pi _{\theta _{i}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{i}}(a|s)}}A^{\pi _{\theta _{i}}}(s,a)\right]} 代替の利点 です。π θ {\displaystyle \pi _{\theta }} π θ i {\displaystyle \pi _{\theta _{i}}} ϵ {\displaystyle \epsilon } 一般に、他の代替的な利点も可能であることに注意してください。ここでは、前述のタイプの任意の線形和です。実際、OpenAIは単純な利点 ではなく、一般化利点推定 を使用することを推奨しています。 L ( θ , θ i ) = E s , a ∼ π θ i [ π θ ( a | s ) π θ i ( a | s ) Ψ π θ i ( s , a ) ] {\displaystyle L(\theta ,\theta _{i})=\mathbb {E} _{s,a\sim \pi _{\theta _{i}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{i}}(a|s)}}\Psi ^{\pi _{\theta _{i}}}(s,a)\right]} Ψ {\displaystyle \Psi } A π θ {\displaystyle A^{\pi _{\theta }}}
代理アドバンテージは、政策勾配 と一致するように設計されています。具体的には、 のとき、はアドバンテージ関数から導出される政策勾配 と等しくなります。 しかし、 のとき、これは必ずしも真ではありません。したがって、これは真の目的関数の「代理」です。 L ( θ , θ t ) {\displaystyle L(\theta ,\theta _{t})} ∇ θ J ( θ ) {\displaystyle \nabla _{\theta }J(\theta )} θ = θ t {\displaystyle \theta =\theta _{t}} ∇ θ L ( θ , θ t ) {\displaystyle \nabla _{\theta }L(\theta ,\theta _{t})} ∇ θ J ( θ ) = E ( s , a ) ∼ π θ [ ∇ θ ln π θ ( a | s ) ⋅ A π θ ( s , a ) ] = ∇ θ L ( θ , θ t ) {\displaystyle \nabla _{\theta }J(\theta )=\mathbb {E} _{(s,a)\sim \pi _{\theta }}\left[\nabla _{\theta }\ln \pi _{\theta }(a|s)\cdot A^{\pi _{\theta }}(s,a)\right]=\nabla _{\theta }L(\theta ,\theta _{t})} θ ≠ θ i {\displaystyle \theta \neq \theta _{i}}
自然なポリシー勾配と同様に、小さなポリシー更新の場合、TRPO は の周りのテイラー展開を使用して代理利点と KL ダイバージェンスを近似します。 ここで、 θ t {\displaystyle \theta _{t}} L ( θ , θ i ) ≈ g T ( θ − θ i ) , D ¯ KL ( π θ ‖ π θ i ) ≈ 1 2 ( θ − θ i ) T H ( θ − θ i ) , {\displaystyle {\begin{aligned}L(\theta ,\theta _{i})&\approx g^{T}(\theta -\theta _{i}),\\{\bar {D}}_{\text{KL}}(\pi _{\theta }\|\pi _{\theta _{i}})&\approx {\frac {1}{2}}(\theta -\theta _{i})^{T}H(\theta -\theta _{i}),\end{aligned}}}
g = ∇ θ L ( θ , θ i ) | θ = θ i {\displaystyle g=\nabla _{\theta }L(\theta ,\theta _{i}){\big |}_{\theta =\theta _{i}}} F = ∇ θ 2 D ¯ KL ( π θ ‖ π θ i ) | θ = θ i {\displaystyle F=\nabla _{\theta }^{2}{\bar {D}}_{\text{KL}}(\pi _{\theta }\|\pi _{\theta _{i}}){\big |}_{\theta =\theta _{i}}} これにより問題は二次最適化に帰着し、自然方策勾配更新が得られる。 ここまでは、これは本質的に自然勾配法と同じである。しかし、TRPOは2つの変更を加えることでこれを改善している。 θ i + 1 = θ i + 2 ϵ g T F − 1 g F − 1 g . {\displaystyle \theta _{i+1}=\theta _{i}+{\sqrt {\frac {2\epsilon }{g^{T}F^{-1}g}}}F^{-1}g.}
明示的な逆行列計算を行わずに、共役勾配法 を使用して反復的に解きます。x {\displaystyle x} F x = g {\displaystyle Fx=g} 信頼領域制約が満たされていることを確認するために、バックトラッキング直線探索法 を用いる。具体的には、ステップサイズをバックトラックすることで、KL制約と方策の改善を保証する。つまり、 KL制約を満たし、かつより高い が得られる解が見つかるまで、以下の各テスト解をテストする。ここで、はバックトラッキング係数である。θ i + 1 = θ i + 2 ϵ x T F x x , θ i + α 2 ϵ x T F x x , θ i + α 2 2 ϵ x T F x x , … {\displaystyle \theta _{i+1}=\theta _{i}+{\sqrt {\frac {2\epsilon }{x^{T}Fx}}}x,\;\theta _{i}+\alpha {\sqrt {\frac {2\epsilon }{x^{T}Fx}}}x,\;\theta _{i}+\alpha ^{2}{\sqrt {\frac {2\epsilon }{x^{T}Fx}}}x,\;\dots } D ¯ K L ( π θ i + 1 ‖ π θ i ) ≤ ϵ {\displaystyle {\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}})\leq \epsilon } L ( θ i + 1 , θ i ) ≥ L ( θ i , θ i ) {\displaystyle L(\theta _{i+1},\theta _{i})\geq L(\theta _{i},\theta _{i})} α ∈ ( 0 , 1 ) {\displaystyle \alpha \in (0,1)}
さらなる改善は近似ポリシー最適化 （PPO）であり、これは計算を回避し、クリップされた確率比を使用した一次近似を介して行われます。[ 7 ] F ( θ ) {\displaystyle F(\theta )} F ( θ ) − 1 {\displaystyle F(\theta )^{-1}}
具体的には、KL ダイバージェンス制約の下で代理利点を最大化するのではなく、制約を代理利点に直接挿入します。そして、PPO は、通常どおり、確率的勾配降下法によって代理利点を最大化します。 max θ L ( θ , θ t ) = E s , a ∼ π θ t [ π θ ( a | s ) π θ t ( a | s ) A π θ t ( s , a ) ] {\displaystyle \max _{\theta }L(\theta ,\theta _{t})=\mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}}A^{\pi _{\theta _{t}}}(s,a)\right]} max θ E s , a ∼ π θ t [ { min ( π θ ( a | s ) π θ t ( a | s ) , 1 + ϵ ) A π θ t ( s , a ) if A π θ t ( s , a ) > 0 max ( π θ ( a | s ) π θ t ( a | s ) , 1 − ϵ ) A π θ t ( s , a ) if A π θ t ( s , a ) < 0 ] {\displaystyle \max _{\theta }\mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[{\begin{cases}\min \left({\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}},1+\epsilon \right)A^{\pi _{\theta _{t}}}(s,a)&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a)>0\\\max \left({\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}},1-\epsilon \right)A^{\pi _{\theta _{t}}}(s,a)&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a)<0\end{cases}}\right]}
言い換えれば、新しい代理アドバンテージ関数の勾配上昇とは、ある状態 において、アドバンテージが正の場合、つまり の場合、勾配は状態 におけるアクション実行の確率を高める方向に向くべきであることを意味します。しかし、が大きく変化して になった場合、勾配はその方向への向きを止めるべきです。 の場合も同様です。このように、PPO はパラメータ更新を過度に強くプッシュすることを避け、ポリシーを過度に変更することを避けます。 s , a {\displaystyle s,a} A π θ t ( s , a ) > 0 {\displaystyle A^{\pi _{\theta _{t}}}(s,a)>0} θ {\displaystyle \theta } a {\displaystyle a} s {\displaystyle s} θ {\displaystyle \theta } π θ ( a | s ) ≥ ( 1 + ϵ ) π θ t ( a | s ) {\displaystyle \pi _{\theta }(a|s)\geq (1+\epsilon )\pi _{\theta _{t}}(a|s)} A π θ t ( s , a ) < 0 {\displaystyle A^{\pi _{\theta _{t}}}(s,a)<0}
より正確に言うと、を に更新するには、同じデータバッチに対して複数の更新ステップが必要です。 を初期化し、代理変数の優位性が安定するまで、勾配降下法（ Adam最適化器 など）を繰り返し適用して更新します。その後、を に代入し、これを繰り返します。 θ t {\displaystyle \theta _{t}} θ t + 1 {\displaystyle \theta _{t+1}} θ = θ t {\displaystyle \theta =\theta _{t}} θ {\displaystyle \theta } θ t + 1 {\displaystyle \theta _{t+1}} θ {\displaystyle \theta }
この内部ループ中、 への最初の更新は境界に達しませんが、が からどんどん離れて更新されるにつれて、最終的に境界に達し始めます。境界に達するたびに、対応する勾配はゼロになるため、PPO はからあまりに離れた更新を回避します。 θ {\displaystyle \theta } 1 − ϵ , 1 + ϵ {\displaystyle 1-\epsilon ,1+\epsilon } θ {\displaystyle \theta } θ t {\displaystyle \theta _{t}} θ {\displaystyle \theta } θ t {\displaystyle \theta _{t}}
これは重要です。なぜなら、代理損失は、エージェントが方策 を実行した場合に状態と行動のペアがどのようなものになるかをサンプリングすると仮定しているからです。しかし、方策勾配は方策に則っていなければなりません。したがって、が変化するにつれて、代理損失はますます方策から 外れていきます。これが、を に近接 させることが不可欠な理由です。 s , a {\displaystyle s,a} π θ t {\displaystyle \pi _{\theta _{t}}} θ {\displaystyle \theta } θ {\displaystyle \theta } θ t {\displaystyle \theta _{t}}
学習済みポリシーがあまり乖離しないような参照ポリシーがある場合、KLダイバージェンスペナルティを追加することができます。ここで、はペナルティの強度を調整します。これは、人間のフィードバックからの強化学習 を用いた推論言語モデルの 学習に使用されています。[ 8 ] fダイバージェンスを参照）。 [ 9 ] π ref {\displaystyle \pi _{\text{ref}}} − β E s , a ∼ π θ t [ log ( π θ ( a | s ) π ref ( a | s ) ) ] {\displaystyle -\beta \mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[\log \left({\frac {\pi _{\theta }(a|s)}{\pi _{\text{ref}}(a|s)}}\right)\right]} β {\displaystyle \beta } − β E s , a ∼ π θ t [ log ( π θ ( a | s ) π ref ( a | s ) ) + π ref ( a | s ) π θ ( a | s ) − 1 ] {\displaystyle -\beta \mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[\log \left({\frac {\pi _{\theta }(a|s)}{\pi _{\text{ref}}(a|s)}}\right)+{\frac {\pi _{\text{ref}}(a|s)}{\pi _{\theta }(a|s)}}-1\right]}
グループ相対方策最適化（GRPO）は、PPOのマイナーバリアントであり、価値関数推定器を省略しています。代わりに、各状態 に対して、方策 から複数の行動をサンプリングし、グループ相対優位性[ 9 ] 標準スコアです。 V {\displaystyle V} s {\displaystyle s} a 1 , … , a G {\displaystyle a_{1},\dots ,a_{G}} π θ t {\displaystyle \pi _{\theta _{t}}} A π θ t ( s , a j ) = r ( s , a j ) − μ σ {\displaystyle A^{\pi _{\theta _{t}}}(s,a_{j})={\frac {r(s,a_{j})-\mu }{\sigma }}} μ , σ {\displaystyle \mu ,\sigma } r ( s , a 1 ) , … , r ( s , a G ) {\displaystyle r(s,a_{1}),\dots ,r(s,a_{G})}
次に、すべてのアクションの平均である PPO 目標を最大化します。直感的に、GRPO の各ポリシー更新ステップにより、ポリシーは各状態に対して、その状態で試行された他のアクションよりも比較的パフォーマンスの優れたアクションで応答する可能性が高くなり、比較的パフォーマンスの低いアクションで応答する可能性が低くなります。 max θ 1 G ∑ i = 1 G E ( s , a 1 , … , a G ) ∼ π θ t [ { min ( π θ ( a i | s ) π θ t ( a i | s ) , 1 + ϵ ) A π θ t ( s , a i ) if A π θ t ( s , a i ) > 0 max ( π θ ( a i | s ) π θ t ( a i | s ) , 1 − ϵ ) A π θ t ( s , a i ) if A π θ t ( s , a i ) < 0 ] {\displaystyle \max _{\theta }{\frac {1}{G}}\sum _{i=1}^{G}\mathbb {E} _{(s,a_{1},\dots ,a_{G})\sim \pi _{\theta _{t}}}\left[{\begin{cases}\min \left({\frac {\pi _{\theta }(a_{i}|s)}{\pi _{\theta _{t}}(a_{i}|s)}},1+\epsilon \right)A^{\pi _{\theta _{t}}}(s,a_{i})&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a_{i})>0\\\max \left({\frac {\pi _{\theta }(a_{i}|s)}{\pi _{\theta _{t}}(a_{i}|s)}},1-\epsilon \right)A^{\pi _{\theta _{t}}}(s,a_{i})&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a_{i})<0\end{cases}}\right]}
これまでと同様に、KLペナルティ項を適用することで、学習済みポリシーが参照ポリシーに近づくように促すことができます。GRPOは、DeepSeek の研究者によって推論言語モデルの 学習という文脈で初めて提案されました。[ 9 ]
TRPO、PPO、自然ポリシー勾配などの方法は共通の考え方を持っています。つまり、ポリシーはポリシー勾配の方向に更新される必要がありますが、更新は安全かつ安定した方法で実行する必要があります。通常は、更新前のポリシーに対して一定の距離で測定されます。
更新安定性に関する同様の概念は、ミラー降下法 のような近似凸最適化手法にも見られます。[ 10 ] ブレグマン ダイバージェンス によって測定された現在の に対する近接ペナルティを伴い、勾配 の方向に反復更新されます。これは、次の式で形式化できます。ここで、 は 連続する反復間の近接性を制御します。これは、勾配降下法の学習率に似ています。 x {\textstyle \mathbf {x} } f {\textstyle f} C {\textstyle {\mathcal {C}}} ∇ f {\textstyle \nabla f} x t {\textstyle \mathbf {x} _{t}} B ω {\textstyle B_{\omega }} x t + 1 ∈ arg min x ∈ C ∇ f ( x t ) T ( x − x t ) + 1 η t B ω ( x , x t ) , {\displaystyle \mathbf {x} _{t+1}\in \arg \min _{\mathbf {x} \in {\mathcal {C}}}\nabla f(\mathbf {x} _{t})^{T}(\mathbf {x} -\mathbf {x} _{t})+{\frac {1}{\eta _{t}}}B_{\omega }(x,x_{t}),} η t {\textstyle \eta _{t}}
これにより、ポリシー更新手順が、基盤となるマルコフ決定プロセス (MDP)の (非凸) 最適化ランドスケープで最適なポリシーを見つけることを目的とした最適化手順として再考されることになります。 ポリシー勾配を使用するこの最適化の観点は、ミラー降下ポリシー最適化 (MDPO) と呼ばれ、[ 11 ] [ 12 ] [ 7 ] π t + 1 ∈ arg max π E s , a ∼ π [ A π t ( s , a ) ] + 1 η t D K L ( π | | π t ) {\displaystyle \pi _{t+1}\in \arg \max _{\pi }\mathbb {E} _{s,a\sim \pi }\left[A^{\pi _{t}}(s,a)\right]+{\frac {1}{\eta _{t}}}D_{KL}(\pi ||\pi _{t})} π θ {\textstyle \pi _{\theta }} max θ L ( θ , θ t ) = E s , a ∼ π θ t [ π θ ( a | s ) π θ t ( a | s ) A π θ t ( s , a ) ] + 1 η t D K L ( π θ | | π θ t ) {\displaystyle \max _{\theta }L(\theta ,\theta _{t})=\mathbb {E} _{s,a\sim \pi _{\theta _{t}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{t}}(a|s)}}A^{\pi _{\theta _{t}}}(s,a)\right]+{\frac {1}{\eta _{t}}}D_{KL}(\pi _{\theta }||\pi _{\theta _{t}})}
参照
参考文献 ^ a b Sutton, Richard S.; McAllester, David; Singh, Satinder; Mansour, Yishay (1999). 「関数近似を用いた強化学習のための方策勾配法」 . Advances in Neural Information Processing Systems . 12. MIT Press ^ Mohamed, Shakir; Rosca, Mihaela; Figurnov, Michael; Mnih, Andriy (2020). 「機械学習におけるモンテカルロ勾配推定」 . Journal of Machine Learning Research . 21 (132): 1– 62. arXiv : 1906.10652 . ISSN 1533-7928 . ^ Williams, Ronald J. (1992年5月). 「コネクショニスト強化学習のための単純な統計的勾配追従アルゴリズム」 . 機械学習 . 8 ( 3–4 ): 229–256 . doi : 10.1007/BF00992696 . ISSN 0885-6125 . ^ Schulman, John; Moritz, Philipp; Levine, Sergey; Jordan, Michael; Abbeel, Pieter (2018-10-20). 「一般化アドバンテージ推定を用いた高次元連続制御」. arXiv : 1506.02438 [ cs.LG ]. ^ Kakade, Sham M (2001). 「自然なポリシー勾配」 . ニューラル情報処理システムの進歩 . 14. MITプレス. ^ Schulman, John; Levine, Sergey; Moritz, Philipp; Jordan, Michael; Abbeel, Pieter (2015-07-06). 「信頼領域ポリシー最適化」 . 第32回国際機械学習会議議事録 . 37. リール、フランス: JMLR.org: 1889– 1897. ^ a b シュルマン, ジョン; ウォルスキー, フィリップ; ダリワル, プラフルラ; ラドフォード, アレック; クリモフ, オレグ (2017-08-28). 「近似ポリシー最適化アルゴリズム」. arXiv : 1707.06347 [ cs.LG ]. ^ Nisan Stiennon、Long Ouyang、Jeffrey Wu、Daniel Ziegler、Ryan Lowe、Chelsea Voss、Alec Radford、Dario Amodei、Paul F. Christiano (2020). 「人間のフィードバックによる要約の学習」 . Advances in Neural Information Processing Systems . 33 . ^ a b c シャオ、ジホン;ワン・ペイイー。朱、チーハオ。徐、潤新。ソン・ジュンシャオ。ビー、シャオ。チャン・ハオウェイ。チャン・ミンチュアン；李、YK (2024-04-27)。 「DeepSeekMath: オープン言語モデルにおける数学的推論の限界を押し上げる」。 arXiv : 2402.03300 [ cs.CL ]。 ^ Arkadi Nemirovsky、David Yudin. 最適化における問題の複雑性と手法の効率性. John Wiley & Sons, 1983. ^ Shani, Lior; Efroni, Yonathan; Mannor, Shie (2020-04-03). 「Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rate for Regularized MDPS」 . AAAI人工知能会議論文集 . 34 (4): 5668– 5675. arXiv : 1909.02769 . doi : 10.1609/aaai.v34i04.6021 . ISSN 2374-3468 . ^ トマール、マナン;シャニ、リオール。エフローニ、ヨナサン。ガヴァムザデ、モハマド（2020-05-20）。 「ミラー降下ポリシーの最適化」。 arXiv : 2005.09814v5 [ cs.LG ]。
外部リンク
![{\displaystyle J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\gamma^{t}R_{t}{\Big |}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d43919181ee7b4159b36b2ecb97e733489c7ffe9)
![{\displaystyle \nabla_{\theta}J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{t}\midS_{t})\;\sum_{t\in0:T}(\gamma^{t}R_{t}){\Big |}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/042b82732df0f7d282c910fb42079d8cca23a346)
![{\displaystyle \nabla_{\theta}J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{t}\midS_{t})\sum_{\tau\int:T}(\gamma^{\tau}R_{\tau}){\Big |}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/923327e3f84c1a0229dd764b029abe2084f7c674)
![{\displaystyle \mathbb {E} _{\pi _{\theta}}[\nabla _{\theta}\ln \pi _{\theta}(A_{j}|S_{j})|S_{i}=s_{i}]=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3be722c40c22dda6a30a4792afa9ed3823ddc9e)
![{\displaystyle \mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})\cdot \Psi _{i}|S_{i}=s_{i}]=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9bf5a18524e3e33ba92f5f4ea110525c7ebf5bea)
![{\displaystyle {\begin{aligned}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{i}=s_{i}]&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\pi _{\theta }(a|s)\nabla _{\theta }\ln \pi _{\theta }(a|s)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\pi _{\theta }(a|s){\frac {\nabla _{\theta }\pi _{\theta }(a|s)}{\pi _{\theta }(a|s)}}\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\sum _{a}\nabla _{\theta }\pi _{\theta }(a|s)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\nabla _{\theta }\sum _{a}\pi _{\theta }(a|s)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf4231a80bcbe256216e048119a8bac08bf9a6e8)
![{\displaystyle {\begin{aligned}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A|S)]&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})\nabla _{\theta }(1)\\&=\sum _{s}Pr(S_{j}=s|S_{i}=s_{i})0\\&=0\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55c3c7089bf58e90703bf2892370792bd041dd73)
![{\displaystyle {\begin{aligned}\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{i}=s_{i}\right]&=\mathbb {E} _{\pi _{\theta }}\left[\mathbb {E} _{\pi _{\theta }}[\Psi _{i}\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{j}]{\Big |}S_{i}=s_{i}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}\mathbb {E} _{\pi _{\theta }}[\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j})|S_{j}]{\Big |}S_{i}=s_{i}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\Psi _{i}0{\Big |}S_{i}=s_{i}\right]\\&=0\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19a42b141e608935932e13520419e1fca555f91b)
![{\displaystyle {\begin{aligned}\nabla _{\theta }J(\theta )&=\nabla _{\theta }\mathbb {E} _{\pi _{\theta }}\left[\sum _{i\in 0:T}\gamma ^{i}R_{i}{\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\left(\sum _{i\in 0:T}\gamma ^{i}R_{i}\right)\nabla _{\theta }\ln(\pi _{\theta }(A_{0},A_{1},\dots ,A_{T}|S_{0},S_{1},\dots ,S_{T})){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\left(\sum _{i\in 0:T}\gamma ^{i}R_{i}\right)\sum _{j\in 0:T}\nabla _{\theta }\ln(\pi _{\theta }(A_{j}|S_{j})){\Big |}S_{0}=s_{0}\right]\\&=\mathbb {E} _{\pi _{\theta }}\left[\sum _{i,j\in 0:T}(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6983054f08e350ae08219f5f5416624cf7711c3a)
![{\displaystyle \mathbb {E} _{\pi _{\theta }}\left[(\gamma ^{i}R_{i})\nabla _{\theta }\ln \pi _{\theta }(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57be0cbbd0769e8abe9cc55dab57aa637ef7000f)
![{\displaystyle {\begin{aligned}\nabla_{\theta}J(\theta)&=\mathbb{E}_{\pi_{\theta}}\left[\sum_{0\leqj\leqi\leqT}(\gamma^{i}R_{i})\nabla_{\theta}\ln\pi_{\theta}(A_{j}|S_{j}){\Big |}S_{0}=s_{0}\right]\\&=\mathbb{E}_{\pi_{\theta}}\left[\sum_{j\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{j}|S_{j})\sum_{i\inj:T}(\gamma ^{i}R_{i}){\Big |}S_{0}=s_{0}\right]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2531ef3c24efd66782585cf23e567ceff8157108)
![{\displaystyle \nabla_{\theta}J(\theta)\approx{\frac{1}{N}}\sum_{n=1}^{N}\left[\sum_{t\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{t,n}\midS_{t,n})\sum_{\tau\int:T}(\gamma^{\tau-t}R_{\tau,n})\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2b9603e455bcb6bef4f2e24f6eca9643eb1cf2f)
![{\displaystyle g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t\in 0:T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}\mid S_{t,n})\sum _{\tau \in t:T}(\gamma ^{\tau }R_{\tau ,n})\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7a89ff0c2ee0c9835313280d9d936d0834262d5)
![{\displaystyle \nabla_{\theta}J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{t}|S_{t})\left(\sum_{\tau\int:T}(\gamma^{\tau}R_{\tau})-b(S_{t})\right){\Big |}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19b0f5a24a23370b54dc13d1b1dcf973a5cd3923)
![{\displaystyle g_{i}\leftarrow {\frac {1}{N}}\sum _{n=1}^{N}\left[\sum _{t\in 0:T}\nabla _{\theta _{t}}\ln \pi _{\theta }(A_{t,n}|S_{t,n})\left(\sum _{\tau \in t:T}(\gamma ^{\tau }R_{\tau ,n})-b_{i}(S_{t,n})\right)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/957a3e9572808dea5ea4d9447b6fbd6302bb1f0a)
![{\displaystyle \nabla_{\theta}J(\theta)=\mathbb{E}_{\pi_{\theta}}\left[\sum_{t\in0:T}\nabla_{\theta}\ln\pi_{\theta}(A_{t}|S_{t})\left(\sum_{\tau\int:T}(\gamma^{\tau}R_{\tau})-\gamma^{t}V^{\pi_{\theta}}(S_{t})\right){\Big |}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19f5143a33b6f22300ee1c31bb78019b437a50ba)
![{\displaystyle \nabla_{\theta}J(\theta)=E_{\pi_{\theta}}\left[\sum_{0\leqt\leqT}\gamma^{t}\nabla_{\theta}\ln\pi_{\theta}(A_{t}|S_{t})\cdotQ^{\pi_{\theta}}(S_{t},A_{t}){\Big|}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6032cb42b6795674db94f27e6616bfcf34032766)
![{\displaystyle \nabla_{\theta}J(\theta)=E_{\pi_{\theta}}\left[\sum_{0\leqt\leqT}\gamma^{t}\nabla_{\theta}\ln\pi_{\theta}(A_{t}|S_{t})\cdotA^{\pi_{\theta}}(S_{t},A_{t}){\Big|}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd24ae4ae4ce9f1c3631c52944dc3a603c9b5594)
![{\displaystyle \nabla_{\theta}J(\theta)=E_{\pi_{\theta}}\left[\sum_{0\leqt\leqT}\nabla_{\theta}\ln\pi_{\theta}(A_{t}|S_{t})\cdot\Psi_{t}{\Big |}S_{0}=s_{0}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24ed7dfdb72518175a7e1c15449756eefb5e570d)
![{\displaystyle {\bar {D}}_{KL}(\pi _{\theta _{i+1}}\|\pi _{\theta _{i}}):=\mathbb {E} _{s\sim \pi _{\theta _{i}}}[D_{KL}(\pi _{\theta _{i+1}}(\cdot |s)\|\pi _{\theta _{i}}(\cdot |s))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a8d49700d8510e99f4e90cc090713b31d7d2bb4)
![{\displaystyle F(\theta)=\mathbb{E}_{s,a\sim\pi_{\theta}}\left[\nabla_{\theta}\ln\pi_{\theta}(a|s)\left(\nabla_{\theta}\ln\pi_{\theta}(a|s)\right)^{T}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49689ac94cc809c70b13f9bb1b78264f96c68488)
![{\displaystyle L(\theta ,\theta _{i})=\mathbb {E} _{s,a\sim \pi _{\theta _{i}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{i}}(a|s)}}A^{\pi _{\theta _{i}}}(s,a)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3858853f94b3b1d81f90ddf337a4a3285f47d5be)
![{\displaystyle L(\theta ,\theta _{i})=\mathbb {E} _{s,a\sim \pi _{\theta _{i}}}\left[{\frac {\pi _{\theta }(a|s)}{\pi _{\theta _{i}}(a|s)}}\Psi ^{\pi _{\theta _{i}}}(s,a)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38a866cac1c24f62044a81772070f67ed2be6b30)
![{\displaystyle \nabla_{\theta}J(\theta)=\mathbb{E}_{(s,a)\sim\pi_{\theta}}\left[\nabla_{\theta}\ln\pi_{\theta}(a|s)\cdotA^{\pi_{\theta}}(s,a)\right]=\nabla_{\theta}L(\theta,\theta_{t})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6d03dd56019cc12603057017690f298ee391875)
![{\displaystyle \max_{\theta}L(\theta,\theta_{t})=\mathbb{E}_{s,a\sim\pi_{\theta_{t}}}\left[{\frac{\pi_{\theta}(a|s)}{\pi_{\theta_{t}}(a|s)}}A^{\pi_{\theta_{t}}}(s,a)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/840486b38d88c5790fe4419cbb1c684d6b6b456b)
![{\displaystyle \max_{\theta}\mathbb{E}_{s,a\sim\pi_{\theta_{t}}}\left[{\begin{cases}\min\left({\frac{\pi_{\theta}(a|s)}{\pi_{\theta_{t}}(a|s)}},1+\epsilon\right)A^{\pi_{\theta_{t}}}(s,a)&{\text{ if}}A^{\pi_{\theta_{t}}}(s,a)>0\\\max\left({\frac{\pi_{\theta}(a|s)}{\pi_{\theta_{t}}(a|s)}},1-\epsilon\right)A^{\pi_{\theta _{t}}}(s,a)&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a)<0\end{cases}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a9943e67f78e3a29b673f7afb394b5447055c1c)
![{\displaystyle -\beta\mathbb{E}_{s,a\sim\pi_{\theta_{t}}}\left[\log\left({\frac{\pi_{\theta}(a|s)}{\pi_{\text{ref}}(a|s)}}\right)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/493e3207e1b865552fd2dd6562c72cc455a73b9e)
![{\displaystyle -\beta \mathbb {E}_{s,a\sim \pi_{\theta_{t}}}\left[\log \left({\frac {\pi_{\theta}(a|s)}{\pi_{\text{ref}}(a|s)}}\right)+{\frac {\pi_{\text{ref}}(a|s)}{\pi_{\theta}(a|s)}}-1\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdcc2cd3addfe23c92ec2f880ddef70262c78828)
![{\displaystyle \max_{\theta}{\frac{1}{G}}\sum_{i=1}^{G}\mathbb{E}_{(s,a_{1},\dots,a_{G})\sim\pi_{\theta_{t}}}\left[{\begin{cases}\min\left({\frac{\pi_{\theta}(a_{i}|s)}{\pi_{\theta_{t}}(a_{i}|s)}},1+\epsilon\right)A^{\pi_{\theta_{t}}}(s,a_{i})&{\text{ if }}A^{\pi_{\theta_{t}}}(s,a_{i})>0\\\max\left({\frac{\pi _{\theta }(a_{i}|s)}{\pi _{\theta _{t}}(a_{i}|s)}},1-\epsilon \right)A^{\pi _{\theta _{t}}}(s,a_{i})&{\text{ if }}A^{\pi _{\theta _{t}}}(s,a_{i})<0\end{cases}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/386222bb2e4c7068c83c86f37c25f1d123666d32)
![{\displaystyle \pi_{t+1}\in \arg \max_{\pi}\mathbb{E}_{s,a\sim\pi}\left[A^{\pi_{t}}(s,a)\right]+{\frac{1}{\eta_{t}}}D_{KL}(\pi ||\pi_{t})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a09f1890332e2dc5057b1e1f5667e0bb84d80d81)
![{\displaystyle \max_{\theta}L(\theta,\theta_{t})=\mathbb{E}_{s,a\sim\pi_{\theta_{t}}}\left[{\frac{\pi_{\theta}(a|s)}{\pi_{\theta_{t}}(a|s)}}A^{\pi_{\theta_{t}}}(s,a)\right]+{\frac{1}{\eta_{t}}}D_{KL}(\pi_{\theta}||\pi_{\theta_{t}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2704a0e8663a745634767db3feca7b1058988e7)
