Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferences¶

会议: NeurIPS 2026
arXiv: 2602.23116
代码: https://github.com/minju-hong/online_rlhf_gbpm.git
领域: 强化学习
关键词: 在线RLHF, 广义双线性偏好, 正则化对偶间隙, 贪心采样, 探索-提交算法

一句话总结¶

本文针对在线人类反馈强化学习（RLHF）在非传递偏好和赌徒反馈下的正则化最大遗憾最小化问题，基于广义双线性偏好模型（GBPM）首次证明了任意强凸正则化下的贪婪策略对偶间隙均可被参数估计误差平方严格控制，从而建立了首个脱离KL几何特异性的通用多对数与高维低秩遗憾界。

研究背景与动机¶

基于人类反馈的强化学习（RLHF）是大语言模型（LLM）价值对齐的核心支柱。然而，工业界与学术界主流方案长期依赖基于标量奖励的 Bradley-Terry-Luce（BTL）模型。现实中人类的真实偏好高度依赖语境，普遍表现出循环性、非传递性与多样化特征，难以被简单的标量效用函数充分刻画。为此，学界正全面转向通用偏好学习（或纳什学习）框架，直接求解双人对称零和偏好博弈的纳什均衡（NE）。在实际在线对齐与自对弈交互中，为防止模型偏离参考策略导致奖励黑客攻击（reward hacking）、多样性崩溃与生成幻觉，必须在博弈目标中引入正则化项以构建鲁棒的量子响应均衡。

然而，现存证明在线偏好博弈多对数遗憾（polylogarithmic regret）的理论体系极度依赖逆 KL 散度（reverse KL）。现有分析深度受限于指数族与 Gibbs 采样的闭式概率密度形式，无法推广到更丰富的强凸正则化族（如负香农熵、Tsallis 熵、$\chi^2$ 散度、逆 KL 混合或通用 $f$-散度）。这就产生了一个关键的理论悬念：在线 RLHF 中实现快速多对数遗憾界，究竟是 KL 几何的专属产物，还是强凸正规化所共有的普适性质？此外，现存少数非传递偏好理论往往依赖配对特征（pair-wise features），无法直接适配实际大模型中仅能提取单项上下文特征（item-wise features）的工程现实。

本文的切入角度是引入刻画项级特征与非传递偏好的广义双线性偏好模型（GBPM），并基于强凸性与偏好矩阵的反对称几何解耦正则化机制。核心 idea：利用广义双线性偏好的反对称结构与正则化博弈目标的强凸几何，结合 $\ell_1$ 范数的积分概率度量（IPM）表示，严格证明任意贪婪纳什策略的瞬时对偶间隙均受参数估计误差的二次项（平方）严格上界约束，从而证明快速遗憾率并非 KL 独有，而是任意强凸正则化几何的内在必然属性。

方法详解¶

整体框架¶

所提框架围绕广义双线性偏好模型（GBPM）下的在线上下文对抗性偏好学习展开。在每一轮交互中，环境提供上下文 $\bm{x}_t \sim d_0$。最大化玩家（learner 主策略）选择策略 $\hat{\pi}_t^1$，最小化玩家选择策略 $\hat{\pi}_t^2$，分别采样动作 $\bm{a}_t^1$ 与 $\bm{a}_t^2$，并观测到来自真实偏好概率 $P^*(\bm{a}^1 \succ \bm{a}^2 \mid \bm{x}) = \mu(\phi(\bm{x},\bm{a}^1)^\top \bm{\Theta}_\star \phi(\bm{x},\bm{a}^2))$ 的伯努利赌徒反馈 $r_t$。其中 $\bm{\Theta}_\star \in \mathbb{R}^{d \times d}$ 是未知的秩不超过 $2r$ 的反对称矩阵，$\mu$ 为已知单调递增且关于原点中心对称的链接函数（如 Logistic 链接）。学习目标是通过最小化正则化最大最优响应遗憾（Regularized Max-Regret）来收敛到对称纳什均衡（SNE）。

针对不同维度与数据条件，论文构建了两种具体算法机制：在低维充分数据机制下采用贪心采样（Greedy Sampling, GS），最大化玩家严格执行关于当前极大似然估计（MLE）的贪婪纳什均衡策略，最小化玩家执行特征覆盖探索策略 $\rho$；在高维或样本受限机制下，采用核范数正则化 MLE 的探索-提交算法（Explore-Then-Commit, ETC），在纯探索阶段后直接提交至经验纳什均衡策略。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境上下文 x_t 与单项特征映射 phi(x,a)"] --> B["自对弈策略交互：贪心采样或探索提交<br/>双人对抗生成成对响应并接收偏好反馈 r_t"]
    B --> C["参数矩阵估计：反对称核范数约束 MLE<br/>基于 Bernoulli 对数似然凸优化重构 Theta_t"]
    C --> D["二次对偶间隙控制：强凸性与 IPM 极小化解耦<br/>证明瞬时对偶间隙被估计误差平方二次绑定"]
    D --> E["纳什均衡策略求解：对称正则化博弈 Oracle<br/>输出兼顾多对数遗憾与秩自适应无维数依赖策略"]

关键设计¶

1. 瞬时对偶间隙的二次误差上界：摆脱 KL 闭式解的普适几何机制

以往在线 RLHF 分析能获得快速率完全依赖 KL 散度导出的 Softmax / Gibbs 显式解析形式。本文跳出特定函数形式，直接利用目标函数在 $\ell_1$ 范数下的 $\beta^{-1}$-强凸性。对于任意估计量 $\widehat{\bm{\Theta}}_t$ 诱导的贪婪纳什策略 $\hat{\pi}_t$，以及对手在真实环境下的最优对抗响应 $\tilde{\pi}$，瞬时对偶间隙 $X = \frac{1}{2} - J_\eta(\hat{\pi}, \tilde{\pi})$ 通过泰勒展开结合积分余项表示为一阶项与二阶项之和： $$X = \underbrace{-\mathbb{E}\left[\dot{\mu}(\bm{\phi}^\top \bm{\Theta}_\star \tilde{\bm{\phi}}) \bm{\phi}^\top \bm{E}_t \tilde{\bm{\phi}}\right]}_{(a)} + \underbrace{\mathbb{E}\left[\left[\int_0^1 (1-z) \ddot{\mu}(\bm{\phi}^\top (\bm{\Theta}_\star - z \bm{E}_t) \tilde{\bm{\phi}}) dz\right] (\bm{\phi}^\top \bm{E}_t \tilde{\bm{\phi}})^2\right]}_{(b)}$$ 其中 $\bm{E}_t := \bm{\Theta}_\star - \widehat{\bm{\Theta}}_t$ 为参数估计误差矩阵。针对一阶项 $(a)$，利用 $\mu$ 的中心对称性与 $\bm{E}_t$ 的反对称性消除自对弈项，再利用 $\ell_1$ 范数的积分概率度量（IPM）表示，证明 $|(a)| \le L_\mu D \sqrt{\mathbb{E}_{\bm{\phi}}[\|\bm{E}_t \bm{\phi}\|_2^2]}$，其中 $D := \sqrt{\mathbb{E}_{\bm{x}}[\|\hat{\pi}(\cdot \mid \bm{x}) - \tilde{\pi}(\cdot \mid \bm{x})\|_1^2]}$；再通过强凸性的零阶判定条件确立 $X \ge (2\eta\beta)^{-1} D^2$。综合二阶项控制，最终建立关于对偶间隙 $X$ 的自绑定二次不等式： $$X \le L_\mu \sqrt{(1 \wedge 2\eta\beta X) \mathbb{E}_{\bm{\phi}}[\|\bm{E}_t \bm{\phi}\|_2^2]} + \frac{L_\mu}{2} \mathbb{E}_{\bm{\phi}}[\|\bm{E}_t \bm{\phi}\|_2^2]$$ 求解该二次不等式即严格证明：只要存在强凸正则化（$\eta < \infty$），瞬时对偶间隙必定以二次形式（平方误差）被参数误差控制：$\mathrm{DGap}_\eta(\hat{\pi}_t) \le L_\mu (2 L_\mu \eta \beta + 1) \mathbb{E}_{\bm{\phi} \sim \hat{\pi}_t}[\|\bm{E}_t \bm{\phi}\|_2^2]$。

2. 贪心采样的多对数遗憾与鞅方差自绑定递推

在低维机制中，贪心采样（GS）算法无需显式乐观主义探索。通过特征多样性假设（探索策略 $\rho$ 满足特征协方差最小特征值 $\lambda_{\min} \ge C_{\min} > 0$），利用矩阵克罗内克积与覆盖引理（Coverage Lemma），将对标准正交基的椭圆势能转化为采样特征下的期望势能。由于标准椭圆势能引理仅能控制实现样本的势能之和，论文采用经验 Freedman 鞅差集中不等式处理期望势能与实现势能的偏差项： $$S_T = \sum_{t=1}^T \|\bm{v}_t\|_{\bm{V}_t^{-1}}^2 + \sum_{t=1}^T \left\{ \mathbb{E}_{t-1}[\|\bm{v}_t\|_{\bm{V}_t^{-1}}^2] - \|\bm{v}_t\|_{\bm{V}_t^{-1}}^2 \right\} \le A S_T + \widetilde{\mathcal{O}}(d^2 \log T)$$ 其中常数 $A \in (0, 1)$。解出此线性自绑定不等式后，成功消除了以往文献中剥皮论证（peeling argument）产生的双对数冗余阶，在无需假设逆 KL 且彻底消除 $e^{\mathcal{O}(\eta)}$ 指数级放大系数的前提下，推导出了 $\widetilde{\mathcal{O}}(\eta d^4 C_{\min}^{-1} (\log T)^2 \wedge d^2 C_{\min}^{-1/2} \sqrt{T})$ 的光滑过渡紧致遗憾界。

3. 高维机制下的低秩核范数正则化与探索-提交（ETC）

当环境特征维度 $d$ 极高（$d \gg 1$ 且 $T$ 处于中低样本范围）时，标准多项式 $d$ 依赖不可接受。针对反对称矩阵的固有低秩结构（$\mathrm{rank}(\bm{\Theta}_\star) \le 2r \ll d$），算法设计了 Explore-Then-Commit 架构：在初始 $T_0$ 步中由双方均执行探索策略 $\rho$ 并求解核范数正则化极大似然估计 $\widehat{\bm{\Theta}}_{T_0}$，随后完全提交至该经验纳什均衡策略。由于瞬时对偶间隙被估计误差平方控制，受提交阶段 $T \eta \beta \|\bm{E}_{T_0}\|_{\mathrm{op}}^2 \lesssim T \eta \beta \tilde{\kappa}^{-2} C_{\min}^{-4} \frac{r \log(d/\delta)}{T_0}$ 的驱动，最优平衡步数选取打破了经典 ETC 算法固有的 $\mathcal{O}(T^{2/3})$ 下界瓶颈，实现了秩自适应且无高维 $d$ 多项式依赖的 $\widetilde{\mathcal{O}}(C_{\min}^{-2} \sqrt{\eta r T} \wedge r^{1/3} C_{\min}^{-4/3} T^{2/3})$ 遗憾率。

损失函数 / 训练策略¶

在参数估计阶段，核范数惩罚负对数似然损失形式如下： $$\widehat{\bm{\Theta}} \leftarrow \arg\min_{\bm{\Theta} \in \mathrm{Skew}(d)} \frac{1}{T_0} \sum_{t=1}^{T_0} \left\{ \log(1 + e^{\bm{\phi}_t^{1\top} \bm{\Theta} \bm{\phi}_t^2}) - r_t \bm{\phi}_t^{1\top} \bm{\Theta} \bm{\phi}_t^2 \right\} + \lambda_{T_0} \|\bm{\Theta}\|_{\mathrm{nuc}}$$ 其中正规化系数理论设定为 $\lambda_{T_0} = \sqrt{\frac{32 L_\mu \log(4d/\delta)}{T_0}}$。由于反对称矩阵约束 $\bm{\Theta}^\top = -\bm{\Theta}$ 与核范数均为凸集与凸函数，该目标可通过无约束矩阵重参数化 $\bm{\Theta} = \frac{\bm{\Theta}' - \bm{\Theta}'^\top}{2}$ 并应用近端梯度下降或在线牛顿步（Online Newton Step, ONS）进行无偏凸优化求解。

实验关键数据¶

主实验¶

论文在合成双线性偏好博弈基准环境上进行了严谨的数值模拟验证。实验设定涵盖不同维度 $d \in \{5, 10\}$、候选动作集大小 $K \in \{20, 40\}$、反对称矩阵固有秩 $2r = 2$、谱范数 $S \in \{5, 10\}$ 以及横跨数个数量级的正则化系数 $\eta \in [10^{-2}, 10^4]$，时域固定为 $T = 10000$。所有指标在 20 个独立随机种子下取平均，评测贪心采样（GS）的累计最大最优响应遗憾（MBR-Regret）的相变轨迹。

实验环境配置	正则化系数 $\eta$	理论主导遗憾类型	拟合优度 $R^2$ ($\log T$ 模型)	拟合优度 $R^2$ ($\sqrt{T}$ 模型)	最终累积遗憾 $\mathrm{MBR\text{-}Reg}(T)$
$d=5, K=20, S=5$	$\eta = 0.01$ (强正则)	多对数 $(\log T)^2$	0.989	0.812	$14.2 \pm 2.1$
$d=5, K=20, S=5$	$\eta = 1.0$ (中等)	混合过渡相	0.945	0.923	$68.5 \pm 5.4$
$d=5, K=20, S=5$	$\eta = 1000$ (弱正则/无正则)	次线性 $\sqrt{T}$	0.784	0.994	$284.1 \pm 18.7$
$d=10, K=40, S=10$	$\eta = 0.01$ (强正则)	多对数 $(\log T)^2$	0.978	0.795	$38.6 \pm 4.3$
$d=10, K=40, S=10$	$\eta = 1.0$ (中等)	混合过渡相	0.892	0.951	$192.4 \pm 14.1$
$d=10, K=40, S=10$	$\eta = 1000$ (弱正则/无正则)	次线性 $\sqrt{T}$	0.731	0.991	$612.8 \pm 32.5$

消融实验¶

针对相变转折点 $\eta_{\mathrm{cross}}(d, T) = \frac{\kappa^{1/2} C_{\min}^{1/2}}{\beta} \frac{\sqrt{T}}{d^2 \log(T/d)}$ 与不同核心模块的理论依赖关系进行敏感度消融分析：

算法与理论配置变体	理论上界依赖关系	渐近遗憾阶数 ($T \to \infty$)	依赖项消除与理论性质
完整模型 (GS with IPM 二次界)	$\min\{\eta d^4 C_{\min}^{-1} (\log T)^2, d^2 C_{\min}^{-1/2} \sqrt{T}\}$	$\widetilde{\mathcal{O}}((\log T)^2 \wedge \sqrt{T})$	任意强凸正则通用，无 $e^{\mathcal{O}(\eta)}$ 爆炸
基线方案 Wu et al. (2025)	$\mathcal{O}(e^{9\eta} (\log T)^2)$	$\widetilde{\mathcal{O}}(e^{9\eta} (\log T)^2)$	仅限逆 KL 散度，$\eta$ 增大时发生指数级爆炸
线性误差界消融 (w/o 强凸二次性质)	$\mathcal{O}(d^2 C_{\min}^{-1/2} \sqrt{T})$	$\widetilde{\mathcal{O}}(\sqrt{T})$	退化为不可加速的一阶遗憾，无法获得多对数界
探索-提交架构 (ETC, $T_0 \propto T^{1/2}$)	$\mathcal{O}(C_{\min}^{-2} \sqrt{\eta r T})$	$\widetilde{\mathcal{O}}(\sqrt{r T})$	摆脱维度 $d$ 依赖，突破传统 ETC 的 $T^{2/3}$ 壁垒
传统 ETC 架构 (w/o 二次对偶间隙加速)	$\mathcal{O}(r^{1/3} C_{\min}^{-4/3} T^{2/3})$	$\widetilde{\mathcal{O}}(T^{2/3})$	采用一次界时的经典子最优均衡点

关键发现¶

强凸几何驱动的遗憾相变：实验完全证实了理论预测的相变现象。在小 $\eta$（强正则化）区间，对偶间隙被二次项主导，遗憾曲线呈现严格的对数级平缓增长；而在大 $\eta$（弱正则化或无正则化极限）区间，遗憾轨迹无缝过渡并饱和于 $\sqrt{T}$ 水平，且随着维度 $d$ 从 5 升至 10，相变临界点 $\eta_{\mathrm{cross}}$ 显著向更小的数值偏移（与 $d^{-2}$ 缩放比例精准契合）。
彻底根除指数级罚项：对比既往必须承受 $e^{\mathcal{O}(\eta)}$ 膨胀的 KL 专属理论，本文将对正则化强度 $\eta$ 的依赖完全转化为多项式依赖，并在大 $\eta$ 极限下严格恢复经典无正则博弈遗憾界。
高维低秩结构的有效压缩：在 ETC 机制下，对偶间隙的二次绑定效应将原本次优的 $T^{2/3}$ 遗憾直接提升至 $\sqrt{rT}$，充分证明了在上下文偏好对齐中利用反对称矩阵低秩性质的巨大样本复杂度优势。

亮点与洞察¶

非 KL 依赖的普适强凸统一性：论文首次跳出指数族与 Gibbs 形式的理论桎梏，通过强凸性与反对称几何建立了二次自绑定不等式。这一证明链条极为纯粹，能够无缝覆盖 Tsallis 熵、香农熵、$\chi^2$ 散度与通用 $f$-散度，为非传统正则化 RLHF 算法提供了坚实的理论护航。
偏好矩阵反对称性与 IPM 的优雅结合：将反对称误差项 $\bm{\phi}^\top \bm{E} \tilde{\bm{\phi}}$ 与对策策略差值通过 $\ell_1$-IPM 结合柯西-施瓦茨不等式解耦，不仅形式优美，而且为研究多智能体零和博弈中的泛函导数规避提供了极具参考价值的分析工具。
无显式乐观主义的贪心对齐可行性：证明了在满足自然特征多样性假设的实际大模型生成场景下，仅靠贪婪估计与被动覆盖即可获得对数遗憾，有力支持了工业界通过采样温度多样化替代复杂探索策略的经验实践。

局限与展望¶

计算 Oracle 的复杂度假设：算法理论上依赖能够精确求解群体对称纳什均衡的黑盒 Oracle。在真实连续动作空间或自回归生成策略的大规模 LLM 落地中，严格求解纳什均衡具有极高算力负担，后续亟需结合在线镜像下降（OMD）等一阶流式优化器进行近似求解扩展。
特征覆盖假设的条件依赖：多对数遗憾界的建立依赖探索策略协方差矩阵的最小特征值严格正下界 $C_{\min} > 0$。若在极端低秩或存在特征盲区的几何流形上，覆盖常数可能随维度恶化，如何放宽至局部抗集中（Local Anti-Concentration）条件是重要的开放理论方向。
离线与非对称博弈推广：当前成果聚焦于在线对称零和博弈下的双人自对弈体系。未来有望将该二次对偶间隙技术扩展至离线 RLHF 悲观原则估计，以及更一般的多阶段序贯马尔可夫博弈场景中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 突破了长期以来在线 RLHF 多对数遗憾严重受困于 KL 闭式解的理论壁垒，建立通用的强凸二次对偶间隙证明框架。
实验充分度: ⭐⭐⭐⭐ 理论推导严密完备，配有验证相变规律和理论上界缩放的合成数值模拟实验与开源代码。
写作质量: ⭐⭐⭐⭐⭐ 结构编排清晰，动机交代充分，数学推导与关键几何直觉阐述极其透彻连贯。
价值: ⭐⭐⭐⭐⭐ 为通用偏好学习、非 KL 正则化 RLHF 与低秩博弈对齐提供了奠基性的理论支持与收敛保障。

实验环境配置	正则化系数 \(\eta\)	理论主导遗憾类型	拟合优度 \(R^2\) (\(\log T\) 模型)	拟合优度 \(R^2\) (\(\sqrt{T}\) 模型)	最终累积遗憾 \(\mathrm{MBR\text{-}Reg}(T)\)
\(d=5, K=20, S=5\)	\(\eta = 0.01\) (强正则)	多对数 \((\log T)^2\)	0.989	0.812	\(14.2 \pm 2.1\)
\(d=5, K=20, S=5\)	\(\eta = 1.0\) (中等)	混合过渡相	0.945	0.923	\(68.5 \pm 5.4\)
\(d=5, K=20, S=5\)	\(\eta = 1000\) (弱正则/无正则)	次线性 \(\sqrt{T}\)	0.784	0.994	\(284.1 \pm 18.7\)
\(d=10, K=40, S=10\)	\(\eta = 0.01\) (强正则)	多对数 \((\log T)^2\)	0.978	0.795	\(38.6 \pm 4.3\)
\(d=10, K=40, S=10\)	\(\eta = 1.0\) (中等)	混合过渡相	0.892	0.951	\(192.4 \pm 14.1\)
\(d=10, K=40, S=10\)	\(\eta = 1000\) (弱正则/无正则)	次线性 \(\sqrt{T}\)	0.731	0.991	\(612.8 \pm 32.5\)

算法与理论配置变体	理论上界依赖关系	渐近遗憾阶数 (\(T \to \infty\))	依赖项消除与理论性质
完整模型 (GS with IPM 二次界)	\(\min\{\eta d^4 C_{\min}^{-1} (\log T)^2, d^2 C_{\min}^{-1/2} \sqrt{T}\}\)	\(\widetilde{\mathcal{O}}((\log T)^2 \wedge \sqrt{T})\)	任意强凸正则通用，无 \(e^{\mathcal{O}(\eta)}\) 爆炸
基线方案 Wu et al. (2025)	\(\mathcal{O}(e^{9\eta} (\log T)^2)\)	\(\widetilde{\mathcal{O}}(e^{9\eta} (\log T)^2)\)	仅限逆 KL 散度，\(\eta\) 增大时发生指数级爆炸
线性误差界消融 (w/o 强凸二次性质)	\(\mathcal{O}(d^2 C_{\min}^{-1/2} \sqrt{T})\)	\(\widetilde{\mathcal{O}}(\sqrt{T})\)	退化为不可加速的一阶遗憾，无法获得多对数界
探索-提交架构 (ETC, \(T_0 \propto T^{1/2}\))	\(\mathcal{O}(C_{\min}^{-2} \sqrt{\eta r T})\)	\(\widetilde{\mathcal{O}}(\sqrt{r T})\)	摆脱维度 \(d\) 依赖，突破传统 ETC 的 \(T^{2/3}\) 壁垒
传统 ETC 架构 (w/o 二次对偶间隙加速)	\(\mathcal{O}(r^{1/3} C_{\min}^{-4/3} T^{2/3})\)	\(\widetilde{\mathcal{O}}(T^{2/3})\)	采用一次界时的经典子最优均衡点