遂に第7章から第3部です！第3部では、第2部で紹介された3種類（動的計画法、モンテカルロ法、TD法）の基本的な解法群の統一された使い方の紹介です。
最初は適格度トレース。このメカニズムはモンテカルロ法とTD法とを統合したものです。次に、関数近似を取り入れた状態と行動間の関係の一般化（generalization）。最後に、動的計画法とヒューリスティック探索の長所を取り入れるために環境モデルの導入です。
適格度トレース（eligibility trace）は強化学習の基本的なメカニズムの1つです。TD法を適格度トレースによって補強すると、モンテカルロ法を一方の端、1ステップTD法を他方の端とした範囲にまたがる一連の手法が作り出されます。これらを両極端として、中間にはさらに良い手法を見出すことができます。
適格度トレースは理論的には前方観測的な見方（forward view）と呼ばれ、技術的には後方観測的な見方（backward view）と呼ばれます。
- 前方観測的な見方: 適格度トレースを用いた手法で何が計算されるのかを理解するのに有用
- 後方観測的な見方: アルゴリズムそれ自体の直感を発展させるのに適している
最初に予測問題を、そして次に制御問題を考えます。
nステップTD予測
モンテカルロ法とTD手法との中間に位置する手法はどのような空間を持つでしょうか？
モンテカルロ法では、当該状態から終端エピソードまで観測された報酬の全ての系列に基づいてバックアップを遂行します。他方、単純なTD手法のバックアップでは1つ次の報酬だけに基づきます。従って、中間的な手法の1つは中間的な個数（1個よりも多く、終了までの全ての報酬の個数よりも少ない）の報酬に基づいてバックアップを遂行することになります。
V^πに対する一連のnステップ・バックアップ(n-step backup)を図式化したもが以下の通りです。
nステップに時間的差分を拡張したものはnステップTD法(n-step TD method)と呼ばれます。状態価値の更新方法は2つあります。
- オンライン更新(on-line updating)：推定値の増分が計算され次第エピソード中で更新が行われる
- オフライン更新(off-line updating)：増分は累積されていくだけでエピソードの終端に至るまで価値推定の変更に使われることはない
推定値の増分は以下の式で表されます。
$$ \Delta V_t(s_t) = \alpha [R_t^{(n)} – V_t(s_t)] $$
nステップTD手法は実装には不都合があるため実際はめったに使われません。nステップ収益を計算するためには、結果として得られる報酬と状態を観測するまでnステップ待つことを必要とします。
TD(λ)の前方観測的な見方
TD(λ)アルゴリズムはnステップ・バックアップを平均化する方法の1つです。この平均にはnステップ分のバックアップ全てが含まれており、その各々はλ^{n-1}(0≦λ≦1)に比例して重み付けされます。結果として得られるバックアップはλ収益(λ-return)と呼ばれる収益に対するものとなり次のように定義されます。
$$ R_t^{\lambda} = (1 – \lambda ) \sum_{n=1}^∞ \lambda^{n-1} R_t^{(n)} $$
λ収益アルゴリズム(λ-return algorithm)は、λ収益を用いてバックアップを実行するアルゴリズムです。各時間ステップtでそのときに発生する状態価値に対する増分を次のように計算します。
$$ \Delta V_t(s_t) = alpha [R_t^{\lambda} – V_t(s) ]
ある状態から前方を眺めて更新を行った後、次の状態に移動し以前の状態を参照する必要はありません。（前方観測的見方）
TD(λ)の後方観測的な見方
後方観測的な見方は概念的にも計算上でも単純であるこという理由でとても有用です。TD(λ)の後方観測的見方においては各状態に関連する付加的なメモリ変数が存在し、それが適格度トレース(eligibility trace)となります。各ステップにおいて、この適格度トレース(e_t(s))は、全ての状態に対してΓλだけ減衰し、そのステップで訪問された1個の状態の適格度トレースは全てのsに対して1だけ増加します。
この種類の適格度トレースは累積トレース(accumulationg trace)と呼ばれます。そう呼ばれる理由はある状態が訪問されると累積され、その状態が訪問されないと減衰するからである。
どの時点でも、適格度トレースでは最近訪問された状態が記録されます。ここで「最近」はΓλで定義され、適格度トレースは強化事象が発生した時に、学習上の変化を受けることが適格であることの度合いを示します。対象としている強化事象は1ステップTD誤差となります。
Γ：割引率
λ：トレース減衰パラメータ(trace-decay parameter)
$$ \delta_t = r_{t+1} + \gamma V_t ( s_{t+1} ) – V_t (s_t) $$
全体的なTD誤差信号は、最近訪問した非ゼロトレース信号（恐らく非ゼロなe_t）を持つ全ての状態に対して、比例分配的な更新を生じさせます。
$$ \Delta_t \alpha \delta_t e_t (s) $$
TD(λ)の後方観測は、時間をさかのぼる向きに行われます。自分たちが状態の流れの上に乗ってTD誤差を計算し、以前に訪問した状態の方に向かってその誤差の値を叫ぶことを想像してみましょう。
もしλ=1であるなら、以前に訪問した状態群に与えられる信用は1ステップあたりΓの割合で低下します。これはモンテカルロ法を実行するために必要なことをしているだけであることがわかります。
TD(1)は、これまでに示したものよりも一般的な形でモンテカルロ法を実装する方法で適用範囲もかなり広がります。TD(1)はオンラインで漸進的な実装が可能です。そのため、モンテカルロ法のようにエピソードが終わるまで何も学習しないということがなくなります。
前方観測的見方と後方観測的見方の等価性
上記において技術的であると定義されたオフラインTD(λ)の重み更新、オフラインλ収益アルゴリズムの重み更新とが同じであることを示します。TD(λ)の前方観測的（理論的）な見方と、後方観測的（技法的）な見方を比べてみましょう。
$$ \sum_{t=0}^{T-1} \Delta V_t^{TD} (s) = \sum_{t=0}^{T-1} \Delta V_t^λ (s_t) I_{ss_t} $$
I_{ss_t}は一致関数(identity-indicator function)であり、s = s_tならばその値は1に等しく、それ以外では0である。オフラインの場合には以下のようになります。
$$ \sum_{t=0}^{T-1} \Delta V_t^{λ} (s_t) I_{ss_t} = \sum_{t=0}^{T-1} \alpha I_{ss_t} \sum_{k=t}^{T-1} (λ\gamma)^{k-t} \delta_k $$
Sarsa(λ)
予測だけではなく制御においても適格度トレースを使うにはどうすればよいでしょうか。これまで同様よく出てくる考え方は状態価値V_t(s)ではなく、行動価値Q_t(s, a)を学習することです。どのようにして適格度トレースが、直接的なやり方でSarsaと組み合わされて方策オン型TD制御手法を作り上げるかを示します。
Sarsa(λ)の考え方は、TD(λ)予測手法を状態ではなく状態行動対に対して適用することにあります。各状態に対するトレースではなく状態行動対に対するトレースを行うことが必要となります。
$$ Q_{t+1} (s, a) = Q_t(s, a) + \alpha \delta_t e_t (s, a) $$
$$ \delta_t = r_{t+1} + \gamma Q_t(s_{t+1}, a_{t+1}) – Q_t(s_t, a_t) $$
式7.10参照ください。
（wordpressのlatexで複数行ができないため…）
Q(λ)
適格度トレースとQ学習の組み合わせた異なる2つの手法があります。それはWatkinsのQ(λ)とPengのQ(λ)です。WatkinsのQ(λ)は、行動価値の知識に基づき最初の探査後に取られた行動1個を見ます。オフライン更新を仮定したバックアップ線図は次の通り。
（196ページ式参照）
探査的行動が取られる度にトレースを切り離すことで、適格度トレースを使うことの利点がかなり失われます。PengのQ(λ)は、WatkinsのQ(λ)の代わりにこの問題を解決することを意図したQ(λ)です。PengのQ(λ)は、Sarsa(λ)とWatkinsのQ(λ)の混合型と考えることができます。
PengのQ(λ)はQ学習と異なり、探索的行動とグリーディ行動との間の区別はありません。各要素バックアップは広いステップ数の行動にまたがっていますが、最後の部分で行動群に関する最大化を行って完成します。要素バックアップは方策オン型でも方策オフ型でもありません。一方でPengのQ(λ)は、WatkinsのQ(λ)ほど単純に実装することができません。
アクター・クリティック手法における適格度トレース
アクター・クリティック手法のクリティックの部分は単にV^πに関する方策オン型学習です。これを行うために、TD(λ)アルゴリズムを使うことができ、各状態に対して1この適格度トレースを用います。
アクター部分では各状態行動対に対して適格度トレースを用いることが必要になります。したがって、2組（各状態と各状態行動対）のトレースを使う必要があります。
式7.12参照
入替え更新トレース
入替え更新トレースを(replacing trace)を用いることによって、性能が改善されうることがあります。最初の訪問によるトレースが完全にゼロに減衰する前に再訪問されたと仮定します。累積トレースでは再訪問によってトレースはさらに増加し、1よりも大きな値に向かいますが入替え更新ではトレースは1に再設定されます。
このアルゴリズムを入替え更新トレース手法と呼び、累積トレースとの違いはわずかですが学習速度はかなり改善されます。
※ ここの例題がわかりやすいので是非本書を読んでみてください。
実装上の問題
単純化実装ではすべての状態（あるいは状態行動対）において、あらゆる時間ステップで価値推定と適格度トレースの両者を更新することが要求されます。幸いなことに、ほとんどすべての状態の適格度トレースは常にゼロに近い値であり、最近訪問された状態群のみが0よりかなり大きなトレース値を持ちます。他の状態群における更新は本質的には影響を及ぼさないので、これら少数の状態のみの更新が必要です。
λ可変更新
λの値をステップごとに変化させることを許せば、これまでに記述してきた内容からさらにλ収益を一般化することができます。この場合、トレースの更新を次のようにする。
（205ページ式参照。）