TRPO

一、背景知识

在介绍TRPO算法之前，先问一个问题：TRPO是在什么背景下衍生出来的？为了回答这个问题，需要先介绍策略梯度思想（Policy Gradient，PG）。

1、Policy Gradient

策略梯度不同于值优化算法，策略梯度算法致力于寻求最优策略。其中，策略由参数化函数π(a|s, θ)表示，由此可见，只要更新参数θ，即可获得更新后的策略π(a|s, θ)。引入了最优策略的概念，接下来的问题就是如何定义最优策略？这里介绍最简单的PG算法：蒙特卡洛PG，其最优策略由标量J(θ)衡量，具体表达式为： ∇_θJ(θ) = ∑_s ∈ Sη(s)∑_a ∈ A∇_θπ(a|s, θ)q_π(s, a) 其中，(s)表示状态S概率分布，q_{}(s, a)表示在状态s下执行动作a可获得的q值。

我们可以将上述式子进行一定的转换得到其期望形式： 其中，可以对∇_θπ(a|s, θ)基于以下求导公式进行转换 因此 ∇_θπ(a|s, θ) = π(a|s, θ)∇_θln π(a|s, θ) 带入可得 有了优化目标的具体梯度表达式之后，便可以利用梯度下降方法来由优化参数。下面是利用梯度下降法优化参数，里面带入了时间步的衡量表示t 理论上来说，我们就可以基于上式开始算法实现。但是，现实情况下根本不知道其梯度真实值，因为我们并不了解系统的具体模型。所以，可以考虑利用蒙特卡洛采样来获取具体的q_t(s_t, a_t)，则上式可转换为： θ_t + 1 = θ_t + α∇_θln π(a_t|s_t, θ_t)q_t(s_t, a_t) 由于，可以重写上式： 即 θ_t + 1 = θ_t + αβ_t∇_θπ(a_t|s_t, θ_t).

如果β_t ≥ 0,选择 (s_t, a_t)的概率会增加. 即 π(a_t|s_t, θ_t + 1) ≥ π(a_t|s_t, θ_t). β_t越大, 概率增加的越大，换句话说，如果这个动作会带来q值的提升，那么经过策略更新之后，以后在这个状态下选择这个动作的概率越大

如果β_t < 0, 选择 (s_t, a_t)的概率会减小，即 π(a_t|s_t, θ_t + 1) < π(a_t|s_t, θ_t). 证明如下。当 θ_t + 1 − θ_t足够小, π(a_t|s_t, θ_t + 1)可以进行泰勒展开 结果显而易见。最后，附上REINFORCE算法伪代码

REINFORCE

观察REINFORCE伪代码，可以看出来，REINFORCE是一种on-policy（同策略）算法，也就是选择动作的策略和需要更新的策略是同一种策略。同策略算法会有一种问题：采样得到的样本利用率太低，比如在策略网络参数为t下采样得到的样本轨迹，在下一个时刻就不能用于训练，因为下一个时刻策略网络的参数被更新为{t+1}，理论上t时刻采样得到的样本轨迹与新策略得到的轨迹不一致，所以无法使用。

二、TRPO推导

首先，来了解一下下面几个常见的值函数：

累计奖赏函数，表示在策略： 状态值函数，表示在状态s_t下的累计奖赏： 状态-动作值函数，表示在状态s_t下执行动作a_t后采用策略。V_{}(s_t)可以看作是Q_{}(s_t, a_t)关于动作a的平均： 优势函数，表示在该状态下，采取动作a_t相较于平均水平意义下的优势： A_π(s, a) = Q_π(s, a) − V_π(s) 现在假设策略从，累计奖赏变化为： 证明：

1、首先给出优势函数A_{}(s, a)与Q_{}(s, a)和V_{}(s)之间关系的推导证明： 因此： A_π(s, a) = Q_π(s, a) − V_π(s) = 𝔼_{s^′ ∼ P(s^′|s, a)}[r(s) + γV_π(s^′) − V_π(s)] 2、计算优势函数在策略下的期望 为了便于后面的证明，我们这里需要引入一个新定义：访问频率。其含义是在此路径下访问到状态s的频率，具体表示为： 将访问频率代入式（1），可以得到： 从上式可以看出，当从策略更新到，我们只需要保证∑_sρ_π̃(s)∑_aπ̃(a|s)A_π(s, a) ≥ 0，则可以使得奖赏函数增加或者保持不变，那么利用式（2）不断更新策略便可以不断地增加累计奖赏，直至收敛到一个局部最优值为止。 注意，{}(s)是新策略中每个状态出现的频率，这就意味着我们可能要采样很多数据（基于不同的去采样），才能得到符合∑_sρ_π̃(s)∑_aπ̃(a|s)A_π(s, a) ≥ 0的采样策略轨迹。TRPO的目标之一就是减少采样次数，增大采样数据利用率，因此考虑()的替代函数： L_π(π̃) = η(π) + ∑_sρ_π(s)∑_aπ̃(a|s)A_π(s, a)  (3) L{}()与()的区别仅在于_{}(s)不同，这样我们就可以基于旧策略的采样去得到所有状态的访问频率。为什么这么替换是可以的呢？下面给出两个等式，其中代表旧策略，代表新策略 L_πθ0(π_θ0) = η(π_θ0)  (4)

∇_θL_πθ0(π_θ)|_θ = θ0 = ∇_θη(π_θ)|_θ = θ0  (5)

式（4）证明如下图所示：

（4）证明

式（5）证明如下：

对于替代函数： 对于累积奖赏： 其中a {}(a|s) A_{_{_0}} = 0,，则式（5）成立

式(4)表示当策略没有更新时，替代函数和原累积奖赏函数是完全相等的。式(5)说明替代函数和原累积奖赏函数关于策略参数\theta的导数，在旧策略\pi_{\theta_0}这一点处是相同的，也就是说策略从\pi_{\theta_0} \to \tilde{\pi}有一个极小的变化时，如果替代函数L_{\pi_{\theta_0}}增加了累积奖赏\eta也会增加，那么便可以用替代函数作为优化目标来改善策略。

那么策略迭代时π和π̃具体满足什么样的约束才能保证替代函数增加时累积奖赏也能增加呢？首先定义一个α−coupled policy(π, π̃)，满足联合的分布P(a ≠ ã|s) ≤ α。再定义TV散度(Total variation divergence)为，对于两个离散概率分布p, q，。

TV散度和coupled random variables的关系为： 假设分布p_X, q_Y满足D_{TV}(p_X|q_Y) = ，则存在联合分布(X, Y)，满足X=Y的概率为1-。 令D_{TV}^{max}(, ) = s D{TV}((|s)|(|s)) 则可以得到定理1: 定理1： 令α = D_TV^max(π, π̃)，则替代函数和累积奖赏的差为: 其中, = {s,a} |A{}(s, a)|。 定理1可以通过两个引理证明。

引理1： |Ā(s)| ≤ 2αmax_s, a|A_π(s, a)| 证明： 其中, 𝔼_{a ∼ π(⋅|s)}[A_π(s, a)] = 0。根据三角不等式及coupled pair的定义, 可得 |Ā(s)| ≤ α[|𝔼_{ã ∼ π̄(⋅|s)}[A_π(s, ã)]|+|𝔼_{(ã, a) ∼ (π, π̄)|a ≠ ã}[A_π(s, a)]|] ≤ 2αmax_s, a|A_π(s, a)|◼ 好的，遵照您的指示，我将复刻图片中的所有内容，并对所有公式（无论是行间还是行内）提供未经渲染的原始 LaTeX 代码。

---

引理2： |𝔼_{st ∼ π̄}[Ā(s_t)] − 𝔼_{st ∼ π}[Ā(s_t)]| ≤ 2αmax_s|A_π(s, a)| ≤ 4α(1 − (1 − α)^t)max_s|A_π(s, a)| 证明：

令n_t表示当 i < t 时 a 的次数，则 𝔼_{st ∼ π̄}[Ā(s_t)] = P(n_t = 0)𝔼_{st ∼ π̄|nt = 0}[Ā(s_t)] + P(n_t > 0)𝔼_{st ∼ π̄|nt > 0}[Ā(s_t)] 同理可表示{s_t }[{A}(s_t)]。由于当n_t=0时表明在两种策略下采样到的路径完全相同，因此{s_t |n_t=0}[{A}(s_t)] = {s_t {}|n_t=0}[{A}(s_t)]。作差可得 𝔼_{st ∼ π}[Ā(s_t)] − 𝔼_{st ∼ π̄}[Ā(s_t)] = P(n_t > 0)(𝔼_{st ∼ π|nt > 0}[Ā(s_t)] − 𝔼_{st ∼ π̄|nt > 0}[Ā(s_t)]) 根据coupled pair的定义, P(n_t=0) (1-)^t，且P(n_t>0) -(1-)^t。结合引理1并利用三角不等式可得 |𝔼_{st ∼ π̄}[Ā(s_t)] − 𝔼_{st ∼ π}[Ā(s_t)]| ≤ 4α(1 − (1 − α)^t)max_s|A_π(s, a)|. 回过头来观察替代函数和原累积奖赏的差别|({}) - L({})|。根据二者定义，结合引理2得到 其中，= {s,a}|A(s,a)|。这表明，策略，差值|({}) - L_({})|满足定理1。

由于KL散度D_{TV}(p||q)^2 D_{KL}(p||q)，则可以用KL散度对策略更新的范围重新约束。令D_{KL}^{max} = s D{KL}((|s){}(|s))，可对定理1放缩，得到 η(π̄) ≥ L_π(π̄) − CD_KL^max(π, π̄) 至此，在KL散度约束下，找到了累积奖赏函数的一个下界。

单调递增原理

根据式(7)，我们便能找到一系列单调递增的策略，满足(_0) (_1) (_2) 。

证明：令M_i() = L_{i}() - C D{KL}^{max}(_i, )，则 η(π_i + 1) ≥ M_i(π_i + 1)

η(π_i) = M_i(π_i)

η(π_i + 1) − η(π_i) ≥ M_i(π_i + 1) − M_i(π_i)(8)

因此在迭代时最大化M_i便能保证。

优化模型的改进

根据式(8)，最大化 max_θL_πθ0(π_θ) − CD_KL^max(π_θ0, π_θ)(9) 也能保证累积奖赏函数\eta的优化。但实践中表明惩罚项系数C会将策略迭代的步长非常小，一个能增大步长的方式是用KL散度将新旧策略限制在一个信任区域中： 但(10)的问题是,需要使所有状态下的KL散度满足约束,当状态空间很大时非常不实际。因此启发性地使用KL散度的均值进行约束，即 其中{D}{KL}^{{0}}({0}, ) = {s {_0}}[D_{KL}(_{0}(|s), (|s))]。

基于样本的目标函数估计

目标函数和约束可以用来蒙特卡洛方法近似得到，先对式(11)进行改写，首先用期望代替L_{{0}}()中的s {0}(s)，并删去与参数，得到目标函数{s {0}}[{a }[A_{_{_0}}(s,a)]]。接着用Q函数代替优势函数A，得到{s _{_0}}[{a }[Q_{_{_0}}(s,a)]]。可以证明用Q函数代替后二者仅相差一个常数。

证明： 其中, (12)的第二项为一个与参数, 因此可以用Q函数替代。

然后对{a }[Q_{_{_0}}(s,a)]用重要度采样(Importance sampling)进行改写, 得到 采样分布_{0}(a|s)也可以使用其他的分布, 但作者测试发现使用旧的策略分布{_0}(a|s)在连续问题上表现很好。由此得到了TRPO最终的模型: 最后附上TRPO伪代码

TRPO Pseudocode

参考链接