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定义？