mlsanityData to 14 Oct 2026

A Doubly Robust Approach to Sparse Reinforcement Learning

arXiv 2310.15286 ↗First posted 23 Oct 2023stat.ML cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

We propose a new regret minimization algorithm for episodic sparse linear Markov decision process (SMDP) where the state-transition distribution is a linear function of observed features. The only previously known algorithm for SMDP requires the knowledge of the sparsity parameter and oracle access to an unknown policy. We overcome these limitations by combining the doubly robust method that allows one to use feature vectors of all actions with a novel analysis technique that enables the algorithm to use data from all periods in all episodes. The regret of the proposed algorithm is tildeO(σ-1min sstar H √N), where σmin denotes the restrictive the minimum eigenvalue of the average Gram matrix of feature vectors, s_star is the sparsity parameter, H is the length of an episode, and N is the number of rounds. We provide a lower regret bound that matches the upper bound up to logarithmic factors on a newly identified subclass of SMDPs. Our numerical experiments support our theoretical results and demonstrate the superior performance of our algorithm.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 30 of its 70 references that are in the map. First posted on arXiv 23 Oct 2023.

Builds on

30 of 70 references.

References · 30

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  8. 2016Deep Reinforcement Learning for Dialogue Generationcited by 288
  9. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  10. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  11. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  12. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
18 more
  1. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  3. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  4. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  5. 2020High-Dimensional Sparse Linear Banditscited by 61
  6. 2019Doubly-Robust Lasso Banditcited by 49
  7. 2020Sparsity-Agnostic Lasso Banditcited by 44
  8. 2018Balanced Linear Contextual Banditscited by 30
  9. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  10. 2020Online Sparse Reinforcement Learningcited by 25
  11. 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
  12. 2021Doubly robust Thompson sampling for linear payoffscited by 21
  13. 2022PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Banditscited by 17
  14. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  15. 2022Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Banditscited by 14
  16. 2022Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Banditscited by 6
  17. 2023Learning the Pareto Front Using Bootstrapped Observation Samplescited by 5
  18. 2023Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedbackcited by 2

Built on by

Cited by year

Citing papers per year: 2025: 3.

3 papers.

  1. 2025Linear Bandits with Partially Observable Featurescited by 4
  2. 2025Aligning Learning and Endogenous Decision-Makingcited by 0
  3. 2025Sparse Offline Reinforcement Learning with Corruption Robustnesscited by 0