技术摘要：用于重根化 Levin 树搜索的结构诱导信息

问题定义

在单智能体确定性环境中，复杂的离散规划问题仍然难以解决。虽然像 Levin 树搜索（LTS）和策略引导启发式搜索（PHS*）这样的策略引导树搜索方法提供了关于搜索效率的理论保证，但它们在缺乏额外结构引导的情况下，往往难以应对复杂的领域。

一种常见的策略是将问题分解为子目标。然而，现有的基于子目标的方法（例如 HIPS-$\epsilon$, SGPS）依赖于显式的子目标生成与重构。这引入了显著的模型复杂性和计算开销，因为搜索性能与子目标生成的质量紧密耦合。随着领域复杂度的增加，重构和推理这些显式子目标的成本成为了瓶颈，阻碍了可扩展性。

本文旨在解决如何在不产生显式子目标生成计算成本的情况下，高效利用状态空间结构来引导搜索的问题。具体而言，它研究了如何利用在搜索过程中可获得的结构信号，为 $\sqrt{\text{LTS}}$ 算法（一种在树中每个节点处都隐式开始 LTS 搜索的方法）推导出有效的“重根化”（rerooting）权重。

方法论

作者提出了一个利用结构诱导重根器（Structure-Induced Rerooters）在 $\sqrt{\text{LTS}}$ 中分配搜索精力的框架。该框架并不生成显式的子目标，而是从搜索树的结构和学习到的启发式函数中推导出重根化权重。论文介绍了三种具体的实例化方案：

1. 全局结构诱导重根化 ($\sqrt{\text{LTS-L}}$)

这种方法使用 Leiden 聚类捕捉状态空间中的粗粒度全局结构。

• 机制： 随着搜索树的构建，系统会构建一个状态空间的诱导子图。Leiden 算法会定期（按几何调度方案）被调用，根据连通性对状态进行聚类。
• 权重分配： 节点被分配一个与其所属簇相对应的“颜色”。节点的重根化权重与该簇的大小（通过该颜色的节点计数近似）成反比。
• 原理： 这鼓励搜索将精力集中在探索不足的区域（小簇），并将精力从过度探索的区域（大簇）转移开，从而有效地将簇视为软性的子任务，而无需显式重构。

2. 局部结构诱导重根化 ($\sqrt{\text{LTS-H}}$)

这种方法利用学习到的启发式函数提供的局部代价估计。

• 机制： 重根化权重被定义为归一化启发式值的指数函数：$w_t = \exp(-\alpha \frac{h(n_t)}{h(n_1)})$。
• 原理： 这创建了一种“软性”优先级排序，即被估计为更接近目标的节点（较低的启发式值）会获得更高的权重。通过根节点启发式值进行归一化确保了对启发式绝对尺度的不变性，而指数映射则确保了权重平滑且严格大于零，从而允许存在不完美的启发式函数。

3. 混合结构诱导重根化 ($\sqrt{\text{LTS-LH}}$)

该方法将全局和局部信号进行加性结合。

• 机制： 最终权重是基于聚类的权重与基于启发式的权重的线性组合：$w_t = u_a w_{t, \text{cluster}} + u_b w_{t, \text{heuristic}}$。
• 原理： 全局重根器通过识别结构瓶颈，为应对启发式噪声或失准提供稳定性；而局部重根器则根据预估进度细化这些区域内的优先级。这种“由粗到精”的方法旨在平衡鲁棒性与目标导向的适应性。

理论保证

论文扩展了 $\sqrt{\text{LTS}}$ 所需节点展开数量的理论界限。它为加性重根器提供了一个新的保证，表明搜索复杂度受多个重根器协同效应的约束。具体而言，如果各组件的相对权重保持平衡，则界限取决于单个界限的最小值，这使得搜索能够在树的任何区域都能够回退到信息量最大的信号上。

核心贡献

1. 自动化重根器学习： 本文提出了直接从搜索树结构（通过聚类）和学习到的启发式函数中推导重根化权重的自动化方法，消除了对单独且计算昂贵的子目标生成网络的需求。
2. 三种重根器设计： 引入并评估了三种不同的设计：基于聚类的全局重根器、基于启发式的局部重根器以及混合加性重根器。
3. 理论扩展： 为使用加性重根器的 $\sqrt{\text{LTS}}$ 提供了新的理论界限，展示了如何结合多种结构信号来提高搜索效率。
4. 可扩展性演示： 该工作证明了重根化可以扩展到显式基于子目标的方法失效的复杂环境，实现了最先进的在线训练效率。

实验结果

作者在四个领域评估了其方法：BoulderDash、CraftWorld、Sokoban 以及网格版本的旅行商问题 (TSP)。他们将这些方法与 LTS、PHS*、基于子目标的方法（LTS($\pi_{SG}$), PHS*($\pi_{SG}$)）以及加权 A* 进行对比。

• 训练效率： 在所有领域中，混合重根器 ($\sqrt{\text{LTS-LH}}$) 和基于启发式的重根器 ($\sqrt{\text{LTS-H}}$) 与非重根化基准及先前的基于子目标的方法相比，显著提高了在线训练的样本效率。在复杂设置下（例如高泥土密度的 BoulderDash），基于子目标的方法 (PHS*($\pi_{SG}$)) 无法扩展或超时，而重根化方法成功完成了训练。
• 测试性能： 尽管训练速度更快，但重根化方法实现的测试性能（以解决的问题数、解的展开次数和解的长度衡量）与先前的方法相当或更优。
• 鲁棒性： 混合方法表现出最强的鲁棒性，特别是在存在死锁结构的领域（Sokoban, CraftWorld）中，纯启发式引导可能会变得不稳定。全局聚类组件有助于在启发式函数不可靠时稳定搜索。
• 复杂度缩放： 在 BoulderDash 复杂度缩放实验中，混合重根器和启发式重根器在状态空间增长时仍能保持性能，而基于子目标的方法由于在视觉密集但与任务无关的环境中难以重构相关子目标，性能显著下降。

意义与主张

本文声称，重根化是利用策略树搜索中结构信息的、一种可扩展且灵活的抽象。其主要意义在于证明了：

• 隐式子任务： 人们可以在不产生显式子目标生成与重构的计算开销的情况下，获得子任务分解带来的好处（改进探索和搜索引导）。
• 轻量级信号： 即便是轻量级的结构信号（如局部启发式值）也足以引导有效的重根化，其表现往往优于孤立使用的更复杂的全局聚类方法。
• 协同作用： 将互补的结构信号（全局连通性和局部代价估计）相结合，创建了一种能够适应不同领域复杂度和启发式质量的鲁棒机制。

作者得出结论，使用经典启发式的简单结构变换进行 $\sqrt{\text{LTS}}$ 是一种实现可扩展策略树搜索的高效路径，避免了在复杂领域中与显式子目标建模相关的瓶颈。