TL;DR

传统的 LLM 强化学习（RL）后训练正面临一个尴尬的“能力天花板”：它往往只能微调模型已有的模式，而无法像 AlphaZero 在棋类游戏中那样自主“进化”出超越人类的新策略。本文指出，问题的根源在于我们错误地将动作历史当成了状态。通过重新引入经典的 Markov 状态 (Markov States)，研究者在复杂逻辑任务中实现了从 0 到 76% 的性能跨越，并从理论上证明了这种方法能带来指数级的采样效率提升。

1. 痛点：为什么 LLM 的 RL 只是在“炒冷饭”？

在目前的 RL 实践（如 PPO, GRPO）中，LLM 实际上是在处理一个不断膨胀的历史序列 $(x,y_1,y_2,...,y_{h-1})$。

• 维度灾难：随着推理步数增加，动作空间呈指数级增长。
• 信噪比极低：历史记录中包含大量与当前决策无关的冗余信息。
• 能力瓶颈：Foster 等人的最新理论表明，除非预训练模型已经覆盖了最优路径，否则这种基于全量历史的 RL 搜索成本高得不可接受。

作者通过一个简单的 Combination Lock (组合锁) 实验揭示了真相： 基于 Markov 状态的 Agent 在 3 万步内就能解开锁，而基于全量动作序列的 Agent 在 80 万步后依然一无所获。

2. 核心：重塑状态表征 (Markovian Methodology)

本文的核心直觉非常纯粹：状态应该是未来决策的充分统计量，而不应是过去所有动作的堆砌。

2.1 架构转变

作者对比了两种模式：

1. Action-Sequence Model：输入为 $History=\{a_1,a_2,...,a_{h-1}\}$。
2. Markovian Model：引入一个转移函数 $P$，使得 $s_{h+1}=P(s_h,a_h)$。模型只观测 $s_h$ 来产生 $a_h$。

在实际应用中，这个转移函数 $P$ 可以是：

• 外部环境：如代码编译器或物理模拟器。
• 规则引擎：如数学定理或游戏规则。
• 状态学习器：一个专门训练用于预测“下一步看板状态”的小型 LLM。

3. 实验战绩：全方位突破天花板

研究团队在 Sudoku (数独)、Sokoban (推箱子) 和 Futoshiki (不等式谜题) 三大逻辑任务上进行了严苛测试。

3.1 惊人的性能提升

在 Sokoban 任务中，传统的动作序列模型几乎完全无法处理长程依赖，成功率低至 2.5%。而一旦引入 Markov 状态，成功率飙升至 76.1%。

| 方法 | Sudoku | Sokoban | Futoshiki | | :--- | :--- | :--- | :--- | | Action-seq. (传统) | 93.5 | 2.3 | 0.1 | | Markov (本文) | 97.1 | 76.1 | 75.0 |

3.2 强悍的 OOD 泛化

最令人兴奋的是，即便是在比训练集更复杂的场景中（例如更多的空格、更深的推演步骤），Markov 模型依然表现出极强的鲁棒性。这证明了模型真正理解了“游戏规则”（由状态驱动），而非仅仅记住了“动作序列”。

上图显示：传统模型在 scaling 时很快达到瓶颈，而 Markov 模型则通过采样显著提升了成功率。

4. 深度洞察：为什么这有效？

1. 信用分配 (Credit Assignment)：在 Markov 架构下，奖励可以直接挂钩到特定的状态-动作对，而不是缠绕在冗长的历史中。
2. 搜索空间折叠：Markov 状态将指数级的“历史树”折叠成了线性的“状态链”。
3. 消除伪相关：冗长的历史往往包含干扰，让模型学习到错误的因果关系。实验证明，即便是能看到历史的模型，在训练完成后也主要依赖“当前状态”进行决策。

5. 总结与展望

本文的价值不仅在于刷新了几个谜题的 SOTA。它触及了 Generative AI 长期以来被忽视的一个根本问题：Transformer 的自回归特性是否天然不适合做 RL？

核心启示：

• 对于产品经理/工程师：在设计 Agent 系统时，应优先考虑如何显式地维护“系统状态”（如任务清单、代码快照），而非仅仅堆叠对话历史。
• 对于研究者：未来的 LLM 架构演进可能会朝着“世界模型”与“推理策略”解耦的方向发展，而 Markov 性质正是这一解耦的桥梁。

局限性：目前实验主要集中在可明确定义状态的逻辑任务中。如何在开放域对话或模糊的创意写作中定义有效的 Markov 状态，将是下一个重大的研究课题。