Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP
复制标题
DOI：
--
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Kefan Dong;Yuanhao Wang;Xiaoyu Chen;Liwei Wang
中科院分区：
文献类型：
--
作者：
Kefan Dong;Yuanhao Wang;Xiaoyu Chen;Liwei Wang
强化学习中的一个基本问题是无模型算法是否具有样本效率。最近，Jin等人\cite{jin2018q}提出了一种带UCB探索策略的Q-learning算法，并证明了该算法对于有限视界情景MDP具有近似最优后悔界。在本文中，我们在不访问生成模型的\emph{情况下}，将具有ucb探索奖励的q学习应用于具有折扣奖励的无限视界MDP。我们表明，我们的算法的\textit{探索的样本复杂度}是由$\tilde{O}({\frac{SA}{\epsilon^2(1-\gamma)^7}})$限定的。这改进了之前最著名的结果$\tilde{O}({\frac{SA}{\epsilon^4(1-\gamma)^8}})$在这种情况下通过延迟q学习\cite{strehl2006pac}获得的结果，并且在$\epsilon$以及$S$和$A$方面匹配下界，除了对数因素。
A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. \cite{jin2018q} proposed a Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with UCB-exploration bonus to infinite-horizon MDP with discounted rewards \emph{without} accessing a generative model. We show that the \textit{sample complexity of exploration} of our algorithm is bounded by $\tilde{O}({\frac{SA}{\epsilon^2(1-\gamma)^7}})$. This improves the previously best known result of $\tilde{O}({\frac{SA}{\epsilon^4(1-\gamma)^8}})$ in this setting achieved by delayed Q-learning \cite{strehl2006pac}, and matches the lower bound in terms of $\epsilon$ as well as $S$ and $A$ except for logarithmic factors.