LSTD Algorithm
Incremental updates keep LSTD from repeatedly rebuilding its accumulated quantities, but the matrix update remains O(n^2).
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.
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.
- 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.
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
Tracing Two Consecutive Transitions
Follow the order of operations when LSTD receives one transition and then continues into a later step or episode.
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.
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′.
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.
Update the vector quantity: The reward-weighted term Rφ updates b̂.
Calculate parameters: θ is calculated only after both Â^-1 and b̂ have been updated.
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.
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 |
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
Checking θ first instead of locating the first transition where the procedure diverges.
The unexpected result may have entered earlier through the feature representations, inverse update, or vector update.
Fix:
Compare the procedure at the transition where the trace first differs from the expected result.Using an incorrect current or next-state feature representation.
LSTD depends on both the current representation and the next-state representation.
Fix:
Check φ and φ′ first, and verify that state and feature assignments advance together.Forming v without the feature difference involving φ and γφ′.
The source identifies this feature difference as part of the inverse-update procedure.
Fix:
Check that v used the feature difference φ - γφ′.Using the wrong Sherman-Morrison denominator.
The denominator is part of the specified incremental inverse update.
Fix:
Check the denominator 1 + v⊤φ at the transition where the result first changes.Updating b̂ with the wrong reward-weighted term.
The source specifies that b̂ receives the reward-weighted term Rφ.
Fix:
Verify that the b̂ update uses Rφ.Calculating θ before both maintained quantities have been updated.
The source gives the update sequence as v, Â^-1, b̂, then θ.
Fix:
Calculate θ only after the inverse and vector updates are complete.
Practice Trace
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.
What do you think happens?
If LSTD maintains its inverse incrementally, does its per-step computation become O(n), like semi-gradient TD?
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
- LSTD represents states with φ(s) and assigns the zero representation to the terminal state.
- Its maintained matrix and inverse are n by n, which leads to O(n^2) memory and per-step computation.
- Sherman-Morrison maintains the inverse incrementally instead of recomputing a general inverse at O(n^3) after every sample.
- The operational sequence is current features, transition results, v, Â^-1 update, b̂ update, θ calculation, and advancement to the next state and features.
- LSTD avoids a step-size parameter but still requires ε and may need a separate forgetting mechanism when the target policy changes.
Key Takeaways
- 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.