Timezone: »

 
Poster
Finite-Time Analysis for Double Q-learning
Huaqing Xiong · Lin Zhao · Yingbin Liang · Wei Zhang

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #356
in Poster Session 2 »
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.
Keywords: Natural Language Processing · Embedding Approaches · Applications · Deep Learning

Author Information

Huaqing Xiong (Ohio State University)
Lin Zhao (National University of Singapore)
Yingbin Liang (The Ohio State University)
Wei Zhang (Southern University of Science and Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors