# Logarithmic Regret for Reinforcement Learning with Linear Function Approximation

arXiv: https://arxiv.org/abs/2011.11566 · HTML: https://mlsanity.com/paper/2011.11566/

## Key facts

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

## Built on by (most cited first, 30 of 79)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Leveraging Offline Data in Online Reinforcement Learning](https://mlsanity.com/paper/2211.04974/) (2022)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach](https://mlsanity.com/paper/2112.03432/) (2021)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/2107.01264/) (2021)
- [Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps](https://mlsanity.com/paper/2203.13935/) (2022)
- [Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design](https://mlsanity.com/paper/2207.02575/) (2022)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2102.08940/) (2021)
- [Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting](https://mlsanity.com/paper/2105.08024/) (2021)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation](https://mlsanity.com/paper/2402.15399/) (2024)
- [Learning Stochastic Shortest Path with Linear Function Approximation](https://mlsanity.com/paper/2110.12727/) (2021)
- [Differentially Private Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2201.07052/) (2022)
- [On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2211.13208/) (2022)
- [Exploration-exploitation trade-off for continuous-time episodic reinforcement learning with linear-convex models](https://mlsanity.com/paper/2112.10264/) (2021)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection](https://mlsanity.com/paper/2110.14798/) (2021)
- [Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learning](https://mlsanity.com/paper/2202.10678/) (2022)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation](https://mlsanity.com/paper/2105.01593/) (2021)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)

## 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.