Abstract
This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candidate features, our result sheds light on the fact that sparsity-aware methods can make batch RL more sample efficient. We first consider the off-policy policy evaluation problem. To evaluate a new target policy, we analyze a Lasso fitted Q-evaluation method and establish a finite-sample error bound that has no polynomial dependence on the ambient dimension. To reduce the Lasso bias, we further propose a post model-selection estimator that applies fitted Q-evaluation to the features selected via group Lasso. Under an additional signal strength assumption, we derive a sharper instance-dependent error bound that depends on a divergence function measuring the distribution mismatch between the data distribution and occupancy measure of the target policy. Further, we study the Lasso fitted Q-iteration for batch policy optimization and establish a finite-sample error bound depending on the ratio between the number of relevant features and restricted minimal eigenvalue of the data's covariance. In the end, we complement the results with minimax lower bounds for batch-data policy evaluation/optimization that nearly match our upper bounds. The results suggest that having well-conditioned data is crucial for sparse batch policy learning.
Introduction
Batch reinforcement learning (RL), or offline RL, focuses on learning optimal policies from fixed historical datasets without further environment interaction. This paradigm is essential for applications in healthcare, autonomous driving, and finance, where active exploration is often prohibitively expensive or unethical. However, batch RL frequently encounters the "curse of dimensionality": as the number of features ($d$) increases, standard theory suggests that the sample complexity required for accurate value estimation grows linearly with $d$.
In many practical scenarios, the underlying system dynamics may depend on only a small subset of the available features. This paper addresses the challenge of high-dimensional batch RL by leveraging sparsity. The authors demonstrate that by integrating Lasso-based regularization, it is possible to achieve sample complexity bounds that depend primarily on the number of relevant features ($s$) rather than the ambient dimension ($d$), effectively breaking the curse of dimensionality in sparse environments.
Sparse Linear MDPs and Methodology
The theoretical foundation of this work rests on the concept of Sparse Linear MDPs. In this framework, the transition kernel and reward function are assumed to be representable as linear combinations of a small subset of basis functions. To exploit this structure, the authors propose three primary algorithmic approaches:
- Lasso Fitted Q-Evaluation (Lasso-FQE): This method adapts standard policy evaluation by incorporating $\ell_1$-regularization into the iterative regression steps. By penalizing the complexity of the value function, Lasso-FQE identifies the most predictive features at each iteration, effectively filtering out noise from irrelevant dimensions.
- Post Model-Selection Fitted Q-Evaluation: While Lasso is effective for feature selection, it introduces a "shrinkage bias" that can degrade estimation accuracy. To mitigate this, the authors propose a two-stage estimator. First, Group Lasso is employed to identify the relevant feature support across the entire dataset. Second, a standard, unregularized fitted Q-evaluation is performed using only the selected features, resulting in a sharper, instance-dependent error bound.
- Lasso Fitted Q-Iteration (Lasso-FQI): Extending the sparse selection principle to policy optimization, Lasso-FQI seeks to find the optimal policy. The authors establish finite-sample error bounds for this approach that depend on the ratio between the number of relevant features and the restricted minimal eigenvalue of the data's covariance matrix.
Theoretical Insights and Key Results
A significant contribution of this research is the derivation of error bounds that are nearly independent of the ambient dimension. Specifically, the estimation error scales with $s \log(d)$ rather than $d$. This logarithmic dependence on the total number of features allows for efficient learning even in extremely high-dimensional spaces, provided the underlying signal is sparse.
Furthermore, the paper explores the impact of distribution mismatch. In batch RL, the data distribution (behavior policy) often differs from the occupancy measure of the target policy. The authors show that sparse feature selection relaxes the requirements for data coverage; the behavior policy only needs to sufficiently cover the relevant feature space, a much weaker condition than requiring full coverage of the high-dimensional ambient space.
To establish the fundamental limits of the problem, the authors provide minimax lower bounds. These bounds represent the theoretical "speed limit" of what any algorithm could achieve. The proximity of the proposed algorithms' performance to these lower bounds suggests that Lasso-based methods are nearly optimal for sparse batch RL.
Empirical Validation
The authors validated their theoretical findings using the Mountain Car environment, a standard benchmark in RL. To simulate a high-dimensional setting, they expanded the state space using 800 radial basis functions (RBFs). The experiments compared Lasso-FQE against standard FQE. The results demonstrated that Lasso-FQE achieved significantly lower estimation errors as the number of episodes increased, confirming that feature selection effectively combats the noise introduced by irrelevant RBFs and improves sample efficiency in practice.
Conclusion and Future Work
This work provides a rigorous theoretical and algorithmic framework for high-dimensional batch RL. By proving that sample efficiency can scale with the number of relevant features, the authors offer a path forward for applying RL to complex, "kitchen-sink" datasets where only a fraction of the data is truly predictive.
However, several avenues for future research remain. The current results rely on the Sparse Linear MDP assumption; extending these guarantees to non-linear or dense environments remains a challenge. Additionally, while the bounds for policy evaluation are tight, a gap of $\sqrt{s/C_{min}}$ remains in the optimization bounds. Finally, the computational cost of iterative Lasso procedures in very high dimensions warrants further optimization to ensure these methods are as computationally efficient as they are sample efficient.
Summary updated