AIが解く世界の難問 · 計算機科学の理論 · arXiv · 2026-10-21
マスク付きMDPの告白
原題: Confessions of a Masked MDP
強化学習では行動集合が既知と前提されるが、応用によってはどの状態・行動対が許されないかを特定する行動マスクの決定自体が計算上の主要なボトルネックとなる。試みた行動ごとにその妥当性を定める線形スコアの正確な値が明らかになるという線形MDPの設定のもと、最適方策の探索とマスク学習の結合を研究し、決定的楽観最適化に基づくアルゴリズムがミニマックス最適かつ計算効率的である一方、非縮退なインスタンスでは次善に留まることを明らかにした。探索戦略を自ら計画する別の計算効率的なアルゴリズムは、決定的フィードバックに対する情報指向サンプリングの類似物として形式的に解釈でき、無効行動集合が時間とともに変化する転移学習への応用も示した。