A Dantzig Selector Approach to Temporal Difference Learning

Matthieu Geist, Bruno Scherrer, Alessandro Lazaric, Mohammad Ghavamzadeh

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:

  1. 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.
  2. 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).

Solution paths for LASSO-TD, D-LSTD, and l1-LSTD in on-policy and off-policy settings.

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.

Performance comparison as the number of irrelevant features increases.

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

Abstract

LSTD is a popular algorithm for value function approximation. Whenever the number of features is larger than the number of samples, it must be paired with some form of regularization. In particular, l1-regularization methods tend to perform feature selection by promoting sparsity, and thus, are well-suited for high-dimensional problems. However, since LSTD is not a simple regression algorithm, but it solves a fixed-point problem, its integration with l1-regularization is not straightforward and might come with some drawbacks (e.g., the P-matrix assumption for LASSO-TD). In this paper, we introduce a novel algorithm obtained by integrating LSTD with the Dantzig Selector. We investigate the performance of the proposed algorithm and its relationship with the existing regularized approaches, and show how it addresses some of their drawbacks.
BibTeX
@inproceedings{geist2012dantzig,
  author = {Matthieu Geist and Bruno Scherrer and Alessandro Lazaric and Mohammad Ghavamzadeh},
  title = {{A Dantzig Selector Approach to Temporal Difference Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
  doi = {10.48550/arxiv.1206.6480},
}
Figure