技術的概要：停止のタイミングを学習する：任意のダイナミクスシフト下における選択的模倣学習

1. 問題定式化

本論文は、テスト環境の遷移ダイナミクスがトレーニング環境から任意に異なる状況における**模倣学習（IL）**の課題に取り組む。古典的なオフライン IL では、ソース環境 $M$ からの専門家デモンストレーションでトレーニングされた学習者が、ターゲット環境 $N$ に展開される。$M$ と $N$ の状態サポートが互いに素であるか、あるいは著しくシフトしている場合、標準的な方策は、トレーニングデータがもはや信頼できるガイダンスを提供しないことを認識できないため、任意に悪いパフォーマンスを発揮する可能性がある。

著者らは、学習者がトレーニングデータの信頼できるサポートから外れた現在の状態を検出した際に、実行を中止（abstain）するオプションを付与する選択的模倣学習の枠組みを提案する。目標は、2 つの競合する目的を満たす選択的方策 $(\pi, \tau)$、すなわち基本方策 $\pi$ と停止時刻 $\tau$ からなる方策を学習することである。

1. 完全性（Completeness）: 方策はトレーニング環境 $M$ でめったに中止を行わないこと（すなわち、$\alpha_M(\pi, \tau) \le \epsilon$）。
2. 健全性（Soundness）: 方策は停止する前に、テスト環境 $N$ において低い後悔（regret）を被ること（すなわち、$Regret_N(\pi, \tau) \le \epsilon$）。

この設定では、以下のアクセスが前提とされる。

• ラベル付きトレーニングロールアウト: 環境 $M$ における専門家 $\pi^\star$ からの状態 - 行動ペア $(s, a)$。
• ラベルなしテストロールアウト: 環境 $N$ における専門家 $\pi^\star$ からの状態のみの軌道。この非対称性は、行動テレメトリが高コストまたは機密である現実世界のシナリオ（例えば、操縦コマンドのない自動運転のドライブレコーダー映像など）をモデル化する。

2. 手法：SeqRejectron

核心的なアルゴリズムであるSeqRejectronは、選択的分類（Goldwasser et al., 2020）からのRejectronアルゴリズムを逐次意思決定に一般化したものである。鍵となる洞察は、各時間ステップで独立した意思決定を行うこと（これによりホライズン依存のサンプル複雑性が生じる）ではなく、スパースな検証方策（validator policies）の集合を用いて、完全な軌道プレフィックスを認証することである。

核心メカニズム

1. 基本方策: 学習者はトレーニングデータと整合する基本方策 $\pi_0$ を選択する（例：最尤推定）。
2. 検証者集合: アルゴリズムは、バージョン空間（トレーニングデータと整合する方策）から引き出された「検証者」方策の小さな集合 $\Phi$ を構築する。
3. 停止規則: 学習者は $\pi_0$ を実行し、$\Phi$ 内のすべての検証者が $\pi_0$ に同意する間だけ継続する。最初の不一致点が停止（中止）をトリガーする。
4. スパースな検証者分布: 重要な理論的貢献は、スパースな検証者集合（サイズがホライズン $H$ に依存しない）が安全性を保証するのに十分であるという証明である。これは、「挑戦者（競合する方策を選ぶ）」と「検証者（検証者の集合を選ぶ）」との間のゼロサムゲームに対するミニマックス論法によって達成される。

異なる設定のためのバリエーション

本論文は、この枠組みを3 つのより一般的になる設定に適応させる。

• 決定論的方策:

  • メカニズム: 二値の不一致テストを使用する。停止時刻 $\tau$ は、任意の検証者 $\pi \in \Phi$ が $\pi_0$ と不一致となる最初のステップである。
  • 実装: 検証者分布は、後悔なしダイナミクス（具体的には、重み付き実現可能マルチインスタンス学習へのオラクル効率的な還元）を用いて構築される。
  • 結果: スパースなコスト下で、ホライズンフリーのサンプル複雑性 $\tilde{O}(\sqrt{\log|\Pi|/n})$ を達成する。

• 確率的方策:

  • 課題: 二値の不一致は粗すぎる；分布は単一の警告となる不一致なしに、各ステップで「ソフト」に異なる可能性がある。
  • メカニズム: 二値テストを累積ヘルンガー距離停止時刻に置き換える。学習者は、$\pi_0$ と任意の検証者間の累積された二乗ヘルンガー距離が閾値 $\theta$ を超えたときに停止する。
  • 結果: 停止した軌道のヘルンガー距離に対する有限サンプル bound を提供する。論文は、単一ステップ確率的設定におけるラベル付きサンプル複雑性に対して $\Omega(1/\epsilon^3)$ の下限を確立し、コスト駆動型の上限の一部と一致することを示す。

• 誤指定された方策クラス:

  • 課題: 専門家 $\pi^\star$ が学習者の方策クラス $\Pi$ 内に存在しない可能性がある。
  • メカニズム: 厳密なバージョン空間制約を対称正則化ゲームに置き換える。検証者はソースデータ上で基本方策と不一致を許容されるが、この不一致はペナルティを課される。
  • 結果: 保証は、誤指定の量（最良のクラス内誤指定誤差 $\Delta$ によって測定される）に応じて滑らかに劣化する。

3. 主要な貢献と結果

理論的保証

• ホライズンフリー複雑性: 決定論的方策の場合、サンプル複雑性はホライズン $H$ に依存しない（総コストスケール $C_{max}$ を通じてのみ依存し）、$\tilde{O}(\sqrt{\log|\Pi|/n})$ としてスケーリングする。これは $O(H^2)$ のペナルティを被る単純なステップごとの還元よりも優れている。
• スパースな検証: 本論文は、状態空間、行動空間、またはホライズンに依存せず、サイズ $O(1/\epsilon)$ の集合でサポートされる検証者分布の存在を証明する。
• 下限: 著者らは、確率的単一ステップ設定におけるラベル付きサンプル複雑性に対して $\Omega(1/\epsilon^3)$ の下限を証明し、コスト駆動型レジームにおいて $1/\epsilon$ の3乗依存性が避けられないことを示す。
• 誤指定耐性: この枠組みは、専門家がクラスに存在しないアノスティック設定に拡張され、後悔 bound は誤指定誤差の平方根に比例してスケーリングする。

実証的評価

著者らはLunarLander-v3環境で SeqRejectron を評価する。

• 設定: トレーニングは無風環境で行われ、テストは異なる初期インパルスを持つ風のある環境で行われる。
• 知見: アルゴリズムは分布外ダイナミクスを正常に検出する。安全性閾値 $\theta$ を調整することで、著者らは、分布内（トレーニング）データでは最小限の中止を行いながら、分布外（テスト）データでは確実に停止して壊滅的な失敗を防ぐというトレードオフを実証する。検証者の数は頑健であり、パフォーマンスは急速に飽和することがわかった。

4. 意義と主張

本論文は、模倣学習における予期せぬダイナミクスシフトに対する原理的かつ理論的に裏付けられた対応として、**中止（abstention）**を確立することを主張する。

• ヒューリスティクスを超えて: シフトの性質に関する仮定やテスト分布へのオンラインアクセスを必要とする堅牢な RL やドメインランダム化のアプローチとは異なり、SeqRejectron はオフラインデータのみを使用して分布フリーの PAC 保証を提供する。
• PQ 学習の逐次アナログ: この研究は、Goldwasser ら（2020）の PQ 学習枠組みの逐次アナログとして位置づけられ、中止する能力を単一の予測から完全な軌道プレフィックスへと拡張する。
• 安全性メカニズム: 「何を」行うかの決定と「いつ」停止するかを分離することで、この枠組みは、トレーニングデータが情報に乏しい場合に学習者がシステムを回収不可能な状態に追い込むことを防ぐ安全性メカニズムを提供する。

著者らは限界を認め、確率的設定では現在、決定論的ケースとは異なりオラクル効率的な計算還元が存在しないこと、および確率的方策に対する分散駆動型のサンプル複雑性レートが上限と下限の間の未解決のギャップであることを指摘している。また、今後の研究では、部分的な構造的知識（例えば、有界な TV 距離）を組み込んでテスト側の停止率を厳密化することが提案されている。