Agentic Transformer 可证明通过强化学习学习搜索

树搜索是许多语言智能体推理和决策任务背后的核心抽象：智能体必须探索行动，记住失败，并回溯到有希望的替代方案。然而，我们缺乏对基于 Transformer 的策略如何从强化学习（RL）的训练动态中获得这种搜索能力的理论理解。我们在随机 $k$ 树环境中研究这个问题，其中代理 Transformer 仅通过交互观察其轨迹历史，并因到达隐藏的叶目标节点而获得最终奖励。我们首先构建一个实现随机深度优先搜索（DFS）的双头 Transformer：一个头跟踪先前的操作，而另一个头检测失败结果并触发回溯。然后，我们分析了深度课程下政策梯度的训练动态，表明相同的 DFS 机制是在没有专家论证的情况下从稀疏强化反馈中分阶段出现的。由此产生的策略表现出深度泛化：仅在深度 $1$ 和深度 $2$ 树上进行训练后，它在更深的完整树上取得了成功。我们进一步表明，在不平衡的目标分布下，折扣回报会导致优先考虑较高概率分支的排名 DFS 策略。总的来说，我们的结果确定了基于 Transformer 的搜索的机械范式，其中注意力头专门并合作从上下文中提取与决策相关的痕迹，并通过 RL 训练将它们转换为代理动作选择。