Answers.Body: <p>Here's an intuitive description answer:</p>
  
  <p>Function approximation can be done with any parameterizable function. Consider the problem of a <span class="math-container">$Q(s,a)$</span> space where <span class="math-container">$s$</span> is the positive reals, <span class="math-container">$a$</span> is <span class="math-container">$0$</span> or <span class="math-container">$1$</span>, and the true Q-function is <span class="math-container">$Q(s, 0) = s^2$</span>, and <span class="math-container">$Q(s, 1)= 2s^2$</span>, for all states. If your function approximator is <span class="math-container">$Q(s, a) = m*s + n*a + b$</span>, there exists no parameters which can accurately represent the true <span class="math-container">$Q$</span> function (we're trying to fit a line to a quadratic function). Consequently, even if you chose a good learning rate, and visit all states infinitely often, your approximation function will never converge to the true <span class="math-container">$Q$</span> function. </p>
  
  <p>And here's a bit more detail:</p>
  
  <ol>
  <li>Neural networks <em>approximate</em> functions. A function can be approximated to greater or lesser degrees by using more or less complex polynomials to approximate it. If you're familiar with Taylor Series approximation, this idea should seem pretty natural. If not, think about a function like a sine-wave over the interval [0-<span class="math-container">$\pi/2$</span>). You can approximate it (badly) with a straight line. You can approximate it better with a quadratic curve. By increasing the degree of the polynomial we use to approximate the curve, we can get something that fits the curve more and more closely.</li>
  <li><p>Neural networks are <a href="https://en.wikipedia.org/wiki/Universal_approximation_theorem" rel="noreferrer">universal function approximators</a>. This means that, if you have a function, you can also make a neural network that is deep or wide enough that it can approximate the function you have created to an arbitrarily precise degree. However, any specific network topology you pick will be unable to learn <em>all</em> functions, unless it is infinitely wide or infinitely deep. This is analogous to how, if you pick the right parameters, a line can fit any two points, but not any 3 points. If you pick a network that is of a certain finite width or depth, I can always construct a function that needs a few more neurons to fit properly.</p></li>
  <li><p>Q-learning's bounds hold only when the representation of the Q-function is <em>exact</em>. To see why, suppose that you chose to approximate your Q-function with a linear interpolation. If the true function can take any shape at all, then clearly the error in our interpolation can be made unboundedly large simply by constructing a XOR-like Q-function function, and no amount of extra time or data will allow us to reduce this error. If you use a function approximator, and the true function you try to fit is <em>not</em> something that the function can approximate arbitrarily well, then your model will not converge properly, even with a well-chosen learning rate and exploration rate. Using the terminology of computational learning theory, we might say that the convergence proofs for Q-learning have implicitly assumed that the true Q-function is a member of the hypothesis space from which you will select your model. </p></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-05T19:39:51.173Z
Answers.Text: Where can we see from the proof I mentioned that "Q-learning's bounds hold only when the representation of the Q-function is exact" is true?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-05T22:07:34.497Z
Answers.Text: So, we can approximate any (reasonable) function using some neural network (architecture), but, given a fixed neural network architecture $Z$ (which we need to choose at the beginning of the training phase of the $Q$-learning), $Q$-learning might not converge using that specific architecture $Z$, because $Z$ might not be expressive enough to represent $Q^*$.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-06T00:10:17.323Z
Answers.Text: @nbro The proof doesn't say that explicitly, but it assumes an exact representation of the Q-function (that is, that exact values are computed and stored for every state/action pair). For infinite state spaces, it's clear that this exact representation can be infinitely large in the worst case (simple example: let Q(s,a) = sth digit of pi). Your second comment sums it up well. More formally, if the true hypothesis Q* is not an element of the hypothesis space H that you are selecting a model from, you cannot converge to Q*, even with infinite time or data.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-26T13:39:06.360Z
Answers.Text: You are correct that in a non-realisable setting (when the true function is not in the hypothesis class) one cannot learn the true function, but this does not mean that the learning does not converge. This is different from divergence. For instance, choose the hypothesis class containing only the 0 function.
Answers.UserDisplayName: user27182
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-15T20:41:34.683Z
Answers.Text: @JohnDoucette, thanks for the answer. I learnt a lot. I have more problem on this. Can you please help me out: https://ai.stackexchange.com/questions/37440/what-exactly-is-non-delusional-q-learning
Answers.UserDisplayName: wrek
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-05T19:25:49.813Z
Answers.LastActivityDate: 2019-04-06T00:11:18.947Z
Answers.LastEditDate: 2019-04-06T00:11:18.947Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>As far as I'm aware, it is still somewhat of an open problem to get a really clear, formal understanding of exactly why / when we get a lack of convergence -- or, worse, sometimes a danger of divergence. It is typically attributed to the <strong>"deadly triad"</strong> (see 11.3 of the second edition of Sutton and Barto's book), the combination of:</p>
  
  <ol>
  <li>Function approximation, AND</li>
  <li>Bootstrapping (using our own value estimates in the computation of our training targets, as done by <span class="math-container">$Q$</span>-learning), AND</li>
  <li>Off-policy training (<span class="math-container">$Q$</span>-learning is indeed off-policy).</li>
  </ol>
  
  <p>That only gives us a (possibly non-exhaustive) description of cases in which we have a lack of convergence and/or a danger of divergence, but still doesn't tell us <strong>why</strong> it happens in those cases.</p>
  
  <hr>
  
  <p><a href="https://ai.stackexchange.com/a/11681/1641">John's answer</a> already provides the intuition that part of the problem is simply that the use of function approximation can easily lead to situations where your function approximator isn't powerful enough to represent the true <span class="math-container">$Q^*$</span> function, there may always be approximation errors that are impossible to get rid of without switching to a different function approximator. </p>
  
  <p>Personally, I think this intuition does help to understand why the algorithm cannot guarantee convergence to the optimal solution, but I'd still intuitively expect it to maybe be capable of "converging" to some "stable" solution that is the best possible approximation given the restrictions inherent in the chosen function representation. Indeed, this is what we observe in practice when we switch to on-policy training (e.g. Sarsa), at least in the case with linear function approximators.</p>
  
  <hr>
  
  <p>My own intuition with respect to this question has generally been that an important source of the problem is <strong>generalisation</strong>. In the tabular setting, we have completely isolated entries <span class="math-container">$Q(s, a)$</span> for all <span class="math-container">$(s, a)$</span> pairs. Whenever we update our estimate for one entry, it leaves all other entries unmodified (at least initially -- there may be some effects on other entries in future updates due to bootstrapping in the update rule). Update rules for algorithms like <span class="math-container">$Q$</span>-learning and Sarsa may sometimes update towards the "wrong" direction if we get "unlucky", but <strong>in expectation</strong>, they generally update towards the correct "direction". Intuitively, this means that, in the tabular setting, <strong>in expectation</strong> we will slowly, gradually fix any mistakes in any entries in isolation, without possibly harming other entries.</p>
  
  <p>With function approximation, when we update our <span class="math-container">$Q(s, a)$</span> estimate for one <span class="math-container">$(s, a)$</span> pair, it can potentially also affect <strong>all</strong> of our other estimates for <strong>all</strong> other state-action pairs. Intuitively, this means that we no longer have the nice isolation of entries as in the tabular setting, and "fixing" mistakes in one entry may have a risk of adding new mistakes to other entries. However, like John's answer, this whole intuition would really also apply to on-policy algorithms, so it still doesn't explain what's special about <span class="math-container">$Q$</span>-learning (and other off-policy approaches).</p>
  
  <hr>
  
  <p>A very interesting recent paper on this topic is <a href="https://papers.nips.cc/paper/8200-non-delusional-q-learning-and-value-iteration" rel="noreferrer">Non-delusional Q-learning and Value Iteration</a>. They point out a problem of "delusional bias" in algorithms that combine function approximation with update rules involving a <span class="math-container">$\max$</span> operator, such as Q-learning (it's probably not unique to the <span class="math-container">$\max$</span> operator, but probably applies to off-policy in general?). </p>
  
  <p>The problem is as follows. Suppose we run this <span class="math-container">$Q$</span>-learning update for a state-action pair <span class="math-container">$(s, a)$</span>:</p>
  
  <p><span class="math-container">$$Q(s, a) \gets Q(s, a) + \alpha \left[ \max_{a'} Q(s', a') - Q(s, a) \right].$$</span></p>
  
  <p>The value estimate <span class="math-container">$\max_{a'} Q(s', a')$</span> used here is based on the assumption that we execute a policy that is greedy with respect to older versions of our <span class="math-container">$Q$</span> estimates over a -- possibly very long -- trajectory. As already discussed in some of the previous answers, our function approximator has a limited representational capacity, and updates to one state-action pair may affect value estimates for other state-action pairs. This means that, after triggering our update to <span class="math-container">$Q(s, a)$</span>, <strong>our function approximator may no longer be able to simultaneously express the policy that leads to the high returns that our <span class="math-container">$\max_{a'} Q(s', a')$</span> estimate was based on</strong>. The authors of this paper say that the algorithm is "delusional". It performs an update under the assumption that, down the line, it can still obtain large returns, but it may no longer actually be powerful enough to obtain those returns with the new version of the function approximator's parameters.</p>
  
  <hr>
  
  <p>Finally, another (even more recent) paper that I suspect is relevant to this question is <a href="https://arxiv.org/abs/1902.10250" rel="noreferrer">Diagnosing Bottlenecks in Deep Q-learning Algorithms</a>, but unfortunately I have not yet had the time to read it in sufficient detail and adequately summarise it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-06T09:33:07.950Z
Answers.Text: But isn't the use of a neural network also due to the assumption that certain states are very similar to each? Very similar states (e.g. successive frames in a game) often have very similar (or same) optimal actions, so I am not sure that explanation in the first paper is valid (I should read it to fully understand their main points).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-06T09:48:12.537Z
Answers.Text: @nbro Yeah, often generalisation is considered to be an **advantage** rather than a problem precisely because of that reason. If it works out as "intended", it can be very powerful and speed up learning because we transfer whatever we learn to similar states / similar actions, rather than learning for every slightly different state/action in isolation. But it can also lead to problems, especially in theory but also in practice. It's like a "double-edged sword" I suppose.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-06T16:44:19.427Z
Answers.Text: @DennisSoemers Super interesting answer. The Non-delusional Q-learning point makes a ton of sense. Finding the correct Q-function means finding a fixed point for your update rule, but it sure looks like function approximation could lead to cyclic updates in Q-learning if you think about it this way.
Answers.UserDisplayName: John Doucette
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-15T20:42:17.833Z
Answers.Text: @DennisSoemers, thanks for your answer, I learnt a lot. I have more question on the delusional-Q learning. Can you please help me out here: https://ai.stackexchange.com/questions/37440/what-exactly-is-non-delusional-q-learning
Answers.UserDisplayName: wrek
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-06T09:16:00.397Z
Answers.LastActivityDate: 2019-04-06T09:16:00.397Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>There are three problems</p>
  <ol>
  <li>Limited capacity Neural Network (explained by John)</li>
  <li>Non-stationary Target</li>
  <li>Non-stationary distribution</li>
  </ol>
  <h1>Non-stationary Target</h1>
  <p>In tabular Q-learning, when we update a Q-value, other Q-values in the table don't get affected by this. But in neural networks, one update to the weights aiming to alter one Q-value ends up affecting other Q-values whose states look similar (since neural networks learn a continuous function that is smooth)</p>
  <p>This is bad because when you are playing a game, two consecutive states of a game are always similar. Therefore, Q-value updates will increase or decrease Q-values for both states together. So, when you take one as the target for the other, the target becomes non-stationary since it moves along with you. This is analogous to a donkey running to catch a carrot that is attached to its head. Since the target is non-stationary, the donkey will never reach its target. And, in our case, in trying to chase, the Q-values will explode.</p>
  <p>In <a href="https://daiwk.github.io/assets/dqn.pdf" rel="nofollow noreferrer">Human-level control through deep reinforcement learning</a>, this problem is addressed by caching an OLD copy of the DQN for evaluating the targets, &amp; updating the cache every 100,000 steps of learning. This is called a <em>target network</em>, and the targets remain stationary this way.</p>
  <h1>Non-stationary distribution</h1>
  <p>This is analogous to the &quot;distribution drift&quot; problem in imitation learning, which can be solved with the dataset aggregation technique called <a href="https://www.ri.cmu.edu/pub_files/2011/4/Ross-AISTATS11-NoRegret.pdf" rel="nofollow noreferrer">DAgger</a>.</p>
  <p>The idea is, as we train, our DQN gets better and better and our policy improves. And this causes our sampling distribution to change since we are doing online learning where we sample according to a policy with <span class="math-container">$\epsilon$</span> probability. This is a problem for supervised learning since it assumes stationary distribution or i.i.d. data.</p>
  <p>As an analogy, this is like training a Neural Network to identify cats and dogs but showing the network only dogs during the first 100 epochs, and then showing only cats for the remainder epochs. What happens is, the network learns to identify dogs, then forgets it and learns to identify cats.</p>
  <p>This is what happens when the distribution changes and we care only about the current distribution during training. So, in order to solve this,  <a href="https://daiwk.github.io/assets/dqn.pdf" rel="nofollow noreferrer">same paper</a> starts aggregating data in a large buffer, and samples a mini-batch of both new data as well as old data every time during training. This is called <em>experience replay</em>, since we don't throw away our past experience and keep re-using them in training.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-19T13:16:32.750Z
Answers.Text: This answer seems to address more the question: "In practice, how can I improve the learning stability of Q-learning with neural networks?" rather than the _convergence_ properties of Q-learning with function approximation. My question was not much about practical tricks to improve learning stability (everyone is aware of the target network and experience replay), but I was looking more for mathematical proofs that show the convergence or divergence of Q-learning with function approximation.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-21T06:14:29.357Z
Answers.Text: Oh. I'm sorry for the confusion. I was just sharing my intuition behind why these practical tricks work and how they help. I am not aware of the rigorous mathematical proofs you are looking for. I'm sorry for misunderstanding.
Answers.UserDisplayName: Vignesh Sk
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-29T10:12:30.050Z
Answers.LastActivityDate: 2020-12-19T13:14:29.677Z
Answers.LastEditDate: 2020-12-19T13:14:29.677Z
Answers.UserDisplayName: Vignesh Sk
Body: <p>The tabular Q-learning algorithm is guaranteed to find the optimal <span class="math-container">$Q$</span> function, <span class="math-container">$Q^*$</span>, provided the following conditions (the <a href="https://en.wikipedia.org/wiki/Stochastic_approximation" rel="noreferrer">Robbins-Monro conditions</a>) regarding the learning rate are satisfied</p>
  
  <ol>
  <li><span class="math-container">$\sum_{t} \alpha_t(s, a) = \infty$</span></li>
  <li><span class="math-container">$\sum_{t} \alpha_t^2(s, a) &lt; \infty$</span></li>
  </ol>
  
  <p>where <span class="math-container">$\alpha_t(s, a)$</span> means the learning rate used when updating the <span class="math-container">$Q$</span> value associated with state <span class="math-container">$s$</span> and action <span class="math-container">$a$</span> at time time step <span class="math-container">$t$</span>, where <span class="math-container">$0 \leq  \alpha_t(s, a) &lt; 1$</span> is assumed to be true, for all states <span class="math-container">$s$</span> and actions <span class="math-container">$a$</span>.</p>
  
  <p>Apparently, given that <span class="math-container">$0 \leq  \alpha_t(s, a) &lt; 1$</span>, in order for the two conditions to be true, all state-action pairs must be visited infinitely often: this is also stated in the book <a href="http://incompleteideas.net/book/bookdraft2018mar21.pdf" rel="noreferrer">Reinforcement Learning: An Introduction</a>, apart from the fact that this should be widely known and it is the rationale behind the usage of the <span class="math-container">$\epsilon$</span>-greedy policy (or similar policies) during training.</p>
  
  <p>A complete proof that shows that <span class="math-container">$Q$</span>-learning finds the optimal <span class="math-container">$Q$</span> function can be found in the paper <a href="http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf" rel="noreferrer">Convergence of Q-learning: A Simple Proof</a> (by Francisco S. Melo). He uses concepts like <a href="https://en.wikipedia.org/wiki/Contraction_mapping" rel="noreferrer">contraction mapping</a> in order to define the optimal <span class="math-container">$Q$</span> function (see also <a href="https://ai.stackexchange.com/q/11057/2444">What is the Bellman operator in reinforcement learning?</a>), which is a fixed point of this contraction operator. He also uses a theorem (n. 2) regarding the random process that converges to <span class="math-container">$0$</span>, given a few assumptions. (The proof might not be easy to follow if you are not a math guy.)</p>
  
  <p>If a neural network is used to represent the <span class="math-container">$Q$</span> function, do the convergence guarantees of <span class="math-container">$Q$</span>-learning still hold? Why does (or not) Q-learning converge when using function approximation? Is there a formal proof of such non-convergence of <span class="math-container">$Q$</span>-learning using function approximation? </p>
  
  <p>I am looking for different types of answers, from those that give just the intuition behind the non-convergence of <span class="math-container">$Q$</span>-learning when using function approximation to those that provide a formal proof (or a link to a paper with a formal proof).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-05T19:26:00.673Z
Comments.Text: Great question!
Comments.UserDisplayName: John Doucette
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-05T20:21:20.297Z
Comments.Text: The book that you referenced talks about this problem in chapter 11 so you might read it. Also, I don't think there's a formal proof why this happens but there are few examples that show divergence even in simple environments (e.g. Tsitsiklis and van Roy) .
Comments.UserDisplayName: Brale
Tags: <reinforcement-learning><q-learning><deep-rl><proofs><function-approximation>
Title: Why doesn't Q-learning converge when using function approximation?
UserDisplayName: nbro
ThreadText: # Why doesn't Q-learning converge when using function approximation?
  
  (Asked by: username_0 on 2019-04-05)
  
  The tabular Q-learning algorithm is guaranteed to find the optimal $Q$ function, $Q^\*$, provided the following conditions (the [Robbins-Monro conditions](https://en.wikipedia.org/wiki/Stochastic_approximation)) regarding the learning rate are satisfied
  
  1. $\sum\_{t} \alpha\_t(s, a) = \infty$
  2. $\sum\_{t} \alpha\_t^2(s, a) < \infty$
  
  where $\alpha\_t(s, a)$ means the learning rate used when updating the $Q$ value associated with state $s$ and action $a$ at time time step $t$, where $0 \leq \alpha\_t(s, a) < 1$ is assumed to be true, for all states $s$ and actions $a$.
  
  Apparently, given that $0 \leq \alpha\_t(s, a) < 1$, in order for the two conditions to be true, all state-action pairs must be visited infinitely often: this is also stated in the book [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/bookdraft2018mar21.pdf), apart from the fact that this should be widely known and it is the rationale behind the usage of the $\epsilon$-greedy policy (or similar policies) during training.
  
  A complete proof that shows that $Q$-learning finds the optimal $Q$ function can be found in the paper [Convergence of Q-learning: A Simple Proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) (by Francisco S. Melo). He uses concepts like [contraction mapping](https://en.wikipedia.org/wiki/Contraction_mapping) in order to define the optimal $Q$ function (see also [What is the Bellman operator in reinforcement learning?](https://ai.stackexchange.com/q/11057/2444)), which is a fixed point of this contraction operator. He also uses a theorem (n. 2) regarding the random process that converges to $0$, given a few assumptions. (The proof might not be easy to follow if you are not a math guy.)
  
  If a neural network is used to represent the $Q$ function, do the convergence guarantees of $Q$-learning still hold? Why does (or not) Q-learning converge when using function approximation? Is there a formal proof of such non-convergence of $Q$-learning using function approximation?
  
  I am looking for different types of answers, from those that give just the intuition behind the non-convergence of $Q$-learning when using function approximation to those that provide a formal proof (or a link to a paper with a formal proof).
  
  **Tags:** reinforcement-learning, q-learning, deep-rl, proofs, function-approximation
  > **Comments:**
  > **username_1**: Great question!  
  > **username_2**: The book that you referenced talks about this problem in chapter 11 so you might read it. Also, I don't think there's a formal proof why this happens but there are few examples that show divergence even in simple environments (e.g. Tsitsiklis and van Roy) .  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2019-04-05. Score: 14
  
  Here's an intuitive description answer:
  
  Function approximation can be done with any parameterizable function. Consider the problem of a $Q(s,a)$ space where $s$ is the positive reals, $a$ is $0$ or $1$, and the true Q-function is $Q(s, 0) = s^2$, and $Q(s, 1)= 2s^2$, for all states. If your function approximator is $Q(s, a) = m\*s + n\*a + b$, there exists no parameters which can accurately represent the true $Q$ function (we're trying to fit a line to a quadratic function). Consequently, even if you chose a good learning rate, and visit all states infinitely often, your approximation function will never converge to the true $Q$ function.
  
  And here's a bit more detail:
  
  1. Neural networks *approximate* functions. A function can be approximated to greater or lesser degrees by using more or less complex polynomials to approximate it. If you're familiar with Taylor Series approximation, this idea should seem pretty natural. If not, think about a function like a sine-wave over the interval [0-$\pi/2$). You can approximate it (badly) with a straight line. You can approximate it better with a quadratic curve. By increasing the degree of the polynomial we use to approximate the curve, we can get something that fits the curve more and more closely.
  2. Neural networks are [universal function approximators](https://en.wikipedia.org/wiki/Universal_approximation_theorem). This means that, if you have a function, you can also make a neural network that is deep or wide enough that it can approximate the function you have created to an arbitrarily precise degree. However, any specific network topology you pick will be unable to learn *all* functions, unless it is infinitely wide or infinitely deep. This is analogous to how, if you pick the right parameters, a line can fit any two points, but not any 3 points. If you pick a network that is of a certain finite width or depth, I can always construct a function that needs a few more neurons to fit properly.
  3. Q-learning's bounds hold only when the representation of the Q-function is *exact*. To see why, suppose that you chose to approximate your Q-function with a linear interpolation. If the true function can take any shape at all, then clearly the error in our interpolation can be made unboundedly large simply by constructing a XOR-like Q-function function, and no amount of extra time or data will allow us to reduce this error. If you use a function approximator, and the true function you try to fit is *not* something that the function can approximate arbitrarily well, then your model will not converge properly, even with a well-chosen learning rate and exploration rate. Using the terminology of computational learning theory, we might say that the convergence proofs for Q-learning have implicitly assumed that the true Q-function is a member of the hypothesis space from which you will select your model.
  
  > **Comments:**
  > **username_0**: Where can we see from the proof I mentioned that "Q-learning's bounds hold only when the representation of the Q-function is exact" is true?  
  > **username_0**: So, we can approximate any (reasonable) function using some neural network (architecture), but, given a fixed neural network architecture $Z$ (which we need to choose at the beginning of the training phase of the $Q$-learning), $Q$-learning might not converge using that specific architecture $Z$, because $Z$ might not be expressive enough to represent $Q^*$.  
  > **username_1**: @nbro The proof doesn't say that explicitly, but it assumes an exact representation of the Q-function (that is, that exact values are computed and stored for every state/action pair). For infinite state spaces, it's clear that this exact representation can be infinitely large in the worst case (simple example: let Q(s,a) = sth digit of pi). Your second comment sums it up well. More formally, if the true hypothesis Q* is not an element of the hypothesis space H that you are selecting a model from, you cannot converge to Q*, even with infinite time or data.  
  > **username_3**: You are correct that in a non-realisable setting (when the true function is not in the hypothesis class) one cannot learn the true function, but this does not mean that the learning does not converge. This is different from divergence. For instance, choose the hypothesis class containing only the 0 function.  
  > **username_4**: @JohnDoucette, thanks for the answer. I learnt a lot. I have more problem on this. Can you please help me out: https://ai.stackexchange.com/questions/37440/what-exactly-is-non-delusional-q-learning  
  
  ---
  
  ### Answer by username_5 on 2019-04-06. Score: 9
  
  As far as I'm aware, it is still somewhat of an open problem to get a really clear, formal understanding of exactly why / when we get a lack of convergence -- or, worse, sometimes a danger of divergence. It is typically attributed to the **"deadly triad"** (see 11.3 of the second edition of Sutton and Barto's book), the combination of:
  
  1. Function approximation, AND
  2. Bootstrapping (using our own value estimates in the computation of our training targets, as done by $Q$-learning), AND
  3. Off-policy training ($Q$-learning is indeed off-policy).
  
  That only gives us a (possibly non-exhaustive) description of cases in which we have a lack of convergence and/or a danger of divergence, but still doesn't tell us **why** it happens in those cases.
  
  ---
  
  [John's answer](https://ai.stackexchange.com/a/11681/1641) already provides the intuition that part of the problem is simply that the use of function approximation can easily lead to situations where your function approximator isn't powerful enough to represent the true $Q^\*$ function, there may always be approximation errors that are impossible to get rid of without switching to a different function approximator.
  
  Personally, I think this intuition does help to understand why the algorithm cannot guarantee convergence to the optimal solution, but I'd still intuitively expect it to maybe be capable of "converging" to some "stable" solution that is the best possible approximation given the restrictions inherent in the chosen function representation. Indeed, this is what we observe in practice when we switch to on-policy training (e.g. Sarsa), at least in the case with linear function approximators.
  
  ---
  
  My own intuition with respect to this question has generally been that an important source of the problem is **generalisation**. In the tabular setting, we have completely isolated entries $Q(s, a)$ for all $(s, a)$ pairs. Whenever we update our estimate for one entry, it leaves all other entries unmodified (at least initially -- there may be some effects on other entries in future updates due to bootstrapping in the update rule). Update rules for algorithms like $Q$-learning and Sarsa may sometimes update towards the "wrong" direction if we get "unlucky", but **in expectation**, they generally update towards the correct "direction". Intuitively, this means that, in the tabular setting, **in expectation** we will slowly, gradually fix any mistakes in any entries in isolation, without possibly harming other entries.
  
  With function approximation, when we update our $Q(s, a)$ estimate for one $(s, a)$ pair, it can potentially also affect **all** of our other estimates for **all** other state-action pairs. Intuitively, this means that we no longer have the nice isolation of entries as in the tabular setting, and "fixing" mistakes in one entry may have a risk of adding new mistakes to other entries. However, like John's answer, this whole intuition would really also apply to on-policy algorithms, so it still doesn't explain what's special about $Q$-learning (and other off-policy approaches).
  
  ---
  
  A very interesting recent paper on this topic is [Non-delusional Q-learning and Value Iteration](https://papers.nips.cc/paper/8200-non-delusional-q-learning-and-value-iteration). They point out a problem of "delusional bias" in algorithms that combine function approximation with update rules involving a $\max$ operator, such as Q-learning (it's probably not unique to the $\max$ operator, but probably applies to off-policy in general?).
  
  The problem is as follows. Suppose we run this $Q$-learning update for a state-action pair $(s, a)$:
  
  $$Q(s, a) \gets Q(s, a) + \alpha \left[ \max\_{a'} Q(s', a') - Q(s, a) \right].$$
  
  The value estimate $\max\_{a'} Q(s', a')$ used here is based on the assumption that we execute a policy that is greedy with respect to older versions of our $Q$ estimates over a -- possibly very long -- trajectory. As already discussed in some of the previous answers, our function approximator has a limited representational capacity, and updates to one state-action pair may affect value estimates for other state-action pairs. This means that, after triggering our update to $Q(s, a)$, **our function approximator may no longer be able to simultaneously express the policy that leads to the high returns that our $\max\_{a'} Q(s', a')$ estimate was based on**. The authors of this paper say that the algorithm is "delusional". It performs an update under the assumption that, down the line, it can still obtain large returns, but it may no longer actually be powerful enough to obtain those returns with the new version of the function approximator's parameters.
  
  ---
  
  Finally, another (even more recent) paper that I suspect is relevant to this question is [Diagnosing Bottlenecks in Deep Q-learning Algorithms](https://arxiv.org/abs/1902.10250), but unfortunately I have not yet had the time to read it in sufficient detail and adequately summarise it.
  
  > **Comments:**
  > **username_0**: But isn't the use of a neural network also due to the assumption that certain states are very similar to each? Very similar states (e.g. successive frames in a game) often have very similar (or same) optimal actions, so I am not sure that explanation in the first paper is valid (I should read it to fully understand their main points).  
  > **username_5**: @nbro Yeah, often generalisation is considered to be an **advantage** rather than a problem precisely because of that reason. If it works out as "intended", it can be very powerful and speed up learning because we transfer whatever we learn to similar states / similar actions, rather than learning for every slightly different state/action in isolation. But it can also lead to problems, especially in theory but also in practice. It's like a "double-edged sword" I suppose.  
  > **username_1**: @DennisSoemers Super interesting answer. The Non-delusional Q-learning point makes a ton of sense. Finding the correct Q-function means finding a fixed point for your update rule, but it sure looks like function approximation could lead to cyclic updates in Q-learning if you think about it this way.  
  > **username_4**: @DennisSoemers, thanks for your answer, I learnt a lot. I have more question on the delusional-Q learning. Can you please help me out here: https://ai.stackexchange.com/questions/37440/what-exactly-is-non-delusional-q-learning  
  
  ---
  
  ### Answer by username_6 on 2020-05-29. Score: 3
  
  There are three problems
  
  1. Limited capacity Neural Network (explained by John)
  2. Non-stationary Target
  3. Non-stationary distribution
  
  # Non-stationary Target
  
  In tabular Q-learning, when we update a Q-value, other Q-values in the table don't get affected by this. But in neural networks, one update to the weights aiming to alter one Q-value ends up affecting other Q-values whose states look similar (since neural networks learn a continuous function that is smooth)
  
  This is bad because when you are playing a game, two consecutive states of a game are always similar. Therefore, Q-value updates will increase or decrease Q-values for both states together. So, when you take one as the target for the other, the target becomes non-stationary since it moves along with you. This is analogous to a donkey running to catch a carrot that is attached to its head. Since the target is non-stationary, the donkey will never reach its target. And, in our case, in trying to chase, the Q-values will explode.
  
  In [Human-level control through deep reinforcement learning](https://daiwk.github.io/assets/dqn.pdf), this problem is addressed by caching an OLD copy of the DQN for evaluating the targets, & updating the cache every 100,000 steps of learning. This is called a *target network*, and the targets remain stationary this way.
  
  # Non-stationary distribution
  
  This is analogous to the "distribution drift" problem in imitation learning, which can be solved with the dataset aggregation technique called [DAgger](https://www.ri.cmu.edu/pub_files/2011/4/Ross-AISTATS11-NoRegret.pdf).
  
  The idea is, as we train, our DQN gets better and better and our policy improves. And this causes our sampling distribution to change since we are doing online learning where we sample according to a policy with $\epsilon$ probability. This is a problem for supervised learning since it assumes stationary distribution or i.i.d. data.
  
  As an analogy, this is like training a Neural Network to identify cats and dogs but showing the network only dogs during the first 100 epochs, and then showing only cats for the remainder epochs. What happens is, the network learns to identify dogs, then forgets it and learns to identify cats.
  
  This is what happens when the distribution changes and we care only about the current distribution during training. So, in order to solve this, [same paper](https://daiwk.github.io/assets/dqn.pdf) starts aggregating data in a large buffer, and samples a mini-batch of both new data as well as old data every time during training. This is called *experience replay*, since we don't throw away our past experience and keep re-using them in training.
  
  > **Comments:**
  > **username_0**: This answer seems to address more the question: "In practice, how can I improve the learning stability of Q-learning with neural networks?" rather than the _convergence_ properties of Q-learning with function approximation. My question was not much about practical tricks to improve learning stability (everyone is aware of the target network and experience replay), but I was looking more for mathematical proofs that show the convergence or divergence of Q-learning with function approximation.  
  > **username_6**: Oh. I'm sorry for the confusion. I was just sharing my intuition behind why these practical tricks work and how they help. I am not aware of the rigorous mathematical proofs you are looking for. I'm sorry for misunderstanding.  
  
  ---
  
  