Concepts / TD(λ) Algorithm and Eligibility Traces

TD(λ) Algorithm and Eligibility Traces

TD(λ) changes the weight vector at every learning step.

  • Programming

Why Every Step Matters

TD(λ) changes the weight vector at every learning step. It does not wait until the end of a sequence or until a final batch of changes has been collected. Each step uses the information available at that moment to form and apply a new change to the weights.

The central operational pattern is repeated: obtain the scalar TD error and the vector eligibility trace for the current step, use both to form a proportional weight-vector update, and apply that update to the weights.

Two Quantities in One Update

A TD(λ) learning step brings together two different kinds of information. The scalar TD error supplies one overall error signal for the current step. The vector eligibility trace supplies the pattern used to distribute that signal across the weight vector. The resulting change to the weights is proportional to both quantities.

error quantityeligibility patternapplyTD errorone scalarWeight updateproportional changeWeight vectorupdated each stepEligibility traceone vector
How do one scalar TD error and one vector eligibility trace combine to determine the direction and size of the weight-vector update?
QuantityShapeRole in the step
TD errorScalarProvides one overall error signal for the current step
Eligibility traceVectorProvides the pattern used to distribute the signal across the weights
Weight updateVectorCombines the scalar error with the vector eligibility pattern before changing the weights

Reading the Eligibility Trace

Read the eligibility trace alongside the weight vector. The trace is not a replacement for the weights. Instead, it participates in forming the weight update, and that update is then applied to the weight vector. Because the trace is a vector, it supplies a feature-indexed pattern for the change rather than a single undifferentiated quantity.

indexed byindexed byindexed byFeature 1Trace position 1eligibility valueFeature 2Trace position 2eligibility valueFeature 3Trace position 3eligibility value
How are eligibility values associated with positions in the eligibility vector?

At the next learning step, the same relationship is used again with the quantities available for that step. The trace therefore belongs to the repeated-step process: it helps determine the current weight change, and the updated weights are ready for the next step.

The Step-by-Step Control Flow

  1. Observe the information for the current learning step.
  2. Use the current step to obtain the scalar TD error and the vector eligibility trace used by the update.
  3. Combine the scalar error signal with the vector eligibility pattern to form a proportional weight-vector update.
  4. Apply that update to the weight vector.
  5. Move to the next learning step and repeat the relationship with the quantities available then.
computeupdate or usescalar inputvector inputapplycontinueCurrent stepobserve informationTD errorscalar signalWeight updateproportional to bothWeight vectorapply changeNext steprepeatEligibility tracevector pattern
What happens next in a TD(λ) step, from observing a transition to computing the error, updating the eligibility trace, and changing the weights?

A Worked Mental Model

Separating Signal from Pattern

Imagine a TD(λ) step with one scalar TD error and an eligibility trace containing one value for each weight position. Explain what each quantity contributes before the weight vector is changed.

Read the TD error: Treat the TD error as one overall signal for the current step. It tells the update how much error information is available at this step.

Read the eligibility trace: Treat the eligibility trace as a vector pattern aligned with the weight vector. Its positions indicate how the scalar signal is distributed across the weight positions.

Form the update: Combine the scalar TD error with the vector eligibility trace to form a weight-vector change proportional to both quantities.

Apply the change: Apply the resulting vector update to the weight vector. This is the weight change for the current step, and the process is repeated on the next step.

The scalar TD error supplies the overall error quantity, while the vector eligibility trace supplies the pattern across weights. Together they determine the weight-vector update.

one TD(λ) stepWeight vectorbefore updateWeight vectorafter update
What changes in the weight vector during one TD(λ) update, and how does the eligibility pattern determine the vector pattern of that change?

This mental model intentionally separates the jobs of the two inputs. The TD error is not itself the complete weight update because it is only a scalar. The eligibility trace is not itself the complete weight update because it provides the pattern but not the current scalar error signal. The update requires both.

Mistakes to Avoid

  • Treating the TD error and eligibility trace as interchangeable.

    The TD error is scalar, while the eligibility trace is a vector. They carry different shapes of information and have different roles.

    Fix: Describe the TD error as the overall error signal and the eligibility trace as the vector pattern used to distribute that signal.

  • Calling the eligibility trace the weight vector.

    The trace participates in forming the update, but the update is applied to the separate weight vector.

    Fix: Keep the trace and weight vector as separate objects in your explanation.

  • Assuming TD(λ) waits until the end to change the weights.

    TD(λ) changes the weight vector at every learning step.

    Fix: Look for the repeated update relationship: form the proportional update and apply it on each step.

  • Mentioning both quantities without explaining proportionality.

    Both quantities determine the weight-vector update; they are not background labels.

    Fix: State that the scalar error and vector trace jointly form a proportional weight-vector change.

Check Your Understanding

MEDIUM

In your own words, describe one TD(λ) learning step. Identify which quantity supplies the overall error signal, which quantity supplies the vector pattern, what object is changed, and when the change is applied.

Hints
  • Start by naming the shape of the TD error.
  • Then name the shape and role of the eligibility trace.
  • Finish by explaining the repeated application to the weight vector.

What do you think happens?

If a description of a TD(λ) step mentions the scalar TD error but omits the eligibility trace, does it fully specify the weight-vector update?

  • Yes, because the scalar error is the complete update
  • No, because the vector eligibility pattern is also required
  • Yes, because the trace is only descriptive
  • No, because TD(λ) changes weights only after a final batch
Reveal answer

Answer: No, because the vector eligibility pattern is also required.

The TD error supplies the overall error signal, while the eligibility trace supplies the vector pattern used to distribute that signal across the weight vector. The update is proportional to both.

Key Takeaways

  1. TD(λ) updates the weight vector at every learning step.
  2. The TD error is one scalar overall error signal for the current step.
  3. The eligibility trace is a vector that supplies the pattern for distributing the signal across the weights.
  4. The weight-vector update is proportional to both the TD error and the eligibility trace.
  5. The algorithm repeats this relationship on the next learning step.

Key Takeaways

  • TD(λ) changes the weight vector on every learning step.
  • The scalar TD error and vector eligibility trace have different shapes and different roles.
  • The TD error provides the overall signal, while the eligibility trace provides the vector pattern.
  • Their proportional combination determines the weight-vector update.
  • The same update relationship is repeated at the next step.

Related Topics