Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning
Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Gen Li;Changxiao Cai;Yuxin Chen;Yuantao Gu;Yuting Wei;Yuejie Chi
中科院分区：
文献类型：
--
作者：
Gen Li;Changxiao Cai;Yuxin Chen;Yuantao Gu;Yuting Wei;Yuejie Chi
Q 学习旨在以无模型的方式学习马尔可夫决策过程 (MDP) 的最优 Q 函数，它是强化学习的核心。当谈到同步设置时（例如，在每次迭代中从生成模型中抽取所有状态-动作对的独立样本），最近在理解 Q 学习的样本效率方面取得了实质性进展。为了产生最优 Q 函数的 $\varepsilon$ 准确估计，最先进的理论至少需要 $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^5\varepsilon^{2}}$ 阶样本，用于具有状态空间 $\mathcal{S}$ 和动作空间的 $\gamma$ 折扣无限范围 MDP $\mathcal{A}$。在这项工作中，我们将任何 $0<\varepsilon <1$ 的同步 Q 学习的样本复杂度锐化到 $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^4\varepsilon^2}$ 的数量级（达到某个对数因子），从而导致有效范围 $\frac{1}{1-\gamma}$ 方面的有序改进。对于有限范围 MDP 也得出了类似的结果。我们的发现揭示了普通 Q 学习的有效性，它与快速 Q 学习的效果相匹配，而不需要额外的计算和存储。我们分析的一个关键要素在于建立新颖的错误分解和递归，这可能有助于分析其他 Q 学习变体的有限样本性能。
Q-learning, which seeks to learn the optimal Q-function of a Markov decision process (MDP) in a model-free fashion, lies at the heart of reinforcement learning. When it comes to the synchronous setting (such that independent samples for all state-action pairs are drawn from a generative model in each iteration), substantial progress has been made recently towards understanding the sample efficiency of Q-learning. To yield an entrywise $\varepsilon$-accurate estimate of the optimal Q-function, state-of-the-art theory requires at least an order of $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^5\varepsilon^{2}}$ samples for a $\gamma$-discounted infinite-horizon MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$. In this work, we sharpen the sample complexity of synchronous Q-learning to an order of $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^4\varepsilon^2}$ (up to some logarithmic factor) for any $0<\varepsilon <1$, leading to an order-wise improvement in terms of the effective horizon $\frac{1}{1-\gamma}$. Analogous results are derived for finite-horizon MDPs as well. Our finding unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage. A key ingredient of our analysis lies in the establishment of novel error decompositions and recursions, which might shed light on how to analyze finite-sample performance of other Q-learning variants.