TL;DR
This paper provides a unified framework for linear value function estimation in reinforcement learning, systematically extending both gradient-based and least-squares-based algorithms to handle off-policy learning with eligibility traces. By framing these methods as variations of a single objective function, the authors re-derive classic algorithms like off-policy LSTD($\lambda$) and TD($\lambda$), while mechanically discovering novel extensions like off-policy FPKF($\lambda$) and GTD2($\lambda$). An exhaustive empirical comparison reveals that despite the new additions, classic LSTD/LSPE and TD($\lambda$) still reign supreme in most practical scenarios.
What Problem Does This Paper Address?
In Reinforcement Learning (RL), estimating the value of a target policy using data generated by a different behavior policy is known as off-policy learning. This is notoriously difficult, especially when combined with function approximation (to handle large state spaces) and eligibility traces (a mechanism controlled by a parameter $\lambda$ that speeds up learning by balancing bias and variance).
While many algorithms exist for simple on-policy learning without traces (like TD, LSTD, and BRM), the literature on off-policy learning with traces is highly fragmented. There hasn't been a systematic, unified way to translate all these standard algorithms into the off-policy, trace-enabled regime. This paper bridges that gap by creating a universal "recipe" to upgrade existing algorithms.
Methods
The authors categorize existing linear value function approximators by their objective (bootstrapping, residual, or projected fixed point) and their optimization strategy (gradient descent vs. least-squares).
Their core methodological contribution is showing that all these methods essentially minimize a common squared-error cost function, differing only in how they instantiate a specific target parameter ($\xi$). To extend these to the off-policy setting with eligibility traces, they follow a systematic three-step recipe:
- Importance Sampling: They introduce cumulative importance sampling weights ($\rho$) to correct for the mismatch between the behavior policy and the target policy.
- The Forward View: They replace the standard Bellman operator with a $\lambda$-weighted empirical Bellman operator that looks ahead at future rewards and states.
- The Backward View: Because looking into the future is memory-inefficient for online learning, they use algebraic tricks (like the Sherman-Morrison/Woodbury matrix identities for least-squares, and recursive expectations for gradient methods) to convert the "forward view" into an equivalent, recursive "backward view" that only relies on past data.
This mechanical derivation yields known algorithms (off-policy LSTD($\lambda$), LSPE($\lambda$), TD($\lambda$), TDC/GQ($\lambda$)) and births entirely new ones (off-policy FPKF($\lambda$), BRM($\lambda$), gBRM($\lambda$), GTD2($\lambda$)).
Datasets
The algorithms are evaluated on Garnet problems ($\mathcal{G}(n_S, n_A, b, p)$), which are a class of randomly constructed, abstract finite Markov Decision Processes (MDPs). They tested on:
- Small instances: $\mathcal{G}(30, 4, 2, 8)$ (30 states, 4 actions, branching factor 2, 8 features).
- Big instances: $\mathcal{G}(100, 10, 3, 20)$ (100 states, 10 actions, branching factor 3, 20 features).
Key Insights and Ideas
- A Unifying Lens: The biggest "aha" moment is realizing that disparate algorithms—like Baird's residual algorithms, Sutton's TD methods, and Bradtke's LSTD—are just different flavors of the exact same optimization pattern.
- Mechanical Discovery: By establishing this unified pattern, discovering "new" RL algorithms becomes a systematic, mathematical process rather than a stroke of isolated genius.
- The Danger of Traces in Off-Policy: In off-policy settings, higher values of $\lambda$ (longer traces) can severely hurt performance. This is because importance sampling weights multiply over time; longer traces lead to compounding variance that can destabilize learning.
- The Classics Hold Up: Despite introducing several novel algorithms specifically designed for off-policy learning, the authors found that the standard, well-known algorithms are incredibly robust and generally perform the best.
Key Results
- Least-Squares Dominance: The least-squares methods LSTD($\lambda$) and LSPE($\lambda$) consistently provided the best estimates and fastest convergence across both on-policy and off-policy settings.
- Gradient Fallback: Least-squares methods have an $O(p^2)$ computational complexity (where $p$ is the number of features). When $p$ is too large, standard TD($\lambda$) proved to be the best gradient-based alternative ($O(p)$ complexity).
- Optimal $\lambda$ Tuning: In off-policy scenarios, the best performing least-squares algorithms (LSTD/LSPE) favored $\lambda = 0$. This effectively turns off the eligibility traces to avoid the massive variance introduced by importance sampling.
- Performance of New Algorithms: The newly derived gBRM($\lambda$) works surprisingly well in on-policy settings. However, algorithms specifically designed to fix off-policy divergence (like TDC/GTD2) were empirically much slower to converge than standard TD.
Limitations and Future Work
- Theoretical Gaps: The authors note a significant lack of convergence proofs for many off-policy trace-based stochastic gradient algorithms under mild assumptions. Current proofs for off-policy TD($\lambda$) require artificial parameter bounding, and TDC requires restrictive assumptions on trace variance. Providing complete theoretical analyses for the newly derived algorithms (FPKF($\lambda$), BRM($\lambda$), gBRM($\lambda$)) remains an open problem.
- Empirical Scope: The evaluation is limited to linear function approximation on abstract Garnet MDPs. The paper does not explore how these unified algorithms behave with non-linear approximations (like deep neural networks) or in complex, real-world environments.
Summary updated