# Why doesn't Q-learning converge when using function approximation?

The tabular Q-learning algorithm is guaranteed to find the optimal $$Q$$ function, $$Q^*$$, provided the following conditions (the Robbins-Monro conditions) 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, 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 (by Francisco S. Melo). He uses concepts like contraction mapping in order to define the optimal $$Q$$ function (see also What is the Bellman operator in reinforcement learning?), 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).

• Great question! Apr 5 '19 at 19:26
• 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) . Apr 5 '19 at 20:21

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. 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.

• 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?
– nbro
Apr 5 '19 at 19:39
• 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^*$.
– nbro
Apr 5 '19 at 22:07
• @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. Apr 6 '19 at 0:10

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 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. 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, but unfortunately I have not yet had the time to read it in sufficient detail and adequately summarise it.

• 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).
– nbro
Apr 6 '19 at 9:33
• @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. Apr 6 '19 at 9:48
• @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. Apr 6 '19 at 16:44

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, 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.

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 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.

• 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.
– nbro
Dec 19 '20 at 13:16
• 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. Dec 21 '20 at 6:14