mlsanityData to 14 Oct 2026

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs

arXiv 2411.10906 ↗First posted 16 Nov 2024cs.LG cs.DScited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however, the space usage of this algorithm can be prohibitive due to a utilized linear regression step. We propose and analyze two modifications of LSVI-UCB, which alternate periods of learning and not-learning, to reduce space and time usage while maintaining sublinear regret. We show experimentally, on synthetic data and real-world benchmarks, that our algorithms achieve low space usage and running time, while not significantly sacrificing regret.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 22 of its 35 references that are in the map. First posted on arXiv 16 Nov 2024.

Builds on

22 of 35 references.

References · 22

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2014Sketching as a Tool for Numerical Linear Algebracited by 288
  6. 2017Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agentscited by 269
  7. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 203
  8. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  9. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  10. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  11. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  12. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
10 more
  1. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 28
  2. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  3. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  4. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  5. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
  6. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  7. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  8. 2022Reinforcement Learning and Bandits for Speech and Language Processing: Tutorial, Review and Outlookcited by 10
  9. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  10. 2023Genetic multi-armed bandits: a reinforcement learning approach for discrete optimization via simulationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Achieving Constant Regret in Linear Markov Decision Processes
  2. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPs
  3. 2024Sublinear Regret for a Class of Continuous-Time Linear-Quadratic Reinforcement Learning Problems
  4. 2024No-Regret Reinforcement Learning in Smooth MDPs
  5. 2024Horizon-Free Regret for Linear Markov Decision Processes
  6. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  7. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  8. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs