ここから遂に第2部具体的な解法に入ります！本書では大きく3つの解法が記載されています。（長所、短所も一緒に）

• 動的計画法：数学的にうまく作られた方法。完全で正確な環境のモデルが必要。
• モンテカルロ法：概念的に単純でモデルを必要としない。ステップ・バイ・ステップの斬新的な計算に適していない。
• TD手法：モデル不要で、完全に斬新的。複雑で分析が難しい。

そして、第3部ではそれぞれの最も良い特徴を利用できる組み合わせの説明です。

動的計算法（DP）は、完全なモデルが必要で、計算量が膨大なので、実用的ではないけど、理論的には重要で多くの解法の元となる考え方なので重要です。DPと強化学習では、価値関数を利用して良い方策の探索を計画し組み立てる考え方が中心となっています。

方策評価

方策評価（policy evaluation）とは、任意の方策πに対する状態価値関数 V^πを計算することです。ここでは予測問題（prediction problem）と呼びます。第3章で出てきた状態価値関数に対するBellman方程式を更新規則として用いることで、連続した近似が次のように得られます。

\begin{align}
V_{k+1}(s) & = E_{\pi} [r_{t+1}+\gamma V_k ( s_{t+1} ) | s_t = s]
& = \sum_{\alpha}\pi( s, \alpha)\sum_{s’}P_{ss’}^{\alpha}[R_{ss’}^{\alpha}+\gamma V_k(s’)]
\end{align}

※ 何故かLatexが効かないので、{}を[]としている部分が、ここを含めいくつかあります。

V^πと同じ条件の下で、系列｛Vk}が極限 k -> ∞ でV^πに収束することが一般的に示されます。このアルゴリズムは反復方策評価（iterative policy evaluation）と呼ばれます。

ここで、sの期待値（即時報酬と価値）を使って、新しいsの価値を計算します。反復方策評価は、すべての状態の価値に対して一度ずつバックアップを行い、新しい近似価値関数V_{k+1}を作り出します。（完全バックアップ：full backup）DPアルゴリズムは、次状態の標本値ではなく、可能な次状態すべてを対象とするので、完全バックアップに相当します。

一方で、価値を全て保存せず、次々に更新していく（スイープ操作）手法を「その場更新型（in-place）」と呼びます。このアルゴリズムは、更新を終える時が重要で、極限でのみ収束するが、実際には以下の式が十分に小さい正の値ならば終わります。

$$ max_{s∈S} [V_{k+1} (s) – V_k(s)] $$

また参考アルゴリズムは以下の通り。

方策改善

方策に対して価値観数を計算することで、さらに良い方策を見いだす手がかりが得られます。気になるのは、新しい方策に変えることがより良いのか、それとも以前より悪いのか、です。それを知る方法の1つは、状態sで行動aを選択し、その後は既存の方策πに従うことで、

\begin{align}
Q^{\pi} (s, a) & = E_{\pi} [ r_{t+1} + \gamma V^{\pi} (s_{t+1} ) | s_t = s, a_t = a ]
& = \sum_{s’} P_{ss’}^{\alpha} [R_{ss’}^{\alpha} + \gamma V^{\pi} (s’)]
\end{align}

もし、この値がV^π(s)より大きい場合、つまりsで一度aを選んで、その後πに従うことが、常にπに従う場合よりも良いならば、状態sに対してaを常に選ぶことが良いと判断できます。これが成り立つのは一般的な定理の特別な場合に相当します。（方策改善定理: policy improvement theorem）証明は本書がわかりやすいです！

これを利用して全ての状態で、全ての可能な行動に関して、各状態でQ^π(s,a)が最良となる行動を選択するような変更が考えられます。（グリーディ方策 : greedy policy : 記号π’）

\begin{align}
\pi'(s) & = arg \max_{\alpha} Q^{\pi} (s, a)
& = arg \max_{\alpha} E [ r_{t+1} + \gamma V^{\pi} (s_{t+1} | s_t = s, a_t = a ]
& = arg \max_{\alpha} \sum_{s’} P_{ss’}^{\alpha} [ R_{ss’}^{\alpha} + \gamma V^{\pi} (s’) ]
\end{align}

argmax_aは、それに続く式を最大にするようなaの値を与えます。このグリーディ方策はV^πによって1ステップ先読みを行い、短期的に最良となるであろう行動を選択する。

これまでの議論では、決定論的な方策という特別な場合を扱ってきましたが、確率的方策πでは状態sで行動aを選択する確率π（s, a）を指定します。ここでの考え方は、確率的方策に用意に拡張することができます。

方策反復

方策評価と方策改善を繰り返して、最適価値関数に収束させる手法を方策反復（policy iteration）といいます。

参考プログラミング

価値反復

方策反復の欠点は、各繰り返しステップで方策評価を必要とすることです。価値反復は、方策改善と方策評価ステップを打ち切りを組み合わせた、極めて単純なバックアップ操作です。

価値反復は、方策評価と方策改善の2つのスイープ操作を、1回のスイープ操作の中に結合しています。方策改善のスイープ操作の間に、方策評価のスイープ操作を複数回行うことによって、収束がさらに早くなる場合が多いです。方策評価のスイープ操作をいくつか行った結果に、最大値を求める操作が加わっているアルゴリズムの例。

非同期動的計画法

非同期DPアルゴリズムは、その場更新型の反復DPアルゴリズムです。このアルゴリズムは状態集合全体の系統的なスイープ操作は行わず、状態を任意の順序で選んで価値のバックアップを行います。非同期DPアルゴリズムは、バックアップ操作を適用する状態の選択に大きな自由度を与えます。

与えられたMDP問題を解くために、エージェントが実際にMDPを経験するのに並行して、反復DPアルゴリズムを実行させることができ、エージェントの経験を用いてDPアルゴリズムがバックアップを適用する状態を決めることができます。

一般化方策反復

方策評価と方策改善の2つの過程の相互作用を一般的概念として、一般化方策反復（generalized policy iteration; GPI）と呼びます。

動的計画法の効率

DPは方策空間を直接探索するどのような手法よりも指数関数的に速いです。直接探索で最適方策の発見を保証するためには、すべての方策を余すところなく調べなければならないからです。したがって、大規模問題群に対しては、DP手法のみが適用可能。

DP手法では、後続状態の価値の推定量に基づいて、状態の価値の推定量を更新します。この手法は、別な推定量を基準にして当該推定量を更新します。このような考え方をブートストラップ（bootstrap）と呼びます。
次章は、完全で正確なモデルを必要とせず、ブートストラップを行わない強化学習法について。