Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction

Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP), based on a single trajectory of Markovian samples induced by a behavior policy. Focusing on a <inline-formula> <tex-math notation="LaTeX">$\gamma$ </tex-math></inline-formula>-discounted MDP with state space <inline-formula> <tex-math notation="LaTeX">$\mathcal {S}$ </tex-math></inline-formula> and action space <inline-formula> <tex-math notation="LaTeX">$\mathcal {A}$ </tex-math></inline-formula>, we demonstrate that the <inline-formula> <tex-math notation="LaTeX">$\ell _{\infty }$ </tex-math></inline-formula>-based sample complexity of classical asynchronous Q-learning — namely, the number of samples needed to yield an entrywise <inline-formula> <tex-math notation="LaTeX">$\varepsilon$ </tex-math></inline-formula>-accurate estimate of the Q-function — is at most on the order of <inline-formula> <tex-math notation="LaTeX">$\frac {1}{ \mu _{\mathsf {min}}(1-\gamma)^{5}\varepsilon ^{2}}+ \frac { t_{\mathsf {mix}}}{ \mu _{\mathsf {min}}(1-\gamma)}$ </tex-math></inline-formula> up to some logarithmic factor, provided that a proper constant learning rate is adopted. Here, <inline-formula> <tex-math notation="LaTeX">$t_{\mathsf {mix}}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\mu _{\mathsf {min}}$ </tex-math></inline-formula> denote respectively the mixing time and the minimum state-action occupancy probability of the sample trajectory. The first term of this bound matches the sample complexity in the synchronous case with independent samples drawn from the stationary distribution of the trajectory. The second term reflects the cost taken for the empirical distribution of the Markovian trajectory to reach a steady state, which is incurred at the very beginning and becomes amortized as the algorithm runs. Encouragingly, the above bound improves upon the state-of-the-art result by a factor of at least <inline-formula> <tex-math notation="LaTeX">$|\mathcal {S}||\mathcal {A}|$ </tex-math></inline-formula> for all scenarios, and by a factor of at least <inline-formula> <tex-math notation="LaTeX">$t_{\mathsf {mix}}|\mathcal {S}||\mathcal {A}|$ </tex-math></inline-formula> for any sufficiently small accuracy level <inline-formula> <tex-math notation="LaTeX">$\varepsilon$ </tex-math></inline-formula>. Further, we demonstrate that the scaling on the effective horizon <inline-formula> <tex-math notation="LaTeX">$\frac {1}{1-\gamma }$ </tex-math></inline-formula> can be improved by means of variance reduction.