第4講は方策を評価するだけだった（予測）。今度はその道具で最適方策を見つける（制御）。モデルを知らないまま、つまり遷移も報酬も知らないまま、経験だけで最適へ近づく。核心は三つだ。なぜ状態価値ではなく行動価値を学ぶべきなのか、どう探索を混ぜるべきか、そして行動する方策と学ぶ方策を同じにするか別にするか（オンポリシー対オフポリシー）。
講義スライド: PDF
モデルフリー制御が必要な場面
エレベーターの配車、ロボカップサッカー、縦列駐車、Quake、船の操縦、ポートフォリオ管理、バイオリアクター、タンパク質折りたたみ、ヘリコプターの曲芸飛行、ロボットの歩行、囲碁。シルバーが列挙するこれらの問題はほとんどが二つのどちらかだ。MDPモデルをまったく知らないが経験を取り出せるか、モデルは知っているが大きすぎて標本でしか扱えないか。どちらであれ、モデルフリー制御が答えを与える。
オンポリシーとオフポリシーの区別も、ここで先に押さえておこう。オンポリシーは「働きながら学ぶ」だ。自分が従う方策 $\pi$ から出た経験で、まさにその $\pi$ を学ぶ。オフポリシーは「他人の肩越しに学ぶ」だ。別の方策 $\mu$ が作った経験で、自分が知りたい方策 $\pi$ を学ぶ。
一般化方策反復をモデルフリーに
第3講の骨格は一般化方策反復だった。方策を評価し（価値推定）、その価値で方策を改善し（貪欲化）、これを交互に回せば最適へ収束する。モデルフリーでも骨組みは同じだ。評価の位置に第4講のモンテカルロを挿せばよい。ところが改善の位置で問題が生じる。
なぜ状態価値ではなく行動価値なのか
状態価値 $V(s)$ で貪欲改善をするには、こう書かねばならない。
$$\pi'(s) = \arg\max_{a\in\mathcal{A}} \Big( R_s^a + P_{ss'}^a\, V(s') \Big)$$ここに遷移確率 $P_{ss'}^a$ と報酬 $R_s^a$、つまりモデルが入っている。モデルを知らなければ、この $\arg\max$ は計算できない。「この行動をすればどこへ行っていくら受け取るか」を知らないので、状態価値だけではどの行動が良いかを指し示せないのだ。
行動価値 $Q(s,a)$ を学べば、この壁は消える。
$$\pi'(s) = \arg\max_{a\in\mathcal{A}} Q(s,a)$$行動価値はすでに「各行動の値」をまるごと含んでいるので、モデルなしで表から最大の値を選ぶだけで改善が終わる。だからモデルフリー制御は $V$ ではなく $Q$ を学ぶ。評価の位置に「モンテカルロで $Q \approx q_\pi$」、改善の位置に「$Q$ に対する貪欲」を入れるのが出発点だ。
探索を混ぜるべき理由：二つの扉
純粋な貪欲改善には落とし穴がある。シルバーの二つの扉の例が、この落とし穴を鮮明に見せてくれる。
前に扉が二つある。左の扉を開けたら報酬 $0$ だ。$V(\text{left})=0$。右の扉を開けたら $+1$。$V(\text{right})=+1$。もう一度右を開けたら $+3$ で、平均が $+2$ に上がる。さらに右を開けて $+2$、依然として平均 $+2$。ここで貪欲に振る舞えば、右ばかり開け続ける。右が左より良く見えるからだ。
だが本当に最良の扉を選んだと言えるのか。左はたった一度しか開けていない。そのとき偶然 $0$ が出ただけかもしれず、実は平均 $+10$ のお宝の扉だったかもしれない。左を二度と開けなければ、その真実は永遠に分からない。一度の悪い経験で扉を閉ざしてしまうこと、これが純粋な貪欲の危険だ。だから常に少しずつは探索しなければならない。
ε-貪欲
探索を保証する最も単純な方法だ。$m$ 個すべての行動に0でない確率を与えつつ、確率 $1-\epsilon$ では貪欲行動を、確率 $\epsilon$ では無作為な行動を選ぶ。
$$\pi(a|s) = \begin{cases} \epsilon/m + 1 - \epsilon & a^* = \arg\max_{a} Q(s,a) \\ \epsilon/m & \text{その他} \end{cases}$$ほとんどは最も良く見える行動をするが、たまには別の扉も開けてみる。左の扉がお宝だったなら、いつか その $\epsilon$ の瞬間に露見する。
ε-貪欲は必ず改善である
$\epsilon$ を混ぜると貪欲より悪くなるのではと心配するかもしれない。そうではない。シルバーはこれを定理として釘を刺す。どんな $\epsilon$-貪欲方策 $\pi$ であれ、その $q_\pi$ に対する新しい $\epsilon$-貪欲方策 $\pi'$ は必ず改善だ。つまり $v_{\pi'}(s) \ge v_\pi(s)$。
証明の核心は、新しい方策で一歩打ったときの値が、古い方策の値以上であることを示すことだ。
$$q_\pi(s,\pi'(s)) = \sum_{a} \pi'(a|s)\, q_\pi(s,a) = \frac{\epsilon}{m}\sum_{a} q_\pi(s,a) + (1-\epsilon)\max_a q_\pi(s,a)$$ここで $\max_a q_\pi(s,a)$ は、どんな加重平均以上である。特に、古い方策 $\pi$ の確率から $\epsilon/m$ だけ差し引いた残りで作った加重平均より大きい。
$$\ge \frac{\epsilon}{m}\sum_{a} q_\pi(s,a) + (1-\epsilon)\sum_{a} \frac{\pi(a|s) - \epsilon/m}{1-\epsilon}\, q_\pi(s,a) = \sum_{a}\pi(a|s)\, q_\pi(s,a) = v_\pi(s)$$まとめると $q_\pi(s,\pi'(s)) \ge v_\pi(s)$ であり、方策改善定理により $v_{\pi'}(s) \ge v_\pi(s)$ だ。$\epsilon$-貪欲で改善しても損はないこと、この保証があってこそ安心して探索を混ぜられる。
GLIE
とはいえ、いつまでも $\epsilon$ だけ無作為に振る舞えば、最後まで最適方策にぴったり張り付くことはできない。だから探索は無限に行いつつ、次第に減らさねばならない。この条件がGLIE（Greedy in the Limit with Infinite Exploration）だ。二つを要求する。
- すべての状態-行動対を無限回訪問する: $\lim_{k\to\infty} N_k(s,a) = \infty$。
- 方策が結局貪欲へ収束する: $\lim_{k\to\infty} \pi_k(a|s) = \mathbf{1}(a = \arg\max_{a'} Q_k(s,a'))$。
$\epsilon$-貪欲は $\epsilon$ を0へ減らせばGLIEになる。最も簡単なスケジュールが $\epsilon = 1/k$ だ。序盤は多く彷徨い（小さい $k$ なら大きい $\epsilon$）、回を重ねるほど探索を減らして貪欲へ収束する。無限に探索しつつも結局は最適を選び出す、絶妙な均衡だ。
GLIEモンテカルロ制御
これで一つのアルゴリズムに組み上がる。$k$ 番目のエピソードを現在の方策 $\pi$ で取る。そのエピソードの各状態 $S_t$、行動 $A_t$ について
$$N(S_t,A_t) \leftarrow N(S_t,A_t) + 1$$$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \frac{1}{N(S_t,A_t)}\big(G_t - Q(S_t,A_t)\big)$$で行動価値をリターンの平均のほうへ引き寄せる。そのあと $\epsilon \leftarrow 1/k$ に減らし、$\pi \leftarrow \epsilon\text{-貪欲}(Q)$ で方策を改善する。定理により、このGLIEモンテカルロ制御は最適行動価値へ収束する。$Q(s,a) \to q_*(s,a)$。
シルバーの例は再びブラックジャックだ。ディーラーの規則も確率も知らないまま数多の勝負を実際に打ちながら $Q$ を更新し、$\epsilon$-貪欲で方策を磨けば、人が紙の上で整理した「基本戦略」の表にきわめて近い方策がひとりでに浮かび上がる。いつカードを引き足しいつ止めるかを、経験だけで学習してのけたのだ。
方策オン型TD制御：Sarsa
モンテカルロの代わりに時間差分学習を制御ループに挿せば、自然な改善になる。TDはMCより分散が低く、オンラインで、終わっていない系列からも学ぶ。だから $Q(S,A)$ にTDを適用し、$\epsilon$-貪欲で改善し、毎歩更新しようというのが発想だ。
実際に取った次の行動 $A'$ で更新する。状態、行動、報酬、次状態、次行動をすべて使うのでSarsaだ。
$$Q(S,A) \leftarrow Q(S,A) + \alpha\,\big(R + \gamma Q(S',A') - Q(S,A)\big)$$行動を選ぶ方策と学ぶ方策が同じだ（オンポリシー）。毎歩ごとに評価（Sarsaで $Q\approx q_\pi$）と改善（$\epsilon$-貪欲）を一緒に回す。
Sarsaが最適行動価値へ収束するには二つの条件が要る。一つは先に見たGLIE方策列であり、もう一つはステップサイズ $\alpha_t$ がロビンス・モンロー条件を満たすことだ。つまり $\sum_{t=1}^{\infty}\alpha_t = \infty$ かつ $\sum_{t=1}^{\infty}\alpha_t^2 < \infty$。前の和が無限であるとは、どれほど遠くまで行くべき値でも結局到達できるだけの歩幅の総量が十分だということであり、後の和が有限であるとは、雑音が次第に収まって値が一点に落ち着くということだ。（実務ではこの条件を厳密に守らず、小さな定数 $\alpha$ を使う場合が多い。）
風の吹く格子
シルバーの例は風の吹く格子だ。出発点から到達点まで上下左右に動くのだが、到達するまで毎歩報酬 $-1$ だ（割引なし）。だからできるだけ早く到達するのが目標だ。落とし穴は、特定の列に上へ吹く風があることだ。その列では、自分が移動したあと風が駒を上へ1、2マス余分に押し上げる。Sarsaはこの風を勘案して回り込む経路を学ぶ。風が押す方向をあらかじめ計算に入れ、目標にぴたりと着地する迂回路を見つけ出す。
nステップSarsaとSarsa(λ)
予測でそうだったように、制御でも一歩と最後までは両極端にすぎない。n歩を見通すnステップQリターンがその間をつなぐ。
$$q_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q(S_{t+n})$$$n=1$ なら $R_{t+1} + \gamma Q(S_{t+1})$ で普通のSarsa、$n=\infty$ ならエピソードの最後まで行くモンテカルロだ。nステップSarsaは $Q$ をこのnステップQリターンのほうへ引き寄せる。
$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(q_t^{(n)} - Q(S_t,A_t)\big)$$前方視点のSarsa(λ)は、すべての $n$ のQリターンを $(1-\lambda)\lambda^{n-1}$ の重みで一挙に混ぜた $q^\lambda$ リターンを目標に使う。
$$q_t^\lambda = (1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1} q_t^{(n)}, \qquad Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(q_t^\lambda - Q(S_t,A_t)\big)$$前方視点は未来をすべて見なければならないので、エピソードが終わってから計算される。後方視点のSarsa(λ)は適格度トレースで同じことをオンラインでやってのける。ただし今度はトレースが状態ごとではなく、各（状態、行動）対ごとに一つずつ付く。
$$E_0(s,a) = 0, \qquad E_t(s,a) = \gamma\lambda\, E_{t-1}(s,a) + \mathbf{1}(S_t = s, A_t = a)$$そしてTD誤差 $\delta_t = R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t)$ を、このトレースに比例させてすべての対へ流し込む。
$$Q(s,a) \leftarrow Q(s,a) + \alpha\,\delta_t\, E_t(s,a)$$直観はこうだ。たまたま報酬に到達すると、その良い信号がたった今踏んだ（状態、行動）対へトレースを辿って一挙に広がる。最近踏んだものほどトレースが濃いので、より大きく補正を受ける。報酬が稀な問題では、この広がりのおかげで学習が大きく速まる。シルバーの格子の例を見ると、一歩ぶんのSarsa(0)は目標のすぐ手前一マスだけ値が上がるのに対し、Sarsa(λ)は目標へつながる経路全体に一度に信用が配分される。
方策オフ型学習
ここまでは行動する方策と学ぶ方策が同じだった。方策オフ型はこの二つを分離する。行動方策 $\mu$ に従って $\{S_1,A_1,R_2,\dots,S_T\}\sim\mu$ を経験しながら、目標方策 $\pi$ の価値 $v_\pi(s)$ や $q_\pi(s,a)$ を学ぶ。なぜこれが重要か。シルバーは四つの動機を挙げる。
- 人や他のエージェントを観察して学ぶ。他人のプレイを見て学ぶのだ。
- 古い方策たち $\pi_1,\pi_2,\dots,\pi_{t-1}$ が作った経験を再利用する。捨てずにもう一度使う。
- 探索的な方策に従いながら最適方策を学ぶ。これがQ学習の核心的な動機だ。
- 一つの行動方策に従いながら複数の目標方策を同時に学ぶ。
重点サンプリング
問題は、$\mu$ が作った経験で $\pi$ の期待値をどう推定するかだ。答えが重点サンプリング（importance sampling）だ。別の分布 $P$ に対する期待値を、手元にある分布 $Q$ で書き直す技だ。
$$\mathbb{E}_{X\sim P}[f(X)] = \sum_X P(X) f(X) = \sum_X Q(X)\frac{P(X)}{Q(X)}f(X) = \mathbb{E}_{X\sim Q}\left[\frac{P(X)}{Q(X)}f(X)\right]$$二つの分布の比 $P/Q$ で重みを付け直すのだ。
モンテカルロにこれを使うと、$\mu$ で作ったリターン $G_t$ に二つの方策の類似度を掛けて補正する。問題は、リターンがエピソードの最後まで続くので、毎歩の確率比をエピソードの間じゅう掛けねばならないことだ。
$$G_t^{\pi/\mu} = \frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}\frac{\pi(A_{t+1}|S_{t+1})}{\mu(A_{t+1}|S_{t+1})}\cdots\frac{\pi(A_T|S_T)}{\mu(A_T|S_T)}\, G_t$$$$V(S_t) \leftarrow V(S_t) + \alpha\big(G_t^{\pi/\mu} - V(S_t)\big)$$$\pi$ が0でないのに $\mu$ が0だと使えず（経験していない経験は補正もできない）、何より確率比を何十回も掛けていくと分散が爆発する。一つでも非常に小さいか大きいと、積全体が揺れ動く。だからMCの重点サンプリングは実戦ではほとんど使えない。
TDに使うと事情が大きく良くなる。TD目標 $R + \gamma V(S')$ はちょうど一歩ぶんなので、ただ一度の重点補正だけで済む。
$$V(S_t) \leftarrow V(S_t) + \alpha\left(\frac{\pi(A_t|S_t)}{\mu(A_t|S_t)}\big(R_{t+1} + \gamma V(S_{t+1})\big) - V(S_t)\right)$$二つの方策が一歩だけ似ていればよいので、分散がモンテカルロよりはるかに低い。
Q学習：重点サンプリングがまったく要らない
行動価値 $Q(s,a)$ の方策オフ型学習では、もっと劇的なことが起きる。重点サンプリングがまったく要らない。理由はこうだ。次に実際にする行動 $A_{t+1}$ は行動方策 $\mu$ で選ぶが、目標の中では目標方策 $\pi$ が選んだ代替行動 $A'\sim\pi(\cdot|S_t)$ の値をそのまま使う。
$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha\big(R_{t+1} + \gamma Q(S_{t+1},A') - Q(S_t,A_t)\big)$$目標にすでに $\pi$ が選んだ行動を直接入れるので、あとから確率比で補正するものが残らない。ここで目標方策 $\pi$ を $Q$ に対して貪欲に置くと、つまり $\pi(S_{t+1}) = \arg\max_{a'} Q(S_{t+1},a')$ と置くと、目標がすっきり単純になる。
$$R_{t+1} + \gamma Q(S_{t+1}, \arg\max_{a'} Q(S_{t+1},a')) = R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a')$$$\pi$ が選んだ代替行動がすなわち $Q$ を最大化する行動なので、$\arg\max$ が $\max$ へ畳まれる。これがQ学習のあの有名な更新式だ。
$$Q(S,A) \leftarrow Q(S,A) + \alpha\,\big(R + \gamma \max_{a'} Q(S',a') - Q(S,A)\big)$$行動は $\epsilon$-貪欲のような探索方策 $\mu$ で行うが、学ぶ対象は貪欲な最適方策だ。行動方策と目標方策がともに改善され、Q学習は最適行動価値へ収束する。$Q(s,a) \to q_*(s,a)$。
崖歩き
方策オン型（Sarsa）と方策オフ型（Q学習）の違いを、崖歩き（cliff walking）の例がよく見せてくれる。格子の下の縁が崖で、崖に落ちると大きな罰点を受けて出発点へ戻される。目標は崖を避けて反対側の端に着くことだ。
Q学習は崖のすぐ横を辿る最短経路を学ぶ。目標方策が貪欲なので「最適は崖の横の直線」だとすぐに身につける。問題は、実際に歩くときは $\epsilon$-貪欲で動くので、たまにその $\epsilon$ の瞬間に崖へ足を踏み外すことだ。だから学習中の実際の成績はしばしば急落する。
Sarsaは違う。方策オン型なので実際に取る次の行動、つまり探索まで含めた行動で学ぶ。「たまに無作為に動く自分自身」を計算に入れるので、崖から一マス離れた安全な迂回路を学ぶ。最適ではないが、探索中の事故が少なく実際の成績はより良い。最適を知るQ学習と、探索まで勘案して安全なSarsa、二つの性格の違いがここでもくっきりだ。
崖歩き。下の縁が崖（−100）で、SからGへ行かねばならない。エピソードを回すとQ学習は崖のすぐ横の最短経路（赤）を、Sarsaは探索まで勘案して一マス離れた安全経路（青）を学ぶ。εを大きくするとSarsaがより遠くへ回り込むのが見える。
DPとTD、一目で
制御まで来ると、第3講の動的計画法と今回の講義の対応がくっきりする。同じベルマン方程式を、モデルを知っていれば全幅バックアップで解き、知らなければ標本バックアップで解くわけだ。対応はこう対になる。
- ベルマン期待方程式（$v_\pi$）：全幅なら反復方策評価、標本ならTD学習。
- ベルマン期待方程式（$q_\pi$）：全幅ならQ方策反復、標本ならSarsa。
- ベルマン最適方程式（$q_*$）：全幅ならQ価値反復、標本ならQ学習。
更新式で並べると対応がさらに鮮明だ。$x \xleftarrow{\alpha} y$ を $x \leftarrow x + \alpha(y-x)$ の約束とすれば、
$$Q(s,a) \leftarrow \mathbb{E}[R + \gamma Q(S',A') \mid s,a] \quad\Longleftrightarrow\quad Q(S,A) \xleftarrow{\alpha} R + \gamma Q(S',A')$$左は期待値をモデルで全部なめるQ方策反復、右は経験した標本一つでその場を埋めるSarsaだ。最適方程式も同じ構造だ。
$$Q(s,a) \leftarrow \mathbb{E}\Big[R + \gamma \max_{a'} Q(S',a') \mid s,a\Big] \quad\Longleftrightarrow\quad Q(S,A) \xleftarrow{\alpha} R + \gamma \max_{a'} Q(S',a')$$DPで学んだ骨格が、モデルフリーで期待値の代わりに標本でそのまま繰り返されるのだ。
このQ学習が第6講で神経回路網と出会いDQNになる。そしてここまでは状態を表に一つずつ保存した（テーブル型）。状態が非常に多いか連続なら表は不可能だ。次講は価値関数を関数で近似する。