Answers.Body: <p>Most Deep Q-learning implementations I have read are based on <a href="https://deepmind.com/research/dqn/" rel="nofollow noreferrer">Deep Q-Networks</a> (DQN).  In DQN, the q-value network maps an input state to a vector of q-values, one for each action:</p>
  
  <p><span class="math-container">$$
  Q(s, \mathbf{w}) \to \mathbf{v}
  $$</span></p>
  
  <p>where <span class="math-container">$s$</span> is the input state from the environment, <span class="math-container">$\mathbf{w}$</span> are the parameters of the neural network, and <span class="math-container">$\mathbf{v}$</span> is a vector of q-values, where <span class="math-container">$v_i$</span> is the estimated q-value of the ith action. In the <a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">Sutton and Barto book</a>, the q-value function is written as <span class="math-container">$Q(s, a, \mathbf{w})$</span>, which corresponds to the network output for action <span class="math-container">$a$</span>.</p>
  
  <p>Unlike tabular Q-learning, Deep Q-learning updates the parameters of the the neural network according to the gradients of the loss function with respect to the parameters. DQN uses the loss function</p>
  
  <p><span class="math-container">$$
  L(\mathbf{w}) = [(r + \gamma max_{a'} Q(s', a', \mathbf{w^-})) - Q(s, a, \mathbf{w})]^2
  $$</span></p>
  
  <p>where <span class="math-container">$\gamma$</span> is the discount rate, <span class="math-container">$a$</span> is the selected action (either greedily or randomly for an <span class="math-container">$epsilon$</span>-greedy behavior policy), <span class="math-container">$s'$</span> is the next state, <span class="math-container">$a'$</span> is the argmax action for the next state, and <span class="math-container">$\mathbf{w^-}$</span> is an older version of the network weights <span class="math-container">$\mathbf{w}$</span> that is used to help stabilize training.</p>
  
  <p>In deep Q-learning, training directly updates parameters, not q-values. Parameters are updated by taking a small step in the direction of the gradient of the loss function</p>
  
  <p><span class="math-container">$$
  \mathbf{w} \gets \mathbf{w} + \alpha [(r + \gamma max_{a'} Q(s', a', \mathbf{w^-})) - Q(s, a, \mathbf{w})] \nabla_w Q(s, a, \mathbf{w})
  $$</span></p>
  
  <p>where <span class="math-container">$\alpha$</span> is the learning rate.</p>
  
  <p>In frameworks like tensorflow or pytorch the derivative is calculated automatically by giving the loss function and model parameters directly to an optimizer class which uses some variation of mini-batch gradient descent. In eagerly executed tensorflow updating the parameters for a mini-batch might look something like</p>
  
  <pre><code>batch = buffer.sample(batch_size)
  observations, actions, rewards, next_obervations = batch
  
  with tf.GradientTape() as tape:
      qvalues = model(observations, training=True)
      next_qvalues = target_model(next_obervations)
      # r + max_{a'} Q(s', a') for the batch
      target_qvalues = rewards + gamma * tf.reduce_max(next_qvalues, axis=-1)
      # Q(s, a) for the batch
      selected_qvalues = tf.reduce_sum(tf.one_hot(actions, depth=qvalues.shape[-1]) * qvalues, axis=-1)
      loss = tf.reduce_mean((target_qvalues - selected_qvalues)**2)
  
  grads = tape.gradient(loss, model.variables)
  optimizer.apply_gradients(zip(grads, model.variables))
  </code></pre>
  
  <p>Though I am not familiar with the Encog neural network framework you are using, based on the example <code>Brain.java</code> file from your <a href="https://github.com/SuchtyTV/RLearningBird/blob/master/src/main/java/rlgame/Brain.java" rel="nofollow noreferrer">Github repo</a> and Chapter 5 of the Encog <a href="https://s3.amazonaws.com/heatonresearch-books/free/Encog3Java-User.pdf" rel="nofollow noreferrer">User Manual</a> and the Encog neural network <a href="https://github.com/encog/encog-java-examples/tree/master/src/main/java/org/encog/examples/neural" rel="nofollow noreferrer">examples on Github</a> it looks like weights are updated as follows:</p>
  
  <ol>
  <li>A training set is constructed from pairs of <strong>input</strong> and <strong>target output</strong>.</li>
  <li>A <code>Propagation</code> instance, <code>train</code>, is constructed with a network and training set. Different subclasses of <code>Propagation</code> use different loss functions to update the network parameters.</li>
  <li>The method <code>train.iterate()</code> is called to run the network on the inputs, calculate the loss between the network outputs and target outputs, and update the weights according to the loss.</li>
  </ol>
  
  <p>For DQN, a training set is constructed from a random sample from the experience replay buffer to help stabilize training. A training set could also be the trajectory of an episode, which is what the <code>tupels</code> argument in the example code of the question appears to be.</p>
  
  <p>The <strong>input</strong> would be the <code>statefirst</code> member of each element of <code>tupels</code>. Since the network produces a vector of q-values, the <strong>target output</strong> must also be a vector of q-values. </p>
  
  <p>The target output element for the selected action is <span class="math-container">$r + \gamma max_{a'} Q(s', a', \mathbf{w^-})$</span>,  In the example code of the question, this is</p>
  
  <pre><code>double qnew = 0;
  if(i &lt;= tupels.size()-2){
      qnew = tupels.get(i).rewardafter + discountfactor*qMax(tupels.get(i+1));
  } else {
      qnew = tupels.get(i).rewardafter;
  }
  tupels.get(i).qactions.elements[tupels.get(i).actionTaken] = qnew
  </code></pre>
  
  <p>The target output elements for actions that were not selected should be <span class="math-container">$Q(s, b, \mathbf{w})$</span>, where <span class="math-container">$b$</span> is one of the non-selected actions.  This should have the effect of ignoring the q-values of non-selected actions by making the network output equal to the target output.</p>
  
  <p><em>So what are the new Q - Values, assuming a discount factor of 0.99 and the learning rate 0.1?</em></p>
  
  <p>Assuming you mean <strong>target outputs</strong> by the new Q - Values, and given the trajectory of actions, <code>(1, 1, 1)</code>, and q-value vectors from the question, the concrete target outputs are <code>(0, 0 + 0.99 * 0, -5, 0)</code>, <code>(0, 0 + 0.99 * 0, 0, 0)</code>, and <code>(0, 1 + 0, 0, 0)</code>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-05T09:55:11.890Z
Answers.Text: $$w←w+α[(r+γmaxa′Q(s′,a′,w−))−Q(s,a,w)]∇wQ(s,a,w)$$
  Does this mean I have to hold always an older version of the network? 
  I do not understand this. I understand what the loss function does. It is the normal loss function for most BP-algorithms. But how to calculate:
  
  $$maxa′Q(s′,a′,w−))$$
Answers.UserDisplayName: TVSuchty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T07:06:32.883Z
Answers.Text: Yes, the DQN method uses an older version of the model which gets replaced every N time steps by the current model. According to the paper this improves training.
Answers.UserDisplayName: todddeluca
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T07:17:39.430Z
Answers.Text: You could calculate $max_{a'} Q(s', a', w^-)$ by running the state s' through an older copy of the model (i.e. the target network) and choosing the max of the outputs.
Answers.UserDisplayName: todddeluca
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-06T11:56:45.320Z
Answers.Text: Unfortunately, this still does not work. Is there anything else to consider. I must have done an obvious mistake.
Answers.UserDisplayName: TVSuchty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-01-05T05:26:57.870Z
Answers.LastActivityDate: 2019-01-05T05:26:57.870Z
Answers.UserDisplayName: todddeluca
Body: <p>I am not sure if I understood the q learning algorithms correctly. 
  Therefore I would give a concrete example and ask if someone can tell me how to update the q value correctly. </p>
  
  <p>First I initialized a Neural Network with random weights. It shall henceforth evaluate the Q Value for all possible actions(4) given a State S.</p>
  
  <p>Then the following happens. The agent is playing and is exploring. 
  For 3 steps the Q Values evaluated were:
  <em>(0,-1,-5,0), (0,-1,0,0), (0,-.6,0,0)</em></p>
  
  <p>The reward given was: <em>0,0,1</em>
  The action took were: <em>(1.,1.,1.)</em>
  In the random walk example (same reward given), it was: <em>(1.,2.,3.)</em></p>
  
  <p>So what are the new Q - Values, assuming a discount factor of 0.99 and the learning rate 0.1?</p>
  
  <p>The States for Simplicity are only one number: <em>1,1.3,2.4</em> Where 2.4 is the state who ends the game...</p>
  
  <p>The same example holds for exploiting. Is the algorithm the same here?</p>
  
  <p>Here you see my last implementation:</p>
  
  <pre><code>    public void rlearn(ArrayList&lt;Tuple&gt; tupels, double learningrate, double discountfactor) {
  
      //newQ = sum of all rewards you have got through
      for(int i = tupels.size()-1; i &gt; 0; i--) {
          MLData in = new BasicMLData(45);
          MLData out = new BasicMLData(5);
  
          //Add State as in
          int index = 0;
          for(double w : tupels.get(i).statefirst.elements) {
              in.add(index++, w);
          }
  
          //Now start updating Q - Values 
          double qnew = 0;
          if(i &lt;= tupels.size()-2){
              qnew = tupels.get(i).rewardafter + discountfactor*qMax(tupels.get(i+1));
          } else {
              qnew = tupels.get(i).rewardafter;
          }
  
          tupels.get(i).qactions.elements[tupels.get(i).actionTaken] = qnew;
          //Add Q Values as out
          index = 0;
          for(double w : tupels.get(i).qactions.elements) {
              out.add(index++, w);
          }
           bigset.add(in, out);
      }
  }
  </code></pre>
  
  <p>Edit: This is the qMax - function:</p>
  
  <pre><code>    private double qMax(Tuple tuple) {
      double max = Double.MIN_VALUE;
      for(double w : tuple.qactions.elements) {
          if(w &gt; max) {
              max = w;
          }
      }
      return max;
  }
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T15:32:52.677Z
Comments.Text: See https://ai.stackexchange.com/questions/7298/reinforcement-learning-in-asteroid-game/8028#8028
Comments.UserDisplayName: DrMcCleod
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T16:17:36.867Z
Comments.Text: Your example needs to give the action taken on each step that generated those sampled rewards. You should include at least one step where the non-maximising action was taken. For a full explanation, you should give the example data in the form of `state_label`, `predicted_rewards`, `action_taken`, `actual_reward`, `next_state_label`, `end_flag` - these don't all need to be in vector/numeric form, although it would help if the Q values and rewards are (as you have already done), plus the action id needs to be numeric in order to find what the predicted Q value was
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T16:30:39.450Z
Comments.Text: Your right, I edited the Acgtions taken, What are endflag and nextstatelabel?
Comments.UserDisplayName: TVSuchty
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T16:54:00.320Z
Comments.Text: `state_label` and `next_state_label` identify the states in the trajectory - it is implied in your question but not stated that your neural network estimates $(q(s, a_0), q(s, a_1), q(s, a_2), q(s, a_3) )$, and we need to know $s$. It is $q(s,a)$ that you revise, using $\text{max}_{a'} q(s',a')$ to improve the estimate, so you need to identify $s$ (`state_label`), $s'$ (`next_state_label`) and $a$. The `end_flag` is boolean - whether the transition ends an episode - that is critical information on how you learn Q values, because $\text{max}_{a'} q(s',a')$ is by definition $0$ in that case
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T16:57:46.717Z
Comments.Text: I understood the end_flag. But I think I do not understand the state label. For what do you need the states again? Just to recalculate the error of the net. (see above)
Comments.UserDisplayName: TVSuchty
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T17:43:23.353Z
Comments.Text: The ids of the states are needed to explain how the formula works. They are used both for calculating the new target value, and for showing *which* Q value is being updated. References to different states are used in different parts of the same step, so it is important to make it clear which state is being used and why.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T17:47:51.163Z
Comments.Text: If your examples are sequential from the same trajectory (looks like they are), then you will end up with repeats, so first time step might have `state_label` $s_a$ and  `next_state_label` $s_b$ then the second time step might have  `state_label` $s_b$ and  `next_state_label` $s_c$ etc - or you could make up a state vector for each one (because that's what you'd have for input to the NN). I am asking because I want you to add this information in the way that *you* understand it, so that the answer can explain things to you in your own terms.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T21:38:29.630Z
Comments.Text: I have added the stated. Can you now explain it to me?
Comments.UserDisplayName: TVSuchty
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-04T21:41:27.837Z
Comments.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/87855/discussion-between-tvsuchty-and-neil-slater).
Comments.UserDisplayName: TVSuchty
Tags: <deep-learning><reinforcement-learning><q-learning>
Title: Concrete Example for Q Learning
UserDisplayName: TVSuchty
ThreadText: # Concrete Example for Q Learning
  
  (Asked by: username_0 on 2019-01-04)
  
  I am not sure if I understood the q learning algorithms correctly. 
  Therefore I would give a concrete example and ask if someone can tell me how to update the q value correctly. 
  First I initialized a Neural Network with random weights. It shall henceforth evaluate the Q Value for all possible actions(4) given a State S.
  Then the following happens. The agent is playing and is exploring. 
  For 3 steps the Q Values evaluated were:
  (0,-1,-5,0), (0,-1,0,0), (0,-.6,0,0)
  The reward given was: 0,0,1
  The action took were: (1.,1.,1.)
  In the random walk example (same reward given), it was: (1.,2.,3.)
  So what are the new Q - Values, assuming a discount factor of 0.99 and the learning rate 0.1?
  The States for Simplicity are only one number: 1,1.3,2.4 Where 2.4 is the state who ends the game...
  The same example holds for exploiting. Is the algorithm the same here?
  Here you see my last implementation:
      public void rlearn(ArrayList tupels, double learningrate, double discountfactor) {
  
      //newQ = sum of all rewards you have got through
      for(int i = tupels.size()-1; i > 0; i--) {
          MLData in = new BasicMLData(45);
          MLData out = new BasicMLData(5);
  
          //Add State as in
          int index = 0;
          for(double w : tupels.get(i).statefirst.elements) {
              in.add(index++, w);
          }
  
          //Now start updating Q - Values 
          double qnew = 0;
          if(i <= tupels.size()-2){
              qnew = tupels.get(i).rewardafter + discountfactor*qMax(tupels.get(i+1));
          } else {
              qnew = tupels.get(i).rewardafter;
          }
  
          tupels.get(i).qactions.elements[tupels.get(i).actionTaken] = qnew;
          //Add Q Values as out
          index = 0;
          for(double w : tupels.get(i).qactions.elements) {
              out.add(index++, w);
          }
           bigset.add(in, out);
      }
  }
  
  Edit: This is the qMax - function:
      private double qMax(Tuple tuple) {
      double max = Double.MIN_VALUE;
      for(double w : tuple.qactions.elements) {
          if(w > max) {
              max = w;
          }
      }
      return max;
  }
  
  **Tags:** deep-learning, reinforcement-learning, q-learning
  > **Comments:**
  > **username_1**: See https://ai.stackexchange.com/questions/7298/reinforcement-learning-in-asteroid-game/8028#8028  
  > **username_2**: Your example needs to give the action taken on each step that generated those sampled rewards. You should include at least one step where the non-maximising action was taken. For a full explanation, you should give the example data in the form of `state_label`, `predicted_rewards`, `action_taken`, `actual_reward`, `next_state_label`, `end_flag` - these don't all need to be in vector/numeric form, although it would help if the Q values and rewards are (as you have already done), plus the action id needs to be numeric in order to find what the predicted Q value was  
  > **username_0**: Your right, I edited the Acgtions taken, What are endflag and nextstatelabel?  
  > **username_2**: `state_label` and `next_state_label` identify the states in the trajectory - it is implied in your question but not stated that your neural network estimates $(q(s, a_0), q(s, a_1), q(s, a_2), q(s, a_3) )$, and we need to know $s$. It is $q(s,a)$ that you revise, using $\text{max}_{a'} q(s',a')$ to improve the estimate, so you need to identify $s$ (`state_label`), $s'$ (`next_state_label`) and $a$. The `end_flag` is boolean - whether the transition ends an episode - that is critical information on how you learn Q values, because $\text{max}_{a'} q(s',a')$ is by definition $0$ in that case  
  > **username_0**: I understood the end_flag. But I think I do not understand the state label. For what do you need the states again? Just to recalculate the error of the net. (see above)  
  > **username_2**: The ids of the states are needed to explain how the formula works. They are used both for calculating the new target value, and for showing *which* Q value is being updated. References to different states are used in different parts of the same step, so it is important to make it clear which state is being used and why.  
  > **username_2**: If your examples are sequential from the same trajectory (looks like they are), then you will end up with repeats, so first time step might have `state_label` $s_a$ and  `next_state_label` $s_b$ then the second time step might have  `state_label` $s_b$ and  `next_state_label` $s_c$ etc - or you could make up a state vector for each one (because that's what you'd have for input to the NN). I am asking because I want you to add this information in the way that *you* understand it, so that the answer can explain things to you in your own terms.  
  > **username_0**: I have added the stated. Can you now explain it to me?  
  > **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/87855/discussion-between-tvsuchty-and-neil-slater).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2019-01-05. Score: 3 | Accepted answer
  
  Most Deep Q-learning implementations I have read are based on Deep Q-Networks (DQN).  In DQN, the q-value network maps an input state to a vector of q-values, one for each action:
  $$
  Q(s, \mathbf{w}) \to \mathbf{v}
  $$
  where $s$ is the input state from the environment, $\mathbf{w}$ are the parameters of the neural network, and $\mathbf{v}$ is a vector of q-values, where $v_i$ is the estimated q-value of the ith action. In the Sutton and Barto book, the q-value function is written as $Q(s, a, \mathbf{w})$, which corresponds to the network output for action $a$.
  Unlike tabular Q-learning, Deep Q-learning updates the parameters of the the neural network according to the gradients of the loss function with respect to the parameters. DQN uses the loss function
  $$
  L(\mathbf{w}) = [(r + \gamma max_{a'} Q(s', a', \mathbf{w^-})) - Q(s, a, \mathbf{w})]^2
  $$
  where $\gamma$ is the discount rate, $a$ is the selected action (either greedily or randomly for an $epsilon$-greedy behavior policy), $s'$ is the next state, $a'$ is the argmax action for the next state, and $\mathbf{w^-}$ is an older version of the network weights $\mathbf{w}$ that is used to help stabilize training.
  In deep Q-learning, training directly updates parameters, not q-values. Parameters are updated by taking a small step in the direction of the gradient of the loss function
  $$
  \mathbf{w} \gets \mathbf{w} + \alpha [(r + \gamma max_{a'} Q(s', a', \mathbf{w^-})) - Q(s, a, \mathbf{w})] \nabla_w Q(s, a, \mathbf{w})
  $$
  where $\alpha$ is the learning rate.
  In frameworks like tensorflow or pytorch the derivative is calculated automatically by giving the loss function and model parameters directly to an optimizer class which uses some variation of mini-batch gradient descent. In eagerly executed tensorflow updating the parameters for a mini-batch might look something like
  batch = buffer.sample(batch_size)
  observations, actions, rewards, next_obervations = batch
  
  with tf.GradientTape() as tape:
      qvalues = model(observations, training=True)
      next_qvalues = target_model(next_obervations)
      # r + max_{a'} Q(s', a') for the batch
      target_qvalues = rewards + gamma * tf.reduce_max(next_qvalues, axis=-1)
      # Q(s, a) for the batch
      selected_qvalues = tf.reduce_sum(tf.one_hot(actions, depth=qvalues.shape[-1]) * qvalues, axis=-1)
      loss = tf.reduce_mean((target_qvalues - selected_qvalues)**2)
  
  grads = tape.gradient(loss, model.variables)
  optimizer.apply_gradients(zip(grads, model.variables))
  
  Though I am not familiar with the Encog neural network framework you are using, based on the example Brain.java file from your Github repo and Chapter 5 of the Encog User Manual and the Encog neural network examples on Github it looks like weights are updated as follows:
  
  A training set is constructed from pairs of input and target output.
  A Propagation instance, train, is constructed with a network and training set. Different subclasses of Propagation use different loss functions to update the network parameters.
  The method train.iterate() is called to run the network on the inputs, calculate the loss between the network outputs and target outputs, and update the weights according to the loss.
  
  For DQN, a training set is constructed from a random sample from the experience replay buffer to help stabilize training. A training set could also be the trajectory of an episode, which is what the tupels argument in the example code of the question appears to be.
  The input would be the statefirst member of each element of tupels. Since the network produces a vector of q-values, the target output must also be a vector of q-values. 
  The target output element for the selected action is $r + \gamma max_{a'} Q(s', a', \mathbf{w^-})$,  In the example code of the question, this is
  double qnew = 0;
  if(i <= tupels.size()-2){
      qnew = tupels.get(i).rewardafter + discountfactor*qMax(tupels.get(i+1));
  } else {
      qnew = tupels.get(i).rewardafter;
  }
  tupels.get(i).qactions.elements[tupels.get(i).actionTaken] = qnew
  
  The target output elements for actions that were not selected should be $Q(s, b, \mathbf{w})$, where $b$ is one of the non-selected actions.  This should have the effect of ignoring the q-values of non-selected actions by making the network output equal to the target output.
  So what are the new Q - Values, assuming a discount factor of 0.99 and the learning rate 0.1?
  Assuming you mean target outputs by the new Q - Values, and given the trajectory of actions, (1, 1, 1), and q-value vectors from the question, the concrete target outputs are (0, 0 + 0.99 * 0, -5, 0), (0, 0 + 0.99 * 0, 0, 0), and (0, 1 + 0, 0, 0).
  
  > **Comments:**
  > **username_0**: $$w←w+α[(r+γmaxa′Q(s′,a′,w−))−Q(s,a,w)]∇wQ(s,a,w)$$ Does this mean I have to hold always an older version of the network?  I do not understand this. I understand what the loss function does. It is the normal loss function for most BP-algorithms. But how to calculate:  $$maxa′Q(s′,a′,w−))$$  
  > **username_3**: Yes, the DQN method uses an older version of the model which gets replaced every N time steps by the current model. According to the paper this improves training.  
  > **username_3**: You could calculate $max_{a'} Q(s', a', w^-)$ by running the state s' through an older copy of the model (i.e. the target network) and choosing the max of the outputs.  
  > **username_0**: Unfortunately, this still does not work. Is there anything else to consider. I must have done an obvious mistake.  
  
  ---
  
  