Introduction
In Reinforcement Learning (RL), estimating the expected future reward—the value function—is a foundational task. When dealing with massive state spaces, practitioners rely on linear approximation, representing the value function as a weighted sum of features. The standard algorithm for this is Least-Squares Temporal Difference (LSTD) learning.
However, LSTD struggles in high-dimensional regimes where the number of features far exceeds the number of data samples ($p \gg n$). To prevent overfitting, researchers typically apply $\ell_1$-regularization (like LASSO) to promote sparsity, effectively isolating the most important features. While the current state-of-the-art, LASSO-TD, is effective, it suffers from significant theoretical and practical drawbacks. This paper introduces Dantzig-LSTD (D-LSTD), a novel approach that combines LSTD with the Dantzig Selector to provide a robust, convex alternative that handles high-dimensional features without restrictive assumptions.
The Problem with LASSO-TD
Integrating $\ell_1$-regularization with LSTD is not as simple as applying it to standard regression because LSTD solves a fixed-point problem. LASSO-TD attempts this integration but introduces two major headaches:
- The P-matrix Assumption: LASSO-TD only works reliably if the underlying system matrix possesses specific mathematical properties (the P-matrix assumption). In "off-policy" learning—where the agent learns from data gathered by a different policy—this assumption frequently fails, leading to unstable or non-existent solutions.
- Optimization Complexity: The resulting formulation is not a standard convex optimization problem, making it difficult to solve efficiently and analyze theoretically.
The D-LSTD Solution
Instead of forcing LASSO into the TD framework, the authors adapt the Dantzig Selector, a powerful tool originally developed for compressed sensing.
The D-LSTD formulation is elegant: it minimizes the $\ell_1$-norm of the weights (seeking the sparsest model) subject to a constraint that the "correlated Bellman residual" remains small. Specifically, the correlation between the features and the model error must fall below a threshold $\lambda$.
This approach yields several breakthrough advantages:
- Linear Programming: D-LSTD can be formulated as a standard Linear Program (LP), meaning it can be solved efficiently using off-the-shelf solvers.
- Convexity: It is a proper convex optimization problem, guaranteeing stability and simplifying theoretical analysis.
- No P-matrix Required: The mathematics hold up regardless of whether the setting is on-policy or off-policy.
Key Insights and Experimental Results
The authors evaluated D-LSTD on synthetic RL environments designed to stress-test sparse recovery, revealing several key strengths.
Off-Policy Stability
To test the algorithms in scenarios where the P-matrix assumption fails, the authors used a pathological two-state Markov Decision Process (MDP).
As demonstrated in the solution paths above, LASSO-TD becomes highly unstable in the off-policy setting, branching into multiple potential solutions. In contrast, D-LSTD produces a unique, well-defined solution path regardless of the policy setting, confirming its theoretical robustness.
High-Dimensional Noise Robustness
A critical theoretical guarantee of D-LSTD is that its error scales only logarithmically with the number of features ($\log p$). This means the algorithm can sift through thousands of irrelevant features with minimal performance degradation.
The authors tested this using a "Corrupted Chain" environment, injecting between 800 and 1,400 irrelevant noise features alongside a small set of useful radial basis functions.
The results starkly highlight the benefits of $\ell_1$-regularization in high dimensions. While standard $\ell_2$-regularized LSTD (Ridge) degrades significantly as noise features are added, D-LSTD remains remarkably flat and stable, successfully identifying the relevant features even with only 400 samples.
Solving the Cross-Validation Gap
A persistent challenge in RL is the lack of a standard "loss function" (like Mean Squared Error) to tune hyperparameters like the regularization penalty $\lambda$. The authors propose a heuristic ($J_2$) that uses a cross-validation-like approach on the Bellman residual. Experiments showed this heuristic is surprisingly effective, allowing D-LSTD to perform competitively with an "oracle" version of LASSO-TD that knows the optimal $\lambda$ in advance.
Limitations and Future Work
While D-LSTD presents a significant step forward for policy evaluation, challenges remain. The theoretical error bound contains a term related to the inverse Gram matrix ($L_\mu^\phi$) which could potentially grow in certain feature spaces, warranting further investigation. Additionally, the $J_2$ cross-validation heuristic, while empirically successful, currently lacks rigorous theoretical proof. Finally, the natural next step is to integrate D-LSTD beyond policy evaluation and into full policy iteration for active control tasks.
Summary updated