Linear Methods for Function Approximation

Why the Matrix Matters

Linear function approximation represents a value estimate using features and weights. In linear TD(0), the central convergence question is not only whether the update has a target. It is whether the part of the update involving the current weights shrinks the weight vector or amplifies some of its components. The matrix A controls that behavior.

This condition gives a useful way to organize the topic. First, identify A. Next, unpack its factorization. Then examine the middle factor D(I − γP), because that is where the transition structure and the stationary distribution enter the positive-definiteness argument. Finally, keep the scope of the result clear: a stability condition is not by itself a complete probability-one convergence proof.

Tracing the Update Through A

A = ΦᵀD(I − γP)Φ

The factorization shows the responsibilities of the three ingredients. Φ is the feature matrix, with one row containing the feature vector φ(s) for each state. D is diagonal and contains the stationary-distribution values d(s). P is the transition matrix under policy π, with entries p(s′ | s). The feature matrix appears on both sides of the middle factor because the transition-and-distribution structure is expressed in the feature representation.

The vector b also appears in the TD(0) update, but A has the key stability role. To see the intuition, imagine that A is diagonal. If one diagonal element is negative, the corresponding diagonal element of I − αA is greater than one. That component of the weight vector is amplified rather than reduced. If all diagonal elements are positive, α can be chosen small enough that the diagonal elements of I − αA lie between zero and one, so the corresponding components are shrunk.

Why D(I − γP) Is Central

The middle factor D(I − γP) is central because it combines how often states are represented in the stationary distribution with how the policy moves between states. The convergence argument examines this factor before the feature transformation by Φ and Φᵀ.

Because P is a stochastic matrix and γ is less than 1, every row sum of D(I − γP) is positive. The remaining part of the argument is to establish that the column sums are nonnegative. The stationary-distribution relation d = Pᵀd is used when analyzing those column sums. In the stated continuing, on-policy setting, the resulting components are positive.

1ᵀD(I − γP)

Building a Value Estimate

A linear value estimate is a weighted sum of feature values. For a state s, the feature vector φ(s) describes the state in the chosen representation, and the weight vector determines how strongly the features contribute to the estimate. The learning method changes the weights; the feature design determines what patterns those weights can express.

Estimated value = weighted sum of feature values

This is why a linear approximator should not automatically be dismissed as too simple. It can work well when its features are appropriate. A feature representation can emphasize useful patterns instead of presenting the learning method with an undifferentiated description of the task.

Choosing Feature Representations

Polynomials, Fourier basis features, coarse coding, tile coding, and radial basis functions are different representation choices, not different names for the same feature construction. Each gives the linear learner a different way to describe states and activate features. Consequently, the same update rule can behave differently in practice when supplied with different representations.

LSTD and Nonlinear Alternatives

Linear methods do not all make the same data and computation trade-off. LSTD favors data efficiency, but it has a higher computational scaling cost than the other linear methods described. In practical terms, LSTD uses a more computation-intensive approach in exchange for making efficient use of collected experience.

Nonlinear methods take a different modeling direction from linear approximation. The source includes artificial neural networks trained by backpropagation and variations of stochastic gradient descent among these methods. Their popularity in reinforcement learning has led to the term deep reinforcement learning. The choice between linear and nonlinear approximation is therefore also a choice between relying on designed features and using a nonlinear model to learn representations and parameters.

Common Reasoning Errors

• Treating b as the matrix that determines stability.

  The convergence analysis is mainly about A. The vector b appears in the update, but A determines the behavior of the part involving the current weights.

  Fix: When analyzing stability, begin by identifying A and asking whether it is positive definite.

• Stopping after writing A = ΦᵀD(I − γP)Φ.

  D(I − γP) is the key inner matrix in the positive-definiteness argument.

  Fix: Track the roles of Φ, D, and P, then examine the row sums, column sums, and stationary-distribution relation associated with D(I − γP).

• Claiming that positive definiteness alone is a complete probability-one convergence proof.

  The condition supports the stability analysis, but a complete probability-one proof requires additional stochastic-approximation conditions and reasoning.

  Fix: State clearly whether you are describing the matrix condition or the full convergence proof.

• Assuming every linear approximator is too simple to be useful.

  A linear method can work well when its features are chosen appropriately.

  Fix: Evaluate the feature representation together with the learning method.

• Treating feature selection as a neutral preprocessing detail.

  Feature selection places prior domain knowledge into the reinforcement learning system and strongly influences what can be learned and generalized.

  Fix: Ask which task patterns the chosen representation emphasizes.

Check Your Understanding

Key Takeaways

1. Linear TD(0) uses the matrix A as the central object for analyzing whether the weight-dependent update shrinks or grows.
2. The important factorization is A = ΦᵀD(I − γP)Φ.
3. D(I − γP) is central because its row sums, column sums, and the relation d = Pᵀd support the positive-definiteness argument in the continuing on-policy setting with γ less than 1.
4. Positive definiteness is a stability condition used in the analysis, not by itself a complete probability-one convergence proof.
5. A linear value estimate is a weighted sum of features, so feature selection adds prior domain knowledge and strongly affects learning and generalization.
6. LSTD favors data efficiency at higher computational scaling cost, while nonlinear neural-network methods follow a different modeling direction associated with deep reinforcement learning.