技術要約：Levin Tree Searchの再根根（Rerooting）に向けた構造誘発型情報の活用

問題定義

単一エージェントの決定論的環境における複雑な離散計画問題は、依然として大規模化において困難な課題である。Levin Tree Search (LTS) や Policy Guided Heuristic Search (PHS*) のような方策誘導型の木探索手法は、探索努力に関する理論的な保証を提供しているが、追加的な構造的ガイダンスなしでは複雑なドメインにおいて苦戦することが多い。

これに対処するための一般的な戦略は、問題をサブゴール（副目標）に分解することである。しかし、既存のサブゴールベースの手法（例：HIPS-ε、SGPS）は、明示的なサブゴールの生成と再構成に依存している。これは、検索のパフォーマンスがサブゴール生成の品質に密接に結合するため、重大なモデリングの複雑さと計算オーバーヘッドをもたらす。ドメインの複雑さが増すにつれ、これらの明示的なサブゴールを再構成し、それに基づいて推論するコストがボトルネックとなり、スケーラビリティを阻害する。

本論文は、明示的なサブゴール生成の計算コストをかけることなく、状態空間の構造を利用して効率的に探索を導くための課題に取り組む。具体的には、探索プロセス中に利用可能な構造的信号を用いて、$\sqrt{\text{LTS}}$ アルゴリズム（木内のすべてのノードでLTS探索を暗黙的に開始する手法）のための効果的な「再根根（rerooting）」重みを導出する方法を調査する。

手法

著者らは、$\sqrt{\text{LTS}}$ における探索努力を割り当てるために、**構造誘発型リ根根（Structure-Induced Rerooters）**を利用するフレームワークを提案している。明示的なサブゴールを生成する代わりに、このフレームワークは、探索木の構造と学習されたヒューリスティックからリ根根の重みを導出する。本論文では、以下の3つの具体的な実装を紹介する。

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}}$。
• 根拠: グローバルなリ根根器は、構造的なボトルネックを特定することで、ヒューリスティックのノイズや誤校正に対する安定性を提供する。一方で、ローカルなリ根根器は、推定された進捗に基づいてそれらの領域内の優先順位を精緻化する。この「粗から密へ（coarse-to-fine）」のアプローチは、堅牢性と目標指向の適応性のバランスを図ることを目的としている。

理論的保証

本論文は、$\sqrt{\text{LTS}}$ によって必要とされるノード展開数に関する理論的境界を拡張する。加算的なリ根根器を用いた新しい保証を提供し、探索の複雑さが複数のリ根根器の相乗効果によって制限されることを示す。具体的には、各コンポーネントの相対的な重みがバランスされている場合、その複雑さは個々の境界の最小値に依存し、これにより、探索は任意の領域において最も情報量の多い信号にフォールバックできる。

主な貢献

1. 自動化されたリ根根学習: 探索木の構造（クラスタリング経由）と学習されたヒューリスティックから、リ根根の重みを直接導出する自動化された手法を提示し、別途、計算コストの高いサブゴール生成ネットワークを必要としないようにした。
2. 3つのリ根根設計: クラスタリングに基づくグローバル・リ根根器、ヒューリスティックに基づくローカル・リ根根器、およびハイブリッド加算型リ根根器という、3つの異なる設計を導入し評価した。
3. 理論的拡張: 加算的なリ根根を用いた $\sqrt{\text{LTS}}$ の新しい理論的境界を提供し、複数の構造的信号を組み合わせることで、いかに探索効率を向上させられるかを示した。
4. スケーラビリティのデモンストレーション: 本研究は、リ根根が、明示的なサブゴールベースの手法が失敗する複雑な環境においてもスケールできることを実証し、最先端のオンライン学習効率を達成した。

実験結果

著者らは、BoulderDash、CraftWorld、Sokoban、およびグリッドワールド版のTraveling Salesman Problem (TSP) の4つのドメインで手法を評価した。これらを LTS、PHS*、サブゴールベースのバリアント（LTS($\pi_{SG}$)、PHS*($\pi_{SG}$)）、および Weighted A* と比較した。

• 学習効率: すべてのドメインにおいて、ハイブリッド・リ根根器 ($\sqrt{\text{LTS-LH}}$) およびヒューリスティック・リ根根器 ($\sqrt{\text{LTS-H}}$) は、リ根根を行わないベースラインや従来のサブゴールベースの手法と比較して、オンライン学習のサンプル効率を大幅に向上させた。複雑な設定（例：土の密度が高い BoulderDash）では、サブゴールベースの手法（PHS*($\pi_{SG}$)）はスケールしないかタイムアウトしたが、リ根根手法は学習を正常に完了した。
• テスト性能: 学習が高速であるにもかかわらず、リ根根手法は、解決された問題数、解決までの展開数、解の長さのいずれにおいても、従来の先行手法と同等またはそれ以上のテスト性能を達成した。
• 堅牢性: ハイブリッドなアプローチは、特にヒューリスティックによる誘導が不安定になりやすいデッドロック構造（Sokofan、CraftWorld）を持つドメインにおいて、最も堅牢であることが証明された。グローバルなクラスタリング成分が、ヒューリスティックが信頼できない場合の探索を安定させる役割を果たした。
• 複雑性のスケーリング: BoulderDash の複雑性スケーリング実験において、ハイブリッドおよびヒューリスティックのリ根根器は、状態空間が大きくなっても性能を維持したが、サブゴールベースの手法は、視覚的に高密度だがタスクとは無関係な環境において、関連するサブゴールを再構成することの困難さから、著しく低下した。

意義と主張

本論文は、**リ根根（rerooting）**が、方策ツリー探索における構造を利用するための、スケーラブルかつ柔軟な抽象化であることを主張している。その主な意義は、以下のことを実証した点にある：

• 暗黙的なサブタスク: 明示的なサブゴール生成と再構成という計算オーバーヘッドをかけることなく、サブタスク分解（探索と探索のガイダンスの向上）の恩恵を受けることができる。
• 軽量な信号: ローカルなヒューリスティック値のような軽量な構造的信号であっても、効果的なリ根根を導くのに十分であり、多くの場合、単独での複雑なグローバル・クラスタリング・アプローチを凌駕する。
• 相乗効果: 相補的な構造的信号（グローバルな接続性とローカルなコスト・トゥ・ゴー）を組み合わせることで、変動するドメインの複雑さやヒューリスティックの品質に適応する堅牢なメカニズムが構築される。

著者らは、古典的なヒューリスティックの単純な構造的変換を用いた $\sqrt{\text{LTS}}$ が、複雑なドメインにおける明示的なサブゴールモデリングに伴うボトルネックを回避し、スケーラブルな方策ツリー探索への非常に効率的な経路を提供すると結論づけている。