Temporal-Difference Learning II and DRL Taxonomy #

One-step TD methods bootstrap after a single transition. Multi-step methods instead use several observed rewards before bootstrapping, forming a bridge between TD(0) and Monte Carlo learning.

Course Content covered in this module:

• Temporal-Difference Learning: n-step returns and TD(λ)
• Classification of Reinforcement Learning approaches, algorithms and applications:
  • Model-Based versus Model-Free
  • Value-Based versus Policy-Based
  • On-Policy versus Off-Policy

Learning Objectives #

By the end of this module, you should be able to:

• calculate one-step, two-step and n-step returns;
• apply the n-step TD prediction update;
• explain the bias-variance trade-off created by the choice of \( n \) ;
• explain how TD(λ) combines returns of different lengths;
• describe the purpose of eligibility traces; and
• classify reinforcement learning algorithms along three independent dimensions.

1. From One-Step TD to Multi-Step TD ☆ #

TD(0) uses one observed reward and then bootstraps from the estimated value of the next state:

Monte Carlo learning waits until the episode ends and uses the complete observed return. An n-step method lies between these two extremes:

• it observes the next \( n \) rewards;
• it then bootstraps from the estimated value of the state reached after those steps.

flowchart TD
    A["TD(0): one reward"] --> B["n-step TD: several rewards"]
    B --> C["Monte Carlo: complete episode"]

    style A fill:#E1F5FE,stroke:#1E88E5
    style B fill:#BBDEFB,stroke:#1E88E5
    style C fill:#90CAF9,stroke:#1E88E5

2. The n-Step Return ☆ #

The n-step return from time \( t \) is:

The final term is the bootstrap estimate. If the episode terminates before step \( t+n \) , there is no successor value beyond the terminal state, so the remaining bootstrap term is zero.

Special Cases #

For \( n=1 \) :

This is the ordinary TD(0) target.

For \( n=2 \) :

As \( n \) reaches the remaining episode length, the target becomes the Monte Carlo return because no estimated successor value is needed.

3. n-Step TD Prediction ☆ #

After the n-step return becomes available, the value of the starting state is updated by:

The n-step TD error is therefore:

Unlike TD(0), the update cannot be made immediately after one transition. It becomes available after \( n \) rewards have been observed, or when the episode terminates.

Simplified Algorithm #

Initialise V(s)

For each episode:
    generate experience one transition at a time
    after n rewards are available:
        calculate the n-step return
        update the state visited n steps earlier
    continue until all remaining states have been updated

4. Worked n-Step Example ☆ #

Suppose:

• \( n=3 \) ;
• rewards are \( 2, 0, 4 \) ;
• \( \gamma=0.9 \) ;
• \( V(S_{t+3})=5 \) ;
• \( V(S_t)=3 \) ;
• \( \alpha=0.1 \) .

First calculate the three-step return:

Then update the value:

5. Choosing n: Bias and Variance ☆ #

The choice of \( n \) determines how much the target depends on current estimates and how much it depends on sampled rewards.

There is no universally best value of \( n \) . It depends on the task, reward noise, quality of current estimates and acceptable update delay.

6. TD(λ): Combining Different Step Lengths ☆ #

Choosing one fixed value of \( n \) can be restrictive. TD(λ) combines one-step, two-step, three-step and longer returns using geometrically decreasing weights.

For a continuing formulation, the λ-return is:

The value update is:

Meaning of λ #

• \( \lambda=0 \) gives the one-step TD target.
• Intermediate values blend short and long returns.
• \( \lambda \rightarrow 1 \) gives increasing weight to longer returns and approaches Monte Carlo learning in episodic tasks.

The discount factor ( \gamma )

controls the importance of rewards over time. The trace-decay parameter ( \lambda )

controls how strongly learning credit is carried backwards across recently visited states.

7. Eligibility Traces ☆ #

The λ-return is the forward view of TD(λ): it considers a weighted mixture of future n-step returns. Eligibility traces provide the corresponding backward view, allowing values to be updated online.

The ordinary TD error remains:

For an accumulating trace:

Every state is updated according to its current eligibility:

A recently visited state has a larger trace and receives more credit or blame. Its trace decays when it is not revisited.

8. Three Independent Classification Questions ☆ #

Reinforcement learning algorithms can be classified by asking three different questions:

flowchart TD
    A["Reinforcement Learning Algorithm"] --> B["Uses a model?"]
    A --> C["Learns values or a policy?"]
    A --> D["Learns about the behaviour policy?"]

    style A fill:#90CAF9,stroke:#1E88E5
    style B fill:#E1F5FE,stroke:#1E88E5
    style C fill:#E1F5FE,stroke:#1E88E5
    style D fill:#E1F5FE,stroke:#1E88E5

These dimensions are independent. For example, an algorithm can be model-free, value-based and off-policy at the same time.

9. Model-Based versus Model-Free ☆ #

The relevant model is usually represented by transition and reward information such as \( p(s',r\mid s,a) \) .

Model-free does not mean that the agent has no neural network or internal representation. It means that the algorithm does not require an explicit model of environment transitions and rewards for planning.

10. Value-Based versus Policy-Based ☆ #

Value-Based #

A value-based method learns \( V(s) \) or \( Q(s,a) \) and derives behaviour from those estimates.

Examples include SARSA, Q-learning and DQN.

Policy-Based #

A policy-based method directly parameterises and improves \( \pi_\theta(a\mid s) \) . REINFORCE is a standard example.

Actor-Critic #

Actor-Critic methods combine both ideas:

• the actor represents the policy;
• the critic estimates value and evaluates the actor’s decisions.

11. On-Policy versus Off-Policy ☆ #

The distinction concerns the relationship between two policies:

• behaviour policy: generates experience;
• target policy: is evaluated or improved.

An off-policy method can explore using an \( \varepsilon \) -greedy behaviour policy while learning about a greedy target policy.

12. Classifying Common Algorithms ☆ #

Do not force every algorithm into one label. The three axes answer different questions, and some algorithm families have both on-policy and off-policy variants.

Common Mistakes ☆ #

• n-step TD does not sum only rewards; unless termination occurs, it also includes a discounted bootstrap value.
• The exponent on the bootstrap term is ( n )

, while the final sampled reward uses ( \gamma^{n-1} )

.

• A larger ( n )

does not automatically mean better learning; it changes bias, variance and update delay. #

\( \gamma \)

and ( \lambda )

have different roles.

• Model-Free is not the same as Value-Based.
• On-Policy and Policy-Based are different classifications.

Practice Questions #

1. Write the three-step return and identify its bootstrap term.
2. Calculate an n-step TD update for a supplied reward sequence.
3. Explain what happens as \( n \) grows to the remaining episode length.
4. Compare the bias and variance of small and large values of \( n \) .
5. Explain the meanings of \( \lambda=0 \) and \( \lambda\rightarrow1 \) .
6. What information is stored by an eligibility trace?
7. Classify SARSA and Q-learning along the three taxonomy dimensions.
8. Why are Value-Based and On-Policy not opposite categories?

Key Takeaways ☆ #

• n-step TD observes several rewards before bootstrapping.
• TD(0) and Monte Carlo are the two ends of the multi-step spectrum.
• Small ( n )

usually means more bias and less variance; large ( n )

usually means less bias and more variance.

• TD(λ) combines returns of different lengths.
• Eligibility traces distribute each TD error across recently visited states.
• Model-Based/Model-Free, Value-Based/Policy-Based and On-Policy/Off-Policy are separate classification axes.

Checklist #

• I can calculate an n-step return.
• I can apply the n-step TD update.
• I can explain the bias-variance effect of changing \( n \) .
• I can explain the meaning of \( \lambda \) .
• I can describe eligibility traces.
• I can distinguish the three DRL taxonomy axes.
• I can classify common reinforcement learning algorithms.

References #

1. Sutton and Barto, Reinforcement Learning: An Introduction, Chapters 7 and 12.
2. Official Course Content for Temporal-Difference Learning II and DRL taxonomy.
3. Supplied material introducing n-step TD prediction.

Home | Deep Reinforcement Learning