Temporal Difference Learning: The Most Powerful RL Solution

Mastering the third and most widely used method in reinforcement learning

Our Robot enjoys using SARSA(TD method), Source: Generated by ChatGPT

Not a Medium member yet? No worries, you can still read it **here!**

If you’ve been following along, you’re now ready to dive into the third, and most popular, solution method for RL problems: Temporal Difference (TD) Learning! If not, check out the previous article first: **Monte Carlo Off-Policy Explained.**

🔎 What is Temporal Difference (TD) Learning?

Basically, TD takes everything we’ve learned so far and blends it into the best combination! It borrows the strengths of both Dynamic Programming (DP) and Monte Carlo (MC):

• Like DP, it updates estimates based on existing estimates (bootstrapping).
• Like MC, it learns directly from sampled experience by interacting with the environment.

Let’s see the difference:

• In DP, we relied on expectations because we weren’t simulating any real episodes.
• In MC, we used sampling, where the agent interacts with the environment, waits until the end of an episode, and then updates values.
• In TD, we also use sampling, but with a twist: instead of waiting until the episode ends, we update at every step (online).

To understand how TD works, let’s first revisit the update equation used in MC’s incremental implementation (EMA formula):

EMA Value Update Formula, Source: Author

In MC, we used the EMA formula for incremental updates to calculate values and Q-values. In TD, we keep the same incremental style, but instead of waiting until the episode ends, we update at every step.

-How does that work if we don’t know the full return yet?

That’s exactly why MC had to wait until the episode finished! But TD introduces a clever trick: it estimates the return by looking just one step ahead. Let’s look at its formula:

TD(0) Value Update Formula, Source: Author

Here, we redefine the return Rₜ​ to include only the immediate reward plus the discounted value of the next state. This simplest form of Temporal Difference learning is called TD(0).

-Why does it converge?

Even though we only look at the next step’s value, each update shifts our estimates closer to the true values. Over many steps and episodes, these estimates converge to the real values. This is possible because TD uses bootstrapping (updating values from existing estimates), something it inherits from DP. MC, on the other hand, didn’t bootstrap at all; it just waited for the full return.

TD = sampling (from MC) + bootstrapping (from DP).

🤔 Why is it called Temporal Difference Learning?

Remember in EMA, we updated by incrementing the difference (the error) between our current estimate and the new one. TD works the same way, but the new information comes from the next time step.

• Difference → comes from the TD error, the gap between our current value estimate and the updated one.
• Temporal → comes from comparing predictions across successive time steps.

In short, TD learns from the error between consecutive time-based predictions, hence the name Temporal Difference :)

🌟 Advantages of Temporal Difference (TD) Learning

The key question TD answers is: -Do we really need to wait until the episode finishes to start learning, or can learning begin earlier?

The answer: we can (and should) learn before the episode ends! Here’s why TD is so powerful:

• No model required: TD learns directly from sampling the environment, no need for a full model.
• Fully incremental (online): updates happen at every step, not just at the end of an episode. This means the agent can learn while interacting, which mimics real reinforcement learning. This is especially important when episodes are very long or when the task is continual (with no episodes).
• Efficient: requires less computation and memory compared to other methods.
• Convergence: TD methods are guaranteed to converge, and in practice, they often converge faster than MC.

🤖SARSA: On-Policy TD Control

Before diving into the TD algorithm, we need to address an important point: just like MC methods, TD also faces the exploration-exploitation trade-off. To address this, TD methods are categorized into two types: on-policy and off-policy. The on-policy TD control method is called SARSA. It uses the same incremental update formula as before, but applied to Q-values instead of state values:

The name SARSA comes from the five elements (5-tuple) required for each update: (S, A, R, S′, A′)

• S → current state
• A → action taken
• R → reward received
• S′ → next state
• A′ → next action chosen (according to the current policy)

This makes SARSA an on-policy method, since it updates using the same policy that the agent is currently following.

Now, let's take a look at our algorithm:

input: -, output: Vπ
Algorithm SARSA():
    Initialize Q(s, a) ← arbitrarily for all s ∈ S, a ∈ A(s)
    s ← intial state
    repeat:
        a ← action taken on s by π
        s', r ← env.step(a)
        a' ← action taken on s' by π
        Q(s, a) ← Q(s, a) + α[r + γQ(s', a') - Q(s, a)]
        s ← s'; a ← a'
    return Vπ

1️⃣ Initialization

• Q(s, a) is initialized arbitrarily (often zeros).
• s is set to the initial state.

2️⃣ Interaction Loop

• The agent selects an action a in state s using policy π (can be greedy, ε-greedy, softmax, etc.).
• The environment returns the next state s′ and reward r.
• The agent selects the next action a′ in state s′ according to π.

3️⃣ TD(0) Update

• The Q-value is updated using the SARSA formula: Q(s,a) ← Q(s,a) + α[r + γQ(s′,a′) − Q(s,a)]
• Then move to the next state and action: s ← s′, a ← a′.

4️⃣ Policy Improvement

• Explicit policy improvement is not required at each step.
• However, when taking actions, you can always select the max-value action for a greedy improvement.
• If needed, a formal policy function π(s) can be defined later by looping over Q(s, a).

✅ What We’ve Learned…

Sounds like TD is better and easier than MC and DP, huh? Let’s review:

• TD Learning Combines the Best of MC and DP: From Monte Carlo: learning directly from sampled experience. From Dynamic Programming: bootstrapping using existing estimates.
• TD(0) Is the Simplest Form Uses the immediate reward plus the discounted value of the next state to estimate returns. TD updates values online, at each step, rather than waiting for the episode to finish.
• SARSA: On-Policy TD Control On-policy method that updates Q-values using (S, A, R, S′, A′). Handles exploration vs. exploitation via the chosen policy (ε-greedy, softmax, etc.).

In short, TD Learning lets the agent learn continuously, efficiently, and effectively, making it the most widely used solution method in reinforcement learning today!

👉Next up: See it all in action!

[embed]Learn SARSA the Easy Way: Your First Temporal Difference Algorithm Tutorial 9.1: Implementing the SARSA Algorithm for Our Maze Problempub.towardsai.net

👉 Then, check the next TD method:

[embed]Cracking Q-Learning Mastering the second key method in Temporal Difference learningpub.towardsai.net

✨ *As always…* stay curious, stay coding, and stay tuned!**

📚References:

• Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.