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

Question

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

Answer 1

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

Answer 2

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.

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