Answers.Body: <p>In the tabular case, then the Q table will only converge if you <em>have</em> walked around the whole of the table. Note that to guarantee convergence we need <span class="math-container">$\sum\limits_{n=1}^{\infty}\alpha_n(a) = \infty$</span> and <span class="math-container">$\sum\limits_{n=1}^\infty \alpha_n^2(a) &lt; \infty$</span>. 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. </p>
  
  <p>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. </p>
  
  <p>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 <a href="https://ai.stackexchange.com/questions/21388/what-are-the-conditions-of-convergence-of-temporal-difference-learning/21408#21408">this answer</a> for more details. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-06T07:36:53.397Z
Answers.Text: 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?
Answers.UserDisplayName: Tfovid
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-06T10:22:31.900Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-01T10:07:48.473Z
Answers.LastActivityDate: 2020-06-02T17:36:34.637Z
Answers.LastEditDate: 2020-06-02T17:36:34.637Z
Answers.UserDisplayName: David
Body: <p>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.</p>
  
  <p>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? </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-02T15:25:06.883Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T18:47:24.347Z
Comments.Text: @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.
Comments.UserDisplayName: Tfovid
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-03T19:19:09.383Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Tags: <machine-learning><reinforcement-learning><q-learning><exploration-exploitation-tradeoff>
Title: Can tabular Q-learning converge even if it doesn't explore all state-action pairs?
UserDisplayName: Tfovid
ThreadText: # Can tabular Q-learning converge even if it doesn't explore all state-action pairs?
  
  (Asked by: username_0 on 2020-06-01)
  
  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?
  
  **Tags:** machine-learning, reinforcement-learning, q-learning, exploration-exploitation-tradeoff
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: @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.  
  > **username_1**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-06-01. Score: 1 | Accepted answer
  
  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](https://ai.stackexchange.com/questions/21388/what-are-the-conditions-of-convergence-of-temporal-difference-learning/21408#21408) for more details.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_2**: 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.  
  
  ---
  
  