Generalization in Linear Function Approximation

Suppose a reinforcement learning agent observes one state and updates its estimate. The update may affect nearby states as well. How far that effect spreads depends initially on the size and shape of the receptive fields activated by the state. A large receptive field can therefore produce broad generalization. However, broad initial generalization does not by itself mean that the learned function must remain permanently coarse.

The visual represents the first stage of the reasoning. A feature that responds over a large receptive field can connect an observed state with a broader set of nearby states. Changing the shape can also change the pattern of states that receive similar treatment. This is initial generalization: the behavior produced early by the chosen receptive fields.

A linear approximation should therefore be analyzed along two dimensions. Receptive-field size and shape determine the initial generalization behavior. The total number of features has the stronger role in determining the finest discrimination that the complete representation can ultimately support. These statements are compatible: a representation can generalize broadly at first while still supporting finer distinctions through its full collection of features and subsequent updates.

Linear function approximation turns feature values and weights into a value estimate through a weighted sum. Each feature contributes according to its current value and its associated weight. The contributions are then combined into one estimated value. The representation determines which feature values are available to the approximation method, while the weights determine how strongly those available features contribute.

The feature representation strongly influences what a reinforcement learning system can learn and generalize. Feature selection is therefore a way to place prior domain knowledge into the system. Instead of giving the learning method an undifferentiated description, the designer chooses a representation that emphasizes useful patterns in the problem.

Several feature families can be used to represent a task: polynomials, Fourier basis features, coarse coding, tile coding, and radial basis functions. The source identifies these as different ways to represent a task. Their choice matters because the feature representation affects what the system can learn and how it generalizes. The source pack does not specify the internal construction of each family, so the important comparison here is their role as alternative representation choices rather than an unsupported claim about their detailed mechanics.

Linear methods do not all make the same data and computation trade-off. LSTD favors data efficiency: it can make effective use of fewer data samples than the other linear methods described in the source. The cost is higher computational scaling. In other words, LSTD exchanges more computation and associated resource demands for greater efficiency in the amount of experience required.

A linear approximator is not automatically too simple to produce useful value estimates. The source emphasizes that linear approximation can work well when its features are chosen appropriately, and that the linear case is especially well understood theoretically. The source also reports that semi-gradient methods can obtain good results in this setting.

Nonlinear methods take a different modeling direction. 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 contrast is therefore not simply that one method is always better: linear methods depend strongly on a suitable feature representation, while nonlinear methods use a different modeling approach involving neural networks and their training procedures.