方策反復法とは？意味とベルマン方程式との関係について

1. 方策反復法

強化学習における「最適な行動ルール（方策）」を求めるための基本的な手法の1つが、方策反復法（Policy Iteration）です。これは 動的計画法（Dynamic Programming; DP） を使って実装され、マルコフ決定過程（MDP）の情報がすべてわかっているときに利用されます。

はるか

方策反復法って、最適な方策を見つける方法の一つなんだよね。

ふゅか

そうそう！状態や行動、報酬が全部わかってるときに使える手法よ！

2. 前提：MDPの構成

方策反復法は、以下のような MDP の構成要素がすべて既知であることを前提とします。

• 状態集合 $\mathcal{S}$
• 行動集合 $\mathcal{A}$
• 状態遷移確率 $P(s’|s,a)$
• 報酬関数 $R(s,a,s’)$
• 割引率 $\gamma \in [0,1)$

3. 方策反復法の2ステップ

方策反復法は以下の2つを繰り返します。

1. 方策評価： 方策 $\pi$ に従った価値関数 $V^\pi(s)$ を推定
2. 方策改善： 推定した $V^\pi(s)$ に基づき、方策 $\pi$ を改善

はるか

方策反復法、2つのステップを繰り返すだけ。

ふゅか

うん！まずは「方策評価」で、今の方策がどのくらい良いかを数値で確かめる。そして「方策改善」で、もっと良い方策に更新していくの。

3.1. ① 方策評価

現在の方策 $\pi$ に従って行動したとき、各状態 $s$ がどれだけ価値があるかを評価するのが「方策評価」です。
正確には、状態価値関数 $V^\pi(s)$ は次のベルマン方程式で表されます。

$$ V^\pi(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma V^\pi(s’) \right] $$

ただしこれを厳密に解くのは困難なため、実際には反復的に推定値 $\hat{V}_k(s)$ を使って近似していきます。

このように過去の推定値を用いて更新する手法を「ブートストラップ法」と呼びます。

3.2. ② 方策改善

方策評価で得た $\hat{V}_{k+1}(s)$ を使い、「今より良い行動はないか？」を考えて方策を改善します。新しい方策 $\pi’$ は、以下のように更新されます。

$$ \pi'(a|s) = \arg\max_a Q^\pi(s,a) $$

ここで $Q^\pi(s,a)$ は行動価値関数で、次のように計算されます。

$$ Q^\pi(s,a) = \sum_{s’} P(s’|s,a) \left[ R(s,a,s’) + \gamma \hat{V}^\pi(s’) \right] $$

4. 繰り返すと、最適方策にたどりつく

この①評価と②改善を交互に繰り返すことで、最終的に方策が変化しなくなります。
これが最適方策 $\pi^*$ であり、どの状態にいても最も良い行動がわかるようになります。

5. まとめ