Linear Function Approximation

In tabular reinforcement learning, the value function $v_\pi(s)$ is stored as one independent number per state. Function approximation instead posits a parametric family of functions $\hat v(\cdot, \mathbf w)$, indexed by a weight vector $\mathbf w \in \mathbb R^d$, and asks the learning algorithm to find good weights rather than good table entries. Linear function approximation is the special case where the approximation is linear in the weights:

where $\mathbf x(s) = (x_1(s), \dots, x_d(s))^\top$ is a feature vector representing state $s$. The features are fixed, hand-designed (or otherwise pre-computed) functions of the raw state; only the weights $\mathbf w$ are learned. This is distinct from nonlinear approximators such as neural networks, where the mapping from state to features is itself learned jointly with the output weights. The appeal of linearity is twofold. First, the approximation's gradient with respect to the weights is simply the feature vector itself,

independent of $\mathbf w$. This makes gradient-based updates trivial to write down and analyze. Second, because the objective (mean squared value error, weighted by the on-policy state distribution) is a quadratic function of $\mathbf w$ when the target is fixed, the associated optimization landscape has a single global optimum with no spurious local minima — a property that is lost the moment the features themselves are learned nonlinearly. Feature construction is where domain knowledge enters. Classic choices include polynomial features (products of state coordinates up to some degree), tile coding (a form of coarse coding using multiple overlapping binned grids, each grid shifted slightly from the others), radial basis functions (Gaussian bumps centered at prototype states), and the Fourier basis (cosine features at increasing frequencies). Each induces a different notion of "similarity" between states — two states with similar feature vectors will necessarily be assigned similar values, whether or not that similarity is appropriate for the task. This is the central tradeoff of linear approximation: it is exactly as good as the features fed into it, and no amount of clever weight-tuning can compensate for a representation that cannot express the true value function.

The learning target for prediction under a fixed policy $\pi$ is to find $\mathbf w$ minimizing the Mean Squared Value Error,

where $\mu(s)$ is the fraction of time spent in state $s$ under the behavior policy (the on-policy distribution when learning on-policy). Since $v_\pi$ is unknown, we cannot compute this loss directly; instead we use sampled transitions and bootstrap estimates, exactly as in tabular TD(0), but now update a shared weight vector using stochastic gradient descent.

Monte Carlo with linear approximation. If we had the true return $G_t$ as an unbiased target, the update is ordinary stochastic gradient descent on squared error:

This is a true gradient step because $G_t$ does not depend on $\mathbf w$.

TD(0) with linear approximation. TD(0) instead bootstraps, using $R_{t+1} + \gamma \hat v(S_{t+1}, \mathbf w)$ as the target. Crucially, this target does depend on $\mathbf w$, but the standard algorithm ignores that dependency and treats the target as fixed when differentiating — hence the name semi-gradient TD(0):

This is not gradient descent on any fixed objective (it is a semi-gradient), yet under on-policy sampling and diminishing step sizes it converges — to a specific, well-understood fixed point derived below, not to the minimizer of $\overline{VE}$ itself. ``` Algorithm: Semi-Gradient TD(0) for Policy Evaluation with Linear Function Approximation Input: policy π to evaluate feature function x : S → R^d step size α ∈ (0, 1], discount factor γ ∈ [0, 1] Initialize weight vector w ∈ R^d arbitrarily (e.g., all zeros) for each episode: initialize S (first state of episode) while S is not terminal: A ← action given by π(·|S) take action A, observe reward R and next state S' if S' is terminal: target ← R # no bootstrap term else: target ← R + γ dot(w, x(S')) δ ← target − dot(w, x(S)) # TD error w ← w + α δ x(S) # semi-gradient update S ← S' return w ``` The pseudocode is deliberately close to tabular TD(0): the table lookup `V[S]` is replaced by `dot(w, x(S))`, and the tabular update — which changes exactly one table entry — is replaced by an update that nudges every* weight touched by the nonzero components of $\mathbf x(S)$. If features are sparse (e.g., tile coding, where a fixed small number of tiles are active per state), this update touches only $O(k)$ weights per step, where $k$ is the number of active features, regardless of $d$. Extending to control (estimating $q_\pi$ or an optimal policy) replaces $\hat v(s,\mathbf w)$ with $\hat q(s,a,\mathbf w) = \mathbf w^\top \mathbf x(s,a)$ and follows the same semi-gradient recipe for SARSA or Q-learning, using an $\varepsilon$-greedy policy derived from $\hat q$ for action selection. The weight update becomes $\mathbf w \leftarrow \mathbf w + \alpha \delta_t\, \mathbf x(S_t, A_t)$ with $\delta_t$ built from either the SARSA target (on-policy) or the max-Q target (off-policy, and hence more fragile under function approximation).

Time and space complexity. Storing the weight vector requires $O(d)$ space, versus $O(|\mathcal S|)$ for a table — decisive when $|\mathcal S|$ is combinatorially large or continuous, since $d$ is chosen by the designer independent of state-space size. Each TD(0) step computes $\mathbf x(S_t)$, $\mathbf x(S_{t+1})$, two dot products, and an update — all $O(d)$ in the dense case. With sparse binary features such as tile coding, where exactly $k$ features are active per state (a small constant, e.g. $k=8$ tiles), the dot products and updates cost $O(k)$ per step, independent of $d$, because only the active components need be touched. This is why tile coding scales to $d$ in the millions in practice: memory is dominated by the weight array, but per-step compute stays bounded by $k$.

Correctness for on-policy linear TD(0). Unlike the tabular case, linear TD(0) does not converge to the true value function $v_\pi$ in general, because $v_\pi$ may not lie in the span of the chosen features. Instead, on-policy linear TD(0) with diminishing step sizes converges (with probability 1, under standard stochastic-approximation conditions on the step-size sequence and an irreducible, aperiodic Markov chain induced by $\pi$) to the unique fixed point $\mathbf w_{TD}$ satisfying

where

A key structural fact — proved by Tsitsiklis and Van Roy (1997) — is that under the on-policy distribution $\mu$, the matrix $\mathbf A$ is positive definite (in the relevant subspace), which guarantees this linear system has a unique solution and that the associated ODE (the expected direction of the stochastic update) is globally stable. The proof sketch: $\mathbf A = \mathbf X^\top D (I - \gamma P) \mathbf X$ where $\mathbf X$ has rows $\mathbf x(s)^\top$, $D = \mathrm{diag}(\mu)$, and $P$ is the policy's transition matrix; a classical result shows $D(I-\gamma P)$ is positive definite whenever $\mu$ is the stationary distribution of $P$, and this property is inherited by $\mathbf X^\top D(I-\gamma P)\mathbf X$ for any full-rank feature matrix $\mathbf X$. Positive definiteness is precisely what fails when the sampling distribution is off-policy, which is the root cause of divergence examples in the deadly triad.

Error bound. The fixed point $\mathbf w_{TD}$ is not the projection minimizer of $\overline{VE}$, but it is provably close to it:

That is, TD's fixed-point error is at most a factor $\frac{1}{1-\gamma}$ worse than the best possible linear approximation of $v_\pi$ under the chosen features — a guarantee unavailable to naive bootstrapping schemes without this structural analysis. As $\gamma \to 1$ this bound loosens considerably, reflecting the well-known difficulty of long-horizon credit assignment with bootstrapping.

Honest tradeoffs. These guarantees hinge on three things simultaneously: (1) on-policy sampling, (2) linear architecture, (3) the specific semi-gradient TD update. Change any one — e.g., train off-policy, or use a nonlinear network, or use a different bootstrapping scheme — and the clean positive-definiteness argument no longer applies; convergence must be re-established (or may provably fail), which is exactly the subject of the deadly triad and of corrective algorithms like gradient-TD (GTD2, TDC).

Consider a tiny 5-state random walk: states $S_1, \dots, S_5$ in a line, terminal states at both ends (reward $0$ on the left exit, reward $1$ on the right exit), and equiprobable left/right moves — the classic tabular TD(0) benchmark, now equipped with linear features. Use a simple aggregation feature scheme: group the five states into two feature "bins" for illustration —

This deliberately imperfect feature set cannot represent the true values exactly (true values under random walk dynamics are $\tfrac16,\tfrac26,\tfrac36,\tfrac46,\tfrac56$), which lets us see the semi-gradient update converge to a biased but bounded solution rather than the exact answer. Initialize $\mathbf w = (0,0)$, $\alpha = 0.1$, $\gamma = 1$. Trace one episode $S_3 \to S_4 \to S_5 \to \text{terminal (right, reward 1)}$:

After this single episode $\mathbf w = (0, 0.1)$. Note that step 3's update changed $w_2$ only, because $\mathbf x(S_5) = (0,1)$ has a zero first component — exactly the sparse-update behavior predicted by the complexity analysis. On the next episode, suppose the walk visits $S_3 \to S_2 \to S_1 \to \text{terminal (left, reward 0)}$:

Over many more episodes, $\mathbf w$ converges toward the fixed point $\mathbf w_{TD}$ solving $\mathbf A \mathbf w = \mathbf b$ for this feature map and Markov chain — a pair of values that best fit each aggregated bin, biased slightly by the bootstrapping and averaging inherent to TD, but with error provably within the $\frac{1}{1-\gamma}$ factor of the best two-parameter linear fit to the true random-walk values. This demonstrates concretely how coarse features force nearby states to share value estimates ($S_1$ and $S_2$ are forced identical, likewise $S_4$ and $S_5$), trading exactness for a drastically smaller parameter count — 2 weights instead of 5 table entries — and this ratio only becomes more favorable as state spaces grow.

Linear function approximation underlies decades of applied reinforcement learning before the deep learning era, and remains the workhorse whenever interpretability, sample efficiency, or provable convergence matter more than raw representational capacity. Classic large-scale successes include Tesauro's TD-Gammon-style value learning (originally with neural nets, but linear variants with hand-designed backgammon features perform competitively), robotic control with tile-coded state spaces (as in early Sarsa and Q-learning applications to mountain-car and acrobot benchmarks), and industrial process control where engineers can hand-design physically meaningful features (position, velocity, error terms) and need auditable, stable weight updates. Linear methods with sparse coarse-coded features (tile coding, radial basis functions) remain standard baselines in continuous-control benchmarking because they train in milliseconds and their convergence properties are mathematically characterized, unlike black-box deep networks. The positive-definiteness argument developed here for on-policy linear TD(0) is also the conceptual seed for gradient-TD methods and later analyses of semi-gradient methods with function approximation more broadly, and the divergence risks identified in the linear, off-policy setting directly foreshadow the deadly triad, the central cautionary framework used to explain instability in deep reinforcement learning systems such as DQN (which needed target networks and experience replay specifically to blunt these effects).

Ask the tutor: How does the positive-definiteness of matrix A break down specifically under off-policy sampling, and how do gradient-TD methods like TDC restore convergence?