Why does regular Q-learning (and DQN) overestimate the Q values?

Question

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?

Answer 1

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.