结构诱导信息用于重根 Levin 树搜索：深度解读

背景

在复杂单智能体确定性问题的求解中，基于子目标（Subgoal-based）的策略树搜索是一种高效的方法。这类方法通过引入策略来引导搜索过程，从而在庞大的状态空间中寻找最优路径。然而，传统方法往往依赖于显式的子目标生成机制。这种显式生成不仅带来了巨大的计算开销，还严重限制了算法在大规模环境中的可扩展性。

Levin 树搜索（Levin Tree Search, LTS）及其变体 $\sqrt{\text{LTS}}$ 旨在解决此类搜索效率问题，但原有的框架在处理重根（Rerooting）操作时，通常假设重根器是预先给定或手工设计的，缺乏对自动学习重根策略的深入探索。本文针对这一局限，提出了一种利用学习到的“重根器”来隐式分解问题的新框架，旨在降低计算开销并提升搜索的可扩展性。

核心内容

本文提出了一种基于学习到的重根器（Rerooter）的框架，用于改进 $\sqrt{\text{LTS}}$ 算法。该框架的核心思想是通过重根器将复杂问题隐式地分解为“软子任务”（soft subtasks），从而避免显式重构和推理生成的子目标所带来的高昂成本。

1. 重根器的三种设计

为了克服以往工作仅关注给定或手工设计重根器的形式化保证的局限，本文提出了三种不同的重根器设计方案：

• 基于聚类的重根器（Clustering-based Rerooter）： 该设计利用全局状态空间的结构特性。通过分析状态空间的分布和聚类特征，重根器能够识别出具有相似动态特性的状态区域，从而在搜索过程中更智能地选择重根点。
• 基于启发式的重根器（Heuristic-based Rerooter）： 该设计利用学习到的“剩余成本估计”（cost-to-go estimates）。通过预测从当前状态到达目标状态所需的预期成本，重根器可以优先选择那些更有希望快速收敛到目标的节点作为重根点。
• 混合重根器（Hybrid Rerooter）： 该设计结合了上述两种信号，既利用全局状态空间的结构信息，又结合学习到的剩余成本启发式信息，以在复杂环境中实现更稳健的性能。

2. 框架优势

• 隐式分解： 与显式生成子目标不同，重根器隐式地将问题分解为软子任务。这意味着系统不需要显式地重建子目标并进行复杂的逻辑推理，从而显著降低了计算开销。
• 可扩展的搜索努力分配： 通过避免显式子目标的重构，该框架能够更灵活、高效地分配搜索资源，使得算法能够扩展到更复杂的环境。

3. 实验结果

在多个测试领域进行的实证研究表明：

• 可扩展性： 基于重根的方法能够扩展到基于子目标的策略树搜索所无法处理的复杂环境。
• 训练效率： 在这些领域中，该方法实现了最先进的在线训练效率（online training efficiency），证明了其在实际应用场景中的有效性。

关键要点

• 解决痛点： 传统基于子目标的策略树搜索因显式子目标生成导致的高开销和可扩展性差的问题。
• 核心机制： 引入学习到的“重根器”，通过 $\sqrt{\text{LTS}}$ 算法隐式地将问题分解为软子任务。
• 三种重根器设计：
  • 利用全局状态空间结构的基于聚类的重根器。
  • 利用学习到的剩余成本估计的基于启发式的重根器。
  • 结合上述两者的混合重根器。
• 主要优势： 避免了显式重构和推理子目标，显著降低了计算开销，实现了搜索努力的更优分配。
• 性能表现： 在子目标方法失效的复杂环境中表现优异，并达到了最先进的在线训练效率。

意义与影响

这项研究在强化学习和规划领域具有重要的理论和实践意义。首先，它提供了一种新的视角来处理复杂状态空间中的搜索问题，即通过隐式的软子任务分解来替代显式的子目标生成，这在计算效率上是一个显著的进步。

其次，提出的三种重根器设计为如何结合结构信息（聚类）和预测信息（启发式）提供了具体的范例，这对于设计更智能的搜索算法具有参考价值。

最后，实证结果表明该方法在复杂环境中的优越性，意味着在实际应用如机器人导航、游戏AI或自动化规划中，可以采用更高效的学习和搜索策略，从而在资源受限或时间敏感的场景下取得更好的性能。这为未来开发更 scalable（可扩展）的单智能体决策系统奠定了坚实的基础。