マルコフ決定問題を解くための新しい複雑性結果

n 状態と各状態に対するアクションの数を持つマルコフ決定問題 (MDP) を解くための新しい複雑性結果を提示します。これは、レオンティエフ行列構造を持つ実数線形計画の特別なクラスです。割引因子 θ が 1 よりも厳密に小さいとき、この問題は O(n 1.5 (log 1/(1 − θ) + log n)) の古典的な内部点法の反復回数および O(n 4 (log 1/(1 − θ) + log n)) の算術演算で解くことができることを証明します。私たちの方法は、Ye (1990) および Vavasis と Ye (1996) の研究に関連する組合せ内部点法です。私たちの知る限り、これは割引因子が 1 より小さいときの MDP を解くための最初の強い多項式時間アルゴリズムです。