Greedy Sampling Is Provably Efficient for RLHF¶

会议: NeurIPS 2025
arXiv: 2510.24700
代码: 无
领域: LLM对齐 / RLHF理论
关键词: Greedy Sampling, KL正则化, 偏好学习, 遗憾界, Bradley-Terry模型

一句话总结¶

证明了在KL正则化的RLHF设置下，直接使用经验估计的贪心采样（无需构建乐观/悲观估计）就能在在线和离线两种设置中实现\(O(\log T)\)遗憾界和\(O(\varepsilon^{-1})\)样本复杂度，这是首次在一般偏好模型下达到这些阶数。

研究背景与动机¶

领域现状：RLHF是LLM后训练的关键技术。理论分析关注两个核心问题：在线设置下的遗憾（regret）界和离线设置下的样本复杂度。之前的工作已证明KL正则化目标下可以实现\(O(\log T)\)遗憾和\(O(\varepsilon^{-1})\)样本复杂度，但这些结果要么假设直接奖励观测，要么局限于Bradley-Terry偏好模型。
现有痛点：
一般偏好模型（不假设底层奖励函数存在）的理论保证还停留在\(O(\sqrt{T})\)遗憾和\(O(\varepsilon^{-2})\)样本复杂度
现有算法都遵循乐观（optimism）或悲观（pessimism）原则——需要构建置信上下界，计算成本高且在一般场景下困难
KL正则化引入的结构性质没有在算法设计中被充分利用
核心矛盾：在经典RL/CB中，直接使用经验估计（不加乐观/悲观修正）是已知不work的——贪心策略会导致探索不足和次优收敛。但RLHF的KL正则化是否改变了这一格局？
切入角度：发现KL正则化目标下，最优策略类有一个之前被忽视的结构性质——所有候选最优策略与参考策略的似然比是有界的，即\(\pi_f(a|x)/\pi_0(a|x) \in [\exp(-\eta), \exp(\eta)]\)。这意味着最优策略必须是随机的且不会与参考策略偏差太大，从而自然提供了充分的探索。
核心idea一句话：KL正则化让最优策略"自带探索"——不需要刻意的乐观/悲观修正，直接贪心采样就够了。

方法详解¶

整体框架¶

考虑KL正则化的上下文老虎机（CB）问题：策略\(\pi\)对给定上下文\(x\)（prompt）选择动作\(a\)（response），目标是最大化偏好得分减去KL惩罚。同时处理两种偏好模型：一般偏好模型（直接建模\(\mathbb{P}(a^1 \succ a^2 | x)\)）和Bradley-Terry模型（通过潜在奖励函数）。

关键设计¶

最优策略类的结构性质（Proposition 1 + Lemma 1）：
核心发现：KL正则化目标下，最优策略的形式为\(\pi_f(a|x) \propto \pi_0(a|x)\exp(\eta f(x,a))\)，其中\(f \in [0,1]\)
关键推论：\(\pi_f(a|x)/\pi_0(a|x) \in [\exp(-\eta), \exp(\eta)]\)
两个重要含义：(a) 最优策略必须是随机的（与经典RL中最优策略通常是确定性的不同）；(b) 最优策略与参考策略的比值有界——这意味着从任何候选最优策略中采样都能对所有动作提供一定程度的覆盖
这就是贪心采样work的根本原因：不需要额外的探索机制
在线贪心采样（Algorithm 1）：
做什么：每轮从当前最优策略采样\(a^1\)，从参考策略采样\(a^2\)，观察偏好反馈，做MLE更新偏好模型估计，再计算新的贪心策略
与现有方法的区别：不需要构建置信上界/下界，不需要乐观采样策略，也不需要特殊的enhancer策略
理论保证（Theorem 1）：一般偏好模型下遗憾\(O(\exp(\eta) \cdot d_{\text{GP}} \cdot \log(N_{\mathcal{P}}T/\delta))\)，是\(O(\log T)\)阶数
离线贪心采样（Algorithm 2）：
做什么：在已有离线数据上做MLE估计偏好模型，直接计算贪心策略
理论保证：样本复杂度\(O(\varepsilon^{-1})\)，只需要单策略覆盖
与经典\(O(\varepsilon^{-2})\)的对比：整整一个阶数的改进

理论证明的核心技巧¶

将单步遗憾转化为涉及最佳响应策略的形式，使min-player的策略对齐
利用Lemma 1（似然比有界）将所有中间策略转换为参考策略\(\pi_0\)，避免了对未知策略的依赖
通过浓度不等式将MLE估计误差与Eluder维度联系起来

实验关键数据¶

合成实验（KL正则化CB，20个上下文，10个动作）¶

方法	在线遗憾（GP, T=2000）	在线遗憾（BT, T=2000）
贪心采样（本文）	~40	~35
乐观方法（OFUL-style）	~45	~40
均匀探索	~100	~90

离线实验¶

方法	样本复杂度达到\(\varepsilon\)-最优
贪心采样	\(O(\varepsilon^{-1})\)
悲观方法	\(O(\varepsilon^{-1})\)（但计算更复杂）
朴素MLE	\(O(\varepsilon^{-2})\)

关键发现¶

贪心采样在合成实验中与更复杂的乐观/悲观方法统计性能可比，但计算简单得多
\(O(\log T)\)遗憾界是首次在一般偏好模型下达到的
代价是遗憾界多了一个\(\exp(\eta)\)因子——当KL惩罚较弱（\(\eta\)大）时，贪心采样需要更多样本才能追上

亮点与洞察¶

反直觉的结论：在经典RL中，贪心采样是出了名的"不work"（探索不足）。本文证明KL正则化从根本上改变了这一点——正则化本身就是探索
算法极其简洁：只需MLE + 贪心而已，不需要构建复杂的置信区间或求解minimax优化。这不仅理论的更强，实际也更容易实现
统一了GP和BT模型：以前的tight bound局限于BT模型，本文首次将同阶数的结果推广到一般偏好模型

局限性 / 可改进方向¶

理论局限：所有结果基于tabular/有限函数类假设，推广到连续或无限函数类需要进一步工作
\(\exp(\eta)\)因子：当KL正则化较弱时（大\(\eta\)），贪心采样的优势会减弱
合成实验：只在小规模合成设置上验证，没有真实LLM实验
单轮CB设置：实际RLHF涉及多轮对话（完整MDP），推广到多步决策需要额外分析
未讨论DPO的联系：DPO也利用了KL正则化的结构但从不同角度，二者的理论联系值得探索

评分¶

新颖性: ⭐⭐⭐⭐⭐ "贪心采样在RLHF中可证明高效"是反直觉且深刻的理论发现
实验充分度: ⭐⭐⭐ 合成实验验证了理论，但缺少真实LLM场景的验证
写作质量: ⭐⭐⭐⭐⭐ 数学推导严谨，直觉解释清晰，证明sketch有效传达了核心思想
价值: ⭐⭐⭐⭐ 对RLHF理论有重要推进，对算法设计简化有指导意义