GRPO之前的强化学习算法

本文用于记录从原始强化学习到PPO的发展史

概念定义

要了解强化学习基础，首先需要确定其中的概念，以防止在后续的算法演进和公式推理中弄混 1. 强化学习基本框架

• 智能体（Agent）：与环境交互、采取动作的主体
• 环境（Environment）：智能体所处的外部世界
• 状态（State）：对环境的完整描述，不隐藏世界信息
• 观测（Observation）：对状态的部分描述，可能遗漏信息
• 动作（Action）：智能体基于当前状态输出的行为
• 奖励（Reward）：环境给出的标量反馈信号，评价动作的好坏 2. 序列决策
• 强化学习的本质是序列决策问题，目的是选取一系列动作来最大化累积奖励
• 历史是观测、动作、奖励的序列：$H_t = o_1, a_1, r_1, ..., o_t, a_t, r_t$
• 状态是历史的函数：$S_{t} = f(H_t)$ 3. 智能体的三大组成成分
• 策略：把状态映射到动作的函数，分为随机性策略和确定性策略
• 价值函数：对未来奖励的预测，评估状态的好坏（包含折扣因子$γ$）
  • 状态价值函数：$V_π(s) = E[Σγᵏ r_{t+k+1} | s_t = s]$：当前状态能在将来获取到的奖励的期望
  • Q函数：$Q_π(s, a) = E[Σγᵏ r_{t+k+1} | s_t = s, a_t = a]$：在当前状态和动作下，能在将来获取奖励的期望
• 模型：环境的模拟器，包含状态转移概率和奖励函数 4. 智能体类型分类
• 基于价值的智能体：显式学习价值函数，隐式学习策略（如Q-learning）
• 基于策略的智能体：直接学习策略函数（如策略梯度）
• 演员-评论家智能体：同时学习策略和价值函数
• 有模型智能体：学习环境的状态转移模型，可以进行"想象"
• 免模型智能体：不学习环境模型，直接与环境交互 5. 核心矛盾
• 探索（Exploration）：尝试新动作，可能发现更好策略，也可能失败
• 利用（Exploitation）：执行已知的最优动作，确保获得奖励
• 探索-利用窘境：两者在资源有限时相互矛盾 6. 学习与规划
• 学习：环境未知，通过交互改进策略
• 规划：环境已知，通过计算找出最优策略

概念间的关系

智能体与环境交互（序列决策）
    ↓
状态 → 策略 → 动作 → 环境 → 奖励 + 新状态
    ↓
价值函数：评估状态好坏，指导策略改进
    ↓
模型：预测状态转移（有模型时）

关键关系：

1. 状态与观测：状态是完整描述，观测是部分描述；当智能体能观测到环境所有状态时，称为完全可观测，否则为部分可观测
2. 策略与价值函数：基于价值的智能体先学价值函数再推导策略；基于策略的智能体直接学策略；演员-评论家同时学习两者
3. 探索与利用：平衡这个矛盾是强化学习的核心挑战
4. 学习与规划：有模型强化学习可以先用学习得到模型，再用规划计算最优策略
5. 马尔可夫决策过程（MDP）：当策略、价值函数、模型三者都具备时，形成MDP框架，可用四元组$<S, A, P, R>$表示

马尔可夫决策过程

1. 马尔可夫过程（Markov Process）

• 马尔可夫性质：未来状态只依赖于当前状态，与历史无关
• 数学表达：$p(s_{t+1}|s_t) = p(s_{t+1}|h_t)$
• 状态转移矩阵：描述各状态间的转移概率
• 特点：无奖励、无决策，纯粹的状态转移过程

2. 马尔可夫奖励过程（Markov Reward Process）

• 扩展：在马尔可夫过程基础上增加奖励函数
• 回报（Return）：$G_t = r_{t+1} + γr_{t+2} + γ²r_{t+3} + ...$
• 价值函数：$V(s) = E[G_t|s_t = s]$
• 贝尔曼方程：$V(s) = R(s) + γ∑p(s'|s)V(s')$
• 核心概念：
  • 折扣因子γ：处理无穷奖励和不确定性
  • 价值评估：衡量状态的长期收益

3. 马尔可夫决策过程（Markov Decision Process）

• 扩展：在MRP基础上增加动作选择
• 四元组定义：$<S, A, P, R>$
• 策略：$π(a|s) = p(a_t = a|s_t = s)$
• 状态转移：$p(s_{t+1}|s_t, a_t) = p(s_{t+1}|h_t, a_t)$
• 奖励函数：$R(s, a) = E[r_t|s_t = s, a_t = a]$

价值函数体系

状态价值函数（V函数）

• 定义：$V_π(s) = E_π[G_t|s_t = s]$
• 含义：在策略π下，从状态s开始的期望回报

动作价值函数（Q函数）

• 定义：$Q_π(s, a) = E_π[G_t|s_t = s, a_t = a]$
• 含义：在策略π下，从状态s采取动作a后的期望回报
• 关系：$V_π(s) = Σπ(a|s)Q_π(s, a)$

贝尔曼方程体系

贝尔曼期望方程

• 状态价值：$V_π(s) = Σπ(a|s)[R(s, a) + γ∑p(s'|s, a)V_π(s')]$ ：针对s'和a两次求期望
• 动作价值：$Q_π(s, a) = R(s, a) + γ∑p(s'|s, a)V_π(s')$
• 用途：策略评估，计算给定策略的价值

贝尔曼最优方程

• 最优状态价值：$V*(s) = max_a Q*(s, a)$
• 最优动作价值：$Q*(s, a) = R(s, a) + γ∑p(s'|s, a)max_a' Q*(s', a')$
• 用途：策略优化，寻找最优策略

解决MDP的核心问题

预测问题（Prediction）

• 输入：MDP + 策略π
• 输出：价值函数V_π
• 解决方法：策略评估（Policy Evaluation）
• 迭代公式：$V^{t+1}(s) = Σπ(a|s)[R(s, a) + γ∑p(s'|s, a)V^t(s')]$

控制问题（Control）

• 输入：MDP
• 输出：最优策略π* + 最优价值函数V*
• 解决方法：策略迭代和价值迭代

动态规划算法详解

1. 策略迭代（Policy Iteration）

算法流程：

1. 策略评估：给定策略π，计算V_π
2. 策略改进：基于V_π，通过贪心策略改进π
3. 重复步骤1-2直到收敛

策略改进公式：

π_{i+1}(s) = argmax_a Q_{π_i}(s, a)

特点：

• 每次迭代都有完整的策略
• 收敛快，但每次计算量大

2. 价值迭代（Value Iteration）

算法流程：

1. 初始化V(s) = 0
2. 迭代更新：V(s) ← max_a[R(s, a) + γ∑p(s'|s, a)V(s')]
3. 收敛后提取最优策略

最优性原理：如果策略在状态s达到最优价值，那么从s可达的所有状态都必须达到最优价值 特点：

• 直接迭代贝尔曼最优方程
• 每次迭代都是价值传播，中间结果无意义
• 计算效率高，但可能需要更多迭代

3. 算法对比

关键技术概念

1. 备份操作（Backup Operation）

• 定义：利用后续状态价值更新当前状态价值
• 类型：
  • 贝尔曼期望备份（用于预测）
  • 贝尔曼最优备份（用于控制）
• 本质：价值信息的反向传播

2. 自举（Bootstrapping）

• 含义：用估计值来更新估计值
• 优势：提高样本效率
• 应用：动态规划和时序差分学习

3. 广义策略迭代（Generalized Policy Iteration）

• 概念：策略评估和策略改进的交互过程
• 特点：两个过程不必完全收敛即可交替进行
• 应用：强化学习中的许多算法

实际应用示例

网格世界问题

• 环境：二维网格，智能体在格点间移动
• 奖励设计：每步-1，特殊状态有额外奖励
• 目标：找到到达终点的最短路径
• 求解过程：
  1. 初始化价值函数
  2. 应用策略迭代或价值迭代
  3. 价值从高奖励状态向周围传播
  4. 最终收敛到最优策略

MRP的比喻

将马尔可夫奖励过程比作"纸船随波逐流"：

• 纸船：智能体
• 河流：状态转移矩阵
• 船的轨迹：生成的路径
• 目的地奖励：到达某些状态获得的奖励

求解方法对比

蒙特卡洛方法

• 原理：采样多条轨迹，计算平均回报
• 优点：无偏估计，不需要模型
• 缺点：方差大，收敛慢

动态规划方法

• 原理：迭代贝尔曼方程
• 优点：收敛快，计算精确
• 缺点：需要完整模型，计算复杂度高

时序差分学习

• 原理：结合蒙特卡洛和动态规划
• 优点：在线学习，无偏估计
• 应用：Q-learning、Sarsa等算法

关键概念关系图

马尔可夫过程（MP）
    ↓ 加奖励函数
马尔可夫奖励过程（MRP）
    ↓ 加动作和策略
马尔可夫决策过程（MDP）
    ↓
预测问题 → 策略评估 → 贝尔曼期望方程
控制问题 → 策略迭代/价值迭代 → 贝尔曼最优方程

表格方法

什么是Q表格？

Q表格是一个查找表（look-up table），用于存储状态-动作对的价值：

• 行：所有可能的状态（如悬崖行走问题中的网格位置）
• 列：所有可能的动作（上下左右）
• 值：对应状态下执行该动作的期望回报 有这样一个表格，自然就知道在每个状态下的最佳策略是什么

基于要获取这样一个Q表格的目标，如果我们已有世界模型，可以通过蒙特卡洛方法或者时序查分的自举方法去填空 而如果没有世界模型，我们就需要通过Q-learning或Sarsa方法去利用每一步行为得到的奖励来更新Q表格，其中前者是每走一步，用新获得的奖励+新状态所有可采取动作中最大的Q值 来与当前Q值计算误差，再用误差更新Q表格；后者则已知每走一步，新状态采取了什么新动作，用这个给定的新Q值来更新当前的Q表格

策略梯度方法

策略梯度算法是强化学习中基于 策略网络（Actor），输入状态，直接输出动作的概率分布。

详细内容介绍

1. 核心概念与架构

• 三个组成部分：强化学习由演员（Actor/Policy）、环境（Environment）和奖励函数（Reward Function）组成。在策略梯度中，我们能控制的只有演员（即策略网络 $\pi_\theta$），通过调整参数 $\theta$ 来获得最大的奖励。
• 策略网络：输入是状态（如游戏画面像素），输出是动作的概率分布（如向左、向右、开火的概率）。智能体根据这个概率分布进行采样来决定具体的动作。
• 轨迹（Trajectory）：在一场游戏中，状态和动作的序列 $\tau = {s_1, a_1, s_2, a_2, ..., s_T, a_T}$ 称为一个轨迹。

2. 数学原理：如何最大化期望奖励？

我们的目标是调整参数 $\theta$，使得期望奖励 $\bar{R}_\theta$ 最大化。

• 期望奖励： $\bar{R}_\theta = \sum_{\tau} R(\tau)p_\theta(\tau)$ 即所有可能轨迹的总奖励 $R(\tau)$ 乘以该轨迹发生概率 $p_\theta(\tau)$ 的加权和。
• 策略梯度公式： 为了使用梯度上升法（Gradient Ascent）更新参数，我们需要计算 $\bar{R}_\theta$ 的梯度。经过推导，梯度近似为： $\nabla \bar{R}_\theta \approx \frac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} R(\tau^n) \nabla \log p_\theta(a_t^n | s_t^n)$
  • 直观理解：如果某个轨迹 $\tau^n$ 的总奖励 $R(\tau^n)$ 是正的，我们就增加该轨迹中所有“状态-动作对”出现的概率；如果是负的，就减小其概率。
• 与分类问题的联系：在实现时，这很像是一个分类问题（Classification）。状态是输入，动作是标签。但不同的是，损失函数前乘以了一个权重（即奖励 $R(\tau)$）。奖励越大的动作，我们越希望模型去学习它。

3. 策略梯度的实现技巧

为了让训练更稳定和高效，第四章介绍了两个关键技巧： 技巧 1：添加基线 (Baseline)

• 问题：很多游戏中的奖励总是正的（最低是0）。根据公式，无论动作好坏，其概率都会上升，只是上升幅度不同。如果在采样中某些动作未被选中，归一化后它们的概率反而会下降，这可能导致错误的策略更新。
• 解决：引入基线 $b$（通常设为奖励的平均值，这个值是不断计算更新的）。 $\nabla \bar{R}_\theta \approx \frac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} (R(\tau^n) - b) \nabla \log p_\theta(a_t^n | s_t^n)$ 这样，奖励 $R(\tau^n) - b$ 就有正有负。表现好的动作（高于平均）概率上升，表现差的动作（低于平均）概率下降。 技巧 2：分配合适的分数 (Credit Assignment)
• 问题：原始公式中，整场游戏的总奖励 $R(\tau)$ 被用来评估每一个动作。但实际上，第 $t$ 步的动作只影响第 $t$ 步及之后的奖励，与之前的奖励无关,。
• 解决：将总奖励替换为折扣回报（Discounted Return）。对于时刻 $t$ 的动作，只计算从 $t$ 开始到游戏结束的累积奖励，并乘上折扣因子 $\gamma$（衰减未来奖励的影响）。 $\nabla \bar{R}_\theta \approx \frac{1}{N} \sum_{n=1}^N \sum_{t=1}^{T_n} \left( \underbrace{\sum_{t'=t}^{T_n} \gamma^{t'-t} r_{t'}^n}_{\text{从时刻t开始的折扣回报}} - b \right) \nabla \log p_\theta(a_t^n | s_t^n)$
• 求和范围的变化：权重的计算不再是整场回报，而是 $\sum_{t'=t}^{T_n}$。这意味着第 $t$ 步的动作只对 $t$ 时刻及之后的奖励负责，与 $t$ 时刻之前的奖励无关（过去的事情已经发生，现在的动作无法改变过去）
• 折扣因子 $\gamma$：引入 $\gamma^{t'-t}$ 是为了进一步体现时间的影响。虽然 $t$ 时刻的动作影响未来，但时间越久远，影响越小。$\gamma \in$，通常设为 0.9 或 0.99
• 基线 $b$：公式中通常保留减去基线 $b$（来自技巧1），这一项 $( \sum \gamma r - b )$ 被称为优势函数（Advantage Function） $A_\theta(s_t, a_t)$，衡量的是在状态 $s_t$ 下采取动作 $a_t$ 相对于平均表现的“相对优势”。这个函数通常可以由一个网络估计出来，这个网络称为评论员 (critic)

4. REINFORCE 算法

REINFORCE 是最经典的蒙特卡洛策略梯度算法。

• 特点：
  • 回合更新：它需要等待一个回合（Episode）完全结束后，收集到完整的轨迹数据，算出每个时刻的回报 $G_t$，才能进行参数更新。
• 流程：
  1. 智能体与环境交互，采样生成一个回合的轨迹。
  2. 从后往前计算每个时刻的折扣回报 $G_t$。
  3. 利用公式 $\theta \leftarrow \theta + \alpha \gamma^t G_t \nabla \log \pi(a_t | s_t, \theta)$ 更新策略参数。

近端策略优化(proximal policy optimization,PPO)

在GRPO之前最负盛名的强化学习方法之一，也是GRPO的研究基础 其建立在策略梯度方法的基础上，加入了KL散度的限制或优化步幅的clip限制，这两点在后续的研究中也将经常看到 这个优化的目的在于控制每次更新过程中，用于采样的策略分布和更新参数后的策略分布的差距不要太大（主要是方差的差距），这样使得更新更稳定有效

DQN

深度Q网络，是建立在离散的Q表格的基础上，进一步将Q函数值的分布区间从可穷举的离散空间扩展到连续空间，用一个网络来拟合Q函数，学习该网络的输出，就是学习Q表格中的每个数字。

这个方法的本质就是一个回归问题，我们需要用深度学习的方法，回归训练出Q网络的参数。

在这个方法中，不再关乎actor，而是关乎critic，即Q函数。相关的一系列优化手段，包括引入目标网络、经验回放、随机探索动作，都是为了更好、更稳定地优化Q网络

在DQN的基础之上，前人探索出了一系列更详细的优化手段，这些手段大部分是针对上述的三种策略进行进一步改进。从实验角度而言，这些优化手段都是有效的。

演员-评论家算法

Actor-Critic算法的核心建立在PPO和DQN方法各自的缺点的基础之上，策略梯度需要读完一整条链路，方差较大，而DQN的方差太小，难以训练 因此，将二者结合起来，用Q函数去代替策略梯度中的奖励项，并通过贝尔曼方程和一些近似考虑，将最终要用于优化的优势函数定义为一个差分误差的形式，