mlsanityData to 7 Oct 2026

Logarithmic Regret for Reinforcement Learning with Linear Function Approximation

arXiv 2011.11566 ↗First posted 23 Nov 2020cs.LG math.OC stat.MLcited by 79

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning (RL) with linear function approximation has received increasing attention recently. However, existing work has focused on obtaining √T-type regret bound, where T is the number of interactions with the MDP. In this paper, we show that logarithmic regret is attainable under two recently proposed linear MDP assumptions provided that there exists a positive sub-optimality gap for the optimal action-value function. More specifically, under the linear MDP assumption (Jin et al. 2019), the LSVI-UCB algorithm can achieve tildeO(d3H5/gapmin· log(T)) regret; and under the linear mixture MDP assumption (Ayoub et al. 2020), the UCRL-VTR algorithm can achieve tildeO(d2H5/gapmin· log3(T)) regret, where d is the dimension of feature mapping, H is the length of episode, gapmin is the minimal sub-optimality gap, and tilde O hides all logarithmic terms except log(T). To the best of our knowledge, these are the first logarithmic regret bounds for RL with linear function approximation. We also establish gap-dependent lower bounds for the two linear MDP models.

Key facts. Cited by 79 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Nov 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 23; 2022: 19; 2023: 12; 2024: 14; 2025: 9; 2026: 2.

79 papers.

Sort:

By area:

  1. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  2. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  3. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  4. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  5. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  6. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  7. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  8. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  9. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  10. 2024Reinforcement Learning from Human Feedback with Active Queriescited by 39
  11. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  12. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
38 more
  1. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  2. 2021Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learningcited by 33
  3. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  4. 2021Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learningcited by 29
  5. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  6. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  7. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  8. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  9. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  10. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  11. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  12. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  13. 2021Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex modelscited by 18
  14. 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
  15. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  16. 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
  17. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  18. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  19. 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
  20. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  21. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  22. 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
  23. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  24. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  25. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
  26. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  27. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithmcited by 10
  28. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  29. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  30. 2023Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regretcited by 9
  31. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  32. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  33. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  34. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  35. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  36. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
  37. 2024Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimizationcited by 6
  38. 2025Replicable Reinforcement Learning with Linear Function Approximationcited by 6

50 most cited of 79 All 79 (JSON)