Temporal Difference learning

What is Temporal Difference Learning?

The Fundamental TD Update

Let's derive the core TD(0) update from first principles.

Start with the value function definition: $V^\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$

where $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$ is the return.

Key insight: We can rewrite the return recursively: $G_t = R_{t+1} + \gamma G_{t+1}$

Why this step? We're separating the immediate reward from all future rewards, which lets us substitute our estimate of future value.

Substitute into the value function: $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} \mid S_t = s]$

Why this step? By linearity of expectation: $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} \mid S_t = s] + \gamma \mathbb{E}_\pi[G_{t+1} \mid S_t = s]$

The bootstrapping magic: The second term is just the value of the next state: $V^\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma V^\pi(S_{t+1}) \mid S_t = s]$

This is the Bellman equation for $V^\pi$ .

Formula TD(0) Update Rule

At each step, after observing transition $S_t \xrightarrow{A_t, R_{t+1}} S_{t+1}$ : $V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$ where:

$\alpha \in (0, 1]$ is the learning rate
$\gamma \in [0, 1]$ is the discount factor
$\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the TD error Why this form?
$R_{t+1} + \gamma V(S_{t+1})$ is the TD target: our improved estimate using actual reward + bootstrapped future value
$V(S_t)$ is our old estimate
The difference (TD error) tells us how wrong were
We move our estimate a fraction $\alpha$ toward the target

Deriving the TD Target

The diagram shows why TD works: at each step, we get new information (the actual reward $R_{t+1}$ ) that makes our estimate more accurate than it was before.

The three estimates in play:

Old estimate: $V(S_t)$ — what we thought before taking action
Actual sample: We observe $R_{t+1}$ — real, experienced data
TD target: $R_{t+1} + \gamma V(S_{t+1})$ — combines real reward with our current best guess about the future

Why this is smarter than Monte Carlo:

MC waits until episode end to see $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots$
TD substitutes $V(S_{t+1})$ for the infinite sum $R_{t+2} + \gamma R_{t+3} + \cdots$
This reduces variance because we're estimating less (only one step of randomness)
But introduces bias because $V(S_{t+1})$ is not the true value (yet)

TD(0) Algorithm for Policy Evaluation

Worked example TD(0) Step-by-Step

Goal: Estimate $V^\pi(s)$ for a given policy $\pi$ Algorithm:

Initialize V(s) arbitrarily for all s∈ S (except V(terminal) = 0)
For each episode:
    Initialize S_t
    For each step of episode:
        A_t ← action from π(S_t)
        Take action A_t, observe R_{t+1}, S_{t+1}
        V(S_t) ← V(S_t) + α[R_{t+1} + γV(S_{t+1}) - V(S_t)]
        
        S_t ← S_{t+1}
        If S_t is terminal, break

Why each component:

We initialize arbitrarily because TD will correct any starting values through experience
We update immediately after each transition (online learning)
Terminal states have value 0 by definition (no future rewards)

Worked Examples

Worked example Example 1: Grid World Navigation

Setup: 3×3 grid, start at (0,0), goal at (2,2), reward -1 per step, γ=0.9, α=0.1 Initial values: All $V(s) = 0$ except goal

Episode 1, Step 1:

State: (0,0), Action: Right, Reward: -1, Next State: (0,1)
TD error: $\delta = -1 + 0.9 \times 0 - 0 = -1$
Update: $V(0,0) \leftarrow 0 + 0.1 \times (-1) = -0.1$ Why this step? We just learned that being in (0,0) and going right gives us -1 reward and leads to a state we currently value at 0. Our estimate was too optimistic (we thought 0), so we lower it.

Episode 1, Step 2:

State: (0,1), Action: Right, Reward: -1, Next State: (0,2)
TD error: $\delta = -1 + 0.9 \times 0 - 0 = -1$
Update: $V(0,1) \leftarrow 0 + 0.1 \times (-1) = -0.1$ After many episodes: Values propagate backward from the goal. States closer to goal develop higher (less negative) values. The agent learns the value landscape through bootstrapping.

Worked example Example 2: Why Bootstrapping Helps

Scenario: 100-step path to reward +10, γ=1, α=0.5

Monte Carlo approach:

Must complete all 100 steps to get first update
After Episode 1: $V(s_0) \leftarrow 0 + 0.5 \times (10 - 0) = 5$
All intermediate states still at 0
Need 100 episodes to propagate value to all states

TD approach:

Episode 1, Step 99: $V(s_{99})$ learns about the +10 reward immediately
Episode 2, Step 98: $V(s_{98})$ learns from $V(s_{99})$
Episode 3, Step 97: $V(s_{97})$ learns from $V(s_{98})$
Value propagates backward much faster

Why this is powerful: TD creates a value gradient that propagates through the state space. Each state "teaches" its predecessor, creating a cascade of learning.

Worked example Example 3: Understanding the TD Error

Setup: States A → B → C (terminal, reward +1)

Current estimates: $V(A) = 0.5$ , $V(B) = 0.8$ , $V(C) = 0$
γ = 1, α = 0.1

Transition A → B (reward 0):

TD target: $0 + 1 \times 0.8 = 0.8$
TD error: $\delta = 0.8 - 0.5 = 0.3$ (positive!)
Update: $V(A) \leftarrow 0.5 + 0.1 \times 0.3 = 0.53$

Why positive TD error? We discovered that from A, we reach a state (B) that's more valuable than we expected. This is good news, so we increase $V(A)$ .

Transition B → C (reward +1):

TD target: $1 + 1 \times 0 = 1$
TD error: $\delta = 1 - 0.8 = 0.2$ (positive!)
Update: $V(B) \leftarrow 0.8 + 0.1 \times 0.2 = 0.82$

Why this step? B leads directly to reward, so its value should be close to 1. We're gradually correcting upward.

Common Mistakes and Misconceptions

Common mistake Mistake 3: "Larger α means faster learning, so always use α=1"

Why it feels right: Bigger steps → faster convergence.

Why it's wrong: Large α creates instability. With α=1, you completely replace your old estimate with a noisy sample: $V(S_t) \leftarrow R_{t+1} + \gamma V(S_{t+1})$ This is pure sample-based learning with no smoothing.

Example: Values will wildly oscillate based on random rewards, never converging.

The fix:

Use smaller α (e.g., 0.1) for smooth convergence
Or use decaying learning rate: $\alpha_t = \frac{1}{n(s)}$ where $n(s)$ is visit count
Rule of thumb: α should decrease such that $\sum \alpha_t = \infty$ but $\sum \alpha_t^2 < \infty$

TD vs Monte Carlo vs Dynamic Programming

Property	TD	Monte Carlo	Dynamic Programming
Requires model?	No	No	Yes
Bootstraps?	Yes	No	Yes
Online?	Yes	No	N/A
Complete episodes?	No	Yes	N/A
Bias	Biased	Unbiased	N/A
Variance	Low	High	N/A
Convergence	Guaranteed*	Guaranteed	Guaranteed

*with appropriate learning rate schedule

Recall Feynman Explanation (Explain to a 12-year-old)

Imagine you're walking home from school, and you want to guess how long it will take. You could:

Monte Carlo way: Walk all the way home, check your watch, and then say "Oh, it took 20 minutes." Only update your guess after you're done.
TD way: After each block, update your guess. "I thought it'd take 20 minutes total, but I just walked one block in 2 minutes, and I think the rest will take 17 more minutes. So my new guess is 2 + 17 = 19 minutes."

TD is smarter because:

You learn during the walk, not just at the end
If something unexpected happens (like hitting traffic), you update your guess right away
By the time you're halfway home, you already have a pretty good estimate

The "temporal difference" is the difference between what you thought would happen and what actually happened. Every time reality surprises you (good or bad), you adjust your guess a little bit.

Why the fancy math? $R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is just:

$R_{t+1}$ = what just happened (like walking one block)
$V(S_{t+1})$ = your guess for the rest of the journey
$V(S_t)$ = your old guess for the full journey
The difference tells you if your old guess was too high or too low!

Connection to OtherRL Concepts

Key Takeaways

TD learns from incomplete episodes by bootstrapping from current value estimates
The TD error $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ drives all updates
TD combines strengths: sampling (like MC) + bootstrapping (like DP) = model-free online learning
Bias-variance tradeoff: TD has lower variance than MC but introduces bias from bootstrapping
Faster propagation: Values spread backward through state space more efficiently than MC

#flashcards/ai-ml

What is the fundamental idea behind Temporal Difference learning? :: TD learning updates value estimates immediately after each step by comparing the current prediction with a new prediction based on the actual reward received plus the estimated value of the next state (bootstrapping). It learns from incomplete episodes.

What is the TD(0) update rule?

V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]

, where the bracketed term is the TD error measuring how much our prediction was off.

What is the TD error formula and what does it represent?

\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)

. It represents the difference between our improved estimate (TD target:

R_{t+1} + \gamma V(S_{t+1})

) and our old estimate

V(S_t)

. It tells us how wrong we were.

What is the TD target?

The TD target is

R_{t+1} + \gamma V(S_{t+1})

. It's our improved estimate combining the actual observed reward

R_{t+1}

with our current best guess about future value

\gamma V(S_{t+1})

What is bootstrapping in the context of TD learning?

Bootstrapping means updating an estimate based on other estimates rather than waiting for actual final outcomes. TD uses

V(S_{t+1})

(an estimate) to update

V(S_t)

, rather than waiting for the true return

G_t

What are the three key differences between TD and Monte Carlo?

1) TD updates online (each step) vs MC updates after episode; 2) TD bootstraps from estimates vs MC uses actual returns; 3) TD is biased but lower variance vs MC is unbiased but higher variance.

Why does TD learning have lower variance than Monte Carlo?

TD only depends on one step of randomness (R_{t+1} and S_{t+1}), then uses an estimate. MC depends on the randomness of all remaining steps in the episode. Fewer random variables = lower variance.

Why does TD learning have bias while Monte Carlo does not?

TD uses

V(S_{t+1})

which is an estimate (not the true value) to compute the target. This introduces bias. MC uses the actual return

G_t

, which is an unbiased sample of the true value.

Is TD learning model-free or model-based and why?

Model-free. TD learns from sampled experience (transitions) without needing to know the transition dynamics

P(s'|s,a)

or reward function

R(s,a)

. We observe

(S_t, A_t, R_{t+1}, S_{t+1})

directly from environment interaction.

What properties must the learning rate α satisfy for TD convergence?

For guaranteed convergence:

\sum_{t=1}^{\infty} \alpha_t = \infty

(sufficient learning) and

\sum_{t=1}^{\infty} \alpha_t^2 < \infty

(decreasing step sizes). Example:

\alpha_t = 1/t

\alpha_t = 1/n(s)

where n(s) is state visit count.

How does TD learning propagate value information through state space?

Backward propagation: states near rewards learn first, then their predecessors learn from them, creating a value gradient. Each state "teaches" its predecessor through bootstrapping, allowing faster propagation than MC.

What happens if you set α=1 in TD learning?

With α=1, you get

V(S_t) \leftarrow R_{t+1} + \gamma V(S_{t+1})

, completely replacing the old estimate with a single noisy sample. This causes wild oscillations and prevents convergence—no smoothing over multiple experiences.

What are the advantages of TD over Dynamic Programming?

TD is model-free (doesn't require knowing

P(s'|s,a)

R(s,a)

), learns from actual experience, and naturally handles stochastic environments without neding to compute expectations over all possible transitions.

Why might TD error never reach zero even with perfect value estimates?

Due to stochasticity in the environment. Even with correct values, random rewards and transitions cause TD error to fluctuate around zero. Only the expected TD error

\mathbb{E}[\delta_t]

converges to zero, not individual samples.

What is the relationship between TD(0) and the Bellman equation?

TD(0) is a stochastic approximation to the Bellman equation. The TD target

R_{t+1} + \gamma V(S_{t+1})

is a sampled estimate of the right side of the Bellman equation

\mathbb{E}[R_{t+1} + \gamma V(S_{t+1})|S_t]

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Temporal Difference learning ko samajhne ke liye ek simple examplete hain. Maan lo tum school se ghar jaa rahe ho aur tumhe guess karna hai kitna time lagega. Monte Carlo method mein tum pora walk complete karte ho, tab jake update karte ho—"Oh, 20 minute laga." Lekin TD learning smart hai—har block ke bad tum apna guess update karlete ho: "Ek block mein 2 minute laga, baki ka 17 minute lagega, toh total 19 minute." Real-time learning hai ye.

TD ka core idea hai bootstrapping—matlab tum apne hi estimates seekhte ho. Formula dekho: $V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$ . Yahan $R_{t+1}$ actual reward hai jo tumne dekha, aur $V(S_{t+1})$ tumhara next state ka estimate hai. Dono ko combine karke "TD target" banta hai, jisko tum apne purane estimate $V(S_t)$ se compare karte ho. Jo difference ata hai, usko "TD error" bolte hain—ye bata hai ki tumhara prediction kitna galat tha.

Ye approach powerful kyon hai? Pehla, episodes incomplete bhi hon tab bhi kaam karta hai—khelne ke bech mein hi seekh lete ho, wait nahi karna padta. Dosra, values jaldi propagate hoti hain backwards—goal ke pas wale states pehle seekhte hain, phir unke pehle wale, aur aise hi chain reaction hoti hai. Monte Carlo mein har state ko khud puri episode khelni padti hai value seekhne ke liye, lekin TD mein ek state apne neighbor seekh leta hai.

Ek common confusion: log sochte hain ki TD error zero ho jayega jab learning complete hogi. Galat! Environment stochastic hai—random rewards aur transitions hain. Toh individual TD errors fluctuate karte rahenge, lekin average zero ke around hoga. Aur learning rate alpha ko carefully choose karna padta hai—zyada b toh values oscillate karenge, bohot chhota toh learning slow hogi. TD learning reinforcement learning ki backbone hai—Q-learning, SARSA, sabhi isi foundation pe khade hain.