Q-learning is guaranteed to convergence if the learning rate satisfies the Robbins-Monro conditions and if every state-action pair is visited infinitely often.

Regarding the latter, does it mean that the MDP must be ergodic? An MDP is ergodic if there any state can be reached from any other within finite time under any policy (see Puterman's book, this question, this paper). This is a rather strict condition.
Or does Q-Learning just need that every state can be reached under some policy? (I.e., that the MDP is communicating?)
If so, would the $\epsilon$-greedy policy satisfy this condition? Is there any proof showing that an $\epsilon$-greedy policy visit all states within finite time?



You must log in to answer this question.