LSTD Algorithm

The incremental nature of LSTD does not make its update linear in the number of features. LSTD uses O(n^2) memory and per-step computation, whereas semi-gradient TD uses O(n) computation per step according to the source pack.

Programming

Why the Matrix Matters

LSTD, or Least-Squares Temporal Difference learning, processes experience one episode and one step at a time. Its appeal is that accumulated quantities can be updated as new experience arrives instead of being rebuilt from all previous experience. However, LSTD maintains a matrix and its inverse, not only a vector. If the state representation has n features, that matrix is n by n, so the number of features directly affects both memory use and the work required at every step.

What does an n-by-n matrix contain, and why do storing and updating Â^-1 require O(n^{^2}) memory and computation?

Key point

The incremental nature of LSTD does not make its update linear in the number of features. LSTD uses O(n^{^2}) memory and per-step computation, whereas semi-gradient TD uses O(n) computation per step according to the source pack.

A Transition Through LSTD

At a single step, LSTD begins with the current state representation φ. An action is selected, and the environment then produces a reward R and a next state S′. The next-state feature representation φ′ is obtained from that next state. These current and next features, together with the reward and discount factor, provide the transition information used to update the maintained quantities.

How do the current features, next-state features, reward, discount factor, Â^-1, and b̂ flow into the LSTD update?

Inputs from the transition: current features φ, next-state features φ′, reward R, and discount factor γ.
Maintained state: Â^-1 and b̂.
Intermediate matrix quantity: v, formed using the feature difference involving φ and γφ′.
Update result: Â^-1 and b̂ are updated, and θ is calculated afterward.

Incremental Inverse Maintenance

LSTD's matrix is built from sums of outer products. That special structure makes it possible to maintain its inverse as new samples arrive. A general matrix inverse computed from scratch has O(n^{^3}) complexity. Repeating that full operation after every new sample would be unnecessarily expensive. The Sherman-Morrison formula changes this into an incremental inverse operation with O(n^{^2}) cost.

How does the Sherman-Morrison formula update Â^-1 from the previous inverse without recomputing the entire matrix inverse?

The important distinction is between rebuilding and maintaining. Rebuilding computes a general inverse from the entire current matrix and costs O(n^{^3}). Maintaining starts with the previous inverse and applies an incremental correction based on the new transition. Sherman-Morrison therefore removes the repeated cubic recomputation, but it does not make the update constant-cost or linear-cost: the resulting incremental update remains O(n^{^2}).

Episode-by-Episode State

What happens first, next, and last as LSTD receives transitions, updates Â^-1 and b̂, and carries accumulated quantities into another episode?

Worked example

Tracing Two Consecutive Transitions

Follow the order of operations when LSTD receives one transition and then continues into a later step or episode.

1
Start with the current state
LSTD first has the current feature representation φ. The first update therefore requires current features before a next-state representation exists.
2
Obtain transition results
After an action is selected, the environment supplies reward R and next state S′. LSTD obtains the next-state representation φ′ from S′.
3
Update the inverse quantity
The feature difference involving φ and γφ′ is used to form v. The Sherman-Morrison update uses v and the denominator 1 + v⊤φ to update Â^-1.
4
Update the vector quantity
The reward-weighted term Rφ updates b̂.
5
Calculate parameters
θ is calculated only after both Â^-1 and b̂ have been updated.
6
Continue processing
The state and feature assignments advance together to the next step. Across episodes, the accumulated maintained quantities continue to matter rather than being rebuilt after every transition.

Result

The required order is current features, transition results, inverse update, vector update, parameter calculation, and advancement to the next state and feature representation.

Cost and Tuning Trade-offs

Method	Per-step computation	Main maintained form	Trade-off
LSTD	O(n^{^2})	Matrix inverse and vector	Higher cost, potentially faster learning
Semi-gradient TD	O(n)	Vector-oriented update	Lower per-step cost

The source compares the per-step computational cost of LSTD and semi-gradient TD as the number of features n grows.

Which operations are performed at each step in LSTD and semi-gradient TD, and how do their costs differ as the number of features grows?

LSTD does not require a step-size parameter, but that does not remove every tuning concern. It requires ε. If ε is too small, the sequence of inverses can vary wildly; if ε is too large, learning is slowed. LSTD also lacks a step-size parameter that would provide forgetting. This can preserve older information when it remains relevant, but it can be a problem when the target policy changes. In control applications, another mechanism is typically needed to induce forgetting.

Debugging the Update Chain

At which stage could an unexpected result arise: input features, outer-product accumulation, b̂ update, Sherman-Morrison denominator, or parameter calculation?

Common mistake
Checking θ first instead of locating the first transition where the procedure diverges.
What it looks like
A final parameter estimate looks unexpected, so the whole episode is inspected at once.
Why it fails
The unexpected result may have entered earlier through the feature representations, inverse update, or vector update.
Do this instead
Compare the procedure at the transition where the trace first differs from the expected result.
Common mistake
Using an incorrect current or next-state feature representation.
What it looks like
The state advances but φ is not advanced with it, or φ′ is taken from the wrong next state.
Why it fails
LSTD depends on both the current representation and the next-state representation.
Do this instead
Check φ and φ′ first, and verify that state and feature assignments advance together.
Common mistake
Forming v without the feature difference involving φ and γφ′.
Why it fails
The source identifies this feature difference as part of the inverse-update procedure.
Do this instead
Check that v used the feature difference φ - γφ′.
Common mistake
Using the wrong Sherman-Morrison denominator.
What it looks like
The inverse update uses a denominator other than 1 + v⊤φ.
Why it fails
The denominator is part of the specified incremental inverse update.
Do this instead
Check the denominator 1 + v⊤φ at the transition where the result first changes.
Common mistake
Updating b̂ with the wrong reward-weighted term.
What it looks like
The reward is used without the current feature representation.
Why it fails
The source specifies that b̂ receives the reward-weighted term Rφ.
Do this instead
Verify that the b̂ update uses Rφ.
Common mistake
Calculating θ before both maintained quantities have been updated.
Why it fails
The source gives the update sequence as v, Â^-1, b̂, then θ.
Do this instead
Calculate θ only after the inverse and vector updates are complete.

Practice Trace

MEDIUM

A trace produces an unexpected θ after one transition. Describe the order in which you would investigate the update. Include the current and next feature representations, v, the Sherman-Morrison denominator, the reward-weighted b̂ term, and the point at which θ is calculated.

Hints

Start at the transition where the trace first differs from the expected result.
Check φ and φ′ before checking the matrix and vector updates.
Verify v and the denominator 1 + v⊤φ.
Confirm that b̂ received Rφ and that θ was calculated afterward.

Your attempt (not saved)

What do you think happens?

If LSTD maintains its inverse incrementally, does its per-step computation become O(n), like semi-gradient TD?

Yes, because no matrix is involved after initialization.
No, it remains O(n^{^2}) per step.
Only when the number of features is one.

Reveal answer

Answer:

No, it remains O(n^{^2}) per step.

Sherman-Morrison avoids recomputing a general inverse at O(n^{^3}), but the incremental inverse update still requires O(n^{^2}) computation.

Essential Takeaways

1
LSTD represents states with φ(s) and assigns the zero representation to the terminal state.
2
Its maintained matrix and inverse are n by n, which leads to O(n^{^2}) memory and per-step computation.
3
Sherman-Morrison maintains the inverse incrementally instead of recomputing a general inverse at O(n^{^3}) after every sample.
4
The operational sequence is current features, transition results, v, Â^-1 update, b̂ update, θ calculation, and advancement to the next state and features.
5
LSTD avoids a step-size parameter but still requires ε and may need a separate forgetting mechanism when the target policy changes.

At a glance

LSTD gains incremental updates without becoming a linear-cost method: its matrix update remains O(n^{^2}).
Sherman-Morrison changes repeated inverse computation from a general O(n^{^3}) operation into an O(n^{^2}) incremental operation.
Each transition supplies current features, next-state features, reward, and discount information for updating Â^-1 and b̂ before calculating θ.
LSTD can learn rapidly and does not use a step-size parameter, but ε, feature size, policy changes, and forgetting remain important concerns.
When results look wrong, inspect the first divergent transition and check features, v, the denominator, b̂, and the final parameter calculation in that order.

Related concepts

More concepts starting with L