4
$\begingroup$

The motivation for the introduction of double DQN (and double Q-learning) is that the regular Q-learning (or DQN) can overestimate the Q value, but is there a brief explanation as to why it is overestimated?

$\endgroup$
0
4
$\begingroup$

The overestimation comes from the random initialisation of your Q-value estimates. Obviously these will not be perfect (if they were then we wouldn't need to learn the true Q-values!). In many value based reinforcement learning methods such as SARSA or Q-learning the algorithms involve a $\max$ operator in the construction of the target policy. The most obvious case is, as you mentioned, Q-learning. The learning update is $$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$ The Q-function for the state-action tuple we are considering is shifted towards the max Q-function at the next state where the $\max$ is taken with respect to the actions.

Now, as mentioned our initial estimates of the Q-values are initialised randomly. This naturally leads to incorrect values. The consequence of this is that when we calculate $\max_aQ(s', a)$ we could be choosing values that are grossly overestimated.

As Q-learning (in the tabular case) is guaranteed to converge (under some mild assumptions) so the main consequence of the overestimation bias is that is severely slows down convergence. This of course can be overcome with Double Q-learning.

The answer above is for the tabular Q-Learning case. The idea is the same for the the Deep Q-Learning, except note that Deep Q-learning has no convergence guarantees (when using a NN as the function approximator) and so the overestimation bias is more of a problem as it can mean the parameters of the network get stuck in sub-optimal values.

As someone asked in the comments about always initialising the values to be very low numbers, this would not really work.

Consider the following MDP taken from Sutton and Barto: We start in state A, from which we can either go right with reward 0 leading to a terminal state or go left with reward 0 to state B. From state B we can take, say, 100 different actions, all of which lead to a terminal state and have reward drawn from a Normal distribution with mean -0.1 and variance 1.

Now, clearly the optimal action from state A is to go right. However, when we go left and take an action in state B there is an (almost) 0.5 probability of getting a reward bigger than 0. Now, recall that the Q-value is shifted towards $r(s, a) + \max_a Q(s', a)$; because of the stochastic rewards when transitioning out of state B and the fact that we will likely see a positive reward the $\max_a Q(s', a)$ will be positive.

This means that when we take the left action the Q-value (Q(A, left)) is shifted towards a positive value, meaning that when we are in state A the value of moving left will be higher than moving right (which will gradually be being shifted towards the true value of 0) and so when following the $\epsilon$-greedy policy the greedy action will be to go left when in fact this is sub-optimal.

Now, of course, we know that the true Q-values will eventually converge but if we do have, say, 100 actions then you can probably see that the time it will take for the Q-values to converge to the true value will potentially be a long time as we would have to keep choosing all the overestimated values until we had convergence.

$\endgroup$
7
  • 2
    $\begingroup$ Why couldn't you then initialize everything with let's say $-\infty$ or very negative value to prevent this overestimation, if this is really because of random initialization, why would you then need double Q-learning. $\endgroup$
    – Brale
    Jan 10 at 18:58
  • $\begingroup$ You may find a more rigorous explanation in the original double Q-learning paper. $\endgroup$
    – nbro
    Jan 10 at 19:30
  • $\begingroup$ @brale you’re right, my answer isn’t satisfactory. I’ll expand on it tomorrow. I have a nice example where rewards are stochastic that can illustrate the example. $\endgroup$ Jan 10 at 20:33
  • $\begingroup$ Unfortunately, I haven't received a solid explanation for overestimation. To the end, it doesn't stack up, and there's no reason to overestimate if it finally converges. Ultimately, the question is how much faster learning can be done by modifying this expression than other methods that streamline learning. Do you have the resources to compare with other learning efficiency methods? $\endgroup$ Jan 10 at 21:10
  • 1
    $\begingroup$ @groundclown I just finished making another edit, could you let me know whether this clears things up for you, please. You say there is 'no reason' to overestimate - could you elaborate on this as I'm not sure what you mean. The reason we overestimate is clear - because we are taking the $\max$ of a noisy estimate. The reason it is an issue is because it severely slows down convergence. $\endgroup$ Jan 10 at 21:14

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.