Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping

Abstract

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\sqrt{T}/(1-\gamma {)}^2)$ regret, where $d$ is the dimension of the feature space, $T$ is the time horizon and $\gamma$ 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\sqrt{T}/(1-\gamma {)}^{1.5})$. Our upper and lower bound results together suggest that the proposed reinforcement learning algorithm is near-optimal up to a $(1-\gamma {)}^{-0.5}$ factor.

arXiv comment31 pages, 1 figure

References in corpus (13)

• 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
• Finite-Sample Analysis for SARSA with Linear Function Approximation
• 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
• Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?
• Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
• Comments on the Du-Kakade-Wang-Yang Lower Bounds
• Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles
• Regret Bounds for Discounted MDPs

Cited by in corpus (20)

• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes
• Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
• Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL
• Provably Efficient Exploration in Policy Optimization
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces
• MADE: Exploration via Maximizing Deviation from Explored Regions
• Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
• Robust Policy Gradient against Strong Data Corruption
• An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Near-optimal Representation Learning for Linear Bandits and Linear RL
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
• Online Sparse Reinforcement Learning
• Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs
• Efficient Local Planning with Linear Function Approximation
• Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP
• Gap-Dependent Bounds for Two-Player Markov Games