n-step TD法

1-step TD が軽い代わりに遠い報酬を取り込みにくいなら、数歩先までだけ実報酬を見て、残りを bootstrap で埋めればよい。その発想をそのまま形にしたのが n-step TD です。

参考動画（外部）

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

n-step TD法の解説

1-step と Monte Carlo の間に、いくらでも中間を作れる

n=1 なら普通の TD、n=T-t なら終端まで足し切る Monte Carlo に近づきます。n-step TD は、その中間のどこで折り合いを取るかを選ぶ方法です。

短い n は bootstrap 依存が強く、長い n は実報酬依存が強くなります。つまり、bias と variance のバランスを、何歩先まで見るかで直接調整していると読むのが自然です。

この notebook の見どころ

g1 と g3 の差、bootstrap 項 V_boot の役割、n=T-t で Monte Carlo return に近づく様子を順に見ます。

ここでの主役はアルゴリズム名ではなく target の作り方です。後で $TD(\lambda)$ を読むと、この n-step return をたくさん混ぜる発想につながります。

読み方の軸

n を増やすとよい、ではありません。どのくらい先の実報酬を見たいか、どのくらい bootstrap に頼りたいかを設計している、と読むべきです。

import math

gamma = 0.9
rewards = [0.2, 0.0, 1.0, -0.1, 0.5]  # R_{t+1}, R_{t+2}, ...
V_boot = 0.7  # V(S_{t+n})


def n_step_return(rews, n, gamma, v_boot):
    n = min(n, len(rews))
    g = 0.0
    for k in range(n):
        g += (gamma ** k) * rews[k]
    if n < len(rews):
        g += (gamma ** n) * v_boot
    return g

for n in [1, 2, 3, 5]:
    print(f'n={n}: G_t^(n)=', round(n_step_return(rewards, n, gamma, V_boot), 6))

Q更新への適用

Q(s_t,a_t) \leftarrow Q(s_t,a_t)+\alpha\{G_t^{(n)}-Q(s_t,a_t)\}

n=1 が通常の TD、n=T-t がモンテカルロ更新に対応します。

alpha = 0.3
q_old = 0.4
g1 = n_step_return(rewards, 1, gamma, V_boot)
g3 = n_step_return(rewards, 3, gamma, V_boot)

q_after_1 = q_old + alpha * (g1 - q_old)
q_after_3 = q_old + alpha * (g3 - q_old)

print('old Q =', q_old)
print('after 1-step update =', round(q_after_1, 6))
print('after 3-step update =', round(q_after_3, 6))

n が大きい更新は遠い報酬を早く反映できます。その代わり、ノイズや終端の不確実さも一緒に背負うので、環境によって有利不利が変わります。