[RL] TRPO 和 PPO

准备写TRPO和PPO的代码. 数学的推导非常的多, 即使不深究原理也有难度

begin

对于两个策略, 我们需要衡量两个两个策略的"优劣",
即, 在已有 $\pi, \pi'$以及 $\theta, \theta'$的情况下, 怎么样得到一个

$$J(\theta) = E_{s_0}[V^{\pi_\theta}(s_0)]$$

使得我们可以根据目标函数的指导, 用于作为优化目标. 从而将问题转换为一个最优化问题.

推导过程:
先根据定义得到下面的等式

$$J(\theta') - J(\theta) = E_{\pi_\theta'}[\sum_{t = 0}^{\infty} y^t [ r(s_t, a_t) + \gamma V^{\pi_\theta}(s_{t+1}) - V^{\pi_\theta}(s_t)] ]$$

其中下标的$\pi_{\theta'}$ 表示 $s_t, a_t$服从 $\pi_{\theta'}$ 导出的分布.

将时序差分残差定义为优势函数A

$$J(\theta') - J(\theta) = E_{\pi_\theta'}[\sum_{t = 0}^{\infty} y^t A^{\pi_\theta}(s_t, a_t) ]$$

于是进一步得到

$$J(\theta') - J(\theta) = \frac{1}{1 - \gamma} E_{s\sim v^{\pi_\theta'}}E_{a \sim \pi_\theta'(\cdot | s)} [A^{\pi_\theta}(s_t, a_t) ]$$

其中用到了状态访问分布的定义:

$$v^{\pi_\theta}(s) = (1 - \gamma) \sum_{t = 0}^{\infty} \gamma^t P_{t}^{\pi}(s)$$

忽略状态访问分布的变化

由于该式很难直接求解, 因此我们忽略两个策略状态访问分布的变化, 直接有旧策略的状态分布, 定义替代的优化目标

$$L_{\theta} (\theta') = J(\theta) + \frac{1}{1 - \gamma} E_{s\sim v^{\pi_\theta}} E_{a \sim \pi_\theta'(\cdot | s)} [A^{\pi_\theta}(s_t, a_t) ]$$

下面, 我们用重要性采样对动作分布进行处理

$$L_{\theta} (\theta') = J(\theta) + \frac{1}{1 - \gamma} E_{s\sim v^{\pi_\theta}}E_{a \sim \pi_\theta(\cdot | s)} [\frac{\pi_\theta'(a|s)}{\pi_\theta(a|s)} A^{\pi_\theta}(s_t, a_t) ]$$

为了保证两个策略足够接近, 我们用KL散度来衡量策略之间的距离, 于是得到了一个整体的优化公式

$$\max_{\theta'} L_{\theta} (\theta')$$

$$s.t. E_{s\sim v^{\pi_{\theta_k}}} [D_{KL} (\pi_{\theta_k} (\cdot|s), \pi_{\theta'}(\cdot|s))] \leq \delta$$

近似求解优化问题

对目标函数与约束进行一阶和二阶泰勒展开

展开得到

$$\max_{\theta'} g^T(\theta' - \theta_k)$$

$$s.t. \frac{1}{2} (\theta' - \theta_k)^TH(\theta' - \theta_k) \leq \delta$$

其中g代表目标函数的梯度, H代表策略间平均KL距离的黑塞矩阵 (Hessian matrix)

于是根据KKT条件得到问题的解

$$\theta_{k+1} = \theta_k + \sqrt{\frac{2\delta}{g^T H^{-1} g}} H^{-1} g$$

KL散度类似策略之间的距离, 用于度量策略之间的差异

---

KL 散度（KL Divergence）

KL 散度（Kullback-Leibler Divergence）是一种衡量两个概率分布之间差异的非对称度量。给定两个概率分布 $P$ 和 $Q$，KL 散度 $D_{KL}(P \parallel Q)$ 描述了通过 $Q$ 来近似 $P$ 所造成的信息损失。

其数学公式为：

$$D_{KL}(P \parallel Q) = \sum_{x} P(x) \log \frac{P(x)}{Q(x)}$$

对于连续分布，则变为：

$$D_{KL}(P \parallel Q) = \int p(x) \log \frac{p(x)}{q(x)} \, dx$$

KL 散度在强化学习、机器学习等领域中常用来度量策略之间的差异，尤其是在策略优化（如自然梯度下降）中，KL 散度常常用于控制策略更新的步长，避免过大更新导致的性能不稳定。

黑塞矩阵（Hessian Matrix）

黑塞矩阵是一个二阶导数矩阵，用来描述一个多元函数在某点的局部曲率。对于一个标量函数 f(θ)，其黑塞矩阵 $H$ 的元素是该函数关于参数 θ 的二阶偏导数，即：

$$H_{ij} = \frac{\partial^2 f(\theta)}{\partial \theta_i \partial \theta_j}$$

黑塞矩阵反映了函数在某一点的变化速度以及弯曲程度。它常用于优化问题中，帮助分析目标函数的曲率，以便选择合适的优化步长。

---

采用共轭梯度方法避免求逆

为了避免求解 $H^{-1}$(它通常非常大), 我们转而求解 $x = H^{-1} g$, 并用 $x$ 来表示参数更新方向.

$$\theta_{k+1} = \theta_k + \sqrt{\frac{2\delta}{ x^T H x}} x$$

因此, 我们只需要使用共轭梯度法解 $Hx = g$即可 (H为对称正定矩阵).

---

共轭梯度法（Conjugate Gradient Method）

共轭梯度法是一种用于求解大规模线性方程组 ($Ax = b$) 的迭代方法，尤其适用于稀疏或大规模的对称正定矩阵 ($A$)。它的基本思想是通过一系列“共轭”方向的线性组合来逐步逼近方程的解。与传统的梯度下降法不同，共轭梯度法在每一步中都会选择一个新的搜索方向，该方向与前几步的搜索方向“正交”或“共轭”，从而加速了收敛过程。

基本原理

共轭梯度法的目标是通过迭代优化问题中的目标函数 ( $f(x) = \frac{1}{2} x^T A x - b^T x$ ) 来找到最优解。这个目标函数是一个二次函数，且假设 ($A$) 是对称正定矩阵。共轭梯度法使用以下步骤来更新解 ($x$)：

1. 初始化：选择一个初始点 ($x_0$)，计算初始梯度 ($r_0 = b - A x_0$)（即残差），并设置初始方向为 ($p_0 = r_0$)。

2. 迭代更新：
   对于每一步 ($k$)：

   • 计算步长 ($\alpha_k = \frac{r_k^T r_k}{p_k^T A p_k}$)，这个步长决定了沿着当前方向 (p_k) 的更新量。
   • 更新解：($x_{k+1} = x_k + \alpha_k p_k$)
   • 更新残差：($r_{k+1} = r_k - \alpha_k A p_k$)
   • 计算新的搜索方向：($\beta_k = \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k}$)
   • 更新方向：($p_{k+1} = r_{k+1} + \beta_k p_k$)

3. 停止条件：
   共轭梯度法通常会在残差 ($r_k$) 足够小，或者达到预设的迭代次数时停止。

共轭梯度法的优点

• 不需要显式存储矩阵 (A)：对于大规模问题，直接存储矩阵 ($A$) 是不切实际的。而共轭梯度法仅需要 ($A$) 的矩阵-向量乘法（即 ($A p_k$)），这使得它在处理大规模稀疏矩阵时非常高效。

• 快速收敛：对于正定矩阵，特别是当矩阵条件数较小的时候，共轭梯度法通常能比标准的梯度下降法更快收敛。理论上，它最多需要 ($n$) 次迭代（其中 ($n$) 是矩阵的维数）就能得到精确解。

• 内存需求较少：相比于高阶优化方法（如牛顿法），共轭梯度法只需要存储当前解、残差和方向等少量信息，因此内存消耗较小。

共轭梯度法的缺点

• 适用于对称正定矩阵：共轭梯度法要求矩阵 ($A$) 是对称正定的，这意味着它并不适用于所有类型的矩阵。对于非对称矩阵，可能需要先进行预处理或转换。

• 无法保证全局最优：虽然共轭梯度法在大多数情况下表现良好，但它的收敛性不能保证在所有问题中都能找到全局最优解。特别是在非线性优化问题中，可能需要更多的技术来控制和改善收敛性。

共轭梯度法的应用

共轭梯度法广泛应用于以下领域：

1. 求解线性方程组：尤其是大规模稀疏方程组，在科学计算、工程计算、计算机图形学、物理模拟等领域中非常常见。

2. 优化问题：在机器学习中，尤其是在深度学习的训练过程中，共轭梯度法有时被用来优化某些目标函数（例如二次损失函数）。

3. 物理模拟：在有限元分析、流体力学等应用中，很多线性方程组是由离散化的偏微分方程构成的，这些方程常常需要通过共轭梯度法来求解。

4. 图像处理和信号处理：在图像去噪、图像重建等问题中，常需要求解大规模的线性方程组，共轭梯度法常常被用来求解这些问题。

共轭梯度法的改进

共轭梯度法在许多情况下可以通过一些技巧进行改进：

• 预条件共轭梯度法（Preconditioned Conjugate Gradient, PCG）：预处理步骤可以通过引入预条件矩阵 ($M$) 来加速共轭梯度法的收敛性，特别是在条件数较大的问题中。预条件矩阵 ($M$) 使得 ($A$) 的性质在计算中变得更好，从而加速收敛。

• 共轭梯度法的变种：针对特定问题或特定矩阵，可能会有针对性的变种算法，优化收敛速度或内存消耗。

总结

共轭梯度法是一种高效的求解线性方程组的迭代方法，特别适用于大规模的稀疏系统。它通过选择共轭方向和二阶信息来加速收敛，与传统的梯度下降法相比具有显著的优点，尤其是在计算复杂度和内存消耗上。虽然它的应用受到矩阵对称正定的限制，但在许多实际问题中表现良好，并且能够通过预处理和改进进一步提高性能。

---

同样, 为了避免 $H$的出现, 我们只计算和存储 $Hx$向量. 容易验证, 这可以通过 先计算 “一阶导数 乘 v”, 在对此标量求导, 得到需要的向量. (容易验证此相等关系)

所以散度的梯度怎么求呢?

采用线性搜索方法确保近似精度

• 找到一个系数 $\alpha ^i$, 使得更新后的参数确实能够满足要求(在做泰勒展开近似前的要求)
• 因此, 做泰勒展开并求解的过程类似于求出了更新方向
• 线性搜索的步骤就在确定步长. $\alpha$ 为超参数

广义优势估计 GAE

广义优势估计（Generalized Advantage Estimation, GAE）

广义优势估计（GAE）是一种在强化学习中用于估计优势函数（Advantage Function）的方法，旨在平衡偏差和方差，以提高策略梯度方法的稳定性和效率。它由 John Schulman 等人在 2015 年提出，特别是在 Proximal Policy Optimization（PPO）算法中得到了广泛应用。

GAE 是对传统的优势函数估计方法的一个改进，它通过引入一个超参数 (\lambda) 来控制估计的平滑程度，从而在偏差（bias）和方差（variance）之间取得更好的平衡。GAE 的核心思想是结合 蒙特卡洛估计 和 时序差分（TD）学习 的方法，通过加权平均来减少估计的方差，同时避免增加过多的偏差。

1. 背景知识

为了理解 GAE，首先需要了解 优势函数（Advantage Function） 和 时序差分（TD）误差。

• 价值函数（Value Function） ($V(s_t)$)：表示从状态 ($s_t$) 出发，未来所有奖励的期望值。
• Q 函数（Q-function） ($Q(s_t, a_t)$)：表示从状态 ($s_t$) 开始，采取动作 ($a_t$) 后，未来所有奖励的期望值。
• 优势函数（Advantage Function） ($A(s_t, a_t$))：表示某一状态-动作对相对于平均策略的优势。它的定义为：
  [

$$A(s_t, a_t) = Q(s_t, a_t) - V(s_t)$$

]

在强化学习的策略梯度方法中，优势函数是用于权衡动作 ($a_t$) 的好坏程度，它帮助我们调整策略的参数。

传统的优势估计

传统的优势估计方法包括 蒙特卡洛方法 和 时序差分方法（TD方法）：

• 蒙特卡洛方法：使用完整的回报来估计优势函数，通常会引入较大的方差，尤其是在长时间步的情况下。
• 时序差分（TD）方法：通过迭代更新状态价值估计，计算每个状态的 TD误差 来估计优势，方差较小，但可能引入偏差。

2. GAE的公式

GAE 结合了这两种方法，通过引入一个 折扣因子 ($\gamma$) 和 GAE超参数 ($\lambda$) 来控制时序差分的误差和回报的加权平均。

GAE 的优势估计公式为：
[

$$\hat{A}_t^{\lambda} = \sum_{l=0}^{\infty} (\gamma\lambda)^l \delta_t^{(l)}$$

]
其中：

• ($\delta_t^{(l)}$) 是 TD误差，表示当前估计和实际回报之间的差异：
  [

$$\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$$

]
这是计算每个时间步的误差。

• ( $\gamma$ ) 是 折扣因子，控制未来奖励的影响程度。
• ( $\lambda$ ) 是 GAE超参数，控制估计的平滑程度。如果 ($\lambda = 0$)，则只有TD方法的贡献；如果 ($\lambda = 1$)，则使用完整的蒙特卡洛估计。

3. GAE的优点

• 减少方差，平衡偏差：GAE 通过权衡折扣因子 ($\gamma$) 和超参数 ($\lambda$) 来平衡偏差和方差。较小的 ($\lambda$) 值会减少方差，但可能引入较大的偏差；较大的 ($\lambda$) 值会增加估计的方差，但减少偏差。

• 适用于大规模强化学习：在大规模强化学习任务中，GAE能够有效地减少方差，因此能提高策略更新的稳定性，避免过度波动。

• 高效的估计：GAE 使得策略梯度方法能够更有效地利用多个时间步的数据，特别是在高维环境下，GAE 显著提高了收敛速度。

4. GAE的实现

在具体实现中，GAE 常常用于 优势函数估计，并结合 策略梯度方法（如 PPO）来优化策略。以下是 GAE 在强化学习中的常见步骤：

1. 计算时序差分误差：
   对于每个时间步 ($t$)，计算 TD误差 ($\delta_t$)：
   [

$$\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$$

]

2. 计算GAE优势估计：
   对每个时间步 ($t$)，计算 GAE 优势估计 ($\hat{A}_t^{\lambda}$)：
   [

$$\hat{A}_t^{\lambda} = \delta_t + (\gamma\lambda) \delta_{t+1} + (\gamma\lambda)^2 \delta_{t+2} + \dots$$

]

3. 策略优化：
   使用优势估计值 ($\hat{A}_t^{\lambda}$) 来更新策略参数，以最大化期望回报。

5. 超参数 ($\lambda$)

• ($\lambda = 0$)：仅使用TD方法进行优势估计，完全依赖于当前值函数的估计。虽然收敛较快，但方差较大。
• ($\lambda = 1$)：使用完全的蒙特卡洛回报进行优势估计，能够完全消除偏差，但方差较大。
• 中间值的 ($\lambda$)：通常选择在 ($0 < \lambda < 1$) 之间的某个值，以平衡偏差和方差，通常使用 0.9 到 0.95 之间的值。

6. GAE在PPO中的应用

在 Proximal Policy Optimization (PPO) 中，GAE 用于计算优势函数，从而减少策略梯度的方差，提高训练的稳定性。PPO 的目标是通过限制策略更新的幅度（通过剪切的目标函数）来避免策略更新过大，并确保策略优化的稳定性。

总结

广义优势估计（GAE）是一种非常有效的策略梯度优化技术，它通过平衡偏差和方差来改进优势函数的估计。在强化学习中，GAE 能够提高训练的效率和稳定性，特别是在策略优化算法如 PPO 中，能够加速收敛并降低训练过程中的波动性。GAE 的核心优势在于它通过引入超参数 ($\lambda$)，灵活地控制估计的平滑程度，从而在多种环境中表现出色。

PPO

• 不采用泰勒展开近似、共轭梯度、线性搜索等方法直接求解
• 而是用相对简单的方式进行求解, PPO-惩罚和PPO-截断
• 从而能够直接计算出loss, 并进行无约束的优化求解 (梯度下降)