Finite-Sample Analysis of LSTD

Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi MunosICML 2010 · OpenReview

Least-Squares Temporal-Difference (LSTD) learning is a cornerstone algorithm for policy evaluation in reinforcement learning (RL). While standard temporal-difference learning is popular, LSTD is often preferred for its superior data efficiency. However, for over a decade, our theoretical understanding of LSTD was predominantly asymptotic. Researchers knew the algorithm converged given infinite data, but precise "finite-sample" bounds—guarantees on accuracy given a specific, limited number of samples—were missing.

This paper provides the first complete finite-sample analysis of LSTD, deriving rigorous performance bounds that demonstrate how the error decreases as sample size increases. Crucially, it proves that LSTD can succeed even in environments that have not yet reached a steady state.

The Challenge of Policy Evaluation

In RL, policy evaluation involves estimating the value function (the expected long-term reward) of a specific strategy. When dealing with large or continuous state spaces, this value function is typically approximated using a linear combination of features.

Before this work, we lacked the mathematical guarantees needed to understand LSTD's reliability in real-world, data-limited scenarios. We didn't know exactly how many samples were required to reach a target accuracy, nor did we fully understand how the algorithm's stability depended on the specific features chosen to represent the state space. This paper fills that critical gap.

Methodology: Pathwise LSTD and Geometric Projections

To analyze the algorithm, the authors introduce a specific formulation called Pathwise LSTD. The key technical innovation is the use of a "pathwise Bellman operator" that is guaranteed to be a contraction mapping with respect to the empirical norm (based on the data actually collected during a trajectory).

Geometric interpretation of the LSTD solution, illustrating the projection onto the feature space.

Geometrically, LSTD operates by projecting updates back onto the chosen linear feature space. As illustrated above, the algorithm seeks a fixed point $\hat{v}$ within the feature space $\mathcal{F}_n$. It applies the empirical Bellman operator $\widehat{\mathcal{T}}$ to $\hat{v}$, and then projects that result back onto the feature space using the projection operator $\widehat{\Pi}$. The LSTD solution is found when $\hat{v} = \widehat{\Pi}\widehat{\mathcal{T}}\hat{v}$.

To rigorously bound the error of this solution, the authors break the problem into two distinct settings:

  1. Markov Design (Training Bound): They first analyze the error strictly on the specific states visited during a single trajectory. Using martingale concentration inequalities, they establish that the error on the observed trajectory decreases at a rate of $O(1/\sqrt{n})$. This bound explicitly accounts for both the approximation error (how well the features can represent the true value function) and the estimation error (noise from finite data).
  2. Generalization: They then extend this analysis to the entire state space by assuming the underlying Markov chain is $\beta$-mixing. This property implies that the system "forgets" its initial state quickly enough to behave predictably over time. The resulting generalization bound shows that as the number of samples $n$ goes to infinity, the error converges to classic asymptotic results, but it explicitly quantifies the "price" paid for having finite data.

Key Insights and Theoretical Guarantees

Several surprising and highly practical insights emerge from this finite-sample analysis:

  • Stationarity is Optional for Visited States: LSTD does not strictly require the Markov chain to have a stationary distribution to provide a good estimate of the value function at the states actually visited. It can learn effectively even if the agent is constantly exploring new territory, provided the features are sufficiently independent.
  • The Eigenvalue Bottleneck: The stability and accuracy of LSTD depend critically on $\nu_n$, the smallest strictly positive eigenvalue of the empirical Gram matrix (which represents feature overlap). If the chosen features are nearly redundant, this eigenvalue approaches zero, and the error bound explodes. The paper provides a specific condition on the number of samples required to ensure the LSTD solution is stable based on the environment's mixing properties.
  • Faster Convergence for Linear Spaces: Because LSTD leverages a linear structure, it achieves a better convergence rate ($O(1/n)$ for squared error) compared to more general, non-linear methods.
  • The "Burn-in" Trick: For non-stationary processes, the authors prove that simply discarding a small, logarithmic number of initial samples (a "burn-in" period) allows the algorithm to achieve the same theoretical performance as if it had started in a perfectly stationary regime.

Limitations and Future Directions

While this paper establishes a vital theoretical foundation, it notes several limitations that pave the way for future research.

First, the bounds are highly sensitive to the smallest eigenvalue of the Gram matrix ($\nu_n$). In high-dimensional spaces with many features, this value can be very small, resulting in pessimistic bounds; removing this dependency remains an open challenge. Second, the analysis is strictly limited to LSTD(0). Extending these finite-sample proofs to LSTD($\lambda$), which uses eligibility traces to balance bias and variance, is a logical next step. Finally, the proofs rely entirely on linear function approximation. As the RL field increasingly adopts deep neural networks, translating these rigorous finite-sample guarantees to non-linear settings will be a critical hurdle.

Summary updated

Abstract

In this paper we consider the problem of policy evaluation in reinforcement learning, i.e., learning the value function of a fixed policy, using the least-squares temporal-difference (LSTD) learning algorithm. We report a finite-sample analysis of LSTD. We first derive a bound on the performance of the LSTD solution evaluated at the states generated by the Markov chain and used by the algorithm to learn an estimate of the value function. This result is general in the sense that no assumption is made on the existence of a stationary distribution for the Markov chain. We then derive generalization bounds in the case when the Markov chain possesses a stationary distribution and is β-mixing.
BibTeX
@inproceedings{lazaric2010finite,
  author = {Alessandro Lazaric and Mohammad Ghavamzadeh and Rémi Munos},
  title = {{Finite-Sample Analysis of LSTD}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=HJEESh-_-B},
}
Figure