9
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ why does "two functions approximators seen different samples" help? $\endgroup$ – Albert Chen Apr 22 '19 at 1:44
  • 1
    $\begingroup$ Because one of the function approximators might see samples that overestimate action a1 while the other see samples that overestimate action a2. The important thing is not to overestimate the same action $\endgroup$ – lgvaz Apr 23 '19 at 4:03
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.