mlsanityData to 7 Oct 2026

A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost

arXiv 2101.00494 ↗First posted 2 Jan 2021cs.LG cs.AI stat.MLcited by 38

Not on the map. Why?

Abstract (arXiv)

Many real-world applications, such as those in medical domains, recommendation systems, etc, can be formulated as large state space reinforcement learning problems with only a small budget of the number of policy changes, i.e., low switching cost. This paper focuses on the linear Markov Decision Process (MDP) recently studied in [Yang et al 2019, Jin et al 2020] where the linear function approximation is used for generalization on the large state space. We present the first algorithm for linear MDP with a low switching cost. Our algorithm achieves an widetildeOleft(√d3H4Kright) regret bound with a near-optimal Oleft(d Hlog Kright) global switching cost where d is the feature dimension, H is the planning horizon and K is the number of episodes the agent plays. Our regret bound matches the best existing polynomial algorithm by [Jin et al 2020] and our switching cost is exponentially smaller than theirs. When specialized to tabular MDP, our switching cost bound improves those in [Bai et al 2019, Zhang et al 20020]. We complement our positive result with an Omegaleft(dH/log dright) global switching cost lower bound for any no-regret algorithm.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). Builds on 33 of its 54 references that are in the map. First posted on arXiv 2 Jan 2021.

Builds on

33 of 54 references.

References · 33

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  12. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
21 more
  1. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  2. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  3. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  4. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  5. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  6. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  7. 2018Deep Reinforcement Learning for Page-wise Recommendationscited by 99
  8. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  9. 2017Device Placement Optimization with Reinforcement Learningcited by 84
  10. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  11. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  12. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  13. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 60
  14. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  15. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 53
  16. 2017Applications of Deep Learning and Reinforcement Learning to Biological Datacited by 45
  17. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  18. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  19. 2018Learning to Optimize Join Queries With Deep Reinforcement Learningcited by 32
  20. 2020Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexitycited by 19
  21. 2020Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learningcited by 2

Built on by

Cited by year

Citing papers per year: 2021: 8; 2022: 13; 2023: 11; 2024: 3; 2025: 3.

38 papers.

Sort:

By area:

  1. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  2. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  3. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  4. 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
  5. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  6. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  7. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  8. 2022Learn to Match with No Regret: Reinforcement Learning in Markov Matching Marketscited by 16
  9. 2021Sublinear Least-Squares Value Iteration via Locality Sensitive Hashingcited by 15
  10. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  11. 2022Byzantine-Robust Online and Offline Distributed Reinforcement Learningcited by 13
  12. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
26 more
  1. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  2. 2021Differentially Private Exploration in Reinforcement Learning with Linear Representationcited by 11
  3. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  4. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  5. 2022Improved Regret for Differentially Private Exploration in Linear MDPcited by 8
  6. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  7. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  8. 2023A Reduction-based Framework for Sequential Decision Making with Delayed Feedbackcited by 7
  9. 2023Low-Switching Policy Gradient with Exploration via Online Sensitivity Samplingcited by 6
  10. 2023A General Framework for Sequential Decision-Making under Adaptivity Constraintscited by 6
  11. 2021Dealing with Non-Stationarity in MARL via Trust-Region Decompositioncited by 5
  12. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  13. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  14. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  15. 2024Batched Nonparametric Contextual Banditscited by 3
  16. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  17. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2
  18. 2022Provably Efficient Lifelong Reinforcement Learning with Linear Function Approximationcited by 2
  19. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  20. 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 2
  21. 2021Online Sub-Sampling for Reinforcement Learning with General Function Approximationcited by 1
  22. 2022A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Designcited by 1
  23. 2024To Switch or Not to Switch? Balanced Policy Switching in Offline Reinforcement Learningcited by 1
  24. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  25. 2021A Benchmark for Low-Switching-Cost Reinforcement Learningcited by 0
  26. 2025The Adaptivity Barrier in Batched Nonparametric Bandits: Sharp Characterization of the Price of Unknown Margincited by 0