強化学習の目的は「長期的な報酬を最大化する方策を求めること」であり，長期的な報酬は価値関数で表現されます．

ある状態 $s$ で方策 $\pi$ に従って行動したときの価値関数を状態価値関数と呼び，次の式で定義します．

$V^{\pi}(s) = \sum_a \pi(a|s) \sum_{s'} P(s'|s,a) \bigl(R(s,a,s') + \gamma V^{\pi}(s')\bigr)$

価値反復法

価値反復法 (Vlaue Iteration) とは，方策は「価値が最大となる行動を選択する」という仮定のもとで，価値を繰り返し更新しながら価値を推定する方法です．価値をベースに考えるので「Value ベース」の手法と呼ばれます．

方策は「価値が最大となる行動を選択する」ことなので，状態価値関数を以下の式に書き換えます．

$V^{\pi}(s) = \max_a \sum_{s'} P(s'|s,a) \bigl(R(s,a,s') + \gamma V^{\pi}(s')\bigr)$

この価値関数の形を用いて更新を行います．

具体的なアルゴリズムは以下の通りです．

Initialize $V(s)$ （例えば全ての状態に対して $V(s)=0$ ）

Repeat
　　 $\Delta$ ← 0
　　For each $s \in S$
　　　　 $v$ ← $V(s)$
　　　　 $V(s)$ ← $\max_a \sum_{s'} P(s'|s,a) \bigl(R(s,a,s') + \gamma V(s')\bigr)$
　　　　 $\Delta$ ← $\max(\Delta, |v-V(s)|)$
　　until $\Delta$ < $\theta$ （ $\theta$ は小さい正数）

方策反復法

方策反復法 (Policy Iteration) とは，価値反復法とは異なり，行動は方策に基づき選択されます．方策を更新していくことで方策を求めます．具体的には，方策を更新すると価値も更新されるため，更新された方策の下で価値を推定する「方策評価」と，推定した価値により方策を更新する「方策改善」を繰り返すことで方策を求めます．方策をベースに考えるので「policy ベース」と呼ばれます．

具体的なアルゴリズムは以下の通りです．

Initialize $V(s), \pi(a|s)$ （例えば全ての状態に対して $V(s)=0$ ， $\pi(a|s)$ は一様分布）

Policy Evaluation
　　Repeat
　　 $\Delta$ ← 0
　　For each $s \in S$
　　　　 $v$ ← $V(s)$
　　　　 $V(s)$ ← $\sum_a \pi(a|s) \sum_{s'} P(s'|s,a) \bigl(R(s,a,s') + \gamma V(s')\bigr)$
　　　　 $\Delta$ ← $\max(\Delta, |v-V(s)|)$
　　until $\Delta$ ← $\theta$ （ $\theta$ は小さい正数）

Policy Improvement
　　policy_stable ← True
　　For each $s \in S$
　　　　a ← $\pi(a|s)$
　　　　 $\pi(s)$ ← argmax $_a \sum_{s'} P(s'|s,a) \bigl(R(s,a,s') + \gamma V(s')\bigr)$
　　　　if $a \neq \pi(s)$
　　　　　　policy_stable ← False
　　if policy_stable, stop and return $V, \pi$ , else go to 2