生成モデルを用いた確率的最短経路（SSP）におけるサンプル複雑性の境界
arXiv cs.LG / 2026/4/20
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- この論文は、生成モデルへのアクセスを仮定したうえで、確率的最短経路（SSP）問題におけるε最適方策の学習に必要なサンプル複雑性を解析します。
- 最悪ケースにおいて、どのアルゴリズムでも高確率でε最適性を達成するには Ω(SAB⋆^3/(c_min ε^2)) 個のサンプルが必要であることを下界として示します。
- 重要な含意として、c_min = 0 のときSSPは一般には学習できない可能性があり、有限ホライズンや割引設定よりもSSP学習が本質的に難しいことを明らかにします。
- 著者らは下界に（対数因子まで）一致するアルゴリズムも提示しており、一般の場合と、c_min = 0 の場合では目標状態への到達時間（ヒッティングタイム）が有界であるという条件のもとで一致することを示します。
- 全体として、この研究はSSP学習が可能になる条件を特徴づけ、前提ごとのサンプルコストを定量化します。
