Answers.Body: <p>Your pseudocode is fairly close to something that could be implemented. There are a couple of omissions, where it is not clear whether your implementation would do the right thing. There are a few non-general assumptions that are worth noting - they don't prevent you implementing for a specific purpose, but do prevent you writing the most generic DQN that you could. There is one mistake that prevents it working at all.</p>
  
  <p>Your mistake is here:</p>
  
  <blockquote>
    <p><code>Do gradient step where error = (y - max(q1))^2, only the max of q1 gets any gradient</code></p>
  </blockquote>
  
  <p>The loss function and gradient must be applied to the state/action pair <code>s1, a1</code>, i.e. the action that was taken. This is an important distinction for when the agent takes exploratory (non-greedy) actions, as it must if it is going to learn about their values.</p>
  
  <p>A corrected statement might read: <code>Do gradient step where error = (y - Q(s1,a1))^2, only the output for a1 gets any gradient</code>.</p>
  
  <hr>
  
  <p>Regarding the rest of the pseudocode I could make the following observations:</p>
  
  <blockquote>
    <p><code>The state, s1, is initialised randomly</code></p>
  </blockquote>
  
  <p>This is fine if it is possible. However, it is more usual in Q learning to initialise the state to whatever the normal start of the episode would be. That <em>might</em> be from some randomised starting rules, but that is not quite the same as 
  picking a random state from all possible states.</p>
  
  <blockquote>
    <p><code>action a1 is chosen based off the max of q1 (or randomly)</code></p>
  </blockquote>
  
  <p>It is not quite clear what you mean by "or randomly". For Q learning - and most RL - exploration is important. So this is not a design time choice for your algorithm, but a runtime choice that must itself be made so that all actions can be tried. Typically you would use an <span class="math-container">$\epsilon$</span>-greedy policy here that took the argmax action by default, but with probability <span class="math-container">$\epsilon$</span> took a random sample from actions with same chance of each possible action.</p>
  
  <blockquote>
    <p><code>state s2 is found by progressing s1 based on a1</code></p>
  </blockquote>
  
  <p>This is one of a few places where you have not quite captured the nature of a time step in a general MDP. You appear to have made the assumption that rewards are directly associated with states (with language like "reward at s2"). Whilst some MDPs are like that, it is not true in general.</p>
  
  <p>A better, more general statement might be:</p>
  
  <p><code>s2, reward, done are found by taking a step from s1, using a1 as the action</code></p>
  
  <p>Typically the environment (or a wrapper for it that establishes state representations and rewards) will provide a step method that returns the tuple <span class="math-container">$s_{t+1}, r_{t+1}, (s_{t+1} = s_T)$</span>, although you could also hold these values in the environment model for the current time step and return them as required.</p>
  
  <p>This statement:</p>
  
  <blockquote>
    <p><code>(The "otherwise" doesn't match bellmans equation as α=1)</code></p>
  </blockquote>
  
  <p>I don't know which Bellman equation you are referring to, but they don't include a learning rate, <span class="math-container">$\alpha$</span> in any version I have seen. Perhaps you are referring to a tabular Q learning update? In any case, it doesn't seem relevant, as whatever learning rate you are using is now inside the gradient step, and does not need to be part of the pseuodcode.</p>
  
  <p>Finally, regarding this:</p>
  
  <blockquote>
    <p>I am also not taking into account storing network states (in this case, the network is called Q) for proper learning to avoid catastrophic forgetting, as I'm more concerned on getting the specifics right before good practice.</p>
  </blockquote>
  
  <p>DQN will very likely not work at all, for most environments, unless you implement experience replay i.e. training the neural network on a random sample of stored <code>s1,a1,r,s2,done</code> taken from a table that you build up on each time step. Usually you <em>cannot</em> simply use the latest data from the current step. This is not just "good practice", but an almost-always necessary stability improvement.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T14:31:31.177Z
Answers.Text: Thank you so much for addressing each point with such detail. It is to my knowledge that for each state (for example s1), it is fed through the neural network, and the network then returns the Q values for every action possible at that state, in my case I referred to this array as q1. Is this correct?
Answers.UserDisplayName: Recessive
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T14:33:38.737Z
Answers.Text: @Recessive yes that is a common approach, as it is more efficient to use and train than the alternative which is a NN that directly implements Q(s,a) with both s and a as inputs with a single value output. However, the latter approach is also viable and correct in theory.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T14:35:38.327Z
Answers.Text: as for `state s2 is found by progressing s1 based on a1`, I am still a little bit confused. In order to find the Q values for each action that could be taken at the state that would follow after taking action `a1`, isn't it necessary to feed the new state into the neural network in order to get these values (or q2)? So would this not mean you have to progress the state forward? And I think I understand what you mean about my misconception of a state having an associated reward. Am I correct in saying that, it is instead rather a specific *action* at a state is what has the associated reward?
Answers.UserDisplayName: Recessive
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T14:38:03.787Z
Answers.Text: @Recessive: All of current state, action, next state and a random factor may influence reward. Which of these are used depends on your problem. That is why the most general approach to capturing the results of an action is to have something like `next_state, reward, done = env.step(action)`
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T14:39:54.133Z
Answers.Text: Ahh that makes sense. However, I'm not sure what the variable `done` is referring to?
Answers.UserDisplayName: Recessive
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T14:41:22.670Z
Answers.Text: Just a flag as to whether `s2` is a terminal state. It is possible that the state features don't include whether or not the state is terminal (this is never going to be used to drive any approximation, as will always be `False` when you feed to a NN - when `True` then $Q(s_2,\cdot) = 0$ by definition), so it is a matter of convenience. You may be able to avoid it in your case, but if you want to work with Open AI gym for instance, it uses this convention
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-09T10:52:49.340Z
Answers.LastActivityDate: 2019-12-09T14:36:00.783Z
Answers.LastEditDate: 2019-12-09T14:36:00.783Z
Answers.UserDisplayName: Neil Slater
Body: <p>I just wanted to confirm that my understanding of Q learning was correct (with respect to a neural network).</p>
  
  <pre><code>The network, Q, is initialised randomly.
  for n "episodes":
      The state, s1, is initialised randomly
      while s1 != terminal state:
          s1 is fed into Q to get action vector q1
          action a1 is chosen based off the max of q1 (or randomly)
          state s2 is found by progressing s1 based on a1
  
          s2 is fed into Q to get action vector q2
  
          The expected output for Q at q1, y, is found by:
          {If s2 is terminal, it is the reward at s2
          {Otherwise: reward at s2 + gamm*max(q2)
          (The "otherwise" doesn't match bellmans equation as α=1)
  
          Do gradient step where error = (y - max(q1))^2, only the max of q1 gets any gradient
          s1 = s2
  </code></pre>
  
  <p>This does not directly follow equations found by searching Q-learning as I find them rather ambiguous.</p>
  
  <p>I am also not taking into account storing network states (in this case, the network is called Q) for proper learning to avoid catastrophic forgetting, as I'm more concerned on getting the specifics right before good practice.</p>
  
Tags: <neural-networks><q-learning>
Title: Is the following the correct implementation of the Q learning algorithm for a neural network?
UserDisplayName: Recessive
ThreadText: # Is the following the correct implementation of the Q learning algorithm for a neural network?
  
  (Asked by: username_0 on 2019-12-09)
  
  I just wanted to confirm that my understanding of Q learning was correct (with respect to a neural network).
  The network, Q, is initialised randomly.
  for n "episodes":
      The state, s1, is initialised randomly
      while s1 != terminal state:
          s1 is fed into Q to get action vector q1
          action a1 is chosen based off the max of q1 (or randomly)
          state s2 is found by progressing s1 based on a1
  
          s2 is fed into Q to get action vector q2
  
          The expected output for Q at q1, y, is found by:
          {If s2 is terminal, it is the reward at s2
          {Otherwise: reward at s2 + gamm*max(q2)
          (The "otherwise" doesn't match bellmans equation as α=1)
  
          Do gradient step where error = (y - max(q1))^2, only the max of q1 gets any gradient
          s1 = s2
  
  This does not directly follow equations found by searching Q-learning as I find them rather ambiguous.
  I am also not taking into account storing network states (in this case, the network is called Q) for proper learning to avoid catastrophic forgetting, as I'm more concerned on getting the specifics right before good practice.
  
  **Tags:** neural-networks, q-learning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-12-09. Score: 1 | Accepted answer
  
  Your pseudocode is fairly close to something that could be implemented. There are a couple of omissions, where it is not clear whether your implementation would do the right thing. There are a few non-general assumptions that are worth noting - they don't prevent you implementing for a specific purpose, but do prevent you writing the most generic DQN that you could. There is one mistake that prevents it working at all.
  
  Your mistake is here:
  
  > `Do gradient step where error = (y - max(q1))^2, only the max of q1 gets any gradient`
  
  The loss function and gradient must be applied to the state/action pair `s1, a1`, i.e. the action that was taken. This is an important distinction for when the agent takes exploratory (non-greedy) actions, as it must if it is going to learn about their values.
  
  A corrected statement might read: `Do gradient step where error = (y - Q(s1,a1))^2, only the output for a1 gets any gradient`.
  
  ---
  
  Regarding the rest of the pseudocode I could make the following observations:
  
  > `The state, s1, is initialised randomly`
  
  This is fine if it is possible. However, it is more usual in Q learning to initialise the state to whatever the normal start of the episode would be. That *might* be from some randomised starting rules, but that is not quite the same as
  picking a random state from all possible states.
  
  > `action a1 is chosen based off the max of q1 (or randomly)`
  
  It is not quite clear what you mean by "or randomly". For Q learning - and most RL - exploration is important. So this is not a design time choice for your algorithm, but a runtime choice that must itself be made so that all actions can be tried. Typically you would use an $\epsilon$-greedy policy here that took the argmax action by default, but with probability $\epsilon$ took a random sample from actions with same chance of each possible action.
  
  > `state s2 is found by progressing s1 based on a1`
  
  This is one of a few places where you have not quite captured the nature of a time step in a general MDP. You appear to have made the assumption that rewards are directly associated with states (with language like "reward at s2"). Whilst some MDPs are like that, it is not true in general.
  
  A better, more general statement might be:
  
  `s2, reward, done are found by taking a step from s1, using a1 as the action`
  
  Typically the environment (or a wrapper for it that establishes state representations and rewards) will provide a step method that returns the tuple $s\_{t+1}, r\_{t+1}, (s\_{t+1} = s\_T)$, although you could also hold these values in the environment model for the current time step and return them as required.
  
  This statement:
  
  > `(The "otherwise" doesn't match bellmans equation as α=1)`
  
  I don't know which Bellman equation you are referring to, but they don't include a learning rate, $\alpha$ in any version I have seen. Perhaps you are referring to a tabular Q learning update? In any case, it doesn't seem relevant, as whatever learning rate you are using is now inside the gradient step, and does not need to be part of the pseuodcode.
  
  Finally, regarding this:
  
  > I am also not taking into account storing network states (in this case, the network is called Q) for proper learning to avoid catastrophic forgetting, as I'm more concerned on getting the specifics right before good practice.
  
  DQN will very likely not work at all, for most environments, unless you implement experience replay i.e. training the neural network on a random sample of stored `s1,a1,r,s2,done` taken from a table that you build up on each time step. Usually you *cannot* simply use the latest data from the current step. This is not just "good practice", but an almost-always necessary stability improvement.
  
  > **Comments:**
  > **username_0**: Thank you so much for addressing each point with such detail. It is to my knowledge that for each state (for example s1), it is fed through the neural network, and the network then returns the Q values for every action possible at that state, in my case I referred to this array as q1. Is this correct?  
  > **username_1**: @Recessive yes that is a common approach, as it is more efficient to use and train than the alternative which is a NN that directly implements Q(s,a) with both s and a as inputs with a single value output. However, the latter approach is also viable and correct in theory.  
  > **username_0**: as for `state s2 is found by progressing s1 based on a1`, I am still a little bit confused. In order to find the Q values for each action that could be taken at the state that would follow after taking action `a1`, isn't it necessary to feed the new state into the neural network in order to get these values (or q2)? So would this not mean you have to progress the state forward? And I think I understand what you mean about my misconception of a state having an associated reward. Am I correct in saying that, it is instead rather a specific *action* at a state is what has the associated reward?  
  > **username_1**: @Recessive: All of current state, action, next state and a random factor may influence reward. Which of these are used depends on your problem. That is why the most general approach to capturing the results of an action is to have something like `next_state, reward, done = env.step(action)`  
  > **username_0**: Ahh that makes sense. However, I'm not sure what the variable `done` is referring to?  
  > **username_1**: Just a flag as to whether `s2` is a terminal state. It is possible that the state features don't include whether or not the state is terminal (this is never going to be used to drive any approximation, as will always be `False` when you feed to a NN - when `True` then $Q(s_2,\cdot) = 0$ by definition), so it is a matter of convenience. You may be able to avoid it in your case, but if you want to work with Open AI gym for instance, it uses this convention  
  
  ---
  
  