Can tabular Q-learning converge even if it doesn't explore all state-action pairs?

My understanding of tabular Q-learning is that it essentially builds a dictionary of state-action pairs, so as to maximize the Markovian (i.e., step-wise, history-agnostic?) reward. This incremental update of the Q-table can be done by a trade-off exploration and exploitation, but the fact remains that one "walks around" the table until it converges to optimality.

But what if we haven't "walked around" the whole table? Can the algorithm still perform well in those out-of-sample state-action pairs?

• I removed the part about the "self-learned algorithm" or "self-learning", which are ambiguous terms, in order to avoid more discussions in this comment section. If you have a question related to the term "self-learning", you can ask it as a separate question. Similarly, if you have a question about whether Q-learning is really a learning algorithm or not, ask it as another separate question. – nbro Jun 2 '20 at 15:25
• @nbro Thanks. I don't have enough command in this field to rephrase what I meant by "self-learning". If I did, I might not have asked the question in the first place. I think that most people can get the gist of what I meant and meet me half-way in understanding the question. As I had mentioned, tabular Q-learning seems to me to be more akin to a parameter-sweep or a grid search than <insert right term here> that can extrapolate to unseen data. It's this very aspect which I'd like to clear up. – Tfovid Jun 3 '20 at 18:47
• If you wonder if Q-learning can generalize to unseen environments, the answer is probably no, unless you train the network on the unseen environment again, but does this imply that it's not a learning algorithm? Note that learning can be thought of as a search. There are some questions on this site related to the topic, if you are interested. – nbro Jun 3 '20 at 19:19

In the tabular case, then the Q table will only converge if you have walked around the whole of the table. Note that to guarantee convergence we need $$\sum\limits_{n=1}^{\infty}\alpha_n(a) = \infty$$ and $$\sum\limits_{n=1}^\infty \alpha_n^2(a) < \infty$$. These conditions imply that in the limit each state-action pair will have been visited an infinite number of times, thus we will have walked around the whole table, so there are no out-of-sample state-action pairs.