Timezone: »

 
Poster
Speedy Q-Learning
Mohammad Gheshlaghi Azar · Remi Munos · Mohammad Ghavamzadeh · Hilbert J Kappen

Mon Dec 12 10:00 AM -- 02:59 PM (PST) @
in Poster Session and Reception »

We introduce a new convergent variant of Q-learning, called speedy Q-learning, to address the problem of slow convergence in the standard form of the Q-learning algorithm. We prove a PAC bound on the performance of SQL, which shows that for an MDP with n state-action pairs and the discount factor \gamma only T=O\big(\log(n)/(\epsilon^{2}(1-\gamma)^{4})\big) steps are required for the SQL algorithm to converge to an \epsilon-optimal action-value function with high probability. This bound has a better dependency on 1/\epsilon and 1/(1-\gamma), and thus, is tighter than the best available result for Q-learning. Our bound is also superior to the existing results for both model-free and model-based instances of batch Q-value iteration that are considered to be more efficient than the incremental methods like Q-learning.

[ PDF] 

Author Information

Mohammad Gheshlaghi Azar (Radboud University of Nijmegen)
Remi Munos (Google DeepMind)
Mohammad Ghavamzadeh (Facebook AI Research)
Hilbert J Kappen (Radboud University)

More from the Same Authors