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:
- 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.
- 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$.
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:
- Boyan’s Chain: A small, 13-state Markov chain used to verify that the algorithm behaves correctly on simple problems.
- 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.
- 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