η ( π ) = E s 0 , a 0 , … [ ∑ t = 0 ∞ γ t r ( s t ) ] , where s 0 ∼ ρ 0 ( s 0 ) , a t ∼ π ( a t ∣ s t ) , s t + 1 ∼ P ( s t + 1 ∣ s t , a t ) \begin{array}{l}{\eta(\pi)=\mathbb{E}_{s 0, a_{0}, \ldots}\left[\sum_{t=0}^{\infty} \gamma^{t} r\left(s_{t}\right)\right], \text { where }} \\ {s_{0} \sim \rho_{0}\left(s_{0}\right), a_{t} \sim \pi\left(a_{t} | s_{t}\right), s_{t+1} \sim P\left(s_{t+1} | s_{t}, a_{t}\right)}\end{array} η ( π ) = E s 0 , a 0 , … [ ∑ t = 0 ∞ γ t r ( s t ) ] , where s 0 ∼ ρ 0 ( s 0 ) , a t ∼ π ( a t ∣ s t ) , s t + 1 ∼ P ( s t + 1 ∣ s t , a t )
Q π ( s t , a t ) = E s t + 1 , a t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ] V π ( s t ) = E a t , s t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ] A π ( s , a ) = Q π ( s , a ) − V π ( s ) , where a t ∼ π ( a t ∣ s t ) , s t + 1 ∼ P ( s t + 1 ∣ s t , a t ) for t ≥ 0 \begin{array}{l}{Q_{\pi}\left(s_{t}, a_{t}\right)=\mathbb{E}_{s_{t+1}, a_{t+1}, \ldots}\left[\sum_{l=0}^{\infty} \gamma^{l} r\left(s_{t+l}\right)\right]} \\ {V_{\pi}\left(s_{t}\right)=\mathbb{E}_{a_{t}, s_{t+1}, \ldots}\left[\sum_{l=0}^{\infty} \gamma^{l} r\left(s_{t+l}\right)\right]} \\ {A_{\pi}(s, a)=Q_{\pi}(s, a)-V_{\pi}(s), \text { where }} \\ {a_{t} \sim \pi\left(a_{t} | s_{t}\right), s_{t+1} \sim P\left(s_{t+1} | s_{t}, a_{t}\right) \text { for } t \geq 0}\end{array} Q π ( s t , a t ) = E s t + 1 , a t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ] V π ( s t ) = E a t , s t + 1 , … [ ∑ l = 0 ∞ γ l r ( s t + l ) ] A π ( s , a ) = Q π ( s , a ) − V π ( s ) , where a t ∼ π ( a t ∣ s t ) , s t + 1 ∼ P ( s t + 1 ∣ s t , a t ) for t ≥ 0 定义策略 π ~ \tilde{\pi} π ~ π \pi π
η ( π ~ ) = η ( π ) + E s 0 , a 0 , ⋯ ∼ π ~ [ ∑ t = 0 ∞ γ t A π ( s t , a t ) ] \eta(\tilde{\pi})=\eta(\pi)+\mathbb{E}_{s_{0}, a_{0}, \cdots \sim \tilde{\pi}}\left[\sum_{t=0}^{\infty} \gamma^{t} A_{\pi}\left(s_{t}, a_{t}\right)\right] η ( π ~ ) = η ( π ) + E s 0 , a 0 , ⋯ ∼ π ~ [ ∑ t = 0 ∞ γ t A π ( s t , a t ) ]
即动作根据π ~ \tilde{\pi} π ~ π \pi π
令 ρ π ( s ) = P ( s 0 = s ) + γ P ( s 1 = s ) + γ 2 P ( s 2 = s ) + … \rho_{\pi}(s)=P\left(s_{0}=s\right)+\gamma P\left(s_{1}=s\right)+\gamma^{2} P\left(s_{2}=s\right)+\ldots ρ π ( s ) = P ( s 0 = s ) + γ P ( s 1 = s ) + γ 2 P ( s 2 = s ) + …
η ( π ~ ) = η ( π ) + ∑ t = 0 ∑ s P ( s t = s ∣ π ~ ) ∑ a π ~ ( a ∣ s ) γ t A π ( s , a ) = η ( π ) + ∑ s ∑ t = 0 ∞ γ t P ( s t = s ∣ π ~ ) ∑ a π ~ ( a ∣ s ) A π ( s , a ) = η ( π ) + ∑ s ρ π ~ ( s ) ∑ a π ~ ( a ∣ s ) A π ( s , a ) \begin{aligned} \eta(\tilde{\pi}) &=\eta(\pi)+\sum_{t=0} \sum_{s} P\left(s_{t}=s | \tilde{\pi}\right) \sum_{a} \tilde{\pi}(a | s) \gamma^{t} A_{\pi}(s, a) \\ &=\eta(\pi)+\sum_{s} \sum_{t=0}^{\infty} \gamma^{t} P\left(s_{t}=s | \tilde{\pi}\right) \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a) \\ &=\eta(\pi)+\sum_{s} \rho_{\tilde{\pi}}(s) \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a) \end{aligned} η ( π ~ ) = η ( π ) + t = 0 ∑ s ∑ P ( s t = s ∣ π ~ ) a ∑ π ~ ( a ∣ s ) γ t A π ( s , a ) = η ( π ) + s ∑ t = 0 ∑ ∞ γ t P ( s t = s ∣ π ~ ) a ∑ π ~ ( a ∣ s ) A π ( s , a ) = η ( π ) + s ∑ ρ π ~ ( s ) a ∑ π ~ ( a ∣ s ) A π ( s , a ) 这个式子表明只要能保证 ∑ a π ~ ( a ∣ s ) A π ( s , a ) ≥ 0 \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a) \geq 0 ∑ a π ~ ( a ∣ s ) A π ( s , a ) ≥ 0 π ~ ( s ) = arg max a A π ( s , a ) \tilde{\pi}(s)=\arg \max _{a} A_{\pi}(s, a) π ~ ( s ) = arg max a A π ( s , a ) A π A_\pi A π ∑ a π ~ ( a ∣ s ) A π ( s , a ) < 0 \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a)<0 ∑ a π ~ ( a ∣ s ) A π ( s , a ) < 0
L π ( π ~ ) = η ( π ) + ∑ s ρ π ( s ) ∑ a π ~ ( a ∣ s ) A π ( s , a ) L_{\pi}(\tilde{\pi})=\eta(\pi)+\sum_{s} \rho_{\pi}(s) \sum_{a} \tilde{\pi}(a | s) A_{\pi}(s, a) L π ( π ~ ) = η ( π ) + s ∑ ρ π ( s ) a ∑ π ~ ( a ∣ s ) A π ( s , a ) 注意这里使用的是 ρ π ( s ) \rho_{\pi}(s) ρ π ( s ) ρ π ~ ( s ) \rho_{\tilde{\pi}}(s) ρ π ~ ( s )
因为 L π L_{\pi} L π η \eta η
L π θ 0 ( π θ 0 ) = η ( π θ 0 ) ∇ θ L π θ 0 ( π θ ) ∣ θ = θ 0 = ∇ θ η ( π θ ) ∣ θ = θ 0 \begin{aligned} L_{\pi_{\theta_{0}}}\left(\pi_{\theta_{0}}\right) &=\eta\left(\pi_{\theta_{0}}\right) \\ \nabla_{\theta} L_{\pi_{\theta_{0}}}\left.\left(\pi_{\theta}\right)\right|_{\theta=\theta_{0}} &=\nabla_{\theta} \eta\left.\left(\pi_{\theta}\right)\right|_{\theta=\theta_{0}} \end{aligned} L π θ 0 ( π θ 0 ) ∇ θ L π θ 0 ( π θ ) ∣ θ = θ 0 = η ( π θ 0 ) = ∇ θ η ( π θ ) ∣ θ = θ 0 令 π ′ = arg max π ′ L π o l d ( π ′ ) \pi^{\prime}=\arg \max _{\pi^{\prime}} L_{\pi_{\mathrm{old}}}\left(\pi^{\prime}\right) π ′ = arg max π ′ L π old ( π ′ ) π new ( a ∣ s ) = ( 1 − α ) π old ( a ∣ s ) + α π ′ ( a ∣ s ) \pi_{\text { new }}(a | s)=(1-\alpha) \pi_{\text { old }}(a | s)+\alpha \pi^{\prime}(a | s) π new ( a ∣ s ) = ( 1 − α ) π old ( a ∣ s ) + α π ′ ( a ∣ s )
η ( π new ) ≥ L π old ( π new ) − 2 ϵ γ ( 1 − γ ) 2 α 2 w h e r e ϵ = max s ∣ E a ∼ π ′ ( a ∣ s ) [ A π ( s , a ) ] ∣ \eta\left(\pi_{\text { new }}\right) \geq L_{\pi_{\text { old }}}\left(\pi_{\text { new }}\right)-\frac{2 \epsilon \gamma}{(1-\gamma)^{2}} \alpha^{2} \\ where\ \epsilon=\max _{s}\left|\mathbb{E}_{a \sim \pi^{\prime}(a | s)}\left[A_{\pi}(s, a)\right]\right| η ( π new ) ≥ L π old ( π new ) − ( 1 − γ ) 2 2 ϵ γ α 2 w h ere ϵ = max s E a ∼ π ′ ( a ∣ s ) [ A π ( s , a ) ]
我们用total variation divergence作为 α \alpha α
D T V max ( π , π ~ ) = max s D T V ( π ( ⋅ ∣ s ) ∥ π ~ ( ⋅ ∣ s ) ) D_{\mathrm{TV}}^{\max }(\pi, \tilde{\pi})=\max _{s} D_{T V}(\pi(\cdot | s) \| \tilde{\pi}(\cdot | s)) D TV m a x ( π , π ~ ) = max s D T V ( π ( ⋅ ∣ s ) ∥ π ~ ( ⋅ ∣ s ))
注意到其与KL散度的关系 D T V ( p ∥ q ) 2 ≤ D K L ( p ∥ q ) D_{T V}(p \| q)^{2} \leq D_{\mathrm{KL}}(p \| q) D T V ( p ∥ q ) 2 ≤ D KL ( p ∥ q )
证明：令 M i ( π ) = L π i ( π ) − C D K L max ( π i , π ) M_{i}(\pi)=L_{\pi_{i}}(\pi)-C D_{\mathrm{KL}}^{\max }\left(\pi_{i}, \pi\right) M i ( π ) = L π i ( π ) − C D KL m a x ( π i , π )
maximize θ [ L θ old ( θ ) − C D K L max ( θ old , θ ) ] \underset{\theta}{\operatorname{maximize}}\left[L_{\theta_{\text { old }}}(\theta)-C D_{\mathrm{KL}}^{\max }\left(\theta_{\text { old }}, \theta\right)\right] θ maximize [ L θ old ( θ ) − C D KL m a x ( θ old , θ ) ]
maximize L θ old ( θ ) subject to D K L max ( θ old , θ ) ≤ δ \begin{array}{l}{\text { maximize } L_{\theta_{\text { old }}}(\theta)} \\ {\text { subject to } D_{\mathrm{KL}}^{\max }\left(\theta_{\text { old }}, \theta\right) \leq \delta}\end{array} maximize L θ old ( θ ) subject to D KL m a x ( θ old , θ ) ≤ δ
D ‾ K L ρ ( θ 1 , θ 2 ) : = E s ∼ ρ [ D K L ( π θ 1 ( ⋅ ∣ s ) ∥ π θ 2 ( ⋅ ∣ s ) ] \overline{D}_{\mathrm{KL}}^{\rho}\left(\theta_{1}, \theta_{2}\right) :=\mathbb{E}_{s \sim \rho}\left[D_{\mathrm{KL}}\left(\pi_{\theta_{1}}(\cdot | s) \| \pi_{\theta_{2}}(\cdot | s)\right]\right. D KL ρ ( θ 1 , θ 2 ) := E s ∼ ρ [ D KL ( π θ 1 ( ⋅ ∣ s ) ∥ π θ 2 ( ⋅ ∣ s ) ]
maximize L θ old ( θ ) subject to D ‾ K L ρ θ old ( θ old , θ ) ≤ δ \begin{array}{l}{\text { maximize } L_{\theta_{\text { old }}}(\theta)} \\ {\text { subject to } \overline{D}_{\mathrm{KL}}^{\rho \theta_{\text { old }}}\left(\theta_{\text { old }}, \theta\right) \leq \delta}\end{array} maximize L θ old ( θ ) subject to D KL ρ θ old ( θ old , θ ) ≤ δ
本节旨在用蒙特卡洛模拟近似上面的优化问题，展开 L θ old ( θ ) L_{\theta \text { old }}(\theta) L θ old ( θ )
首先用 1 1 − γ E s ∼ ρ θ old [ … ] \frac{1}{1-\gamma} \mathbb{E}_{s \sim \rho_{\theta_{\text { old }}}}[\ldots] 1 − γ 1 E s ∼ ρ θ old [ … ] ∑ S ρ θ old ( s ) [ … ] \sum_{S} \rho_{\theta_{\text { old }}}(s)[\ldots] ∑ S ρ θ old ( s ) [ … ] Q θ old Q_{\theta_{\text { old }}} Q θ old A θ old A_{\theta_{\text { old }}} A θ old
∑ a π θ ( a ∣ s n ) A θ old ( s n , a ) = E a ∼ q [ π θ ( a ∣ s n ) q ( a ∣ s n ) A θ old ( s n , a ) ] \sum_{a} \pi_{\theta}(a | s_{n}) A_{\theta_{\text { old }}}\left(s_{n}, a\right)=\mathbb{E}_{a \sim q}\left[\frac{\pi_{\theta}(a | s_{n})}{q(a | s_{n})} A_{\theta_{\text { old }}}\left(s_{n}, a\right)\right] ∑ a π θ ( a ∣ s n ) A θ old ( s n , a ) = E a ∼ q [ q ( a ∣ s n ) π θ ( a ∣ s n ) A θ old ( s n , a ) ]
maximize [ ∇ θ L θ old ( θ ) ∣ θ = θ old ⋅ ( θ − θ old ) ] subject to 1 2 ( θ old − θ ) T A ( θ old ) ( θ old − θ ) ≤ δ where A ( θ old ) i j = ∂ ∂ θ i ∂ ∂ θ j E s ∼ ρ π [ D K L ( π ( ⋅ ∣ s , θ old ) ∥ π ( ⋅ ∣ s , θ ) ) ] ∣ θ = θ old \begin{array}{l}{\text { maximize }\left[\nabla_{\theta} L_{\theta_{\text { old }}}\left.(\theta)\right|_{\theta=\theta_{\text { old }}} \cdot\left(\theta-\theta_{\text { old }}\right)\right]} \\ {\text { subject to } \frac{1}{2}\left(\theta_{\text { old }}-\theta\right)^{T} A\left(\theta_{\text { old }}\right)\left(\theta_{\text { old }}-\theta\right) \leq \delta} \\ {\text { where } A\left(\theta_{\text { old }}\right)_{i j}=} \\ {\frac{\partial}{\partial \theta_{i}} \frac{\partial}{\partial \theta_{j}} \mathbb{E}_{s \sim \rho_{\pi}}\left.\left[D_{\mathrm{KL}}(\pi(\cdot | s, \theta_{\text { old }}) \| \pi(\cdot | s, \theta))\right]\right|_{\theta=\theta_{\text { old }}}}\end{array} maximize [ ∇ θ L θ old ( θ ) ∣ θ = θ old ⋅ ( θ − θ old ) ] subject to 2 1 ( θ old − θ ) T A ( θ old ) ( θ old − θ ) ≤ δ where A ( θ old ) ij = ∂ θ i ∂ ∂ θ j ∂ E s ∼ ρ π [ D KL ( π ( ⋅ ∣ s , θ old ) ∥ π ( ⋅ ∣ s , θ )) ] ∣ θ = θ old 更新式: θ new = θ old + 1 λ A ( θ old ) − 1 ∇ θ L ( θ ) ∣ θ = θ old \theta_{\text { new }}=\theta_{\text { old }}+\frac{1}{\lambda} A\left(\theta_{\text { old }}\right)^{-1} \nabla_{\theta} L\left.(\theta)\right|_{\theta=\theta_{\text { old }}} θ new = θ old + λ 1 A ( θ old ) − 1 ∇ θ L ( θ ) ∣ θ = θ old
