পাঠ ১১ · ৩২-এর মধ্যে · মডিউল ২

Home / AI Courses / রিইনফোর্সমেন্ট লার্নিং / TD Learning

Temporal Difference (TD) learning

TD learning — bootstrapping from one-step experience

৮ মিনিট পড়া উচ্চ · Advanced Python কোডসহ

এই পাঠে যা শিখবেন

TD(0) — সরলতম TD method
TD error δ — RL-এর "dopamine signal"
n-step TD — MC ও TD-এর spectrum
TD(λ) — eligibility traces

১ · The big idea — bootstrap

MC: $V(s) = \mathbb{E}[G_t]$ — full episode return-এর গড়।
DP: $V(s) = \mathbb{E}[r + \gamma V(s')]$ — model দিয়ে next state value।
TD: $V(s) = $ sample $r + \gamma V(s')$ — sample, কিন্তু বর্তমান $V$ estimate ব্যবহার।

TD(0) update rule

$$V(s_t) \leftarrow V(s_t) + \alpha [\underbrace{r_{t+1} + \gamma V(s_{t+1})}_{\text{TD target}} - V(s_t)]$$

$\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)$ — TD error।

২ · কেন TD revolutionary

Online: প্রতি step-এ update — episode-শেষ চাই না।
Continuing tasks: infinite horizon-এও কাজ করে।
Variance কম: single $r + \gamma V(s')$ — full $G$ না।
Bias আছে: $V(s')$ estimate (boots-strap)।

৩ · TD error — biological connection

Schultz, Dayan, Montague (১৯৯৭) — dopaminergic neurons-এর firing pattern TD error-এর সাথে match। মস্তিষ্ক natural TD-প্রকৃতির। RL ↔ neuroscience-এর সবচেয়ে strong link।

আপনি ছবিতে দেখলেন বন্ধু এসেছে — চমৎকার। এই "চমৎকার" — expected value হঠাৎ বেড়েছে। এটাই positive TD error। মস্তিষ্ক dopamine release করে। RL agent same — δ > 0 হলে অভ্যাস strengthen।

৪ · TD(0) Python implementation

Python · TD(0)

import numpy as np

# 5-state random walk, terminals at 0 (-1) and 4 (+1)
n = 5
gamma = 1.0
alpha = 0.1

def episode():
    s = 2
    traj = []
    while s not in [0, 4]:
        a = np.random.choice([-1, 1])
        s_next = s + a
        if s_next == 4: r = 1
        elif s_next == 0: r = -1
        else: r = 0
        traj.append((s, r, s_next))
        s = s_next
    return traj

V = np.zeros(n)
np.random.seed(0)

for ep in range(500):
    traj = episode()
    for (s, r, s_next) in traj:
        terminal = s_next in [0, 4]
        V_next = 0 if terminal else V[s_next]
        td_error = r + gamma * V_next - V[s]
        V[s] += alpha * td_error

print("TD(0) estimate:")
for s in range(n):
    print(f"  V({s}) = {V[s]:.3f}")
# Analytical: V(s) = (s - 2)/2 for s in [1,2,3]
# V(1)=-0.5, V(2)=0, V(3)=0.5

TD(0) ৫০০ episode-এ analytical-এর কাছাকাছি। MC একই accuracy পেতে আরও episode লাগে — variance বেশি।

৫ · TD vs MC — bias-variance

MC: unbiased, high variance। full $G$ — long horizon noise।
TD: biased (bootstrapping), low variance। single $r + \gamma V$।
Practice: TD usually faster convergence on Markov problems। MC robust to non-Markov।

৬ · n-step TD

Spectrum between TD(0) and MC:

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

$n=1$ → TD(0)। $n=\infty$ → MC।

Trade-off:

Larger $n$ — less bias (more sample, less bootstrap), more variance।
Smaller $n$ — more bias, less variance।
Optimal $n$ — task-dependent। Atari-এ $n=3$-$5$ common।

৭ · TD(λ) — eligibility traces

Single $n$ বাছার বদলে — সব $n$-step return-এর geometric average:

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

$\lambda=0$ → TD(0)। $\lambda=1$ → MC।

Eligibility trace: efficient online implementation —

$$e_t(s) = \gamma \lambda e_{t-1}(s) + \mathbb{1}[s_t = s]$$

Update: $V(s) \leftarrow V(s) + \alpha \delta_t e_t(s)$ — সব state-এ trace অনুযায়ী।

TD(0), n-step TD, ও MC — backup-এর গভীরতা spectrum। modern RL এই spectrum-এর intermediate point ব্যবহার।

৮ · n-step TD Python

Python · n-step TD

def n_step_td(n_steps=3, n_episodes=500, alpha=0.1):
    V = np.zeros(n)
    for ep in range(n_episodes):
        traj = episode()
        for t in range(len(traj)):
            # n-step return
            G = 0
            for k in range(n_steps):
                if t + k >= len(traj): break
                G += (gamma ** k) * traj[t+k][1]
            # bootstrap from V at end
            if t + n_steps < len(traj):
                G += (gamma ** n_steps) * V[traj[t+n_steps][0]]
            s = traj[t][0]
            V[s] += alpha * (G - V[s])
    return V

for n in [1, 2, 5, 100]:
    V_est = n_step_td(n_steps=n)
    print(f"n={n}: V = {V_est.round(3)}")

Different $n$ — different convergence pattern। $n=1$ (TD(0)) দ্রুত start কিন্তু biased। $n$ বড় → MC-এর কাছাকাছি — slower but unbiased।

৯ · TD-এর প্রভাব — কোথায় ব্যবহার

Q-learning, SARSA — TD-based control।
DQN — TD + neural net।
A2C, A3C — n-step advantage TD-based।
PPO, TRPO — GAE-based, TD-extended।
SAC, TD3 — TD critic update।

প্রায় সব modern RL algorithm — TD-এর কোনো-না-কোনো রূপ।

ভাবনার প্রশ্ন

প্র ০১TD-এর "bootstrap" শব্দটি কী মানে — এবং কেন bias আনে?

Bootstrap = "নিজেকে নিজে টানা"। TD update-এ next state-এর value estimate ব্যবহার — যা agent নিজেই learning। তাই self-referential।

Bias source: $V(s')$ true value না, current estimate। ভুল হলে — সেটা $V(s)$-এ propagate।

কিন্তু কেন কাজ করে:

Convergence guaranteed (tabular case): contraction।
Errors decrease with iteration।
Sample-efficient: full episode wait নেই।

Function approximation-এ সমস্যা: NN-এ bootstrapping-এর "deadly triad" — যেটি DQN-এ target net + replay buffer দিয়ে handle।

প্র ০২TD error-এর neuroscience interpretation কী?

Schultz et al. (1997) — monkey-এর midbrain dopamine neurons-এর recording:

Unexpected reward — burst firing (positive TD error)।
Predicted reward — no extra burst (zero TD error)।
Expected reward absent — dip in firing (negative TD error)।

এই pattern exactly TD error-এর behavior। মস্তিষ্ক naturally TD computer।

Implications:

Addiction — drug induces artificial positive TD error।
Depression — chronic negative TD error → low value estimate।
Parkinson's — dopamine deficit → TD signal disrupted → motor learning হারায়।

Reverse application: RL theory mental health-এ insight দেয়। computational psychiatry — emerging field।

প্র ০৩Random walk-এ TD কেন MC-এর চেয়ে দ্রুত converge?

Sutton-Barto-র classic experiment। Random walk Markov — TD assumption সঠিক।

কেন TD জেতে:

Variance কম: full $G$-র noise এড়ায়।
Markov-এ bias minimal — V estimate true value-র কাছে।
Information propagation: এক episode-এর update পরের episode-এ instantly available।

MC কেন slow:

Long episode-এর full $G$ noisy।
Episode-শেষে only update — within-episode information unused।
Convergence-এ অনেক episode প্রয়োজন।

কখন MC জেতে:

Non-Markov environment — TD bias amplify।
Function approximation + offline — MC simpler।

প্র ০৪Eligibility trace কীভাবে credit assignment করে?

TD(0) — শুধু last visited state credit পায়। Eligibility trace — past states-ও credit পায় (decaying)।

$e_t(s) = \gamma \lambda e_{t-1}(s) + \mathbb{1}[s_t = s]$

Visualization:

State $s$-এ visit হলো — trace 1-এ jump।
Time pass — trace exponentially decay ($\gamma \lambda$ rate)।
Reward এলে — সব trace-এর share পায় credit।

Backward view interpretation: TD error δ আসলে — সব state-এ এটার trace অনুযায়ী allocate হয়।

Forward equivalence: Sutton প্রমাণ করেছেন — backward (eligibility) ও forward (n-step return mixture) computationally equivalent।

Practical: TD(λ) tabular-এ excellent। NN-এর সাথে eligibility trace কঠিন (parameter space-এ trace), তাই modern deep RL-এ rarely. কিন্তু GAE (PPO-এ) — TD(λ)-এর spirit।

অনুশীলন

TD update manual: $V(s)=2, V(s')=4, r=1, \gamma=0.9, \alpha=0.1$। TD error ও new $V(s)$?

$\delta = 1 + 0.9 \cdot 4 - 2 = 2.6$। $V(s) \leftarrow 2 + 0.1 \cdot 2.6 = 2.26$।
n-step return: $r_1=1, r_2=2, r_3=3$, $V(s_3)=5$, $\gamma=0.9$। 3-step return $G^{(3)}$?

$G^{(3)} = 1 + 0.9 \cdot 2 + 0.81 \cdot 3 + 0.729 \cdot 5 = 1 + 1.8 + 2.43 + 3.645 = 8.875$।
TD vs MC code: উপরের code-এ MC version implement করুন; sample efficiency compare।

MC version-এ — episode শেষ পর্যন্ত wait, all (s, G) pair update। TD version per-step। সাধারণত TD ৩-১০× কম episode-এ similar accuracy।