Online Sparse Reinforcement Learning

2020/11/08 by Botao Hao, Hao, Botao, Tor Lattimore +5 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2011.04018

openalex publication_date 2020/11/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the hardness of online reinforcement learning in fixed horizon, sparse linear Markov decision process (MDP), with a special focus on the high-dimensional regime where the ambient dimension is larger than the number of episodes. Our contribution is two-fold. First, we provide a lower bound showing that linear regret is generally unavoidable in this case, even if there exists a policy that collects well-conditioned data. The lower bound construction uses an MDP with a fixed number of states while the number of actions scales with the ambient dimension. Note that when the horizon is fixed to one, the case of linear stochastic bandits, the linear regret can be avoided. Second, we show that if the learner has oracle access to a policy that collects well-conditioned data then a variant of Lasso fitted Q-iteration enjoys a nearly dimension-free regret of O( s^2/3 N^2/3) where N is the number of episodes and s is the sparsity level. This shows that in the large-action setting, the difficulty of learning can be attributed to the difficulty of finding a good exploratory policy.

Citations

• A Dantzig Selector Approach to Temporal Difference Learning
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and\n Distribution Shift
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient

Cited by

• Learning Personalized Ad Impact via Contextual Reinforcement Learning under Delayed Rewards

Related

• Settling the Sample Complexity of Online Reinforcement Learning
• Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
• Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
• Fast Rates for the Regret of Offline Reinforcement Learning
• What can online reinforcement learning with function approximation benefit from general coverage conditions?