If $\alpha$ decreases over time, why is Q-learning guaranteed to converge?

Question

Q-Learning is guaranteed to converge if $\alpha$ decreases over time.

On page 161 of the RL book by Sutton and Barto, 2nd edition, section 8.1, they write that Dyna-Q is guaranteed to converge if each action-state pair is selected an infinite number of times and if $\alpha$ decreases appropriately over time.

It seems that it would be better if $\alpha$ increased over time, as it is the learning rate of the gradient of Q-function values ($R+\gamma\max_aQ(S',a)-Q(S,A)$), and, initially, they start off incredibly inaccurate, because they are initialized arbitrarily and over time converge to the true values, hence you'd want to weight them more as time increases rather than decrease it?

Why is this a convergence criterion?

Answer 1

Why is this a convergence criterion?

It is because $R$ and $S'$ are stochastic. A large learning rate applied when these values have variance would not converge to mean, but would wander around typically within some value proportional to $\alpha\sigma$ of the true value, where $\sigma$ is the standard deviation of the term $R + \gamma\text{max}_aQ(S',a)$. If you reduce $\alpha$ towards zero, then this expected error will also reduce to zero.

For deterministic environments, it should be possible to prove convergence with large $\alpha$.

---

In the special case of static policy, tabular learning and $\alpha = \frac{1}{N(s,a)}$ where $N(s,a)$ is number of visits to state $s$, action $a$, then the expected error for each Q value is the MSE from basic stats i.e. $\frac{\sigma_{TD}}{\sqrt{N(s,a)}}$