iLSTD: Eligibility Traces and Convergence Analysis

Alborz Geramifard, Michael H. Bowling, Martin Zinkevich, Richard S. SuttonNeurIPS 2006 · OpenReview

This paper, from reinforcement learning (RL) researchers at the University of Alberta, tackles a classic trade-off in policy evaluation: the choice between computational speed and data efficiency. By extending the iLSTD (incremental Least-Squares Temporal Difference) algorithm, the authors provide a way to get the high-quality results of second-order methods without the crippling $O(n^2)$ computational cost.

TL;DR

The authors introduce iLSTD($\lambda$), an algorithm that bridges the gap between fast-but-wasteful TD learning and data-efficient-but-slow LSTD. It achieves $O(n)$ complexity while maintaining near-LSTD performance, now with a formal convergence proof and support for eligibility traces.

What Problem Does This Paper Address?

In RL, "policy evaluation" is the task of estimating how much reward an agent will get from a specific state. There are two traditional ways to do this with linear function approximation:

  1. Temporal Difference (TD) Learning: It’s fast ($O(n)$ per step, where $n$ is the number of features) but "forgets" data quickly, requiring many samples to converge.
  2. Least-Squares TD (LSTD): It’s incredibly data-efficient because it solves a system of linear equations ($A\theta = b$) to find the best fit for all observed data. However, it costs $O(n^2)$ per step. If you have 10,000 features, $n^2$ is 100 million—making LSTD too slow for real-time use.

The dilemma is that practitioners often have to choose between wasting data (TD) or wasting CPU cycles (LSTD). iLSTD was originally proposed to solve this, but it lacked a convergence proof and didn't support eligibility traces ($\lambda$), a crucial tool in RL for credit assignment over time.

Methods

The core idea of iLSTD is to maintain the same $A$ matrix and $b$ vector as LSTD but to avoid solving the whole system at every time step. Instead, it performs an incremental update on only a few dimensions of the parameter vector $\theta$.

iLSTD Algorithm and Complexity

Key innovations in this paper: * Eligibility Traces: They integrated the $\lambda$ parameter, allowing the algorithm to look back at previous states (the "backward view") to speed up learning. * Dimension Selection: The algorithm picks $m$ dimensions of $\theta$ to update each step. The authors generalized this mechanism, allowing for either "greedy" selection (updating the dimensions with the largest errors) or "random" selection. * Sparsity Exploitation: The algorithm is designed for cases where features are sparse (only $k$ features are non-zero at once). This keeps the complexity at $O((m+k)n)$, which is linear in $n$.

Datasets

The authors evaluated the algorithm on two classic RL benchmarks:

  1. Boyan’s Chain: A small, 13-state Markov chain used to verify that the algorithm behaves correctly on simple problems.
  2. Mountain Car: A more complex task where a car must gain momentum to climb a hill. To test scalability, they used Tile Coding to create a large feature space of $n = 10,000$ features.

Key Insights and Ideas

  • The "Best of Both Worlds": iLSTD($\lambda$) acts like a "lazy" LSTD. By only updating a few dimensions of the solution at a time, it eventually reaches the same solution as LSTD but spreads the computational cost across many time steps.
  • Convergence is Guaranteed: The authors proved that if you select which dimensions to update uniformly at random, iLSTD($\lambda$) is guaranteed to converge to the same solution as TD($\lambda$) and LSTD($\lambda$).
  • Greedy vs. Random: While random selection is mathematically "safe," the "greedy" selection (picking the dimensions with the highest current error) often performs better in practice, even though it's harder to prove convergence for it.
  • Linear Scaling: The jump from $O(n^2)$ to $O(n)$ is the difference between an algorithm being "research-only" and "production-ready" for high-dimensional problems.

Key Results

  • Speedup: In the Mountain Car task ($n=10,000$), LSTD took 253.42 ms per step, while iLSTD($\lambda$) took only 9.80 ms. That is a ~25x speedup, making it feasible for real-time control.
  • Data Efficiency: iLSTD($\lambda$) significantly outperformed standard TD($\lambda$). In Boyan’s Chain, iLSTD reached near-optimal error levels in 200 episodes, whereas TD was still far off.
Loss vs. Episodes for different algorithms
  • Stability: While iLSTD-Greedy performed best on simple problems, it showed some instability on Mountain Car with high $\lambda$ values, highlighting the importance of the authors' "Random" selection proof for guaranteed stability.

Limitations and Future Work

  • The Selection Mechanism: The authors admit that finding the optimal way to choose which dimensions to update is still an open question. Greedy is fast but potentially unstable; Random is stable but potentially slower to improve.
  • Learning Rates: The algorithm is sensitive to the learning rate ($\alpha$), especially in the greedy variant.
  • Complex Environments: The authors suggest testing iLSTD on even larger scales, such as simulated soccer (Keepaway), where feature counts can be even higher and LSTD is completely impossible to run.

Summary updated

Abstract

We present new theoretical and empirical results with the iLSTD algorithm for policy evaluation in reinforcement learning with linear function approximation. iLSTD is an incremental method for achieving results similar to LSTD, the dataefficient, least-squares version of temporal difference learning, without incurring the full cost of the LSTD computation. LSTD is O(n2 ), where n is the number of parameters in the linear function approximator, while iLSTD is O(n). In this paper, we generalize the previous iLSTD algorithm and present three new results: (1) the first convergence proof for an iLSTD algorithm; (2) an extension to incorporate eligibility traces without changing the asymptotic computational complexity; and (3) the first empirical results with an iLSTD algorithm for a problem (mountain car) with feature vectors large enough (n = 10, 000) to show substantial computational advantages over LSTD.
BibTeX
@inproceedings{geramifard2006ilstd,
  author = {Alborz Geramifard and Michael H. Bowling and Martin Zinkevich and Richard S. Sutton},
  title = {{iLSTD: Eligibility Traces and Convergence Analysis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=ByVSftWdbr},
}
Figure