Logarithmic Regret for Reinforcement Learning with Linear Function Approximation

Abstract

Reinforcement learning (RL) with linear function approximation has received increasing attention recently. However, existing work has focused on obtaining $\sqrt{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 $\tilde{O}(d^3{H}^5/{\text{gap}}_{\text{min}}\cdot \log (T))$ regret; and under the linear mixture MDP assumption (Ayoub et al. 2020), the UCRL-VTR algorithm can achieve $\tilde{O}(d^2{H}^5/{\text{gap}}_{\text{min}}\cdot {\log }^3(T))$ regret, where $d$ is the dimension of feature mapping, $H$ is the length of episode, ${\text{gap}}_{\text{min}}$ 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.

26 pages

References in corpus (21)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Provably Efficient Reinforcement Learning with Linear Function Approximation
• Contextual Decision Processes with Low Bellman Rank are PAC-Learnable
• Model-Based Reinforcement Learning with Value-Targeted Regression
• Learning Near Optimal Policies with Low Inherent Bellman Error
• What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• On Lower Bounds for Regret in Reinforcement Learning
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition
• Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
• Provably Efficient $Q$-learning with Function Approximation via Distribution Shift Error Checking Oracle
• On Reward-Free Reinforcement Learning with Linear Function Approximation
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Exponential Lower Bounds for Planning in MDPs With Linearly-Realizable Optimal Action-Value Functions
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• $Q$-learning with Logarithmic Regret
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• On the Sample Complexity of Reinforcement Learning with Policy Space Generalization

Cited by in corpus (13)

• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Corruption-robust exploration in episodic reinforcement learning
• Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning
• Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap
• Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
• Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Gap-Dependent Unsupervised Exploration for Reinforcement Learning
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Gap-Dependent Bounds for Two-Player Markov Games