arXiv 2607.17823v1 · 发布 2026-07-20

$max$ @ $k$ 强化学习的理论基础

Theoretical Foundations of $max$ @ $k$ Reinforcement Learning

AUTHORS Riccardo Poiani, Martino Bernasconi, Andrea Celli

EVIDENCE max@k强化学习的理论基础与策略类表征

SCORE 0.8

GENERATED 2026-07-21 22:04:38 UTC

📝 TLDR

针对大推理模型在代码生成、定理证明等困难任务中广泛采用的 max@k 评估指标，本文在有限时域强化学习框架下开展首个系统性理论研究。结果表明 max@k 优化与标准期望回报最大化存在本质区别：一般情形下 Markov 策略不足以达到最优，需借助紧凑的历史状态增广；本文进一步量化了历史依赖与无历史依赖策略之间的性能差距，并设计了样本复杂度匹配信息论下界的高效算法。

🧭 速览

动机

max@k 已成为大模型推理的事实标准评估指标，但现有理论多关注期望回报最大化，对其学习的统计与结构性质缺乏系统理解。

方法

在有限时域 MDP 设定下分析 max@k 最优策略结构，提出紧凑历史增广使 Markov 策略恢复最优性，并设计达到最优样本复杂度的算法。

结果

证明 Markov 策略一般无法实现 max@k 最优，量化了历史依赖与 Markov 策略之间的性能差距，并使所提算法达到信息论下界。

结论

为 max@k 强化学习奠定理论基础，揭示其与标准 RL 在策略结构与统计难度上的本质差异，并提供可证明高效的学习方法。

📊 论文图表(共 3 张)

展开查看 3 张图

图 1 / 3:Figure 1: Visualization of the MDP that illustrates the sub-optimality of Markovian policies. Dashed edges denote stochastic transitions, and leaves are associated with the rewards at the end of the horizon.

图 2 / 3:Figure 2: Visualization of the MDP for the linear lower bound in K. There is a state s and two actions, a1 (blue) and a2 (red), which both lead to rewards of 1 and 0 with probabilities p and 1 −p, respectively.

图 3 / 3:Figure 3: MDP that is used as example to prove Proposition 3.

TL;DR

这篇论文首次在有限时域强化学习框架下为 $max$ @ $k$ 评估指标建立了系统理论，证明了一个关键洞察：标准 Markov 策略在 $max$ @ $k$ 目标下不再是最优的，需要借助一种紧凑的状态增广（记录"此前最大回报"与"当前累计回报"）才能恢复最优性。作者进一步证明 $max$ @ $k$ 学习的统计复杂度比标准 RL 高出 $K$ 倍，并给出了匹配信息论下界的近似规划与学习算法。

研究背景与动机

大推理模型（large reasoning models）在代码生成、定理证明、数学推理等困难任务上取得突破的关键之一，是采用了 $max$ @ $k$ 评估范式：模型一次性生成 $K$ 个候选响应，在 verifier 或测试用例的反馈下取其中奖励最高的那个作为最终输出。这种"允许重试、支持多尝试"的评估方式，与人类解决复杂问题时的自我修正、试错迭代过程高度吻合，已成为 OpenAI o 系列、DeepSeek-R1 等前沿推理系统的默认配置。

然而，现有强化学习训练理论几乎全部围绕期望回报最大化展开。当我们将 $max$ @ $k$ 视为目标函数时，一个根本性的数学困难浮现出来： $max$ @ $k$ 关于策略诱导的轨迹分布是非线性的——取 $K$ 个样本的最大值这一操作破坏了标准 RL 理论中"期望的线性结构保证 Markov 策略最优"的关键前提。具体而言，标准 RL 的核心结论（如 Policy Gradient 定理、Bellman 最优方程）都依赖于奖励的线性可加性，而 $max$ @ $k$ 中的 $max$ 运算符打断了这种线性结构，使得已有理论工具不再直接适用。

这种理论与实践的脱节造成了严重后果：当前主流的 RLHF 训练方法（如 PPO、GRPO）默认采用期望回报目标，即使在 $max$ @ $k$ 评估范式下也是如此。这是否会导致系统性次优？最优策略应该具备怎样的结构？学习它需要多少样本？这些问题在本文之前缺乏系统回答。

方法

论文的核心贡献在于从三个层面建立了 $max$ @ $k$ RL 的完整理论：规划（给定模型知道环境如何行动）、学习（通过交互发现环境）、以及两者的计算与统计复杂度。

问题形式化是理论分析的起点。论文将 $max$ @ $k$ 决策建模为一种具有 $K$ 次轨迹预算的有限时域过程：智能体在第 $i$ 次 rollout（ $i = 1, \dots, K$ ）中从初始状态 $s$ 出发，基于完整历史 $H_{h, i}$ 在每个时间步 $h$ 选择动作，最终性能度量为 $K$ 次累计回报的最大值期望。这一定义精确刻画了"生成 $K$ 个响应、取最优"这一实际评估流程。

第一个关键发现是 Markov 策略的失效。论文证明，在一般 MDP 中， $max$ @ $k$ 目标下的最优策略必须依赖历史信息。具体构造了一个双动作 toy MDP，表明历史依赖策略与纯 Markov 策略之间存在乘性常数级的性能差距：

π \in Π_{hist} max V_{1, 1}^{π} (s) \geq (1.24 - O (1/ K)) \cdot π \in Π_{M} max V_{1, 1}^{π} (s)

这个 1.24 的常数意味着，即使我们已知环境的所有转移概率和奖励，盲目使用标准 RL 方法训练出的 Markov 策略也可能比最优策略差超过 20%。

直觉上，这个结果来源于 $max$ @ $k$ 的非线性结构：当只有一次尝试时（ $K = 1$ ），策略只需关注期望回报；但当允许 $K$ 次尝试时，策略应该"多样化"自己的行为——在早期尝试中承担风险探索不同状态，以便在后继尝试中基于已有信息选择更有前景的方向。这种"条件化于历史"的行为模式天然超出了 Markov 策略的表达能力。

第二个关键发现是压缩定理（Compression Theorem）。虽然最优策略必须历史依赖，但作者证明全历史是冗余的——最优策略可仅依赖一个紧凑的三元组：

Φ (H_{h, i}) = (s_{h, i}, M_{i}, G_{h, i})

其中 $M_{i} = max_{j < i} G_{H, j}$ 是此前 $i - 1$ 次 rollout 中的最大累计回报（失败者的最佳成绩）， $G_{h, i}$ 是当前 rollout 的累计回报（当前候选的实时表现）。换言之，智能体只需要知道自己"现在在哪里"以及"之前最好的是什么水平"，就足以做出 $max$ @ $k$ 意义上的最优决策。

论文进一步证明这个压缩表示是最小必要的（Proposition 3）：去掉 $G_{h, i}$ （当前进度）或 $M_{i}$ （历史最佳）中的任意一项都会导致次优。这一发现具有重要的实践启示——它解释了为什么有效的推理系统（如 self-refinement、tree-of-thought）需要维护某种"最佳轨迹的摘要"，而不是记住完整的探索历史。

第三个关键结果是计算复杂性。基于上述压缩表示，规划问题可以形式化为一个扩展 MDP，其状态空间为 $X = S \times ⌈ H / κ ⌉ \times ⌈ H / κ ⌉$ 。论文通过从 Subset-Sum 问题的归约，证明了精确规划是 NP-hard 的（Theorem 2）——即使想要一个常数近似也计算不可行。但好消息是，作者给出了一个 FPTAS：通过将 $M$ 的取值均匀离散化为精度 $κ$ ，然后在离散化后的状态空间上执行标准的 backward induction，可以在 $O (K S^{2} A H^{3} / κ^{2})$ 时间内得到 $ϵ$ -最优策略。

学习层面的分析则揭示了统计复杂度的另一个维度。论文考虑 generative model 设置（学习者可以反复查询任意状态-动作对获取下一状态和奖励），给出了 $max$ @ $k$ 学习的极小极大下界：

E [τ_{δ}] \geq Ω (\frac{K S A H ^{3}}{ϵ ^{2}} lo g \frac{1}{δ})

与标准 RL 的 $Ω (S A H^{3} / ϵ^{2})$ 下界相比，这里多出了一个与 $K$ 成正比的因子。其直觉在于： $max$ @ $k$ 目标关注的是"稀有成功事件能否被 $K$ 次尝试捕获"，这要求对转移概率的估计精度提升 $K$ 倍。

论文进一步给出了一个匹配下界的学习算法（Theorem 4）：对每个 $(s, a)$ 独立采样约 $m$ 次构建经验转移核 $\overset{p}{^}$ ，在经验 MDP 上求解压缩策略。选取适当的 $m$ 和离散化精度 $κ = O (ϵ / H)$ 后，算法的样本复杂度主项恰好是 $\tilde{O} (K S A H^{3} / ϵ^{2})$ ，与信息论下界匹配。

实验与结果

作为纯理论论文，本文没有在具体基准或大模型上进行经验实验。理论结果的"实验验证"体现为精心设计的反例 MDP 和紧的复杂度界论证。

论文构建了三类关键反例：第一类是用于证明 Markov 策略次优性的双动作 toy MDP，通过解析计算展示 1.24 倍的性能差距；第二类是 $K = 2$ 场景下的压缩性反例，表明同时丢弃 $G$ 或 $M$ 会导致最优值函数下降；第三类是用于下界证明的"低成功概率"构造，通过设计一个成功概率为 $p$ 的稀有事件来论证 $K$ 倍统计开销的必要性。

值得注意的是，虽然缺乏与大模型实验的结合，但论文在理论层面提供了完整且紧密的结果：规划问题的 NP-hard 下界与 FPTAS 上界形成鲜明对比，学习的样本复杂度下界与上界在主项上完全匹配（仅差 $lo g$ 因子）。这种"极小极大紧性"是理论论文质量的标志，表明作者对问题结构的理解是彻底的。

讨论与可借鉴点

这篇论文为大推理模型时代的 RL 训练理论填补了关键空白。它最重要的贡献或许不是某个具体算法，而是一套概念框架：在 $max$ @ $k$ 评估范式下，我们需要重新审视"最优策略是什么样子"这一基础问题，而答案指向了历史依赖和状态压缩这一方向。

从实践角度，论文揭示的设计原则值得关注。压缩历史 $Φ (H_{h, i}) = (s_{h, i}, M_{i}, G_{h, i})$ 恰好对应了许多成功推理系统的内在机制：MCTS 中维护的"最佳路径评分"正是 $M_{i}$ 的角色，而 rollouts 过程中的实时回报累加则是 $G_{h, i}$ 。论文为这些经验设计提供了理论层面的解释——它们并非启发式技巧，而是 $max$ @ $k$ 最优性的必要条件。

局限性方面，论文的分析建立在有限时域 MDP 和 generative model 的假设上，与大模型的在线交互学习场景存在差距。奖励归一化（ $r_{h} \in [0, 1]$ ）的假设在实践中也未必成立。此外，精确规划与近似规划之间的复杂性鸿沟（NP-hard vs. FPTAS）暗示，即使有理论保证，实际部署时仍需在近似精度和计算开销间谨慎权衡。

未来的开放问题包括：在线/前向交互设定下的极小极大学习率、非生成式模型（如真实环境交互）下的样本复杂度下界、以及计算复杂性是否达到 PSPACE-complete。这些问题的答案将进一步完善 $max$ @ $k$ RL 的理论图景，并为下一代推理强化学习系统的设计提供更坚实的基础。

摘要

强化学习是现代大型推理模型的核心技术。通常，对于代码生成和定理证明等困难任务，智能体通过生成 $K$ 个响应而非单个响应来进行评估，并使用诸如 $max$ @ $k$ 等支持重试的指标来衡量性能。尽管此类准则在实际中非常重要，但其在学习方面的理论基础仍然有限。在本文中，我们对有限时域强化学习中的 $max$ @ $k$ 学习问题进行了理论研究。我们证明，优化 $max$ @ $k$ 目标与标准的期望回报最大化在根本上有所不同。具体而言，我们证明了马尔可夫策略通常是不充分的，识别出一种紧凑的状态增广方法以恢复最优性，并显式刻画了历史依赖策略与非历史依赖策略之间可能出现的性能差距。此外，我们证明学习 $max$ @ $k$ 最优策略在统计上比标准强化学习更为困难，并给出一个能达到最优样本复杂度率的高效算法。

Abstract

Reinforcement Learning is a cornerstone technique for modern large reasoning models. Usually, for difficult tasks such as code generation and theorem proving, the agent is evaluated by generating $K$ responses rather than sampling a single response, and performance is then measured using a retry-aware metric such as $max$ @ $k$ . Despite their practical importance, the theoretical foundations of learning under such criteria remain limited. In this work, we provide a theoretical study of the $max$ @ $k$ learning problem in finite-horizon reinforcement learning. We show that optimizing the $max$ @ $k$ objectives is fundamentally different from standard expected-return maximization. In particular, we prove that Markovian policies are in general insufficient, identify a compact state augmentation that restores optimality, and explicitly characterize the performance gap that can arise between history-dependent and non-history-dependent policies. Moreover, we show that learning $max$ @ $k$ -optimal policies is statistically harder than standard reinforcement learning and provide an efficient algorithm that achieves the optimal sample complexity rate.

论文详细总结（自动生成）

《 $max$ @ $k$ 强化学习的理论基础》论文总结

一、核心问题与整体含义

研究动机： $max$ @ $k$ 已成为大推理模型（代码生成、定理证明、数学推理等）在困难任务上评估的"事实标准"——允许模型生成 $K$ 个响应并取其中最高奖励的回报。然而现有 RL 训练理论几乎全部围绕期望回报最大化展开，将 $max$ @ $k$ 视为评估指标，直接套用标准 RL 优化方法已被多篇工作指出存在次优性。
关键缺口：
$max$ @ $k$ 目标关于策略诱导的轨迹分布是非线性的（取 order statistic），破坏了标准 RL 理论中"期望的线性 = Markov 策略最优"的关键前提。
没有系统的理论刻画：在什么意义上 $max$ @ $k$ 与标准 RL 本质不同？最优策略长什么样？学习它到底需要多少样本？规划问题是否可高效求解？
本文目标：在有限时域 MDP 框架下，为 $max$ @ $k$ 学习建立完整的理论基础——策略结构、规划可计算性、统计复杂度的上下界。

二、方法论

2.1 问题形式化（Section 2）

形式化 $max$ @ $k$ 决策过程：智能体拥有 $K$ 次轨迹预算，每次从同一初始状态 $s$ 出发，在每步 $h$ 、第 $i$ 次 rollout 时基于完整历史 $H_{h, i}$ 选动作。性能度量为

E_{π} [i \in [K] max h = 1 \sum H r_{h} (s_{h, i}, a_{h, i}) s_{1, i} = s \forall i] .

给出 Bellman 递推式，定义最优值函数 $V_{h, i}^{⋆} (H_{h, i}) = sup_{π \in Π_{hist}} V_{h, i}^{π} (H_{h, i})$ 。

2.2 规划层面的核心结论（Section 3）

结论 1（命题 1）：在 $max$ @ $k$ 下Markov 策略不再最优，且两类策略之间的性能差距是乘性常数——存在实例使得

π \in Π_{hist} max V_{1, 1}^{π} (s) \geq (1.24 - O (1/ K)) \cdot π \in Π_{M} max V_{1, 1}^{π} (s),

证明历史依赖策略能带来不可忽略的实质性收益。

结论 2（命题 2，关键压缩定理）：虽然最优策略必须历史依赖，但全历史是冗余的——最优策略可仅依赖压缩历史

Φ (H_{h, i}) = (s_{h, i}, M_{i}, G_{h, i}),

其中 $M_{i} = max_{j < i} G_{H, j}$ （此前 $i - 1$ 次 rollout 中的最大累计回报）， $G_{h, i}$ 为当前 rollout 的累计回报。记此类策略集合为 $Π_{C}$ ，并证明 $Π_{C}$ 中存在确定性最优策略。

结论 3（命题 3）：上述压缩表示是最小必要的——去掉 $G$ 或 $M$ 任意一项都会导致次优。

近似规划算法（定理 1）：直接对压缩历史做 backward induction 因状态空间 $S \cdot ∣ B ∣ \cdot ∣ C_{h} ∣$ 可指数级而不可行。因此对 $M$ 的奖励函数做精度为 $κ$ 的均匀离散化得到 $M_{κ}$ ，再在 $M_{κ}$ 上求解。得到

∣ V_{h, i}^{⋆} (H_{h, i}) - V_{h, i}^{\tilde{μ}_{κ}^{⋆}} (H_{h, i}) ∣ \leq 2 κ H,

算法复杂度 $O (\frac{K S ^{2} A H ^{3}}{κ ^{2}})$ ，取 $κ = ϵ / H$ 即得 $ϵ$ -最优策略，多项式时间。

精确规划的不可近似性（定理 2）：通过从 Subset-Sum 的规约证明，精确规划在常规模型下是 NP-hard 的——即使反多项式级近似也不可计算；这是 FPTAS 紧性的论证。

2.3 学习层面的核心结论（Section 4）

PAC 框架：学习者拥有 generative model（生成式模型），目标是 $(ϵ, δ)$ -正确返回 $\overset{π}{^} \in Π_{C}$ 。

下界（定理 3）：对任意 $(ϵ, δ)$ -正确算法，

E [τ_{δ}] \geq Ω (\frac{K S A H ^{3}}{ϵ ^{2}} lo g \frac{1}{δ}),

即 $max$ @ $k$ 学习在统计上比标准 RL 难 $K$ 倍。直觉：稀有成功事件被 $K$ 次 rollout "放大"，因此需要 $K$ 倍更精细的概率估计。

上界（定理 4）：
均匀采样每个 $(s, a, h)$ 约 $m$ 次，构建经验转移核 $\overset{p}{^}_{h}$ ；
在 $\hat{M}_{κ} = (S, A, H, {\overset{p}{^}_{h}}, {\tilde{r}_{h, κ}})$ 上做 backward induction。
取 $m = \tilde{O} (\frac{S K ^{2} H ^{2} lo g ( 1/ δ ) + K S A H ^{3} lo g ( 1/ δ )}{ϵ ^{2}})$ ， $κ = O (ϵ / H)$ ，得到时间齐次情形样本复杂度

\tilde{O} (A S^{2} K^{2} H^{2} lo g \frac{1}{δ} + \frac{K S A H ^{3}}{ϵ ^{2}} lo g \frac{1}{δ}),

非齐次情形为 $\tilde{O} (A S^{2} K^{2} H^{3} lo g \frac{1}{δ} + \frac{K S A H ^{4}}{ϵ ^{2}} lo g \frac{1}{δ})$ 。

主项 $K S A H^{3} / ϵ^{2}$ 与下界匹配（除 $lo g$ 因子），得到紧的极小极大率。

2.4 算法流程（Section 4.3）

步骤 1：对每个 $(s, a, h)$ （齐次情形仅 $(s, a)$ ）独立采样 $m$ 个下一状态；
步骤 2：构造经验转移 $\overset{p}{^}_{h}$ 与离散化奖励 $\tilde{r}_{h, κ}$ ；
步骤 3：在 $\hat{M}_{κ}$ 的增广状态空间 $X = S \times ⌈ H / κ ⌉ \times ⌈ H / κ ⌉$ 上用 backward induction 求最优压缩策略 $\overset{μ}{^}$ 。

三、实验设计

本文为纯理论论文，无任何经验实验或基准测试。所有结论以定理（Theorem）、命题（Proposition）、引理（Lemma）形式给出。
"实验对象"是精心构造的反例 MDP：
用于证明 Markov 策略次优性的双动作 toy MDP（图 1）；
用于证明"忽略 $G$ 或 $M$ 任一即次优"的 K=2 反例 MDP（图 3）；
用于下界证明的"低成功概率"构造（图 2）。
没有任何与 SOTA 经验方法（如 PPO、GRPO、inference-aware RL 估计器等）的实验对比。

四、资源与算力

未涉及任何训练或推理算力。论文未提及 GPU 型号、机器数量或运行时长。
算法复杂度以理论时间复杂度形式给出（如 $O (K S^{2} A H^{3} / κ^{2})$ ），而非实测墙钟时间。

五、实验数量与充分性

不适用——无传统意义上的实验组、消融或对比。
替代的"经验强度"由以下几类理论构造构成：
反例 MDP 的设计与逐案分析（Proposition 1、Proposition 3）；
紧性论证（Theorem 1 给出上界 + Theorem 2 给出 NP-hard 下界 → 精确规划意义下不可能）；
学习复杂度（Theorem 3 下界 + Theorem 4 上界 → 极小极大匹配）；
客观性方面：所有结果附带完整证明（附录 A、B、C 共 ~22 页），并明确指出假设条件（如 $δ \leq 1/16$ 、 $H$ 可被 4 整除、 $ϵ$ 足够小等）。

六、主要结论与发现

1. 策略结构层面： $max$ @ $k$ 下 Markov 策略严格次优，且与最优策略存在乘性常数级（≥1.24）性能差距。

2. 最小充分状态增广：最优策略只需条件于 $(s, M_{i}, G_{h, i})$ ——历史中最优信息是"此前最大回报"与"当前累计回报"，其余历史冗余。

3. 计算可处理性：精确规划 NP-hard，但存在 FPTAS（ $κ$ -离散化 + backward induction），运行时间 $poly (1/ ϵ, K, S, A, H)$ 。

4. 统计复杂度： $max$ @ $k$ 学习在 generative model 下的极小极大样本复杂度为

\tilde{Θ} (\frac{K S A H ^{3}}{ϵ ^{2}} lo g \frac{1}{δ}) (齐次情形),

即比标准 RL 多一个与 rollout 数 $K$ 成线性的因子。

5. 与实践的联系：自适应推理（self-refinement、tree-of-thought、population-level refinement）可视为历史依赖 $Π_{hist}$ 的实现；而"压缩历史保留摘要而非全历史"恰好与实用推理系统中"保留上一轮最佳但丢弃中间过程"的设计哲学对应。

七、优点

问题重要且定位精准：第一次为 $max$ @ $k$ 这一被 LLM 训练与评估广泛采用却缺乏理论的指标建立了系统理论。
结果完整、层次清晰：从策略结构（必要性）→ 压缩表示（充分性）→ 精确不可近似（计算下界）→ 近似算法（计算上界）→ 学习下界/上界（统计极小极大），形成闭环。
技术深度高：通过 Subset-Sum 归约证明 NP-hard，借助 reverse Pinsker、Garevier 等工具做变化测度论证，利用扩展 MDP（augmented state $X$ ）将 $max$ @ $k$ 折回标准有限时域 RL 从而复用经典仿真引理。
匹配的下界与上界： $Ω (\cdot)$ 与 $\tilde{O} (\cdot)$ 在主项上一致，避免了"只证上界"或"只证下界"类工作的常见缺陷。
与实践强关联：作者明确将理论结果与 self-refinement、MCTS、population-level refinement 等推理范式对接，给出可解释的设计含义（"压缩历史即摘要"）。

八、不足与局限

设置受限：仅在有限时域 MDP + 生成式模型（generative model）下分析，未涉及 forward/online 交互设置（作者本人也在 Section 4.1 末尾明确指出是未来工作）。
奖励归一化假设：要求 $r_{h} \in [0, 1]$ ；实际 LLM 训练中的奖励多为非归一化或稀疏奖励。
非齐次情形上界多出 $H$ 因子（ $K S A H^{4} / ϵ^{2}$ ），与下界 $K S A H^{3} / ϵ^{2}$ 间尚有 $H$ 差距，未做到完全匹配。
计算复杂度界：FPTAS 时间复杂度含 $1/ κ^{2}$ ，对 $ϵ$ 较敏感；实际部署到大模型场景的可扩展性未讨论。
无实证验证：作为纯理论论文，所有"实验"均为反例构造，未在大模型推理或 RLHF 基准（如 MATH、HumanEval、APPS 等）上做实证检验理论预言。
应用落地差距：理论给出的最优策略依赖精确的 $(M_{i}, G_{h, i})$ 追踪，需要环境反馈机制支持；在 LLM 推理场景下 verifier 信号未必可微或可回溯。
作者声明的开放问题：(1) 计算复杂性是否 PSPACE-complete；(2) 在线/前向交互设定下的极小极大率；(3) 非生成式模型下的样本下界。

（完）

✨ 编译论文

点「✨ 编译」开始,LLM 会按 Polaris 风格翻译并把图片/表格嵌到对应位置。结果存到浏览器 localStorage,下次访问自动加载。