Finite-Time Analysis for Double Q-learning
  Although Q-learning is one of the most successful algorithms for finding the
best action-value function (and thus the optimal policy) in reinforcement
learning, its implementation often suffers from large overestimation of
Q-function values incurred by random sampling. The double Q-learning algorithm
proposed in~\citet{hasselt2010double} overcomes such an overestimation issue by
randomly switching the update between two Q-estimators, and has thus gained
significant popularity in practice. However, the theoretical understanding of
double Q-learning is rather limited. So far only the asymptotic convergence has
been established, which does not characterize how fast the algorithm converges.
In this paper, we provide the first non-asymptotic (i.e., finite-time) analysis
for double Q-learning. We show that both synchronous and asynchronous double
Q-learning are guaranteed to converge to an $\epsilon$-accurate neighborhood of
the global optimum by taking $\tilde{\Omega}\left(\left(
\frac{1}{(1-\gamma)^6\epsilon^2}\right)^{\frac{1}{\omega}}
+\left(\frac{1}{1-\gamma}\right)^{\frac{1}{1-\omega}}\right)$ iterations, where
$\omega\in(0,1)$ is the decay parameter of the learning rate, and $\gamma$ is
the discount factor. Our analysis develops novel techniques to derive
finite-time bounds on the difference between two inter-connected stochastic
processes, which is new to the literature of stochastic approximation.
