n-step TD学習とEligibility Trace：強化学習コース(6/N)

はじめに

前回の記事では、TD(0)学習とTD誤差の基礎を学びました。TD(0)は1ステップ先の情報だけで学習できる優れた手法ですが、モンテカルロ法の持つ「実際の経験を多く活用する」という利点を失ってしまいました。

本記事では、TD(0)とモンテカルロ法の長所を組み合わせる多段階TD学習と、その効率的な実装であるTD(λ) について解説します。特に、Eligibility Trace（適格度トレース） という巧妙なメカニズムにより、過去の状態への信用割り当てを効率的に実現する方法を学びます。

これまでのシリーズで学んだ内容は以下の通りです。

• 第1回 - 強化学習の全体像と問題設定
• 第2回 - 環境側の定式化（マルコフ決定過程）
• 第3回 - エージェント側の概念とプランニングアルゴリズム（価値反復法）
• 第4回 - モデルフリー学習とモンテカルロ法
• 第5回 - 時間差分学習とTD誤差
• 第6回（本記事）- 多段階TD学習とEligibility Trace

n-step TD学習：TD(0)とモンテカルロ法の架け橋

TD(0)とモンテカルロ法の復習

前回学んだTD(0)とモンテカルロ法の更新式を比較してみましょう。

TD(0)の更新式

$$V(s_t) \leftarrow V(s_t) + \alpha [r_t + \gamma V(s_{t+1}) - V(s_t)]$$

モンテカルロ法の更新式

$$V(s_t) \leftarrow V(s_t) + \alpha [G_t - V(s_t)]$$

ここで、$G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + ... + \gamma^{T-t-1} r_{T-1}$は実際の累積報酬です。

これらの手法の特徴を比較すると、重要な違いが見えてきます。

TD(0)は1ステップの実報酬と推定値を組み合わせて使用します。この方法は高バイアス・低分散という特性を持ち、各ステップで即座に学習できるという大きな利点があります。

一方、モンテカルロ法はエピソード全体の実報酬を使用するため、バイアスはありませんが分散が高くなります。また、エピソード終了まで待つ必要があるため、学習の即時性は失われます。

n-step TD学習の導入

n-step TD学習は、これらの中間的なアプローチです。nステップ先までの実際の報酬を使い、それ以降は推定値を使用します。

n-step リターンの定義

n-stepリターン$G_t^{(n)}$は以下のように定義されます。

n-step リターンの定義

$$G_t^{(n)} = r_t + \gamma r_{t+1} + ... + \gamma^{n-1} r_{t+n-1} + \gamma^n V(s_{t+n})$$

特別なケースとして以下があります。

• $n = 1$のとき：$G_t^{(1)} = r_t + \gamma V(s_{t+1})$（TD(0)）
• $n = \infty$のとき：$G_t^{(\infty)} = G_t$（モンテカルロ法）

n-step TD学習の更新式

n-step TD学習の更新式は以下のようになります。

$$V(s_t) \leftarrow V(s_t) + \alpha [G_t^{(n)} - V(s_t)]$$

n-step TD学習の直感的理解

信用割り当ての範囲

例として、ロボットが迷路を探索する場面を考えてみましょう。

1-step TD（TD(0)）の場合

現在位置 → 1歩先
   A    →    B
  (推定)    (実際+推定)

直後の結果のみから学習します。

3-step TDの場合

現在位置 → 1歩先 → 2歩先 → 3歩先
   A    →   B   →   C   →   D
  (推定)   (実際)  (実際)  (実際+推定)

3歩先までの実際の経験を活用します。

モンテカルロ法の場合

現在位置 → ... → ゴール
   A    → ... →   G
  (推定)  (全て実際)

ゴールまでの全経験を使用します。

バイアス・分散トレードオフ

nの値によって、以下のトレードオフが生じます。

• 小さいn：低分散だがバイアスあり（推定値への依存大）
• 大きいn：高分散だがバイアス小（実際の報酬を多く使用）

n-step TD学習の実装上の課題

n-step TD学習は理論的には優れた手法ですが、実装する際にいくつかの重要な課題に直面します。

まず、メモリ使用量の問題があります。nステップ分の経験（状態、行動、報酬）を保持する必要があるため、nが大きくなるほどメモリ消費が増大します。

また、更新の遅延も深刻な問題です。価値関数を更新するためにはnステップ待つ必要があり、エピソードがnステップより短い場合はエピソード終了まで待たなければなりません。これは、TD学習の「即座に学習する」という利点を部分的に失うことを意味します。

さらに根本的な問題として、最適なnの値をどう選ぶかという課題があります。小さいnでは近視眼的な学習になってしまい、大きいnではモンテカルロ法と同じ問題（高分散、遅延学習）に近づいてしまいます。

これらの課題を解決するため、「すべてのnを同時に使う」という画期的なアイデアが生まれました。これがTD(λ)です。

TD(λ)：時間差分学習の一般化

TD誤差：学習の基本ユニット

TD(λ)を理解するためには、まずTD誤差（Temporal Difference Error） の概念を明確にする必要があります。TD誤差は、現在の予測と実際の経験の間のギャップを数値化したもので、強化学習における学習信号の核心です。

TD誤差の数学的定義

時刻$t$におけるTD誤差$\delta_t$は以下のように定義されます。

$$\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$$

ここで、$r_t$は時刻$t$で得られた実際の報酬、$\gamma$は割引率、$V(s_t)$は状態$s_t$の価値推定です。

TD誤差の意味と重要性

TD誤差は、「今回の経験が、事前の予想よりもどの程度良かったか（悪かったか）」を表します。正のTD誤差は予想よりも良い結果を、負のTD誤差は予想よりも悪い結果を意味します。

このTD誤差を使って、従来のTD(0)では以下のように価値関数を更新します。

$$V(s_t) \leftarrow V(s_t) + \alpha \delta_t$$

しかし、この方法では現在の状態$s_t$のみが更新され、過去に訪問した状態は学習の恩恵を受けられません。

TD(λ)の基本アイデア：過去への信用割り当て

TD(λ)は、現在のTD誤差$\delta_t$を現在の状態だけでなく、過去に訪問したすべての状態に配分する手法です。この配分の重み付けを制御するパラメータが$\lambda \in [0,1]$です。

λパラメータの意味：時間的減衰の制御

λパラメータは、TD誤差$\delta_t$を過去の状態に配分する際の時間的減衰率を制御します。

• $\lambda = 0$：現在の状態のみが更新される（TD(0)と同じ）
• $\lambda = 1$：過去のすべての状態が同等に扱われる（モンテカルロ法に近い）
• $0 < \lambda < 1$：過去の状態ほど影響が減衰する

λ-リターン：理論的背景（簡潔版）

TD(λ)の理論的根拠であるλ-リターンは以下のように定義されます。

$$G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$$

この式は、すべてのn-stepリターン$G_t^{(n)}$を指数的に減衰する重み$(1-\lambda)\lambda^{n-1}$で平均化したものです。このλ-リターンの概念は理論的に重要ですが、実際の実装では次節で説明するEligibility Traceというメカニズムを使用します。

前向き視点と後向き視点

TD(λ)の理解と実装には、2つの異なるが数学的に等価な視点があります。これらの視点の違いを理解することが、TD(λ)の本質を掴む鍵となります。

なぜ2つの視点が必要なのか

λ-リターンの定義を思い出してください。

$$G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)}$$

この式を見ると、$G_t^{\lambda}$を計算するには、理論上は無限の未来まで（実際にはエピソード終了まで）の情報が必要です。これでは、TD(0)の「即座に学習できる」という利点が失われてしまいます。

この根本的な問題をどう解決すべきでしょうか。

TD(λ)を理解し実装するために、2つの異なる視点を考える必要があります。1つは定義に忠実な「前向き視点」、もう1つは実装可能な「後向き視点」です。

前向き視点（Forward View）：問題の明確化

前向き視点は、TD(λ)の定義に忠実なアプローチです。この視点では、現在の状態から未来を見て、各n-stepリターンを計算し、それらをλで重み付けして統合します。

具体的には、1ステップ先のリターン$G_t^{(1)}$には重み$(1-λ)$を、2ステップ先のリターン$G_t^{(2)}$には重み$(1-λ)λ$を、というように指数的に減衰する重みを与えて平均を取ります。

現在 → 1歩先 → 2歩先 → ... → エピソード終了
 ↓      ↓       ↓              ↓
G(1)   G(2)    G(3)    ...    G(T)
 ↓      ↓       ↓              ↓
重み:(1-λ) (1-λ)λ (1-λ)λ²  ... 

この方法は理論的には美しく、λ-リターンの定義そのものです。しかし、実装する際に深刻な問題が明らかになります。

すべてのn-stepリターンを計算するためには、エピソード終了まで待つ必要があります。これは、各リターンが未来の情報を必要とするためです。結果として、オンライン学習ができなくなり、エピソード全体の軌跡をメモリに保存する必要も生じます。

前向き視点は、TD(λ)の「何を学習したいか」を明確に示しますが、「どうやって効率的に学習するか」という実装の問題を解決していません。TD学習の最大の利点である「即座に学習できる」という特性が完全に失われてしまうのです。

それでは、この実装上の問題をどう解決すればよいでしょうか。

後向き視点（Backward View）におけるEligibility Traceによる解決

前向き視点の実装上の課題を解決するために、全く異なる数学的アプローチを導入します。未来の情報を集めて現在を更新する代わりに、現在の情報を過去に配分するという発想の転換です。

数学的動機としてのλ-リターンをTD誤差の線形結合で表現

前向き視点では、λ-リターンの定義により、時刻$t$での状態$s_t$の価値更新は以下のように表されます。

$$\Delta V_t(s_t) = \alpha [G_t^{\lambda} - V_t(s_t)]$$

しかし、この形では未来の情報が必要です。重要な洞察は、$G_t^{\lambda} - V_t(s_t)$をTD誤差の線形結合として表現できることです。

以下の数学的変形を順を追って確認しましょう。

ステップ 1: λ-リターンの定義から開始。

$$G_t^{\lambda} - V_t(s_t) = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)} - V_t(s_t)$$

ステップ 2: 各n-stepリターンを展開。

$$= (1-\lambda) \left[ G_t^{(1)} + \lambda G_t^{(2)} + \lambda^2 G_t^{(3)} + \cdots \right] - V_t(s_t)$$

ステップ 3: n-stepリターンの定義を代入。

$$= (1-\lambda) \left[ (r_t + \gamma V_t(s_{t+1})) + \lambda(r_t + \gamma r_{t+1} + \gamma^2 V_t(s_{t+2})) + \lambda^2(r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \gamma^3 V_t(s_{t+3})) + \cdots \right] - V_t(s_t)$$

ステップ 4: 項を再配置して整理。

$$= r_t + (\lambda\gamma)r_{t+1} + (\lambda\gamma)^2 r_{t+2} + \cdots + (1-\lambda)\gamma\left[ V_t(s_{t+1}) + (\lambda\gamma)V_t(s_{t+2}) + (\lambda\gamma)^2 V_t(s_{t+3}) + \cdots \right] - V_t(s_t)$$

ステップ 5: TD誤差の形に変形（重要な変形）。

$$= \underbrace{(r_t + \gamma V_t(s_{t+1}) - V_t(s_t))}_{\delta_t} + \underbrace{(\lambda\gamma)(r_{t+1} + \gamma V_t(s_{t+2}) - V_t(s_{t+1}))}_{(\lambda\gamma)\delta_{t+1}} + \underbrace{(\lambda\gamma)^2(r_{t+2} + \gamma V_t(s_{t+3}) - V_t(s_{t+2}))}_{(\lambda\gamma)^2\delta_{t+2}} + \cdots$$

結果として、以下の重要な式が得られます。

$$G_t^{\lambda} - V_t(s_t) = \sum_{k=0}^{\infty} (\lambda\gamma)^k \delta_{t+k}$$

この重要な結果は、λ-リターンと現在の価値推定の差が、未来のすべてのTD誤差の減衰加重和で表現できることを示しています。

しかし、この形では依然として未来の情報$\delta_{t+1}, \delta_{t+2}, \ldots$が必要です。

後向き視点の数学的定式化における具体例による導出

後向き視点の本質を理解するために、具体的な系列を使って価値関数の更新を追跡してみましょう。

具体的な系列として以下を考えます。

$$h = (s_0, a_0, r_0, s_1, a_1, r_1, s_2, a_2, r_2, s_3, a_3, r_3, \ldots)$$

特に重要なケースとして、$s_0 = s_2$（状態$s_0$が時刻2で再訪問される）の場合を考えます。

時刻0から順に価値関数の更新を追跡します。

時刻1での更新について説明します。
現在状態$s_0$が更新され、

$$V_1(s_0) = V_0(s_0) + \alpha \delta_0$$

となります。
ここで、$\delta_0 = r_0 + \gamma V_0(s_1) - V_0(s_0)$です。

時刻2での更新では、TD(λ)の本質が現れます。
現在状態$s_1$が更新され、

$$V_2(s_1) = V_1(s_1) + \alpha \delta_1$$

となります。
重要なのは過去の状態$s_0$への配分で、

$$V_2(s_0) = V_1(s_0) + \alpha (\lambda\gamma) \delta_1$$

となります。
ここで、$\delta_1 = r_1 + \gamma V_1(s_2) - V_1(s_1)$です。

時刻3での更新では、$s_2 = s_0$なので状態$s_0$が再訪問されます。

時刻3でのTD誤差$\delta_2 = r_2 + \gamma V_2(s_3) - V_2(s_0)$が、時系列順に各状態に配分されます。

時刻2（現在）の状態$s_0$への配分として

$$V_3(s_0) = V_2(s_0) + \alpha \delta_2$$

があります。
時刻1の状態$s_1$への配分として

$$V_3(s_1) = V_2(s_1) + \alpha (\lambda\gamma) \delta_2$$

があります。
時刻0の状態$s_0$への配分として

$$V_3(s_0) \leftarrow V_3(s_0) + \alpha (\lambda\gamma)^2 \delta_2$$

があります。

時刻2と時刻0の寄与を統合すると、状態$s_0$は2回訪問されているため、上記の第1項と第3項をまとめて以下のようになります。

$$V_3(s_0) = V_2(s_0) + \alpha \delta_2 [1 + (\lambda\gamma)^2]$$

時刻4での更新では、TD誤差$\delta_3$が配分されます。
現在状態$s_3$の更新として

$$V_4(s_3) = V_3(s_3) + \alpha \delta_3$$

があります。
過去の状態$s_0$への配分（最新訪問から）として

$$V_4(s_0) = V_3(s_0) + \alpha (\lambda\gamma) \delta_3$$

があります。
過去の状態$s_1$への配分として

$$V_4(s_1) = V_3(s_1) + \alpha (\lambda\gamma)^2 \delta_3$$

があります。
さらに前の状態$s_0$への配分（初回訪問から）として

$$V_4(s_0) \leftarrow V_4(s_0) + \alpha (\lambda\gamma)^3 \delta_3$$

があります。
ここで、$\delta_3 = r_3 + \gamma V_3(s_4) - V_3(s_3)$です。

状態$s_0$の結果的な更新として、上記の2つの更新を組み合わせると以下のようになります。

$$V_4(s_0) = V_3(s_0) + \alpha \delta_3 [(\lambda\gamma) + (\lambda\gamma)^3]$$

重要な観察として、以下の3つのポイントが挙げられます。
まず、各TD誤差$\delta_t$はその時刻の価値関数$V_t$を使って計算されることです（前向き視点との違い）。
次に、TD誤差は現在の状態だけでなく過去に訪問したすべての状態に配分されることです。
最後に、配分の重みは時間経過とともに$(\lambda\gamma)^k$で減衰することです。

TD誤差の配分パターンの一般化について説明します。

上記の例から、TD(λ)では各時刻のTD誤差が以下のように配分されることがわかります。

時刻$t$でのTD誤差$\delta_t$は、現在状態$s_t$に全額（係数1）配分され、1ステップ前の状態$s_{t-1}$に$(\lambda\gamma)$、2ステップ前の状態$s_{t-2}$に$(\lambda\gamma)^2$、一般に$k$ステップ前の状態に$(\lambda\gamma)^k$が配分されます。

状態の再訪問の場合について考えてみましょう。同じ状態が複数回訪問された場合、各訪問からの寄与が累積されます。例えば、状態$s_0$が時刻0と時刻2で訪問された場合、時刻4の$\delta_3$に対する寄与は、時刻2の訪問から$(\lambda\gamma)^1$、時刻0の訪問から$(\lambda\gamma)^3$となり、総合すると$(\lambda\gamma) + (\lambda\gamma)^3$になります。

更新則の導入

この配分パターンを効率的に実装するため、各状態$s$に対して配分係数$e_t(s)$を導入します。この値は、時刻$t$でのTD誤差$\delta_t$を状態$s$にどの程度配分するかを表します。

配分係数の更新則の導出について説明します。

上記の配分パターンから、配分係数$e_t(s)$は以下の性質を満たす必要があります。

状態訪問時には、状態$s$を訪問すると、その状態の係数に1が加算されます。また時間減衰として、毎ステップ、すべての状態の係数が$\gamma\lambda$で減衰します。

これにより、以下の更新則が導出されます。

$$e_{t+1}(s) = \begin{cases} \gamma \lambda e_t(s) + 1 & \text{if } s = s_{t+1} \\ \gamma \lambda e_t(s) & \text{otherwise} \end{cases}$$

初期値：$e_0(s) = 0$ for all $s$

更新則の妥当性確認として、状態$s_0$が時刻0, 2で訪問された場合を考えます。

時刻0では$e_0(s_0) = 1$（訪問時）となります。
時刻1では$e_1(s_0) = \gamma\lambda$（減衰）となります。
時刻2では$e_2(s_0) = (\gamma\lambda)^2 + 1$（減衰 + 再訪問）となります。
時刻3では$e_3(s_0) = (\gamma\lambda)^3 + \gamma\lambda$（減衰）となります。

時刻4の$\delta_3$に対する配分係数は$(\lambda\gamma) + (\lambda\gamma)^3$となり、手動計算と完全に一致します。

適格度トレース（Eligibility Trace）の定義

配分係数$e_t(s)$を適格度トレース（Eligibility Trace） と定義する。これは時刻$t$において状態$s$が現在のTD誤差$\delta_t$を受け取る「適格度」を数値的に表す。

更新則：

$$e_{t+1}(s) = \begin{cases} \gamma \lambda e_t(s) + 1 & \text{if } s = s_{t+1} \\ \gamma \lambda e_t(s) & \text{otherwise} \end{cases}$$

初期値：$e_0(s) = 0$ for all $s \in S$

Eligibility Traceの本質：履歴管理から状態ベクトル管理への転換

前向き視点を素直に実装すると、各状態の訪問履歴（いつ訪問されたか）を記録し続ける必要があります。しかし、これは明らかに面倒で非効率的です。

Eligibility Traceの核心アイデア：履歴を覚える代わりに、状態空間の大きさ分の次元を持つベクトル $\mathbf{e}_t = [e_t(s_1), e_t(s_2), \ldots, e_t(s_{|S|})]$ を管理することで、すべての状態の現在の「適格度」を一元的に追跡します。

各状態$s$について：

• $e_t(s) = 0$：その状態は最近訪問されておらず、TD誤差を受け取る資格がない
• $e_t(s) > 0$：その状態は最近訪問されており、値が大きいほど多くのTD誤差を受け取る資格がある

この方法により：

1. 履歴不要：「いつ訪問されたか」の記録は一切不要
2. 係数計算不要：$(\lambda\gamma)^{t-t_{visit}}$のような複雑な計算は不要
3. 状態ごとの更新：$V(s) \leftarrow V(s) + \alpha \delta_t e_t(s)$ で一律に処理可能

実装上の注意：動的な状態空間管理

理論的には全状態に対してトレースを保持しますが、実際の実装では：

• 初期状態：空のトレースベクトルから開始
• 新状態の発見：軌跡中に新しい状態が現れたら、その状態のトレース要素を動的に追加
• メモリ効率化：値が十分小さくなったトレースは削除

これにより、状態空間が巨大でも、実際に訪問された状態のみを管理することで実用的な実装が可能になります。

前向き視点と後向き視点の関係における等価性の条件と限界

前向き視点と後向き視点の関係は、実装方法によって大きく異なることに注意が必要です。

オフライン更新での等価性

エピソード終了後に一括で更新を行う場合に限り、両視点は数学的に等価になります。この場合は以下のようになります。

後向き視点での総更新：

$$\Delta V(s) = \alpha \sum_{k=0}^{T} \delta_{t+k} e_{t+k}(s)$$

前向き視点での総更新：

$$\Delta V(s) = \alpha \sum_{k=0}^{T} (\lambda\gamma)^k \delta_{t+k}$$

が一致します（ここで$T$はエピソード長）。

オンライン更新での非等価性

実用的なオンライン学習では両者は等価ではありません。

まず、更新タイミングの違いがあります。後向き視点では各ステップで即座に価値関数を更新しますが、前向き視点では未来の情報が必要です。

次に、価値関数の進化が異なります。後向き視点のTD誤差$\delta_t = r_t + \gamma V_t(s_{t+1}) - V_t(s_t)$は現在の価値関数$V_t$を使用しますが、前向き視点では異なる時点の価値関数を参照することになります。

さらに、エピソード的タスクでの影響も重要です。停止状態があるタスクでは、この違いが特に顕著になります。

実用上の意義

オンライン学習における非等価性にもかかわらず、後向き視点（Eligibility Trace）が広く使用される理由があります。まず即座に学習できる実用性があり、次に収束性の理論的保証が確立されており、さらに多くの実験で良好な性能が確認されています。

理論的な完全一致よりも、実用性と性能が重視されているのが現実です。

TD(λ)アルゴリズムの実装

TD(λ)後向きアルゴリズムの詳細手順

前節で導出したEligibility Traceを用いて、TD(λ)の具体的なアルゴリズムを実装します。各ステップでの処理を詳しく見ていきましょう。

アルゴリズムの流れ

TD(λ)の後向きアルゴリズムは、各時刻$t$で以下の3つのステップを実行します。

ステップ 1: TD誤差の計算

$$\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$$

ステップ 2: 全状態のトレース更新
すべての状態$s$について：

$$e_t(s) = \begin{cases} \gamma \lambda e_{t-1}(s) + 1 & \text{if } s = s_t \\ \gamma \lambda e_{t-1}(s) & \text{otherwise} \end{cases}$$

ステップ 3: 全状態の価値更新

$$V(s) \leftarrow V(s) + \alpha \delta_t e_t(s)\ \ \text{for\ all}\ s$$

実装例：基本的なTD(λ)クラス

class TDLambda:
    def __init__(self, lambda_param, learning_rate, gamma):
        self.lambda_param = lambda_param  # λ ∈ [0,1]
        self.learning_rate = learning_rate  # α > 0
        self.gamma = gamma  # γ ∈ [0,1]
        self.V = {}  # 状態価値関数
        self.eligibility = {}  # Eligibility Trace
    
    def update(self, state, reward, next_state, done):
        # ステップ 1: TD誤差の計算
        next_value = 0 if done else self.V.get(next_state, 0)
        td_error = reward + self.gamma * next_value - self.V.get(state, 0)
        
        # ステップ 2: 現在状態のトレース更新
        current_trace = self.eligibility.get(state, 0)
        self.eligibility[state] = self.gamma * self.lambda_param * current_trace + 1
        
        # ステップ 3 & 4: 全状態の価値更新とトレース減衰
        states_to_remove = []
        for s in list(self.eligibility.keys()):
            # 価値更新
            value_update = self.learning_rate * td_error * self.eligibility[s]
            self.V[s] = self.V.get(s, 0) + value_update
            
            # トレース減衰（現在状態以外）
            if s != state:
                self.eligibility[s] *= self.gamma * self.lambda_param
            
            # 小さなトレースを削除
            if self.eligibility[s] < 1e-5:
                states_to_remove.append(s)
        
        # メモリクリーンアップ
        for s in states_to_remove:
            del self.eligibility[s]

行動価値関数Q(s,a)への拡張

これまでは状態価値関数$V(s)$を扱ってきましたが、実際の強化学習では行動価値関数$Q(s,a)$を学習することが多くあります。TD(λ)を行動価値関数に適用する方法を見ていきましょう。

Q(λ)アルゴリズム

行動価値関数に対するEligibility Traceは、状態-行動ペア$(s,a)$ごとに管理します。

TD誤差の計算は以下のようになります。

$$\delta_t = r_t + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t)$$

Eligibility Traceの更新は次の式で表されます。

$$e_{t+1}(s,a) = \begin{cases} \gamma \lambda e_t(s,a) + 1 & \text{if } (s,a) = (s_{t+1}, a_{t+1}) \\ \gamma \lambda e_t(s,a) & \text{otherwise} \end{cases}$$

行動価値関数の更新は以下のように実行されます。

$$\forall (s,a): Q(s,a) \leftarrow Q(s,a) + \alpha \delta_t e_t(s,a)$$

SARSA(λ)の実装例

class SARSALambda:
    def __init__(self, lambda_param, learning_rate, gamma):
        self.lambda_param = lambda_param
        self.learning_rate = learning_rate
        self.gamma = gamma
        self.Q = {}  # 行動価値関数 Q(s,a)
        self.eligibility = {}  # Eligibility Trace e(s,a)
    
    def get_q_value(self, state, action):
        return self.Q.get((state, action), 0)
    
    def update(self, state, action, reward, next_state, next_action, done):
        # TD誤差の計算
        next_q = 0 if done else self.get_q_value(next_state, next_action)
        td_error = reward + self.gamma * next_q - self.get_q_value(state, action)
        
        # 現在の状態-行動ペアのトレース更新
        current_pair = (state, action)
        current_trace = self.eligibility.get(current_pair, 0)
        self.eligibility[current_pair] = self.gamma * self.lambda_param * current_trace + 1
        
        # 全ペアの更新と減衰
        pairs_to_remove = []
        for pair in list(self.eligibility.keys()):
            # Q値更新
            update_amount = self.learning_rate * td_error * self.eligibility[pair]
            self.Q[pair] = self.Q.get(pair, 0) + update_amount
            
            # トレース減衰
            if pair != current_pair:
                self.eligibility[pair] *= self.gamma * self.lambda_param
            
            # 小さなトレースを削除
            if self.eligibility[pair] < 1e-5:
                pairs_to_remove.append(pair)
        
        for pair in pairs_to_remove:
            del self.eligibility[pair]

状態価値関数と行動価値関数の使い分け

状態価値関数V(s)は、環境のモデルが既知の場合に適用され、主に方策評価に使用されます。メモリ使用量は状態空間のサイズに比例します。

行動価値関数Q(s,a)は、モデルフリー学習で広く使用され、方策改善を直接実行できます。メモリ使用量は状態×行動空間のサイズに比例します。

実用的な強化学習では、Q(λ)やSARSA(λ)のような行動価値関数ベースの手法がより頻繁に使用されます。

Replacing Trace vs Accumulating Trace

Eligibility Traceには2つの主要なバリエーションがあります。

Accumulating Trace（累積トレース）

これまで説明してきた標準的な形式です。訪問のたびに1を加算し、同じ状態を繰り返し訪問するとトレースが1を超えることがあります。

Replacing Trace（置換トレース）

訪問時にトレースを1にリセットします。

$$e_t(s) = \begin{cases} 1 & \text{if } s = s_t \\ \gamma \lambda e_{t-1}(s) & \text{otherwise} \end{cases}$$

使い分けの指針として、理論的正確性を重視する場合はAccumulating Traceが前向き視点と数学的に等価であることから適しています。一方、実用性能を重視する場合は、Replacing Traceがより安定した学習を実現することが多いため推奨されます。

多くの実用アプリケーションでは、同じ状態の繰り返し訪問によるノイズを抑制できるReplacing Traceが採用されています。

パラメータ選択と実用的考慮事項

λパラメータの選択指針

λパラメータの選択は環境の特性に大きく依存します。

環境別の選択指針

探索的な環境では、λを0.9から0.95という高い値に設定することが推奨されます。この設定は長期的な結果を重視し、探索による分散を許容できる場合に適しています。エージェントが環境を積極的に探索している段階では、遠い未来の情報も重要になるためです。

確定的な環境、つまり同じ行動が常に同じ結果をもたらす環境では、λを0.5から0.8の中間的な値に設定します。これによりバランスの取れた学習が可能になり、安定した収束が期待できます。

ノイズの多い環境では、λを0.0から0.5という低い値に設定することが適切です。これは分散を抑制し、局所的な情報を重視することで、ノイズによる悪影響を最小限に抑えるためです。

学習率の調整

TD(λ)では、λが大きいほど更新の影響が大きくなるため、学習率の調整が重要です。

# λに応じた学習率の調整例
adjusted_alpha = base_alpha * (1 - lambda_param + 0.1)

実装上の最適化

メモリ効率化

Eligibility Traceは指数的に減衰するため、小さな値は無視できます。

# 閾値以下のトレースを削除
TRACE_THRESHOLD = 0.01
if eligibility[state] < TRACE_THRESHOLD:
    del eligibility[state]

計算効率化

訪問していない状態のトレースは常に減衰するだけなので、明示的に保持する必要はありません。

# アクティブな状態のみを追跡
active_states = list(eligibility.keys())
for s in active_states:
    # 更新処理

まとめ

本記事で学んだ重要な概念

TD(λ)の理論的基盤について、λ-リターンによるすべてのn-stepリターンの統合、TD誤差の線形結合としての数学的表現、そして前向き視点と後向き視点の関係を学びました。

Eligibility Traceの本質として、履歴管理から状態ベクトル管理への転換、TD誤差の効率的な配分メカニズム、そして最近性と頻度を考慮した信用割り当ての仕組みを理解しました。

実装上の重要ポイントでは、Accumulating TraceとReplacing Traceの使い分け、行動価値関数Q(s,a)への拡張、そしてパラメータ選択の環境依存性について学習しました。

TD(λ)の意義と展望

TD(λ)は強化学習において重要な貢献をしています。

まず理論的完成度の観点から、TD学習の自然な一般化として数学的に美しい枠組みを提供しています。次に実用性の面では、多くの実問題で優れた性能を示し、深層強化学習の基礎技術となっています。さらに拡張性においても、関数近似や深層学習への拡張が容易で、現代的な手法の基盤を形成しています。

次回の記事では、価値関数を関数近似する手法について学び、より大規模で複雑な問題への強化学習の適用を探ります。