Answers.Body: <p>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 <span class="math-container">$\max$</span> operator in the construction of the target policy. The most obvious case is, as you mentioned, Q-learning. The learning update is
  <span class="math-container">$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$</span>
  The Q-function for the state-action tuple we are considering is shifted towards the <em>max</em> Q-function at the next state where the <span class="math-container">$\max$</span> is taken with respect to the actions.</p>
  <p>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 <span class="math-container">$\max_aQ(s', a)$</span> we could be choosing values that are grossly <em>overestimated</em>.</p>
  <p>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.</p>
  <p>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.</p>
  <p>As someone asked in the comments about always initialising the values to be very low numbers, this would not really work.</p>
  <p>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.</p>
  <p>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 <span class="math-container">$r(s, a) + \max_a Q(s', a)$</span>; because of the stochastic rewards when transitioning out of state B and the fact that we will likely see a positive reward the <span class="math-container">$\max_a Q(s', a)$</span> will be positive.</p>
  <p>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 <span class="math-container">$\epsilon$</span>-greedy policy the greedy action will be to go left when in fact this is sub-optimal.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T18:58:45.320Z
Answers.Text: 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.
Answers.UserDisplayName: Brale
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T19:30:45.123Z
Answers.Text: You may find a more rigorous explanation in the original [double Q-learning](https://papers.nips.cc/paper/2010/file/091d584fced301b442654dd8c23b3fc9-Paper.pdf) paper.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T20:33:33.807Z
Answers.Text: @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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T21:10:06.320Z
Answers.Text: 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?
Answers.UserDisplayName: ground clown
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T21:14:04.347Z
Answers.Text: @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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T21:20:24.123Z
Answers.Text: This starts to be an exact duplicate of this: https://ai.stackexchange.com/q/22776/2444. The original question was why Q-learning overestimates the values. The question was not something different, such as "Why would we need Double DQN" or "Could we initialize the values to minus infinity?". So, your original answer already answered the original question. It's probably better to just link to your other answer, if it contains the exact info, rather than writing everything here again. This is just my suggestion.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T21:24:40.173Z
Answers.Text: Thanks @nbro, I thought as much (and also didn't want to have to repeat myself!).
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-10T17:44:31.027Z
Answers.LastActivityDate: 2021-01-10T21:13:42.720Z
Answers.LastEditDate: 2021-01-10T21:13:42.720Z
Answers.UserDisplayName: David
Body: <p>The motivation for the introduction of <em>double DQN</em> (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?</p>
  
Tags: <reinforcement-learning><q-learning><dqn><double-dqn><double-q-learning>
Title: Why does regular Q-learning (and DQN) overestimate the Q values?
UserDisplayName: ground clown
ThreadText: # Why does regular Q-learning (and DQN) overestimate the Q values?
  
  (Asked by: username_0 on 2021-01-10)
  
  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?
  
  **Tags:** reinforcement-learning, q-learning, dqn, double-dqn, double-q-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-01-10. Score: 4
  
  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.
  
  > **Comments:**
  > **username_2**: 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.  
  > **username_3**: You may find a more rigorous explanation in the original [double Q-learning](https://papers.nips.cc/paper/2010/file/091d584fced301b442654dd8c23b3fc9-Paper.pdf) paper.  
  > **username_1**: @username_2 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.  
  > **username_0**: 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?  
  > **username_1**: @username_0 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.  
  > **username_3**: This starts to be an exact duplicate of this: https://ai.stackexchange.com/q/22776/2444. The original question was why Q-learning overestimates the values. The question was not something different, such as "Why would we need Double DQN" or "Could we initialize the values to minus infinity?". So, your original answer already answered the original question. It's probably better to just link to your other answer, if it contains the exact info, rather than writing everything here again. This is just my suggestion.  
  > **username_1**: Thanks @username_3, I thought as much (and also didn't want to have to repeat myself!).  
  
  ---
  
  