Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Dongruo Zhou;Jiafan He;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Dongruo Zhou;Jiafan He;Quanquan Gu
强化学习中的现代任务往往具有较大的状态空间和动作空间。为了有效地处理它们，人们通常使用预定义的特征映射来表示低维空间中的状态和动作。本文研究折扣马尔可夫决策过程(MDP)的特征映射强化学习。我们提出了一种新的算法，该算法利用特征映射，得到了一个O(dSQRT{T}/(1-Gamma)^2)$遗憾，其中$d$是特征空间的维度，$T$是MDP的时间范围，$\Gamma$是MDP的折扣率。就我们所知，这是第一个多项式后悔界限，没有使用生成模型，也没有做出像MDP遍历性这样的强假设。通过构造一类特殊的MDP，我们还证明了对于任何算法，遗憾的下界是$\Omega(d\Sqrt{T}/(1-\Gamma)^{1.5})$。我们的上界和下界结果表明，所提出的强化学习算法在$(1-\Gamma)^{-0.5}$因子下是近最优的。
Modern tasks in reinforcement learning are always with large state and action spaces. To deal with them efficiently, one often uses predefined feature mapping to represents states and actions in a low dimensional space. In this paper, we study reinforcement learning with feature mapping for discounted Markov Decision Processes (MDPs). We propose a novel algorithm which 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 to a 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.