後方観測TD(λ)とEligibility Trace

Eligibility Trace は、いま生じた TD 誤差を「どの過去状態にどれだけ返すか」を数値で管理する仕組みです。TD(λ)\lambda) の後ろ向き実装を理解するうえで、ここがいちばん実装的な要所になります。

参考動画（外部）

授業本編ではなく、別の説明で見直したいときの参考材料です。

trace は「過去の責任の残り具合」を持っている

TD 誤差が出た瞬間、それを現在だけに当てるのではなく、少し前に通った状態にも配りたいことがあります。trace はそのための記憶で、最近訪れた状態ほど大きく、時間が経つと減衰していきます。

accumulating と replacing の差は、同じ状態を再訪したときに trace を積み増すか、1 に戻すかです。更新を強く通したいか、暴れすぎを抑えたいかで設計が分かれます。

この notebook の見どころ

E が時間とともにどう残るか、再訪の多い状態で accumulating / replacing の差がどう広がるか、同じ TD 誤差でも更新先が変わる様子を見ます。

trace は抽象論ではなく、実装上の credit assignment そのものです。どの過去状態がまだ責任を持っているかを陽に持つことで、長期依存をオンラインで扱えるようになります。

読み方の軸

ここで見るべきは V の最終値だけではなく、E の形です。誤差がどこへ流れているかが見えれば、trace の設計差も自然に読めます。

gamma = 0.9
lam = 0.8
alpha = 0.1

states = ['s0', 's1', 's0', 's2', 's0']
rewards = [0.1, 0.0, 0.8, -0.2, 0.0]

V_acc = {'s0': 0.0, 's1': 0.0, 's2': 0.0}
V_rep = {'s0': 0.0, 's1': 0.0, 's2': 0.0}
E_acc = {'s0': 0.0, 's1': 0.0, 's2': 0.0}
E_rep = {'s0': 0.0, 's1': 0.0, 's2': 0.0}

for t in range(len(states) - 1):
    s = states[t]
    s_next = states[t + 1]
    r = rewards[t]

    # accumulating trace
    delta_acc = r + gamma * V_acc[s_next] - V_acc[s]
    for k in E_acc:
        E_acc[k] *= gamma * lam
    E_acc[s] += 1.0
    for k in V_acc:
        V_acc[k] += alpha * delta_acc * E_acc[k]

    # replacing trace
    delta_rep = r + gamma * V_rep[s_next] - V_rep[s]
    for k in E_rep:
        E_rep[k] *= gamma * lam
    E_rep[s] = 1.0
    for k in V_rep:
        V_rep[k] += alpha * delta_rep * E_rep[k]

print('Accumulating V =', {k: round(v, 6) for k, v in V_acc.items()})
print('Replacing V    =', {k: round(v, 6) for k, v in V_rep.items()})
print('Accumulating E =', {k: round(v, 6) for k, v in E_acc.items()})
print('Replacing E    =', {k: round(v, 6) for k, v in E_rep.items()})

状態再訪が多い問題では accumulating trace が更新を強めやすく、発散気味な問題では replacing trace が安定しやすい傾向があります。どちらがよいかは、責任をどれだけ強く残したいかで決まります。