Learning Rates for Q-learning

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. [abs] [ pdf ][ ps.gz ][ ps ]

Authors

• Eyal Even Dar
• Yishay Mansour School of Computer Science, Tel Aviv University Google Research, Tel Aviv

Keywords

No keywords are indexed for this paper.