RL——TRPO

TRPO

TRPO目标

$$
\begin{aligned}
\max_{\theta_\text{new}} \quad &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 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}
  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}) \\
  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}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] $$
  • \(H\)为海森矩阵（Hessian Matrix，又译作黑塞矩阵）：
    $$ H = H[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}
      $$
• 于是得到进一步优化的目标
  $$
  \begin{aligned}
  \theta_{k+1} = \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\)的解可通过共轭梯度法来求解，方法参见ML——共轭梯度法和最速下降法

TRPO更新步长

• 当前TRPO求解方案采用了泰勒展开的1阶近似和2阶近似，不是精准求解，新参数不一定能满足KL散度约束限制，所以在更新时，我们可以再进行一次步长搜索，使得更新后的新参数满足KL散度限制，且能够提升目标函数
• 线性搜索的具体规则，在\((0,1)\)区间内抽取K个点\(\{\alpha^i\}_{i=1}^K\)

附录：最优化问题求解的详细推导

• 给定最优化问题
  $$
  \begin{aligned}
  \theta_{k+1} = \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矩阵是对称的），\(\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.
  $$