通过课程 II 学习推理：组合概括

组合泛化，即通过组合更简单的子问题的解决方案来解决复杂问题的能力，是自然智能和人工智能的基本能力，也是思想链推理的关键机制。然而，组合泛化的理论基础仍然知之甚少：何时以及为什么将问题分解为多个部分会比直接解决问题产生更有效的学习？我们通过学习模拟半自动机（预测顺序计算 $T$ 步骤的结果）的典型问题来研究这个问题，半自动机是一种捕获状态跟踪、常规语言识别和模块化算术的模型。我们证明，基于自动课程的方法建立在本系列的第一部分的基础上，递归地将较长的序列分解为较短的子问题，学习解决它们，并组合解决方案，与直接方法相比，实现了显着更好的统计复杂性。 (i) 对于受监督的 微调 (SFT) 启发的设置，其中学习者收到有关计算中间状态的交互式反馈，课程有助于仅从 $2^{\mathcal{O}(\sqrt{\log T})}$ 监督词元进行学习；即序列长度 $T$ 的次多项式，克服直接模拟所需的 $Ω(T)$ 词元障碍。 (ii) 对于受可验证奖励的强化学习 (RLVR) 启发的设置，其中学习者使用结果验证器改进预先训练的参考模型，我们表明课程将对参考模型的要求从全序列长度 $T$ 的覆盖范围降低到较短块长度 $B \ll T$ 的覆盖范围，这是一个指数较弱的条件。