---
title: "Least-Squares TD"
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 11
order: 311
summary: >
  Semi-gradient TD spends one cheap step per example and needs many examples;
  this lesson makes the opposite tradeoff. Least-Squares TD (LSTD)
  accumulates the matrices $\mathbf{A}$ and $\mathbf{b}$ and solves the TD fixed
  point $\mathbf{w} = \mathbf{A}^{-1}\mathbf{b}$ directly, using the
  Sherman-Morrison identity to maintain the inverse in $O(d^2)$ — the most
  data-efficient linear TD method, at a quadratic cost. We work a solve by hand,
  weigh the quadratic cost against semi-gradient TD's cheap steps, and note
  that LSTD never forgets — a problem in control, where least-squares policy
  iteration is the natural extension.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 9 — On-policy Prediction with Approximation; §9.8 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 $\mathbf{A}$ and $\mathbf{b}$ that defined the TD fixed point and
solves for $\mathbf{w} = \mathbf{A}^{-1}\mathbf{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](/reinforcement-learning/approximation/memory-and-kernel-methods).

## 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:[^sb-lstd]

$$
\mathbf{w}_{\mathrm{TD}} \;=\; \mathbf{A}^{-1}\mathbf{b},
\qquad
\mathbf{A} \;\doteq\; \mathbb{E}\!\big[\mathbf{x}_t(\mathbf{x}_t - \gamma\mathbf{x}_{t+1})^\top\big],
\qquad
\mathbf{b} \;\doteq\; \mathbb{E}\!\big[R_{t+1}\mathbf{x}_t\big],
$$

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

$$
\widehat{\mathbf{A}}_t \;\doteq\; \sum_{k=0}^{t-1} \mathbf{x}_k(\mathbf{x}_k - \gamma\mathbf{x}_{k+1})^\top \;+\; \varepsilon\mathbf{I},
\qquad
\widehat{\mathbf{b}}_t \;\doteq\; \sum_{k=0}^{t-1} R_{k+1}\mathbf{x}_k,
$$

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

$$
\mathbf{w}_t \;\doteq\; \widehat{\mathbf{A}}_t^{-1}\,\widehat{\mathbf{b}}_t.
$$

$$
% caption: LSTD versus semi-gradient TD(0). TD(0) takes one small step per example
% and drifts toward the fixed point $\mathbf{A}^{-1}\mathbf{b}$ over many episodes;
% LSTD accumulates $\widehat{\mathbf{A}}$ and $\widehat{\mathbf{b}}$ and lands on
% the exact fixed point of the data seen so far every step.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % error-vs-examples axes
  \draw[->, black] (0,0) -- (7.4,0) node[anchor=north east, font=\scriptsize] {examples seen};
  \draw[->, black] (0,0) -- (0,3.4) node[anchor=south east, font=\scriptsize] {error};
  % TD(0): slow decay
  \draw[red, thick] plot[domain=0.1:7.0, samples=60] (\x, {2.9*exp(-0.35*\x)+0.28});
  \node[red, anchor=west, font=\scriptsize] at (7.05,0.5) {TD(0)};
  % LSTD: fast decay
  \draw[acc, thick] plot[domain=0.1:7.0, samples=60] (\x, {2.9*exp(-1.4*\x)+0.28});
  \node[acc, anchor=west, font=\scriptsize] at (7.05,0.32) {LSTD};
  % fixed-point floor
  \draw[black, dashed] (0,0.28) -- (7.0,0.28);
  \node[anchor=south west, font=\scriptsize] at (0.1,0.3) {f\/ixed-point error};
\end{tikzpicture}
$$

> **Definition (Least-Squares TD).** The batch linear-prediction method that
> accumulates $\widehat{\mathbf{A}}_t = \sum_k \mathbf{x}_k(\mathbf{x}_k -
> \gamma\mathbf{x}_{k+1})^\top + \varepsilon\mathbf{I}$ and $\widehat{\mathbf{b}}_t
> = \sum_k R_{k+1}\mathbf{x}_k$ and reports $\mathbf{w}_t =
> \widehat{\mathbf{A}}_t^{-1}\widehat{\mathbf{b}}_t$, the exact TD fixed point of
> the data collected so far. It is the most data-efficient form of linear TD(0),
> and the most expensive.

### A worked LSTD solve

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

Each transition contributes the rank-one term $\mathbf{x}_k(\mathbf{x}_k -
\gamma\mathbf{x}_{k+1})^\top$ to $\widehat{\mathbf{A}}$ and $R_{k+1}\mathbf{x}_k$ to
$\widehat{\mathbf{b}}$. For the first transition,
$\mathbf{x}_0 - \gamma\mathbf{x}_1 = [1,0]^\top - 0.9\,[0,1]^\top = [1, -0.9]^\top$, so

$$
\mathbf{x}_0(\mathbf{x}_0 - \gamma\mathbf{x}_1)^\top = \begin{bmatrix}1\\0\end{bmatrix}\begin{bmatrix}1 & -0.9\end{bmatrix} = \begin{bmatrix}1 & -0.9\\0 & 0\end{bmatrix},
\qquad
R_1\mathbf{x}_0 = 2\begin{bmatrix}1\\0\end{bmatrix} = \begin{bmatrix}2\\0\end{bmatrix}.
$$

For the second transition $\mathbf{x}_1 - \gamma\mathbf{x}_2 = [0,1]^\top - 0.9\,[0,0]^\top = [0,1]^\top$, so

$$
\mathbf{x}_1(\mathbf{x}_1 - \gamma\mathbf{x}_2)^\top = \begin{bmatrix}0\\1\end{bmatrix}\begin{bmatrix}0 & 1\end{bmatrix} = \begin{bmatrix}0 & 0\\0 & 1\end{bmatrix},
\qquad
R_2\mathbf{x}_1 = 1\begin{bmatrix}0\\1\end{bmatrix} = \begin{bmatrix}0\\1\end{bmatrix}.
$$

Summing gives
$\widehat{\mathbf{A}} = \left[\begin{smallmatrix}1 & -0.9\\0 & 1\end{smallmatrix}\right]$
and $\widehat{\mathbf{b}} = [2, 1]^\top$. Its inverse is
$\widehat{\mathbf{A}}^{-1} = \left[\begin{smallmatrix}1 & 0.9\\0 & 1\end{smallmatrix}\right]$,
and the fixed point is

$$
\mathbf{w} = \widehat{\mathbf{A}}^{-1}\widehat{\mathbf{b}} = \begin{bmatrix}1 & 0.9\\0 & 1\end{bmatrix}\begin{bmatrix}2\\1\end{bmatrix} = \begin{bmatrix}2.9\\1\end{bmatrix}.
$$

So $\hat v(s_2) = w_2 = 1$ (its return is the single reward $1$) and
$\hat 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]^\top$ only after many passes; LSTD read it off the
two transitions directly.

$$
% caption: 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 $\gamma=0.9$ LSTD returns $w_2=1$ and
% $w_1 = 2 + 0.9\cdot 1 = 2.9$, the exact Bellman-consistent values.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=11mm, inner sep=0pt},
  term/.style={rectangle, draw, fill=black!12, minimum size=9mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st, draw=acc, text=acc] (s1) at (0,0) {s1};
  \node[st] (s2) at (3.4,0) {s2};
  \node[term] (t) at (6.8,0) {term};
  \draw[->, thick] (s1) -- (s2) node[midway, above] {R = 2};
  \draw[->, thick] (s2) -- (t) node[midway, above] {R = 1};
  \node[acc, anchor=south, font=\scriptsize] at (0,0.75) {x = (1,0)};
  \node[anchor=south, font=\scriptsize] at (3.4,0.75) {x = (0,1)};
  \node[anchor=south, font=\scriptsize] at (6.8,0.7) {x = (0,0)};
  \node[acc, anchor=north, font=\scriptsize] at (0,-0.75) {w1 = 2.9};
  \node[anchor=north, font=\scriptsize] at (3.4,-0.75) {w2 = 1.0};
\end{tikzpicture}
$$

### The Sherman-Morrison incremental inverse

Written naively, LSTD looks like it grows more expensive as $t$ grows, and
forming $\widehat{\mathbf{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 $\widehat{\mathbf{A}}_t$ is a running sum of
**outer products** (each term $\mathbf{x}_k(\mathbf{x}_k -
\gamma\mathbf{x}_{k+1})^\top$ 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**:[^sb-lstd]

$$
\widehat{\mathbf{A}}_t^{-1}
\;=\; \Big(\widehat{\mathbf{A}}_{t-1} + \mathbf{x}_t(\mathbf{x}_t - \gamma\mathbf{x}_{t+1})^\top\Big)^{-1}
\;=\; \widehat{\mathbf{A}}_{t-1}^{-1} \;-\; \frac{\widehat{\mathbf{A}}_{t-1}^{-1}\,\mathbf{x}_t(\mathbf{x}_t - \gamma\mathbf{x}_{t+1})^\top\,\widehat{\mathbf{A}}_{t-1}^{-1}}{1 + (\mathbf{x}_t - \gamma\mathbf{x}_{t+1})^\top\,\widehat{\mathbf{A}}_{t-1}^{-1}\,\mathbf{x}_t},
$$

for $t > 0$, initialized with $\widehat{\mathbf{A}}_0^{-1} = \varepsilon^{-1}
\mathbf{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 $\widehat{\mathbf{A}}_t^{-1}$ (itself $O(d^2)$
memory), maintains it with one Sherman-Morrison update per step, and reads off
$\mathbf{w}_t = \widehat{\mathbf{A}}_t^{-1}\widehat{\mathbf{b}}_t$ — all in
$O(d^2)$ time and memory per step.

$$
% caption: One LSTD step. The new transition contributes a rank-one outer product
% to $\widehat{\mathbf{A}}$; Sherman-Morrison folds that update into the stored
% inverse $\widehat{\mathbf{A}}^{-1}$ using only matrix-vector products (never a
% fresh inversion), and $\mathbf{w} = \widehat{\mathbf{A}}^{-1}\widehat{\mathbf{b}}$
% is read off directly.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (trans) at (0,0) {new transition\\(x, R, next x)};
  \node[box] (rank1) at (3.4,0) {rank-one\\outer product};
  \node[box, draw=acc, text=acc, minimum width=26mm] (inv) at (7.2,0) {update inverse\\(Sherman-Morrison)};
  \node[box, draw=acc, text=acc] (w) at (7.2,-2.1) {w = Ainv b};
  \draw[->, black, thick] (trans) -- (rank1);
  \draw[->, black, thick] (rank1) -- (inv);
  \draw[->, acc, thick] (inv) -- (w);
  \node[anchor=west, font=\scriptsize] at (1.0,0.85) {O(d squared) per step};
\end{tikzpicture}
$$

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

```algorithm
caption: $\textsc{LSTD}$ — batch linear prediction of $\hat v = \mathbf{w}^\top\mathbf{x}(\cdot) \approx v_\pi$
input: feature map $\mathbf{x}$ with $\mathbf{x}(\text{terminal}) = \mathbf{0}$, small $\varepsilon > 0$
$\widehat{\mathbf{A}}^{-1} \gets \varepsilon^{-1}\mathbf{I}$ // a $d \times d$ matrix
$\widehat{\mathbf{b}} \gets \mathbf{0}$ // a $d$-vector
for each episode do
  initialize $S$
  $\mathbf{x} \gets \mathbf{x}(S)$
  repeat
    choose $A \sim \pi(\cdot \mid S)$, take it, observe $R$, $S'$
    $\mathbf{x}' \gets \mathbf{x}(S')$
    $\mathbf{v} \gets (\widehat{\mathbf{A}}^{-1})^\top(\mathbf{x} - \gamma\mathbf{x}')$
    $\widehat{\mathbf{A}}^{-1} \gets \widehat{\mathbf{A}}^{-1} - (\widehat{\mathbf{A}}^{-1}\mathbf{x})\,\mathbf{v}^\top / (1 + \mathbf{v}^\top\mathbf{x})$
    $\widehat{\mathbf{b}} \gets \widehat{\mathbf{b}} + R\,\mathbf{x}$
    $\mathbf{w} \gets \widehat{\mathbf{A}}^{-1}\widehat{\mathbf{b}}$
    $S \gets S'$
    $\mathbf{x} \gets \mathbf{x}'$
  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 $\varepsilon$: 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
$\pi$, 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.[^sb-lstd]

| | 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 $\widehat{\mathbf{A}}^{-1}$) |
| Data efficiency | needs many examples | most efficient linear TD method |
| Step size | needs $\alpha$ (must be tuned) | none, but needs $\varepsilon$ |
| Forgetting | built in (step size) | none — bad for changing $\pi$ |

## 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 $\hat q(s,a,\mathbf{w}) = \mathbf{w}^\top\mathbf{x}(s,a)$
of the current policy directly from the stored data, then the policy is made greedy
with respect to that $\hat 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.[^lspi]

$$
% caption: Least-squares policy iteration. LSTDQ solves the action-value fixed
% point $\mathbf{w} = \mathbf{A}^{-1}\mathbf{b}$ from a fixed batch of transitions;
% the policy is made greedy in the resulting $\hat q$; the two steps alternate over
% the same batch until the policy stops changing, never re-sampling the environment.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=12mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (data) at (0,0) {f\/ixed batch\\of transitions};
  \node[box, draw=acc, text=acc] (lstdq) at (4.2,0) {LSTDQ\\solve q-hat = Ainv b};
  \node[box] (greedy) at (4.2,-2.4) {greedy policy\\in q-hat};
  \draw[->, thick] (data) -- (lstdq);
  \draw[->, acc, thick] (lstdq) -- (greedy) node[midway, right, font=\scriptsize] {improve};
  \draw[->, acc, thick] (greedy) to[out=180,in=180] node[midway, left, font=\scriptsize] {re-evaluate} (lstdq.west);
  \node[anchor=west, font=\scriptsize] at (0.2,-2.4) {reuse same data};
\end{tikzpicture}
$$

[^sb-lstd]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §9.8 — Least-Squares TD: the TD fixed point $\mathbf{w}_{\mathrm{TD}} = \mathbf{A}^{-1}\mathbf{b}$ with $\mathbf{A} = \mathbb{E}[\mathbf{x}_t(\mathbf{x}_t - \gamma\mathbf{x}_{t+1})^\top]$ and $\mathbf{b} = \mathbb{E}[R_{t+1}\mathbf{x}_t]$; the LSTD estimates (9.20)–(9.21) with the $\varepsilon\mathbf{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 $\varepsilon$ parameter, and the lack of forgetting in control. LSTD is due to Bradtke and Barto (1996); the incremental inverse to Sherman and Morrison (1949).
[^lspi]: **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.