Feature Construction for Linear Function Approximation

A reinforcement learning system does not have to learn directly from an undifferentiated description of a state. It can first transform the state into a collection of features. A linear value approximator then combines those feature values with weights to produce an estimated value. This makes feature construction a central design decision: the learning method matters, but the representation supplied to it matters as well.

For an OrderN polynomial basis, begin with a state containing d real-valued variables. Each basis function chooses one integer exponent for every state variable. The function then raises each variable to its chosen exponent and multiplies all of those powered terms together. The full basis contains every function formed from the allowed exponent choices.

In an OrderN basis, every exponent may be any integer from 0 through N. The exponent choices are independent across the state variables: choose one allowed power for the first variable, one for the second, and continue until every variable has a power. Each complete set of choices identifies one basis function.

The two-variable case can be pictured as a grid of exponent pairs. Moving across the grid changes the exponent for one variable, while moving in the other direction changes the exponent for the other variable. The important counting rule remains the same: every allowed combination is included, not only products in which both variables appear with positive powers.

After a state has been converted into feature values, a linear function approximator combines those values with weights through a weighted sum. The features describe the representation supplied to the approximator; the weights determine how strongly the approximator uses those features in its value estimate.

Feature selection is a way to place prior domain knowledge into a reinforcement learning system. Instead of presenting the learning method with an undifferentiated description, the designer chooses a representation that emphasizes useful patterns in the problem. A linear approximator can therefore be useful when its features are chosen appropriately; judging the learning method without considering the representation can give the wrong impression about what it can learn.

The source characterizes LSTD as favoring data efficiency while having a higher computational scaling cost than the other linear methods described. This is a practical trade-off: LSTD can make better use of available data, but the additional computational cost must be considered when choosing an approximation method.

Linear approximation and nonlinear approximation represent two different modeling directions. In the linear case, selected features and weights are combined through a weighted sum. The source reports that the linear case is especially well understood theoretically and that semi-gradient methods can obtain good results in this setting when the features are appropriate.

Nonlinear methods include artificial neural networks trained by backpropagation and variations of stochastic gradient descent. Their popularity in reinforcement learning has led to the term deep reinforcement learning. The essential contrast for this topic is that linear approximation relies on a chosen feature representation and a weighted sum, whereas these nonlinear methods use neural-network training methods.