0
$\begingroup$

The convergence criteria of Q-Learning state that the learning rate parameter $\alpha$ must satisfy the conditions: $$\sum_k \alpha_{n^k(s,a)} =\infty \quad \text{and}\quad \sum_k \alpha_{n^k(s,a)}^{2} <\infty \quad \forall s \in \mathcal{S}$$ where $n_k(s,a)$ denotes the $k^\text{th}$ time $(s,a)$ is visited

Why can a constant $\alpha$ be used in practice?

$\endgroup$
  • $\begingroup$ Why wouldn't you be able to? There's nothing in the above two conditions that says $\alpha$ has to change as $n_k(s,a)$ changes. $\endgroup$ – jbowman Feb 27 at 20:37
  • $\begingroup$ Sorry, I should have also added $0 \leq \alpha_{n_k(s,a)}\leq 1$. If alpha is constant and non-zero then both sums diverge. I may be missing the point of what you are saying though. $\endgroup$ – KaneM Feb 27 at 20:50
1
$\begingroup$

The same question can be asked in principle for any machine learning method. We almost never decay the step-size, and in fact we often use optimizers (like ADAM) that have errors in their proof of convergence. In fact, we continue to use ADAM instead of alternatives that correct this deficiency and provably converge (see here).

Why the discrepancy? Perhaps convergence is not something that matters too much in practice. It's still important to be sure, but I would rather have something that is quickly able to reach a small region of the optimum and never converge than something that guarantees convergence in an unachievable limit. I think this is the key point as well. An algorithm that converges with a decaying step-size will still get close to a local optimum with a constant step-size. However, the constant step-size will determine how close one can get before oscillating around said optimum.

The problem with such a set-up is that it is hard to analyze. What can be said about the finite-time analysis of algorithms in the average case? Not much. A convergence proof is easy to show in comparison.

You can also read a similar discussion in Chapter 2, page 33 of Sutton's RL book. Although the chapter is on bandits and not on Q-learning, Sutton discusses that constant step-sizes can be good in non-stationary problems, where convergence is not really desirable.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.