- 参考链接：
TRPO
TRPO 目标
- 目标定义：
$$
\begin{aligned}
\max_{\theta_\text{new}} \quad &\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}}\left[\frac{\pi_{\theta_\text{new}}(a|s)}{\pi_{\theta_\text{old}}(a|s)} A_{\pi_{\theta_\text{old}}}(s,a)\right] \\
&\text{s.t. } \quad \quad \mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}} \left[D_{\text{KL}}(\pi_{\theta_\text{old}}, \pi_{\theta_\text{new}})\right] \le \delta
\end{aligned}
$$ - TRPO 的目标详细推导见RL——TRPO-PPO-目标函数基础推导
TRPO 推导
- TRPO 的目标仍然很难直接求解，所以TRPO考虑对目标做进一步的近似（近似形式的具体证明见附录）
$$
\begin{aligned}
\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}}\left[\frac{\pi_{\theta}(a|s)}{\pi_{\theta_\text{old}}(a|s)} A_{\pi_{\theta_\text{old}}}(s,a)\right] &\approx g^T(\theta-\theta_{old}) \\
\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}} \left[D_{\text{KL}}(\pi_{\theta_\text{old}}, \pi_{\theta})\right] &\approx \frac{1}{2}(\theta-\theta_{old})^TH(\theta-\theta_{old})
\end{aligned}
$$- \(g\) 为一阶梯度：
$$ g = \nabla_{\theta}\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}}\left[\frac{\pi_{\theta}(a|s)}{\pi_{\theta_\text{old}}(a|s)} A_{\pi_{\theta_\text{old}}}(s,a)\right] \vert_{\theta = \theta_{\text{old}}}$$ - \(H\) 为原始KL散度在 \(\theta = \theta_{\text{old}} \) 处的海森矩阵（Hessian Matrix，又译作黑塞矩阵），（PS：KL散度的海森矩阵就是Fisher矩阵，一般是正定的）：
$$ H = H[\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}} \left[D_{\text{KL}}(\pi_{\theta_\text{old}}, \pi_{\theta})\right]] $$- 其中
$$ H[f(x,y)] = \begin{bmatrix}
\frac{\partial^2f}{\partial x^2} & \frac{\partial^2f}{\partial x\partial y} \\
\frac{\partial^2f}{\partial x \partial y} & \frac{\partial^2f}{\partial y^2}
\end{bmatrix}
$$ - 在当前场景中 \(H_{ij}\) 为
$$ H_{ij} = \frac{\partial}{\partial \theta_i}\frac{\partial}{\partial \theta_j} \mathbb{E}_{s \sim \rho_{\pi_{\theta_{\text{old}}}}} \left[D_{\text{KL}}(\pi_{\theta_{\text{old}}}, \pi_{\theta})\right] \vert_{\theta = \theta_{\text{old}}} $$
- 其中
- \(g\) 为一阶梯度：
- 于是得到进一步优化的目标
$$
\begin{aligned}
\theta_{k+1} = \mathop{\arg\max}_\theta &g^T(\theta-\theta_k)\\
\text{s.t. } \quad \frac{1}{2}(\theta-\theta_k)^T&H(\theta-\theta_k)≤\delta
\end{aligned}
$$ - 可根据拉格朗日乘子法求解以上问题得到如下解（详细推导见附录）：
$$ \theta_{k+1}=\theta_k+\sqrt{\frac{2\delta}{g^TH^{-1}g}}H^{-1}g $$ - 现实场景中，计算和存储Hessian矩阵的逆矩阵 \(H^{-1}\) 会耗费大量时间，所以TRPO通过共轭梯度法来避免直接求解 \(H^{-1}\)，核心思想就是直接计算 \(x = H^{-1}g\) 作为参数的更新方向
- 设定 \(x = H^{-1}g\)，则原始参数更新公式可变为：
$$ \theta_{k+1}=\theta_k+\sqrt{\frac{2\delta}{x^{T}Hx}}x $$ - 求解 \(x = H^{-1}g\) 则可转换为求方程 \(Hx = g\) 的解，方程 \(Hx = g\) 的解可通过共轭梯度法（Conjugate Gradient Method,）来求解，方法参见ML——共轭梯度法和最速下降法
- 其中，共轭梯度法伪代码如下
- 其中，共轭梯度法伪代码如下
TRPO更新步长
- 当前TRPO求解方案采用了泰勒展开的1阶近似和2阶近似，不是精准求解，新参数不一定能满足KL散度约束限制，所以在更新时，我们可以再进行一次步长搜索，使得更新后的新参数满足KL散度限制，且能够提升目标函数
- 线性搜索的具体规则，在 \((0,1)\) 区间内抽取K个点 \(\{\alpha^i\}_{i=1}^K\)
TRPO训练伪代码
- TRPO伪代码：
附录：约束问题的泰勒展开近似推导证明
- 近似结果
$$
\begin{aligned}
\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}}\left[\frac{\pi_{\theta}(a|s)}{\pi_{\theta_\text{old}}(a|s)} A_{\pi_{\theta_\text{old}}}(s,a)\right] &\approx g^T(\theta-\theta_{old}) \\
\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}} \left[D_{\text{KL}}(\pi_{\theta_\text{old}}, \pi_{\theta})\right] &\approx \frac{1}{2}(\theta-\theta_{old})^TH(\theta-\theta_{old})
\end{aligned}
$$ - \(g\) 为一阶梯度：
$$ g = \nabla_{\theta}\mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}}\left[\frac{\pi_{\theta}(a|s)}{\pi_{\theta_\text{old}}(a|s)} A_{\pi_{\theta_\text{old}}}(s,a)\right] \vert_{\theta = \theta_{\text{old}}}$$ - \(H\) 为原始KL散度在 \(\theta = \theta_{\text{old}} \) 处的海森矩阵：
$$
H_{ij} = \frac{\partial}{\partial \theta_i}\frac{\partial}{\partial \theta_j} \mathbb{E}_{s \sim \rho_{\pi_{\theta_{\text{old}}}}} \left[D_{\text{KL}}(\pi_{\theta_{\text{old}}}, \pi_{\theta})\right] \vert_{\theta = \theta_{\text{old}}}
$$
泰勒展开回顾
- 泰勒展开是一种在数学分析中用于近似函数的方法，特别是当直接计算函数值较为困难时，基本思想是将一个函数在一个点附近用一个多项式来近似表示
- 对于一个在点 \(a\) 处具有 \(n+1\) 阶导数的函数 \(f(x)\)，其在 \(a\) 点的泰勒展开可以表示为：
$$ f(x) = f(a) + \frac{f’(a)}{1!}(x-a) + \frac{f’’(a)}{2!}(x-a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x-a)^n + R_n(x) $$- 其中， \(R_n(x)\) 是余项，表示的是泰勒多项式与实际函数之间的误差，常表示为：
$$ R_n(x) = o((x-a)^n) $$- 这里的 \(o\) 表示当 \(x\) 趋向于 \(a\) 时， \(R_n(x)\) 相对于 \((x-a)^n\) 是高阶无穷小
- 其中， \(R_n(x)\) 是余项，表示的是泰勒多项式与实际函数之间的误差，常表示为：
泰勒展开在很多领域都有广泛的应用，例如物理学中的近似计算、工程学中的信号处理等。通过选择合适的 (a) 值和 (n) 阶次，可以得到不同精度的近似结果。特别地，当 (a=0) 时，这种特殊的泰勒展开被称为麦克劳林展开
目标的泰勒一阶近似推导
- 令 \(f(\theta)\) 为最优化目标，则：
$$ f(\theta) = \mathbb{E}_{s \sim \rho_{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}}\left[\frac{\pi_{\theta}(a|s)}{\pi_{\theta_\text{old}}(a|s)} A_{\pi_{\theta_\text{old}}}(s,a)\right] $$ - 此时对 \(f(\theta)\) 在 \(\theta = \theta_{\text{old}}\) 做泰勒展开有
$$ f(\theta) = f(\theta_{\text{old}}) + \nabla_\theta f(\theta)\vert_{\theta=\theta_{\text{old}}}(\theta - \theta_{\text{old}}) + o(\theta^2)$$ - 由于 \(f(\theta_{\text{old}})\) 与 \(\theta\) 无关，所以最大化 \(f(\theta)\) 等价于最大化 \(\nabla_\theta f(\theta)\vert_{\theta=\theta_{\text{old}}}(\theta - \theta_{\text{old}}) = g^T(\theta-\theta_{old})\)
约束的泰勒二阶近似推导
- 将KL散度在 \(\theta = \theta_{\text{old}}\) 处二阶展开有
$$
\begin{align}
f(\theta) &= D_{\text{KL}}(\pi_{\theta_{\text{old}}}, \pi_\theta) \\
&= D_{\text{KL}}(\pi_{\theta_{\text{old}}}, \pi_{\theta_{\text{old}}}) + \nabla_\theta D_{\text{KL}}(\pi_{\theta_{\text{old}}}, \pi_\theta) \vert_{\theta=\theta_{\text{old}}} (\theta - \theta_{\text{old}}) + \frac{1}{2}(\theta - \theta_{\text{old}})^TH(\theta - \theta_{\text{old}}) + o(\theta^3)
\end{align}
$$- 显然，第一项 \( D_{\text{KL}}(\pi_{\theta_{\text{old}}}, \pi_{\theta_{\text{old}}})=0 \)
- 可以证明，第二项为0，证明如下：
$$
\begin{align}
\nabla_\theta D_{\text{KL}}(\pi_{\theta_{\text{old}}}, \pi_\theta) \vert_{\theta=\theta_{\text{old}}} &= \nabla_\theta \int_a \pi_{\theta_{\text{old}}}(a|s) \log \frac{\pi_{\theta_{\text{old}}}(a|s)}{\pi_{\theta(a|s)}} da\vert_{\theta = \theta_{\text{old}}} \\
&= \nabla_\theta \int \pi_{\theta_{\text{old}}}(a|s) \Big(\log \pi_{\theta_{\text{old}}}(a|s) - \log\pi_{\theta}(a|s)\Big) da\vert_{\theta = \theta_{\text{old}}} \\
&= - \int \pi_{\theta_{\text{old}}}(a|s) \nabla_\theta \log \pi_{\theta(a|s)} \vert_{\theta = \theta_{\text{old}}} da \quad \text{积分求导互换} \\
&= - \int \pi_{\theta_{\text{old}}}(a|s) \frac{\nabla_\theta \pi_{\theta}(a|s)}{\pi_{\theta}(a|s)}\vert_{\theta = \theta_{\text{old}}} da \quad \text{对数概率技巧} \\
&= - \int \pi_{\theta_{\text{old}}}(a|s) \frac{\nabla_\theta \pi_{\theta}(a|s)\vert_{\theta = \theta_{\text{old}}}}{\pi_{\theta_\text{old}}(a|s)} da \\
&= - \nabla_\theta \int \pi_{\theta}(a|s) da\vert_{\theta = \theta_{\text{old}}} \quad \text{积分求导再次互换} \\
&= - \nabla_\theta 1 \\
&= 0
\end{align}
$$ - 证毕
附录：最优化问题求解的详细推导证明
给定最优化问题
$$
\begin{aligned}
\theta_{k+1} = \mathop{\arg\max}_\theta &g^T(\theta-\theta_k)\\
\text{s.t. } \quad \frac{1}{2}(\theta-\theta_k)^T&H(\theta-\theta_k)≤\delta
\end{aligned}
$$对于上述问题，Karush-Kuhn-Tucker (KKT) 条件可以表述为以下几点：
- 原始可行性 ：解必须满足原始约束
$$
\frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k) \leq \delta.
$$ - 对偶可行性 ：拉格朗日乘子（或对偶变量）必须非负
$$
\lambda \geq 0.
$$ - 互补松弛性 ：拉格朗日乘子与对应的不等式约束之间的乘积必须为零
$$
\lambda \left( \frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k) - \delta \right) = 0.
$$ - 拉格朗日函数的梯度为零 ：考虑拉格朗日函数 \(L(\theta, \lambda) = - g^T(\theta-\theta_k) + \lambda \left( \frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k) - \delta \right)\)，其对 \(\theta\) 的偏导数应等于零
$$
\nabla_\theta L = - g + \lambda H (\theta - \theta_k) = 0.
$$- 注意：这里是因为目标是max，需要改成min后才能用 \(+\lambda (\cdot)\) 的操作
- 原始可行性 ：解必须满足原始约束
这里， \(H\) 是一个对称矩阵（Hessian矩阵是对称的，因为 \(\frac{\partial^2 f}{\partial x \partial y} = \frac{\partial^2 f}{\partial y \partial x}\) ）， \(\lambda\) 是与约束相关的拉格朗日乘子， \(\delta\) 是给定的常数
根据KKT条件中的互补松弛性条件，当 \(\lambda > 0\) 时，这意味着约束 \(\frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k) \leq \delta\) 是紧的，即：
$$
\frac{1}{2}(\theta-\theta_k)^TH(\theta-\theta_k) = \delta.
$$- 注意，这里无法直接求解这个问题，因为这个解问题的解不是唯一的，比如一维情况就是二次方程，解就有正负两个值，实际上，这里的解是一个以 \(\theta_k\) 为球心的球体（椭球体）构成的集合（一共有 \(2^n\) 个解？其中n是变量的维度）
因此，当 \(\lambda > 0\) 时， \(\theta\) 必须位于约束的边界上。为了确定 \(\theta\) 的具体值，我们需要同时考虑其他KKT条件，尤其是拉格朗日函数的梯度为零的条件：
$$
- g + \lambda H (\theta - \theta_k) = 0
$$从这个方程中，我们可以解出 \(\theta\)：
$$
\theta - \theta_k = \frac{1}{\lambda} H^{-1} g
$$将 \(\theta\) 代入互补松弛条件中可得：
$$
\frac{1}{2} \left( \frac{1}{\lambda} H^{-1} g \right)^T H \left( \frac{1}{\lambda} H^{-1} g \right) = \delta
$$简化后得到：
$$
\begin{align}
\frac{1}{2} \left( \frac{1}{\lambda^2} g^T H^{-1} H H^{-1} g \right) &= \delta \\
\frac{1}{2} \left( \frac{1}{\lambda^2} g^T H^{-1} g \right) &= \delta \\
\frac{1}{2} \frac{g^T H^{-1} g}{\lambda^2} &= \delta \\
\frac{g^T H^{-1} g}{2\delta} &= \lambda^2 \\
\end{align}
$$最终可求得：
$$
\lambda = \sqrt{\frac{g^T H^{-1} g}{2\delta}}.
$$现在我们已经得到了 \(\lambda\) 的表达式，可以将其代回 \(\theta\) 的表达式中：
$$
\begin{align}
\theta - \theta_k &= \frac{1}{\sqrt{\frac{g^T H^{-1} g}{2\delta}}} H^{-1} g = \sqrt{\frac{2\delta}{g^T H^{-1} g}} H^{-1} g
\end{align}
$$最终， \(\theta\) 的值为：
$$
\theta_{k+1} = \theta_k + \sqrt{\frac{2\delta}{g^T H^{-1} g}} H^{-1} g.
$$