動的計画法 — 環境を知っているなら「計算」で解ける

前章のベルマン方程式を、今度は実際に解きます。環境のモデル（遷移 P と報酬 R）が完全に分かっているとき、エージェントは一歩も動かずに最適方策を計算だけで導けます。その2大アルゴリズム — 方策反復と価値反復 — をグリッドワールドで回しながら理解します。

1. 前提 — モデル P と R を「知っている」

マルコフ決定過程（MDP）は（S, A, P, R, γ）の5点セットでした。この章では、そのうち遷移確率 P(s′|s,a) と報酬 R がすべて既知という強い仮定を置きます。すると価値の計算は「試行錯誤」ではなく「連立方程式を解く」問題になります。これが動的計画法（DP: Dynamic Programming）によるプランニングです。

以下の3つのデモは全部同じ環境を使います。

6×6 のグリッド。右上の G に入ると +10 で終了、灰色のマスは壁
1回の移動ごとに報酬 −1（壁や外にぶつかるとその場に留まり、やはり −1）
割引率 γ = 0.9（viz3 ではスライダーで変更可）

注意 — 現実には P も R も知らないロボットの車輪がどれくらい滑るか、ユーザーが次に何をクリックするか — 現実の環境モデルは普通、事前には分からない。DPは「モデル既知」という理想条件での解法であり、モデルなしで体験から学ぶ方法は次章「TD学習とQ学習」で扱う。それでもDPが重要なのは、ほとんどのRLアルゴリズムが本質的にDPの近似になっているから。

2. 方策評価 — 固定した方策の価値を求める

まずは一番の基礎、方策評価。方策 π を固定して（下のデモでは矢印で表示。わざと下手な方策にしてあります）、その価値関数 V^π(s) を求めます。やり方は単純で、ベルマン期待方程式の右辺を計算して左辺に代入する操作を、全マスに対して繰り返すだけ。全マス1周ぶんの更新を1スイープと呼びます。

V_k+1(s) = Σ_a π(a|s) Σ_s′ P(s′|s,a) [ R(s,a,s′) + γ V_k(s′) ] このデモは方策も遷移も決定的なので V_k+1(s) = R + γ V_k(s′) に簡単化される

方策評価 — スイープを繰り返すと V が収束していく

γ = 0.9 固定｜移動 −1、ゴール到達 +10

矢印＝固定方策 π、マスの色と数字＝現在の V(s)（緑が高く赤が低い）。「+1 スイープ」を押すたびに全マスが一斉更新され、右のグラフの最大変化量 Δ が減っていきます。矢印がループしているマスは V = −1/(1−γ) = −10 に沈むのも見てください。

POINT — なぜ必ず収束するのかこの更新は縮小写像：1スイープごとに真の値との誤差が必ず γ 倍以下に縮む。だから Δ のグラフは対数目盛でほぼ直線になり、γ が 1 に近いほど傾きが緩く（＝収束が遅く）なる。収束先はベルマン期待方程式の唯一の解 V^π。

3. 方策反復 — 「評価」と「改善」のキャッチボール

評価しただけでは方策は1ミリも良くなりません。そこで第2の操作、方策改善。求めた V^π を使って、各状態で「R + γV(s′) が最大になる行動」を選び直します（貪欲化）。方策改善定理により、こうして作った新方策は元の方策より必ず「同等以上」になることが保証されています。

すると自然な戦略が生まれます。評価 → 改善 → 評価 → 改善 → … を繰り返すのです。これが方策反復。有限MDPでは方策の総数が有限なので、「改善しても方策が変わらない」＝最適方策 π* に、必ず有限回で到達します。

方策反復 — 2つのボタンを交互に押して最適方策へ

viz1 と同じ下手な初期方策からスタート。① で V ヒートマップが更新され、② で矢印が貪欲化されます（オレンジ枠＝矢印が変わったマス）。変化するマスが 0 個になったら、それが最適方策です。何サイクルで到達するか数えてみてください。

4. 価値反復 — max を取り込んで一直線

方策反復には無駄があります。どうせ改善で方策を作り直すのに、評価を毎回「収束するまで」やるのはやり過ぎでは？ — 実はその通りで、評価を1スイープで打ち切り、そのまま max を更新に組み込んだのが価値反復です。方策を持ち歩かず、V だけを直接、最適価値 V* へ向けて更新します。

V_k+1(s) = max_a Σ_s′ P(s′|s,a) [ R(s,a,s′) + γ V_k(s′) ] 右辺がベルマン最適作用素 T*。T* は γ 縮小写像で、唯一の不動点が最適価値 V* — だから V ← T*V を繰り返すだけでよい

このデモだけは床が滑る確率的な環境にしてあります：意図した方向へ 80%、左右いずれかへ 10% ずつそれる。遷移確率 P(s′|s,a) が自明でなくなるので、式の中の期待値 Σ_s′ P(s′|s,a)[…] がようやく本領を発揮します（決定的な環境だと数スイープで「厳密に」収束してしまい、γ の効果が見えないため、という事情もあります）。

価値反復 — γ で収束の速さが変わる

γ（割引率）

矢印は「現在の V に対する貪欲方策」。V が収束するずっと前に矢印（方策）が最適形に固定されるのに注目してください。右のバーは同じ γ・同じ滑る床での「方策反復の総スイープ数」との比較。γ を 0.5 → 0.99 と上げると、遠い将来まで価値が効くぶん価値反復のスイープ数は倍以上に、方策反復側の評価コストは数百スイープまで膨らみます（更新は縮小率 γ の縮小写像なので、γ が 1 に近いほど誤差の減りが遅い）。

5. まとめ

方策評価：ベルマン期待方程式を代入の反復で解く。誤差は γ 倍ずつ縮み、必ず収束する。
方策改善：V に対して貪欲化。改善定理により方策は決して悪化しない。
方策反復：評価⇄改善の交互反復。少ないサイクル数で最適方策に到達（ただし1サイクルの評価が重い）。
価値反復：評価を1スイープに打ち切って max を直接適用。実装が最も簡単。γ が大きいほど反復回数は増える。
どちらも「モデル既知」前提のプランニング。モデルなしで学ぶのが次章のTD学習。

一歩先へ — 「動的計画法」はRL専用の道具ではない DPの本質は「大きな問題の最適解を、部分問題の最適解の再利用で組み立てる」こと。最短経路（ダイクストラ法）、文字列の編集距離、ナップサック問題 — みんな同じ発想で、命名者はベルマン本人。自動運転の経路計画で出てくる A* も、「ゴールまでの残りコストの見積もり」を頼りに最短経路DPを賢く枝刈りしたものだ。V(s) は「s からゴールまでの最短コスト（の符号反転）」だと思うと、この章の絵がそのまま最短経路問題に見えてくる。