Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
This work addresses the problem of efficient learning in large-scale reinforcement learning tasks for researchers and practitioners, providing a provably near-optimal algorithm without strong assumptions like ergodicity.
The paper tackles reinforcement learning for discounted Markov Decision Processes with feature mapping, proposing a novel algorithm that achieves a $ ilde O(d\sqrt{T}/(1-\gamma)^2)$ regret bound, which is near-optimal up to a $(1-\gamma)^{-0.5}$ factor compared to a lower bound of $\Omega(d\sqrt{T}/(1-\gamma)^{1.5})$.
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-γ)^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 $Ω(d\sqrt{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.