Value-Based DRL: Function Approximation #

Tabular methods store a separate value for every state or state-action pair. This becomes impractical when the state space is very large, continuous or represented by raw observations. Function approximation replaces this table with a parameterised function that can learn from observed states, generalise to related states and predict values for states not seen during training.

Course Content covered in this module:

• Function approximation
• Feature Construction for Linear Methods:
  • Tile Coding
  • Asymmetric Tile Coding
• Linear function approximation
• Semi-Gradient TD methods
• Off-policy function approximation and TD divergence
• TD-Gammon

Learning Objectives #

By the end of this module, you should be able to:

• explain why tabular value functions fail to scale;
• distinguish a state, its feature vector and the approximator’s parameters;
• derive gradient Monte Carlo and semi-gradient TD(0) updates;
• apply linear value-function approximation to a numerical example;
• explain coarse coding, tile coding and asymmetric tilings;
• identify the source of the term semi-gradient;
• explain why off-policy TD with function approximation may diverge; and
• connect classical function approximation to deep value-based methods.

1. Why Tabular Learning Is Not Enough ☆ #

In a table, learning about one state changes only that state’s entry. A nearby or perceptually similar state receives no benefit unless it is visited and updated separately.

This causes two practical problems:

• coverage: there may be too many states to visit during training;
• storage: there may be too many values to hold in memory.

For example, two Pac-Man screens may differ by only one grid position. A tabular agent treats them as unrelated keys, whereas an approximator can represent their common structure through shared features and weights.

flowchart TD
    A["Observed state"] --> B["Feature representation"]
    B --> C["Shared parameters"]
    C --> D["Estimated value"]
    C --> E["Generalisation to similar states"]

    style A fill:#E1F5FE,stroke:#1E88E5
    style B fill:#BBDEFB,stroke:#1E88E5
    style C fill:#90CAF9,stroke:#1E88E5
    style D fill:#E1F5FE,stroke:#1E88E5
    style E fill:#E1F5FE,stroke:#1E88E5

More training does not change the basic limitation of a table. It may fill more entries, but it still does not naturally share information between related states.

2. Parameterised Value Functions ☆ #

Let a differentiable function approximate the state value:

Here:

• \( s \) is the current state;
• \( \mathbf{x}(s) \) is a feature vector describing that state;
• \( \mathbf{w} \) is the vector of learnable parameters; and
• \( \hat v(s,\mathbf w) \) is the estimated value.

The same parameter vector is used for every state. Consequently, changing one weight can change the predictions of many states.

An action-value approximator similarly uses both state and action:

State-value approximation supports prediction. Action-value approximation is normally required for model-free control, because the agent must compare the values of available actions.

3. The Prediction Objective #

A common objective is the mean-squared value error under a state distribution \( \mu \) :

The distribution \( \mu(s) \) determines which states matter most. Frequently visited states receive more weight when \( \mu \) is the on-policy state distribution.

The true value \( v_\pi(s) \) is usually unknown. Learning therefore uses a sampled target \( U_t \) in its place.

For a differentiable approximator, the general stochastic-gradient update is:

It has three factors:

4. Gradient Monte Carlo ☆ #

Monte Carlo prediction uses the complete sampled return as its target:

The update becomes:

Because \( G_t \) is an unbiased sample of \( v_\pi(S_t) \) under the policy, this is a true stochastic-gradient method for the squared prediction objective. Its familiar Monte Carlo limitation remains: the update must wait for the return to become available.

5. Linear Function Approximation ☆ #

In a linear approximator, the estimated value is a weighted sum of features:

Its gradient is especially simple:

Therefore, the generic update reduces to:

Only features active in the current state receive a direct update. However, those weights are shared, so every other state containing the same features can acquire a different prediction.

Worked Example: Generalisation Through Shared Weights ☆ #

Suppose:

• \( \mathbf{x}(S_t)=[2,2,1]^{\mathsf T} \) ;
• \( \mathbf{w}_t=[0,0,0]^{\mathsf T} \) ;
• target \( U_t=10 \) ; and
• \( \alpha=0.1 \) .

The current estimate is zero, so:

Now consider an unvisited but related state with \( \mathbf{x}(S')=[2,4,1]^{\mathsf T} \) . Its value can already be predicted:

The number \( 13 \) is not a memorised table entry. It arises because the newly learned parameters are reused for the new feature vector.

6. Semi-Gradient TD(0) ☆ #

TD(0) uses a bootstrapped target:

Define the approximate TD error:

The semi-gradient TD(0) update is:

For a linear approximator:

Why Is It Called a Semi-Gradient? #

The TD target itself contains \( \hat v(S_{t+1},\mathbf w_t) \) , which depends on the same parameters being updated. A full derivative of the squared TD error would differentiate through both the current estimate and this target.

Semi-gradient TD deliberately treats the target as if it were constant and differentiates only \( \hat v(S_t,\mathbf w_t) \) . It therefore follows only part of the complete gradient.

The word semi does not mean that half the data or half the features are used. It means that the derivative through the bootstrapped target is omitted.

Why Use It? #

Semi-gradient methods remain important because they:

• learn continually and online;
• do not need to wait until an episode ends;
• work with continuing tasks;
• are computationally efficient; and
• converge reliably in important on-policy linear cases under standard assumptions.

They do not possess the same general objective-descent guarantee as gradient Monte Carlo because the bootstrapped target is biased and moves with the parameters.

7. Semi-Gradient n-Step TD #

The n-step return from the previous module can also serve as the target:

The parameter update is:

The conceptual change from tabular n-step TD is small: update a weight vector instead of one table entry.

8. Feature Construction ☆ #

The approximator can generalise only through the representation supplied to it. Good features make relevant states similar; poor features may merge states that require different values or separate states that should share information.

Coarse Coding #

Coarse coding places overlapping receptive fields over a continuous state space.

• A feature is \( 1 \) when the state lies inside its receptive field.
• It is \( 0 \) otherwise.
• A single state activates several overlapping features.
• Updating that state changes all corresponding weights.

Nearby states share some active regions, which produces smooth generalisation.

Tile Coding #

Tile coding overlays several offset grids called tilings. Each state activates one tile in each tiling.

flowchart TD
    A["Continuous state"] --> B["Several offset tilings"]
    B --> C["One active tile per tiling"]
    C --> D["Sparse binary feature vector"]
    D --> E["Linear value estimate"]

    style A fill:#E1F5FE,stroke:#1E88E5
    style B fill:#BBDEFB,stroke:#1E88E5
    style C fill:#90CAF9,stroke:#1E88E5
    style D fill:#BBDEFB,stroke:#1E88E5
    style E fill:#E1F5FE,stroke:#1E88E5

The representation is sparse, quick to compute and capable of local generalisation. The number and width of the tilings control resolution and generalisation.

Asymmetric Tile Coding #

Ordinary symmetric tiles generalise by similar amounts in each dimension. Asymmetric tilings use different shapes, widths or offsets across dimensions when the task requires different resolutions.

For example, a control problem may require very fine resolution for velocity but coarser resolution for position. Asymmetric tiles encode that preference directly.

Other Feature Constructions #

Radial basis functions, Fourier bases and polynomial features provide other fixed representations. Their shared limitation is that feature design may require domain knowledge. Deep neural networks reduce this dependence by learning representations jointly with the value estimate.

9. Off-Policy Function Approximation and TD Divergence ☆ #

Function approximation is not automatically stable. A particularly dangerous combination contains three elements:

flowchart TD
    A["Function approximation"] --> D["Deadly triad"]
    B["Bootstrapping"] --> D
    C["Off-policy learning"] --> D
    D --> E["Possible instability or divergence"]

    style A fill:#E1F5FE,stroke:#1E88E5
    style B fill:#E1F5FE,stroke:#1E88E5
    style C fill:#E1F5FE,stroke:#1E88E5
    style D fill:#90CAF9,stroke:#1E88E5
    style E fill:#FFCDD2,stroke:#D32F2F

• Function approximation couples the values of different states through shared parameters.
• Bootstrapping updates an estimate towards another estimate.
• Off-policy learning learns about a target policy from data generated by a different behaviour policy.

Together, the update can move one estimate, alter many other estimates and repeatedly chase changing targets under a distribution different from the target policy’s distribution. In some problems, the weights grow rather than converge—even with a linear approximator.

Divergence is a possibility, not an assertion that every off-policy approximation method fails. Stability depends on the algorithm, representation, sampling distribution and step size.

10. TD-Gammon: Why Function Approximation Matters #

TD-Gammon used a neural network and temporal-difference learning to estimate positions in backgammon. It illustrated two central ideas:

• the value function can be represented by a nonlinear approximator instead of a table; and
• self-play can produce training experience without labelled optimal moves.

Its importance is conceptual: value approximation allows TD learning to operate in a state space where enumerating and learning every position separately is infeasible.

11. From Linear Approximation to Deep Q-Learning #

A neural network follows the same broad pattern as a linear approximator:

1. receive a state representation;
2. produce an estimated value or action values;
3. compare the estimate with a learning target;
4. back-propagate the error to update shared parameters.

The difference is representational power. A linear method combines supplied features, while a deep network can learn intermediate features from inputs such as image pixels.

For action selection, a value-based agent approximates \( q(s,a) \) and can act greedily or \( \varepsilon \) -greedily. Deep Q-learning develops this idea further, but its architecture, replay memory, target network and stability mechanisms belong to the next module.

Gradient Monte Carlo versus Semi-Gradient TD #

Common Mistakes ☆ #

• The feature vector ( \mathbf{x}(s) )

describes a state; the weight vector ( \mathbf w )

is learned.

• Function approximation does not mean only neural networks; linear approximators are function approximators too.
• A state-value estimate alone does not directly select an action in a model-free control problem.
• Semi-gradient TD does not differentiate through the bootstrapped target.
• Generalisation can help or harm: unrelated states should not be forced to share inappropriate features.
• Linear approximation can still diverge under the deadly triad.
• Tile coding creates features; it is not itself a reinforcement learning control algorithm.

Practice Questions #

1. Why does a tabular value function not generalise to an unseen state?
2. Distinguish \( s \) , \( \mathbf{x}(s) \) and \( \mathbf w \) .
3. Derive the gradient Monte Carlo update from a squared-error objective.
4. For a supplied feature vector, target and step size, calculate one linear weight update.
5. Why is TD(0) with function approximation called a semi-gradient method?
6. Compare coarse coding with tile coding.
7. Why might asymmetric tilings be useful when state dimensions have different sensitivities?
8. Name the three parts of the deadly triad and explain their interaction.
9. Why is \( \hat q(s,a,\mathbf w) \) more directly useful than \( \hat v(s,\mathbf w) \) for model-free control?
10. Explain how function approximation creates the bridge from tabular Q-learning to DQN.

Key Takeaways ☆ #

• Function approximation replaces independent table entries with shared parameters.
• Shared parameters enable learning, generalisation and prediction across related states.
• Gradient Monte Carlo uses an unbiased complete-return target.
• Semi-gradient TD treats its bootstrapped target as constant during differentiation.
• Linear approximation makes the update direction equal to the active feature vector.
• Coarse coding and tile coding turn continuous states into overlapping features.
• Function approximation, bootstrapping and off-policy learning can produce divergence when combined.
• Deep value-based learning extends the same parameter-update idea with learned nonlinear features.

Checklist #

• I can explain why tabular methods do not scale.
• I can write the generic stochastic-gradient value update.
• I can apply the linear function-approximation update.
• I can derive and explain semi-gradient TD(0).
• I can distinguish weights from features.
• I can explain coarse coding, tile coding and asymmetric tilings.
• I can identify the deadly triad.
• I can explain how this material leads towards DQN.

References #

1. Sutton and Barto, Reinforcement Learning: An Introduction, Second Edition, Chapters 9 and 11.
2. Official Course Content for Value-Based DRL Methods.
3. Supplied material on on-policy prediction with approximation.

Home | Deep Reinforcement Learning