Abstract In the framework of Markov Decision Processes, off-policy learning is the problem of learning a linear approximation of the value function of some fixed policy from one trajectory possibly generated by some other policy. We briefly review on-policy learning algorithms of the literature (gradient-based and least-squares-based), adopting a unified algorithmic view. Then, we highlight a systematic approach for adapting them to off-policy learning with eligibility traces. This leads to some known algorithms—off-policy LSTD($\lambda$), LSPE($\lambda$), TD($\lambda$), TDC/GQ($\lambda$)—and suggests new extensions—off-policy FPKF($\lambda$), BRM($\lambda$), gBRM($\lambda$), GTD2($\lambda$). We describe a comprehensive algorithmic derivation of all algorithms in a recursive and memory-efficient form, discuss their known convergence properties and illustrate their relative empirical behavior on Garnet problems. Our experiments suggest that the most standard algorithms on and off-policy LSTD($\lambda$)/LSPE($\lambda$)—and TD($\lambda$) if the feature space dimension is too large for a least-squares approach—perform the best.
Introduction
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 task is notoriously difficult, especially when combined with linear function approximation to handle large state spaces and eligibility traces (controlled by a parameter $\lambda$) to balance bias and variance.
While many algorithms exist for simple on-policy learning, the literature on off-policy learning with traces has historically been fragmented. This paper bridges that gap by creating a universal "recipe" to upgrade existing algorithms into the off-policy, trace-enabled regime.
Methods: A Unified Algorithmic Framework
The authors categorize existing linear value function approximators along two axes: their objective (bootstrapping, residual, or projected fixed point) and their optimization strategy (gradient descent vs. least-squares).
The core methodological contribution is showing that these methods minimize a common squared-error cost function, differing only in their instantiation of a specific target parameter. To extend these to the off-policy setting with eligibility traces, the authors follow a systematic three-step recipe:
- Importance Sampling: Cumulative importance sampling weights ($\rho$) are introduced to correct for the mismatch between the behavior and target policies.
- The Forward View: The standard Bellman operator is replaced with a $\lambda$-weighted empirical Bellman operator that looks ahead at future rewards and states.
- The Backward View: To enable online learning, algebraic tricks (such as the Sherman-Morrison matrix identity) convert the "forward view" into an equivalent, recursive "backward view" that relies only on past data.
This mechanical derivation yields both known algorithms and entirely new extensions.
Empirical Evaluation and Key Results
The algorithms were evaluated on Garnet problems, which are randomly constructed, abstract finite Markov Decision Processes (MDPs). Testing across various state and action space sizes revealed several key insights:
- Least-Squares Dominance: Least-squares methods like 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 due to its $O(p)$ complexity.
- The Variance of Traces: In off-policy scenarios, higher values of $\lambda$ can severely hurt performance. Importance sampling weights multiply over time; longer traces lead to compounding variance that can destabilize learning. For LSTD/LSPE, the best performance was often found at $\lambda = 0$.
- Performance of New Algorithms: While the framework successfully derived new algorithms like GTD2($\lambda$), they were often empirically slower to converge than standard TD in the tested scenarios.
Conclusion and Future Work
This survey provides a unifying lens for linear value function estimation, turning the discovery of RL algorithms into a systematic mathematical process. However, significant theoretical gaps remain, particularly regarding convergence proofs for off-policy trace-based stochastic gradient algorithms under mild assumptions. Future work should also explore how these unified algorithms behave with non-linear approximations, such as deep neural networks, in complex real-world environments.
Summary updated