マルチチェーンMDPのためのより高速な固定点法
arXiv stat.ML / 2026/4/23
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、平均報酬基準のマルチチェーン・マルコフ決定過程（MDP）に対する価値反復（VI）法を扱い、ベルマン作用素の収縮性の欠如や解の非一意性といった理論的難しさに取り組みます。
- マルチチェーンMDPでは、最適方策が各強連結成分内での長期的な性能最適化に加えて、「最良の連結成分へ到達させる」ためのナビゲーション問題を解く必要があると述べています。
- 著者らは、このナビゲーション部分の扱いを改善するアルゴリズムを新たに提案し、その結果としてマルチチェーンMDPでの収束をより速くすることに成功しています。
- さらに、平均報酬問題と割引問題の関係、一般バナッハ空間での割引VIに対する最適固定点法、割引価値誤差に対する従属線形（sublinear）収束率、ならびにマルチチェーンでの改良された劣適分解といった、再利用可能な理論的成果も提供します。
- 全体として、本研究は割引・平均報酬の両設定でより鋭い複雑性評価と収束率保証を与えることで、VIアプローチの理論的基盤を強化します。
