Trust Region Policy Optimization

Schulman et al, 2015. motivation ,ICML

Introduction

1. policy iteration
2. policy gradient
3. derivative-free（例如CEM、CMA，特点是在简单的问题上解决有效，因为计算复杂度

Motivation

希望每次迭代参数能保证提升效果,所以后面采样置信域的方法优化

Method

基础概述

在MDP问题中，这里先形式化一些概念，为了引导出后面奖励函数单调递增的证明及最终目标函数的形式。

理解：定义以s0为初始状态，s0根据环境ρ(s)得到，遵循π策略所获得奖励的期望。（当然也可以有其他定义方式）

理解：在π随机策略下且这里标记处t时刻，Q函数表示s在t时刻的执行a动作，即（st,at）所能得奖励的期望，V函数表示s在t时刻所能得到奖励的期望。注意这里将t时间联系在一起。A函数表示在s状态下执行a动作相对其他动作的优势/劣势。

证明上式成立：

其中两个点

1. ∑ t = 0 ∞ ( γ t + 1 V π ( s t + 1 ) − γ t V π ( s t ) ) = γ V π ( s 1 ) − V π ( s 0 ) + γ 2 V π ( s 2 ) − γ V π ( s 1 ) + ⋯ = − V π ( s 0 ) \begin{aligned} & \sum_{t=0}^{\infty}\left(\gamma ^{t+1}V_{\pi}\left(s_{t+1}\right)-\gamma ^tV_{\pi}\left(s_{t}\right)\right) \\ =& \gamma V_{\pi}\left(s_{1}\right)-V_\pi(s_0)+ \gamma^2 V_{\pi}\left(s_{2}\right)- \gamma V_{\pi}\left(s_{1}\right)+\cdots \\=&-V_{\pi}\left(s_{0}\right) \end{aligned} ==​t=0∑∞​(γt+1Vπ​(st+1​)−γtVπ​(st​))γVπ​(s1​)−Vπ​(s0​)+γ2Vπ​(s2​)−γVπ​(s1​)+⋯−Vπ​(s0​)​

2. E s 0 [ V π ( s 0 ) ] = E s 0 [ E a 0 , s 1 , … [ ∑ l = 0 ∞ γ l r ( s 0 + l ) ] ] = E s 0 , a 0 , … [ ∑ l = 0 ∞ γ l r ( s l ) ] = η ( π ) \begin{aligned} \mathbb{E}_{s_{0}}\left[V_{\pi}\left(s_{0}\right)\right] &=\mathbb{E}_{s_{0}}\left[\mathbb{E}_{a_{0}, s_{1}, \ldots}\left[\sum_{l=0}^{\infty} \gamma^{l} r\left(s_{0+l}\right)\right]\right] \\ &=\mathbb{E}_{s_{0}, a_{0}, \ldots}\left[\sum_{l=0}^{\infty} \gamma^{l} r\left(s_{l}\right)\right] \\ &=\eta(\pi) \end{aligned} Es0​​[Vπ​(s0​)]​=Es0​​[Ea0​,s1​,…​[l=0∑∞​γlr(s0+l​)]]=Es0​,a0​,…​[l=0∑∞​γlr(sl​)]=η(π)​

既然能将更新后的η(˜π)写成η(˜π) = η(π) + B的形式，那么只要保证B的值总大于0，则能保证每一次更新都能增加获得的奖励。

为了简化表达形式，将E期望里的action和state展开：

同时定 义ρπ(s)为折扣访问频率：

理解：为了消去关于t的积分，表示在新策略˜π下，s在不同时刻出现的频率。但是这个是新策略的期望，在实际总很难计算得到所以希望采用过去的策略π近似计算ρπ(s)，所以得到目标函数L(π)，追求目标函数越大越好

而且可以证明L η \eta η的关系， π θ 0 ( a ∣ s ) \pi_{\theta_{0}}(a|s) πθ0​​(a∣s)为旧策略

并可以以此迭代更新。

证明：
L π θ 0 ( π θ 0 ) = η ( π θ 0 ) + ∑ s ρ π θ 0 ( s ) ∑ a π θ 0 ( a ∣ s ) A π θ 0 ( s , a ) η ( π θ 0 ) = η ( π θ 0 ) + ∑ s ρ π θ 0 ( s ) ∑ a π θ 0 ( a ∣ s ) A π θ 0 ( s , a ) \begin{aligned} &L_{\pi_{\theta_{0}}}\left(\pi_{\theta_0}\right)=\eta\left(\pi_{\theta_{0}}\right)+\sum_{s} \rho_{\pi_{\theta_{0}}}(s) \sum_{a} \pi_{\theta_0}(a \mid s) A_{\pi_{\theta_{0}}}(s, a) \\ &\eta\left(\pi_{\theta_0}\right)=\eta\left(\pi_{\theta_{0}}\right)+\sum_{s} \rho_{\pi_{\theta_0}}(s) \sum_{a} \pi_{\theta_0}(a \mid s) A_{\pi_{\theta_{0}}}(s, a) \end{aligned} ​Lπθ0​​​(πθ0​​)=η(πθ0​​)+s∑​ρπθ0​​​(s)a∑​πθ0​​(a∣s)Aπθ0​​​(s,a)η(πθ0​​)=η(πθ0​​)+s∑​ρπθ0​​​(s)a∑​πθ0​​(a∣s)Aπθ0​​​(s,a)​

证明梯度相等：
L π θ 0 ( π θ ) = η ( π θ 0 ) + ∑ s ρ π θ 0 ( s ) ∑ a π θ ( a ∣ s ) A π θ 0 ( s , a ) η ( π θ ) = η ( π θ 0 ) + ∑ s ρ π θ ( s ) ∑ a π θ ( a ∣ s ) A π θ 0 ( s , a ) \begin{aligned} &L_{\pi_{\theta_{0}}}\left(\pi_{\theta}\right)=\eta\left(\pi_{\theta_{0}}\right)+\sum_{s} \rho_{\pi_{\theta_{0}}}(s) \sum_{a} \pi_{\theta}(a \mid s) A_{\pi_{\theta_{0}}}(s, a) \\ &\eta\left(\pi_{\theta}\right)=\eta\left(\pi_{\theta_{0}}\right)+\sum_{s} \rho_{\pi_{\theta}}(s) \sum_{a} \pi_{\theta}(a \mid s) A_{\pi_{\theta_{0}}}(s, a) \end{aligned} ​Lπθ0​​​(πθ​)=η(πθ0​​)+s∑​ρπθ0​​​(s)a∑​πθ​(a∣s)Aπθ0​​​(s,a)η(πθ​)=η(πθ0​​)+s∑​ρπθ​​(s)a∑​πθ​(a∣s)Aπθ0​​​(s,a)​

∇ θ L π θ 0 ( π θ ) = ∑ s ρ π θ 0 ( s ) ∑ a ∇ θ π θ ( a ∣ s ) A π θ 0 ( s , a ) ∇ θ η ( π θ ) = ∑ s ρ π θ ( s ) ∑ a π θ ( a ∣ s ) A π θ 0 ( s , a ) = ∑ s ( ∇ θ ρ π θ ( s ) ∑ a π θ ( a ∣ s ) A π θ 0 ( s , a ) + ρ π θ ( s ) ∑ a ∇ θ π θ ( a ∣ s ) A π θ 0 ( s , a ) ) \begin{aligned} &\nabla_{\theta} L_{\pi_{\theta_{0}}}\left(\pi_{\theta}\right)=\sum_{s} \rho_{\pi_{\theta_{0}}}(s) \sum_{a} \nabla_{\theta} \pi_{\theta}(a \mid s) A_{\pi_{\theta_{0}}}(s, a) \\ &\nabla_{\theta} \eta\left(\pi_{\theta}\right)=\sum_{s} \rho_{\pi_{\theta}}(s) \sum_{a} \pi_{\theta}(a \mid s) A_{\pi_{\theta_{0}}}(s, a) \\ &=\sum_{s}\left(\nabla_{\theta} \rho_{\pi_{\theta}}(s) \sum_{a} \pi_{\theta}(a \mid s) A_{\pi_{\theta_{0}}}(s, a)+\rho_{\pi_{\theta}}(s) \sum_{a} \nabla_{\theta} \pi_{\theta}(a \mid s) A_{\pi_{\theta_{0}}}(s, a)\right) \end{aligned} ​∇θ​Lπθ0​​​(πθ​)=s∑​ρπθ0​​​(s)a∑​∇θ​πθ​(a∣s)Aπθ0​​​(s,a)∇θ​η(πθ​)=s∑​ρπθ​​(s)a∑​πθ​(a∣s)Aπθ0​​​(s,a)=s∑​(∇θ​ρπθ​​(s)a∑​πθ​(a∣s)Aπθ0​​​(s,a)+ρπθ​​(s)a∑​∇θ​πθ​(a∣s)Aπθ0​​​(s,a))​

并且当 θ = θ 0 \theta=\theta_0 θ=θ0​时， ∑ a π θ 0 ( a ∣ s ) A π θ 0 ( s , a ) = 0 \sum_{a} \pi_{\theta_{0}}(a \mid s) A_{\pi_{\theta_{0}}}(s, a)=0 a∑​πθ0​​(a∣s)Aπθ0​​​(s,a)=0,所以上面的等式成立。

但是问题是step-size确定为多大合适呢？因为在该式中并没有评估两次策略的差距到底有多大。就有人提出conservative policy iteration的方法。

核心思想：π‘定义为根据πold即L函数近似出来的结果。增加α系数，混合近似的新策略π‘和旧策略πold。能够证明出η(πnew)大于一个值明确的下界，那么不断提高这个下界就可以不断更新得到更好的η(πnew)。该混合策略的方法在实际应用中应用很少。

推广到随机策略

为了推广到一般随机策略，使用Total variation divergence取代α（TV能定义两个概率分布的差异性），并将ε也做替换：

证明思路：

（1）证明：
∣ A ˉ ( s ) ∣ ≤ α ⋅ 2 max ⁡ s , a ∣ A π ( s , a ) ∣ |\bar{A}(s)| \leq \alpha \cdot 2 \max _{s, a}\left|A_{\pi}(s, a)\right| ∣Aˉ(s)∣≤α⋅2s,amax​∣Aπ​(s,a)∣
（2）证明：
∣ E s t ∼ π ~ [ A ˉ ( s t ) ] − E s t ∼ π [ A ˉ ( s t ) ] ∣ ≤ 2 α max ⁡ s A ˉ ( s ) ≤ 4 α ( 1 − ( 1 − α ) t ) max ⁡ s ∣ A π ( s , a ) ∣ \left|\mathbb{E}_{s_{t} \sim \tilde{\pi}}\left[\bar{A}\left(s_{t}\right)\right]-\mathbb{E}_{s_{t} \sim \pi}\left[\bar{A}\left(s_{t}\right)\right]\right| \leq 2 \alpha \max _{s} \bar{A}(s) \leq 4 \alpha\left(1-(1-\alpha)^{t}\right) \max _{s}\left|A_{\pi}(s, a)\right| ∣∣​Est​∼π~​[Aˉ(st​)]−Est​∼π​[Aˉ(st​)]∣∣​≤2αsmax​Aˉ(s)≤4α(1−(1−α)t)smax​∣Aπ​(s,a)∣
证明如下：

（1）中已知

定义α-couple， P ( a ≠ a ~ ∣ s ) ≤ α P(a \neq \tilde{a} \mid s) \leq \alpha P(a​=a~∣s)≤α, α表达的是差异度
E a ∼ π [ A π ( s , a ) ] = 0 \mathbb{E}_{a \sim \pi}\left[A_{\pi}(s, a)\right]=0 Ea∼π​[Aπ​(s,a)]=0

A ˉ ( s ) = E a ~ ∼ π ~ [ A π ( s , a ~ ) ] = E ( a , a ~ ) ∼ ( π , π ~ ) [ A π ( s , a ~ ) − A π ( s , a ) ] = P ( a ≠ a ~ ∣ s ) E ( a , a ~ ) ∼ ( π , π ~ ) ∣ a ≠ a ~ [ A π ( s , a ~ ) − A π ( s , a ) ] \begin{aligned} \bar{A}(s) &=\mathbb{E}_{\tilde{a} \sim \tilde{\pi}}\left[A_{\pi}(s, \tilde{a})\right] \\ &=\mathbb{E}_{(a, \tilde{a}) \sim(\pi, \tilde{\pi})}\left[A_{\pi}(s, \tilde{a})-A_{\pi}(s, a)\right] \\ &=P(a \neq \tilde{a} \mid s) \mathbb{E}_{(a, \tilde{a}) \sim(\pi, \tilde{\pi}) \mid a \neq \tilde{a}}\left[A_{\pi}(s, \tilde{a})-A_{\pi}(s, a)\right] \end{aligned} Aˉ(s)​=Ea~∼π~​[Aπ​(s,a~)]=E(a,a~)∼(π,π~)​[Aπ​(s,a~)−Aπ​(s,a)]=P(a​=a~∣s)E(a,a~)∼(π,π~)∣a​=a~​[Aπ​(s,a~)−Aπ​(s,a)]​

由绝对值不等式：
∣ A π ( s , a ~ ) − A π ( s , a ) ∣ ≤ ∣ A π ( s , a ~ ) ∣ + ∣ A π ( s , a ) ∣ ≤ 2 m a x ∣ A π ( s , a ) ∣ |A_{\pi}(s, \tilde{a})-A_{\pi}(s, a)|\leq|A_{\pi}(s, \tilde{a})|+|A_{\pi}(s, a)|\leq2max|A_{\pi}(s, a)| ∣Aπ​(s,a~)−Aπ​(s,a)∣≤∣Aπ​(s,a~)∣+∣Aπ​(s,a)∣≤2max∣Aπ​(s,a)∣
所以有
∣ A ˉ ( s ) ∣ ≤ α ⋅ 2 max ⁡ s , a ∣ A π ( s , a ) ∣ |\bar{A}(s)| \leq \alpha \cdot 2 \max _{s, a}\left|A_{\pi}(s, a)\right| ∣Aˉ(s)∣≤α⋅2s,amax​∣Aπ​(s,a)∣
（2）中首先假设 n t n_t nt​为i<t时满足 a i ≠ a ~ i a_{i} \neq \tilde{a}_{i} ai​​=a~i​的个数，

∣ η ( π ~ ) − L π ( π ~ ) ∣ = ∑ t = 0 ∞ γ t ∣ E τ ∼ π ~ [ A ˉ ( s t ) ] − E τ ∼ π [ A ˉ ( s t ) ] ∣ ≤ ∑ t = 0 ∞ γ t ⋅ 4 α ( 1 − ( 1 − α ) t ) ⋅ max ⁡ s , a ∣ A π ( s , a ) ∣ = 4 ϵ α ( 1 1 − γ − 1 1 − γ ( 1 − α ) ) ⋅ max ⁡ s , a ∣ A π ( s , a ) ∣ = 4 α 2 γ ϵ ( 1 − γ ) ( 1 − γ ( 1 − α ) ) ⋅ max ⁡ s , a ∣ A π ( s , a ) ∣ ≤ 4 α 2 γ ϵ ( 1 − γ ) 2 ( 设 ϵ = max ⁡ s , a ∣ A π ( s , a ) ∣ ) \begin{aligned} \left|\eta(\tilde{\pi})-L_{\pi}(\tilde{\pi})\right| &=\sum_{t=0}^{\infty} \gamma^{t}\left|\mathbb{E}_{\tau \sim \tilde{\pi}}\left[\bar{A}\left(s_{t}\right)\right]-\mathbb{E}_{\tau \sim \pi}\left[\bar{A}\left(s_{t}\right)\right]\right| \\ & \leq \sum_{t=0}^{\infty} \gamma^{t} \cdot 4 \alpha\left(1-(1-\alpha)^{t}\right) \cdot \max _{s, a}\left|A_{\pi}(s, a)\right|\\ &=4 \epsilon \alpha\left(\frac{1}{1-\gamma}-\frac{1}{1-\gamma(1-\alpha)}\right)\cdot \max _{s, a}\left|A_{\pi}(s, a)\right| \\ &=\frac{4 \alpha^{2} \gamma \epsilon}{(1-\gamma)(1-\gamma(1-\alpha))}\cdot \max _{s, a}\left|A_{\pi}(s, a)\right| \\ & \leq \frac{4 \alpha^{2} \gamma \epsilon}{(1-\gamma)^{2}} (设\epsilon=\max _{s, a}\left|A_{\pi}(s, a)\right|) \end{aligned} ∣η(π~)−Lπ​(π~)∣​=t=0∑∞​γt∣∣​Eτ∼π~​[Aˉ(st​)]−Eτ∼π​[Aˉ(st​)]∣∣​≤t=0∑∞​γt⋅4α(1−(1−α)t)⋅s,amax​∣Aπ​(s,a)∣=4ϵα(1−γ1​−1−γ(1−α)1​)⋅s,amax​∣Aπ​(s,a)∣=(1−γ)(1−γ(1−α))4α2γϵ​⋅s,amax​∣Aπ​(s,a)∣≤(1−γ)24α2γϵ​(设ϵ=s,amax​∣Aπ​(s,a)∣)​
使用KL散度度量两个分布之间的差距，因为 D T V ( p ∣ ∣ q ) 2 ≤ D K L ( p ∣ ∣ q ) D_{TV}(p||q)^2\leq D_{KL}(p||q) DTV​(p∣∣q)2≤DKL​(p∣∣q),施加了一个强约束。引入KL散度为了使用MC方法和conjugate gradient方法。

其中C为惩罚因子= 2 ϵ γ ( 1 − γ ) 2 \frac{2\epsilon\gamma}{(1-\gamma)^2} (1−γ)22ϵγ​，也可以证明策略更新的过程是一个单调并不断变好的过程。

所以通过不断优化 M i ( π ) M_i(\pi) Mi​(π)可以保证 η ( π ) \eta(\pi) η(π)是非递减的。

Trust Region Policy Optimization

在实际中，C总是特别小，导致step-size太小，所以本文提出给KL散度由惩罚项变成约束项（trust region constraint）来获得更大的step-size,而不是使用C惩罚因子的方式。

D K L m a x D_{KL}^{max} DKLmax​定义是两策略中所有state最大的Dtv,理论上需要对每一个state施加约束确定边界这太复杂了，所以考虑使用平均KL散度代替各个状态下的KL散度，权重为 ρ ( θ o l d ) \rho(\theta_{old}) ρ(θold​)会更加健壮。

基于MC的方式表达形式：

将上式的 ∑ s ρ o l d ( s ) [ . . . ] \sum_s\rho_{old}(s)[...] ∑s​ρold​(s)[...]替换成期望的形式，用 Q θ o l d Q_{\theta_{old}} Qθold​​替换 A θ o l d A_{\theta_{old}} Aθold​​。用重要性采样动作分布q(a|s)采样动作，并可以适用于on-policy，并发现用旧策略表示q(a|s)分布代替在连续问题上表现更好。采用 π o l d \pi_{old} πold​采样状态。

介绍两种采样估计的方法single path和vine。

single path

​ 主要应用在policy gradient，基于 π o l d ( a ∣ s ) \pi_{old}(a|s) πold​(a∣s)每次采样一条完整的轨迹，得到关于s,a,s,a…的序列，并采用 π o l d ( a ∣ s ) \pi_{old}(a|s) πold​(a∣s)作为q(a|s)分布去采样。

vine

​ 主要用在policy iteraiton，vine方法首先通过生成多个on-policy的轨迹来确定一个状态集合s1,s2…sn 。对于状态集合的每一个状态sn采样K个动作，服从 a n , k ∼ q ( ⋅ ∣ s n ) a_{n,k} \sim q(\cdot|s_n) an,k​∼q(⋅∣sn​)。对每一个 ( s n , a n , k ) (s_n,a_{n,k}) (sn​,an,k​)再去生成一次rollout来估计 Q ^ θ i ( s n , a n , k ) \hat{Q}_{\theta_{i}}(s_{n}, a_{n, k}) Q^​θi​​(sn​,an,k​)。实验证明，在连续动作空间问题中， 直接使用on-policy可以取得不错效果，在离散空间问题中，使用uniform分布效果更好。

Practical Algorithm

为求解目标：

TRPO大致分为三步：

1. 使用single path或vine收集一组状态动作对以及它们的Q值的MC估计

2. 通过对样本进行平均，构造方程中估计的目标和约束

3. 近似解决这个约束优化问题来更新策略的参数向量θ。我们使用conjugate gradient算法计算梯度。

基于Natural Policy Gradient算法，将优化目标用一阶函数来近似，约束项用二阶函数来近似，由于二阶函数涉及到构造Hessian matrix，计算量巨大，论文给出了 conjugate gradient + Fisher information matrix的近似快速实现方案

参数更新：
θ new  = θ old  + 1 λ A ( θ old  ) − 1 ∇ θ L ( θ ) ∣ θ = θ old  \theta_{\text {new }}=\theta_{\text {old }}+\left.\frac{1}{\lambda} A\left(\theta_{\text {old }}\right)^{-1} \nabla_{\theta} L(\theta)\right|_{\theta=\theta_{\text {old }}} θnew ​=θold ​+λ1​A(θold ​)−1∇θ​L(θ)∣∣∣∣​θ=θold ​​
作者指出natrual policy gradient和policy gradient都是TRPO的特别形式。

a_{\text {new }}=\theta_{\text {old }}+\left.\frac{1}{\lambda} A\left(\theta_{\text {old }}\right)^{-1} \nabla_{\theta} L(\theta)\right|{\theta=\theta{\text {old }}}
$$
作者指出natrual policy gradient和policy gradient都是TRPO的特别形式。