TRPO

摘要：一种策略改进过程，保证单调改进。通过对理论进行几次近似，开发了TRPO算法。该算法类似于自然梯度策略（natural policy gradient）方法。尽管近似值与理论有所偏差，但它往往能够实现单调改进，几乎不用调超参。

背景

大多数策略优化算法可以分为三类：1）策略迭代方法（policy iteration methods），即基于值函数的方法；2）策略梯度方法（policy gradient methods），即参数化策略的方法；3）无导数优化方法（derivative-free optimization methods）。

无导数优化方法在很多问题上受到青睐，因为它们效果好，容易理解和实现。ADP（approximate dynamic programming）和基于梯度的方法无法击败无导数优化方法，这是令人不满意的，因为基于梯度的优化算法比无梯度方法享有更好的样本复杂度保证。基于梯度的优化方法在监督学习的函数估计中已经比较成功，如何将其扩展到强化学习？

文章证明最小化某个替代目标函数可以保证策略改进。通过对理论算法进行一系列近似，文章给出了TRPO算法。文章给出了这个算法的两种变体——single path和vine。前者可以应用于model-free场景，后者需要将系统恢复到特定状态（这通常只能在模拟中实现）。

预备知识

基于策略\(\pi\)的期望收益\(\eta(\pi)\)和优势函数\(A_{\pi}(s_{t},a_{t})\)，计算策略\(\widetilde{\pi}\)的期望收益\(\eta(\widetilde{\pi})\)，公式如下： \[ \eta(\widetilde{\pi})=\eta(\pi)+E_{s_0,a_0,...\sim\color{red}\widetilde{\pi}}[\sum_{t=0}^{\infty}\gamma^{t}A_{\color{red}\pi}(s_{t},a_{t})] \tag{1} \]

证明：

定义策略\(\pi\)下状态\(s\)的折扣状态访问频率（discounted visitation frequencies）为\(\rho_{\pi}(s)\)如下： \[ \rho_{\pi}(s)=P(s_{0}=s)+\gamma P(s_{1}=s)+\gamma^{2}P(s_{2}=s)+\dots \tag{2} \]

上面的折扣状态访问频率未归一化，归一化形式为\(\rho_{\pi}(s) = (1 - \gamma) \sum_{t=0}^{\infty} \gamma^{t} P(s_{t}=s)\)

基于折扣状态访问频率，期望收益计算公式可以改写为基于状态分布的形式，如下： \[ \begin{align*} \eta(\widetilde{\pi}) &= \eta(\pi) + \sum_{t=0}^{\infty} \sum_{s} P(s_{t}=s|\widetilde{\pi}) \sum_{a} \widetilde{\pi}(a|s) \gamma^{t} A_{\pi}(s,a) \\ &= \eta(\pi) + \sum_{s} \sum_{t=0}^{\infty} \gamma^{t}P(s_{t}=s|\widetilde{\pi}) \sum_{a} \widetilde{\pi}(a|s) A_{\pi}(s,a) \\ &= \eta(\pi) + \sum_{s} \rho_{\color{red}\widetilde{\pi}}(s) \sum_{a} \widetilde{\pi}(a|s) A_{\pi}(s,a) \tag{3} \end{align*} \]

\(\sum_{a} \widetilde{\pi}(a|s) A_{\pi}(s,a)\)可以看作对策略\(\pi\)的优势函数\(A_{\pi}\)的加权求和，策略改进即调整一组更好的权重。

从等式（3）可以看出，如果我们能够保证，从策略\(\pi\)更新到策略\(\widetilde{\pi}\)，对于每一个状态\(s\)，都有非负的期望优势，即\(\sum_{a} \widetilde{\pi}(a|s) A_{\pi}(s,a) \geq 0\)，就能实现策略的单调改进。这个结果和使用确定性策略进行策略迭代的过程也具有一致性，策略迭代中策略改进采用\(\widetilde{\pi}(s)=argmax_{a}A_{\pi}(s,a)\)，如果存在\((s,a)\)使得\({A_{\pi}(s,a)} \gt 0\)，则策略将得到改善，否则，算法收敛到最优策略。

第一次近似：等式(3)的计算依赖于\(\rho_{\widetilde{\pi}}(s)\)，这意味着需要用改进策略\(\widetilde{\pi}\)来采样（而不是用原策略\(\pi\)），用所有可能的改进策略\(\widetilde{\pi}\)采样并计算其期望收益是不现实的，因此论文做出如下近似（即忽略了策略变化对状态访问频率的影响）： \[ L_{\pi}(\widetilde{\pi}) = \eta(\pi) + \sum_{s} \rho_{\color{red} \pi}(s) \sum_{a} \widetilde{\pi}(a|s) A_{\pi}(s,a) \] 假设有参数化策略\(\pi_{\theta}\)，并且策略\(\pi_{\theta}\)关于参数\(\theta\)可微，上述近似函数\(L_{\pi}\)和原函数\(\eta\)一阶匹配。表示如下： \[ \begin{align*} L_{\pi_{\theta_{0}}}(\pi_{\theta_{0}}) &= \eta(\pi_{\theta_{0}}) \\ \nabla_{\theta} L_{\pi_{\theta_{0}}}(\pi_{\theta})|_{\theta=\theta_{0}} &= \nabla_{\theta} \eta(\pi_{\theta})|_{\theta=\theta_{0}} \tag{4} \end{align*} \] 上述结论表明，在策略变化较小的情况下，对\(L\)的改进也将导致\(\eta\)的改进。但该结论没有提供一个具体的步长设置的指导。

2002年，Kakade & Langford提出了一种策略更新方案叫做保守策略迭代（conservative policy iteration），并且他们能够给出\(\eta\)改进的明确下限。假设\(\pi_{old}\)表示当前策略，\(\pi^{\prime} = argmax_{\pi^{\prime}} L_{\pi_{old}}(\pi^{\prime})\)，改进策略\(\pi_{new}\)定义如下： \[ \pi_{new}(a|s) = (1-\alpha) \pi_{old}(a|s) + \alpha \pi^{\prime}(a|s) \tag{5} \] 该方法给出\(\eta\)下限如下： \[ \eta(\pi_{new}) \ge L_{\pi_{old}}(\pi_{new}) - \frac{2 \epsilon \gamma}{(1-\gamma)^2} \alpha^2 \tag{6} \\ \epsilon = \max_{s}|E_{a \sim \pi^{\prime}(a|s)}[A_{\pi}(s,a)]| \] 这个界限仅适用于由公式(5)生成的混合策略。这种策略在实际使用中笨重且受限，实际的策略更新方案最好适用于所有一般随机策略。

一般随机策略的单调改进保证

等式(6)表明，如果策略更新能够改进不等式右侧，就能够保证提高真实性能\(\eta\)。这篇文章的主要理论结果即，通过将\(\alpha\)替换为\(\pi\)和\(\widetilde{\pi}\)的距离，并且适当调整\(\epsilon\)，就可以将等式(6)的策略性能下限扩展到一般随机策略。本文采用全变差距离（total variation divergence）对策略进行距离度量。

全变差距离：\(D_{TV}(p || q) = \frac{1}{2} \sum_{i} |p_{i} - q_{i}|\)，其中\(p,q\)表示离散随机变量的分布律（结论可以通过用积分代替求和直接扩展到连续状态和动作场景）

定义策略\(\pi\)和策略\(\widetilde{\pi}\)距离如下： \[ D_{TV}^{max}(\pi, \widetilde{\pi}) = \max_{s} D_{TV}(\pi(\cdot|s)||\widetilde{\pi}(\cdot|s)) \tag{7} \] 定理1：定义\(\alpha = D_{TV}^{max}(\pi_{old}, \pi_{new})\)，存在下面的策略性能下限： \[ \begin{align*} \eta(\pi_{new}) &\ge L_{\pi_{old}}(\pi_{new}) - \frac{4 \epsilon \gamma}{(1 - \gamma)^2} \alpha^2 \\ \epsilon &= \max_{s,a}|A_{\pi}(s,a)| \tag{8} \end{align*} \]

证明：

因为全变差距离和KL散度具有如下关系\(D_{TV}(p || q)^2 \le D_{KL}(p || q)\)，定义\(D_{KL}^{max}(\pi, \widetilde{\pi})=max_{s}D_{KL}(\pi(\cdot|s)||\widetilde{\pi}(\cdot|s))\)，可以得到如下策略性能下限： \[ \begin{align*} \eta(\widetilde{\pi}) &\ge L_{\pi}(\widetilde{\pi}) - CD_{KL}^{max}(\pi, \widetilde{\pi}) \\ C &= \frac{4 \epsilon \gamma}{(1 - \gamma)^2} \tag{9} \end{align*} \] 定义\(M_{i}(\pi) = L_{\pi_{i}}(\pi) - CD_{KL}^{max}(\pi_{i},\pi)\)，于是有如下推导： \[ \begin{align*} \eta(\pi_{i+1}) &\ge M_{i}(\pi_{i+1}) \\ \eta(\pi_{i}) &= M_{i}(\pi_{i}) \\ \eta(\pi_{i+1}) - \eta(\pi_{i}) &\ge M_{i}(\pi_{i+1}) - M_{i}(\pi_{i}) \tag{10} \end{align*} \] 由此可以得到，通过在每轮迭代时最大化\(M_{i}(\pi_{i+1})\)，算法能够保证真实策略性能\(\eta\)单调提升。这篇文章基于此提出了一个近似策略迭代方案（TRPO算法是对该方案的近似），如下图：

参数化策略的优化

前面考虑问题时没有深入到策略参数层面。现在考虑参数化策略\(\pi_{\theta}(a|s)\)，并使用\(\theta\)重写前面的符号，例如\(\eta(\theta) := \eta(\pi_{\theta})\),\(L_{\theta}(\widetilde{\theta}) := L_{\pi_{\theta}}(\pi_{\widetilde{\theta}})\)。

前面的章节已经表明，\(\eta(\theta) \ge L_{\theta_{old}}(\theta) - CD_{KL}^{max}(\theta_{old}, \theta)\)，在\(\theta = \theta_{old}\)时不等式取等号，为了保证策略性能\(\eta\)单调改进，优化目标为\(\max_{\theta} [L_{\theta_{old}}(\theta) -CD_{KL}^{max}(\theta_{old}, \theta)]\)。

实际上，如果我们使用上述理论推荐的惩罚系数\(C\)，步长将会非常小。一种方式是针对新旧策略的\(KL\)散度施加约束，即一个信任区域： \[ \begin{align*} & \max_{\theta} L_{\theta_{old}}(\theta) \\ & s.t.D_{KL}^{max}(\theta_{old}, \theta) \le \delta \tag{11} \end{align*} \] 第二次近似：上面约束计算新旧参数的\(KL\)散度是针对所有状态\(s\)求\(max\)，因此虽然上式是由理论推导得到的，但在实际中直接优化这个问题是非常困难的。因此论文使用平均\(KL\)散度替代\(max\)操作，即： \[ \bar{D}_{KL}^{\rho}(\theta_{1},\theta_{2}) := E_{\color{red} s \sim \rho_{\pi_{\theta_{1}}}}[D_{KL}(\pi_{\theta_{1}}(\cdot|s) || \pi_{\theta_{2}}(\cdot|s))] \] 因此优化问题变为： \[ \begin{align*} \max_{\theta} \space & L_{\theta_{old}}(\theta) \\ s.t. \space & \bar{D}_{KL}^{\rho_{\pi_{old}}}(\theta_{old}, \theta) \le \delta \tag{12} \end{align*} \]

基于样本估计目标和约束

现在考虑使用蒙特卡洛模拟，用采样样本近似目标函数和约束函数。目标是求解下面的优化问题（对\(L_{\theta_{old}}\)展开，其中\(\eta(\theta_{old})\)相对于优化变量\(\theta\)为常数，直接舍去）： \[ \begin{align*} \max_{\theta} \space & \sum_{s} \rho_{\theta_{old}}(s) \sum_{a} \pi_{\theta}(a|s) A_{\theta_{old}}(s,a) \\ s.t. \space & \bar{D}_{KL}^{\rho_{\theta_{old}}}(\theta_{old}, \theta) \le \delta \tag{13} \end{align*} \] 对上面的优化问题做3次替换：

1. 将\(\sum_{s}\rho_{\theta_{old}}(s)[...]\)替换为\(E_{s \sim \rho_{\theta_{old}}}[...]\)（原文中还有\(\frac{1}{1 - \gamma}\)系数，一方面我没看懂怎么推出来的，另一方面这个系数不影响优化问题本身，因此忽略）
2. 将\(A_{\theta_{old}}\)替换为\(Q_{\theta_{old}}\)
3. 将关于动作\(a\)的求和\(\sum_a\)替换为一个重要度采样估计量：\(\sum_{a} \pi_{\theta}(a|s_{n}) A_{\theta_{old}}(s_{n},a) = E_{a \sim q}[\frac{\pi_{\theta}(a|s_{n})}{q(a|s_{n})} A_{\theta_{old}}(s_{n},a)]\)

于是优化问题变为如下形式： \[ \begin{align*} \max_{\theta} \space & E_{s \sim \rho_{\theta_{old}}, a \sim q}[\frac{\pi_{\theta}(a|s)}{q(a|s)}Q_{\theta_{old}}(s,a)] \\ s.t. \space & E_{s \sim \rho_{\theta_{old}}}[D_{KL}(\pi_{\theta_{old}}(\cdot|s) || \pi_{\theta}(\cdot|s))] \le \delta \tag{14} \end{align*} \] 下面介绍两种采样方案——single path和vine

Single Path

基于\(s_{0} \sim \rho_{0}\)分布，收集一系列状态序列，模拟\(\pi_{\theta_{old}}\)策略执行若干时间步，生成轨迹\(s_{0},a_{0},s_{1},a_{1},...,s_{T-1},a_{T-1},s_{T}\)。这种方案下，\(q(a|s)=\pi_{\theta_{old}}(a|s)\)。

Vine

基于\(s_{0} \sim \rho_{0}\)分布，收集一系列状态序列，模拟\(\pi_{\theta_{i}}\)策略生成轨迹。然后沿着这些轨迹，选择关于\(N\)个状态的子集，表示为\(s_{1},s_{2},...,s_{N}\)

Q&A

1. 什么是自然梯度策略（natural policy gradient）？

2. 什么是无导数优化方法（derivative-free optimization methods）？启发式搜索算法？

3. 状态访问频率为什么取折扣？是为了配合后续推导？是否有单独的含义？

4. minorization-maximization (MM) algorithm定义？proximal gradient methods定义？mirror descent定义？