Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient

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.

References in corpus (16)

• Simultaneous analysis of Lasso and Dantzig selector
• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Least squares after model selection in high-dimensional sparse models
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation
• Consistent On-Line Off-Policy Evaluation
• Greedy Algorithms for Sparse Reinforcement Learning
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Minimax Weight and Q-Function Learning for Off-Policy Evaluation
• A Dantzig Selector Approach to Temporal Difference Learning
• Off-Policy Evaluation via the Regularized Lagrangian
• Exploration-Enhanced POLITEX
• Regularized Off-Policy TD-Learning
• Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning

Cited by in corpus (5)

• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Online Sparse Reinforcement Learning
• Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings