Answers.Body: <p>When training a Deep Q network with experienced replay, you accumulate what is known as training experiences <span class="math-container">$e_t = (s_t, a_t, r_t, s_{t+1})$</span>. You then sample a batch of such experiences and for each sample you do the following.</p>
  
  <ol>
  <li>Feed <span class="math-container">$s_t$</span> into the network to get <span class="math-container">$Q(s,a;\theta)$</span>.</li>
  <li>Feed <span class="math-container">$s_{t+1}$</span> into the network to get <span class="math-container">$Q(s’,a’,\theta)$</span>.</li>
  <li>Choose <span class="math-container">$max_aQ(s’,a’,\theta)$</span> and set <span class="math-container">$ \gamma max_aQ(s’,a’,θ)$</span> + <span class="math-container">$r_t$</span> as the target of the network.</li>
  <li>Train the network with <span class="math-container">$s_t$</span> as input to update <span class="math-container">$\theta$</span>. The output from the input of <span class="math-container">$s_t$</span> is <span class="math-container">$Q(s,a,\theta)$</span> and the gradient descent step minimises the squared distance between <span class="math-container">$Q(s,a,\theta)$</span> and <span class="math-container">$\gamma max_aQ(s’,a’,θ)$</span> + <span class="math-container">$r_t$</span></li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T12:27:45.833Z
Answers.Text: Ah, so the target values of Q(s,a) = Reward for performing action a in state s + Max Q( s′,a′ ) for next state s′.
  I can find out the Max Q( s′,a′ ) by looking through my batch of stored experiences( since I have data on the Q values of next state s′), and hence find the target value of Q(s,a)
Answers.UserDisplayName: BG10
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T16:42:11.457Z
Answers.Text: Ur neural network outputs all possible Q(s’, a’) values over all actions. Hence, u can find the max of these values easily
Answers.UserDisplayName: calveeen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T23:56:56.087Z
Answers.Text: Oh, so my batch of stored experiences will be used as input to my neural net, which will output all the possible Q values of that state S( If I only inputted 1 state) / States S,S',...(If I inputted more than 1 state)
Answers.UserDisplayName: BG10
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T04:46:45.717Z
Answers.Text: ur batch of samples can contain different s, s' pairs. the input to a neural network is the state. I am not sure what u mean by "inputted 1 state" ?
Answers.UserDisplayName: calveeen
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T09:24:47.860Z
Answers.LastActivityDate: 2020-04-19T09:24:47.860Z
Answers.UserDisplayName: calveeen
Answers.Body: <p>The deep Q-learning (DQL) algorithm is really similar to the tabular Q-learning algorithm. I think that both algorithms are actually quite simple, at least, if you look at their pseudocode, which isn't longer than 10-20 lines.</p>
  
  <p>Here's a screenshot of the pseudocode of DQL (from <a href="https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf" rel="nofollow noreferrer">the original paper</a>) that highlights the Q target.</p>
  
  <p><a href="https://i.sstatic.net/Eyy49.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Eyy49.png" alt="enter image description here"></a></p>
  
  <p>Here's the screenshot of Q-learning (from <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="nofollow noreferrer">Barto and Sutton's book</a>) that highlights the Q target.</p>
  
  <p><a href="https://i.sstatic.net/qgJdk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/qgJdk.png" alt="enter image description here"></a></p>
  
  <p>In both cases, the <span class="math-container">$\color{red}{\text{target}}$</span> is a <strong>reward plus a discounted maximum future Q value</strong> (apart from the exception of final states, in the case of DQL, where the target is just the reward). </p>
  
  <p>There are at least 3 differences between these two algorithms. </p>
  
  <ul>
  <li><p>DQL uses gradient descent because the <span class="math-container">$Q$</span> function are represented by neural networks rather than tables, like in Q-learning, and so you have an explicit loss function (e.g. MSE).</p></li>
  <li><p>DQL typically uses experience replay (but, in principle, you could also do this in Q-learning) </p></li>
  <li>DQL encodes the states (i.e. <span class="math-container">$\phi$</span> encodes the states). </li>
  </ul>
  
  <p>Apart from that, the logic of both algorithms is more or less the same, so, if you know Q-learning (and you should know it before diving into DQL), then it shouldn't be a problem to learn DQL (if you also have a decent knowledge of deep learning).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T23:54:50.653Z
Answers.Text: Ah, so for Q-learning I use the Q learning update rule to make my Q function values converge, while for DQN I use gradient descent to make my Q function values converge. How does the company batch of stored experiences come into play though? (Used to feed the neural net?)
Answers.UserDisplayName: BG10
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T00:02:49.697Z
Answers.Text: @BG10 Sorry, I realized I had already said that about gradient descent. Regarding the experience replay, it's used to stabilize the neural network learning, given that successive states in a typical RL task are correlated and NNs don't learn well when data is highly correlated, so, rather than performing gradient descent with successive tuples of experience, you perform it with randomly selected tuples from the experience replay buffer. In Q-learning, you don't have this issue because you don't have NNs.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T00:28:06.960Z
Answers.Text: I understand the part where we want the tuples of experiences sampled to be independent and identically distributed. However, when you say 'to stabilize the neural network learning' , does this mean you want the neural network to give better Q-function outputs, through gradient descent of the randomized samples?
Answers.UserDisplayName: BG10
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T00:32:42.833Z
Answers.Text: @BG10 By "stabilize" I mean that your performance metric doesn't go up and down, but more regularly increases or decreases. In this case, the performance could be the metric or the Q values. If you look [at original paper for DQL](https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf), the authors say a similar thing.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T00:41:03.610Z
Answers.Text: So you use random samples to ensure outputted Q-values for the same state and action, but from different episodes, are less volatile? And gradient descent is used to make the estimated Q values(outputted from the Q-network) closer to the target Q values(outputted from the target network)
Answers.UserDisplayName: BG10
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-20T02:33:32.930Z
Answers.Text: @BG10 I wouldn't use the word "volatile" in this case. I would use "variable" or "unstable". Also, not necessarily only from different episodes. In general, during the whole training, you will be collecting rewards. You can e.g. print a plot of the amount of rewards you obtain at every step or episode. That will give you an idea of the performance (or not). Note: this is just an example to make you understand. I am not saying that the authors of DQN did this. Regarding your second question, GD is used to minimize a loss, which happens to be a function of the predicted and target Q values.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T12:31:57.617Z
Answers.LastActivityDate: 2020-04-19T23:59:45.223Z
Answers.LastEditDate: 2020-04-19T23:59:45.223Z
Answers.UserDisplayName: nbro
Answers.Body: <blockquote>
  <p>What does the target Q-values represent?</p>
  </blockquote>
  <p>In a DQN, which uses off-policy learning, they represent a <em>refined</em> estimate for the expected future reward from taking an action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>, and from that point on following a target policy. The target policy in Q learning is based on always taking the maximising action in each state, according to current estimates of value.</p>
  <p>The estimate is <em>refined</em> in that it is based on at least a little bit of data from experience - the immediate reward, and what transition happened next - but generally it is not going to be perfect.</p>
  <blockquote>
  <p>And how is it obtained/calculated by the DQN?</p>
  </blockquote>
  <p>There are lots of ways to do this. The simplest in DQN is to process a single step lookahead based on the experience replay table.</p>
  <p>If your table contains the tuple <em>[state, action, immediate reward, next state, done?]</em> as <span class="math-container">$[s, a, r, s', d]$</span> then the formula for TD target, <span class="math-container">$g_{t:t+1}$</span> is</p>
  <p><span class="math-container">$$r + \gamma \text{max}_{a'}[Q_{target}(s',a')], \qquad \text{when}\space d \space \text{is false}$$</span></p>
  <p><span class="math-container">$$r, \qquad \text{when}\space d \space \text{is true}$$</span></p>
  <p>Typically <span class="math-container">$Q_{target}$</span> is calculated using the &quot;target network&quot; which is a copy of the learning network for Q that is updated every N steps. This delayed update of the target predictions is done for numerical stability in DQN - conceptually it is an estimate for the same action values that you are learning.</p>
  <p>This target value can change every time you use any specific memory from experience replay. So you have to perform the same calculations on each minibatch, you cannot store the target values.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-19T09:29:04.090Z
Answers.LastActivityDate: 2021-01-18T01:05:46.710Z
Answers.LastEditDate: 2021-01-18T01:05:46.710Z
Answers.UserDisplayName: Neil Slater
Body: <p>I understand that in DQNs, the loss is measured by taking the MSE of outputted Q-values and target Q-values.</p>
  <p>What does the target Q-values represent? And how is it obtained/calculated by the DQN?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-19T20:55:35.960Z
Comments.Text: See also this related question: [Why is the target $r + \gamma \max_{a'} Q(s', a'; \theta_i^-)$ in the loss function of the DQN architecture?](https://ai.stackexchange.com/q/4740/2444).
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><q-learning><dqn><deep-rl><value-functions>
Title: What is the target Q-value in DQNs?
UserDisplayName: BG10
ThreadText: # What is the target Q-value in DQNs?
  
  (Asked by: username_0 on 2020-04-19)
  
  I understand that in DQNs, the loss is measured by taking the MSE of outputted Q-values and target Q-values.
  
  What does the target Q-values represent? And how is it obtained/calculated by the DQN?
  
  **Tags:** reinforcement-learning, q-learning, dqn, deep-rl, value-functions
  > **Comments:**
  > **username_1**: See also this related question: [Why is the target $r + \gamma \max_{a'} Q(s', a'; \theta_i^-)$ in the loss function of the DQN architecture?](https://ai.stackexchange.com/q/4740/2444).  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_2 on 2020-04-19. Score: 5
  
  When training a Deep Q network with experienced replay, you accumulate what is known as training experiences $e\_t = (s\_t, a\_t, r\_t, s\_{t+1})$. You then sample a batch of such experiences and for each sample you do the following.
  
  1. Feed $s\_t$ into the network to get $Q(s,a;\theta)$.
  2. Feed $s\_{t+1}$ into the network to get $Q(s’,a’,\theta)$.
  3. Choose $max\_aQ(s’,a’,\theta)$ and set $ \gamma max\_aQ(s’,a’,θ)$ + $r\_t$ as the target of the network.
  4. Train the network with $s\_t$ as input to update $\theta$. The output from the input of $s\_t$ is $Q(s,a,\theta)$ and the gradient descent step minimises the squared distance between $Q(s,a,\theta)$ and $\gamma max\_aQ(s’,a’,θ)$ + $r\_t$
  
  > **Comments:**
  > **username_0**: Ah, so the target values of Q(s,a) = Reward for performing action a in state s + Max Q( s′,a′ ) for next state s′. I can find out the Max Q( s′,a′ ) by looking through my batch of stored experiences( since I have data on the Q values of next state s′), and hence find the target value of Q(s,a)  
  > **username_2**: Ur neural network outputs all possible Q(s’, a’) values over all actions. Hence, u can find the max of these values easily  
  > **username_0**: Oh, so my batch of stored experiences will be used as input to my neural net, which will output all the possible Q values of that state S( If I only inputted 1 state) / States S,S',...(If I inputted more than 1 state)  
  > **username_2**: ur batch of samples can contain different s, s' pairs. the input to a neural network is the state. I am not sure what u mean by "inputted 1 state" ?  
  
  ---
  
  ### Answer by username_1 on 2020-04-19. Score: 3
  
  The deep Q-learning (DQL) algorithm is really similar to the tabular Q-learning algorithm. I think that both algorithms are actually quite simple, at least, if you look at their pseudocode, which isn't longer than 10-20 lines.
  
  Here's a screenshot of the pseudocode of DQL (from [the original paper](https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf)) that highlights the Q target.
  
  [![enter image description here](https://i.sstatic.net/Eyy49.png)](https://i.sstatic.net/Eyy49.png)
  
  Here's the screenshot of Q-learning (from [Barto and Sutton's book](http://incompleteideas.net/book/RLbook2020.pdf)) that highlights the Q target.
  
  [![enter image description here](https://i.sstatic.net/qgJdk.png)](https://i.sstatic.net/qgJdk.png)
  
  In both cases, the $\color{red}{\text{target}}$ is a **reward plus a discounted maximum future Q value** (apart from the exception of final states, in the case of DQL, where the target is just the reward).
  
  There are at least 3 differences between these two algorithms.
  
  * DQL uses gradient descent because the $Q$ function are represented by neural networks rather than tables, like in Q-learning, and so you have an explicit loss function (e.g. MSE).
  * DQL typically uses experience replay (but, in principle, you could also do this in Q-learning)
  * DQL encodes the states (i.e. $\phi$ encodes the states).
  
  Apart from that, the logic of both algorithms is more or less the same, so, if you know Q-learning (and you should know it before diving into DQL), then it shouldn't be a problem to learn DQL (if you also have a decent knowledge of deep learning).
  
  > **Comments:**
  > **username_0**: Ah, so for Q-learning I use the Q learning update rule to make my Q function values converge, while for DQN I use gradient descent to make my Q function values converge. How does the company batch of stored experiences come into play though? (Used to feed the neural net?)  
  > **username_1**: @BG10 Sorry, I realized I had already said that about gradient descent. Regarding the experience replay, it's used to stabilize the neural network learning, given that successive states in a typical RL task are correlated and NNs don't learn well when data is highly correlated, so, rather than performing gradient descent with successive tuples of experience, you perform it with randomly selected tuples from the experience replay buffer. In Q-learning, you don't have this issue because you don't have NNs.  
  > **username_0**: I understand the part where we want the tuples of experiences sampled to be independent and identically distributed. However, when you say 'to stabilize the neural network learning' , does this mean you want the neural network to give better Q-function outputs, through gradient descent of the randomized samples?  
  > **username_1**: @BG10 By "stabilize" I mean that your performance metric doesn't go up and down, but more regularly increases or decreases. In this case, the performance could be the metric or the Q values. If you look [at original paper for DQL](https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf), the authors say a similar thing.  
  > **username_0**: So you use random samples to ensure outputted Q-values for the same state and action, but from different episodes, are less volatile? And gradient descent is used to make the estimated Q values(outputted from the Q-network) closer to the target Q values(outputted from the target network)  
  > **username_1**: @BG10 I wouldn't use the word "volatile" in this case. I would use "variable" or "unstable". Also, not necessarily only from different episodes. In general, during the whole training, you will be collecting rewards. You can e.g. print a plot of the amount of rewards you obtain at every step or episode. That will give you an idea of the performance (or not). Note: this is just an example to make you understand. I am not saying that the authors of DQN did this. Regarding your second question, GD is used to minimize a loss, which happens to be a function of the predicted and target Q values.  
  
  ---
  
  ### Answer by username_3 on 2020-04-19. Score: 3
  
  > What does the target Q-values represent?
  
  In a DQN, which uses off-policy learning, they represent a *refined* estimate for the expected future reward from taking an action $a$ in state $s$, and from that point on following a target policy. The target policy in Q learning is based on always taking the maximising action in each state, according to current estimates of value.
  
  The estimate is *refined* in that it is based on at least a little bit of data from experience - the immediate reward, and what transition happened next - but generally it is not going to be perfect.
  
  > And how is it obtained/calculated by the DQN?
  
  There are lots of ways to do this. The simplest in DQN is to process a single step lookahead based on the experience replay table.
  
  If your table contains the tuple *[state, action, immediate reward, next state, done?]* as $[s, a, r, s', d]$ then the formula for TD target, $g\_{t:t+1}$ is
  
  $$r + \gamma \text{max}\_{a'}[Q\_{target}(s',a')], \qquad \text{when}\space d \space \text{is false}$$
  
  $$r, \qquad \text{when}\space d \space \text{is true}$$
  
  Typically $Q\_{target}$ is calculated using the "target network" which is a copy of the learning network for Q that is updated every N steps. This delayed update of the target predictions is done for numerical stability in DQN - conceptually it is an estimate for the same action values that you are learning.
  
  This target value can change every time you use any specific memory from experience replay. So you have to perform the same calculations on each minibatch, you cannot store the target values.
  
  
  ---
  
  