Uncorrected Least-Squares Temporal Difference with Lambda-Return

Takayuki OsogamiAAAI 2020 · OpenReview

Abstract

Temporal difference, TD($\lambda$), learning is a foundation of reinforcement learning and also of interest in its own right for the tasks of prediction. Recently, true online TD($\lambda$) has been shown to closely approximate the “forward view” at every step, while conventional TD($\lambda$) does this only at the end of an episode. We re-examine least-squares temporal difference, LSTD($\lambda$), which has been derived from conventional TD($\lambda$). We design Uncorrected LSTD($\lambda$) in such a way that, when $\lambda = 1$, Uncorrected LSTD(1) is equivalent to the least-squares method for the linear regression of Monte Carlo (MC) return at every step, while conventional LSTD(1) has this equivalence only at the end of an episode, since the MC return is corrected to be unbiased. We prove that Uncorrected LSTD($\lambda$) can have smaller variance than conventional LSTD($\lambda$), and this allows Uncorrected LSTD($\lambda$) to sometimes outperform conventional LSTD($\lambda$) in practice. When $\lambda = 0$, however, Uncorrected LSTD(0) is not equivalent to LSTD. We thus also propose Mixed LSTD($\lambda$), which mixes the two LSTD($\lambda$)s in a way that it matches conventional LSTD($\lambda$) at $\lambda = 0$ and Uncorrected LSTD($\lambda$) at $\lambda = 1$. In numerical experiments, we study how the three LSTD($\lambda$)s behave under limited training data.

Introduction

In reinforcement learning, estimating a value function—predicting total future rewards from a state—is a core challenge. This is typically approached via Monte Carlo (MC) methods, which wait for episode completion, or Temporal Difference (TD) methods, which update estimates based on subsequent estimates (bootstrapping). The $\lambda$ parameter in TD($\lambda$) allows for an interpolation between these two extremes.

LSTD($\lambda$) is the least-squares variant of TD($\lambda$), known for superior sample efficiency but higher computational cost. Standard implementations, such as Boyan’s LSTD, utilize a specific correction to ensure the estimator remains unbiased. However, this correction often introduces significant variance, making the algorithm sensitive to hyperparameters and preventing it from matching standard linear regression except at the end of an episode. This paper explores the "Uncorrected" approach to address these stability issues through a bias-variance tradeoff.

Proposed Methods

The authors derive two new algorithms using the method of instrumental variables, aiming to improve stability and step-wise equivalence to linear regression.

  1. Uncorrected LSTD($\lambda$): This version omits the "bias correction" found in standard LSTD. At $\lambda=1$, it becomes mathematically equivalent to standard least-squares regression on Monte Carlo returns (LSMC) at every time step.
  2. Mixed LSTD($\lambda$): This variant blends the transition matrices of the Uncorrected and Boyan versions. It is designed to match standard LSTD at $\lambda=0$ and the Uncorrected version at $\lambda=1$, effectively interpolating between the two.
Algorithms for Boyan’s LSTD($\lambda$), Uncorrected LSTD($\lambda$), and Mixed LSTD($\lambda$).

Both algorithms maintain $O(k^2)$ computational complexity, where $k$ is the number of features, making them suitable for recursive updates in real-time scenarios.

Experimental Evaluation and Results

The methods were evaluated on randomly constructed Markov Reward Processes (MRPs), including small (10 states), large (100 states), and deterministic variants. The experiments focused on the "small $T$" regime (100–1,000 steps) to assess performance under limited data.

The Bias-Variance Tradeoff

While the Uncorrected version is technically biased, it exhibits significantly lower variance than Boyan’s version. In early learning stages or data-scarce environments, a stable, slightly biased guess is often better than an erratic, unbiased one.

Empirical Robustness

A key finding is the "brittleness" of Boyan’s LSTD. While it can achieve minimal error with perfect hyperparameter tuning (optimal $\lambda$ and regularization coefficient $\alpha$), its performance degrades sharply with sub-optimal settings. In contrast, Uncorrected LSTD is remarkably robust, maintaining stable performance across a broad range of parameters.

MSE performance across different regularization coefficients and $\lambda$ values for three MRP environments.

As shown in the experimental results, Uncorrected and Mixed LSTD frequently outperformed Boyan’s version in data-limited scenarios. Although Boyan’s LSTD could achieve a slightly lower Mean Squared Error (MSE) (by about 2%) under optimal tuning, the Uncorrected version was significantly better on average across all hyperparameter settings.

Conclusion and Future Work

Uncorrected LSTD($\lambda$) offers a compelling alternative to standard LSTD by trading off theoretical unbiasedness for practical stability and robustness. Future work includes extending these findings from prediction to control problems, such as Least-Squares Policy Iteration (LSPI), and providing formal proofs for the bias-variance tradeoff in general MRPs. While Mixed LSTD($\lambda$) provides a useful interpolation, it carries a higher computational overhead due to the need to update two matrices.

Summary updated

Abstract

Temporal difference, TD(λ), learning is a foundation of reinforcement learning and also of interest in its own right for the tasks of prediction. Recently, true online TD(λ) has been shown to closely approximate the “forward view” at every step, while conventional TD(λ) does this only at the end of an episode. We re-examine least-squares temporal difference, LSTD(λ), which has been derived from conventional TD(λ). We design Uncorrected LSTD(λ) in such a way that, when λ = 1, Uncorrected LSTD(1) is equivalent to the least-squares method for the linear regression of Monte Carlo (MC) return at every step, while conventional LSTD(1) has this equivalence only at the end of an episode, since the MC return is corrected to be unbiased. We prove that Uncorrected LSTD(λ) can have smaller variance than conventional LSTD(λ), and this allows Uncorrected LSTD(λ) to sometimes outperform conventional LSTD(λ) in practice. When λ = 0, however, Uncorrected LSTD(0) is not equivalent to LSTD. We thus also propose Mixed LSTD(λ), which % mixes the two LSTD(λ)s in a way that it matches conventional LSTD(λ) at λ = 0 and Uncorrected LSTD(λ) at λ = 1. In numerical experiments, we study how the three LSTD(λ)s behave under limited training data.
BibTeX
@inproceedings{osogami2020uncorrected,
  author = {Takayuki Osogami},
  title = {{Uncorrected Least-Squares Temporal Difference with Lambda-Return}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=mrk1JYuT0Sh},
}
Figure