Unit 4: Temporal Difference (TD) Learning
Comprehensive Exam Notes
Syllabus Covered: Temporal-Difference learning methods - TD (0), SARSA, Q-Learning
and their variants. Markov reward process (MRP), Overview of TD(1) and TD(λ).
Reference: Chapters 6, 7, and 12 of Sutton & Barto.
1. Introduction to Temporal Difference (TD) Learning
Temporal Difference (TD) learning is a central and novel idea in Reinforcement Learning. It
acts as a bridge between Monte Carlo (MC) methods and Dynamic Programming (DP):
• Like MC: TD methods can learn directly from raw experience without a model of the
environment's dynamics.
• Like DP: TD methods update estimates based in part on other learned estimates,
without waiting for a final outcome (they bootstrap).
2. Markov Reward Process (MRP)
A Markov Reward Process (MRP) is a simplified version of a Markov Decision Process
(MDP). It is essentially an MDP without actions. In an MRP, the state transitions occur
probabilistically, and rewards are emitted, but there is no agent making choices. It is
formally a tuple (S, P, R, γ).
Evaluating an autonomous system or a specific fixed policy in an MDP effectively turns the
MDP into an MRP (because the actions are fixed by the policy).
3. TD(0) Prediction
The goal of prediction is to estimate the state-value function V (s). MC methods wait until
π
the end of the episode to determine the actual return G to update V(S ). TD(0), or one-step
t t
TD, only waits until the next time step.
At time t+1, it immediately forms a target and makes a useful update using the observed
reward R
t+1 and the estimate V(St+1):
1
V(St) ← V(St) + α [ Rt+1 + γ V(St+1) − V(St) ]
• α: Learning rate (step size).
• TD Target: R
t+1 + γ V(St+1)
• TD Error (δ ): The difference between the estimated value and the better estimate
t
(Target − V(St)).
4. TD Control Algorithms
For control (finding the optimal policy), we again need to estimate Action-Values Q(s, a)
instead of State-Values V(s). There are two primary TD control algorithms:
A. SARSA (On-Policy TD Control)
SARSA derives its name from the tuple of events that make up a single transition: State,
Action, Reward, Next State, Next Action (S , A , R
t t t+1, St+1, At+1). It evaluates the exact same
policy that it uses to select actions.
Q(St, At) ← Q(St, At) + α [ Rt+1 + γ Q(St+1, At+1) − Q(St, At) ]
B. Q-Learning (Off-Policy TD Control)
Q-learning is arguably the most famous RL algorithm. It is an off-policy method because the
learned action-value function Q directly approximates the optimal action-value function q ,
*
independent of the policy being followed.
It assumes the agent will take the greedy (best) action in the next state, regardless of what
the actual behavior policy decides to do.
Q(St, At) ← Q(St, At) + α [ Rt+1 + γ maxa Q(St+1, a) − Q(St, At) ]
2
5. Overview of TD(1) and TD(λ)
TD(0) looks 1 step ahead. MC looks all the way to the end of the episode. What if we want to
look n steps ahead?
• n-step TD: Updates based on n steps of real rewards plus the estimated value of the
state n steps later.
• TD(1): Equivalent to Monte Carlo. It waits until the end of the episode and propagates
the error backwards.
• TD(λ): Uses a mechanism called Eligibility Traces. It elegantly averages all n-step
updates. When a state is visited, its trace is set to 1, and then decays by γλ every step.
The error is distributed backward to recently visited states based on their trace. λ
controls the trade-off between TD(0) and MC.
6. Code Example: Q-Learning
def q_learning(env, num_episodes, alpha=0.1, gamma=0.99, epsilon=0.1):
# Initialize Q-table to zeros
Q = [Link](([Link], [Link]))
for _ in range(num_episodes):
state = [Link]()
done = False
while not done:
# Epsilon-greedy action selection
if [Link](0, 1) < epsilon:
action = env.action_space.sample() # Explore
else:
action = [Link](Q[state]) # Exploit
next_state, reward, done, _ = [Link](action)
# Q-Learning Update (Off-Policy)
best_next_action = [Link](Q[next_state])
td_target = reward + gamma * Q[next_state][best_next_action]
td_error = td_target - Q[state][action]
Q[state][action] += alpha * td_error
state = next_state
return Q
3
📝 Exam Preparation Section
Short Answer Questions
1. Define the TD Error.
Ans: The TD error, δ = R
t t+1 + γ V(St+1) − V(St), is the difference between the estimated
value of a state and the updated target estimate based on the subsequent immediate
reward and next state value.
2. How does TD differ from Monte Carlo (MC)?
Ans: TD updates its estimates based on other learned estimates without waiting for the
episode to end (Bootstrapping). MC must wait until the episode terminates to calculate
the true return.
Long Answer Questions
1. Explain the difference between SARSA and Q-Learning with equations.
Hint: SARSA is On-Policy. It updates using the action A
t+1 actually taken by the ε-greedy
policy. Q-Learning is Off-Policy. It updates using the maximum possible Q-value for the
next state max Q(S
a t+1, a), assuming greedy behavior.
2. What is an Eligibility Trace? Briefly explain TD(λ).
Hint: It is a temporary record of the occurrence of an event (state or action). It helps
bridge the gap between 1-step TD and Monte Carlo. TD(λ) uses these traces to propagate
TD errors back to recently visited states.
Multiple Choice Questions
Q1. Q-learning is a/an ________ method.
a) On-policy b) Off-policy c) Model-based d) Unsupervised
Q2. In TD learning, what is "bootstrapping"?
a) Learning without exploration
b) Updating estimates based on other learned estimates
c) Waiting until the end of an episode to learn
d) Using a perfect model of the environment
4
⚡ Quick Revision Cheat Sheet
• TD Advantage: Can learn online, step-by-step. Doesn't need a model, doesn't need
to wait for the end of the episode.
• TD(0): V(S) ← V(S) + α [R + γV(S') − V(S)]
• SARSA: Q(S,A) ← Q(S,A) + α [R + γQ(S',A') − Q(S,A)]. (Safe, on-policy, considers
exploration risks).
• Q-Learning: Q(S,A) ← Q(S,A) + α [R + γ max Q(S',a) − Q(S,A)]. (Bold, off-policy,
finds optimal path).
• Eligibility Traces (λ): A decaying memory variable. Helps update states that
happened multiple steps ago, not just the immediate predecessor.
• TD(1): Mathematically identical to Monte Carlo.