强化学习的基本概念

强化学习主要考虑解决智能体(Agent)与环境(Environment)之中最优交互策略的问题。在一个交互中，智能体一般会根据现在的状态(State)，进行相应的策略思考后做出动作(Action)，随后环境因为智能体的动作发生了变化，返回给智能体对应的反馈(Reward，或称为奖励)。对于每个概念，定义对应变量如下：

• t时刻智能体做出的动作$A_t$：

• t时刻环境已对智能体动作给出的反馈：$R_t$，值得注意的是对于$A_t$，环境给出的反馈是$R_{t+1}$而非$R_t$。因为在$t=0$时，环境不会给出反馈

• t时刻的状态(State)：$S_t$，一般使用$S_t^e$代表环境状态(它可能并非完全由智能体感知，比如围棋中智能体可完全感知$S_t^e$，而在MOBA对战中智能体只能感知一部分可见的$S_t^e$)。而$S_t^a$代表智能体当前的状态，它包含了当前、历史中智能体的感知$O_1$~$O_t$以及反馈$R_1$~$R_t$，还有智能体历史中的动作$A_1$~$A_t$。$S_t^a = f(H_t) = f(O_1,R_1,A_1,…,A_{t-1},O_t,R_t)$

• 智能体的策略：$\pi$，有固定策略$a=\pi(s)$和概率选择策略$\pi(a|s)=P[A_t=a|S_t=s]$两种，由于前者固定，所以模型学习的一般是后一种。强化学习的目标就是找到一个相应的$\pi$，来最大化自己的最终反馈。对于$\pi$的初始化，则可以有通过其他预训练得到、随机初始化得到

为了简便化，在强化学习中，一个重要的假设是状态转移是一个马尔可夫过程，即$t+1$时刻的状态$S_{t+1}$仅与$t$时刻的状态$S_t$有关，即$P[S_{t+1}|S_1,…,S_t]=P[S_{t+1}|S_{t}]$，且对于特定的动作$A_t$，不同状态变化的概率$P[S_{t+1}|S_{t}]$可通过一个状态转移概率矩阵来进行描述。对于环境状态完全由智能体感知($S_t^a=S_t^e=S_t$)的情形，强化学习就是一个马尔科夫决策过程(MDP)，而对于环境状态不完全被智能体感知($S_t^a \neq S_t^e$)的情形，强化学习是一个不完全感知马尔科夫决策过程(POMDP)。当前，强化学习主要研究方向是MDP，也就是$S_t^a=S_t^e=S_t$的情形

Bellman方程

对于特定采取的某个$A_t$来说，它的好坏等价于对未来反馈的期望。因此，引入回报$G_t$来描述$t$时刻将具备的回报：

$$G(t)=R_{t+1}+\lambda R_{t}+…=\sum_{k=0}^{\infty}\lambda^k R_{t+k+1}$$

其中$\lambda$为取值(0~1)的未来折扣因子，引入此因子的目的是让模型对每步进行优化时更加着眼于当前Action的影响，而非未来

而在状态转移概率矩阵已知的马尔科夫过程下，我们可求得$t$时刻回报的期望，也就是价值函数：$v(s)=E[G_t|S_t=s]$

全期望公式

离散形式$$E(E(Y|X))=\sum_i p_i E(Y|X=x_i)=E(Y)$$

连续形式$$E(E(Y|X))=\int_{-\infty}^{\infty} E(Y|X)f_X(x) dx=E(Y)$$

全期望公式从统计均值角度的理解：随机变量集合的总体平均，等于先将它们按某条件划分，分组聚合得出每组平均后再计算各组的加权平均

证明，这里仅写出连续形式的证明：

$$E(E(Y|X))=\int_{-\infty}^{\infty} E(Y|X)f_X(x) dx=\int_{-\infty}^{\infty}[\int_{-\infty}^{\infty} y * f_{Y|X}(y|x)dy]f_X(x)dx $$ $$=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty} y * f_{Y|X}(y|x)f_X(x)dxdy = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty} y * f(x,y)dxdy$$ $$=\int_{-\infty}^{\infty}y*[\int_{-\infty}^{\infty} f(x,y)dx]dy=\int_{-\infty}^{\infty}y*f(y)dy=E(Y)$$

由全期望公式，即可将回报变为如下形式

$$v(s)=E[G_t|S_t=s]=E[\sum_{k=0}^{\infty}\lambda^k R_{t+k+1}|S_t=s]=E[R_{t+1} + \lambda G_{t+1}|S_t=s]$$ $$=E[R_{t+1} + \lambda E[G_{t+1}|S_{t+1}]|S_t=s]=E(R_{t+1} + \lambda v(S_{t+1}|S_{t+1})|S_t=s)$$

回报的此递推形式被称为Bellman方程

强化学习的主要方法

引入Bellman方程后，强化学习就可以通过使用程序迭代的方式，不断从一个状态探索到另一个状态，直到结束。在一次探索(episode)结束后，更新自己的策略，进入下一个episode中。而在探索的方式，主要可以分为如下几类：

• model-based：会建模状态转移方程

  • Bellman方程的形式可以很容易让人想到使用动态规划的方式进行求解。求解动态规划则需要获得各个环境的状态转移方程及每个状态、动作对应的的最优值函数。由于最优值函数是强化学习的核心，任何策略都会涉及到。因此model-based的方法实际就是也对环境建模，将状态转移方程也建模为模型

  • 优点：通过对环境建模可以学习环境信息，将已有经验重复利用，样本、计算资源利用效率高。学习易收敛

  • 缺点：环境不断变化，模型可能与真实环境学习出现偏差。有些环境建模十分复杂甚至于几乎无法建模

• model-free：只学习最优值函数，不建模状态转移(最优值函数可以是模型，因此model-free的“free”只代表不建模环境模型，不代表没有模型！)

  • 在很多场景下环境建模十分复杂，乃至无法建模(如对战游戏中对手的操作可以是毫无逻辑)，因此model-free专注于优化最优值函数，通过不断与环境交互来得到最优策略。当前大多数的强化学习方式都是model-free方式，根据优化最优值函数的方式，model-free可更细分为如下几种

    • 优化策略：直接优化策略$\pi$。如Policy Gradient算法、PPO(Proximal Policy Gradient)算法

    • 优化价值：即评估每种状态转移的价值优劣，随后通过选择回报最高的状态转移作为策略(在学习时选择则一般会赋予一定随机探索性，如ϵ−greedy选择策略)。如Q learning、SARSA、DQN算法

    • Actor-Critic算法：价值和策略都进行建模，同时进行优化

  • 优点：泛化能力强。由于直接与环境交互不存在建模偏差，计算资源、数据量足够的情况下效果一般是最好

  • 缺点：试错成本高，样本、计算资源利用效率低。学习不易收敛。在某些虚拟环境数据众多真实环境数据很少的场景中(比如自动驾驶、机器人)，真实数据的量不能支持model-free的迭代，因此主要拟合最优虚拟环境的model-free反而会相较可更有效利用真实数据的model-based更易产生过拟合偏差

model-based和model-free的主要区别是“是否建模环境”，因此二者一个简单的区分方式就是在模型进行一次Action后，是否已可预测到下一步的环境以及这步Action的Reward是多少。如果是，那就是model-based，如果不是，那就是model-free

当前由于model-free的适用面更广，且PPO是强化学习效果最好的算法之一，因此之后仅对model-free进行介绍

此外，由于强化学习需要与环境交互，因此强化学习的参数更新使用的交互样本也有两种区分：

• on-policy：在参数更新时，仅使用上一轮迭代后与环境交互产生的样本，如Policy Gradient、SARSA算法。on-policy认为在模型迭代后，与环境的交互很可能会发生变化甚至完全不同，因此需重新收集数据。on-policy的优点是简单直接，在模型收敛的情况下收敛很快。缺点是数据利用效率低，在模型做复杂的情况下容易出现难收敛的情况，由于只使用上一轮最优可能会使模型收敛到局部最优

• off-policy：在参数更新时，除上一轮外还会使用更之前轮迭代后与环境交互产生的样本，如DQN、PPO(有争议)算法。off-policy认为智能体与环境的交互产生的结果与当前智能体的智能水平无关，因此数据收集应该和参数更新是两个独立的过程。优点是数据利用效率高，收敛更稳定，缺点是模型收敛速度更慢

Q learning 和 DQN

价值优化强化学习的主要思想是模型通过不断地迭代试错，评估每种状态转移的价值优劣，最终找到一个回报最高的状态转移链作为策略。但是Bellman方程中可以看出，不执行到最后一步，并不会得到当前步的回报，无限穷举所有可能分别计算则随着动作的步长指数增加而不现实。因此Q learning的主要思想是“走一步看一步”，在未来的回报还未确定时，将其视为当前的值，在每一次试错中都迭代更新当前状态下计算的回报，进行不断逼近。具体做法是首先初始化一个行是State，列是Action的矩阵，将其值全部赋为0，称为Q矩阵。随后采用某种Action选择策略(如ϵ−greedy)根据当前的State下不同Action的回报值随机选择一个Action，根据环境给出的反馈Reward来更新Q矩阵，更新公式为：

$$Q(S,A) \leftarrow Q(S,A) + \alpha(R+\gamma max_a Q(S’,a)-Q(S,A))$$

其中是$\alpha$取值(0-1]的learning rate，R为Action获得的Reward，$\gamma$是Bellman方程中的$\lambda$未来折扣因子。而$max_a Q(S’,a)$则是当前Q矩阵中查表得到的$S’$状态对应最大回报。可以看到$R+\gamma max_a Q(S’,a)$就是我们此次迭代时与环境交互后“与真实情况更接近的$v(s)$”，观察Q learning的更新策略，可以发现其实际就是将“与真实情况更接近的$v(s)$”作为此次迭代的真实label y，当前Q值为拟合$\hat{y}$，使用MSE作为损失的一个梯度下降过程。以下为Q learning的详细算法：

Q learning的缺点显而易见，那就是在任务复杂后，无数的State和Action组合后Q矩阵会极为庞大。在神经网络深度学习席卷各个领域后，一个自然的想法就是将$<S, A>$的Q矩阵转化为神经网络，使用神经网络来估计每种State和Action组合的回报期望Q值，使用Q learning的策略学习，这就是DQN

由Q learning的参数更新策略，可知DQN的损失函数为：$$L(w)=E[(R+\gamma max_{a’}Q(s’,a’,w)-Q(s,a,w))^2]$$

由DQN的损失可知其损失梯度为：$$\nabla_w L(w) = - \frac{1}{N}\sum_{n=1}^{N}(R+\gamma Q_w(s’)-Q_w(s))\nabla_w Q_w(s) = - \frac{1}{N}\sum_{n=1}^{N}\delta_t \nabla_w Q_w(s)$$

DQN的详细算法逻辑为：

从这里可以看到，Q learning和DQN每次迭代均会使用所有探索的信息，因此其是off policy的

Policy Gradient

策略优化强化学习相对价值优化强化学习则更加直击问题，它直接使用神经网络优化策略$\pi$，并使用网络给出的策略执行下一个状态切换。策略优化中最简单的算法即是Policy Gradient算法，在Policy Gradient中，神经网络作为一个分类器，主要用来输出某个State下应该采取各个Action的概率

之后，算法就会使用当前策略进行数据收集，每次数据搜集我们称为一次轨迹$\tau$，因此当前策略的期望回报即为此次所有数据搜集的均值

$$\bar {R_\theta} = \sum_\tau R(\tau) p_\theta(\tau)$$

其中$R_\tau$即为一次搜集(轨迹)得到的总回报，$p_\theta(\tau)$则是一次轨迹$\tau$出现的总概率：

$$p_\theta(\tau) = p(s_1)p_\theta(a_1,s_1)p(s_2|s_1,a_1), … p_\theta(a_t,s_t) p(s_{t+1}|s_{t},a_{t}) = p(s_1) \prod_{t=1}^{T} p_\theta(a_t|s_t)p(s_{t+1}|s_t, a_t)$$

前面也提到，model-free方式不会对环境的状态转移进行建模，因此我们事实优化的只有$\prod_{t=1}^{T} p_\theta(a_t|s_t)$这项

为了最大化$$\bar {R_\theta}$，我们可以使用梯度上升(或取个负号做梯度下降)的方式，求$p_\theta(\tau)$的梯度，随后根据梯度让当前参数更新从而达到极值。首先，将$p_\theta(\tau)$由离散形式改为连续形式，称为目标函数$J(\theta)$：

$$J(\theta) = \int p_\theta(\tau)R(\tau)d\tau$$

求导，可获的梯度为：

$$\nabla_\theta J(\theta) = \int \nabla_\theta p_\theta(\tau)R(\tau)d\tau = \int p_\theta(\tau) \frac{\nabla_\theta p_\theta(\tau)}{p_\theta(\tau)} R(\tau)d\tau $$ $$= \int p_\theta(\tau) (\nabla_\theta \log p_\theta(\tau)) R(\tau)d\tau = E_{\tau\sim p_\theta(\tau)} [(\nabla_\theta \log p_\theta(\tau)) R(\tau)] $$ $$= E_{\tau\sim p_\theta(\tau)} [(\nabla_\theta \log \prod_{t=1}^{T} p_\theta(a_t|s_t)) R(\tau)] \ = E_{\tau\sim p_\theta(\tau)} [(\sum_{t=1}^{T} \nabla_\theta \log p_\theta(a_t|s_t)) R(\tau)]$$

其中第3步利用了$\nabla \log f(x) = \frac{1}{f(x)} \nabla f(x)$，第4步则运用了$E[f(x)] = \int x f(x) dx$

$J(\theta)$这种单纯的期望很难有解析解，因此一般使用每次迭代中所有的搜集取平均，即$\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{n=1}^{N} \left( \left(\sum_{t=1}^{T} \nabla_\theta \log p_\theta(a_t|s_t)\right) R(\tau) \right)$，其简写为$\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{n=1}^{N} \nabla_\theta \log P(\tau,\theta) R(\tau)$

有了优化目标、梯度后，参数更新策略就是梯度上升/下降了：$\theta \leftarrow \theta + \alpha \nabla_\theta J(\theta)$

由于Policy Gradient中每次参数更新仅使用每次迭代的搜集数据，因此Policy Gradient是on policy的

归一化

不同于分类任务的“正负样本”之分，策略优化强化学习主要优化的$J(\theta)$有两个不同，一是可能在某状态并没有“坏动作”，执行所有可能的动作都可以得到正的Reward，二是$J(\theta)$通过采样得到的。这会导致两个问题：

1. 当某状态没有“坏动作”时，按照梯度所有Action的概率都应增加，但判别模型给出的softmax概率和只能为1(下图1)

2. 如果某状态在一次迭代中的所有搜集中都没有出现，其也会因为softmax和为1的影响被强制赋予一个不合理的梯度而变化(下图2，b、c都上涨的情况下a只能被强制拉低)

解决方法：减去所有回报的均值，作为归一。使得高于平均回报的轨迹回报为正，低于平均的为负

$$\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{n=1}^{N} \nabla_\theta \log P(\tau,\theta) [R(\tau) - b]$$ $$b = \frac{1}{N} \sum_{n=1}^{N} R(\tau)$$

重要性采样和PPO(近端策略优化算法)

前面提到，Policy Gradient这种on policy的在模型做复杂的情况下容易出现难收敛的情况，由于只使用上一轮最优可能会使模型收敛到局部最优。这两个缺点实际根因是一个：在on policy中每次迭代使用的sample数量永远是设定好的固定不变的，如果我们的learning rate设的过大，就会导致在可以采取复杂策略的复杂模型中两次迭代的策略几乎完全不同，两次迭代获得的轨迹完全不同，模型就像在无穷的参数海中和每次迭代完全不同的体验如同无头苍蝇般乱撞。如果我们的learning rate设的过小，那么模型就会探索性不足，在某个局部最优点就收敛。而off policy则会随着迭代看到的数据越来越多，收敛也趋于稳定并至全局最优

为了削减on policy的问题，我们对Policy Gradient进行如下改进：

1. 应对获得轨迹完全不同问题：使用sample data多次，使用重要性采样来修正参数的方式来更新参数而非直接更新

   1. PPO到底是on policy还是off policy争议的根源，认为是on policy的表示每次策略总迭代仍然使用的还是上一次迭代的sample，下次总迭代后就会舍弃。而认为是off policy的则表示在每次小迭代中，修正参数方式迭代本身就没有总迭代小迭代的强顺序要求，而且属于多次利用之前样本，所以是off policy的

   2. 个人认为完全不需要纠结这些“从大迭代看”，“从小迭代看”等等这些无聊的定义细枝末节，其到底是什么不会给模型结构的优化研究、应用带来任何有效信息，这种问题就应该被奥卡姆剃刀剃掉

2. 应对两次迭代策略完全不同：参数更新时对新旧策略进行评估，要求新旧策略的差异不能过大，如参数的值差异不能过大(TRPO)，或二者的KL散度不能过大(PPO)

这就是PPO算法的主要思想，下面对其进行分别介绍

重要性采样

在一次策略更新后，如果我们还想用旧策略的数据进行训练，那么就不得不考虑新旧策略的差异性问题，考虑使用策略$\theta’$去更新$J(\theta) = \int p_\theta(\tau)R(\tau)d\tau$

$$J(\theta) = \int p_\theta(\tau)R(\tau)d\tau \approx \int p_\theta(\tau) \frac{q_\theta’(\tau)}{q_\theta’(\tau)} R(\tau)d\tau = E_{x\sim\theta’}[\frac{p_\theta(\tau)}{q_\theta’(\tau)} R(\tau)]$$

其中q是由第一次直接策略更新的数据中采样而来的，因此，在式中引入q后$\tau$的含义也有所改变，所积的是采样q对应的所有轨迹而不是原本整体的轨迹，等于号也改为了约等于号。可以发现这个最大熵模型引入隐含变量的套路类似，将原本x~p的期望改为了x~q的期望，而$\frac{p_\theta(\tau)}{q_\theta’(\tau)}$则代表旧策略概率集中而新策略概率不集中的地方重要性系数会很小，而新策略概率集中旧策略概率不集中的地方重要性系数会更大些。这样可以理解为在修正中我们不希望矫枉过正，把新策略修正回旧策略去，而是只是往回拉一把，让其离旧策略近一点即可。重要性采样整体流程如下：

截断约束和相对熵约束

为了防止两次迭代策略差异过大，因此须对新旧策略之间的参数进行一定的约束，PPO提出了两种方法：

• clip约束，如果$\frac{p_\theta(\tau)}{q_\theta’(\tau)}$过大/过小，则对其进行一个截断，并且取不截断与截断策略之间$J(\theta)$的最小值，其中$r(\theta)=\frac{p_\theta(\tau)}{q_\theta’(\tau)}$

$$J^{CLIP}(\theta) = E_{x\sim\theta’}\left[min\left(r(\theta) R(\tau)\right), clip(r(\theta), 1 - \epsilon, 1 + \epsilon) R(\tau)\right]$$

• 可调节的KL散度约束(类似TRPO做法)：在$J(\theta)$中加入新旧策略的KL散度作为惩罚项，并使用可自动调节的$\beta$系数来进行调节(而TRPO中$\beta$固定)，如果计算的KL散度大于设定的最大值，则增大$\beta$加重惩罚，如果计算的KL散度小于设定的最小值，则减小$\beta$减小惩罚

PPO算法简明流程如下：(注，为保持文章一致性文章中的符号标记与引用图片略有差别，图片中为相对熵版本，但事实上截断版本用的更多)

Actor-Critic

通过对DQN及Policy Gradient的学习，我们可以发现二者各自的缺点，DQN中策略选择仅仅是一个固定的“基于价值判断的随机策略”，而Policy Gradient拟合的每次搜寻则抖动较大。因此一个想法是可不可以将二者结合？答案是肯定的，我们只需将DQN的“基于价值判断的随机策略”替换成Policy Gradient的策略网络，或另一个角度说把Policy Gradient拟合的期望回报换为DQN的回报期望Q值。这就是Actor-Critic

另外，由于价值函数本身就是归一化的，因此用价值函数拟合的Q直接替代Policy Gradient期望回报时，不再需要再额外归一化，直接代入即可

Actor-Critic 算法的具体流程如下：

• 初始化策略网络参数$\theta$，价值网络参数w

• for 序列 $e = 1 \rightarrow E$ do :

  • 用当前策略$\pi_\theta$采样轨迹，为每一次搜集数据计算总回报$R_\tau$及计算梯度时的$\delta_t$

  • 更新价值参数$w \leftarrow w + \alpha_w \sum_t \delta_t \nabla_w V_w (s_t)$，（一般在Actor-Critic中称原本DQN中的Q网络为V网络）

  • 更新策略参数$\theta \leftarrow \theta + \alpha_\theta \sum_t \delta_t \nabla_\theta \log \pi_\theta(a_t|s_t)$

• end for

Instruct GPT中的RLHF

Instruct GPT中的RLHF实际就是额外训练一个Reward Model用来做判断人类喜好的“环境”，随后采用Actor-Critic + PPO的方式进行学习，整体流程如下：

1. 对目标raw LLM进行SFT，生成可以理解指令的SFT Model

2. 将SFT Model额外复制一份并frozen参数当做Reference Model，用来做PPO相对熵约束部分，防止模型距离最初模型过远，产生遗忘问题

3. 根据人类喜好数据，训练一个较小的判别模型，用来判断一个输出按照人类偏好而言的好坏

4. 同样，将判别模型也额外复制一份并frozen参数当做Reward Model，用来做强化学习中的“环境”部分

5. 将SFT Model作为Actor，判别模型做Critic，frozen参数的Reward Model当做环境使用Actor-Critic算法学习。在Actor网络更新参数时，使用PPO的方式更新，但PPO中的相对熵约束并不是一般强化学习中“上一轮自己”，而是frozen参数的Reference Model