Answers.Body: <p>Your problem is not that the environment is stochastic or dynamic. In fact you are using the terms slightly incorrectly. These terms do not usually refer to the fact that starting state can differ or goal locations can move episode-by-episode. They typically refer to behaviour of state transitions. </p>
  
  <p>Although in your case you could view the initial state as stochastic, this is not a big deal, and not likely to be the cause of your problems.</p>
  
  <p>From your questions, it seems to me that you are not really running a DQN algorithm yet. It is not 100% clear what your neural network is predicting, but my best guess is that you have 4 outputs to select "best" action and are treating the neural network as a classifier. This training approach seems closest to <a href="https://en.wikipedia.org/wiki/Cross-entropy_method" rel="nofollow noreferrer">Cross Entropy Method (CEM)</a> due to how you are selecting "successful" navigation only.</p>
  
  <blockquote>
    <p>When training the DQN, how do i apply Q-values?</p>
  </blockquote>
  
  <p>This question is the most revealing that you are not using DQN. This is too complex to describe in full in an answer, but the basics are:</p>
  
  <ul>
  <li><p>Your neural network (NN) should be estimating Q values. Typically in DQN, you input the state and the NN outputs an array of estimates for Q of each action (although other architectures are possible). This should be a regression problem, so last layer of network needs to be linear.</p></li>
  <li><p>Current best guess of optimal policy is to run the NN forward and find the maximising action. </p></li>
  <li><p>In DQN you also have a "behaviour policy" - a simple and popular choice is to use <span class="math-container">$\epsilon$</span>-greedy action selection, which just means to take the maximising action (as calculated above), except with probability <span class="math-container">$\epsilon$</span> (some small value, e.g. 0.1) to take a random action.</p></li>
  <li><p>To figure out your training data to improve the NN, you need Q values to calculate a TD Target. In single-step Q learning that would be <span class="math-container">$r + \gamma Q(s',a*)$</span> where <span class="math-container">$r$</span> is the immediate reward <span class="math-container">$s'$</span> is the next state seen, and <span class="math-container">$a*$</span> is the maximising action in that state. You should force <span class="math-container">$Q(s', a*) = 0$</span> (i.e. not use the NN) if <span class="math-container">$s'$</span> is a terminal state.</p></li>
  </ul>
  
  <p>This means you typically need to work with Q values in 2 or 3 places in your inner loop. Your inner loop should look <em>something</em> like this per time step, given a current state <code>current_state</code>:</p>
  
  <pre><code># Figure out how to act
  current_q_values = NN_predict(current_state)
  current_action = argmax(current_q_values)
  if random() &lt; epsilon:
    current_action = random_action()
  
  # Take an action
  reward, next_state, done = call_environment(current_state, current_action)
  
  # Remember what happened
  store_in_replay_memory(current_state, current_action, reward, next_state, done)
  
  # Train the NN from memory
  repeat N times: # This can be vectorised for efficiency
    mem_state, mem_action, mem_reward, mem_next_state, mem_done = sample_replay_memory()
    mem_q_values = NN_predict(mem_next_state)
    mem_max_action = argmax(mem_q_values)
    if done:
      td_target = mem_reward
    else
      td_target = mem_reward + gamma * mem_q_values[mem_max_action]
    target_q_values = NN_predict(mem_state)
    target_q_values[mem_action] = td_target
    NN_train(mem_state, target_q_values)
  
  # Maybe end an episode (this can include generating new map)
  if done:
    current_state = reset_environment()
  else:
    current_state = next_state
  </code></pre>
  
  <p>You can see above, <code>NN_predict</code> is called three different times to get Q values in slightly different contexts. I have ignored extras such as using a separate target network.</p>
  
  <blockquote>
    <p>I train the network using only a short replay memory of the last move, or the last N moves that led to success. Is this the right way to approach this?</p>
  </blockquote>
  
  <p>It is important to include moves that lead to failure so that the NN learns the difference. Typically you will need a replay memory with from a few hundred to a few hundred thousand entries. You would get away with a few hundred perhaps for your simple problem. The idea is to use this training data a bit like a dataset from supervised learning.</p>
  
  <blockquote>
    <p>I use Keras, and am simply training the network every time it does something right - and ignoring failed attempts. - But is this anywhere near the right approach?</p>
  </blockquote>
  
  <p>This is not the right approach for DQN, although perhaps could be considered a crude version of CEM.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-01T22:41:37.477Z
Answers.Text: Thanks a bunch for the greatly detailed answer. It’s highly appreciated. I will go over every one of the details you describe in your post, as i’ve had a really hard time understanding these networks properly. I get the normal NNs and the normal Q-learning, but not the DQNs, so admittedly i am fumbling my way through the jungle herr. - I hope that going meticulously through the details in your answer, will help me on this path. Thanks again.
Answers.UserDisplayName: skywalkerdk
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-01T16:28:00.267Z
Answers.LastActivityDate: 2019-07-01T16:28:00.267Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm trying to apply a DQN to a stochastic environment, but I'm having trouble getting it to converge.</p>
  <p>I found some similar questions asked here, but no solutions yet.</p>
  <p>I can easily get the DQN to converge on a static environment, but I am having trouble with a dynamic environment where the end is not given.</p>
  <p>Example: I have made a really simple model of the Frozen Lake (without any holes) - simply navigation from A to B. This navigation works fine when A and B are always the same, but when I shuffle the position of A or B for each session, the DQN cannot converge properly.</p>
  <p>I am using the grid (3x3, 4x4 sizes) as input neurons. Each with &quot;0&quot; value. I assign the current position &quot;0.5&quot; and the end position &quot;1&quot;. 4x4 grid gives us 16 input neurons. Example of 3x3 grid:</p>
  <pre><code> 0.5  0  0 
    0   0  0 
    0   0  1
  </code></pre>
  <p>I have a few questions in this regard:</p>
  <ul>
  <li><p>When training the DQN, how do I apply Q-values? (Or do I really need to? I'm not sure how to correctly &quot;reward&quot; the network. I'm not using any adversarial network or target network at this point.)</p>
  </li>
  <li><p>I train the network using only a short replay memory of the last move, or the last N moves that led to success. Is this the right way to approach this?</p>
  </li>
  <li><p>I use Keras, and am simply training the network every time it does something right - and ignoring failed attempts. - But is this anywhere near the right approach?</p>
  </li>
  <li><p>Am I missing something else?</p>
  </li>
  </ul>
  <p>Perhaps I should note that my math skills are not that strong, but I try my best.</p>
  <p>Any input is appreciated.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-01T12:40:03.583Z
Comments.Text: Please clarify what your state representation is in the modified environment. I think this will be critical to explanations of why it doesn't work. I *think* you are still using the basic grid position as state?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-01T12:41:19.920Z
Comments.Text: Also please clarify your first question. What do you mean by "apply Q-values" - what process or calculation are you wondering about?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-01T12:51:17.377Z
Comments.Text: Thanks, the edit is really useful, and I was wrong in my assumption about the state. I think your state representation is workable (although maybe not the fastest, it *should* work)
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-07-01T12:51:54.617Z
Comments.Text: Thanks, i have tried to clarify it above. Yes, i am using the grid as state. - By Q-value i mean, i'm a bit unsure of how to correctly use reward policies in the DQN. At present, i do not use any Q-values at all, but only train the network when it does something successful. (Finds the route) - But is this a good way to approach this, or should i use more nuances somehow? (I know it's kind of simple, but it works for grid where the goal-position is static)
Comments.UserDisplayName: skywalkerdk
Tags: <deep-learning><reinforcement-learning><python><dqn>
Title: Why does the DQN not converge when the start or goal states can change dynamically?
UserDisplayName: skywalkerdk
ThreadText: # Why does the DQN not converge when the start or goal states can change dynamically?
  
  (Asked by: username_0 on 2019-07-01)
  
  I'm trying to apply a DQN to a stochastic environment, but I'm having trouble getting it to converge.
  I found some similar questions asked here, but no solutions yet.
  I can easily get the DQN to converge on a static environment, but I am having trouble with a dynamic environment where the end is not given.
  Example: I have made a really simple model of the Frozen Lake (without any holes) - simply navigation from A to B. This navigation works fine when A and B are always the same, but when I shuffle the position of A or B for each session, the DQN cannot converge properly.
  I am using the grid (3x3, 4x4 sizes) as input neurons. Each with "0" value. I assign the current position "0.5" and the end position "1". 4x4 grid gives us 16 input neurons. Example of 3x3 grid:
   0.5  0  0 
    0   0  0 
    0   0  1
  
  I have a few questions in this regard:
  
  When training the DQN, how do I apply Q-values? (Or do I really need to? I'm not sure how to correctly "reward" the network. I'm not using any adversarial network or target network at this point.)
  
  I train the network using only a short replay memory of the last move, or the last N moves that led to success. Is this the right way to approach this?
  
  I use Keras, and am simply training the network every time it does something right - and ignoring failed attempts. - But is this anywhere near the right approach?
  
  Am I missing something else?
  
  
  Perhaps I should note that my math skills are not that strong, but I try my best.
  Any input is appreciated.
  
  **Tags:** deep-learning, reinforcement-learning, python, dqn
  > **Comments:**
  > **username_1**: Please clarify what your state representation is in the modified environment. I think this will be critical to explanations of why it doesn't work. I *think* you are still using the basic grid position as state?  
  > **username_1**: Also please clarify your first question. What do you mean by "apply Q-values" - what process or calculation are you wondering about?  
  > **username_1**: Thanks, the edit is really useful, and I was wrong in my assumption about the state. I think your state representation is workable (although maybe not the fastest, it *should* work)  
  > **username_0**: Thanks, i have tried to clarify it above. Yes, i am using the grid as state. - By Q-value i mean, i'm a bit unsure of how to correctly use reward policies in the DQN. At present, i do not use any Q-values at all, but only train the network when it does something successful. (Finds the route) - But is this a good way to approach this, or should i use more nuances somehow? (I know it's kind of simple, but it works for grid where the goal-position is static)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-07-01. Score: 3 | Accepted answer
  
  Your problem is not that the environment is stochastic or dynamic. In fact you are using the terms slightly incorrectly. These terms do not usually refer to the fact that starting state can differ or goal locations can move episode-by-episode. They typically refer to behaviour of state transitions. 
  Although in your case you could view the initial state as stochastic, this is not a big deal, and not likely to be the cause of your problems.
  From your questions, it seems to me that you are not really running a DQN algorithm yet. It is not 100% clear what your neural network is predicting, but my best guess is that you have 4 outputs to select "best" action and are treating the neural network as a classifier. This training approach seems closest to Cross Entropy Method (CEM) due to how you are selecting "successful" navigation only.
  
  When training the DQN, how do i apply Q-values?
  
  This question is the most revealing that you are not using DQN. This is too complex to describe in full in an answer, but the basics are:
  
  Your neural network (NN) should be estimating Q values. Typically in DQN, you input the state and the NN outputs an array of estimates for Q of each action (although other architectures are possible). This should be a regression problem, so last layer of network needs to be linear.
  Current best guess of optimal policy is to run the NN forward and find the maximising action. 
  In DQN you also have a "behaviour policy" - a simple and popular choice is to use $\epsilon$-greedy action selection, which just means to take the maximising action (as calculated above), except with probability $\epsilon$ (some small value, e.g. 0.1) to take a random action.
  To figure out your training data to improve the NN, you need Q values to calculate a TD Target. In single-step Q learning that would be $r + \gamma Q(s',a*)$ where $r$ is the immediate reward $s'$ is the next state seen, and $a*$ is the maximising action in that state. You should force $Q(s', a*) = 0$ (i.e. not use the NN) if $s'$ is a terminal state.
  
  This means you typically need to work with Q values in 2 or 3 places in your inner loop. Your inner loop should look something like this per time step, given a current state current_state:
  # Figure out how to act
  current_q_values = NN_predict(current_state)
  current_action = argmax(current_q_values)
  if random() < epsilon:
    current_action = random_action()
  
  # Take an action
  reward, next_state, done = call_environment(current_state, current_action)
  
  # Remember what happened
  store_in_replay_memory(current_state, current_action, reward, next_state, done)
  
  # Train the NN from memory
  repeat N times: # This can be vectorised for efficiency
    mem_state, mem_action, mem_reward, mem_next_state, mem_done = sample_replay_memory()
    mem_q_values = NN_predict(mem_next_state)
    mem_max_action = argmax(mem_q_values)
    if done:
      td_target = mem_reward
    else
      td_target = mem_reward + gamma * mem_q_values[mem_max_action]
    target_q_values = NN_predict(mem_state)
    target_q_values[mem_action] = td_target
    NN_train(mem_state, target_q_values)
  
  # Maybe end an episode (this can include generating new map)
  if done:
    current_state = reset_environment()
  else:
    current_state = next_state
  
  You can see above, NN_predict is called three different times to get Q values in slightly different contexts. I have ignored extras such as using a separate target network.
  
  I train the network using only a short replay memory of the last move, or the last N moves that led to success. Is this the right way to approach this?
  
  It is important to include moves that lead to failure so that the NN learns the difference. Typically you will need a replay memory with from a few hundred to a few hundred thousand entries. You would get away with a few hundred perhaps for your simple problem. The idea is to use this training data a bit like a dataset from supervised learning.
  
  I use Keras, and am simply training the network every time it does something right - and ignoring failed attempts. - But is this anywhere near the right approach?
  
  This is not the right approach for DQN, although perhaps could be considered a crude version of CEM.
  
  > **Comments:**
  > **username_0**: Thanks a bunch for the greatly detailed answer. It’s highly appreciated. I will go over every one of the details you describe in your post, as i’ve had a really hard time understanding these networks properly. I get the normal NNs and the normal Q-learning, but not the DQNs, so admittedly i am fumbling my way through the jungle herr. - I hope that going meticulously through the details in your answer, will help me on this path. Thanks again.  
  
  ---
  
  