arXiv は 2026 年 5 月 28 日に、Jake Tuero 氏ら 4 名による新論文「Structure-Induced Information for Rerooting Levin Tree Search」（arXiv:2605.30664v1、cs.AI 分類）を公開した。本論文は ICML 2026 に採択されている。研究の焦点は、複雑な単一エージェント決定論的問題に有効とされるサブゴールベースのポリシーツリー探索が抱えるスケーラビリティの課題にある。
サブゴールベースのポリシーツリー探索は、ポリシーを用いて探索を誘導する手法であり、複雑な問題に対して効果を発揮する。しかし、その多くは明示的なサブゴール生成に依存しており、生成のための多大なオーバーヘッドが発生し、スケーラビリティを妨げる要因となっていた。探索を進めるには、まずサブゴールを構築し、それを再構成して推論したうえで、探索資源を各サブタスクへ配分する必要があるためである。
これに対し著者らは、最近提案された √LTS アルゴリズムを通じて学習された「rerooter（再ルート化器）」を用いることで、この制約を克服する。rerooter は問題を明示的なサブゴールに分割するのではなく、複数の「ソフトなサブタスク」へと暗黙的に分解する。これにより、生成されたサブゴールを明示的に再構築して推論する工程を回避しつつ、はるかに低い計算オーバーヘッドで探索努力をスケーラブルに配分できる。
従来研究は、与えられた、あるいは手作業で設計された rerooter に対する形式的保証に主眼を置いていた。本論文はむしろ、rerooter 自体をどう設計し学習するかに踏み込む。具体的には三つの設計を提案する。第一は、大域的な状態空間の構造を活用するクラスタリングベースの rerooter。第二は、学習された cost-to-go 推定（残りコストの予測）を利用するヒューリスティックベースの rerooter。第三は、両方の信号を組み合わせるハイブリッド型である。
これら三設計は共通の枠組みに立脚しており、rerooter による暗黙的な問題分解によって、明示的なサブゴールの再構築と推論を不要にする。その結果、探索の質を保ちながら計算負担を抑えられる点が特徴である。実験面では、rerooting ベースの手法がサブゴールベースのポリシーツリー探索では失敗する複雑な環境までスケールし、テストした領域においてオンライン学習効率で最先端の性能を達成したと報告されている。
論文の投稿情報も明示されている。v1 は 2026 年 5 月 28 日 23:51:21 UTC に提出され、全文は約 1,560 KB。PDF、実験的な HTML、TeX ソースなどの形で閲覧可能で、DOI は DataCite により発行予定（登録待ち）である。なお、要旨では各領域の具体的な数値比較までは示されておらず、形式的保証に関する議論は主に既存研究を対象とし、本論文の主眼は rerooter の設計と学習にある点には留意が必要である。全体として本工作は、明示的サブゴール生成を回避して探索資源の配分をスケーラブルにする道筋を示し、より複雑な環境でのオンライン学習効率に関する今後の研究に参照点を与えるものである。