Linear Function Approximation

Imagine estimating the value of every possible position in a robot’s world or every configuration of a game. A table with one entry per state works only for tiny problems. Linear function approximation gives the agent a compact way to make sensible estimates about states it has not seen before.

How the estimate is built

Instead of storing a separate value for each state, the agent describes a state with a vector of features, such as distance to a goal, current speed, or whether an obstacle is nearby. It then predicts a value by taking a weighted sum:

v̂(s) = w₁x₁(s) + w₂x₂(s) + ... + wₙxₙ(s)

Here, the features x(s) describe the state and the learned weights w say how strongly each feature matters. “Linear” refers to being linear in the weights; the features themselves can encode quite rich transformations of the raw state.

Learning from reward signals

After a transition, a method such as semi-gradient TD learning adjusts the weights so the current prediction moves toward a target based on reward and a later estimate. A useful state feature therefore influences many related states at once. Common feature choices include:

Tile coding, which splits continuous inputs into overlapping regions and is a classic choice for control tasks.
Radial basis features, which activate most strongly near selected prototype states.
Hand-designed features, such as a car’s position and velocity in Mountain Car.

Why it matters in practice

This is one of reinforcement learning’s most dependable ways to generalise without a neural network. In a Gymnasium control environment, an agent can learn that moving toward the goal is valuable across nearby positions, rather than relearning that fact for each exact position. Its behaviour is easier to inspect than a deep model: a surprising weight can reveal a misleading feature or a reward loophole. But representation still determines success. If the features omit a crucial distinction—say, whether a robot is moving toward or away from a ledge—no choice of linear weights can recover it. With bootstrapped methods such as TD or Q-learning, unsuitable features, aggressive learning rates, and off-policy updates can also produce unstable or divergent estimates. Linear approximation is simple, fast, and mathematically well understood, but it can only express patterns its features make visible.

Linear function approximation represents a value function, action-value function, or policy as a weighted sum of input features: \(f(x)=\mathbf{w}^{\top}\boldsymbol{\phi}(x)\). Learning adjusts the weights from reward-derived updates while shared features generalise estimates across states or actions. It makes reinforcement learning tractable in large or continuous spaces and supports efficient online learning, though performance depends critically on the chosen feature representation.

Imagine judging houses by a few simple clues: size, number of bedrooms, and distance from town. You do not need to memorize the price of every house; you learn how those clues usually relate to price.

Linear function approximation gives a learning system a similarly simple way to make useful guesses. Instead of treating every situation as completely new, it notices familiar features and uses them to estimate which choices are likely to pay off. This matters when there are far too many possible situations to learn one by one—such as a robot moving through countless positions. It helps the system carry lessons from past experience into new, similar situations.