Feature Construction for Linear Function Approximation
Each OrderN polynomial basis function multiplies one powered term for every state variable.
From State to Features
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.
Exponent Vectors
For the ith polynomial basis function, cᵢ,ⱼ denotes the integer exponent selected for state variable j. The complete exponent vector for that function contains one such exponent for each of the d state variables.
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.
A Two-Variable Basis Function
Construct the function determined by the exponent pair (1, 2) for state variables s₁ and s₂.
Choose the first exponent: The first exponent is 1, so the first state variable contributes s₁¹.
Choose the second exponent: The second exponent is 2, so the second state variable contributes s₂².
Multiply the powered terms: The basis function multiplies the contribution from every state variable.
The resulting function is s₁s₂².
Counting the Basis
(N + 1)^d
A Small Two-Variable Basis
Determine how many functions are in an Order2 polynomial basis for d = 2 state variables, then list the exponent pairs.
Count choices for each variable: Because N = 2, each exponent can be 0, 1, or 2. Each variable therefore has 3 choices.
Count all pairs: There are 3 choices for the first exponent and 3 choices for the second, giving 3 × 3 = 9 exponent pairs.
List the pairs: The pairs are (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), and (2,2).
Translate pairs into products: Each pair supplies the powers for s₁ and s₂ in one product.
The basis contains 9 functions: 1, s₂, s₂², s₁, s₁s₂, s₁s₂², s₁², s₁²s₂, and s₁²s₂².
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.
Weighted Value Estimates
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.
Combining Three Features
A state is represented by three feature values, and the approximator has three corresponding weights. Describe how the estimate is formed.
Represent the state: Evaluate the selected features for the state.
Pair features with weights: Each feature value is combined with its corresponding weight.
Add the weighted contributions: The linear approximator sums the contributions to form one value estimate.
The estimate is a weighted sum of the three feature values.
Representation as Prior Knowledge
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.
| Representation | High-level role supported by the source |
|---|---|
| Polynomial basis | Constructs features by multiplying powered terms from the state variables. |
| Fourier basis features | Provides an alternative way to represent a task. |
| Coarse coding | Provides an alternative way to represent a task. |
| Tile coding | Provides an alternative way to represent a task. |
| Radial basis functions | Provides an alternative way to represent a task. |
LSTD Trade-offs
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 and Nonlinear Directions
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.
Mistakes to Avoid
Counting only the products in which every state variable appears with a positive power.
The allowed exponent range includes 0 through N.
Fix:
Include every exponent combination, including combinations with one or more zero exponents.Using N^d instead of (N + 1)^d.
There are N + 1 integer choices from 0 through N.
Fix:
Count the endpoints as well as the values between them.Treating one exponent pair as the whole basis.
A complete basis combines all allowed exponent choices.
Fix:
Use one exponent vector to construct one function, then enumerate all allowed vectors for the full basis.Assuming a linear approximator is automatically too simple to be useful.
The source says that linear approximation can work well when its features are chosen appropriately.
Fix:
Evaluate the representation and the learning method together.Describing every named representation with details not established in this section.
The source only establishes that they provide different ways to represent a task.
Fix:
Use the stated high-level distinction unless a source covering their construction is available.
Practice
A state has d = 3 variables and you choose an Order1 polynomial basis. How many basis functions are included? Then describe the function produced by the exponent vector (1, 0, 1). Finally, explain in words how the resulting feature values would be combined with weights to form a value estimate.
Hints
- Each variable has N + 1 allowed exponent choices.
- Use one powered term for each of the three state variables.
- A linear value estimate is a weighted sum of the feature values.
Practice Check
Resolve the three-variable Order1 task.
Count the basis: Each of the three variables has 2 choices, 0 or 1, so the complete basis contains 2^3 functions.
Construct the selected function: The vector (1,0,1) assigns power 1 to the first variable, power 0 to the second, and power 1 to the third. The product is s₁s₃.
Form the estimate: Evaluate the selected basis features for the state and combine their values with their corresponding weights through a weighted sum.
The basis contains 8 functions, the selected exponent vector produces s₁s₃, and the value estimate is the weighted sum of the resulting feature values.
Key Takeaways
- An OrderN polynomial feature is formed by choosing one exponent from 0 through N for every state variable and multiplying the powered terms.
- The exponent vector identifies one basis function, while the complete set of allowed vectors forms the basis.
- With d state variables, the complete OrderN basis contains (N + 1)^d functions.
- A linear value approximator combines feature values and weights through a weighted sum.
- Feature selection supplies prior domain knowledge; LSTD favors data efficiency at higher computational scaling cost, while nonlinear neural-network methods use backpropagation and stochastic-gradient-descent variations.
Key Takeaways
- Each polynomial basis function is determined by an exponent choice for every state variable.
- The exponent range 0 through N gives N + 1 choices per variable, so d variables produce (N + 1)^d functions.
- A linear value estimate is a weighted sum over the constructed features.
- Feature selection places prior domain knowledge into the representation and strongly affects learning and generalization.
- LSTD favors data efficiency at increased computational scaling cost, while nonlinear neural-network methods follow a different modeling direction.