Answers.Body: <p>When you make updates in-place, then <em>some</em> of the entries in <code>state_values[next_i, next_j]</code> that you are referencing here</p>
  <pre><code>value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
  </code></pre>
  <p>will already be updated earlier in the same loop. Which means you get to use the latest and likely more accurate values earlier.</p>
  <p>The strength of this effect varies depending on the order that states and actions are visited. If you can manage to visit them in reverse order that they would appear in natural trajectories, then the speed improvement will be very noticeable.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-02T21:01:01.713Z
Answers.LastActivityDate: 2021-02-02T21:01:01.713Z
Answers.UserDisplayName: Neil Slater
Body: <p>In <a href="http://incompleteideas.net/book/RLbook2020.pdf#page=97" rel="nofollow noreferrer">Barto and Sutton's book</a>, it's written that we have two types of updates in dynamic programming</p>
  <ol>
  <li>Update out-of-place</li>
  <li>Update in-place</li>
  </ol>
  <p>The update in-place is the faster one. Why is that the case?</p>
  <p>This is the pseudocode that I used to test it.</p>
  <pre><code>if in_place:
      state_values = new_state_values
  else:
      state_values = new_state_values.copy()
  old_state_values = state_values.copy()
  
  for i in range(WORLD_SIZE):
      for j in range(WORLD_SIZE):
          value = 0
          for action in ACTIONS:
              (next_i, next_j), reward = step([i, j], action)
              value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
          new_state_values[i, j] = value
  
  max_delta_value = abs(old_state_values - new_state_values).max()
  if max_delta_value &lt; 1e-4:
      break
  </code></pre>
  <p>Why is the in-place version faster, and what is the difference? What I think is that it is only better for storage usage, I don't understand the speed increase part.</p>
  
Tags: <reinforcement-learning><sutton-barto><policy-evaluation><dynamic-programming>
Title: Why is the update in-place faster than the out-of-place one in dynamic programming?
UserDisplayName: VanasisB
ThreadText: # Why is the update in-place faster than the out-of-place one in dynamic programming?
  
  (Asked by: username_0 on 2021-02-02)
  
  In Barto and Sutton's book, it's written that we have two types of updates in dynamic programming
  
  Update out-of-place
  Update in-place
  
  The update in-place is the faster one. Why is that the case?
  This is the pseudocode that I used to test it.
  if in_place:
      state_values = new_state_values
  else:
      state_values = new_state_values.copy()
  old_state_values = state_values.copy()
  
  for i in range(WORLD_SIZE):
      for j in range(WORLD_SIZE):
          value = 0
          for action in ACTIONS:
              (next_i, next_j), reward = step([i, j], action)
              value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
          new_state_values[i, j] = value
  
  max_delta_value = abs(old_state_values - new_state_values).max()
  if max_delta_value < 1e-4:
      break
  
  Why is the in-place version faster, and what is the difference? What I think is that it is only better for storage usage, I don't understand the speed increase part.
  
  **Tags:** reinforcement-learning, sutton-barto, policy-evaluation, dynamic-programming
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-02-02. Score: 0 | Accepted answer
  
  When you make updates in-place, then some of the entries in state_values[next_i, next_j] that you are referencing here
  value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
  
  will already be updated earlier in the same loop. Which means you get to use the latest and likely more accurate values earlier.
  The strength of this effect varies depending on the order that states and actions are visited. If you can manage to visit them in reverse order that they would appear in natural trajectories, then the speed improvement will be very noticeable.
  
  
  ---
  
  