Learning Rates for Q-learning
Eyal Even-Dar, Yishay Mansour; 5(Dec):1--25, 2003.
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.
[abs][pdf][ps.gz][ps]