適格度トレース - Shinichi0713/RL-study GitHub Wiki
概要
適合度トレース（エリジビリティトレース、eligibility trace）は、強化学習のTD(λ)アルゴリズムで使われる仕組みです。このコードでは、各状態-行動ペアごとに「どれだけ最近そのペアが訪れたか」を記録し、TD誤差（学習信号）をどの程度反映させるかを調整します。
動作の概要 行動を選択・実行するたびに、その状態-行動ペアの適合度トレース値を1だけ増やします（self.set_eligibility_trace(state, action, ... + 1)）。 すべての状態-行動ペアについて、価値関数の更新時に「TD誤差 × 適合度トレース値」を掛けて重み付けします。 各エピソードのステップごとに、適合度トレース値はγλ倍されて減衰していきます（
self.get_eligibility_trace(*sa) * self.gamma * self.lambd
）。 エピソードが終了したら、すべての適合度トレースをリセットします。 まとめ 適合度トレースは「過去に訪れた状態-行動ペア」にもTD誤差を分配し、より効率的に学習できるようにするための仕組みです。最近訪れたペアほど大きく、古いものほど小さく重み付けされます。
前方観測的な見方 / 後方観測的な見方
適格度トレースは理論的には前方観測的な見方（forward view）と呼ばれ、技術的には後方観測的な見方（backward view）と呼ばれます。
- 前方観測的な見方: 適格度トレースを用いた手法で何が計算されるのかを理解するのに有用
- 後方観測的な見方: アルゴリズムそれ自体の直感を発展させるのに適している
前方観測的な見方
TD(λ)アルゴリズムはnステップ・バックアップを平均化する方法の1つです。 この平均にはnステップ分のバックアップ全てが含まれており、その各々はλ^{n-1}(0≦λ≦1)に比例して重み付けされます。 結果として得られるバックアップはλ収益(λ-return)と呼ばれる収益に対するものとなり次のように定義されます。
Rλt=(1–λ)∑n=1∞λn−1R(n)t
λ収益アルゴリズム(λ-return algorithm)は、λ収益を用いてバックアップを実行するアルゴリズムです。各時間ステップtでそのときに発生する状態価値に対する増分を次のように計算します。
参考
適格度トレースとは、過去起きたことを記憶しておくためのキャッシュ。
状態の価値を更新するために保持しておきたい。
状態を入力する関数と考えることが出来る。
活用することでTD誤差を各ステップごとに更新することが出来る。
アルゴリズム