Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis
复制标题
DOI：
10.1287/opre.2023.2450
复制
发表时间：
2021-02
影响因子：
2.7
通讯作者：
Gen Li;Ee;Changxiao Cai;Yuting Wei
中科院分区：
文献类型：
--
作者：
Gen Li;Ee;Changxiao Cai;Yuting Wei
本文研究了强化学习领域广泛关注的无模型算法，即 Q 学习。尽管近年来在理解 Q-learning 的样本效率方面取得了实质性进展，但在很大程度上仍不清楚 Q-learning 是否是样本最优以及如何提高 Q-learning 的样本复杂性分析。在本文中，我们解决了这些问题：（1）当只有一个动作时，我们证明 Q 学习（或者等效的 TD 学习）是可证明的极小极大最优。 (2) 当至少有两个动作时，我们的理论揭示了 Q 学习的严格次优性，并严格说明了 Q 学习中高估的负面影响。我们的理论适用于同步情况（即抽取独立样本的情况）和异步情况（即只能访问单个马尔可夫轨迹的情况）。
This paper investigates a model-free algorithm of broad interest in reinforcement learning, namely, Q-learning. Whereas substantial progress had been made toward understanding the sample efficiency of Q-learning in recent years, it remained largely unclear whether Q-learning is sample-optimal and how to sharpen the sample complexity analysis of Q-learning. In this paper, we settle these questions: (1) When there is only a single action, we show that Q-learning (or, equivalently, TD learning) is provably minimax optimal. (2) When there are at least two actions, our theory unveils the strict suboptimality of Q-learning and rigorizes the negative impact of overestimation in Q-learning. Our theory accommodates both the synchronous case (i.e., the case in which independent samples are drawn) and the asynchronous case (i.e., the case in which one only has access to a single Markovian trajectory).