1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Jun 2, 2020 at 15:25
  • $\begingroup$ @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. $\endgroup$
    – Tfovid
    Jun 3, 2020 at 18:47
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Jun 3, 2020 at 19:19

1 Answer 1

Reset to default
1
$\begingroup$

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.

However, in the case of function approximation, then convergence is no longer guaranteed. Generalisability is possible though - assuming we have an infinite state or action space then we will only ever visit the same state-action pair once, so the role of a function approximator is to allow us to generalise the state/action space.

NB that the convergence conditions I mentioned are only required in some proofs of convergence, depending on what type of convergence you are looking to prove. See this answer for more details.

Improve this answer
$\endgroup$
2
  • $\begingroup$ My initial question (which has now been edited by an admin) was really about whether tabular Q-learning is just a search-based algorithm or one that actually can predict out of sample. I gather from your answer that it is search-based whereas functional methods---presumably such as DQN?--- can predict out of sample? $\endgroup$
    – Tfovid
    Jun 6, 2020 at 7:36
  • $\begingroup$ in tabular Q-Learning there isn't such a thing as 'out of sample'. As I said, in the limit, you will have explored every state-action pair of the MDP. If you introduced a new state-action pair not originally defined in the MDP then you would have to run Q-Learning on this new MDP as it is a new problem. In functional methods it is inherently out of sample because even in the limit you would not visit any state more than once (or even visit every state), so it has to generalise to unseen states, but the states are still defined per the MDP. $\endgroup$
    – David Ireland
    Jun 6, 2020 at 10:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .