Abstract
In this paper we derive convergence rates for Q-learning. We show an interesting relationship between the convergence rate and the learning rate used in the Q-learning. For a polynomial learning rate, one which is 1/t ω at time t where ω ε (1/2, 1), we show that that the convergence rate is polynomial in 1/(1 - γ), where γ is the discount factor. In contrast we show that for a linear learning rate, one which is 1/t at time t, the convergence rate has an exponential dependence on 1/(1 - γ). In addition we show a simple example that proves that this exponential behavior is inherent for a linear learning rate.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. Beleznay, T. Grobler, and Cs. Szepesvari. Comparing value-function estimation algorithms in undiscounted problems. Technical Report TR-99-02, Mindmaker Ltd, 1999.
V.S. Borkar and S.P. Meyn. The o.d.e method for convergence of stochstic approximation and reinforcement learning. Siam J. control, 38(2):447–69, 2000.
Dimitri P. Bertsekas and Jhon N. Tsitsklis. Neuro-Dynamic Programming. Athena Scientific, Belmont, MA, 1996.
T. Jaakkola, M.I. Jordan, and S.P. Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural Computation, 6, 1994.
Michael Kearns and Stinder Singh. Finite-sample convergence rates for qlearning and indirect algorithms. In Neural Information Processing Systems 10, 1998.
Littman M. and Cs. Szepesvari. A generalized reinforcement learning model: convergence and applications. In In International Conference on Machine Learning, 1996.
M.L Puterman. Markov Decision Processes-Discrete Stochastic Dynamic Programming. Jhon Wiley & Sons. Inc., New York, NY, 1994.
Richard S. Sutton and Andrew G. Bato. Reinforcement Learning. Mit press, 1998.
Cs. Szepesvari. The asymptotic convergence-rate of q-learning. In Neural Information Processing Systems 10, pages 1064–1070, 1997.
Jhon N. Tsitsklis. Asynchronous stochastic approximation and q-learning. Machine Learning, 16:185–202, 1994.
C. Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge University, 1989.
C. Watking and P. Dyan. Q-learning. Machine Learning, 8(3/4):279–292, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Even-Dar, E., Mansour, Y. (2001). Learning Rates for Q-Learning. In: Helmbold, D., Williamson, B. (eds) Computational Learning Theory. COLT 2001. Lecture Notes in Computer Science(), vol 2111. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44581-1_39
Download citation
DOI: https://doi.org/10.1007/3-540-44581-1_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42343-0
Online ISBN: 978-3-540-44581-4
eBook Packages: Springer Book Archive