Does LSTD need a model of transition probabilities?

The sample-based calculation uses observed transitions without requiring an explicit transition model.

Must a matrix inverse be formed explicitly?

No. A suitable linear-system solver is generally the more useful computational operation.

Does the method always recover exact values?

No. Representation, sampling and mathematical conditions determine what solution can be recovered.

AI Glossary / Reinforcement learning and robotics / Advanced

Least-squares temporal-difference learning

Definition

Least-squares temporal-difference learning, usually abbreviated LSTD, estimates a value function by solving a system of equations built from observed transitions. In its standard linear form, it uses features of the current and next states together with rewards to find parameters satisfying empirical temporal-difference consistency conditions. It is primarily a policy-evaluation method.

What it means

The question is how much future reward to expect while following a particular policy. Ordinary temporal-difference learning repeatedly nudges a prediction after each experience. LSTD instead accumulates information about relationships between features, rewards and successor states, then solves for parameters jointly.

The word least-squares can be misleading. LSTD is not generally ordinary regression on fixed labels, because its target includes the value being estimated. Nor is it simply minimizing the squares of all sampled temporal-difference errors. Its equations correspond to a different consistency condition, with the current-state features acting as instruments in the original derivation.

How it works

Represent a state's value as the inner product of its feature vector phi and a parameter vector theta. For each transition, record phi, the next feature vector phi_next, reward r and discount gamma. Use zero next-state features at genuine termination.

Accumulate A as the sum of phi times the transpose of phi minus gamma times phi_next. Accumulate b as the sum of phi times r. Solve A theta equals b when the system is well posed. Using averages instead of sums produces the same unregularized solution.

These equations set the aggregate feature-weighted TD error to zero. They do not require every individual transition to have zero error. Random rewards and imperfect representations can leave substantial individual residuals.

With d features, a dense A needs quadratic storage. A conventional dense solve costs cubic work, while recursive variants update matrix information more incrementally. Regularization and numerical safeguards can improve conditioning, but change the precise fitted problem. Feature dependence, weak coverage and nearly singular systems require attention. The linear theory does not automatically extend to an arbitrary neural-network critic.

Three practical examples

1. A simulator evaluates a fixed dispatch policy using a small set of features describing queue length, workload and available capacity.

2. A researcher compares ordinary TD and LSTD on identical trajectories to distinguish data efficiency from computation per observation.

3. An educational model uses separate features for two states, making the accumulated equations visible before introducing compressed representations.

Think of it this way

Think of reconciling a network of linked estimates. A value today depends partly on a reward now and partly on a value tomorrow. LSTD collects many such relationships and solves their combined equations. Solving them neatly cannot repair a missing relationship or make an unsuitable feature representation expressive enough.

Worked example

Consider an original two-state episodic dataset. State A has features (1, 0), state B has features (0, 1), and termination has features (0, 0). Set gamma to 0.5.

The first observed transition is A to B with reward 1. It contributes the matrix with first row (1, -0.5) and second row (0, 0), and contributes (1, 0) to b. The second transition is B to termination with reward 2. It adds a 1 in the matrix's bottom-right position and adds (0, 2) to b.

The resulting equations are theta_A minus 0.5 times theta_B equals 1, and theta_B equals 2. Therefore theta_B is 2 and theta_A is 2. Directly checking the observed return from A gives 1 plus 0.5 times 2, also 2.

Now add another observed A-to-B transition, this time with reward 3. The first row of A becomes (2, -1), and b becomes (4, 2). Solving gives theta_B equal to 2 and theta_A equal to 3. The two observed A rewards average 2, so the fitted A value is 2 plus 0.5 times 2.

The two A-transition TD errors are now -1 and +1. They cancel in the feature-weighted equations although neither is zero. This dataset calculation illustrates the estimator; three observations do not establish the true expected returns of an unknown environment.

Illustrative case study

In a fictional project, Alder Simulation evaluates one warehouse-routing policy before comparing alternatives. The team chooses a compact feature representation and saves transition summaries so it can reproduce the LSTD equations.

An early fit changes sharply when a rarely visited state appears. Investigation finds two features that almost duplicate one another. The team revises the representation, reports conditioning diagnostics and evaluates prediction quality on separate simulated episodes. It records the policy that generated the data and does not interpret a stable matrix solution as evidence that the routing policy is optimal.

Common misconceptions and mistakes

Do not confuse solving policy-evaluation equations with selecting the best policy. Policy improvement is a separate operation.

Avoid describing LSTD as free of design choices because it lacks an ordinary TD learning-rate schedule. Features, discounting, data selection, regularization and solver choices still matter.

More observations do not necessarily correct a feature space that cannot represent important distinctions. Likewise, data collected under another policy need an appropriate off-policy formulation or correction; an unmodified calculation can evaluate a different process from the one intended.

Business use

LSTD is relevant when experiences are expensive and the value representation is modest enough to support matrix calculations. A business team can compare its prediction accuracy, processing cost and sensitivity to data coverage against incremental alternatives. The useful decision is whether improved use of existing experience outweighs storage and numerical complexity for the actual workflow, not whether a closed-form equation sounds more rigorous.

Check your understanding

Why can the final example have nonzero individual TD errors?

Answer: Its aggregate feature-weighted errors cancel.

What happens if a feature is never activated?

Answer: Its associated information can be insufficient, potentially making the system singular.

Related terms

Policy evaluation
Instrumental variables
temporal-difference learning
linear function approximation
projected Bellman equation
recursive least squares and least-squares policy iteration

Learn next

Next, derive A and b for a three-state chain. Then replace separate state features with a compressed representation and inspect how the solution and residuals change.

Sources

Primary source: Steven J. Bradtke and Andrew G. Barto, Linear Least-Squares Algorithms for Temporal Difference Learning, especially Section 5: https://all.cs.umass.edu/pubs/1995_96/bradtke_b_ML96.pdf

The two-state dataset, calculations and fictional project are original teaching material. The explanation specifies the basic linear LSTD(0) form; trace-based and off-policy variants require their own equations.

Previous: Least-squares support vector machine Next: Least-to-most prompting