Answers.Body: <p>In <span class="math-container">$Q$</span>-learning there is what is known as a maximisation bias. That is because the update target is <span class="math-container">$r + \gamma \max_a Q(s,a)$</span>. If you slightly overestimate your <span class="math-container">$Q$</span>-value then this error gets compounded (there is a nice example in the Sutton and Barto book that illustrates this). The idea behind tabular double <span class="math-container">$Q$</span>-learning is to have two <span class="math-container">$Q$</span>-networks, <span class="math-container">$Q_1,Q_2$</span>, and you choose an action <span class="math-container">$a$</span> from them, e.g. from <span class="math-container">$Q_1 + Q_2$</span>. You then flip a coin to decide which to update. If you choose to update <span class="math-container">$Q_1$</span> then the update target becomes <span class="math-container">$r + \gamma Q_2(s', \arg\max_a Q_1(s',a))$</span>.</p>
  <p>The idea is that if you overshoot your estimate on one <span class="math-container">$Q$</span> network then having the second will hopefully control this bias when you would take the max.</p>
  <p>In Deep Double <span class="math-container">$Q$</span>-learning the idea is essentially the same but instead of having to maintain and train two <span class="math-container">$Q$</span>-networks, they use the target network from vanilla DQN to provide the target. To make this more concrete, the update target they use is
  <span class="math-container">$$r + \gamma Q(s', \arg\max_aQ(s',a;\theta);\theta^-)\;,$$</span>
  where <span class="math-container">$Q(s,a;\theta^-)$</span> denotes the target network whose parameters are only updated to the current networks every <span class="math-container">$C$</span> time steps.</p>
  <p>As before, the idea is that if we have overestimated our value of being state <span class="math-container">$s'$</span> in our current network when taking the max action, using the target network to provide the target will help control for this bias.</p>
  <h2>Maximisation Bias</h2>
  <p>I will here explain maximisation bias from the simple example given from the Sutton and Barto book.</p>
  <p><a href="https://i.sstatic.net/d3B7w.png" rel="noreferrer"><img src="https://i.sstatic.net/d3B7w.png" alt="enter image description here" /></a></p>
  <p>The Markov Decision Process in the image is defined as follows: we start in state A and can take the 'right' action which gives us 0 reward and immediately leads to termination. If we choose 'left' we get 0 immediate reward where we then move to state B. From there, we have an arbitrary number of action we can take where they all lead to the terminal state and the reward is drawn from a Normal(-0.1,1) distribution.</p>
  <p>Clearly, the optimal action is always to move to the right from state A as this gives 0 expected future returns. Taking the left action will give a <span class="math-container">$\gamma \times -0.1$</span> expected future returns (the <span class="math-container">$\gamma$</span> is our discount factor).</p>
  <p>Now, if we got into state <span class="math-container">$B$</span> and took some random action our initial reward could be bigger than 0 -- after all it is drawn from a Normal(-0.1,1) distribution.</p>
  <p>Now, consider we are updating our <span class="math-container">$Q$</span>-function for state A and taking the left action. Our update target will be <span class="math-container">$0 + \gamma \max_a Q(B,a)$</span>. Because we are taking the max over all possible actions, this will lead to a positive reward and so we are backing up the belief of our expected future rewards from taking action left in state A to be something positive -- clearly this is wrong since we know it should be -0.1. This is what is known as the maximisation bias, because it gives us a kind of 'optimistic' estimate of the action value!</p>
  <p>I've attached an image below that shows the %age of time the agent chose the left action, which it <em>shouldn't</em> be choosing). As you can see, it takes normal <span class="math-container">$Q$</span>-learning along time to even start to correct itself, whereas double <span class="math-container">$Q$</span>-learning corrects the mistake almost immediately.</p>
  <p><a href="https://i.sstatic.net/4hepx.png" rel="noreferrer"><img src="https://i.sstatic.net/4hepx.png" alt="enter image description here" /></a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-30T22:10:17.093Z
Answers.Text: Suppose our target network is the one overestimating our Q values. We use our main value network for selecting the action and use our target for calculating Q values. Wouldn't this value still be overestimated?
Answers.UserDisplayName: Chukwudi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-31T09:30:45.190Z
Answers.Text: Well, the target network is randomly initialized, so that is unlikely to be the case.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-31T09:40:43.343Z
Answers.Text: But, at the beginning of training, isn't our target network just a copy of our main value network? What happens if those weights overestimate the values?
Answers.UserDisplayName: Chukwudi
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-31T11:04:38.240Z
Answers.Text: Yes, exactly. However, your online/main value network is just randomly initialized... Depending on the method, they usually just initialize it to very small values, so, as I say, it is unlikely to have a strong effect.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T07:47:18.230Z
Answers.Text: Interestingly DDQN is not going to 0%!
Answers.UserDisplayName: Mohit
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-25T09:28:44.283Z
Answers.Text: @mohit yes, this is because of the $\epsilon$-greedy exploration.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-30T20:08:55.683Z
Answers.LastActivityDate: 2020-07-31T13:26:07.227Z
Answers.LastEditDate: 2020-07-31T13:26:07.227Z
Answers.UserDisplayName: David
Body: <p>I started looking into the <em>double DQN</em> (DDQN). Apparently, the difference between DDQN and DQN is that in DDQN we use the main value network for action selection and the target network for outputting the Q values.</p>
  <p>However, I don't understand why would this be beneficial, compared to the standard DQN. So, in simple terms, what exactly is the advantage of DDQN over DQN?</p>
  
Tags: <comparison><q-learning><dqn><deep-rl><double-dqn>
Title: What exactly is the advantage of double DQN over DQN?
UserDisplayName: Chukwudi
ThreadText: # What exactly is the advantage of double DQN over DQN?
  
  (Asked by: username_0 on 2020-07-30)
  
  I started looking into the *double DQN* (DDQN). Apparently, the difference between DDQN and DQN is that in DDQN we use the main value network for action selection and the target network for outputting the Q values.
  
  However, I don't understand why would this be beneficial, compared to the standard DQN. So, in simple terms, what exactly is the advantage of DDQN over DQN?
  
  **Tags:** comparison, q-learning, dqn, deep-rl, double-dqn
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-07-30. Score: 11 | Accepted answer
  
  In $Q$-learning there is what is known as a maximisation bias. That is because the update target is $r + \gamma \max\_a Q(s,a)$. If you slightly overestimate your $Q$-value then this error gets compounded (there is a nice example in the Sutton and Barto book that illustrates this). The idea behind tabular double $Q$-learning is to have two $Q$-networks, $Q\_1,Q\_2$, and you choose an action $a$ from them, e.g. from $Q\_1 + Q\_2$. You then flip a coin to decide which to update. If you choose to update $Q\_1$ then the update target becomes $r + \gamma Q\_2(s', \arg\max\_a Q\_1(s',a))$.
  
  The idea is that if you overshoot your estimate on one $Q$ network then having the second will hopefully control this bias when you would take the max.
  
  In Deep Double $Q$-learning the idea is essentially the same but instead of having to maintain and train two $Q$-networks, they use the target network from vanilla DQN to provide the target. To make this more concrete, the update target they use is
  $$r + \gamma Q(s', \arg\max\_aQ(s',a;\theta);\theta^-)\;,$$
  where $Q(s,a;\theta^-)$ denotes the target network whose parameters are only updated to the current networks every $C$ time steps.
  
  As before, the idea is that if we have overestimated our value of being state $s'$ in our current network when taking the max action, using the target network to provide the target will help control for this bias.
  
  ## Maximisation Bias
  
  I will here explain maximisation bias from the simple example given from the Sutton and Barto book.
  
  [![enter image description here](https://i.sstatic.net/d3B7w.png)](https://i.sstatic.net/d3B7w.png)
  
  The Markov Decision Process in the image is defined as follows: we start in state A and can take the 'right' action which gives us 0 reward and immediately leads to termination. If we choose 'left' we get 0 immediate reward where we then move to state B. From there, we have an arbitrary number of action we can take where they all lead to the terminal state and the reward is drawn from a Normal(-0.1,1) distribution.
  
  Clearly, the optimal action is always to move to the right from state A as this gives 0 expected future returns. Taking the left action will give a $\gamma \times -0.1$ expected future returns (the $\gamma$ is our discount factor).
  
  Now, if we got into state $B$ and took some random action our initial reward could be bigger than 0 -- after all it is drawn from a Normal(-0.1,1) distribution.
  
  Now, consider we are updating our $Q$-function for state A and taking the left action. Our update target will be $0 + \gamma \max\_a Q(B,a)$. Because we are taking the max over all possible actions, this will lead to a positive reward and so we are backing up the belief of our expected future rewards from taking action left in state A to be something positive -- clearly this is wrong since we know it should be -0.1. This is what is known as the maximisation bias, because it gives us a kind of 'optimistic' estimate of the action value!
  
  I've attached an image below that shows the %age of time the agent chose the left action, which it *shouldn't* be choosing). As you can see, it takes normal $Q$-learning along time to even start to correct itself, whereas double $Q$-learning corrects the mistake almost immediately.
  
  [![enter image description here](https://i.sstatic.net/4hepx.png)](https://i.sstatic.net/4hepx.png)
  
  > **Comments:**
  > **username_0**: Suppose our target network is the one overestimating our Q values. We use our main value network for selecting the action and use our target for calculating Q values. Wouldn't this value still be overestimated?  
  > **username_1**: Well, the target network is randomly initialized, so that is unlikely to be the case.  
  > **username_0**: But, at the beginning of training, isn't our target network just a copy of our main value network? What happens if those weights overestimate the values?  
  > **username_1**: Yes, exactly. However, your online/main value network is just randomly initialized... Depending on the method, they usually just initialize it to very small values, so, as I say, it is unlikely to have a strong effect.  
  > **username_2**: Interestingly DDQN is not going to 0%!  
  > **username_1**: @username_2 yes, this is because of the $\epsilon$-greedy exploration.  
  
  ---
  
  