MDPを完全に知っている状況、すなわち遷移と報酬を知っているとき、最適方策を計算する方法が動的計画法（DP）だ。環境と相互作用せずモデルだけで答えを求めるので、計画（planning）と呼ぶ。DPが通用するのは、ベルマン方程式が問題を部分問題に分割し（最適性の原理）、その部分解を価値関数に保存して再利用できるからだ。
講義スライド: PDF
動的計画法とは
名前からして誤解を招く。ここでの「計画法（programming）」はコードを書くプログラミングではなく、線形計画法のように最適解を求める数学的最適化を意味する。「動的（dynamic）」は時間にわたる逐次的な問題という意味だ。この名を付けたリチャード・ベルマンは、数学研究を快く思わなかった当時の国防長官の目を避けるため、あえてもっともらしく難癖をつけにくい名前を選んだという有名な逸話がある。だから名前の重みに怯む必要はない。
核心となるアイデアは単純だ。大きな問題を小さな部分問題に分割して解き、その答えを合わせて大きな問題を解く。これが通用するには二つの条件が必要だ。
- 最適部分構造：全体の最適解が部分問題の最適解に分解される（最適性の原理）。
- 部分問題の重複：同じ部分問題が何度も現れ、一度解いた答えを保存して再利用できる。
MDPはこの二つを正確に満たす。ベルマン方程式が「今の状態の答え = 今の報酬 + 次の状態たちの答え」という再帰的分解を与え（最適部分構造）、その部分解を価値関数という表に書き留めて、隣を計算するたびに取り出して使う（部分問題の重複）。フィボナッチを手で数えるとき前の値をメモしておくと指数時間が多項式時間に減るように、ここでも価値をメモした瞬間に計算が扱える程度になる。
だからDPは強化学習の最も理想的なケースだ。環境（遷移と報酬）を完璧に知っているという前提のもと、ベルマン方程式を反復して解くだけで最適方策が出る。これからの講義は、この完璧な知識を一つずつ取り除きながら、それでも学べるのかを問う。
方策評価
与えられた方策 $\pi$ の価値 $v_\pi$ を求める問題だ（予測）。ベルマン期待方程式を更新則に変えて反復する。
$$v_{k+1}(s) = \sum_a \pi(a\mid s)\left(\mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_k(s')\right)$$すべての状態を一度に更新する同期バックアップで $k$ を増やすと $v_\pi$ に収束する。
シルバーの例は小さな格子世界だ。4×4の格子で両端の二マスが終了状態で、一歩ごとに −1 の報酬を与える。上下左右を無作為に選ぶ方策を置いて反復評価を回すと、最初はすべて0だった価値が、反復するほど終了から遠いほど大きな負の値へと落ち着いていく。数回回すだけで「どのマスが終了からどれだけ遠いか」という地図が現れる。
左上と右下が終了状態、一歩ごとに −1 だ。「1回反復」を押すたびにすべてのマスが同時に更新され、価値が収束していく。矢印はその時点の貪欲方策だ。驚くことに、方策の矢印は価値が完全に収束するはるか前にすでに最適になる。モードを「価値反復」に変えると、最大値で更新するバージョンが見られる。
面白い点が一つ。この評価だけでも、各マスで価値が高い隣へ進む貪欲方策を取り出すと、すでに最適方策になっていることが多い。評価と改善が自然につながる箇所だ。
方策反復
最適方策を見つける問題だ（制御）。評価と改善を交互に行う。
- 評価：現在の方策の $v_\pi$ を求める。
- 改善：$v_\pi$ に対して貪欲に新しい方策を作る。$\pi'(s) = \arg\max_a q_\pi(s,a)$。
改善された方策は決して悪くならない（方策改善定理）。この二つのステップを交互に行うと最適方策 $\pi_*$ に収束する。
シルバーが挙げる方策反復の例はジャックのレンタカーだ。二つの営業所を行き来しながら夜のあいだに車を移し（移すのに1台あたり費用がかかる）、昼に貸し出せば収入が生まれる。需要と返却は確率的（ポアソン）だ。方策反復を回すと、「各営業所に車が何台あるとき何台を移すか」という方策の地図が、反復するほどくっきりした階段状に整えられていく。
評価と改善を必ず最後まで交互に行う必要はない。上の格子で見たように、評価を数回だけして改善しても、いっそ一度だけして改善しても収束する。このように評価と改善をどんなふうに混ぜても最適に収束する大きな枠組みを一般化方策反復（GPI）と呼ぶ。これから出てくるほぼすべての強化学習の手法は、このGPIの変奏だ。
価値反復
方策を明示的に持たず、ベルマン最適方程式を直接反復する。
$$v_{k+1}(s) = \max_a\left(\mathcal{R}_s^a + \gamma\sum_{s'}\mathcal{P}_{ss'}^a\, v_k(s')\right)$$$v_*$ に収束し、最後に貪欲方策を取り出せばそれが最適方策だ。評価を一度だけしてすぐ最大値を取る形なので、方策反復より簡潔だ。ただし途中の価値がどんな実際の方策の価値でもないかもしれない点が異なる。
直観は最短経路探索と同じだ。終了（目標）マスの価値は確実だ。そこから一歩離れたマス、二歩離れたマスへと正確な値が波紋のように広がっていく。反復1回がこの波紋を1マスずつ広げるわけだ。格子で価値反復を回してみると、目標の周りから値が落ち着き、その波紋が外へ広がっていくのが目に見える。
なぜ収束するのか
ベルマン作用素は $\gamma$-縮小写像だ。反復すると二つの価値関数のあいだの距離が毎回 $\gamma$ 倍に縮み、唯一の不動点に収束する。その不動点が真の価値関数だ。方策評価と方策反復と価値反復がすべて同じ理由で収束する。
まとめと限界
三つの手法はいずれも状態価値 $v$ に基づき、各反復が全状態を走査する同期バックアップだ。状態が多いとこの一度の走査が高くつくので、シルバーは必要な状態だけを更新する非同期DPにも触れる。その場で直接上書き（in-place）、誤差の大きい状態を先に更新（優先度付きスイープ）、エージェントが実際に踏む状態から更新（リアルタイムDP）といった変形だ。
そしてDPの更新は全幅バックアップだ。ある状態を更新するとき、行ける次の状態をすべて漏れなく考慮する。正確だが分岐数だけ高くつき、遷移を知っている必要がある。次講のモデルフリー手法は、この位置にサンプルバックアップを置く。実際に経験した次の状態一つだけを使って更新するのだ。安く、モデルが要らず、大きな問題へ拡張できる。
DPは強力だが、二つのことが足を引っ張る。遷移と報酬を知っている必要があり、状態数に比例して計算が増える。次講からは環境モデルを知らないまま、経験だけで学ぶモデルフリー手法へ移る。