要旨: 自律的な推論および身体性のある計画において探索深さが増すと、候補となる行動空間は指数関数的に拡大し、計算予算に大きな負荷がかかります。ヒューリスティックによる剪定は一般的な対策ですが、サロゲートモデル（LLMなど）が系統的な評価バイアスを示す場合には、形式的な安全性保証を伴わずに動作します。本論文では、ノード展開プロセスを、動的なフロンティア上での局所的な Best-Arm Identification（BAI）問題として定式化し、上界がある系統的バイアス L を仮定します。Lambert W 関数を反転することで、mathcal{O}((\Delta-4L)^{-2}) の加法的なサンプル複雑性を導出します。これは、安全なノード除去が可能なのは、経験的な報酬ギャップが 4L を上回る場合に限られることを示します。さらに、バイアスのある探索が持つ構造的な限界を確認するため、情報理論的な下界 Omega((\Delta-2L)^{-2}) も補完的に示します。続く評価では、合成木と複雑な推論タスクの両方において、この局所的な安全境界に従うことで最適な軌道を適切に維持しつつ、サンプル割り当ての効率を最大化できることを実証します。
有界な系統的バイアス下での最良腕同定（BAI）に対するタイトなサンプル複雑度の限界
arXiv cs.LG / 2026/4/17
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 自律的推論や身体性を持つ計画におけるノード展開を、動的フロンティア上の局所的な最良腕同定（BAI）問題として定式化し、LLMのような代理モデルに起因する有界な系統的評価バイアスLを明示的に扱っています。
- 逆ランバートW関数を用いる手法により、加法的なサンプル複雑度がO((Δ−4L)^{-2})であることを導き、経験的報酬ギャップが4Lを超える場合にのみ安全なノード除去が可能であることを示しています。
- 系統的バイアス下の探索の本質的限界として、情報論的な下界Ω((Δ−2L)^{-2})も提示しており、上界の構造的タイトさを確認しています。
- 合成木と複雑な推論タスクの両方での評価により、この「局所的安全境界」に従うことで最適軌道を保ちつつ、サンプル配分効率を高められることを示しています。
