必备知识

重要性采样

重要性采样

问题定义

• 函数$f(x)$，需要从分布$p(x)$中采样，来计算期望值；但现在很难从$p(x)$中采样

方法

• 从另一个容易采样的分布$q(x)$中采样，间接达到从$p(x)$中采样的效果

$$\begin{array}{ll}{E}_{x\sim p(x)}[f(x)]& =\int p(x)f(x)\mathrm{d}x\\ & =\int q(x)\cdot \frac{p(x)}{q(x)}f(x)\mathrm{d}x\\ & =E_{x\sim q(x)}[\frac{p(x)}{q(x)}f(x)]\end{array}$$$$E_{x\sim p}[f(x)]=E_{x\sim q}[\frac{p(x)}{q(x)}f(x)]=\frac{1}{N}\sum _i\frac{p(x_i)}{q(x_i)}f(x_i)$$

• $\frac{p(x)}{q(x)}$：重要性权重，用来修正采样的偏差，即两个分布直接的差异。
• 重要性采样也是一种特殊的MC采样，允许从简单分布采样，避免直接从困难分布采样的问题。

缺点

• $q(x)$必须尽可能接近$p(x)$，$q$越接近$p$，方差越小；否则，尽管期望相同，但方差会很大
• 如果采样次数不够多，$E_{x\sim p}[f(x)]$ 和 $E_{x\sim q}[\frac{p(x)}{q(x)}f(x)]$ 会有很大的差异。

主流方法

TRPO

Trust region policy optimization

背景

TRPO 提出背景

Actor-Critic 缺点

• 虽然简单直观，但训练不不稳定
• 目标：找到${\theta }^{\ast }=\arg \underset{\theta }{max}J(\theta )$，沿${\mathrm{\nabla }}_{\theta }J(\theta )$方向迭代更新策略参数

$$J(\theta )=E_{s_0}[V^{{\pi }_{\theta }}(s_0)]=E_{{\pi }_{\theta }}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot r(s_t,a_t)]$$

• 缺点：沿策略梯度更新参数，可能由于步长太长，策略突然显著变差，从而影响训练效果

策略目标

TRPO 策略目标

核心目标

• 期望借助当前$\theta$找到一个更优${\theta }^{\prime }$，使得$J({\theta }^{\prime })\ge J(\theta )$
• 只要找到一个新策略，使$E_{s_t\sim v^{{\pi }_{{\theta }^{\prime }}}}{E}_{a\sim {\pi }_{{\theta }^{\prime }}(\cdot \mid s_t)}[A^{{\pi }_{\theta }}(s_t,a_t)]\ge 0$，就能保证策略性能单调递增

$$\begin{array}{ll}J({\theta }^{\prime })-J(\theta )& =\frac{1}{1-\lambda }{E}_{s_t\sim v^{{\pi }_{{\theta }^{\prime }}}}{E}_{a\sim {\pi }_{{\theta }^{\prime }}(\cdot \mid s_t)}[A^{{\pi }_{\theta }}(s_t,a_t)]\end{array}$$$$A^{{\pi }_{\theta }}(s_t,a_t)=r(s_t,a_t)+\gamma V^{{\pi }_{\theta }}(s_{t+1})-V^{{\pi }_{\theta }}(s_t)$$

难点

• 直接求解该式非常困难，${\pi }_{{\theta }^{\prime }}$是我们需要求解的策略，又要用它收集样本。
• 把所有可能的新策略拿来收集样本，又用它来判断条件，显然是不现实的。

目标优化

• 对状态访问分布做了相应处理，忽略两个策略的状态访问分布，直接采用旧策略${\pi }_{\theta }$的状态分布

$$L_{\theta }({\theta }^{\prime })=J(\theta )+\frac{1}{1-\lambda }{E}_{s_t\sim v^{{\pi }_{\theta }}}{E}_{a\sim {\pi }_{{\theta }^{\prime }}(\cdot \mid s_t)}[A^{{\pi }_{\theta }}(s_t,a_t)]$$

• 新旧策略接近时，状态访问分布变化很小，近似是合理的，动作仍然用新策略采样得到，用重要性采样做处理。
• 这样就能基于旧策略${\pi }_{\theta }$采样出的数据，来估计并优化新策略${\pi }_{{\theta }^{\prime }}$

$$L_{\theta }({\theta }^{\prime })=J(\theta )+E_{s_t\sim v^{{\pi }_{\theta }}}{E}_{a\sim {\pi }_{{\theta }^{\prime }}(\cdot \mid s_t)}[\frac{{\pi }_{{\theta }^{\prime }}(a\mid s)}{{\pi }_{\theta }(a\mid s)}\cdot A^{{\pi }_{\theta }}(s_t,a_t)]$$$$$$

KL 约束

• 增加KL约束，保证新旧策略足够近

$$\begin{array}{ll}& \underset{{\theta }^{\prime }}{max}{L}_{\theta }({\theta }^{\prime }),\\ & \mathrm{s}.\mathrm{t}.E_{s_t\sim v^{{\pi }_{{\theta }_k}}}[D_{KL}({\pi }_{{\theta }_k}(\cdot \mid s),{\pi }_{\theta }(\cdot \mid s))]\le \delta \end{array}$$$$\begin{array}{ll}& \underset{{\theta }^{\prime }}{max}{L}_{\theta }({\theta }^{\prime }),\\ & \mathrm{s}.\mathrm{t}.E_{s_t\sim v^{{\pi }_{{\theta }_k}}}[D_{KL}({\pi }_{{\theta }_k}(\cdot \mid s),{\pi }_{\theta }(\cdot \mid s))]\le \delta \end{array}$$

• 信任区域：不等式约束定义了策略空间中的一个KL球。
• 在信任区域中
  • 学习策略和环境交互的状态分布，与上一轮策略最后采样的状态分布一致
  • 可以基于一步行动的重要性采样使当前学习策略稳定提升

信任区域示意图：左侧无信任区域，梯度更新可能导致性能骤降；右侧有信任区域，每次梯度更新都能带来稳定提升。

目标推导过程

$J(\theta )$ 另一种形式

$$\begin{array}{ll}J(\theta )& =E_{s_0}[V^{{\pi }_{\theta }}(s_0)]\\ & =E_{{\pi }_{{\theta }^{\prime }}}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot V^{{\pi }_{\theta }}(s_t)-\sum _{t=1}^{\mathrm{\infty }}{\gamma }^t\cdot V^{{\pi }_{\theta }}(s_t)]\\ & =-E_{{\pi }_{{\theta }^{\prime }}}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot (\gamma V^{{\pi }_{\theta }}(s_{t+1})-V^{{\pi }_{\theta }}(s_t))]\end{array}$$

$J({\theta }^{\prime })-J(\theta )$推导过程

$$\begin{array}{ll}J({\theta }^{\prime })-J(\theta )& =E_{s_0}[V^{{\pi }_{{\theta }^{\prime }}}(s_0)]-E_{s_0}[V^{{\pi }_{\theta }}(s_0)]\\ & =E_{{\pi }_{{\theta }^{\prime }}}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot r(s_t,a_t)]+E_{{\pi }_{{\theta }^{\prime }}}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot (\gamma V^{{\pi }_{\theta }}(s_{t+1})-V^{{\pi }_{\theta }}(s_t))]\\ & =E_{{\pi }_{{\theta }^{\prime }}}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot (r(s_t,a_t)+\gamma V^{{\pi }_{\theta }}(s_{t+1})-V^{{\pi }_{\theta }}(s_t))]\\ & =E_{{\pi }_{{\theta }^{\prime }}}[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot A^{{\pi }_{\theta }}(s_t,a_t)]\\ & =\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t\cdot E_{s_t\sim v^{{\pi }_{{\theta }^{\prime }}}}{E}_{a\sim {\pi }_{{\theta }^{\prime }}(\cdot \mid s_t)}[A^{{\pi }_{\theta }}(s_t,a_t)]\\ & =\frac{1}{1-\lambda }{E}_{s_t\sim v^{{\pi }_{{\theta }^{\prime }}}}{E}_{a\sim {\pi }_{{\theta }^{\prime }}(\cdot \mid s_t)}[A^{{\pi }_{\theta }}(s_t,a_t)]\end{array}$$

广义优势估计

GAE 笔记

GAE

• 对不同TD步数的优势估计进行指数加权平均，平衡方差和偏差

$${\delta }_{t+l}=r_{t+l}+\gamma V(s_{t+l+1})-V(s_{t+l})$$$$A_t^{GAE(\gamma ,\lambda )}(s_t,a_t)=\sum _{l=0}^{\mathrm{\infty }}(\gamma \lambda {)}^l\cdot {\delta }_{t+l}$$$$A_t^{GAE(\gamma ,\lambda )}(s_t,a_t)=\sum _{l=0}^{\mathrm{\infty }}(\gamma \lambda {)}^l\cdot (r_{t+l}+\gamma V(s_{t+l+1})-V(s_{t+l}))$$

def compute_advantage(gamma, lmbda, td_delta):
    td_delta = td_delta.detach().numpy()
    advantage_list = []
    advantage = 0.0
    for delta in td_delta[::-1]:
        advantage = gamma * lmbda * advantage + delta
        advantage_list.append(advantage)
    advantage_list.reverse()
    return torch.tensor(advantage_list, dtype=torch.float)

PPO

背景

PPO 背景

TRPO的问题

• 计算复杂， 每步更新运算量非常大

PPO

• 基于TRPO的思想，但实现更简单，能学的一样好、甚至更快。

算法流程

笔记

PPO算法流程

• 初始策略参数${\theta }^0$
• 每一次迭代，用前面训练的演员${\theta }^k$ 和环境交互，采样大量$(s,a)$对
• 根据${\theta }^k$交互结果，估计$A^{{\pi }_{{\theta }^k}}(s_t,a_t)$
• 采样到这组数据后，最大化目标函数，可以让$\theta$更新很多次，
• 由于有了重要性采样，${\theta }^k$ 和 $\theta$ 有差异也没关系，可以训练$\theta$

$$J_{PPO}^{{\theta }^k}(\theta )=J^{{\theta }^k}(\theta )-\beta \cdot \mathrm{KL}(\theta ,{\theta }^k)$$

重要性采样

PPO 重要性采样

策略梯度

• 交互策略${\pi }_{{\theta }^{\prime }}$：与环境交互，采集大量数据来训练${\pi }_{\theta }$
• 学习策略${\pi }_{\theta }$：要训练学习的网络，${\pi }_{\theta }$更新多次后，再去更新${\pi }_{{\theta }^{\prime }}$

$$\mathrm{\nabla }J(\theta )=E_{\tau \sim p_{{\theta }^{\prime }}(\tau )}[\frac{p_{\theta }(\tau )}{p_{{\theta }^{\prime }}(\tau )}R(\tau )\mathrm{\nabla }\log p_{\theta }(\tau )]$$

优势策略梯度

• 优势作权重

$$\mathrm{\nabla }J(\theta )=E_{(s_t,a_t)\sim {\pi }_{\theta }}[\underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{权}\mathrm{重}}{\underbrace{A^{{\pi }_{\theta }}(s_t,a_t)}}\cdot \underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{梯}\mathrm{度}}{\underbrace{\mathrm{\nabla }\log p_{\theta }(a_t\mid s_t)}}]$$

• 引入重要性采样

$$\mathrm{\nabla }J(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\underset{\mathrm{重}\mathrm{要}\mathrm{性}\mathrm{权}\mathrm{重}}{\underbrace{\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}}}\cdot \underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{权}\mathrm{重}}{\underbrace{A^{{\pi }_{\theta }}(s_t,a_t)}}\cdot \underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{梯}\mathrm{度}}{\underbrace{\mathrm{\nabla }\log p_{\theta }(a_t\mid s_t)}}]$$

• 优势应是演员和环境交互时计算出来的

$$\mathrm{\nabla }J(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\underset{\mathrm{重}\mathrm{要}\mathrm{性}\mathrm{权}\mathrm{重}}{\underbrace{\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}}}\cdot \underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{权}\mathrm{重}}{\underbrace{A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t)}}\cdot \underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{梯}\mathrm{度}}{\underbrace{\mathrm{\nabla }\log p_{\theta }(a_t\mid s_t)}}]$$

目标函数

$$J^{{\theta }^{\prime }}(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\underset{\mathrm{重}\mathrm{要}\mathrm{性}\mathrm{权}\mathrm{重}}{\underbrace{\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}}}\cdot \underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{权}\mathrm{重}}{\underbrace{A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t)}}]$$$$J^{{\theta }^{\prime }}(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\underset{\mathrm{重}\mathrm{要}\mathrm{性}\mathrm{权}\mathrm{重}}{\underbrace{\frac{\mathrm{\nabla }{p}_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}}}\cdot \underset{\mathrm{动}\mathrm{作}a\mathrm{的}\mathrm{权}\mathrm{重}}{\underbrace{A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t)}}]$$$$$$

优点

• 可通过重要性采样把同策略换成异策略
• 核心还是TRPO里的求解

目标函数

信息

PPO 目标函数

$$J_{PPO}^{{\theta }^{\prime }}(\theta )=J^{{\theta }^{\prime }}(\theta )-\beta \cdot KL(\theta ,{\theta }^{\prime })$$$$J^{{\theta }^{\prime }}(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}\cdot A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t)]$$$$J_{PPO}^{{\theta }^{\prime }}(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}\cdot A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t)]-\beta \cdot \mathrm{KL}(\theta ,{\theta }^{\prime })$$

TRPO 目标函数

$$J_{TRPO}^{{\theta }^{\prime }}(\theta )=E_{(s_t,a_t)\sim {\pi }_{{\theta }^{\prime }}}[\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}\cdot A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t)],\mathrm{KL}(\theta ,{\theta }^{\prime })\le \delta$$

GAE

GAE 笔记

GAE

• 对不同步数的TD优势估计进行指数加权平均，平衡方差和偏差

$${\delta }_{t+l}=r_{t+l}+\gamma V(s_{t+l+1})-V(s_{t+l})$$$$A_t^{GAE(\gamma ,\lambda )}(s_t,a_t)=\sum _{l=0}^{\mathrm{\infty }}(\gamma \lambda {)}^l\cdot {\delta }_{t+l}$$$$A_t^{GAE(\gamma ,\lambda )}(s_t,a_t)=\sum _{l=0}^{\mathrm{\infty }}(\gamma \lambda {)}^l\cdot (r_{t+l}+\gamma V(s_{t+l+1})-V(s_{t+l}))$$

PPO-Penalty

PPO-Penalty

• KL散度：是约束行为上的距离，而不是参数上的距离，也因此无法使用L1L2范数等距离方法。

$$J_{PPO}^{{\theta }^{\prime }}(\theta )=J^{{\theta }^{\prime }}(\theta )-\beta \cdot \mathrm{KL}(\theta ,{\theta }^{\prime })$$

• 自适应KL散度，自动调节$\beta$，设置最大值和最小值，自动调节
  • $\mathrm{KL}(\theta ,{\theta }^{\prime })>{\mathrm{KL}}_{max}$： 相距太远，没有起效果，应该增大$\beta$
  • $\mathrm{KL}(\theta ,{\theta }^{\prime })<{\mathrm{KL}}_{min}$： 相距太近，KL太强了，应该减小$\beta$

PPO-Clip

PPO-Clip

核心思想

• 不做KL散度，直接做裁剪，约束变化范围，希望采样策略和学习策略不要差距太大。

$$J_{PPO}^{{\theta }^{\prime }}(\theta )=\sum _{s_t,a_t}min(\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)}\cdot A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t),\mathrm{clip}(\frac{p_{\theta }(a_t\mid s_t)}{p_{{\theta }^{\prime }}(a_t\mid s_t)},1-ϵ,1+ϵ)\cdot A^{{\pi }_{{\theta }^{\prime }}}(s_t,a_t))$$

缺点不足

PPO不足

GAE带来的计算开销大、训练不稳定

• GAE 主要依赖于单步时序误差

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

• 计算TDError之前，需为每个token计算奖励和价值
  • 每个token的价值：需由独立的Critic模型计算得到
  • Critic通常和策略模型同架构和大小，Critic计算开销非常大，且训练不稳定导致 无法提供准确的价值信号

GRPO

背景

GRPO 背景

解决PPO训练开销大,训练不稳定的

• 不用GAE

核心思想

GRPO 核心思想

Group Relative Policy Optimization

• 核心思想
  • 把多次采样的奖励均值，作为优势估计的baseline，避免单独优化Critic模型带来的麻烦
• 具体操作
  • 对1个输入1q，多次rollout
    • 采样一组$G$个输出$\{o_1,o_2,\cdots ,o_G\}$，为每个样本计算奖励得$\{r_1,r_2,\cdots ,r_G\}$
  • 单个样本中的所有token 共享一个优势
    • 优势计算：减去组内奖励均值、除以标准差

$${\hat{A}}_{i,t}={\hat{r}}_i=\frac{r_i-\mathrm{mean}(\mathbf{r})}{\mathrm{std}(\mathbf{r})}$$