Least-Squares TD

The previous lessons settled on semi-gradient TD(0) as the default linear learner: one gradient step per transition, $O (d)$ memory and $O (d)$ compute per step for $d$ weights. That frugality is also a weakness. Each example moves the weights only a little, and the example is then discarded, so the method needs a great many transitions to converge. This lesson makes the opposite tradeoff: spend more compute per step to extract more from each example.

Least-Squares TD stays parametric and linear but stops iterating: it accumulates the same matrices $A$ and $b$ that defined the TD fixed point and solves for $w = A^{- 1} b$ in closed form, the most data-efficient linear TD method there is. The complementary route to sample efficiency — abandoning the parametric form and storing the examples themselves — follows in the next lesson.

Least-Squares TD

Every method in the previous lesson spent compute per step proportional to the number of parameters. Recall the endpoint that linear semi-gradient TD(0) converges to. Under the on-policy distribution it settles at the TD fixed point, the weight vector where the expected update vanishes:¹

w_{TD} = A^{- 1} b, A ≐ E [x_{t} (x_{t} - γ x_{t + 1})^{⊤}], b ≐ E [R_{t + 1} x_{t}],

writing $x_{t} = x (S_{t})$ for the feature vector at time $t$ . TD(0) reaches $w_{TD}$ only in the limit, by taking many small steps that gradually average toward the expectations defining $A$ and $b$ . This is wasteful of data. If the fixed point is a solved linear system, why iterate at all? Estimate $A$ and $b$ from the data directly, then solve. Least-Squares TD (LSTD) takes this route. It forms the running sums

A_{t} ≐ k = 0 \sum t - 1 x_{k} (x_{k} - γ x_{k + 1})^{⊤} + ε I, b_{t} ≐ k = 0 \sum t - 1 R_{k + 1} x_{k},

where $I$ is the identity and $ε I$ , for a small $ε > 0$ , guarantees the sum is always invertible. These look like they ought to be divided by $t$ to be estimates of $A$ and $b$ ; as written they estimate $t A$ and $t b$ . But the extra $t$ cancels in the ratio, so LSTD estimates the fixed point as

w_{t} ≐ A_{t}^{- 1} b_{t} .

LSTD versus semi-gradient TD(0). TD(0) takes one small step per example and drifts toward the fixed point

A^{- 1} b

over many episodes; LSTD accumulates

A

and

b

and lands on the exact fixed point of the data seen so far every step.

A worked LSTD solve

For example, take a chain with three states carrying one-hot features $x (s_{1}) = [1, 0]^{⊤}$ , $x (s_{2}) = [0, 1]^{⊤}$ , and $x (terminal) = [0, 0]^{⊤}$ , discount $γ = 0.9$ , and two transitions in the data: $s_{1} \to s_{2}$ with reward $R = 2$ , and $s_{2} \to terminal$ with reward $R = 1$ . Take $ε = 0$ for a clean solve.

Each transition contributes the rank-one term $x_{k} (x_{k} - γ x_{k + 1})^{⊤}$ to $A$ and $R_{k + 1} x_{k}$ to $b$ . For the first transition, $x_{0} - γ x_{1} = [1, 0]^{⊤} - 0.9 [0, 1]^{⊤} = [1, - 0.9]^{⊤}$ , so

x_{0} (x_{0} - γ x_{1})^{⊤} = [10] [1 - 0.9] = [10 - 0.9 0], R_{1} x_{0} = 2 [10] = [20] .

For the second transition $x_{1} - γ x_{2} = [0, 1]^{⊤} - 0.9 [0, 0]^{⊤} = [0, 1]^{⊤}$ , so

x_{1} (x_{1} - γ x_{2})^{⊤} = [01] [01] = [0001], R_{2} x_{1} = 1 [01] = [01] .

Summing gives $A = [10 - 0.9 1]$ and $b = [2, 1]^{⊤}$ . Its inverse is $A^{- 1} = [10 0.9 1]$ , and the fixed point is

w = A^{- 1} b = [10 0.9 1] [21] = [2.9 1] .

So $\overset{v}{^} (s_{2}) = w_{2} = 1$ (its return is the single reward $1$ ) and $\overset{v}{^} (s_{1}) = w_{1} = 2.9 = 2 + 0.9 \cdot 1$ — the reward $2$ plus the discounted value of $s_{2}$ , exactly the Bellman-consistent values. Semi-gradient TD(0) would have reached the same $[2.9, 1]^{⊤}$ only after many passes; LSTD read it off the two transitions directly.

The two-transition chain of the worked LSTD solve. State

s_{1}

(feature

[1, 0]

) rewards

+ 2

into

s_{2}

(feature

[0, 1]

), which rewards

+ 1

into the terminal (feature

[0, 0]

). With

γ = 0.9

LSTD returns

w_{2} = 1

and

w_{1} = 2 + 0.9 \cdot 1 = 2.9

, the exact Bellman-consistent values.

The Sherman-Morrison incremental inverse

Written naively, LSTD looks like it grows more expensive as $t$ grows, and forming $A_{t}^{- 1}$ from scratch is $O (d^{3})$ — the cost of inverting a general $d \times d$ matrix. An incremental update resolves both problems. The accumulator $A_{t}$ is a running sum of outer products (each term $x_{k} (x_{k} - γ x_{k + 1})^{⊤}$ is a column vector times a row vector, a rank-one $d \times d$ matrix). A matrix of that special form — a previous matrix plus a rank-one update — has an inverse that can be updated directly, without ever inverting anything, by the Sherman-Morrison formula:¹

A_{t}^{- 1} = (A_{t - 1} + x_{t} (x_{t} - γ x_{t + 1})^{⊤})^{- 1} = A_{t - 1}^{- 1} - \frac{A _{t - 1}^{- 1} x _{t} ( x _{t} - γ x _{t + 1} ) ^{⊤} A _{t - 1}^{- 1}}{1 + ( x _{t} - γ x _{t + 1} ) ^{⊤} A _{t - 1}^{- 1} x _{t}},

for $t > 0$ , initialized with $A_{0}^{- 1} = ε^{- 1} I$ . The formula is simpler than it looks: the numerator is an outer product of two $d$ -vectors, and the denominator is a scalar. Every operation is a matrix-vector or vector-vector product — $O (d^{2})$ , never $O (d^{3})$ . So LSTD stores the inverse matrix $A_{t}^{- 1}$ (itself $O (d^{2})$ memory), maintains it with one Sherman-Morrison update per step, and reads off $w_{t} = A_{t}^{- 1} b_{t}$ — all in $O (d^{2})$ time and memory per step.

One LSTD step. The new transition contributes a rank-one outer product to

A

; Sherman-Morrison folds that update into the stored inverse

A^{- 1}

using only matrix-vector products (never a fresh inversion), and

w = A^{- 1} b

is read off directly.

The full procedure keeps $A^{- 1}$ and $b$ and updates both every step:

Algorithm:

\textsc{LSTD}

— batch linear prediction of

\hat v = \mathbf{w}^\top\mathbf{x}(\cdot) \approx v_\pi

1
input: feature map $\mathbf{x}$ with $\mathbf{x}(\text{terminal}) = \mathbf{0}$ , small $\varepsilon > 0$
2
$\widehat{\mathbf{A}}^{-1} \gets \varepsilon^{-1}\mathbf{I}$
a $d \times d$ matrix
3
$\widehat{\mathbf{b}} \gets \mathbf{0}$
a $d$ -vector
4
for each episode do
5
initialize $S$
6
$\mathbf{x} \gets \mathbf{x}(S)$
7
repeat
8
choose $A \sim \pi(\cdot \mid S)$ , take it, observe $R$ , $S'$
9
$\mathbf{x}' \gets \mathbf{x}(S')$
10
$\mathbf{v} \gets (\widehat{\mathbf{A}}^{-1})^\top(\mathbf{x} - \gamma\mathbf{x}')$
11
$\widehat{\mathbf{A}}^{-1} \gets \widehat{\mathbf{A}}^{-1} - (\widehat{\mathbf{A}}^{-1}\mathbf{x})\,\mathbf{v}^\top / (1 + \mathbf{v}^\top\mathbf{x})$
12
$\widehat{\mathbf{b}} \gets \widehat{\mathbf{b}} + R\,\mathbf{x}$
13
$\mathbf{w} \gets \widehat{\mathbf{A}}^{-1}\widehat{\mathbf{b}}$
14
$S \gets S'$
15
$\mathbf{x} \gets \mathbf{x}'$
16
until $S$ is terminal

What the quadratic cost buys, and what it costs

LSTD is the most data-efficient linear TD(0) method — it extracts the fixed point from the data as fast as the data can define it — but $O (d^{2})$ is still substantially more than the $O (d)$ of semi-gradient TD. Whether the greater data efficiency is worth the expense depends on how large $d$ is, how costly data is relative to compute, and the cost of the rest of the system. With $d$ in the thousands, $O (d^{2})$ can be prohibitive, and semi-gradient TD with a good step size wins on wall-clock; with $d$ small and data expensive to gather, LSTD's sample efficiency justifies the cost.

LSTD also has no step-size parameter, which is sometimes cited as an advantage but is overstated. It does still require $ε$ : set too small, the sequence of inverses can vary wildly; set too large, learning is slowed. More consequentially, lacking a step size means LSTD never forgets. That is fine for a fixed policy $π$ , but in control — where generalized policy iteration keeps changing the target policy — an approximation that weights all past data equally is a liability. The data from an abandoned policy should fade, and LSTD has no mechanism to fade it. In control applications LSTD must be combined with some means of inducing forgetting, which moots the supposed advantage of needing no step size.¹

	Semi-gradient TD(0)	LSTD
Update	one small SGD step per example	recompute exact fixed point of data so far
Compute / step	$O (d)$	$O (d^{2})$
Memory	$O (d)$	$O (d^{2})$ (holds $A^{- 1}$ )
Data efficiency	needs many examples	most efficient linear TD method
Step size	needs $α$ (must be tuned)	none, but needs $ε$
Forgetting	built in (step size)	none — bad for changing $π$

Least-squares control

LSTD as presented evaluates a fixed policy. The natural next question — how to do control with the same data efficiency — was answered by least-squares policy iteration (Lagoudakis and Parr 2003, JMLR), which Sutton and Barto cite as the extension of least-squares methods to control. LSPI runs policy iteration on a batch of transitions: an inner routine, LSTDQ, solves the LSTD fixed point for the action-value function $\overset{q}{^} (s, a, w) = w^{⊤} x (s, a)$ of the current policy directly from the stored data, then the policy is made greedy with respect to that $\overset{q}{^}$ , and the two steps repeat over the same fixed batch. Because every iteration reuses all the data and never touches the environment again, LSPI is fully off-line and among the most sample-efficient linear control methods — the control counterpart of LSTD's prediction efficiency, at the same $O (d^{2})$ cost.²

Least-squares policy iteration. LSTDQ solves the action-value fixed point

w = A^{- 1} b

from a fixed batch of transitions; the policy is made greedy in the resulting

\overset{q}{^}

; the two steps alternate over the same batch until the policy stops changing, never re-sampling the environment.

Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), §9.8 — Least-Squares TD: the TD fixed point $w_{TD} = A^{- 1} b$ with $A = E [x_{t} (x_{t} - γ x_{t + 1})^{⊤}]$ and $b = E [R_{t + 1} x_{t}]$ ; the LSTD estimates (9.20)–(9.21) with the $ε I$ regularizer; the $O (d^{2})$ Sherman-Morrison incremental inverse (9.22); the LSTD algorithm box; and the discussion of the $O (d^{2})$ versus $O (d)$ tradeoff, the $ε$ parameter, and the lack of forgetting in control. LSTD is due to Bradtke and Barto (1996); the incremental inverse to Sherman and Morrison (1949). ↩ ↩² ↩³
Lagoudakis and Parr (2003), Least-Squares Policy Iteration, Journal of Machine Learning Research 4: extends least-squares TD to control by running policy iteration over a fixed batch of transitions, with an inner LSTDQ step that solves the LSTD fixed point for the action-value function of the current policy. Cited by Sutton & Barto (§9.8, Bibliographical Remarks) as the extension of least-squares methods to control. ↩

Least-Squares TD

A worked LSTD solve

The Sherman-Morrison incremental inverse

What the quadratic cost buys, and what it costs

Least-squares control

Footnotes