いまやMDPを知らない。遷移も報酬も知らないまま、環境と相互作用して得た経験だけで、与えられた方策の価値を推定する。二つの大きな枝がモンテカルロと時間的差分学習だ。
講義スライド: PDF
モンテカルロ（MC）
エピソードが終わるまで待ってから、実際に受け取った収益 $G_t$ で価値を引き寄せる。
$$V(S_t) \leftarrow V(S_t) + \alpha\,(G_t - V(S_t))$$完結したエピソードが必要だ（終わりがなければならない）。一つのエピソードで同じ状態を何度も踏むことがあるが、その状態の初回訪問だけを数えれば初回訪問MC、踏むたびに全部数えれば毎回訪問MCだ。どちらも訪問が積み重なれば真の価値へ収束する。
もともとMCは収益の単純平均だ。これを毎回計算し直す代わりに更新式へ書き換えると、$1/N$ の位置に定数 $\alpha$ を置いた途端、意味が少しだけ変わる。$1/N$ はすべての過去エピソードを等しく反映する本当の平均であり、定数 $\alpha$ は古いエピソードを指数的に忘れていく。環境が少しずつ変化する（非定常）問題では、忘れるほうがよい。
シルバーの例はブラックジャックだ。ディーラーの規則も確率も知らないまま、数多くの局を実際に打ってみて、各状況（自分のカードの合計、ディーラーが見せたカード、使えるエースの有無）の価値を、勝ち負けの結果の平均で採点する。モデルなしに、経験だけで価値の地図が埋まっていく。
時間的差分学習（TD）
終わりまで待たずに一歩だけ先を見てから、推定値で推定値を更新する（ブートストラップ）。TD(0)はこうだ。
$$V(S_t) \leftarrow V(S_t) + \alpha\,\big(R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\big)$$括弧の中がTD誤差だ。エピソードが終わらなくても、一歩ごとにオンラインで学ぶ。
シルバーの例は帰り道だ。家までかかる時間を予測しながら運転するのだが、車に乗って30分を見込んだところで雨に遭えば、その場で40分に直す。到着してから（エピソードの終わり）予測を直すのがMCなら、TDは一瞬ごとに新しい情報で予測をすぐさま手直しする。終わりを見なくても学べることがTDの力だ。
MCとTD、何をいつ
- MC：実際の収益、バイアスなし、高バリアンス、終了が必要、初期値に鈍感。
- TD：ブートストラップ、バイアスあり、低バリアンス、オンライン、初期値に敏感でマルコフ性を活用。
バイアスとバリアンスの差がどこから来るかを見れば直観が立つ。収益 $G_t$ 一つには、エピソードの終わりまでのすべてのランダムな行動・遷移・報酬が入っている。だからバイアスはないが大きく揺れる（高バリアンス）。TDターゲット $R + \gamma V(S')$ には、ちょうど一歩ぶんのランダム性だけが入っている。その代わりまだ間違っている推定値 $V(S')$ に頼るのでバイアスが生じるが、揺れははるかに小さい（低バリアンス）。
二つが何へ収束するかも違う。シルバーの有名なA、Bの例がこれをあらわにする。八回の短い経験だけを与えてバッチで学習させると、MCは観測された収益の平均だけを合わせようとして、Aの価値を0と見る（Aが現れた唯一のエピソードの収益が0だったから）。TDは「Aの次にBが来て、Bはたいてい報酬を与える」という構造をつなぎ合わせ、Bを経由してAの価値を0.75と見る。MCは経験したことの平均（最小二乗）を、TDは経験したことで組み立てたMDPの答え（確実性等価）を見つける。だからマルコフ構造があればTDが有利で、なければMCのほうが安全だ。
ランダムウォーク。中央から出発して左右へランダムに歩き、右端に触れると報酬 +1 だ。真値はAからEまで 1/6, 2/6, …, 5/6（点線）。エピソードを押し進めながら、MCとTD(0)の推定（実線）が真値へ近づく速さを比べてみよう。たいていTDのほうが速く追いつく。
統合ビュー：ブートストラップとサンプリング
DP、MC、TDを一つの座標に置くと地図が描ける。二つの軸だ。第一はブートストラップの有無、すなわち次の状態の推定値をターゲットに使うか。第二はサンプリングの有無、すなわち次の状態たちを確率ですべて洗うか（全幅）、それとも実際に経験した一つだけを使うか（標本）。
- 動的計画法：ブートストラップあり、全幅（サンプリングなし）。モデルを知って浅く洗う。
- モンテカルロ：ブートストラップなし、標本あり。モデルなしで終わりまで深く行く。
- 時間的差分学習：ブートストラップあり、標本あり。モデルなしで浅く洗う。
強化学習のほとんどすべての方法が、この二つの軸のどこかに置かれる。この講義は、その地図の三つの隅を立てたことになる。
nステップとTD(λ)
一歩（TD）と終わりまで（MC）は両極端でしかない。n歩先を見るnステップ収益がその間をつなぐ。そしてすべてのnの収益を一度に混ぜたものがλ収益で、nステップ収益に $(1-\lambda)\lambda^{n-1}$ の重みを与える。最近のステップほど大きく、後ろへ行くほど幾何級数的に小さくなるこの形のおかげで、無限の和を効率よく再帰的に計算できる。$\lambda=0$ なら第一項だけが残ってTD(0)、$\lambda=1$ ならMCに近い。
TD(λ)には二つの顔がある。前を見る前方視は、上のλ収益をターゲットに使う。直観は明快だが、未来をすべて見なければならないので、エピソードが終わってから計算される。後ろを見る後方視は、適格度トレース（eligibility trace）で同じことをオンラインでやってのける。
適格度トレースは信用割り当て問題を解く。鐘が三度鳴り、光が一度ともった後に電気ショックが来たなら、何がショックを招いたのか。よく起きた信号（頻度）と、たった今起きた信号（最近性）の両方を疑うのが合理的だ。適格度トレースはその二つを掛け合わせ、各状態に残す。
$$E_t(s) = \gamma\lambda\, E_{t-1}(s) + \mathbf{1}(S_t = s)$$状態を踏むとトレースが1だけ跳ね上がり、以後は一歩ごとに $\gamma\lambda$ 倍で薄れていく。そして一歩ごとのTD誤差が、このトレースに比例して過去の状態たちへ広がる。驚くべきことに、前方視と後方視はオフラインで正確に同じ更新を与える。
ここまでは方策を評価するだけだった（予測）。次の講義では、この道具で最適方策を見つける制御へ進む。