方策反復（Policy Iteration）を徹底解説：理論・実装・実践的注意点まで
エバープレイ編集部方策反復とは（概要）
方策反復（Policy Iteration）は、強化学習（Reinforcement Learning, RL）における古典的な動的計画法に基づく最適化手法の一つです。有限のマルコフ決定過程（MDP）を仮定すると、方策反復は現在の方策を評価（policy evaluation）し、その評価に基づいて方策を改善（policy improvement）するという手続きを交互に行い、最終的に最適方策へ収束させます。代表的なアルゴリズムにはハワードの方策反復（Howard's Policy Iteration）や修正版の方策反復（Modified/Generalized Policy Iteration）があります。
数学的定式化と基本式
有限のMDPは集合（状態集合 S、行動集合 A）、遷移確率 p(s', r | s, a)、割引率 γ (0 ≤ γ < 1) で定義されます。方策 π(a|s) が与えられたとき、価値関数 v_π(s) はベルマン期待方程式を満たします。
ベルマン期待方程式（状態価値関数）: v_π(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [ r + γ v_π(s') ]
行動価値関数: q_π(s,a) = Σ_{s',r} p(s',r|s,a) [ r + γ Σ_{a'} π(a'|s') q_π(s',a') ]
方策反復は以下の2段階を繰り返します。
方策評価（Policy Evaluation）: 与えられたπについてv_πを（数値的に）解く。
方策改善（Policy Improvement）: v_πを用いて各状態で貪欲な行動を選び新方策π'を作成する。具体的には π'(s) = argmax_a q_π(s,a)。
方策評価の方法
方策評価は線形方程式の解法として捉えられます。有限状態空間ではベルマン期待方程式は線形系 (I - γP_π)v = r_π の形となるため、直接解くことが可能です。ただし、状態数が大きい場合は反復法（Iterative Policy Evaluation）を用います。反復評価では更新式
v_{k+1}(s) = Σ_a π(a|s) Σ_{s',r} p(s',r|s,a) [ r + γ v_k(s') ]
を全状態に対して繰り返し適用して収束を待ちます。評価を完全に収束させる方法と、数ステップだけ評価して改善に移る方法（部分的評価・トランケーテッド評価）があり、後者は計算効率と収束速度のトレードオフになります。
方策改善と収束性
方策改善は単純で、評価で得られた価値に基づいて各状態で最良の行動を取る方策を導出します。方策改善定理により、改善した方策は元の方策より優れている（あるいは同等）ことが保証され、有限MDPでは繰り返しにより最適方策に有限回で到達します。理論的には、方策反復はハワードの方策反復で単調に改善し、最適方策π*と最適価値関数v*に収束します。
方策反復のアルゴリズム（高レベル）
初期方策πを設定する。
方策評価: πに対するv_πを求める（反復または直接解法）。
方策改善: 新方策π'を v_π の下で各状態で貪欲に決定する。
π' == πなら停止、そうでなければπ ← π'にして2へ戻る。
計算複雑度と実装上の注意
方策反復は理論的には迅速に最適方策を見つけますが、1回の方策評価に要するコストが課題です。直接解法は状態数Sが大きいとO(S^3)になる可能性があり、反復評価は1スイープがO(S^2)（遷移が密な場合）程度です。実運用では以下の工夫が取られます。
修正版方策反復（Modified Policy Iteration, MPI）: 各方策評価をkステップの反復で打ち切ることで評価コストを削減し、改善を挟みながら進める手法。
非同期更新: 全状態を同時に更新する代わりに、優先度付きスイープや局所更新を行う。Bertsekasらの研究により、非同期動的計画法が実用的であることが示されています。
疎遷移の利用: 多くの現実問題では遷移行列が疎なので、計算は効率化できる。
方策反復と他手法との関係
方策反復は動的計画法の枠組みの一部で、値反復（Value Iteration）は評価と改善を同時に行う特別なケースと見なせます。一般化方策反復（Generalized Policy Iteration, GPI）は、評価と改善の相互作用を抽象化した概念で、方策反復、値反復、そして多くの近似手法（例: Actor-Critic）を包含します。
近似とサンプリングを伴う現実的適用
実世界問題では状態空間が連続または巨大なため、関数近似（線形近似やニューラルネットワーク）を用いた方策反復的手法が必要になります。しかし、関数近似を導入すると収束保証が崩れる場合があります。有名なBairdの反例など、オフポリシーかつ線型関数近似のもとで発散するケースが報告されています。そのため、実装では以下の点に注意します。
安定化手法: 経験再生、ターゲットネットワーク、正則化など。
オンポリシー vs オフポリシー: 収束とサンプル効率のトレードオフ。
アクター・クリティック: 方策（アクター）をパラメータ化し、価値関数（クリティック）で評価・改善を行うことで、方策反復の枠組みを確率的・連続問題に適用する。
例: グリッドワールドでの方策反復
簡単なグリッドワールド（迷路）で考えるとイメージしやすいです。状態はマス目、行動は上下左右、遷移は確実あるいは確率的、報酬はゴールで高い値、罰は障害物など。方策反復を適用すると、
初期方策で各マスの価値を計算する。
各マスで価値最大化する方角へ方策を更新する。
最短経路へ向かう最適方策が得られる。
ただし、確率的遷移や報酬構造によっては最適解が複数存在することもあります。
理論的補足: 収束の証明スケッチ
方策改善定理は、任意の方策πについて改善方策π'を生成すると v_{π'}(s) ≥ v_π(s) が成立することを主張します。有限MDPでは方策の集合が有限なため、単調改善が続けば最終的に改善が不可能な方策（すなわち最適方策）に到達します。評価ステップは収束する（線形収束）ため、全体として収束が保証されます。
実務でのアドバイス
方策反復は教科書的に重要で、問題の構造を理解するのに役立ちます。だが実務では以下を考慮してください。
状態数が大きければMPIや近似手法を用いる。
モデルが無ければモデル推定（モデルベースRL）か、サンプルベースの方策反復（モンテカルロ方策反復）やアクター・クリティックを検討する。
関数近似時は収束性の問題に注意し、安定化手法を導入する。
計算資源とサンプル効率のバランスを設計段階で決める。
まとめ
方策反復は強化学習における基本的かつ強力なアルゴリズムで、方策評価と方策改善という直感的な二段階から成ります。有限MDPでは理論的収束が保証され、実装上は評価の打ち切りや非同期更新などの工夫で規模の大きい問題にも適用可能です。一方、関数近似やサンプリングベースの設定では収束性や安定性に注意が必要で、アクター・クリティックや修正版方策反復などの実用的手法が多く用いられます。
参考文献
- Sutton, R. S. & Barto, A. G., "Reinforcement Learning: An Introduction" (2nd ed.)
- Policy iteration - Wikipedia
- Puterman, M. L., "Markov Decision Processes: Discrete Stochastic Dynamic Programming"
- Bertsekas, D. P., "Dynamic Programming and Optimal Control"
- Baird, L. C., "Residual algorithms: Reinforcement learning with function approximation" (反例議論の文脈)
投稿者プロフィール
