Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
Not on the map. Why?
Abstract (arXiv)
Modern tasks in reinforcement learning have large state and action spaces. To deal with them efficiently, one often uses predefined feature mapping to represent states and actions in a low-dimensional space. In this paper, we study reinforcement learning for discounted Markov Decision Processes (MDPs), where the transition kernel can be parameterized as a linear function of certain feature mapping. We propose a novel algorithm that makes use of the feature mapping and obtains a tilde O(d√T/(1-γ)2) regret, where d is the dimension of the feature space, T is the time horizon and γ is the discount factor of the MDP. To the best of our knowledge, this is the first polynomial regret bound without accessing the generative model or making strong assumptions such as ergodicity of the MDP. By constructing a special class of MDPs, we also show that for any algorithms, the regret is lower bounded by Omega(d√T/(1-γ)1.5). Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a (1-γ)-0.5 factor.
Key facts. Cited by 102 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Jun 2020.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2020: 1; 2021: 27; 2022: 31; 2023: 25; 2024: 10; 2025: 5; 2026: 3.
102 papers.
Sort:
By area:
- 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
- 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
- 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
- 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
- 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
- 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
- 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
- 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
38 more
- 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
- 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
- 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
- 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
- 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
- 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
- 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
- 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
- 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
- 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
- 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
- 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
- 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
- 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
- 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
- 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
- 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
- 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
- 2021Efficient Local Planning with Linear Function Approximationcited by 21
- 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
- 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
- 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
- 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
- 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
- 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
- 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
- 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
- 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
- 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
- 2021Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximationcited by 15
- 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
- 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
- 2021PC-MLP: Model-based Reinforcement Learning with Policy Cover Guided Explorationcited by 14
- 2021Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDPcited by 14
- 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
- 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
- 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
- 2021Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processescited by 13
50 most cited of 102 All 102 (JSON)
- 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost31 Aug 2026
- 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning7 Aug 2026
- 2026Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs19 May 2026
- 2025Replicable Reinforcement Learning with Linear Function Approximation10 Sep 2025
- 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimation4 Aug 2025
- 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration2 Jun 2025
- 2025Linear Mixture Distributionally Robust Markov Decision Processes23 May 2025
- 2025Reinforcement Learning from Multi-level and Episodic Human Feedback20 Apr 2025
- 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Framework31 Oct 2024
- 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm30 Oct 2024
- 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span19 Oct 2024
- 2024A Factored MDP Approach To Moving Target Defense With Dynamic Threat Modeling and Cost Efficiency16 Aug 2024
38 more
- 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error18 Jul 2024
- 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning10 Jul 2024
- 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes3 Jul 2024
- 2024Thompson Sampling for Infinite-Horizon Discounted Decision Processes14 May 2024
- 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation19 Apr 2024
- 2024Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path14 Feb 2024
- 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation26 Nov 2023
- 2023Anytime-Competitive Reinforcement Learning with Policy Prior2 Nov 2023
- 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation29 Oct 2023
- 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration24 Oct 2023
- 2023Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement Learning in Discounted Linear MDPs17 Oct 2023
- 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiency29 Sep 2023
- 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processes28 Aug 2023
- 2023Provably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback6 Jul 2023
- 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Time24 May 2023
- 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes15 May 2023
- 2023Uniform-PAC Guarantees for Model-Based RL with Bounded Eluder Dimension15 May 2023
- 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation10 May 2023
- 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning18 Apr 2023
- 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs17 Mar 2023
- 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPs10 Mar 2023
- 2023Probe: Learning Users' Personalized Projection Bias in Intertemporal Choices9 Mar 2023
- 2023Optimistic Planning by Regularized Dynamic Programming27 Feb 2023
- 2023Exponential Hardness of Reinforcement Learning with Linear Function Approximation25 Feb 2023
- 2023Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space21 Feb 2023
- 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency21 Feb 2023
- 2023Reinforcement Learning with Function Approximation: From Linear to Nonlinear20 Feb 2023
- 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints8 Feb 2023
- 2023Sample Complexity of Kernel-Based Q-Learning1 Feb 2023
- 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation30 Jan 2023
- 2023Refined Regret for Adversarial MDPs with Linear Function Approximation30 Jan 2023
- 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximation27 Dec 2022
- 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes12 Dec 2022
- 2022On the Global Convergence of Fitted Q-Iteration with Two-layer Neural Network Parametrization14 Nov 2022
- 2022Leveraging Offline Data in Online Reinforcement Learning9 Nov 2022
- 2022Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPs27 Oct 2022
- 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity18 Oct 2022
- 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient3 Oct 2022
50 newest of 102 All 102 (JSON)
- 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
- 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
- 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficientcited by 24
- 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
- 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
- 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximationcited by 11
- 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
- 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning10 Jul 2024
- 2022Leveraging Offline Data in Online Reinforcement Learning9 Nov 2022
- 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient3 Oct 2022
- 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar 2022
- 2021Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation19 Aug 2021
- 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL22 Jun 2021
- 2020Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient8 Nov 2020
- 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
- 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
- 2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
- 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
- 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
- 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
- 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
- 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
- 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
- 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
- 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
- 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
12 most cited of 92 All 92 (JSON)
- 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost31 Aug 2026
- 2026Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning7 Aug 2026
- 2026Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs19 May 2026
- 2025Replicable Reinforcement Learning with Linear Function Approximation10 Sep 2025
- 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimation4 Aug 2025
- 2025Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration2 Jun 2025
- 2025Linear Mixture Distributionally Robust Markov Decision Processes23 May 2025
- 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Framework31 Oct 2024
- 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm30 Oct 2024
- 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span19 Oct 2024
- 2024A Factored MDP Approach To Moving Target Defense With Dynamic Threat Modeling and Cost Efficiency16 Aug 2024
- 2024Misspecified Q-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error18 Jul 2024
12 newest of 92 All 92 (JSON)