技術的概要：計画における汎化のための「学習による探索」と「探索による学習」

問題定義

組み合わせ汎化は、深層強化学習（DRL）における中心的な課題であり、そこでは方策や価値関数が、共通の問題構造によって定義された分布外シナリオに対して汎化しなければならない。古典的計画は、この問題に対する理想的なテストベッドを提供する。なぜなら、その基盤となる関係構造（述語と動作スキーマ）は固定され明示的である一方、インスタンスはオブジェクト数、初期状態、目標において変動するためである。

しかし、標準的な DRL アプローチは、スパース報酬を持つ計画ドメインにおいて苦労する。LRTA* や RTDP などの RL アルゴリズムで典型的なリアルタイム探索（反復的な状態から状態への遷移）は、これらの設定における計画の発見には効果的ではない。対照的に、古典的プランナーはベストファースト探索（例：A*、WA*）を使用するが、手作業で設計されたヒューリスティックに依存している。最近の研究では、一般的な方策やヒューリスティックの学習が試みられているが、既存の手法はしばしばリアルタイム探索、専門家デモンストレーションからの教師あり学習、またはヒンサイト再ラベリングに依存しており、探索と学習が互いに強化し合い、変化する問題サイズ全体でゼロショット汎化を達成する自己改善ループを確立することに失敗している。

手法：計画のための汎化探索（GSP）

著者らは、ベストファースト探索と Q 学習を組み合わせ、一般的な行動価値関数（$Q_\theta$）を学習する自己改善フレームワークであるGSPを提案する。

コアループ

1. 探索誘導学習: リアルタイム探索の代わりに、GSP はトレーニングインスタンスを解決するために重み付き A（WA）**を使用する。この探索は、現在学習された $Q_\theta(s, a)$ 値によって誘導される。
2. データ生成: WA* がノードを展開するにつれて、遷移のリプレイバッファが生成される。重要なのは、探索が標準的な RL が欠く監督信号を提供することである。
   • ゴールパス: ゴールに到達したとき、アルゴリズムはバックトラックして、解パス上のペアに対して実際の帰還値（return-to-go）を割り当てる。
   • 行き止まり: 状態が行き止まり（適用可能な動作がない）である場合、親ペアには固定のペナルティ帰還値が割り当てられる。
   • 下限: 探索は、解パス上で遭遇する任意の状態 - 動作ペアに対する最適帰還の下限を提供する。
3. Q 学習更新: $Q_\theta$ ネットワークは、これらの探索由来のターゲットを使用して更新される。ゴールパスのペアについては、ターゲットは $\max(R, \hat{y})$ であり、ここで $R$ は探索由来の下限、$\hat{y}$ は標準的なブートストラップターゲットである。これにより、価値推定値が、探索がすでに達成可能であると証明した値以下に低下することを防いでいる。
4. インスタンス選択: 学習効率を最適化するため、フレームワークは 3 つのインスタンスプール（未解決、解決済み、満足済み）を維持し、それらから指数関数的に増加する重みでサンプリングを行う。これにより、最も有益な更新を提供するインスタンス（例：最適解ではない解を持つもの）が優先される。

表現：関係的 GNN

異なるオブジェクト数や目標に対する汎化を確保するため、$Q_\theta$ は**関係的グラフニューラルネットワーク（R-GNN）**によって表現される。

• 入力: 状態 $s$ と目標 $g$ は、グラウンド原子の集合として符号化される。適用可能な動作は、補助的な「動作オブジェクト」と原子を導入することで明示的に表現され、ネットワークが状態の文脈内で特定の動作選択を評価できるようにする。
• アーキテクチャ: ネットワークは関係構造上のメッセージパッシングを使用する。述語固有の MLP が引数の役割に基づいてメッセージを生成し、それらが置換不変関数を通じて集約される。
• 出力: 共有された読み出し MLP が、特定の動作オブジェクトの埋め込みと、状態および目標のプールされた要約を組み合わせ、Q 値を生成する。このアーキテクチャにより、モデルは各スキーマごとの個別の予測器ではなく、グラウンド化された動作に対する共通のスコアリング原則を学習することが保証される。

主要な貢献

1. 自己改善探索 - 学習サイクル: 本論文は、ベストファースト探索（WA*）が高品質なトレーニングデータ（下限や行き止まりのシグナルを含む）を生成して学習されたヒューリスティックを更新し、それがより効率的な将来の探索を誘導するフレームワークを導入する。
2. ゼロショット汎化: 学習された Q 関数は、トレーニング中に観測されたものよりもはるかに多くのオブジェクトと異なる目標を持つインスタンスを解決できる一般的な方策として機能し、多くの場合、テスト時に探索を必要としない。
3. 統合フレームワーク: このアプローチは、2023 年国際計画コンペティション（IPC）のベンチマークから組み合わせパズル（ソコバン、ザ・ウィットネス）および PushWorld ドメインに至るまで、単一のアーキテクチャとハイパーパラメータセットを使用して、多様なドメインに均一に適用される。
4. リアルタイム探索に対する優位性: この研究は、スパース報酬かつ分岐係数の高い計画ドメインにおける成功にとって、学習ループ内のリアルタイム探索をベストファースト探索に置き換えることが決定的に重要であることを実証している。

実験結果

著者らは GSP を 3 つのカテゴリのベンチマークで評価した。

• 2023 IPC 学習トラック:

  • 貪欲実行（$GSP_\pi$）: Blocksworld、Miconic、Spanner で 100% のカバレッジを達成し、Lifted HER、LAMA、AlphaZero 型の方策などのベースラインを上回った。
  • 探索誘導（$GSP_{WA^*}$）: 結果は混合であった。ソコバンなどのパズルではカバレッジが向上した（14% → 32%）が、学習されたヒューリスティックが局所的なランキングには優れていたものの、大規模な分岐係数を持つドメイン（例：Blocksworld）では全球的な較正が欠けていたため、カバレッジが低下することがあった。
  • スケーリング: 30 個未満のブロックを持つ Blocksworld インスタンスで学習されたヒューリスティックは、488 個のブロックを持つインスタンスを探索なしで成功裡に解決した。

• 組み合わせパズル（ソコバン、ザ・ウィットネス、24 パズル）:

  • ソコバンにおいて、$GSP_{WA^*}$ は平均 207 回の展開でインスタンスの 100% を解決し、標準的なヒューリスティックを用いた WA*（3298 回の展開）や DeepCubeA（1050 回の展開）を大幅に上回った。
  • ザ・ウィットネスでは、行き止まり状態でのトレーニングの価値を示し、すべてのインスタンスを解決した。
  • 24 パズルでは、トレーニング中に解を見つけられなかった。これは、このアプローチが学習をブートストラップするために少なくとも 1 つの解を見つける能力を必要とし、初期のインフォームドヒューリスティックがない極端に難しい固定サイズのパズルではそれが困難であることを浮き彫りにした。

• PushWorld:

  • レベル 0 でトレーニングされたモデルはレベル 1 に汎化した。$GSP_{WA^*}$ は、古典的プランナーである LAMA よりも短い計画で、かつ展開回数が約 30 倍少ない状態で、63 件中 48 件のレベル 1 インスタンスを解決した。
  • 貪欲方策として、モデルフリー RL ベースライン（DQN、PPO）を大幅に上回った。

意義と主張

本論文は、遷移モデルが既知である場合、特にリアルタイム探索が有益な軌跡を発見できないスパース報酬ドメインにおいて、ベストファースト探索は汎化強化学習のための優れた探索メカニズムであると主張する。

主な意義は、自己強化サイクルの実証にある。探索は、ヒューリスティックの改善を可能にするトレーニングターゲット（下限、行き止まり）を提供し、改善されたヒューリスティックは後続の探索をより効率的にする。これにより、システムは任意のサイズと複雑さの問題を探索なしで解決できる一般的な方策を学習するか、または最適解へ導く極めて効率的なヒューリスティックを学習することが可能になる。

著者らは控えめに限界を指摘している。学習された Q 関数はしばしば強力な局所的な動作ランキングメカニズムとして機能するが、探索フロンティア全体にわたる全球的な較正が欠けている場合があり、これは極端に大きな分岐係数を持つドメインにおける WA* の性能低下につながる可能性がある。彼らは、将来の研究が状態間での価値汎化の改善と、ベストファースト探索とリアルタイム探索およびヒンサイト経験再ラベリングの相補的な強みの組み合わせに焦点を当てるべきであると示唆している。