Why does Q-learning overestimate action values?

Question

I'm having difficulty finding any explanation as to why standard Q-learning tends to overestimate q-values (which is addressed by using double Q-learning). The only sources I have found don't really explain exactly why this overestimation occurs.

For example, the Wikipedia article on Q-learning says:

Because the maximum approximated action value is used in the Q-learning update, in noisy environments Q-learning can sometimes overestimate the actions values, slowing the learning.

What does this mean? I understand Q-learning, but not the above. Why does the use of the maximum q-value cause overestimation?

Thanks!

Answer 1

$$Q(s, a) = r + \gamma \text{max}_{a'}[Q(s', a')]$$

Since Q values are very noisy, when you take the max over all actions, you're probably getting an overestimated value. Think like this, the expected value of a dice roll is 3.5, but if you throw the dice 100 times and take the max over all throws, you're very likely taking a value that is greater than 3.5 (think that every possible action value at state s in a dice roll).

If all values were equally overestimated this would be no problem, since what matters is the difference between the Q values. But if the overestimations are not uniform, this might slow down learning (because you will spend time exploring states that you think are good but aren't).

The proposed solution (Double Q-learning) is to use two different function approximators that are trained on different samples, one for selecting the best action and other for calculating the value of this action, since the two functions approximators seen different samples, it is unlikely that they overestimate the same action.

Answer 2

I am not very familiar with reinforcement learning, but the very next line in the Wikipedia article you cite (currently) refers to the paper Double Q-learning (NIPS 2010). The abstract to that paper says

These overestimations result from a positive bias that is introduced because Q-learning uses the maximum action value as an approximation for the maximum expected action value.

Together, these seem to be saying that when the $Q$ function is in reality stochastic, observed rewards $\hat{r}$ resulting from a state-action pair $(s,a)$ will have some (0-mean) noise associated with them, e.g. $\hat{r}=r+\epsilon$. Then, because $Q$ is updated based on $\max_aQ_\text{old}$, the maximum value will tend to be a combination of high reward $r$ and/or large positive noise realizations $\epsilon$. By assuming $r_\max\approx\hat{r}_\max$ and ignoring $\epsilon$, the value of $Q$ will tend to be an over-estimate.

(As noted I am unfamiliar with this area, and only glanced at Wikipedia and the above abstract, so this interpretation could be wrong.)

Answer 3

It is based on the Optimizer's Curse (OC from now on). (And a lot of other math, which correlates the OC to Q-learning. Here is an article written by the original author of the DDQN algorithm covering this correlation).

Normal Explanation: Essentially, the OC states, that if we constantly choose the maximum estimate of an outcome, on average our estimate will lie over the maximum of the actual outcome we're trying to predict. I.e We over-estimate.

This correlates to the Q-value in the following way; The Q-value of the state-action pair (s,a) is actually an estimate of the maximum expected future rewards gained by following the optimal policy $\pi$.

The way we approximate this optimal policy - and therefore the Q-value of (s,a) - is with the following - well known - equation:

$Q(s_t,a_t) <- R_{t+1} + \gamma * max_{a_t}Q(s_{t+1},a_{t+1})$

Concluding; We try to approximate the optimal policy of the current state, which is itself is an expectation of the future rewards, by constantly taking the maximum of the expected reward at the next state.

This falls under the OC, so therefore we overestimate in our max-term.

Very short explanation:

We have a "curse," which tells us, that constantly taking the maximum of our expectations/estimates will give us, on average, an estimate that is higher than the thing we're trying to estimate. I.e we overestimate.

As Q-learning is the act of estimating the maximum future rewards, with its accompanying approximating and well-known equation, it too falls under the curse thanks to the max-term in this equation.

Answer 4

First, I want to quote from Sutton and Barto book

... In these algorithms, a maximum over estimated values is used implicitly as an estimate of the maximum value, which can lead to a significant positive bias. To see why, consider a single state s where there are many actions a whose true values, q(s, a), are all zero but whose estimated values, Q(s, a), are uncertain and thus distributed some above and some below zero.

It's a little bit vague. here is a simple example. where Q1(s, X) = Q2(s, X) = 0, but in practice, the values may be uncertain.

Q1(s,A) = 0.1, Q1(s,B) = 0, Q1(s,C) = -0.1

Q2(s,A) = -0.1, Q2(s,B) = 0.1, Q2(s,C) = 0

If you only update Q1 by itself, it always tends to select A at s to update. But if you select max_a Q2(s,a) to update Q1, then, Q2 can compensate the situation. Also, you have to use Q1 to train Q2 in the other way. The noise in Q2 are independent of that in Q1 since Q1 and Q2 are trained using different dataset separately.