Incremental Least-Squares Temporal Difference Learning

Alborz Geramifard, Michael H. Bowling, Richard S. SuttonAAAI 2006 · OpenReview

Abstract

Approximate policy evaluation with linear function approximation is a foundational problem in reinforcement learning, typically addressed using temporal difference (TD) methods. We introduce Incremental Least-Squares TD (iLSTD), a novel algorithm that combines the data efficiency of Least-Squares TD (LSTD) with the computational efficiency of standard TD(0). While LSTD requires $O(n^2)$ operations per time step (where $n$ is the number of features), iLSTD achieves $O(n)$ complexity. Empirical results on the Boyan chain benchmark demonstrate that iLSTD converges significantly faster than TD(0) and nearly as rapidly as LSTD, making it highly suitable for large-scale reinforcement learning applications.

Introduction

In reinforcement learning, policy evaluation involves predicting the expected future reward (the value function) for a given policy. When the state space is large, linear function approximation is used to represent the value function as a weighted sum of features. Traditionally, researchers have faced a trade-off:

  1. TD(0): Computationally efficient ($O(n)$ per step) but data-inefficient, as it discards transition data after a single update.
  2. LSTD: Highly data-efficient but computationally expensive ($O(n^2)$ per step), which becomes prohibitive as the number of features grows into the thousands or millions.

iLSTD addresses this dilemma by providing an incremental approach to the LSTD objective.

The iLSTD Algorithm

iLSTD treats the LSTD solution as a target to be approached incrementally. Key innovations include:

  • Incremental Error Tracking: Instead of solving the LSTD system exactly at each step, iLSTD maintains a vector $\mu$ that tracks the total error relative to the LSTD objective.
  • Prioritized Updates: To maintain $O(n)$ complexity, the algorithm does not update every feature weight at every step. Instead, it identifies and updates only the feature(s) contributing most to the current error (using an argmax strategy).
  • Exploiting Sparsity: The algorithm is optimized for sparse feature sets, common in techniques like tile coding, allowing it to scale linearly with the number of active features.

Experimental Evaluation

The authors evaluated iLSTD using the Boyan Chain, a standard benchmark for policy evaluation. The problem was scaled to three sizes: Small (14 states, 4 features), Medium (102 states, 26 features), and Large (402 states, 101 features).

Data Efficiency

Across all problem sizes, iLSTD demonstrated data efficiency nearly identical to LSTD. As shown in the learning curves for the large-scale problem, iLSTD's RMS error reduces much faster than TD(0), tracking the LSTD curve almost perfectly.

Learning curves for the 402-state Boyan chain problem. iLSTD (green) tracks the data-efficient LSTD (red) closely, while both significantly outperform TD(0) (blue).

Computational Complexity

The primary advantage of iLSTD is its scaling behavior. As the number of features increases, the time required for LSTD grows quadratically, whereas iLSTD maintains a near-linear growth similar to TD(0).

Computational time per episode vs. number of features. LSTD's complexity grows quadratically, while iLSTD scales linearly, matching the efficiency of TD(0).

Key Insights

  • Bridging the Gap: iLSTD successfully occupies the "middle ground" between TD and LSTD, offering the best of both worlds.
  • Performance in Large Problems: In the 402-state problem, iLSTD reached a target error level in less total wall-clock time than TD(0). Although TD(0) is slightly faster per step, its poor data efficiency requires many more episodes to converge, making it slower overall in real-time.

Conclusion and Future Work

iLSTD provides a scalable solution for policy evaluation in high-dimensional feature spaces. Future work includes formalizing convergence proofs and extending the algorithm to incorporate eligibility traces ($TD(\lambda)$). Its linear scaling makes it a promising candidate for massive-scale RL tasks where traditional LSTD is infeasible.

Summary updated

Abstract

Approximate policy evaluation with linear function approximation is a commonly arising problem in reinforcement learning, usually solved using temporal difference (TD) algorithms. In this paper we introduce a new variant of linear TD learning, called incremental least-squares TD learning, or iLSTD. This method is more data efficient than conventional TD algorithms such as TD(0) and is more computationally efficient than non-incremental least-squares TD methods such as LSTD (Bradtke & Barto 1996; Boyan 1999). In particular, we show that the per-time-step complexities of iLSTD and TD(0) are O(n), where n is the number of features, whereas that of LSTD is O(n2). This difference can be decisive in modern applications of reinforcement learning where the use of a large number features has proven to be an effective solution strategy. We present empirical comparisons, using the test problem introduced by Boyan (1999), in which iLSTD converges faster than TD(0) and almost as fast as LSTD.
BibTeX
@inproceedings{geramifard2006incremental,
  author = {Alborz Geramifard and Michael H. Bowling and Richard S. Sutton},
  title = {{Incremental Least-Squares Temporal Difference Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
  url = {https://openreview.net/forum?id=rJWAGgb_WS},
}
Figure