Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

技術要約：$L_\infty$ 頑健 MDP に対する方策反復法の強多項式時間計算量

問題設定
本論文は、不確実性下における逐次決定における根本的な未解決問題である、$L_\infty$ 不確実性集合と固定された割引率を持つ頑健マルコフ決定過程（Robust MDPs; RMDPs）に対する強多項式時間アルゴリズムの存在について取り組んでいる。古典的な MDP では、厳密な値計算のために強多項式アルゴリズムが存在するが（Ye, 2011）、RMDP に対しては線形計画法（LP）を通じて多項式時間アルゴリズムが存在するものの、「強多項式」アルゴリズム（演算回数が入力係数のビット長に依存しないアルゴリズム）が存在するかどうかという問いは未解決のままであった。具体的には、$L_\infty$ 不確実性ポリトープを表現するために必要なアクション数が指数関数的になるため、$(s, a)$-矩形 RMDP をターン制確率ゲームに還元しようとするこれまでの試みは、多項式時間への還元に失敗していた。

モデルおよび定義
著者らは、$L_\infty$ 不確実性集合を持つ $(s, a)$-矩形 RMDP に焦点を当てている。

• $(s, a)$-矩形性: 環境は各状態・アクションのペアに対して独立に遷移確率を選択し、動的計画法の構造を維持する。
• $L_\infty$ 不確実性: 各状態・アクションのペア $(s, a)$ について、真の遷移ベクトルは、公称推定値 $\hat{P}_{s,a}$ の周囲の半径 $\delta_{s,a}$ の $L_\infty$ ボール内にある。
• 目的: エージェントは、敵対的な環境ポリシー $\tau$ に対して、最悪期待コストを最小化する方策 $\sigma$ を求める。
• 強多項式時間: アルゴクションの演算回数が変数と制約の多項式によって抑えられ、かつ計算中の数値のサイズが入力の係数の数値自体に依存せず、入力サイズの多項式であるアルゴリズムを指す。

手法
本論文では、方策評価（Policy Evaluation）と方策改善（Policy Improvement）を交互に行う 頑健方策反復法（Robust Policy Iteration; PI） を分析している。

1. 頑健マルコフ連鎖（RMC）: 著者らはまず、より単純なケースである（エージェントが各状態で単一のアクションを持つ）RMC-PI を分析する。

   • 方策改善: ビット精度に依存する線形計画法（LP）を解く代わりに、著者らは最適な環境の応答を計算するために ホモトピー・アルゴリズム（Behzadian et al., 2021）を利用する。このアルゴリズムは $O(n \log n)$ で動作し、特定の構造的特性を持つ方策を生成する。すなわち、境界（0、1、または不確実性の半径）に達するまで、「ドナー（寄付）」状態から「レシーバー（受取）」状態へと確率質量を移動させることで遷移確率が調整される。
   • ポテンシャル関数: ホモトピー・アルゴリズムによって許容される確率質量の移動を追跡するために、新しいポテンシャル関数 $f_\tau(s, s', s'')$ が導入される。この関数は、より高い最適値を持つ状態へ質量を移動させることによる、値の潜在的な改善度を測定する。
   • 組合せ論的境界: 著者らは、現在の方策の遷移確率と最適な遷移確率との間の「不一致（discrepancy）」が幾何級数的に減少することを証明する。決定的なのは、実数の符号付き部分集合和における異なる最上位ビット（MSB）の数を扱う組合せ論的補題（補題8）である。これは、より一般的な定理（定理20/21）から導出されており、不一致の可能な MSB の数を $O(|X| \log |X|)$ に抑えるものである。
   • 収束の議論: 現在の方策の遷移確率と最適なものとの不一致の幾何学的収縮（補題2）と、不一致の可能な MSB の有限数（補題8）を組み合わせることで、アルゴリズムが任意に小さな更新を無限に繰り返すことはできないことを示す。不一致の MSB は、多項式回しかつなければ変化しない。

2. 頑健 MDP（RMDP）: 分析は、一般的な RMDP ケース（RMDP-PI）へと拡張される。

   • アルゴリズムは、現在のエージェント方策に対する RMC 部分問題を繰り返し解いて最悪の環境応答を見つけ、その後、その結果となるコストを最小化するようにエージェント方策を更新する。
   • 同様のポテンシャル関数がアクションに対して定義され、最適なエージェントアクションから逸脱するコストを追跡する。
   • 同様のロジックが適用される：最大ポテンシャルを持つアクションは、値の誤差の収縮が変化を強制する前に、対数回数のイテレーションを超えて存続することはできない。

主要な貢献と結果

• 強多項式 RMC-PI: 著者らは、$n$ 個の状態と定数割引率 $\gamma$ を持つ RMC に対する頑健方策反復法が、$O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ 回のイテレーションで終了することを証明した。各イテレーションは多項式時間の操作（行列の逆行列計算およびホモトピー・ステップ）を含むため、総実行時間は強多項式である。
• 強多項式 RMDP-PI: この結果は、$n$ 個の状態と $m$ 個のアクションを持つ RMDP に一般化される。アルゴリズムは $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ 回のイテレーションで終了し、RMDP-PI も強多項式であることを確立する。
• 組合せ論的補題: 本論文は、符号付き部分集合和における異なる MSB の数を抑える新しい組合論的結果である補題8を導入している。著者らは、この定理のより強力なバージョンが AI 研究エージェント（Aletheia）によって独立して導出されたことに触れており、数学への AI の貢献を強調している。

意義と主張
本論文は、頑健最適化の理論における主要な未解決問題を解決したと主張している。$(s, a)$-矩形 $L_\infty$ RMDP に対する頑健方策反復法が強多項式時間で終了することを実証することで、著者らは Ye (2011) による古典的な MDP に対する先駆的な結果を、頑健な設定へと一般化した。この結果は以下の理由から重要である：

1. 入力パラメータのビット長に依存することなく、RMDP の 厳密な値 を計算するための理論的保証を提供する。
2. アクション数の指数関数的な増大により失敗した従来の還元手法の限界を克服する。
3. 無限の不確実性集合にもかかわらず、頑健な Bellman オペレータがホモトピー・アルゴリズムの組合せ論的特性を用いて効率的にナビゲートできることを確立する。

著者らは、理論的基礎は確立されたものの、今後の研究では、データ駆動型の不確実性集合に関する経験的研究や、これらのポテンシャルに基づく議論が、より優れた実用的なバリアントや停止基準につながるかどうかを探求できる可能性があると結論付けている。また、標準的な MDP 方策反復法のバリアントに対する多項式境界の問題は依然として未解決であることも述べている。