これまでは状態ごとにマスを一つずつ置いた表に価値を書いてきた。しかしバックギャモンは状態が$10^{20}$個、囲碁は$10^{170}$個、ヘリコプターはそもそも連続でマスを数えることすらできない。表はここで崩れる。代わりに、わずかなパラメータの関数で価値を近似し、見たことのない状態へも一般化する。
講義スライド: PDF
なぜ表を捨てるのか
表形式ルックアップの問題は二つある。状態や行動が多すぎてメモリに収まらないこと、そして収まったとしても各状態の価値を一つずつ別々に学ぶのは遅すぎることだ。一度も訪れていない状態は永遠にわからないままになる。
解法は関数近似だ。真の価値$v_\pi(s)$を、パラメータ$\mathbf{w}$をもつ近似関数で代替する。
$$\hat v(s, \mathbf{w}) \approx v_\pi(s) \quad\text{または}\quad \hat q(s, a, \mathbf{w}) \approx q_\pi(s, a)$$パラメータは状態数よりはるかに少ない。だから見た状態で学んだことが、見ていない状態へ漏れ出す（一般化）。そしてこの$\mathbf{w}$を、前の講義で学んだMCやTDで更新する。
近似器をどうつなぐかによって、三つのアーキテクチャがある。
- 状態を一つ入れて、その状態の価値$\hat v(s, \mathbf{w})$を一つ吐く。
- 状態と行動をともに入れて、その組の行動価値$\hat q(s, a, \mathbf{w})$を一つ吐く。
- 状態を一つだけ入れて、可能なすべての行動の行動価値$\hat q(s, a_1, \mathbf{w}), \dots, \hat q(s, a_m, \mathbf{w})$を一度に吐く。
三つ目がDQNの使う方式だ。制御では$\max_a \hat q(s, a)$をよく求める必要があるが、三つ目の構造なら一度の順伝播ですべての行動値が出るので、その最大値を選ぶのはほぼタダに近い。
近似器の候補は多い。特徴の線形結合、ニューラルネットワーク、決定木、最近傍、フーリエやウェーブレット基底など。この講義はそのうち微分可能なものだけを扱う（勾配をたどる必要があるから）。線形結合とニューラルネットワークがその主役だ。
そして重要な但し書きが一つある。強化学習のデータは普通の教師あり学習とは異なる。方策が変われば分布が変わるので非定常であり、連続する状態どうしは強く絡み合っていて独立同分布（iid）ではない。だから教師あり学習をそのまま持ってきては使えず、こうしたデータに合った学習法が別に必要になる。この講義の半分はその話だ。
増分法：勾配をたどって降りる
目標ははっきりしている。近似価値と真の価値の平均二乗誤差を減らすことだ。
$$J(\mathbf{w}) = \mathbb{E}_\pi\big[(v_\pi(S) - \hat v(S, \mathbf{w}))^2\big]$$この$J$の勾配と逆向きに$\mathbf{w}$を少しずつ押すと、局所最小へ降りていく。ステップ幅$\alpha$を置いて$\Delta\mathbf{w} = -\tfrac{1}{2}\alpha\nabla_\mathbf{w}J(\mathbf{w})$である。期待値を展開すると
$$\Delta\mathbf{w} = \alpha\,\mathbb{E}_\pi\big[(v_\pi(S) - \hat v(S, \mathbf{w}))\nabla_\mathbf{w}\hat v(S, \mathbf{w})\big]$$全体の期待値を毎回計算するのは高くつく。そこで一度に標本を一つだけ引いて勾配を真似る。これが確率的勾配降下（SGD）だ。
$$\Delta\mathbf{w} = \alpha\,(v_\pi(S) - \hat v(S, \mathbf{w}))\nabla_\mathbf{w}\hat v(S, \mathbf{w})$$標本一つの更新の期待値が全体の勾配更新と等しいので、多く繰り返せば結局同じところへ行き着く。
特徴ベクトルと線形近似
状態を数個の数に要約したものが特徴ベクトルだ。
$$\mathbf{x}(S) = \big(x_1(S), \dots, x_n(S)\big)^\top$$ロボットがランドマークから離れた距離、株式市場のトレンド、チェス盤の駒配置といったものが特徴になる。もっとも単純な近似は、これらの特徴を線形に結合することだ。
$$\hat v(S, \mathbf{w}) = \mathbf{x}(S)^\top \mathbf{w} = \sum_{j=1}^{n} x_j(S)\,w_j$$このとき目的関数は$\mathbf{w}$について二次式なので、局所最小がそのまま大域最小になる。SGDが大域最適へ収束する。しかも勾配がとてもきれいだ。$\nabla_\mathbf{w}\hat v(S, \mathbf{w}) = \mathbf{x}(S)$なので、更新式は
$$\Delta\mathbf{w} = \alpha\,(v_\pi(S) - \hat v(S, \mathbf{w}))\,\mathbf{x}(S)$$となる。言葉にすれば、更新＝ステップ幅×予測誤差×特徴値だ。誤差が大きく、その特徴が強くオンになっていた方向へパラメータを押す。
ここで面白い事実が一つ。表形式ルックアップは線形近似の特殊な場合だ。特徴を「この状態かどうか」の指示子として取ると
$$\mathbf{x}^{\text{table}}(S) = \big(\mathbf{1}(S = s_1), \dots, \mathbf{1}(S = s_n)\big)^\top$$この特徴ベクトルと$\mathbf{w}$を掛けると、現在の状態に対応するマスの$w_i$だけが生き残る。つまりパラメータベクトルが、各状態の価値をそのまま収めた表になる。表は近似の反対ではなく、特徴を極端に細かく刻んだ片方の端にすぎない。
真の値がない：目標を差し替える
これまでの式には真の価値$v_\pi(S)$が入っていた。しかし強化学習には正解を教えてくれる監督者がいない。あるのは報酬だけだ。そこで$v_\pi(S)$の場所に、前の講義で作った目標を代わりに差し込む。
- MCは実際のリターン$G_t$を目標に： $$\Delta\mathbf{w} = \alpha\,(G_t - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
- TD(0)はブートストラップしたTD目標$R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w})$を： $$\Delta\mathbf{w} = \alpha\,(R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
- TD(λ)はλリターン$G_t^\lambda$を： $$\Delta\mathbf{w} = \alpha\,(G_t^\lambda - \hat v(S_t, \mathbf{w}))\nabla_\mathbf{w}\hat v(S_t, \mathbf{w})$$
MCのリターンは真の値の不偏な（ただしうるさい）標本だ。だから$\langle S_1, G_1\rangle, \langle S_2, G_2\rangle, \dots$を訓練データとして教師あり学習のように回せるし、非線形近似器を使っても局所最適へ収束する。
TD目標はまだ正しくない推定値$\hat v(S_{t+1}, \mathbf{w})$を含んでいるので、偏った標本だ。それでも訓練データとして立てて学習でき、線形TD(0)は大域最適の近くへ収束する。線形TD(0)の更新は、TD誤差$\delta$を使って$\Delta\mathbf{w} = \alpha\delta\,\mathbf{x}(S)$ときれいに書ける。
TD(λ)も同様に、前方ビュー（λリターンを目標に）と後方ビュー（適格度トレースでオンライン処理）があり、線形では両者が正確に同じ更新を与える。後方ビューは
$$\delta_t = R_{t+1} + \gamma\hat v(S_{t+1}, \mathbf{w}) - \hat v(S_t, \mathbf{w})$$$$E_t = \gamma\lambda E_{t-1} + \mathbf{x}(S_t), \qquad \Delta\mathbf{w} = \alpha\delta_t E_t$$いまやトレースが状態指示子ではなく特徴ベクトル$\mathbf{x}(S_t)$を積む、という点だけが第4講と異なる。
制御：行動価値を近似する
予測を越えて制御へ行くには、状態価値ではなく行動価値を近似する。$\hat q(S, A, \mathbf{w}) \approx q_\pi(S, A)$の平均二乗誤差を減らし、近似した$\hat q$で方策を$\varepsilon$貪欲に改善する一般化方策反復を回す。線形なら状態と行動をともに特徴化して$\mathbf{x}(S, A)$と置き、
$$\hat q(S, A, \mathbf{w}) = \mathbf{x}(S, A)^\top\mathbf{w}, \qquad \Delta\mathbf{w} = \alpha\,(q_\pi(S, A) - \hat q(S, A, \mathbf{w}))\mathbf{x}(S, A)$$で更新する。予測のときと同様に、$q_\pi$の場所にMCなら$G_t$、TD(0)なら$R_{t+1} + \gamma\hat q(S_{t+1}, A_{t+1}, \mathbf{w})$、TD(λ)ならλリターンを差し込む。TD(0)版がそのまま、近似器を載せたSarsaだ。
マウンテンカー：連続状態を特徴に
マウンテンカーは、力の足りない車が谷に閉じ込められている問題だ。ただ右へ押しても登れず、わざと反対の丘へ後退してから反動で越えなければならない。状態は位置と速度、どちらも連続だ。マスが無限なので表は使えない。
シルバーはここに線形Sarsaを載せる。連続状態を特徴に変える方法が肝心だが、粗い符号化（coarse coding）を使う。位置・速度平面を互いに重なる複数の格子（タイル）で覆い、いまの状態がどのタイルの中にあるかをオン・オフする指示子で特徴を作る。一点が複数のタイルに同時にまたがるので、隣接した状態どうしが特徴を共有し、だからなめらかに一般化される。タイルの代わりに放射基底関数（RBF、中心から離れるほどなめらかに減る鐘型の特徴）を使っても、同じように連続表面を覆える。
こうして特徴さえ作ってやれば、あとは先に見た線形Sarsaの更新そのままだ。学習が進むにつれて谷の形をした価値表面が次第にくっきりし、反動で丘を越える方策が自然に浮かび上がる。
ブートストラップすべきか
増分法から自然についてくる問い。λをいくつに置くか。$\lambda = 0$は完全ブートストラップ（TD）、$\lambda = 1$はブートストラップなし（MC）、その間が折衷だ。
シルバーは、いくつかのドメイン（マウンテンカーを含む）でλを変えながら性能を測ったグラフを見せる。結論は一貫している。$\lambda = 1$（純粋なMC）はほとんど常に最悪で、性能がもっとも良い地点はたいていその中間のどこかだ。第4講でブートストラップとサンプリングを二軸に描いたスペクトルが、関数近似を載せた実戦でもそのまま実証されるわけだ。ブートストラップは偏りを甘受して分散を大きく減らすが、近似器のノイズと出会うと、その分散削減の利得はとりわけ大きい。
Bairdの反例：発散の瞬間
良い知らせはここで終わる。三つが重なると（オフ方策＋線形近似＋TD）、学習は収束するどころかパラメータが実際に無限大へ発散する。Bairdの反例がその具体的な証拠だ。わずか数個の状態からなる小さなMDPだが、オフ方策で線形TDを回すと重みが反復のたびに大きくなり、グラフが爆発する。バグではなくアルゴリズムの性質だ。
収束表にまとめるとこうなる。
| 表形式ルックアップ | 線形 | 非線形 | |
|---|---|---|---|
| オン方策 MC | O | O | O |
| オン方策 TD(0) | O | O | X |
| オン方策 TD(λ) | O | O | X |
| オフ方策 MC | O | O | O |
| オフ方策 TD(0) | O | X | X |
| オフ方策 TD(λ) | O | X | X |
オフ方策＋線形＋TDのマスがまさにX、Bairdが弾ける場所だ。
根本の原因を突くとこうだ。TD更新はある目的関数の本当の勾配ではない。見た目には$\Delta\mathbf{w} = \alpha\delta\,\mathbf{x}(S)$が勾配降下のように見えるが、TD目標のなかの$\hat v(S_{t+1}, \mathbf{w})$も$\mathbf{w}$に依存しているのに、我々はその部分を微分せず定数のように凍らせておく（半勾配）。本当の勾配ではないので「丘を降りる」保証がなく、オフ方策でデータ分布がずれると、かえって丘をよじ登ることがある。
処方は、本当の勾配をたどらせることだ。Gradient TDは、射影ベルマン誤差というよく定義された目的関数の実際の勾配をたどって降りる。すると、オフ方策に線形・非線形近似を載せても収束が回復する。
| 表形式ルックアップ | 線形 | 非線形 | |
|---|---|---|---|
| オフ方策 TD | O | X | X |
| オフ方策 Gradient TD | O | O | O |
制御へ行くと状況はもう一枚微妙になる。線形近似を使ったモンテカルロ制御やSarsaはたいてい最適の近くへ行きはするが、正確に一点で止まらず、近似最適の周りを絶えず振動しつづける（チャタリング）。方策が少し変われば価値が変わり、その価値がまた方策を少し変える、というフィードバックのためだ。線形Q学習はそもそも発散しうるし、勾配Q学習がこれを抑え込む。
バッチ法：経験を集めて一度に
増分法（SGD）は単純で魅力的だが、標本を無駄にする。一度の更新に使った経験を捨ててしまうからだ。バッチ法は逆に問う。これまで集めた経験全体にもっともよく合う価値関数は何か。
経験を状態・価値の組の集まり$\mathcal{D} = \{\langle s_1, v_1^\pi\rangle, \dots, \langle s_T, v_T^\pi\rangle\}$と置くと、最小二乗はこの全体に対する誤差の和を最小化する$\mathbf{w}$を探す。
$$LS(\mathbf{w}) = \sum_{t=1}^{T}(v_t^\pi - \hat v(s_t, \mathbf{w}))^2$$経験再生
この最小二乗解はSGDでも得られる。毎ステップ新しい経験だけを使う代わりに、蓄えておいた経験プール$\mathcal{D}$から組を無作為に引き直して更新することを繰り返す。
- 経験から標本を引く：$\langle s, v^\pi\rangle \sim \mathcal{D}$
- SGD更新を適用する：$\Delta\mathbf{w} = \alpha\,(v^\pi - \hat v(s, \mathbf{w}))\nabla_\mathbf{w}\hat v(s, \mathbf{w})$
これを十分に繰り返すと最小二乗解$\mathbf{w}^\pi = \arg\min_\mathbf{w} LS(\mathbf{w})$へ収束する。これが経験再生（experience replay）だ。同じ経験を何度も使い回すので標本効率が上がり、無作為に混ぜて引くので連続する状態どうしの相関（非iid問題）も壊れる。
線形なら閉じた解
近似が線形$\hat v(s, \mathbf{w}) = \mathbf{x}(s)^\top\mathbf{w}$なら、繰り返す必要すらない。最小二乗解を直接計算できる。最小点では期待更新が0でなければならないので
$$\sum_{t=1}^{T}\mathbf{x}(s_t)(v_t^\pi - \mathbf{x}(s_t)^\top\mathbf{w}) = 0$$を解くと
$$\mathbf{w} = \left(\sum_{t=1}^{T}\mathbf{x}(s_t)\mathbf{x}(s_t)^\top\right)^{-1}\sum_{t=1}^{T}\mathbf{x}(s_t)v_t^\pi$$が出る。特徴が$N$個なら、この直接解は逆行列のため$O(N^3)$かかる（シャーマン・モリソンで増分更新すれば$O(N^2)$）。
真の値$v_t^\pi$を知らないのはここでも同じなので、その場所にノイズ混じりの標本を差し込む。リターンを使えばLSMC、TD目標を使えばLSTD、λリターンを使えばLSTD(λ)だ。各場合、MC・TD・TD(λ)の不動点をそのまま閉じた解で解く。興味深いことに、オフ方策で増分TDが発散しても、その不動点を直接解くLSTDは線形で収束する。
制御へ拡張したものが最小二乗方策反復（LSPI）だ。蓄えた経験$\mathcal{D}$を、方策を変えながら反復して再評価する。内側でLSTDQにより行動価値をオフ方策で最小二乗評価し（古い方策が作った遷移で、新しい方策が選ぶ後続行動$A' = \pi_{\text{new}}(S_{t+1})$の値のほうへ引く）、外側で$\pi'(s) = \arg\max_a Q(s, a)$で貪欲改善することを、方策が安定するまで回す。シルバーは50状態のチェーンウォーク問題で、LSPIが数回の反復で最適方策へ収束するのを見せる。
DQN：再生と固定ターゲット
経験再生というアイデアが非線形近似（深層ニューラルネットワーク）と出会って爆発したのがDQNだ。DQNは二つの装置で学習を安定させる。
- 経験再生：$\varepsilon$貪欲方策で行動し、遷移$(s_t, a_t, r_{t+1}, s_{t+1})$を再生メモリ$\mathcal{D}$に積む。学習するときはそこからミニバッチを無作為に引く。相関を壊し、標本を再利用する。
- 固定ターゲットネットワーク：Q学習目標を計算するとき、いま学習中のパラメータ$\mathbf{w}$ではなく、しばらく凍らせておいた古いパラメータ$\mathbf{w}^-$を使う。目標が学習とともに毎ステップ揺れるのを防ぐ。
損失は
$$L_i(\mathbf{w}_i) = \mathbb{E}_{s,a,r,s' \sim \mathcal{D}_i}\left[\left(r + \gamma\max_{a'}Q(s', a'; \mathbf{w}_i^-) - Q(s, a; \mathbf{w}_i)\right)^2\right]$$であり、SGDの変形で最小化する。目標のなかが$\mathbf{w}_i^-$（凍らせたもの）、予測が$\mathbf{w}_i$（学習中）である点が核心だ。
この二つの装置がそれぞれどれだけ寄与するかを、アブレーション実験がはっきり見せる。五つのゲームで再生・固定ターゲットをオン・オフしたスコアだ。
| ゲーム | 再生＋固定ターゲット | 再生のみ | 固定ターゲットのみ | どちらもなし |
|---|---|---|---|---|
| ブレイクアウト | 316.8 | 240.7 | 10.2 | 3.2 |
| エンデューロ | 1006.3 | 831.3 | 141.9 | 29.1 |
| リバーレイド | 7446.6 | 4102.8 | 2867.7 | 1453.0 |
| シークエスト | 2894.4 | 822.6 | 1003.0 | 275.8 |
| スペースインベーダー | 1088.9 | 826.3 | 373.2 | 302.0 |
ブレイクアウトを見ると、どちらもないとき3.2点、どちらもオンで316.8点だ。百倍の差である。二つの安定化装置がなければ、非線形近似＋オフ方策＋ブートストラップという危険な組み合わせがそのまま崩れ、二つの装置を載せた瞬間によみがえる。
ピクセルから人間並みへ
こう安定化したDQNをアタリのゲームに丸ごと付けたものが、第1講で見たあの結果だ。入力はゲームのルールや手を入れた特徴ではなく、直近4フレームの生ピクセルの束だ。出力はジョイスティック・ボタン18通りの位置それぞれの$Q(s, a)$であり（先に述べた三つ目のアーキテクチャ、状態一つからすべての行動値を同時に）、報酬はそのステップのスコア変化だけだ。ネットワーク構造とハイパーパラメータはすべてのゲームで同じに固定した。ゲームごとに手を入れていないのに、ピクセルだけを見て複数のゲームで人間並みの腕前を出した。
表一つ埋められなかった大きな問題をパラメータ近似で越え、その近似が発散しないよう再生と固定ターゲットで押さえたこと。それがこの講義がつないだ橋だ。次の講義では、価値を近似する代わりに方策そのものを直接パラメータ化する方策勾配へと進む。