Learning Rates for Q-learning

Eyal Even-Dar, Yishay Mansour

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.
BibTeX
@article{evendar2003learning,
  author = {Eyal Even-Dar and Yishay Mansour},
  title = {{Learning Rates for Q-learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2003},
  url = {https://openreview.net/forum?id=OdySCq7LJUY},
}

Loading related content...

Figure