Learning Rates for Q-Learning
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 Q-learning. For a polynomial learning rate, one which is 1/tω at time t where ω∈(1/2,1), we show 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 this exponential behavior is inherent for linear learning rates.
Cite
Text
Dar and Mansour. "Learning Rates for Q-Learning." Journal of Machine Learning Research, 2003.Markdown
[Dar and Mansour. "Learning Rates for Q-Learning." Journal of Machine Learning Research, 2003.](https://mlanthology.org/jmlr/2003/dar2003jmlr-learning/)BibTeX
@article{dar2003jmlr-learning,
title = {{Learning Rates for Q-Learning}},
author = {Dar, Eyal Even and Mansour, Yishay},
journal = {Journal of Machine Learning Research},
year = {2003},
pages = {1-25},
volume = {5},
url = {https://mlanthology.org/jmlr/2003/dar2003jmlr-learning/}
}