True Online TD(λ) Algorithm

True Online TD(λ) is derived from the online λ-return construction.

Programming

The Computational Problem

True Online TD(λ) is derived from the online λ-return construction. That construction produces a collection of weight vectors rather than one immediately visible sequence. The collection can be viewed as a triangle. The central computational insight is that the final learning process needs a particular sequence from this triangle, not every vector in it.

Rows of the Weight-Vector Triangle

The online λ-return construction forms a triangle of weight vectors because the construction contains multiple rows, with each row containing vectors associated with different time indices. A vector can therefore be identified by two indices. The diagonal consists of the vectors whose two indices match: θ₀₀, θ₁₁, θ₂₂, and so on. Vectors whose indices do not match belong elsewhere in the triangle.

How are the online λ-return weight vectors arranged across time, and which vectors form the diagonal?

Diagonal and Off-Diagonal Roles

Vector group	Index pattern	Role in the strategy
Diagonal vectors	θ₀₀, θ₁₁, θ₂₂, ... where both indices match	The sequence targeted by the efficient computation
Off-diagonal vectors	Vectors such as θ₁₀, θ₂₀, or θ₂₁ where the indices differ	Other vectors in the full online λ-return triangle

The diagonal is selected by matching the two indices.

The notation θ_t refers to the diagonal vector θ_tt. This shorthand matters because True Online TD(λ) is concerned with the sequence θ₀₀, θ₁₁, θ₂₂, and onward. The other vectors are part of the full construction, but they are not the direct computational target of the final learning process.

Which weight vectors are selected, and how do they differ from the other vectors in the triangle?

Following the Diagonal

Worked example

Selecting the useful sequence

Suppose a short online λ-return construction is represented by rows containing θ₀₀; θ₁₀ and θ₁₁; θ₂₀, θ₂₁, and θ₂₂; and θ₃₀, θ₃₁, θ₃₂, and θ₃₃. Which vectors form the diagonal sequence?

1
Step 1
Look for vectors whose first and second indices are equal.
2
Step 2
From the first row, select θ₀₀. From the second row, select θ₁₁. From the third row, select θ₂₂. From the fourth row, select θ₃₃.
3
Step 3
Treat the selected vectors as the sequence that the efficient strategy aims to compute.

Result

The diagonal sequence is θ₀₀, θ₁₁, θ₂₂, θ₃₃. The remaining vectors belong to the full triangle but are not members of this diagonal sequence.

This example illustrates the distinction between constructing the full object and extracting the computational target. A full construction would contain every vector in each row. The True Online TD(λ) strategy instead seeks a compact way to compute each diagonal vector from the one before it.

How does True Online TD(λ) move from the initial diagonal vector to the final diagonal vector without explicitly constructing the entire triangle?

Linear Value Representation

The diagonal-computation strategy becomes the True Online TD(λ) algorithm in the linear case. Here, the weight vectors are the parameters of a linear value representation. The important point is that linear function approximation supplies the setting in which the needed diagonal vectors can be computed through a compact strategy rather than by explicitly producing every vector in the triangle.

Common Interpretation Errors

Common mistake
Treating every vector in the triangle as part of the diagonal sequence.
What it looks like
Calling θ₂₀, θ₂₁, and θ₂₂ the diagonal vectors simply because they appear in the same row.
Why it fails
The diagonal is determined by matching indices, not by selecting an entire row.
Do this instead
Select θ_tt for each time index t. In the example, θ₂₂ is diagonal, while θ₂₀ and θ₂₁ are off-diagonal.
Common mistake
Assuming θ_t names an arbitrary vector from row t.
What it looks like
Reading θ₂ as a generic shorthand for any vector in the third row.
Why it fails
The notation θ_t refers specifically to the diagonal vector θ_tt.
Do this instead
Expand the shorthand when needed: θ₂ means θ₂₂, not θ₂₀ or θ₂₁.
Common mistake
Thinking True Online TD(λ) must explicitly build the entire triangle.
What it looks like
Describing the algorithm as a procedure that first constructs every off-diagonal vector and only then selects the diagonal.
Why it fails
The defining computational strategy is to avoid unnecessary work by targeting the diagonal sequence directly.
Do this instead
Describe θ₀₀ as the input and θ_TT as the output, with intermediate diagonal vectors computed from the preceding diagonal vector.
Common mistake
Treating linear function approximation as unrelated to the algorithm.
What it looks like
Explaining the diagonal strategy without mentioning the representation setting in which it becomes True Online TD(λ).
Why it fails
The compact diagonal-computation strategy leads to True Online TD(λ) in the linear case.
Do this instead
Connect the algorithm to the use of a linear value representation whose parameters are the weight vectors.

Check Your Understanding

MEDIUM

A construction contains θ₀₀, θ₁₀, θ₁₁, θ₂₀, θ₂₁, and θ₂₂. Identify the diagonal sequence, explain why the other vectors are not diagonal, and state why an efficient True Online TD(λ) strategy does not need to explicitly construct every vector.

Hints

Compare the two indices on each vector.
The diagonal uses the form θ_tt.
The efficient strategy targets the useful sequence rather than the complete triangle.

Your attempt (not saved)

What do you think happens?

For the vectors θ₀₀, θ₁₀, θ₁₁, θ₂₀, θ₂₁, and θ₂₂, which sequence is the diagonal?

θ₀₀, θ₁₀, θ₂₀
θ₀₀, θ₁₁, θ₂₂
θ₁₀, θ₂₁
All six vectors

Reveal answer

Answer:

θ₀₀, θ₁₁, θ₂₂

The diagonal consists of vectors whose two indices are equal. The other vectors are off-diagonal members of the full triangle.

Key Takeaways

1
The online λ-return construction forms a triangle of weight vectors indexed by two time-related indices.
2
The diagonal vectors have matching indices and are written as θ_tt; the shorthand θ_t refers to θ_tt.
3
True Online TD(λ) targets the diagonal sequence instead of explicitly constructing every vector in the triangle.
4
The initial diagonal vector θ₀₀ is the input, the final diagonal vector θ_TT is the output, and intermediate diagonal vectors support later bootstrapping.
5
In the linear case, this compact diagonal-computation strategy becomes the True Online TD(λ) algorithm.

At a glance

The online λ-return construction can be pictured as a triangle of weight vectors.
Only vectors with equal indices belong to the diagonal sequence.
True Online TD(λ) avoids explicitly computing the full triangle and instead computes the diagonal sequence efficiently.
The strategy becomes the True Online TD(λ) algorithm when used with a linear value representation.

Related concepts

More concepts starting with T