让大模型在不依赖人工标注的情况下，实现高效多步推理。
Reasoning without Regret
- 用逆向自适应奖励机制，把最终结果反馈转化为每一步的指导信号。
- 理论证明算法在 $O((R_{ ext{max}}/Δ)"log(1/ε))$ 次迭代内达到高精度。
- 适用于无需人工标注的复杂任务推理，如 DeepSeek R1 的理论基础。
链式思维推理使大语言模型能通过将问题求解建模为序列决策过程来处理多步任务。基于结果的奖励仅对最终答案提供反馈，虽表现优异，但面临信用分配困难与收敛缓慢的问题；而基于过程的奖励可提供高效的步骤级反馈，通常需昂贵的人工标注。本文提出无后悔框架——反向自适应奖励塑造（BARS），将稀疏的结果奖励转化为有效的过程信号。BARS利用终端状态先验和覆盖树生成稀疏奖励，并防止策略剥削。结合贝尔曼收缩与 $(Δ, ε)$-间隙奖励，我们的后向欧拉求解器在 $O((R_{ ext{max}}/Δ)"log(1/ε))$ 次迭代中达到 $ε$-精度，且在 $T$ 轮中的动态遗憾为 $O("log T)$。分析基于泛化链、连续缩放极限与非线性费曼-卡克斯边界，将近期基于结果的方法的实证成功与中间监督的优势相联系。该工作首次为结果奖励塑造提供了严格的无后悔算法，为 DeepSeek R1 的实证成功提供了理论支撑。
原文摘要 · Abstract (English)
Chain-of-thought reasoning enables large language models to solve multi-step tasks by framing problem solving as sequential decision problems. Outcome-based rewards, which provide feedback only on final answers, show impressive success, but face challenges with credit assignment and slow convergence. In contrast, procedure-based rewards offer efficient step-level feedback, but typically require costly human supervision. We introduce \emph{Backwards Adaptive Reward Shaping} (BARS), a no-regret framework that converts sparse outcomes-based rewards into effective procedure-based signals. BARS uses sparse rewards generated from terminal-state priors and cover trees to scale rewards while preventing exploitation. With Bellman contraction and $(Δ, ε)$-gap rewards, our backward Euler solver achieves $ε$-accuracy in $O\left((R_{\max}/Δ)\log(1/ε)\right)$ iterations with $O(\log T)$ dynamic regret over $T$ rounds. Our analysis, based on generic chaining, continuous scaling limits, and non-linear Feynman-Kac bounds, connects recent outcome-based methods' empirical successes with the benefits of intermediate supervision. Combined, this provides the first rigorous no-regret algorithm for outcome reward shaping, providing a theoretical foundation for the empirical success of DeepSeek's R1.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。