RL——TRPO-PPO-目标函数基础推导

本文主要介绍TRPO、PPO相关内容

• 参考链接：
  • 如何看懂TRPO里所有的数学推导细节? - 小小何先生的回答 - 知乎：知乎
  • 从TRPO到PPO（理论分析与数学证明）：博客
  • TRPO公式推导:笔记式推导
  • 信赖域策略优化(Trust Region Policy Optimization, TRPO):PPT式推导
  • RL - Trust Region Policy Optimization (TRPO)

相关概念理解

基础概念

• Q值的定义
  $$ Q_\pi(s_t,a_t) = E_{s_{t+1},a_{t+1},\cdots}[\sum\limits_{l=0}^\infty\gamma^lr(s_{t+l})] $$
• V值的定义
  $$ V_\pi(s_t) = E_{a_t, s_{t+1},\cdots}[\sum \limits_{l=0}^\infty \gamma^lr(s_{t+l})] = E_{a_t\sim \pi(\cdot|s_t)}[Q_\pi(s_t, a_t)] $$
• 优势函数的定义
  $$ A_\pi(s_t,a_t) = Q_\pi(s_t,a_t) - V_\pi(s_t) $$

强化学习的目标定义

$$ \eta(\pi) = E_{s_0, a_0,\ldots}[\sum\limits_{t=0}^{\infty}\gamma^t r(s_t)] $$

• 强化学习的目标是找到一个策略\(\pi\)，能最大化以上目标函数

普通策略梯度法的解法

• 设定策略为\(\pi_\theta\)，则\(\eta(\pi)\)可表达为一个关于策略参数\(\theta\)的函数\(\eta(\theta)\)，此时可通过梯度上升法（策略梯度法）得到参数更新公式：
  $$ \theta_{new} = \theta_{old} + \alpha\nabla_{\theta}\eta(\theta) $$

普通策略梯度法会遇到的问题

• 普通策略梯度法可能存在不稳定问题：
  • 如果公式更新的步长选取过小，训练速度慢
  • 如果步长选取过大，那么会导致策略参数更新步子迈得过大，如果更新过渡，可能导致策略变差，从而导致交互样本变差，差的样本进一步导致策略更差，形成恶性循环。
• TRPO/PPO的解法：选择一个合适的更新策略，或是如何选择一个合适的步长，使得更新过后的策略一定比当前策略更好

TRPO/PPO的核心思想

• TRPO/PPO的核心是使用一个约束优化问题来更新策略，这个约束保证了新策略与旧策略之间的差异不会太大

TRPO/PPO的推导

策略提升的引入

• 回顾强化学习的目标函数
  $$ \eta(\pi) = E_{s_0, a_0,\cdots}[\sum\limits_{t=0}^{\infty}\gamma^t r(s_t)] $$
• 两个策略之间的关系（\(\tilde{\pi}\)是新策略，\(\pi\)是旧策略）
  $$ \eta(\tilde{\pi}) = \eta(\pi) + E_{s_0,a_0,\cdots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty \gamma^t A_{\pi}(s_t,a_t)] $$
  • 证明如下：
    $$
    \begin{aligned}
    E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)] &=E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t(Q_\pi(s_t,a_t)-V_\pi (s_t))]\\
    &=E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t(r(s_t)+\gamma V_\pi (s_{t+1})-V_\pi (s_t))]\\
    &=E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^{t+1} V_\pi (s_{t+1})-\sum\limits_{t=0}^\infty\gamma^{t}V_\pi (s_t) + \sum\limits_{t=0}^\infty\gamma^t r(s_t)]\\
    &=E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=1}^\infty\gamma^{t} V_\pi (s_{t})-\sum\limits_{t=0}^\infty\gamma^{t}V_\pi (s_t) + \sum\limits_{t=0}^\infty\gamma^t r(s_t)]\\
    &=E_{s_0,a_0,\ldots\sim\tilde{\pi}}[-V_\pi(s_0) + \sum\limits_{t=0}^\infty\gamma^t r(s_t)] \quad — \sum\limits_{t=0}^\infty\gamma^{t+1} V_\pi (s_{t+1})\\
    &=-E_{s_0}[V_\pi(s_0)] + E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t r(s_t)]\\
    &=-\eta(\pi) + \eta(\tilde{\pi})
    \end{aligned}
    $$
• 显然，如果我们能找到一个策略\(\tilde{\pi}\)使得\(E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)] \ge 0\)成立，即可确保策略性能（目标函数）是单调递增的
  • 但是，直接求解上式是非常困难的，因为策略\(\tilde{\pi}\)是未知的，无法用这个策略收集数据，下面我们先对这个形式进行变形，再通过其他方法近似求解

策略提升的变形

• 变形如下：
  $$
  \begin{aligned}
  \eta({\tilde{\pi}}) - \eta({\pi}) &= E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty\gamma^t A_\pi(s_t,a_t)] \\
  &= \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_\pi(s,a)
  \end{aligned}
  $$
• 其中有
  $$ \rho_\pi(s) = P(s_0=s) + \gamma P(s_1=s) + \gamma^2 P(s_2=s) + \ldots $$
• 证明如下：
  $$
  \begin{aligned}
  \eta(\tilde{\pi}) - \eta(\pi) &= E_{s_0,a_0,\ldots\sim\tilde{\pi}}[\sum\limits_{t=0}^\infty \gamma^t A_{\pi}(s_t,a_t)]\\
  &=\sum\limits_{t=0}^\infty\sum\limits_sP(s_t=s|\tilde{\pi})\sum\limits_a\tilde{\pi}(a|s)\gamma^tA_\pi(s,a)\\
  &=\sum\limits_s\sum\limits_{t=0}^\infty\gamma^tP(s_t=s|\tilde{\pi})\sum\limits_a\tilde{\pi}(a|s)A_\pi(s,a)\\
  &=\sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_{\pi}(s,a)
  \end{aligned}
  $$
• 对于\(\sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_\pi(s,a)\)来说，我们仍然难以求解，因为策略\(\tilde{pi}\)是未知的，我们无法用这个策略收集数据，所以我们使用旧的策略\(\pi\)来替换新策略\(\tilde{\pi}\)收集数据
• 对于状态部分，当新旧策略特别接近时，他们的状态访问分布会比较接近，我们可以利用MM（Majorization-Minimization）方法构造近似目标函数，可以证明，直接优化目标函数即可优化最优:
  $$
  \begin{aligned}
  \eta(\tilde{\pi}) - \eta(\pi) &= \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_{\pi}(s,a) \\
  &\approx \sum\limits_s\rho_{\pi}(s)\sum\limits_a\tilde{\pi}(a|s) A_{\pi}(s,a) - \frac{4\epsilon \gamma}{(1-\gamma)^2} \cdot D_{\text{KL}}^\max\left(\pi(\cdot|s)|| \tilde{\pi}(\cdot|s)\right)
  \end{aligned}
  $$
  • 其中的一些字符含义见下面的描述：在严格证明下，经过一系列推导后，我们可以得到最终优化问题是：
    $$ \theta = \arg\max_{\theta}\left[ \sum\limits_s\rho_{\pi_{\theta_{\text{old}}}}(s)\sum\limits_a\pi_\theta(a|s) A_{\pi_{\theta_{\text{old}}}}(s,a) - \frac{4\epsilon \gamma}{(1-\gamma)^2} \cdot D_{\text{KL}}^\max\left(\pi_{\theta_{\text{old}}}(\cdot|s)|| \pi_\theta(\cdot|s)\right)\right] $$
    • 其中：
      $$
      \begin{aligned}
      \epsilon &= \max_{s,a} A_\pi(s,a) \quad — s,a是所有可行状态动作，不属于具体分布\\
      D_{\text{KL}}^\max(\pi_{\theta_{\text{old}}}(\cdot|s)|| \pi_\theta(\cdot|s)) &= \max_s D_{\text{KL}}(\pi_{\theta_{\text{old}}}(\cdot|s)|| \pi_\theta(\cdot|s)) \quad — s是所有可行状态
      \end{aligned}
      $$
    • 对应求解伪代码
  • MM方法是一种迭代优化算法，其核心思想是在每一步迭代中构造一个目标函数的下界（或上界），这个下界函数被称为“代理函数”。在每一步迭代中，不是直接优化原始的目标函数，而是优化这个更容易处理的代理函数。通过确保每次迭代都能增加（或减少）目标函数值，最终达到优化目标的目的。
  • 可以通过严格的MM方法数学证明，保证这种状态分布的近似替换是正确的，即提升替换后的目标函数可以提升原始目标函数。在一些书籍或者博客中，这里可以严格证明，使用旧策略采样的状态分布后，新的目标函数是旧的目标函数的一个下界，且两者在就策略\(\pi\)处的值和梯度均相等（也就是说两者的一阶近似\(f(x) \approx f(x_0) + f’(x_0)(x-x_0)\)相同）（详细证明见：从TRPO到PPO（理论分析与数学证明）、如何看懂TRPO里所有的数学推导细节? - 小小何先生的回答 - 知乎）。这个证明较为复杂，有时间可以详细看看。
  • 以上是最优形式，求解比较困难，所以，可以将上面式子的约束进行放松，用KL散度来保证新旧策略之间的差异不会太大即可，之后的TRPO和PPO都是这样做的，接下来的推导（除了重要性采样以外）则都是最优形式的近似
• 基于KL散度限制新旧策略的距离后，进一步地对于动作部分，可以用重要性采样来恢复动作分布，两步总结如下（以下\(\approx\)成立的约束是新旧策略之间的KL散度约束），此外，由于\(\eta(\tilde{\pi})\)的最大化本身与\(\eta(\pi)\)并不直接相关，所以接下来我们只需要关注他们的差值即可：
  $$
  \begin{aligned}
  \eta(\tilde{\pi}) - \eta(\pi) &= \sum\limits_s\rho_{\tilde{\pi}}(s)\sum\limits_a\tilde{\pi}(a|s)A_{\pi}(s,a) \\
  &\approx \sum\limits_s\rho_{\pi}(s)\sum\limits_a\tilde{\pi}(a|s) A_{\pi}(s,a) \quad — 限定新旧策略KL散度后可以约等于\\
  &= \sum\limits_s\rho_{\pi}(s)\sum\limits_a q(a|s)\left[\frac{\tilde{\pi}(a|s)}{q(a|s)} A_{\pi}(s,a)\right] \\
  &= \sum\limits_s\rho_{\pi}(s)\sum\limits_a\pi(a|s)\left[\frac{\tilde{\pi}(a|s)}{\pi(a|s)} A_{\pi}(s,a)\right]
  \end{aligned}
  $$
  • 实际上，从重要性采样的视角来看，动作分布可以是基于任意策略\(q(a|s)\)采样得到的，只是一般相近策略进行重要性采样样本效率更高，所以一般都使用旧策略\(\pi(a|s)\)【PS：重要性采样也需要策略分布相近的，当策略分布之间差距过大时，也不利于重要性采样，可能出现样本采样效率低下或者数据稀疏导致的评估不准确的现象】
• 由于相对\(\eta(\tilde{\pi})\)来说，\(\eta(\pi)\)是常数，所以有最大化\(\eta(\tilde{\pi})\)，等价于最大化\(\sum\limits_s\rho_{\pi}(s)\sum\limits_a\pi(a|s)\left[\frac{\tilde{\pi}(a|s)}{\pi(a|s)} A_{\pi}(s,a)\right]\)即可，考虑到需要保证策略采样到的状态分布不能差距太大，我们的目标可以描述为如下的形式：
  $$
  \begin{aligned}
  \max_{\theta_\text{new}} \quad \sum\limits_s\rho_{\pi_{\theta_\text{old}}}(s)&\sum\limits_a\pi_{\theta_\text{old}}(a|s)\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 &D_{\text{KL}}(\pi_{\theta_\text{old}}, \pi_{\theta_\text{new}}) \le \delta
  \end{aligned}
  $$
• 一般也会写成期望的等价形式：
  $$
  \begin{aligned}
  \max_{\theta_\text{new}} \quad &E_{s \sim \rho_{\pi_{\theta_\text{old}}}(s), a \sim \pi_{\theta_\text{old}}(a|s)}\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}}}(s)} \left[D_{\text{KL}}(\pi_{\theta_\text{old}}, \pi_{\theta_\text{new}})\right] \le \delta
  \end{aligned}
  $$
• 或者进一步简写成：
  $$
  \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}
  $$
  • 目标是原始目标等价的期望形式
  • 约束则考虑了计算KL散度时在旧策略采样的状态分布上进行验证
• 至此，目标函数中采样策略（包括状态和动作）变成了之前的旧策略，总结一下有：
  • 状态分布替换旧策略是基于新旧策略的差异不大来近似得到的，这个改动是MM（Majorization-Minimization）方法的思想，构造一个可以严格通过MM方法证明的近似目标函数\(\sum\limits_s\rho_{\pi_{\theta_{\text{old}}}}(s)\sum\limits_a\pi_\theta(a|s) A_{\pi_{\theta_{\text{old}}}}(s,a) - \frac{4\epsilon \gamma}{(1-\gamma)^2} \cdot D_{\text{KL}}^\max\left(\pi_{\theta_{\text{old}}}(\cdot|s)|| \pi_\theta(\cdot|s)\right)\)，这个目标函数的优化没有信赖域的概念，所以不是Trust Region方法
  • 在构造近似目标函数后，进一步简化目标函数的等价形式为KL散度约束下的更简洁形式，此时算是Trust Region方法
  • 动作分布替换旧策略是基于重要性采样实现的

TRPO简单理解

TRPO名字的由来

• TRPO（Trust Region Policy Optimization）的名字来源于其核心方法——信任域（Trust Region）优化。
• TRPO同时包含了Trust Region算法和MM（Majorization-Minimization）算法的思想：
  • MM算法：推导过程中，在对策略提升部分进行转换时，使用的是MM算法的思想，构造了一个近似目标函数，同时证明了该近似目标函数与原始目标函数的关系（两者的梯度和值在当前策略处相等，且近似目标函数处处小于等于原始目标函数）；
  • Trust Region算法：TRPO方法在每次迭代需要在KL散度约束内做更新优化，并且构造了一个KL散度约束的优化问题来近似求解，属于Trust Region方法的思想；
• 补充问题：MM算法、Trust Region算法、近端梯度下降算法，这三种方法的区别和关系是什么？
  • MM算法 vs Trust Region算法：
    • 相同点：两者都是迭代优化方法，每次迭代都通过解决一个较简单的优化问题来逼近原始问题的解。
    • 异同点：
      • 构造方式: MM算法通过构造一个上界函数来近似目标函数，而Trust Region算法通过在一个信赖域内构造一个近似模型来优化目标函数。
      • 信赖域: Trust Region算法明确使用信赖域来限制每次迭代的步长，而MM算法没有这种信赖域的概念。
      • 适用范围: MM算法更适合处理凸优化问题，而Trust Region算法在处理非凸优化问题和大规模优化问题时表现更优。
  • 近端梯度下降：近端梯度下降方法（Proximal Gradient Descent, PGD）是一种用于优化非光滑（nonsmooth）和复合目标函数的优化算法。它结合了梯度下降法和近端算子（proximal operator），可以有效处理带有非光滑正则化项的优化问题。该方法PPO和TRPO都没有用到

TRPO解法思路

• 近似求解上述式子，用一阶梯度近似目标，用二阶梯度近似约束，从而得到一个关于参数最优化问题
• 基于共轭梯度法可以求解该问题

GAE

• GAE（Generalized Advantage Estimation，广义优势估计）是一种用于估计策略梯度算法中优势函数的方法。它旨在解决标准优势函数估计方法的高方差问题，通过引入一个可调参数来平衡偏差与方差之间的关系。
• 详情可参考RL——GAE

PPO简单理解

PPO名字的由来

• PPO（Proximal Policy Optimization）名字中的“Proximal”是指“近端”约束，表示确保新策略不会偏离旧策略太远，从而保证策略更新的稳定性和有效性。跟近端梯度下降（Proximal Gradient Descent）方法没有直接关系。“Proximal”是“最接近的”或“邻近的”。在不同的上下文中，“proximal”可以有不同的具体含义，但其核心概念通常与“接近”或“邻近”有关。
• 由于PPO的优化目标推导过程与TRPO相同，都用到了近似目标函数，所以推导过程中也用到了MM的思想和Trust Region的思想，但在解决问题时仅用到了近端（“Proximal”）约束，即每次迭代策略不要更新太多（没有严格遵循Trust Region推导得到的结果），严格来说不属于Trust Region方法

PPO-Penalty

• 又名PPO-惩罚
  \begin{aligned}
  \max_{\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_{\theta_{\text{old}}}(s,a) - \beta D_{KL}(\pi_{\theta_{\text{old}}}(\cdot|s), \pi_\theta(\cdot|s))\right]
  \end{aligned}

PPO-Clip

• 又名PPO截断
  \begin{aligned}
  \max_\theta&\ \ E_{s\sim \rho_{\theta_{\text{old}}},a\sim q(a|s)}\min\left(\frac{\pi_\theta(a|s)}{q(a|s)}A_{\theta_{\text{old}}}(s,a), clip\left(\frac{\pi_\theta(a|s)}{q(a|s)}, 1-\epsilon, 1+\epsilon\right)A_{\theta_{\text{old}}}(a|s)\right)
  \end{aligned}
• 理论上，以上采样分布可以是任意分布，实际上使用原始策略效果更好（样本利用率也更高）
  \begin{aligned}
  \max_\theta&\ \ E_{s \sim \rho_{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}}\min\left(\frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)}A_{\theta_{\text{old}}}(s,a), clip\left(\frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)}, 1-\epsilon, 1+\epsilon\right)A_{\theta_{\text{old}}}(a|s)\right)
  \end{aligned}