10
$\begingroup$

The tabular Q-learning algorithm is guaranteed to find the optimal $Q$ function, $Q^*$, provided the following 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 is "widely" known, and it is rationale behind the usage of the $\epsilon$-greedy policy (or similar) 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 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.)

I have heard that when we use a neural network to represent the $Q$ function, the convergence guarantees of $Q$-learning do not hold anymore. Why exactly is that? Why doesn't 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).

$\endgroup$
  • 2
    $\begingroup$ Great question! $\endgroup$ – John Doucette Apr 5 at 19:26
  • $\begingroup$ 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) . $\endgroup$ – Brale_ Apr 5 at 20:21
7
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – nbro Apr 6 at 9:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Dennis Soemers Apr 6 at 9:48
  • 1
    $\begingroup$ @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. $\endgroup$ – John Doucette Apr 6 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.