Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning

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. Focusing on the synchronous setting (such that independent samples for all state-action pairs are queried via a generative model in each iteration), substantial progress has been made recently towards understanding the sample efficiency of Q-learning. To yield an entrywise epsilon-accurate estimate of the optimal Q-function, state-of-the-art theory requires at least an order of vertical bar S vertical bar vertical bar A vertical bar/(1-gamma)(5)epsilon(2) samples in the infinite-horizon gamma-discounted setting. In this work, we sharpen the sample complexity of synchronous Q-learning to the order of vertical bar S vertical bar vertical bar A vertical bar/(1-gamma)(4)epsilon(2) (up to some logarithmic factor) for any 0 < epsilon < 1, leading to an order-wise improvement in 1/(1-gamma). Analogous results are derived for finite-horizon MDPs as well. Our sample complexity analysis unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage. Our result is obtained by identifying novel error decompositions and recursions, which might shed light on how to study other variants of Q-learning.