Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

Transformer 可以通过微调获得思维链（Chain-of-Thought, CoT）能力，从而解决复杂的推理任务。强化学习（RL）和监督微调（SFT）是实现这一目标的两种主要方法，但它们背后的机制及差异在理论上仍不清晰。本文针对单层 Transformer 学习具有类似 CoT 的中间监督的 $k$-稀疏布尔函数的情形，专门研究了上述问题。具体而言，我们考虑那些可递归分解为固定 2-稀疏布尔函数的 $k$-稀疏布尔函数。我们分析了通过 RL 或带有 CoT 的 SFT 微调 Transformer 的学习动态，以确定其能够被严格证明学会这些函数的充分条件。我们验证了这三个基本示例——$k$-PARITY、$k$-AND 和 $k$-OR 满足这些条件，从而证明了这两种方法均具备学习能力。值得注意的是，我们发现 RL 与 SFT 表现出截然不同的学习行为：RL 是同时学习整个 CoT 推理链，而 SFT 则是逐步地、按步骤学习 CoT 链。总体而言，我们的研究结果为理解 RL 和 SFT 的内在机制提供了理论洞见，并揭示了二者在激发 Transformer 的 CoT 能力方面的差异。

论文试图解决的问题是：在让Transformer模型获得链式思维（Chain-of-Thought, CoT）能力的过程中，监督微调（SFT）和强化学习（RL）这两种主流方法的内在机制有何不同？特别是，它们是否都能有效激发模型对复杂推理任务的学习能力，以及这些方法在理论上如何工作。这个问题目前在理论层面尚不清晰，因此具有研究的新颖性。

论文提出通过分析一类可递归分解为固定2-稀疏布尔函数的k-稀疏布尔函数，利用带中间监督（类比CoT标签）的单层Transformer模型，研究SFT与RL在学习过程中的动态差异。关键创新在于从理论角度证明了两种方法均可学会目标函数，并揭示了根本性的学习机制差异：RL倾向于同时学习整个CoT推理链，而SFT则是逐步、逐层地构建推理链。

论文在三个典型布尔函数（k-PARITY、k-AND、k-OR）上验证了理论条件成立，证明了两种方法的可学习性。实验设计基于理想化但可分析的模型（单层Transformer），并引入中间监督信号模拟CoT标注，便于理论分析。虽然未提及真实数据集或开源代码，但其理论框架为后续实证研究提供了指导。值得深入的方向包括将该理论推广到深层模型、更复杂的推理任务，以及设计融合RL与SFT优势的混合训练策略。

1. Large Language Models are Zero-Shot Reasoners (2022) 2. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (2022) 3. Self-Consistency Improves Chain of Thought Reasoning in Language Models (2023) 4. Tree of Thoughts: Deliberate Problem Solving with Large Language Models (2023) 5. Reinforcement Learning from Human Feedback: A Brief Survey (2023)