Introduction
Batch Reinforcement Learning (also known as Offline RL) aims to learn optimal policies from fixed, pre-collected datasets without further environmental interaction. To manage high-dimensional or complex environments, researchers rely on function approximation, mapping a set of features to action values.
However, a persistent challenge is the "curse of dimensionality": the sample size required to learn an accurate policy typically scales linearly with the total number of candidate features ($d$). If an environment has thousands of candidate features but only a handful are actually relevant, standard methods still demand massive datasets to account for all of them. This paper investigates whether we can make sample complexity depend strictly on the number of relevant features ($s$) rather than the ambient dimension ($d$), leveraging sparse learning techniques to break the curse of dimensionality.
Methodology
The authors propose three primary algorithms that integrate sparsity into the RL pipeline:
- Lasso Fitted Q-Evaluation (Lasso-FQE): An iterative method for Off-Policy Evaluation (OPE) that applies $\ell_1$-regularization (Lasso) during the value function regression step to filter out irrelevant features.
- Post Model-Selection Fitted Q-Evaluation: A two-stage approach designed to mitigate the inherent shrinkage bias of Lasso. It first uses Group Lasso to identify "active" features, followed by a standard unregularized refit using only that subset.
- Lasso-Regularized Fitted Q-Iteration: An extension of the sparse approach from policy evaluation to policy optimization, actively finding an optimal policy rather than just evaluating a fixed one.
While primarily a theoretical contribution, the authors validate their algorithms on the classic Mountain Car benchmark. They utilized 800 radial basis functions (RBFs) as candidate features and collected datasets ranging from 2 to 100 episodes using various behavior policies with differing noise levels.
Key Insights
- Dimension Independence: The most significant theoretical insight is that the error bounds exhibit no polynomial dependence on the ambient dimension $d$. Instead, they scale with $\log(d)$. This implies that thousands of irrelevant features can be introduced without severely degrading performance, provided the underlying structure is sparse.
- Data Quality and the Restricted Minimal Eigenvalue: The analysis emphasizes that sample efficiency is not solely about data volume, but data quality—specifically, how well the dataset covers the relevant feature space. This is captured mathematically by the restricted minimal eigenvalue of the data's covariance matrix.
- Mitigating Distribution Mismatch: A major hurdle in Offline RL is the distribution mismatch between the behavior policy data and the target policy. Sparse feature selection effectively reduces this mismatch by constraining the comparison to a smaller, more manageable feature subspace.
- The Advantage of Refitting: The authors confirm that identifying features first and then refitting (Algorithm 2) performs strictly better than using a single-stage Lasso, as it eliminates the shrinkage bias that Lasso often introduces.
Results
- Theoretical Efficiency: The paper proves that the policy evaluation error scales approximately as $s \sqrt{\log d / N}$ (where $s$ is the number of relevant features and $N$ is the sample size). This is a massive improvement over the standard $\sqrt{d/N}$ scaling.
- Minimax Optimality: The authors establish minimax lower bounds, proving that their upper bounds are nearly tight. This indicates that no algorithm can perform significantly better under these specific sparse conditions.
- Empirical Validation: In the Mountain Car experiments, Lasso-FQE consistently achieved lower estimation errors than standard FQE (which relies on Ridge regression) in data-limited regimes. Furthermore, empirical results confirmed that the restricted chi-square divergence sharply dictates the error of sparse OPE, aligning perfectly with theoretical predictions.
Limitations and Future Directions
- Policy Completeness: The theoretical guarantees rely on a "Policy Completeness" assumption, meaning the sparse feature class is closed under the Bellman operator. This may only hold approximately in real-world scenarios.
- Linear Function Approximation: The current work is restricted to linear models. Extending these sparsity guarantees to non-linear architectures, such as deep neural networks, remains a significant open challenge for the field.
- Signal Strength: The post-selection method requires a minimal signal strength assumption. If the coefficients of relevant features are too small to be distinguished from background noise, the initial selection step may fail to identify them.
Summary updated