True Online TD(λ) Algorithm

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.

Diagonal and Off-Diagonal Roles

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.

Following the Diagonal

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.

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

• Treating every vector in the triangle as part of the diagonal sequence.

  The diagonal is determined by matching indices, not by selecting an entire row.

  Fix: Select θ_tt for each time index t. In the example, θ₂₂ is diagonal, while θ₂₀ and θ₂₁ are off-diagonal.

• Assuming θ_t names an arbitrary vector from row t.

  The notation θ_t refers specifically to the diagonal vector θ_tt.

  Fix: Expand the shorthand when needed: θ₂ means θ₂₂, not θ₂₀ or θ₂₁.

• Thinking True Online TD(λ) must explicitly build the entire triangle.

  The defining computational strategy is to avoid unnecessary work by targeting the diagonal sequence directly.

  Fix: Describe θ₀₀ as the input and θ_TT as the output, with intermediate diagonal vectors computed from the preceding diagonal vector.

• Treating linear function approximation as unrelated to the algorithm.

  The compact diagonal-computation strategy leads to True Online TD(λ) in the linear case.

  Fix: Connect the algorithm to the use of a linear value representation whose parameters are the weight vectors.

Check Your Understanding

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.