重根Levin树搜索中的结构诱导信息

# 面向重根莱文树搜索的结构诱导信息  
**来源：** [https://arxiv.org/html/2605.30664](https://arxiv.org/html/2605.30664)  

###### 摘要  
基于子目标的策略树搜索利用策略指导搜索，对于复杂的单智能体确定性问题是有效的，但往往依赖于显式的子目标生成，这会产生大量开销，阻碍可扩展性。本文通过最近引入的 `lts√` 算法，利用学得的“重根器”克服了这些限制。*重根器*将问题隐式分解为软子任务。已有工作主要关注给定或手工设计的重根器的形式化保证，而在本文中，我们提出了三种重根器设计：(i) 一种基于聚类的重根器，利用全局状态空间结构；(ii) 一种基于启发式的重根器，利用学得的到达目标代价估计；(iii) 一种结合两种信号的混合重根器。我们的框架避免了显式重建和推理生成的子目标，从而能够以显著降低的计算开销实现可扩展的搜索努力分配。实验表明，在子目标策略树搜索失效的复杂环境中，基于重根的方法能够扩展应用，并在所测试的领域上达到了最先进的在线训练效率。  
机器学习，ICML  

\declaretheorem[name=Theorem,numberwithin=section]{thm}  

## 1 引言  

复杂的离散规划问题仍然难以大规模求解，这推动了对学习引导搜索方法的日益关注。莱文树搜索（LTS） [Orseau 等，2018] 是一种利用学得的策略（动作上的概率分布）指导搜索的树搜索算法，在解决这类问题方面取得了成功。LTS的一个关键特性是它提供了在找到解决方案之前所需搜索步骤数量的上界，该上界取决于策略的*质量*。这反过来使得可以以最小化搜索努力为显式目标来学习策略。策略引导启发式搜索（PHS*） [Orseau 和 Lelis, 2021] 通过将学得的策略与学得的启发式函数相结合来扩展LTS。Orseau 和 Lelis (2021) 为 PHS* 提供了类似的界，并展示了可以在最小化该界的同时学习策略。尽管LTS和PHS*在理论上是健全的，但它们主要依赖学得的策略和启发式函数，如果没有额外的结构引导，可能难以解决复杂问题。  

当扩展到复杂问题领域时，一种常见的方法是受人类规划方式启发 [Botvinick 等，2009；Donnarumma 等，2016；Correa 等，2023]，将问题分解为更简单的子任务和子目标。子目标通过结构化搜索并扩展其超出初始策略支持的范围，有助于解决这一限制。基于这一见解，先前的工作引入了基于子目标的策略树搜索方法，包括 HIPS-ε [Kujanpää 等，2024] 和子目标引导策略启发式搜索（SGPS） [Tuero 等，2025]，这些方法生成中间目标状态，并让低级策略以这些生成的子目标为条件来引导搜索。通过显式推理这些子目标，这些方法可以改进早期探索和学习效率。然而，它们也引入了额外的建模复杂性和计算开销，因为搜索性能与子目标重建的质量以及以它们为条件的策略紧密耦合。正如我们将展示的，随着领域复杂性的增加，这个问题变得愈加突出。  

`lts√` [Orseau 等，2024]，读作“根-LTS”，是一种策略树搜索算法，它在搜索树中的每个节点隐式地启动一个LTS搜索。整体搜索努力在这些搜索之间分配，分配给每个搜索的时间比例通过一个*重根器*给出。这种机制将搜索隐式分解为子任务，避免了 HIPS-ε 和 SGPS 中子目标建模的复杂性——这些复杂性在扩展到复杂领域时使得那些方法成本高昂。Orseau 等人 (2024) 表明，`lts√` 找到解决方案之前节点扩展次数的界可以比 LTS 的界呈指数级改善。  

在本文中，我们重新审视重根化作为一种通用机制，用于在策略树搜索中利用底层状态空间的结构，并研究如何在实际中推导重根权重以有效引导搜索。在此框架内，我们提出了三种实例化。前两种捕捉互补的结构信息：一种全局方法，通过使用 Leiden 聚类 [Traag 等，2019] 识别的状态空间聚类来诱导结构；另一种轻量级局部方法，从学得的启发式代价信息中推导结构。然后，我们展示了加性重根器如何利用每种重根器的优势，并将其实例化为前两种重根器的混合体。  

与依赖于使用高容量模型进行计算昂贵的子目标生成的子目标基线方法 [Tuero 等，2025] 形成对比，我们的方法不需要学习或调用单独的子目标网络。相反，我们从搜索树中已经存在的结构实例化重根器，聚类重根器在搜索过程中按需运行。实验结果表明，我们的重根器显著提升了在线训练样本效率，超越了非重根的基线。这些结果将重根化建立为一种可扩展的方法，用于在搜索中利用结构，同时避免了先前工作中显式的子目标生成。  

我们的贡献可总结如下：我们提供了从搜索树结构中自动学习重根器的方法，并展示了即使是轻量级的结构信号也能实现强大的性能。最后，我们提出了一个关于 `lts√` 在使用加性重根器时首次找到解决方案节点之前节点扩展次数的全新理论保证，突出了 `lts√` 如何利用多个重根器的*协同效应*。进行的实验表明，我们的方法在在线训练期间可以扩展到复杂环境，并在使用自举方法的方法中达到最先进的训练效率，而以前依赖子目标重建的方法则相形见绌。  

## 2 预备知识  

策略树搜索算法通过逐步构建搜索树来解决单智能体确定性问题。这些问题表示为一个元组 (S, A, T, s₁, S_g, ℓ)，其中 S 表示状态空间，A 是有限动作集合，T : S × A → S 是确定性转移函数。初始状态由 s₁ ∈ S 给出，S_g 是目标状态集合。搜索问题诱导出一个有向图 G = (S, A)，其中当存在动作 a ∈ A 使得 T(s, a) = s' 时，存在边 (s, s') ∈ A。搜索树中的节点集合为 N。节点 n 的子节点集合为 C(n)，其父节点为 par(n)。除根节点 n₁（对应初始状态 s₁）外，每个节点恰好有一个父节点。节点 n 的祖先集合为 anc(n)，我们定义 anc_*(n) = anc(n) ∪ {n}。类似地，节点 n 的后代集合为 desc(n)，desc_*(n) = desc(n) ∪ {n}。我们还使用符号 n' ≺ n 表示 n' ∈ anc(n)，n' ⪯ n 表示 n' ∈ anc_*(n)。表示目标状态 S_g 的节点集合记为 N_g。搜索算法每次节点扩展产生损失 ℓ : N → (0, ∞]。对于任何节点 n，*路径损失*定义为 g(n) = ∑_{n' ⪯ n} ℓ(n')，即从根到 n 的损失之和。我们假设本文讨论的所有算法对所有节点 n 都施加损失 ℓ(n) = 1，因此路径损失 g(n) 等价于节点深度 d(n) + 1。  

策略 π 为子节点分配概率，其中 π(·|n) 是 C(n) 上的分布。诱导的*路径概率*定义为：对于任意 n̄ ⪯ n ⪯ n̲，π(n̲|n̄) = π(n̲|n)π(n|n̄)，其中 π(n|n)=1。当 n̄ ⋠ n 时，我们定义 π(n|n̄)=0。为方便起见，我们记 π(n) = π(n|n₁)。  

一些搜索算法利用*启发式* h : N → ℝ_{≥0}，它向节点分配非负值，以估计从当前节点到目标节点的路径损失。  

### 2.1 背景  

**最佳优先搜索（BFS）**。BFS [Pearl, 1984] 按递增的*代价*扩展节点。搜索从根节点放入优先队列开始。在每个搜索步骤中，从队列中移除代价最低的节点并进行扩展，将生成的节点加入队列。如果其底层状态先前已被扩展，BFS 不会再次扩展该节点。当队列中无节点剩余、找到解决方案或超过搜索预算（以扩展次数计）时，BFS 将停止。  

**莱文树搜索**。莱文树搜索（LTS） [Orseau 等，2018] 是一种 BFS 算法，它使用 φ_{LTS}(n) = (d(n)+1)/π(n) (1) 作为代价函数。LTS 保证在首次解决方案节点 n* ∈ N_g 被生成之前，扩展的节点数不超过 (d(n*)+1)/π(n*) 个 [Orseau 等，2018]。  

**`lts√` 算法**。`lts√` [Orseau 等，2024] 是一种*重根化*算法，它在树的每个节点隐式启动一个 LTS 搜索。对于任何节点 n，基础代价函数 c_t^r(n) 表示相对于以节点 n_t ≺ n 为根实例化的 LTS 搜索的代价：  
c_t^r(n) = ∑_{n_t ≺ n' ⪯ n} 1/π(n'|n_t)。 (2)  
*重根器*为这些 LTS 搜索中的每一个分配一个*重根权重*，`lts√` 使用该权重在整体搜索努力中按比例分配搜索资源，比例与其分配的权重成正比。与 LTS 类似，`lts√` 是一种 BFS 算法，使用代价函数  
c^r(n) = min_{n_t ≺ n} (1/w_t) c_t^r(n)， (3)  
其中 w_t ≥ 0 是锚定在 n 的祖先 n_t 处的 LTS 搜索的重根权重。Orseau 等人 (2024) 还提供了直到找到第一个解决方案节点之前所需节点扩展次数的理论保证，该保证取决于策略和重根器的质量。假设 `lts√` 在某个步骤 T 找到解决方案节点 n*。从 n₁ 到 n* 的路径的*子任务分解*是 n* 的祖先的一个子集，必须包括 n₁ 和 n*，被视为子任务边界。例如，对于 Sokoban 游戏，一个子任务分解是所有已把箱子推上目标点的祖先节点。令 D(n*) 为 n* 的所有此类子任务分解的集合。对于 D ∈ D(n*)，n* 的选定祖先在步骤 T₁, T₂, …, T_{|D|} 被扩展，其中必然有 T₁=1，T_{|D|}=T。那么 `lts√` 访问 n* 所需的搜索步骤数 T 满足 [Orseau 等，2024，推论 12，适应版]：  
T ≤ 1 + min_{D ∈ D(n*)} max_{i < |D|} (w_{T_i} / (∏_{j=i}^{|D|-1} π(n'_{j+1}|n'_{j})))， (4)  
其中 n'₁, …, n'_{|D|} 是 D 中的节点，按排序顺序给出。  

### 2.2 相关搜索算法  

**HIPS-ε 和 SGPS**。HIPS-ε [Kujanpää 等，2024] 和子目标引导策略启发式搜索（SGPS） [Tuero 等，2025] 是基于子目标的策略树搜索算法，通过显式生成子目标来扩展策略搜索的范围。HIPS-ε 使用从随机子目标集学习的子目标策略，并在搜索期间进行采样。SGPS 旨在以最小的搜索努力使用子目标序列，并动态选择它们。与我们的方法相比，这些方法需要复杂且计算密集的子目标生成 [Tuero 等，2025]，并且在训练期间无法充分扩展到更复杂的环境。  

## 3 方法  

本节介绍 `lts√` 框架内的三种重根器。我们分别提出了一种基于聚类的重根器（第 3.1 节）和一种基于启发式的重根器（第 3.2 节）。然后我们展示了如何通过加性重根器组合多个结构信号，并将其实例化为聚类重根器和启发式重根器的混合（第 3.3 节）。  

### 3.1 基于聚类的重根器  

聚类重根器是一种全局方法，它利用子图（聚类）诱导搜索树的结构。在搜索过程中，我们通过 `lts√` 探索的状态空间图 G = (S, A) 的*诱导子图* 进行定期聚类。诱导子图是已扩展节点对应的状态之间所有边的并集。使用该诱导子图，我们应用 Leiden 聚类算法 [Traag 等，2019] 来识别社区。Leiden 算法生成一个层次聚类，其中层次级别 γ > 0 处的分辨率参数用于控制聚类的粒度。从结果层次结构中，我们在层次级别 k（超参数）处选择一个聚类图 G_k = (V_k, E_k)，其中每个节点 U ∈ V_k 对应 G_0 中的一组节点（从而对应一组搜索树节点）。我们为每个树节点 n 分配一种颜色 c ∈ {1, …, |V_k||}，表示包含它的节点 U；我们称此分配为*着色*。颜色可能在不同调用之间变化：节点 n 在第 τ 次调用时可以有颜色 i，而在第 τ+1 次调用时可以有颜色 j ≠ i。在搜索步骤 t 时，Leiden 算法已被调用 τ = ⌊log_γ(t)⌋ 次，产生 τ 次着色，最近一次着色发生在搜索步骤 t' = ⌊γ^τ⌋ ≤ t。在 t' 和 t 之间的搜索步骤中，一些节点可能没有颜色，因为它们在最近一次（第 τ 次）着色发生时未出现在诱导子图中。对于这些节点，我们假设它们属于与其父节点相同的聚类，因此被赋予父节点的颜色。使用代理值来推迟昂贵的计算在启发式搜索中已有先例，例如当计算边代价 [Narayanan 和 Likhachev, 2017] 或启发式值 [Karpas 等，2018] 代价高昂时。  

令 M_{τ,c} 为第 τ 次着色中颜色为 c 的节点数，且  
δ_{τ,c} = |{⌊γ^τ⌋ < ℓ ≤ t : c_ℓ = c}| (5)  
为自步骤 ⌊γ^τ⌋ 以来扩展且颜色为 c 的节点计数。那么，`lts√-L` 为在搜索步骤 t 扩展的节点 n_t 分配重根权重 w_t 如下：  
w_t = 1/(M_{τ,c_t} + δ_{τ,c_t}) (6)  
其中 c_t 是与 n_t 关联的颜色。M_{τ,c_t} + δ_{τ,c_t} 的值近似于聚类 c_t 的大小。